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):
The paper presents a deep-learning based variant of the linear average consensus algorithm over networks. At a high level, starting from an initial set of states (scalars associated to each node) the goal is for all states to converge to their average via local exchange of information. Linear average consensus achieves this by (iteratively) updating each state variable by a linear combination of each node*s state with those of its neighbors. The idea proposed in this paper is to learn -- in a data-driven manner -- the *weights* used in synthesizing this linear combination so as to achieve quicker convergence than those used in traditional methods (where the weights are pre-chosen and kept static throughout) for a given budget of iterations (say T). Such a learning can be achieved by recognizing that the dynamics of the state updates can be *unrolled* to form a feedforward T-layer linear neural network; therefore, the weights of such a network can be learned using standard learning methods, given enough training samples of initial states (and their averages). The authors show improved performance of such methods over a baseline method proposed by Xiao and Boyd (2004). While the problem/research direction is interesting, I have several concerns about the setup, proposed method, empirical evaluations, and theoretical contributions: * The basic setup is not well-posed in my opinion. Specifically, the authors never reflect upon the choice of window length (T), and in their experiments somewhat arbitrarily fix T=10 without justification. But why would one want to compute the average in exactly T rounds (no more, no less)? For example, if the network is well connected (and the initial distribution is unimodal and peaky) then the mixing time should be very small -- so if a large and inefficient T is chosen, one would presumably converge much more slowly using this method. Likewise for the reverse case: if the network is very poorly connected (e.g. there is a bottleneck somewhere) the mixing time should be very large, and for an incorrect T, no matter how well the weights are trained one would never get good answers. * The algorithm used to train the network is puzzling. The *unrolled* dynamical system resembles an RNN (not surprising, since one can unroll many iterative methods into an RNN), but the authors train this incrementally layer by layer. Why not use other, more common RNN training methods (e.g., plain backprop with or without weight-sharing)? * The experimental results are in general not easy to understand. Figure 2 suggests that the learned weights jump around quite a bit from layer to layer without much structure (likewise with Figure 5). There are strange bumps in the convergence plots which suggest that the consensus error actually *increases* in some intermediate layer before decreasing. This again suggests that the method is not robust. Moreover, the test examples are synthetic, small networks and it is unclear whether the proposed method would scale at all to realistic networks. * Finally, the theoretical part is a bit confusing. I understand how the upper bound on r^T_asym is derived (basically, Holder*s inequality repeated used) but don*t know where the lower bound (and hence the claimed tightness) comes from. For all these reasons, I recommend a reject.