{'fraction_non_alphanumeric': 0.03456336617131408, 'fraction_numerical': 0.01040797016752936, 'mean_word_length': 4.378030529781503, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Deep-learning based linear average consensus for faster convergence over temporal network

In this paper, we study the problem of accelerating the linear average consensus algorithm over complex networks. We specifically present a data-driven methodology for tuning the weights of temporal (i.e., time-varying) networks by using deep learning techniques. We first unfold the linear average consensus protocol to obtain a feedforward signal flow graph, which we regard as a neural network. We then train the neural network by using standard deep learning technique to minimize the consensus error over a given finite time-horizon. As a result of the training, we obtain a set of optimized timevarying weights for faster consensus in the network. Numerical simulations are presented to show that our methodology can achieve a significantly smaller consensus error than the static optimal strategy.

in [8] that the optimal weights can be computed in a distributed manner by an iterative computation. Zelazo et al. [9] clarified the role of cycles in the linear average consensus algorithm and presented a methodology for accelerating the consensus by adding edges to a network. On the other hand, for the case of directed networks, Hao and Barooah [10] presented a method to accelerate the convergence rate of a linear (but not necessarily an average) consensus algorithm by tuning the weights of edges in the network.
A natural consequence of seeking for further acceleration of consensus algorithms is the emergence of finite-time consensus algorithms [11], in which edge-weights are typically assumed to be time-varying and the designer exploits the additional flexibility to realize consensus in a finite-time. The finite-time consensus algorithm proposed in [12] achieves consensus by stochastic (but possibly asymmetric) matrices in N(N − 1)/2 iterations, where N denotes the number of nodes in the network. The authors in [13], [14] used tools from graph signal processing (see, e.g., [15]) to show that, by allowing non-stochasticity for the state-update matrices, one can realize a finite-time consensus in at most N steps. The theoretical aspects of these works have been further investigated in [16]. Recently, Falsone et al. [17] showed that the number of steps required for consensus can be further improved to N/2 in the specific case of ring networks having an even number of nodes.
Despite the aforementioned advances for consensus acceleration, there is still a lack of an effective methodology for answering the following basic question: Given a finite time-window as well as an underlying network structure, how should we dynamically tune the edge weights in the network for achieving as accurate consensus as possible at the end of the time-window? If the length of the timewindow is not long enough to run the aforementioned finitetime consensus algorithms, currently available options are effectively limited to using the static optimal strategies (e.g., [3]), which does not allow us to dynamically tune the weights of the network. To fill in this gap, in this paper we present a data-driven approach for tuning the weights of an undirected temporal (i.e., time-varying) networks by using deep learning techniques. We first unfold the consensus algorithm and obtain a feedforward signal flow graph [18], which we regard as a neural network. We then use the standard stochastic gradient descent algorithm to train the parameters in each layer of the neural network (i.e., the weights of each snapshot of the temporal network) to minimize the consensus error over a finite time-horizon, which results in an optimized temporal network for faster consensus. We numerically confirm that our approach can drastically accelerate the convergence speed in the linear average consensus algorithm. This paper is organized as follows. In Section II, we state the problem of dynamically tuning the edge weights to accelerate the linear average consensus algorithm, and then we propose our methodology for solving the problem using standard techniques in the field of deep learning. In Section III, we evaluate the performance of the proposed method with various numerical simulations. We finally conclude the paper in Section IV.

II. WEIGHT OPTIMIZATION BY DEEP LEARNING TECHNIQUES
In this section, we describe our methodology for tuning the edge weights of the networks for accelerating the linear average consensus algorithm within a given finite-time horizon. We first give a brief review of the linear average consensus algorithm and state its basic properties. We then describe our data-driven methodology for tuning the weights of the network, in which we apply the techniques in the deep-learning to the signal flow graph obtained by unfolding the consensus algorithm.

A. Linear average consensus algorithm
Let G be an undirected and unweighted network having the node set V = {1, . . . , N} and the edge set E consisting of unordered pairs of nodes in V . Each node in G represents an agent, which is supposed to communicate with its neighbors at each time. In this paper, we focus on the discrete-time case. Let x i (k) ∈ R denote the state of the ith node at time k ≥ 0, and N i denote the set of neighbors of node i. In the standard linear average consensus protocol [1], each node i updates its own state according to the following difference equation: where w i j (k) = w ji (k) ≥ 0 represents the weight of the (undirected) edge {i, j} at time k and x 0,i is the initial state of node i. For each time k ≥ 0, we define the adjacency matrix of the network W (k) ∈ R N×N by Define the degree matrix of the network at time k by Then, the evolution of the state vector in the linear average consensus protocol (1) is written as x(k + 1) = (I − L(k))x(k), is the Laplacian matrix of the network and denotes the initial state vector. The objective of this paper is to present a framework for tuning the weights {w i j (k)} k≥0,{i, j}∈E for the faster average consensus in a given finite time window. Let us denote the average of the initial states of the nodes by Define the consensus error vector where 1 denotes the all-one N-dimensional column vector.
We are now ready to state the problem studied in this paper. Problem 2.1 (Consensus acceleration problem): Let G be an undirected and unweighted network having N nodes. Let T be a positive integer. Assume that the set of initial states follow a probability distribution X 0 , i.e., Find the set of nonnegative weights that minimizes the average consensus error defined by where · denotes the Euclidean norm in R N , and E[·] denotes the expected value. Problem 2.1 is a non-convex problem and it is difficult to compute a set of {w i j (k)} k≥0,{i, j}∈E that minimizes γ T . This motivates us to tackle this problem using a datadriven approach to find a suboptimal solution. In the next subsection, we describe our data-driven approach for tuning the edge weights by using deep leaning techniques. We remark that, although we assume our knowledge of the initial probability distribution X 0 in the process of optimization, the optimized edge-weights can drastically accelerate the consensus protocol even if the initial states do not follow the given distribution. We numerically illustrate this universality property of our approach in Subsection III-D.

B. Data-driven weight optimization
To adjust the weights by using deep learning techniques, we first unfold the recursive state-update formula (1) and obtain a signal-flow graph shown in Fig. 1a. Unlike a standard deep neural network, the resulting neural network has a structure and contains no activation function. The structure of the neural network corresponds to the structure of the graph G, and the same between all layers. The neurons of kth layer corresponds to the nodes at time k as shown in Fig. 1b.
We then apply a standard technique in the field of deep learning to adjust the weights; namely, we train the network with a stochastic gradient descent algorithm such as SGD,  (1) for Signal flow graph obtained by unfolding the linear average consensus al- with a stochastic gradient descent algorithm such as SGD, RMSprop, or Adam. As in [18], we use the technique of the incremental training for adjusting the weights. In the incremental training, we first consider only the first layer (i.e., we set k = 1 in Fig. 1a) and attempt to minimize the loss function of the average consensus error γ 1 using a number of randomly generated initial state x 0 as the training data, which we call the 1st generation. After training the first set of weights w i j (0), we proceed to training the first two sets of edge weights by appending the second layer to the neural network and replacing the loss function by γ 2 . In this training, we use the result from the 1st generation as the initial value of the first layer and train the entire neural network. We repeat this process to finally optimize the weights w i j (T − 1) between T − 1st and T th layers.

III. PERFORMANCE EVALUATION
In this section, we illustrate the effectiveness of the proposed method by various numerical simulations. The simulations were performed in PyTorch [19]. The loss function is the mean squared error, γ 2 T , and the size of minibatch is one. We used Adam for the optimization with learning rate 0.01. The number of data-set per learning is 10000. For evaluations, 100 samples were used.

A. Baseline strategy
Throughout this section, we compare the performance of the proposed method with that of the static optimal strategy presented in [3]. Assume that the initial state x 0 is a deterministic vector. Let us further suppose that the edge weights the authors in [3] have shown that the problem of finding th edge weights minimizing the asymptotic convergence fact r asym = sup (1 reduces to solving a linear matrix inequality, which can b globally and efficiently solved [20]. As the baseline strateg we use the following time-invariant consensus protocol where the weights w stat i j are obtained from solving the line matrix inequality.

B. Deterministic networks
In this subsection, we use the following two empiric and synthetic deterministic networks; Karate network [2 (N = 34 nodes) and the square lattice (N = 6 2 = 36 nodes We assume that the initial state of each node independent follows a uniform distribution on the interval [−1, 1]. For Karate network, we set T = 5 and numerical optimize the edge weights of the networks at the tim k = 0, . . . , 4. In Fig. 4, we present the optimized weigh of edges in the network. We then empirically evaluate th average consensus error E[ e(k) ] for k = 0, . . . , 5. Th results are shown in Fig. 2. The accuracy of the consens archived by the proposed method is 10 times better than th static optimal policy. We observe that the weights of th network are changing in a non-trivial manner. It is wor noting that the weights at time k = 1 are relatively large RMSprop, or Adam. As in [18], we use the technique of the incremental training for adjusting the weights. In the incremental training, we first consider only the first layer (i.e., we set k = 1 in Fig. 1a) and attempt to minimize the loss function of the average consensus error γ 1 using a number of randomly generated initial state x 0 as the training data, which we call the 1st generation. After training the first set of weights w i j (0), we proceed to training the first two sets of edge weights by appending the second layer to the neural network and replacing the loss function by γ 2 .
In this training, we use the result from the 1st generation as the initial value of the first layer and train the entire neural network. We repeat this process to finally optimize the weights w i j (T − 1) between T − 1st and T th layers.

III. PERFORMANCE EVALUATION
In this section, we illustrate the effectiveness of the proposed method by various numerical simulations. The simulations were performed in PyTorch [19]. The loss function is the mean squared error, γ 2 T , and the size of minibatch is one. We used Adam for the optimization with learning rate 0.01. The number of data-set per learning is 10 000. For evaluations, 100 samples were used.

A. Baseline strategy
Throughout this section, we compare the performance of the proposed method with that of the static optimal strategy presented in [3]. Assume that the initial state x 0 is a deterministic vector. Let us further suppose that the edge weights w i j (k) does not depend on time k. Under these assumptions, the authors in [3] have shown that the problem of finding the edge weights minimizing the asymptotic convergence factor r asym = sup  (2) reduces to solving a linear matrix inequality, which can be globally and efficiently solved [20]. As the baseline strategy, we use the following time-invariant consensus protocol where the weights w stat i j are obtained from solving the linear matrix inequality.

B. Deterministic networks
In this subsection, we use the following two empirical and synthetic deterministic networks; Karate network [21] (N = 34 nodes) and the square lattice network (N = 6 2 = 36 nodes). We assume that the initial state of each node independently follows a uniform distribution on the interval [−1, 1].
For Karate network, we set T = 5 and numerically optimize the edge weights of the networks at the times k = 0, . . . , 4. In Fig. 2, we present the optimized weights of edges in the network. We then empirically evaluate the average consensus error E[ e(k) ] for k = 0, . . . , 5. The results are shown in Fig. 3. The accuracy of the consensus archived by the proposed method is 10 times better than the static optimal policy. We observe that the weights of the network are changing in a non-trivial manner. It is worth noting that the weights at time k = 1 are relatively large at various edges in the network. This sudden increase in edge weights in fact drives the nodes away from the consensus state but only temporarily. In Fig. 4, we show the sample trajectories of the average consensus protocol with the static optimal and proposed edge weights. We confirm that the proposed edge weights achieves a more precise average consensus at time k = 5 compared with the static optimal strategy.
We then consider the average consensus on the square lattice network. We set T = 10 and numerically optimize the edge weights of the network. The results are shown in Figs. 5-7. As in the case of Karate network, the accuracy of the consensus by the proposed at the final time k = 10 is about 10 times better than the static optimal methodology. The optimized weights show a trend similar to the one for (a) k = 0  the Karate network. The weights at times k = 1 and k = 6 are relatively larger than the weights at other time instants, which leads to a temporal increase in the consensus error at times k = 2 and k = 7, respectively. Despite this phenomena, the proposed approach allows the nodes to achieve a better average consensus at the final time k = 10.  We notice that, only in the case of the WS network, the consensus error temporarily and significantly increases at time k = 2. In order to examine if this phenomena is specific to the WS model, we run the following experiment. For each of the three random graph models, we create 10 realizations of networks, for which we run the proposed algorithm to obtain the optimized edge weights. We then empirically compute the mean consensus errors E[ e(k) ] for k = 0, . . . , 10 for each of the 3 × 10 cases. We show the results in Fig. 9. From the figure, we confirm that only the case of WS network model presents a temporal increase in the mean consensus errors, while the errors from the other two cases decrease monotonically.

D. Periodic continuation
In the previous subsections, we have confirmed that the proposed method can drastically accelerate the average consensus algorithm under the assumption that we are given a prespecified finite time-window and that we know the distribution of the initial states. In this subsection, we further show that a periodic continuation of our algorithm yields an consensus algorithm that effectively accelerates the consensus for any initial state vector and over an infinite timewindow.
For given T , let G (0), . . . , G (T −1) denote the networks whose weights are optimized by the proposed method. Let L (0), . . . , L (T − 1) denote the Laplacian matrices of the networks. Then, the proposed consensus algorithm is written as By periodically extending the state transition matrices I − L(0) , . . . , I − L(T − 1) , we obtain the following average consensus protocol over an infinite time horizon: Define the asymptotic convergence factor of this algorithm by equation (2). The next lemma gives an explicit representation of the asymptotic convergence factor of the consensus algorithm (4). . This completes the proof. Using Lemma 3.1, we compute the asymptotic convergence factor of the consensus algorithm (4) for each of the five networks (i.e., Karate, lattice, ER, BA, and WS networks). We also compute the asymptotic convergence factor of the baseline strategy (3) for each of the five networks. We show the asymptotic convergence factors in Table I. The proposed method achieves less convergence factors, which shows the effectiveness of the proposed approach even in the case of infinite time-horizon problems.

IV. CONCLUSION
In this paper, we have presented a data-driven approach for accelerating the linear average consensus algorithm over undirected temporal networks. We have first unfolded the consensus algorithm to obtain an equivalent feedforward signal flow graph, which we have regarded as a neural network. We have then showed that we can apply standard deep learning techniques to train the obtained neural network and obtain a temporal network having optimized edge-weights. We have numerically confirmed that our methodology can outperform the average consensus algorithm with the static optimal edge-weights.