Averaging Dynamics on Graphs

We formalize the averaging dynamics on a finite graph, in which every node replaces its value by the average of its neighbours’ values: the degree-weighted sum is conserved, the values stay in the initial range, and on a connected graph with an odd closed walk all values converge to the degree-weighted average of the initial values; on a connected bipartite graph they need not converge. The distance to the limit decays like \(\lambda ^t\), with \(\lambda \) the second largest absolute eigenvalue of the random walk (Lovász); in the random sequential version, where one random edge averages its endpoints, the expected state evolves by the matrix \(I-L/2m\). On a well-clustered regular graph started from random signs, the sign of the last change recovers the two clusters exactly (Becchetti, Clementi, Natale, Pasquale, Trevisan, SODA 2017).

1 The dynamics

Definition 1 Averaging
✓

\(x_{t+1}(v)=\frac1{\deg v}\sum _{u\sim v}x_t(u)\), and \(\bar x=\sum _v\deg (v)\, x_0(v)/\sum _v\deg (v)\).

\(\sum _v\deg (v)\, x_{t}(v)\) does not depend on \(t\); without isolated nodes, a round never leaves an interval containing all current values.

Proof ▶

Double counting over ordered adjacent pairs; an average of values in an interval stays in it.

2 Convergence

\(x_t(v)=\sum _u W_t(v,u)\, x_0(u)\) with \(W_t\) stochastic and \(W_t(v,u){\gt}0\) when a walk of length \(t\) joins \(v\) and \(u\). On a connected graph with an odd closed walk, some length \(L\) joins every pair.

Proof ▶

Induction on \(t\); for \(L\), fix the parity with the odd closed walk and pad with back-and-forth steps.

Theorem 4 Convergence to the degree-weighted average
✓

On a connected graph with an odd closed walk, \(x_t(v)\to \bar x\) for every \(v\).

Proof ▶

All entries of \(W_L\) are at least some \(\delta {\gt}0\), so \(\max -\min \) contracts by \(1-|V|\delta \) every \(L\) rounds (Doeblin); the common limit is \(\bar x\) by conservation.

Theorem 5 Bipartite graphs
✓
#

On a connected bipartite graph with at least two nodes, the values \(\pm 1\) of a proper 2-colouring change sign at every round, so they converge nowhere.

Proof ▶

All neighbours of a node have the other colour.

3 Rate of convergence

Theorem 5.1 of Lovász, Random walks on graphs: a survey (1993), in the form of Theorem 33 of the survey of Becchetti, Clementi and Natale, Consensus dynamics: an overview (SIGACT News 2020). Two printed details need a minor correction: Lovász’s text defines \(\lambda \) as \(\min \{ |\lambda _2|,|\lambda _n|\} \), a slip for \(\max \) (with \(\min \) the bound would fail, e.g. on a connected bipartite graph), and Theorem 33 of the survey prints \(\sqrt{d(v)/d(v)}\) for \(\sqrt{d(v)/d(u)}\); the corrected form is formalized (details).

\(P=D^{-1}A\) is the transition matrix of the random walk, \(N=D^{-1/2}AD^{-1/2}\) its symmetric version with eigenvalues \(\lambda _1\ge \lambda _2\ge \dots \ge \lambda _n\), \(\lambda =\max \{ |\lambda _2|,|\lambda _n|\} \) (\(0\) if \(n{\lt}2\)), and \(\pi (v)=\deg (v)/2m\) with \(m\) the number of edges.

\(P^t(u,v)=W_t(u,v)\) is the probability that the walk from \(u\) is at \(v\) after \(t\) steps, and \(x_t=P^tx_0\). If every degree is positive, \(P\) and \(N\) have the same characteristic polynomial, so \(\lambda \) is computed from the spectrum of \(P\).

Proof ▶

Induction on \(t\); \(P=SNS^{-1}\) with \(S=D^{-1/2}\).

Theorem 8 Lovász’s bound, Survey Theorem 33
✓

If every degree is positive, \(|P^t(u,v)-\pi (v)|\le \sqrt{\deg (v)/\deg (u)}\, \lambda ^t\) for all nodes \(u,v\) and all \(t\).

Proof ▶

\(P^t(u,v)=\sqrt{\deg (v)/\deg (u)}\, N^t(u,v)\) and \(\pi (v)=\sqrt{\deg (v)/\deg (u)}\, s(u)s(v)\) with \(s=\sqrt\pi \) a unit eigenvector of \(N\) for the eigenvalue \(1\). At most one eigenvalue of \(N\) exceeds \(\lambda \) in absolute value, and then it is \(1\) with eigenvector \(s\); so \(N\) contracts \(s^\perp \) by \(\lambda \), and \(N^t(u,v)-s(u)s(v)=\langle Qe_u,N^tQe_v\rangle \) with \(Q=I-ss^\top \) is at most \(\lambda ^t\) by Cauchy–Schwarz.

Lemma 9 Non-bipartite graphs
✓

On a connected graph with an odd closed walk, \(\lambda {\lt}1\).

Proof ▶

An eigenvalue \(\mu \) of \(N\) with \(|\mu |=1\) gives a vector \(y\) with \(x_t=\mu ^ty\) for the dynamics started at \(y\); by Theorem 4 \(\mu =-1\) is impossible and \(\mu =1\) forces \(y\) constant, so \(1\) is a simple eigenvalue and all others have absolute value below \(1\).

Corollary 10 Rate of the averaging dynamics
✓

If every degree is positive, \(|x_t(u)-\sum _v\pi (v)x_0(v)|\le \lambda ^t\sum _v\sqrt{\deg (v)/\deg (u)}\, |x_0(v)|\).

Proof ▶

\(x_t(u)-\sum _v\pi (v)x_0(v)=\sum _v(P^t(u,v)-\pi (v))x_0(v)\) and Theorem 8.

4 Sequential averaging

The random sequential (gossip) averaging of Boyd, Ghosh, Prabhakar and Shah, Randomized gossip algorithms (IEEE Trans. Inf. Theory 52, 2006), the source of equations (4) and (5) of the survey of Becchetti, Clementi and Natale.

A step on the edge \((i,j)\) multiplies the state by \(W_{ij}=I-\frac12(e_i-e_j)(e_i-e_j)^\top \); a run applies the steps of a list of oriented edges in order. For a stochastic matrix \(P\) (given as a kernel), \(\bar W_P=I-\bar D/2n+(P+P^\top )/2n\) with \(\bar D_{ii}=\sum _j(P_{ij}+P_{ji})\), and \(\bar W=I-L/2m\) with \(L\) the Laplacian.

\(W_{ij}x\) replaces \(x_i\) and \(x_j\) by their average and keeps the other values; \(W_{ij}\) is doubly stochastic and a symmetric projection, \(W_{ij}^\top W_{ij}=W_{ij}\).

Proof ▶

Direct computation; \((e_i-e_j)^\top (e_i-e_j)=2\) for \(i\ne j\).

If a uniformly random node \(i\) contacts \(j\) with probability \(P_{ij}\), then \(\mathbb E[W_{ij}]=\bar W_P\); if a uniformly random oriented edge is selected, then \(\mathbb E[W_{ij}]=\bar W\). On a \(d\)-regular graph with \(d{\gt}0\) and \(P=D^{-1}A\) both equal \((1-1/n)I+P/n\).

Proof ▶

Entrywise expansion of \(W_{ij}(a,b)=\delta _{ab}-\frac12(\delta _{ia}-\delta _{ja})(\delta _{ib}-\delta _{jb})\); there are \(\deg (a)\) darts out of \(a\) and \(2m=nd\) darts in all.

For a uniformly random oriented edge, \(\mathbb E[W^\top W]=\bar W\) and \(\mathbb E\| Wx\| ^2=x^\top \bar Wx\); after \(t\) independent uniformly random oriented edges, \(\mathbb E[x_t]=\bar W^tx_0\).

Proof ▶

\(W^\top W=W\); for the first moment, induction on \(t\) and linearity of expectation.

5 Strong reconstruction

Becchetti, Clementi, Natale, Pasquale and Trevisan, Find your place: simple distributed algorithms for community detection (SODA 2017; SIAM J. Comput. 2020), Theorem 3.2.

\(G\) is \(d\)-regular on two clusters \(V_1,V_2\) of \(n\) nodes, each node having \(b\) neighbours in the other cluster; \(\chi =\mathbb 1_{V_1}-\mathbb 1_{V_2}\), \(P=A/d\) with eigenvalues \(\lambda _1\ge \lambda _2\ge \dots \), \(\lambda =\max _{i\ge 3}|\lambda _i|\). Node \(v\) is blue at round \(t\) if \(x_t(v)\ge x_{t-1}(v)\); a coloring is a strong reconstruction if no color appears in both clusters. \(T(n,\delta )=\lceil \log (4n^3)/\log (1+\delta )\rceil +1\).

If \(\lambda {\lt}1-2b/d\) and \(x\in \{ \pm 1\} ^{2n}\), then \(|x_t(v)-\alpha _1-\alpha _2(1-2b/d)^t\chi (v)|\le \lambda ^t\sqrt{2n}\) with \(\alpha _1=\langle x,\mathbb 1\rangle /2n\), \(\alpha _2=\langle x,\chi \rangle /2n\).

Proof ▶

\(\mathbb 1\) and \(\chi \) are eigenvectors with eigenvalues \(1\) and \(1-2b/d\), both above \(\lambda \); at most two eigenvalues exceed \(\lambda \) in absolute value, so by equality in Bessel’s inequality their eigenvectors lie in \(\operatorname {span}\{ \mathbb 1,\chi \} \), and \(P\) contracts the orthogonal complement of this plane by \(\lambda \).

On a connected clustered graph with \(1-2b/d{\gt}(1+\delta )\lambda \), if \(x\in \{ \pm 1\} ^{2n}\) and \(\langle x,\chi \rangle \ne 0\), then for \(t\ge T(n,\delta )=O(\log n/\delta )\), \(\operatorname {sgn}(x_{t-1}(u)-x_t(u))=\operatorname {sgn}(\langle x,\chi \rangle \chi (u))\).

Proof ▶

\(|\langle x,\chi \rangle |\ge 2\) by parity, \(b\ge 1\) by connectivity, \(d{\lt}2n\), and \((1+\delta )^{t-1}\ge 4n^3\), so the main term of Lemma 16 dominates the errors.

Lemma 18 Lemma B.1, exact form
✓

For uniform \(x\in \{ \pm 1\} ^{2n}\), \(P(\langle x,\chi \rangle =0)=\binom {2n}{n}/4^n\le 1/\sqrt{\pi n}\).

Proof ▶

\(x\mapsto \{ v: x(v)=\chi (v)\} \) maps the zeros bijectively to the \(n\)-subsets; Wallis’ product.

Theorem 19 Strong reconstruction, Theorem 3.2
✓
#

With probability at least \(1-1/\sqrt{\pi n}\), the coloring is a strong reconstruction at every round \(t\ge T(n,\delta )\).

Proof ▶

Theorem 17 and Lemma 18.

6 Averaging whenever you meet

Becchetti, Clementi, Manurangsi, Natale, Pasquale, Raghavendra, Trevisan, Average whenever you meet: opportunistic protocols for community detection (ESA 2018, arXiv:1703.05045). The proof of Theorem 4.1 needs a minor correction: its last step uses \(\mathbb E\| z^{(0)}\| ^2\le 1/n\), while for uniform signs \(\mathbb E\| z^{(0)}\| ^2=n-2\). The conclusion still holds, and the formal proof uses its own bookkeeping (details).

One uniformly random edge is activated per round; a node activated for the first time draws a uniform sign, and both endpoints take the average of their two values. The rounds are i.i.d. uniform darts of \(G\).

A uniform dart is a uniform edge; a node holds a value exactly when it has been activated, and the protocol’s values are those of the averaging process started from the coins \(\sigma \); the sum of the values is conserved.

Proof ▶

Induction on the list of rounds; every edge carries two darts.

Proof ▶

\(W_t\) and \(\bar W\) are the matrices \(W_{ij}\) and \(\bar W\) of sequential averaging, and the averaging process is its run (Lemma 12, Theorems 13 and 14); \(\bar W\) is doubly stochastic since \(L\mathbf1=0\) and \(L\) is symmetric.

\(G\) is \(d\)-regular with communities \(V_1\) and \(V_2=V_1^c\) of size \(n/2\), each node having \(b\) neighbours in the other community, \(0{\lt}b\), \(2b{\lt}d{\lt}n\). The state splits as \(x=x_\parallel +y+z\) along \(\mathbb 1\), \(\chi =\mathbb 1_{V_1}-\mathbb 1_{V_2}\) and their orthogonal complement; \(\lambda _2=2b/d\), and \(\lambda _3\) enters as a lower bound on the Rayleigh quotient of \(L/d\) on the complement.

\(\bar W\chi =(1-\lambda _2/n)\chi \), the expected state decomposes exactly as in Lemma B.1, and the monotonicity and sign criteria of Lemmas B.3 and B.4 hold at every node.

Proof ▶

\(\bar W\) contracts the complement of \(\operatorname {span}\{ \mathbb 1,\chi \} \) by \(1-\lambda _3/n\).

With \(\beta =\langle x,\chi \rangle /n\): \(\mathbb E\| z'\| ^2\le (1-\lambda _3/n)\| z\| ^2+\lambda _2\beta ^2\) and, for every \(\gamma \), \(\mathbb E\, n(\beta '-\gamma )^2\le (1-\lambda _2/n)\, n(\beta -\gamma )^2+\lambda _2\gamma ^2 +(4\lambda _2/n^2)(n\beta ^2+\| z\| ^2)\).

Proof ▶

\(\mathbb E\| Wx\| ^2=x^\top \bar Wx\) and Jensen for \(\beta '\); the variance of \(\beta '\) comes from the \(nb\) darts across the cut.

If \(100\lambda _2\log n\le \lambda _3\) and \(3(n/\lambda _3)\log n\le t\le n/(4\lambda _2)\), then \(\mathbb E\| y^{(t)}+z^{(t)}-y^{(0)}\| ^2\le 3\lambda _2t/n\).

Proof ▶

Unroll the two recursions from any state; average over the signs (\(\mathbb E\| y^{(0)}\| ^2=1\), \(\| z^{(0)}\| ^2\le n\)).

If \(\lambda _2/\lambda _3\le \lambda _3\varepsilon ^4/(c\log ^2n)\), then with probability at least \(1-\varepsilon \) at least \((1-3\varepsilon )n\) nodes are \(\varepsilon \)-good at every round of the phase \(6(n/\lambda _3)\log n\le t\le 12(n/\lambda _3)\log n\).

Proof ▶

Good nodes averaged only with good nodes of their community stay good; the bad rounds of the phase are counted in expectation from the second-moment bounds restarted at the start of the phase, and small initial cut components are handled by anti-concentration of \(\langle \sigma ,\chi \rangle \).

Under the hypothesis of Lemma 4.2, with probability at least \(1-4\varepsilon \) at least \((1-4\varepsilon )n\) nodes have the sign of their community’s initial average throughout the phase, and with probability at least \(1/2-6\varepsilon \) the signs of the values are a \(6\varepsilon \)-weak reconstruction at every round of the phase.

Proof ▶

A good node has the sign of \(2S_h/n\) unless \(|S_1|\le \varepsilon |S_2|\) or \(|S_2|\le \varepsilon |S_1|\) (each of probability at most \(\varepsilon +1/\sqrt{n/2+1}\)); \(S_1S_2{\lt}0\) with probability at least \(1/2-1/\sqrt{n/2+1}\).