Title: DEEP LEARNING-BASED AVERAGE CONSENSUS

Abstract: 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 time-varying weights for faster consensus in the complex network. Numerical simulations are presented to show that our methodology can achieve a significantly smaller consensus error than the static optimal strategy.

1. INTRODUCTION:

The distributed agreement problem on networks, often referred to as a consensus problem (Olfati-Saber et al., 2007) , is an important problem in the network science and engineering, with applications in load balancing (Cybenko, 1989) , data fusion (Xiao et al., 2005) , multi-agent coordination (Ren & Beard, 2005) , distributed computing (Xiao & Boyd, 2004) , distributed sensor networks (Cortés & Bullo, 2005) , wireless communication systems (Senel & Akar, 2017) , and power systems (Dörfler & Bullo, 2012) . Recently, it also appears in online machine learning procedures to process big data (Chen & Sayed, 2012; Tsianos et al., 2012, and references therein) .

In the average consensus problem, nodes in the network seek to converge their state variables to the average of their initial states in a distributed manner. The standard solution to the average consensus problem is to use the linear average consensus algorithm (Olfati-Saber & Murray, 2004) , in which each node updates its state by taking a weighted linear average of its own state and the state of its neighbors. This algorithm results in a linear dynamical system whose state transition matrix involves the Laplacian matrix of the underlying communication network.

Designing consensus algorithms with fast convergence speed is of significant practical interest because such algorithms allow the multi-agent systems to reach an agreement with fewer iterations and, therefore, by consuming less communication resource. In the context of the linear average consensus algorithm, the problem of finding the optimal weights of edges for maximizing the asymptotic consensus speed can be reduced to a convex optimization problem (Xiao & Boyd, 2004) , under the assumption that the communication network is static and undirected. It was recently shown by Kempton et al. (2018) that the optimal weights can be computed in a distributed manner by an iterative computation. Zelazo et al. (2013) 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 & Barooah (2012) 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 (Sundaram & Hadjicostis, 2007) , 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 by Hendrickx et al. (2015) achieves consensus by stochastic (but possibly asymmetric) matrices in N(N -1)/2 iterations, where N denotes the number of nodes in the network. Safavi & Khan (2015) ; Shang (2016) used tools from graph signal processing (see, e.g., Shuman et al. (2013) ) 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 by Apers & Sarlette (2017) . Recently, Falsone et al. (2018) 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 finite-time consensus algorithms, currently available options are effectively limited to using the static optimal strategies (e.g., Xiao & Boyd (2004) ), 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 (Ito et al., 2019) , 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 2, 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 3, we evaluate the performance of the proposed method with various numerical simulations. We finally conclude the paper in Section 4.

2. 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.

2.1. 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 discretetime 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 (Olfati-Saber et al., 2007) , each node i updates its own state according to the following difference equation:

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 (i, j) element of the adjacency matrix of the network

W (k) ∈ R N×N by W i j (k) = w i j (k), if j ∈ N i , 0, otherwise,

and the degree matrix of the network at time k by

D(k) = diag(d 1 (k), . . . , d N (k)), d i (k) = ∑ j∈N i w i j (k).

Then, using the Laplacian matrix of the network

L(k) = D(k) -W (k), 𝐿 0 𝐿 1 𝐿 𝑇-1 ⋯ 𝑥(0) 𝑥(1) + - + - + - 𝑥(2) 𝑥(𝑇 -1) 𝑥(𝑇)

(a) Signal flow graph obtained by unfolding the linear average consensus algorithm (1) for k = 0, . . . , T -1.

L k = diag[W (k)1] -W (k) with i, j-element of W (k) is w i j (k) if (i, j) ∈ E and oth- erwise 0. 𝑥(0) 𝑥(1) 𝐿 0 + - 𝐿 1 + - 𝐿 𝑇-1 + - ⋯ 𝑥(2) 𝑥(𝑇 -1) 𝑥(𝑇)

(a) Signal flow graph obtained by unfolding the linear average consensus algorithm ( 1)

for k = 0, . . . , T -1. L k = diag[W (k)1] -W (k) with i, j-element of W (k) is w i j (k) if (i, j) ∈ E and otherwise 0. x2(0) x2(1) x2(2) x2(T ) γT x1(0) x1(1) x1(2) x1(T ) 1-∑ j∈N1 w1 j (0) 1-∑ j∈N1 w1 j (1)

w12(0) w21(0) w12(1) w21( 1) 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.

w12(1) w21(1) 1-∑ j∈N2 w2 j (0) 1-∑ j∈N2 w2 j (1) (b) Corresponding neural network

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 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 x 0 =c1 lim sup k→∞ e(k) e(0) 1/k (14)

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

x i (k + 1) = x i (k) + ∑ j∈N i w stat i j (x j (k) -x i (k)), 0 ≤ k ≤ T -1 (15)

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 (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. 4 , 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. 2 . 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

xN(0) xN(1) xN(2) xN(T ) 1-∑ j∈N1 wN j (0) 1-∑ j∈NN wN j (0) ••• ••• ••• ••• ••• (b) Corresponding neural network

Figure 1 : Unfolded signal flow graph and corresponding neural network the evolution of the state vector

x(k) = [x 1 (k) • • • x N (k)]

in the linear average consensus protocol (1) is written as

x(k + 1) = (I -L(k))x(k), x(0) = x 0 , where x 0 = [x 1,0 • • • x N,0 ]

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

c = 1 N N ∑ i=1 x i,0 .

Define the consensus error vector e(k) = x(k) -c1,

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., {x 0,1 , . . . , x 0,N } ∼ X 0 . Find the set of nonnegative weights

{w i j (k)} k∈{0,1,••• ,T -1},{i, j}∈E

that minimizes the average consensus error defined by

γ T = E[ e(T ) ],

where • denotes the Euclidean norm in R N , and E[•] denotes the expected value.

Because Problem 2.1 is a non-convex problem, it is difficult to compute a set of {w i j (k)} k≥0,{i, j}∈E that minimizes γ T . This difficulty motivates us to tackle this problem using a data-driven 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 3.4.

2.2. 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. We use the mean squared error, γ 2 T , as the loss function, which is then regularized by appending a regularization term of the Frobenius norm. As in Ito et al. (2019) , we use the technique of the incremental training for adjusting the weights during the training process. 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 regularized loss function of the average consensus error γ 2 1 + λ W (0) F 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 2 + λ W (1) F . 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 by minimizing γ 2 T + λ W (T -1) F . We train the network with a stochastic gradient descent algorithm.

3. PERFORMANCE EVALUATION:

In this section, we illustrate the effectiveness of the proposed method by various numerical simulations. The weighting factor for the regularization is set to λ = 1, the number of data-set per learning is set to 10 000, and the size of minibatch is one. For evaluations, 100 samples are used. With the above setup, the simulations were performed in PyTorch (Paszke et al., 2017) using Adam with learning rate 0.01 for training.

3.1. BASELINE STRATEGY:

Throughout this section, we compare the performance of the proposed method with that of the static optimal strategy presented in Xiao & Boyd (2004) . Assume that the initial state x 0 is a deterministic vector. Let us further assume that the edge weights w i j (k) do not depend on time k. Under these assumptions, Xiao & Boyd (2004) have shown that the problem of finding the static edge weights minimizing the (worst-case) asymptotic convergence factor

r asym = sup x 0 =c1 lim sup k→∞ e(k) e(0) 1/k (2)

reduces to solving a linear matrix inequality, which can be globally and efficiently solved (Boyd et al., 1994) . Then, as the baseline strategy, we use the following time-invariant consensus protocol

EQUATION

where w stat i j are the static optimal weights obtained by solving the linear matrix inequality.

3.2. DETERMINISTIC NETWORKS:

In this subsection, we use the following two empirical and synthetic deterministic networks; Karate network (Zachary, 1977) (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 = 10 and numerically optimized the edge weights of the network at the times k = 0, . . . , 9. In Fig. 2 , we present the optimized weights of edges in the network. We then empirically evaluated the average consensus error E[ e(k) ] for k = 0, . . . , 9. The results are shown in Fig. 3 . The accuracy of the consensus achieved by the proposed method is about 50 times better than the static optimal policy. We observe that the optimized weights of the network are dynamically changing in a non-trivial manner. 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 the final time k = 10 compared with the static optimal strategy.

(a) k = 0 (b) k = 1 (c) k = 2 (d) k = 3 (e) k = 4 (f) k = 5 (g) k = 6 (h) k = 7 (i) k = 8 (j) k = 9 (k) Static optimal

We then consider the average consensus on the square lattice network. We set T = 10 and numerically optimized the edge weights of the network. The results are shown in Figs. 5 6 7 . The accuracy of the consensus by the proposed method at the final time k = 10 is about 14 times better than the static optimal methodology. The optimized weights show a trend similar to the one for the Karate network. However, it is worth noting that the weights at time k = 4 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. After all, despite this phenomena, the proposed approach allows the nodes to achieve a better average consensus at the final time.

3.3. RANDOM SYNTHETIC NETWORKS:

We consider the following three random and synthetic network models: the Erdős-Rényi (ER) network (N = 100 nodes and M = 252 edges, where the probability for edge creation is 0.05) the Barabási-Albert (BA) model (Barabási & Albert, 1999 ) (N = 100 and M = 291, where the number of edges to attach from a new node to existing nodes is 3), and the Watts-Strogatz (WS) model (Watts & Strogatz, 1998 ) (N = 100 and M = 200, where each node is joined with its 4 nearest neighbors in a ring topology, and the probability of rewiring each edge is 0.15). We set T = 10. As in the case of the deterministic networks, we assume that the initial states of the nodes independently follow a uniform distribution on the interval [-1, 1]. For each of the networks, we used the deep learning technique to find the weights of the edges at times k = 0, . . . , 9. We then evaluated the empirical average of the consensus error E[ e(k) ] for k = 0, . . . , 10. We show the results in Fig. 8 . As in the case of the deterministic networks in Subsection 3.2, the proposed method achieves significantly less consensus errors at the final time.

(a) k = 0 (b) k = 1 (c) k = 2 (d) k = 3 (e) k = 4 (f) k = 5 (g) k = 6 (h) k = 7 (i) k = 8 (j) k = 9 (k) Static optimal

We notice that, only in the case of the WS network, the consensus error temporarily and significantly increases at time k = 5. In order to examine if this phenomena is specific to the WS model, the following experiment was performed: For each of the three random graph models, we created 10 realizations of networks, for which we ran the proposed algorithm to obtain the optimized edge weights. We then empirically computed 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 almost monotonically. 

3.4. 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 timewindow and that we know the distribution of the initial states. In this subsection, we further show that a periodic continuation of our algorithm discussed in Subsection 2.2 yields an consensus algorithm that effectively accelerates the consensus for any initial state vector and over an infinite time-window.

For given G and T , let L (0), . . . , L (T -1) denote the optimized weighted Laplacian matrices of the network. Then, the consensus algorithm proposed in Subsection 2.2 is written as

x(k + 1) = (I -L (k))x(k), 0 ≤ k ≤ T -1.

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:

EQUATION

The next lemma gives an explicit representation of the asymptotic convergence factor (2) of the consensus algorithm (4). 

EQUATION

)

where • is the spectral norm.

Proof. .

This completes the proof.

Lemma 3.1 states that r T asym is the geometric mean of the spectral norm of the product of T -step transition matrices of I -L (T -1 -t), t = 0, • • • , T -1. Note that r T asym with T = 1 does not necessarily correspond to the static-optimal in (2).

Using Lemma 3.1, we computed the asymptotic convergence factor of the consensus algorithm (4) with T = 10 for each of the five networks (i.e., Karate, lattice, ER, BA, and WS networks). We also computed the asymptotic convergence factor of the baseline strategy (3) for each of the five networks. The obtained asymptotic convergence factors are given in Table 1 . We observe that the proposed method achieved less convergence factors, which shows the effectiveness of the proposed approach even in the case of infinite time-horizon problems.

4. 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.

:



Figures and Tables:

Fig. 1: Unfolded signal flow graph and corresponding neural network

Figure 2: Optimized weight of edges in the Karate network. (a)-(j): Proposed method. (k): Static optimal strategy. The width of the lines indicate the values of the weights (the thicker a line is, the larger its weight is). The edges having weight less than 10 -2 are indicated by dashed lines.

Figure 3: Empirical mean of the consensus errors (Karate network)

Figure 5: Optimized weight of edges in the lattice network. (a)-(j): Proposed method. (k): Static optimal strategy. The width of the lines indicate the values of the weights (the thicker a line is, the larger its weight is). The edges having weight less than 10 -2 are indicated by dashed lines.

Figure 6: Empirical mean of the consensus errors (lattice network)

Figure 9: Distribution of the mean consensus errors for the ER, BA, and WS network models. Solid lines and shaded areas represent the averages and the standard deviations, respectively.

Let L (0), . . . , L (T -1) denote the optimized weighted Laplacian matrices of the networks by our deep learning algorithm. The asymptotic convergence factor of the consensus algorithm

First note that e(k + 1) = k ∏ t=0 (I -L (k -t))e(0).By expressing k using s and τ ask = sT + τ, τ ∈ {0, • • • , T -1}, •• ,T -1} because T := {0, • • • , T -1} is a finite countable set. Next, notice that

Asymptotic convergence factors

Table content: <table><tr><td>Proposed</td><td>Baseline</td></tr><tr><td colspan="2">Karate 6.69 × 10 -1 9.25 × 10 -1 Lattice 7.23 × 10 -1 9.21 × 10 -1 ER 6.53 × 10 -1 8.70 × 10 -1 BA 5.85 × 10 -1 7.79 × 10 -1 WS 6.99 × 10 -1 9.35 × 10 -1</td></tr></table>

Peer review (iclr2020):
This paper tackles the problem of accelerating the linear average consensus algorithm over networks and proposes a data driven approach by formulating it as deep neural network training. Specifically, the authors unfold the algorithm as a feedforward network where each layer represents a specific time and nodes are states at that time, and weights represent connecting weights (edges) in the network. Then the training was done by stochastic gradient descent. In the experimental validation, the proposed approach outperforms the baseline (Xiao & Boyd (2004) for deterministic and random synthetic networks. The proposed approach seems technically sound and interesting, but the paper may need to improve the following issues. First, it may need to show justification why the proposed approach achieved the better results and works well. Second, it needs to have more thorough experimental validation. Specifically, the baseline seems too old and not working well since the proposed approach is more than ten times better in errors, so more recent and appealing baseline (such as Ito et al. (2019)) would be required for better demonstration of the effectiveness of the proposed approach. Finally, the presentation of this paper might need more detail (see my comments below). Detailed comments: - It was not clear to me how training data were generated. - In incremental learning, what are the initial values of weights when adding another layer? - Why do you choose mini-bath size of 1? Have you tried larger sizes? - Why does only WS network have the error increase at k=5? Typo: page 3: deep leaning techniques -> deep learning techniques To AC: I do not know much about this area, but tried to my best to understand and assess the paper and this paper does not look ready yet to publish in ICLR. However, it is still possible that I did not understand the paper well.