Revisiting 1-peer exponential graph for enhancing decentralized learning efficiency
Authors: Kenta Niwa
Yuki Takezawa
Guoqiang Zhang
W. Bastiaan Kleijn
Venue: NeurIPS 2025 poster ()
Keywords: Decentralized learning
network topology
dynamic graph
finite-time convergence
spectral gap
Primary area: optimization
TL;DR: For communication-efficient decentralized learning, we propose two new graphs: the k-peer exponential graph and the null-cascade graph.

Abstract: For communication-efficient decentralized learning, it is essential to employ dynamic graphs designed to improve the expected spectral gap by reducing deviations from global averaging. The $1$-peer exponential graph demonstrates its finite-time convergence property--achieved by maximizing the expected spectral gap--but only when the number of nodes $n$ is a power of two. However, its efficiency across any $n$ and the commutativity of mixing matrices remain unexplored. We delve into the principles underlying the $1$-peer exponential graph to explain its efficiency across any $n$ and leverage them to develop new dynamic graphs. We propose two new dynamic graphs: the $k$-peer exponential graph and the null-cascade graph. Notably, the null-cascade graph achieves finite-time convergence for any $n$ while ensuring commutativity. Our experiments confirm the effectiveness of these new graphs, particularly the null-cascade graph, in most test settings.

Revisiting 1 1-peer exponential graph for enhancing decentralized learning efficiency
Kenta Niwa
Yuki Takezawa
NTT Communication Science Laboratories <kenta. niwa@ntt. com>
Kyoto University
Okinawa Institute of Science and Technology
Syuki-takezawadiin iist. w.t.ii...ttotuut..... ac jp>
Guoqiang Zhang University Exeter
W. Bastiaan Kleijn Victoria University of Wellington
<G. Zhanggexeter ac uk>
<bastiaan. kleijn@vur ac nz>
Abstract
For communication-effee decentralized learning, it is essential to employ dy- namic graphs designed to improve the expected spectral gap by reducing deviations from global averaging. The 1-peer exponential graph demonstrates its finite-time convergence property-achieved by maximizing the expected spectral gap-but only when the number of nodes n power of two. However, efficiency across any and the commutativity of mixing matrices remain unexplored. We delve into the principles underlying the 1-peer exponential graph to explain its efficiency across any and leverage them to develop new dynamic graphs. We propose two new dynamic graphs: the k-peer exponential graph and the null- cascade graph. Notably, the null-cascade graph achieves finite- time convergence for any n while ensuring commutativity. Our experiments confirm the effectiveness of these graphs, particularly the null-cascade graph, in most test settings. https::/ htap::///ithuut wttpg/eeenn///aaaaaaaaaaaaaaaaaa
Introduction
In the era of large-scale datasets, complex models (e.g.. Deep Neural Networks: DNNs), and power- ful computing resources capable of high throughput and simultaneous multicasting, decentralized learning of models over arbitrary network topologies (graphs)-for tasks such as natural language processing and image recognition- gence rates of decentralized learning algorithms, including DSGD 220 26), are primarily influenced by the graphs used for partial averaging of models within n E nodes [33. Thus, optimizing the communication graphs to improve the expected spectral gap (by reducing deviations from global averaging), given a maximum degree & e N (i.c., the maximum number of connections or multicast transmissions per node), is vital for communication-effiiiic
been essential for advanced collective intelligence. The conver-
decentralized learning.
Graphs used in decentralized learning are broadly categorized into static (7=1) and dynamic (722), with the dynamic graphs undergoing changes involving periodic interval r rEN. In contrast, static graphs, such as the ring, grid, torus (24, and exponential graph 44), remain unchanged over time. Dynamic graphs rely on mixing matrices, specifying varying connection paths and weights. A note- worthy dynamic graph is the 1-peer exponential graph [3), characterized by 1-peer communication and known to achieve desirable finite-time convergence-i.e., the expected spectral gap of the product of r mixing matrices is maximized when n power of two, as in Table
The introduction of k-peer communication with k>2 offers the potential for improved decentralized learning, especially in settings where simultancous multicasting supported. This scenario has been
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table I: Comparison of dynamic graphs. The expected spectral gap p and the periodic interval defined in
Assumption 4 in Sec. 2 The r is estimated when n is factorized as n I (v++1), where is S S Vx I
k < 1 ... va. and cach is natural number, with и factors being less than equal to k. Uniform degree is satisfied (V) when every node has the same number of connections.
Dynamic graphs
# of nodes n. Max. degree
Uniferm
Expected spectral gap
Periodic interval r
Commu
1-peer hypercube [3]
A power of
(finite-time convergence) for limited a
logg(n) Dog, (n]]
1-peer exponential 43
Vi E
Not analyzed for (finite-time convergence)
Base-(k++1
35
Vy E
Vi é N
x+> +- 2 (:loge-(M))
k peer exponential (Sec.)
Vx N
Vk E N
1- max -1 (K+1)- sin(ni/h)
si /o]
[loga (xx) /
Null-cascade (Sec.
4/2 N
WkEN s.t. A22
(finite-time convergence)
5 iice 2/(12[/2[]) 7
explored, such as the base-(k + 1) graph [55 which achieves finite-time convergence for any (n, k)
configuration. Nevertheless, several challenges remain. First, the required periodic intervals can become large depending on (n, k).. and the emergence of nonuniform degrees (i.e., unequal numbers of connections per node) can hinder convergence rates in practice. Second, the base-(k: (k+1), graph does not ensure commutativity of the mixing matrices (see Definition in Sec. (2). necessitating strict coordination of periodic and synchronized communication cycles across nodes.
For further communication -ffficief decentralized learning by leveraging k-peer communication with k 2 2. we propose two new dynamic graphs: the k-peer exponential graph and the null-cascade graph. Our key contributions are as follows:
Exploring principles underlying the 1-peer exponential graph. We revisit the advantageous properties of the 1-peer exponential graph. Ying et al. 4 proved its finite-time convergence only when n is power of two. However, its efficiency across any and the commutativity of its mixing matrices remain unexplored, warranting further investigation. to the k-peer exponential graph, which generalizes the 1-peer exponential graph to allow k-peer communication. The k-peer exponential graph, with 1:1,, is characterized by t circulant mixing matrices of uniform weights. Their eigenvalues Transform (DFT) of expansions of Moving Average Filters (MAFs) with uniform weights. This allows us to analyze the efficiencies of the k-peer exponential graph for any by utilizing established Digital Signal Processing (DSP) techniques. Our findings are twofold: i) finite-time convergence can be interpreted isolating the Direct Current (DC) component and eliminating (nullifying) non-zero frequency components through a cascade of mixing matrices, and ii) the k-peer exponential graph functions effectively by isolating the DC component while nullifying non-zero frequency components. Although this suggests desiring finite-time convergence is only achieved when n is power of k+1,
Sec. 3 we explore the extension
analytically determined by the Discrete Fourier
Proposition of null-cascade graph. To achieve finite-time convergence for any while preserving commutativity, our approach builds on the principles underlying the k-peer exponential graph. Our main idea is to incorporate not only MAFs with uniform weights but also Stecrable Nulling Filters (SNFs) with non-uniform weights to nullify all non-zero frequencies, as detailed in Sec. 4 We refer to the resulting graph as the null-cascade graph, which ensures finite-time convergence for any while maintaining commutativity. Limitations in the null-cascade graph are that i) requires k22 for forming SNFs and ii) it is most effective when the factorization of n does not include large prime numbers, as it yields a comparatively small increase in the periodic interval T (see Table D The effectiveness of the proposed graphs, particularly the null-cascade graph, was confirmed through numerical experiments in Sec. 5
2
Preliminaries
The simplest decentralized learning algorithm, DSGD [6). and its convergence rate are presented in As a baseline graph, 1-peer exponential graph is introduced in Sec. 2.2
Sec. 2.1
2.1
DSGD and its convergence rate
Consider a network consisting of n local nodes collaborating to solve an optimization problem:
min xERd
{
[(x)
1 Σ f((x)
(1)
im1
2

---

where fi : R denotes the local loss function and differentiable. A fundamental algorithm for solving this problem DSGD. It iteratively repeats two steps: (i) local updates of n local models X Xn ERRdxn and (ii) partial mixing of local parameters using mixing matrices. Following we consider dynamic communication among local nodes by periodically repeating
sequence of r mixing matrices {W(0) w( JER (nxn)xr Each mixing matrix is doubly stochastic, satisfying 1 O 1, 1, The update rules are given by:
(TT
i1 (x+ X (r) 7V X (()))
(ii (i) (r-1) = ( W (modfrz))
(2)
where (E ..... R-1} denotes the index of communication round, 17 is the learning rate, (X E
R represents stochastic gradients using local sampling data samples &. and mixing matrices are initially given. Representative dynamic graphs include the 1-peer exponential graph 433, 1 1-peer
hypercube graph [3T] 1 1-peer EquiDyn graph [32], and base-(k 1) graph [35]. Conversely, static graphs, such as ring, grid, torus [24]. and exponential graph [[] are available by setting r=1.
Associated with 2 convergence analysis is provided in 13 below, convergence rate of DSGD given: Assumption 1. There exists L(>0) such that [[) V ((b) < L/ bll2. Va, b Rd.
Under the Assumptions iitte
Assumption 2. There exists such that Eg (x) (x 1 - 0², V Rdd.
n E. VV( fx) 11 ( Vx E Rdd Assumption 4 (Expected spectral gap). There exists _ (0, 1| and (21) such that: TEw XW
Assumption 3. There exists such that 1.
I (1 (1-p) X X VX E Rdxn, where W = W (r-I) and X 11,1
Theorem 1 (Complexity estimates of DSGD B.) Suppose that Assumptions 7 hold. For any
target accuracy <(> 0). there exists a learning rate (potentially depending such that the
ΣF E V 113 S can be reached after
accuracy R+1
0²
ST ST
[T) I.jo
R = O
nc
pe3/2
pc
communication rounds, where fo [(x(0)) - g and f denotes the minimum of f-
Theorem
Sareeem@hihhe Tiihhighhts that maximizing the expected spectral gap (p-1), and shortening the periodic interval are crucial for communication-effican decentralized learning. To this end, various graphs have been explored, one of which is introduced in the next subsection.
2.2 1-peer exponential graph
As baseline dynamic graph, the 1-peer exponential graph is introduced. It can be characterized by sequence of circulant mixing matrices:
Definition (Graph consisting of circulant mixing matrices). Consider graph defined by circulant
mixing matrices, denoted by (W()).... ER
(x for each (=0, 1, ,,..,,...--......... 7-1, as
20
AO (1
(n-1)
(1)
(2)
W =
(3)
(110
(n-2)
(n- 1}} where (0)
satisfies E. (1) be doubly stochastic.
Unless the graph consists of circulant mixing matrices, each node has the same number of connections (uniform degree). The 1-peer exponential graph decomposes the connections of the exponential graph into 7= [log2 [n)] mixing matrices, enabling 1-peer communication as follows:
). The 1-peer exponential graph is a dynamic graph composed of 7= [1og2(1)] mixing matrices (0, 1, ,,...,7-111.... --1)) in the form (3) with:
Definition 2 (1-peer exponential graph [43]).
2/2 -=
(0(0))
0 otherwise
3

---

Definition 3 (Finite-time convergence). A dynamic graph composed of т mixing matri- ces {W W ] is considered a T-finite time convergent graph if it satisfies: W W(r-1) = 1 I This indicates that the expected spectral gap in Assumption becomes one (p-1).
In 43 it is proven that the 1-peer exponential graph achieves finite-time convergence for limited (a power of 2). An additional key property is the commutativity of r mixing matrices. Specifically, their product-regardie
of the permutation of the order consistenttt satisfies the following:
Definition 4 (Commutativity of mixing matrices). For any permutation p of indices 701.. the product W(e(0))... (((T-)1) is equal to W .......(-)) (
As shown in Theorem maximizing the expected spectral gap (p-1) and maintaining small periodic interval are effective for communication -eficieent decentralized learning. However, the 1-peer exponential graph only achieves finite-time convergence for limited n such that is a power of two. Moreover, its efficiency across any n and the commutativity of mixing matrices remain unexplored, warranting further investigation.
Revising 1-peer exponential graph to explore its underlying principles
The underlying principles of the 1-peer exponential graph are explored. The previous study established its finite-time convergence property for specific n. However, its efficiency across any n and the commutativity of r mixing matrices remain unexplored. Further investigation may lead more coamunication-effciiee decentralized learning methods. Section p presents the k-peer exponential graph, a generalized form of the 1-peer exponential graph supporting k-peer communications. Sec. we explore the conditions to satisfy finite-time convergence and the underlying principles of the k-peer exponential graph to explain efficiency and commutativity.
3.2
3.1
k-peer exponential graph
The fact that the 1-peer exponential graph achieves finite-time convergence for specific n can be extended to allow k-peer communication for specific (a power of k + 1). To illustrate this, we first introduce the k-peer exponential graph, defined as follows:
Definition (k-peer exponential graph). Given (n, k) and r= [log (n) the k-peer exponential
graph consists of circulant mixing matrices (e {0, 1, ..... 1)) defined in the form of with:
== (k + 1),, 2(k + * otherwise
(1)
x41
0
example is illustrated in Fig. [[); however, this does not achieve finite-time convergence since (n, k) (15, 2). A theoretical analysis of the k-peer exponential graph, including its expected spectral gap and commutativity, provided in the following subsection and Appendix
3.2 Principles underlying k-peer exponential graph
This subsection presents two of our key findings: a necessary condition for graph circulant mixing matrices to achieve finite-time convergence, and ii) description of the efficiency of the k-peer exponential graph, a generalization of the 1-peer exponential graph, across any n.
i) Condition to be finite-time convergent graph. To establish condition for a graph composed of circulant mixing matrices to achieve finite-time convergence, we first analyze the target property of mixing matrix product; namely, the complete graph to connect all nodes: W Woomp = 11, 1 Since W comp also circulant mixing matrix, eigenvalue decomposition is facilitated by the DFT as W comp D diag((L 0, ... D, where D E C denotes the DFT matrix. This reveals that averaging local parameters is equivalent to isolating the DC component (0-th frequency
In the 1- 1-peer exponential graph in Sec. 2.2 the ceiling function was used as r= [log, (n)] however, we the flooring function to derive expected spectral gap for any in Sec. 3.2

---

(a) k-peer exp. graph (n=15, k=2, (I=0)
(b)
Null-cascade graph (n-15, k-2, T-3)
(1=1)
(1=0)
(I
(1=2)
0.5
0.4
02
0.1
0
(HAF, Gokk2, mpm3")
m1-3))
(MAF 22-2, 5)
(9NF, c, m,-2, 0. (SNF, 6-2, Myy1, 96)
Figure I: Proposed graphs: (a) k-peer exponential graph with An) (15, which does achieve finite-time convergence. (b) Null-cascade graph with (n, (15, 2). which achieves finite- convergence. Each graph consists of π = 15 nodes, depicted as black dots arranged in circle and interconnected by lines. The colors of these lines indicate the mixing weights hetween the nodes in W( In (a), uniform weights (Wi6 = 1/3) employed (depicted in yellow), whereas in (b), 15 nodes when & 1, interconnected with lines colored differently (red and green), indicating non non-uniform weights specified by SNFs.
component) while nullifying all non-zero frequencies (Nw E (1..... n 1 1)). Similarly, we analyze the product of circulant mixing matrices through eigenvalue decomposition:
W (0) W(--1) (D H D) -(D H D) D H H(T D,
(5)
where ( diag((H() (0). ..., H (n 1)]) denotes the eigenvalue matrix, of which the di-
agonal elements are in fact the frequency responses of (0) 1.. (n - 1)}: H (i.)
1}), where the DC component is preserved as (() ... (0) = due to the use of the doubly stochastic sequence ΣnO (1) 1.
E (1)e 22vjius/ (iw {0, 10.,,,
Additionally, since the results of (5) remain unchanged even when the order of circulant matrices permuted, dynamic graphs defined in Definition I exhibit commutativity for any n.
From (5) the product of r circulant mixing matrices can be interpreted as a cascade of 7 (spatial) filters that maintain the DC component at 1. Thus, a condition for finite-time convergence is given by the following equation, which ensures that all non-zero frequency components are nullified through the cascade of circulant mixing matrices: (i ... (I,) = 0, (in = 1,............ ..... n 1). If at least one of the circulant mixing matrices has zero response, 11 (iw) frequency i. Let Ar denote the set of null frequency indices for the f-th mixing matrix W(O) Thus, the condition for finite-time convergence can be equivalently expressed as follows: the cascade of r circulant mixing matrices must form nulls at all non-zero frequency indices, ensuring:
0 for every non-zero
U Jv = 21. n t=
(6)
ii) Exploring principles underlying k-peer exponential graph. We next demonstrate the k-peer exponential graph, with 2 1, effectively increases the expected spectral gap p across any n.
We notice that 4 is an MAF with (k: + 1) uniform weights and its expansions motivates to analyze the efficiencies of the k-peer exponential graph by employing DSP techniques:
F This observation
Definition 6 (Frequency response of Moving Average Filter (MAF) (91). For any a E N, frequency response of an MAF with (ce+ 1)-length is given by
sin(w(ce + +1//2) sin(w//)
H H(d
E -jwee/2
cE +1
where w E [0, 2T)) denotes the angular frequency.
Definition 7 (Expanded sequence). Given a sequence (()),... hh(ee) and expansion order m. E N
satisfying (ce + 1 1)me S n, the expanded sequence hym, (0), (0)..... Nymme (n-1) is formed by separating
each element of the original sequence by m zeros:
{ (h(j) = mrj. j j (0....,cc hyme (1) = {00
otherwise
In the DSP field, "expansion" " refers to the process of upsampling by inserting additional zeros between the original samples, thus lengthening the sequence for sampling rate conversion.
5

---

Lemma 1 (Frequency response of expanded sequence (291). Given an original sequence h(i) and its expansion h (i) in 77. the frequency response of expanded sequence H Hm,, (c is represented as shifts in the frequency domain of the original sequence H Hell"): 10mee (e)m)(e H (elwme))
When the original sequence is an MAF of length (ct + i... h(0)= = ... frequency response of the me-order expended MAF can be derived by combining Definition 0 and Lemma as follows:
+ 1). the
1 sin(wme(ce + 1)/2)
(fme(elu)
exp -Jmmmc/22
(8)
CE + sin(wme/2
Recall that the k-peer exponential graph (Definition 5) consists of r [loge+ (n)) circulant mixing matrices, where each matrix W is characterized by an MAF with fixed communication order k and exponential expansion order my = (I- + 1) Using the DSP techniques discussed previously and the fact that the angular frequency w and frequency index tn are related by w = 2 n,, the expected spectral gap regarding the k-peer exponential graph is given as follows:
Theorem 2 (Expected spectral gap of k-peer exponential graph for any (n,k)), k)). The expected spectral gap of k-peer exponential graph for any (n, k) with
(088+1(n)]] is given by
n. a power of k++1
p
max (E
sin(Tr((=+1))// /n) (k+1)T sin(mi/n)
otherwise
The proof is provided in Appendix A It shows that the k-peer exponential graph achieves finite-time convergence when n is a power of Moreover, the expected spectral gap p is increased the order of 1 (L1((k + 1) This result theoretically supports the efficiency of the k-peer exponential graph across any n. In particular, p is efficiently maximized when n is equal to or slightly exceeds a power of (k: + 1), as illustrated in Appendix F Furthermore, the convergence rate of DSGD using this graph is obtained by substituting p in Theorem 2 into Theorem as summarized in Appendix E
As secondary outcome of our exploration in this subsection. we present a simplified algorithm for constructing the base-(k + 1) graph [35], which achieves finite-time convergence for any (n, k) configuration. The details of this are provided in Alg. 5 Appendix C
However, as noted earlier, the base-(k: (k+ + 1) graph does not support the commutative dynamic graph we are aiming to achieve. the next subsection, we further extend the k-peer exponential graph to achieve finite-time convergence for any n while maintaining commutativity.
4 Null-cascade graph
We propose the null-cascade graph designed to achieve finite-time convergence for any n while maintaining commutativity. Recall that the k-peer exponential graph maintains commutativity but only achieves finite- time convergence for specific (a power of k + 1). This limitation stems from the fixed communication order kt Assuming that 2 2 is available, our strategy involves the following steps: (Step 1) using MAFs with dynamic communication orders ca($ k) and dynamic expansion orders my to efficiently nullify as many non-zero frequency components as possible, and (Step 2) incorporating not only MAFs with uniform weights but also SNFs with non-uniform weights, which are defined later, to nullify remaining frequencies, as detailed in Alg.
To implement this strategy, we first factorize ni as n =I[== (1++1), =I++, where 2 S.. S < Uc++1 S ... Vxx with each ia E N (line 2 in Alg. [1] For Step 1, the null frequencies of expanded MAFs with communication order e E N and expansion order my E N are analytically derived from (8)
Lemma 2 (Null frequencies of expanded MAF). Suppose an MAF with communication order et conforms to Definition 0 Its expansion with order me forms nulls at multiples of Ta++1jm²
excluding
multiples of me² within [0, n).
The derivation is shown in Appendix B In 6 the frequencies to be nullified are identified as non-zero frequencies in E {1...., n 1 equivalently represented as multiples of b b= within the interval [0, n) (line [). To effectively nullify these frequencies, is optimal to select my such that
(oc+1)me = b, yielding in m, = (cr+1]8 (line G). To ensure me be a natural number, (ce + 1) must be

---

Algorithm Null-cascade graph
1: Given n. k(2 2), f 0
2: Factorization n:: n-lli- (1++1), where 21 S. Su
S S.... S.S, where 14 EN
3: I (Step 1) Null forming using expanded MAFs
4: for i ...... do
5:
= 1/4
6: my (c++1)b
(j Oj.0.....c.)
7:
())
(otherwise)
8:
W = ciro([) (0)...., Tm
=ciro
(6) (n-1)))
9:
l == =
1 mixing matrix index increment */ /*base of frequencies be nullifiedd
10:
b= blus 1)
11: end for
(Step 2) Null forming using expanded SNFs
13: for x.....,.. K ++1 do
(5)
7/ 1)) JE (m))) -S, 1* Alg. 3 Bi Appendix
15: for j 1 ..... Tan (1) do
16:
W circ(hy (5y (O).... 7 (n
17:
f=
mixing matrix index increment */
18:
end for
19:
b b= 11)
basse of frequencies to be nullified*/
20:
end for
factor of n/b; namely, o =v; (i [l.....x]] (line 5). In our implementation, detailed in Alg. we sequentially select from Us down to v1 as (L (o....,k-1) (line because many nulls can be efficiently formed by choosing the largest possible values for both Gy and m.. After generating an expanded MAF, eirculant mixing matrix (()) is computed (lines 8 and the frequencies still be
nullified can be updated to multiples of <- b(v (line 10 because frequencies associated with factor 24 are eliminated. This process can be incrementally repeated (E (O...., 11) nullify the
frequencies associated with {Vx...., 1/1 } and reaches b - (1/2 + in Step (lines 4 11 in Alg.
exist, as cp k. To address the challenge of nullifying the remaining frequencies for the factors {ux+1,..., V that exceed k; we introduce additional filters, referred
However, this approach is feasible when factors
SNFs, designed to cascade and achieve the complete nullification of non-zero frequencies in Step 2.
Definition 8 (Steerable Nulling Filter (SNF)). When 2 2, peer communication with o S k available. An SNF with length ce frequencies. We derive the SNF by solving a polynomial specifically designed to form these nulls. By setting ea
then be employed to form nulls at specific target
k//2], the polynomial is expressed with roots corresponding to frequency indices {qt,1...., /2. and their conjugate frequency indices {qē,1.... /2,0//2 where Ei qe The polynomial is expressed as
number
This leads to a ce-order polynomial equation of the form: 70)xz² +... 7(c - 1)x x + (C2)- To ensure the doubly stochastic property in (Ce lengghh filter sequence, the normalized filter sequence is computed as 7()) = 7(i) Ei ((1) (i)ffor for i (O....,ce). This will result in filter sequence consisting of non-uniform weights.
In 9.. we set pairwise nulls in conjugate relationship to ensure that SNFs are real numbers. This configuration requires k 2. As stipulated in Definition 8 the SNF creates 6 = 2 /2 nulls at qe and g. d (w (1,..., ct/ /2}). The expanded SNF with order m, leads the following null formation:
Lemma 3 (Null frequencies of expanded SNF), Suppose SNF with communication order Ca conforms to Definition Its expansion with order my forms null frequencies at 2e. ton and F. ton ton. where vb {l,..., /t/ /2 and {0.... mc - 1).
mg
7

---

(kse-(k+1) graph (n=15,
k=2, T=4) (1= 2)
(1 (1= 1)
(1= 3)
1.0
0.8
02
01
Basc-(k++1) 1) graph with (n, k) (15, 2), where nodes are depieted black dots arranged in a circle and interconnected by lines. The colors of these lines indicate the mixing weights between nodes in W(O,
Figure 2:
The derivation is provided in Appendix B To nullify the remaining frequencies associated with
(Vx+1,...., 1/A V. selection of (e,) is required in the SNF, According to Lemma 3 (me: (t,.) .)
must be selected such that qt,//mg corresponds to the remaining frequency indices (multiples of b). However, since this cannot be uniquely determined,
algorithm to select (me, 9r.0) is specified in
Alg. 3) and 4 in Appendix [3] ensuring the positive-definite property of the SNFs. The process of
sequentially generating SNFs (line 14) and corresponding circulant matrices (line (6) to nullify the frequencies associated with (V>...., Mx++1) } continues until reaches n, as outlined in Step (lines 10 of Alg. [ thereby ensuring that nullification at non-zero frequencies in (6) is accomplished.
Theorem 3 (Expected spectral gap of null-cascade graph). The expected spectral gap of the null- is p = finite-iinnn convergence) for any n with k: 2 2.
cascade graph, specified by Alg. 7
Discussion. An example of the null-cascade graph with (n, k) (15, is depicted in Fig.
Since n can factorized as n= (2+1)) the factors are V1 = 2 k) and U/ = 4(> k). For frequencies associated with 1/1 are nullified using MAF, while those associated with 1/2 are nullified with two SNFs, resulting in a total of T = 3 mixing matrices. In Fig. bb), each matrix weights vary across each matrix & E {0, 2, affecting the color of lines connecting the nodes. For t= 0, an MAF with equal weights (co =
is employed, coloring all connecting lines yellow. Conversely, for é = 1, 2, non-uniform weights (c1 22 C2 22) specified by SNFs are employed, resulting in lines colored differently (red and green). From Theorem 3 this achieves finite-time convergence.
Next, we present brief comparison with the base-(k + 1) graph, which also achieves finite-time convergence for any n. Figure 2 illustrates the base-(k (k++)) 1) graph for (n, k)) = (15, 2). Comparing this to Fig. (b), which depicts the null-cascade graph under the same (n, k) configuration, several differences emerge. Primarily, the null-cascade graph maintains a uniform degree across n nodes (every node has the same number of connections), whereas the base- + 1) graph does not, leading to unbalanced parameter mixing within each subgroup and occasional parameter exchanges among subgroups (E f0, 1, 2)). This uniformity in local degree within the null-cascade graph supports stable parameter training. Moreover, the periodic interval т, which is required for finite-time convergence, differs between null-cascade graph and base-(kk+1] graph. For (n. k) (15, 2), in the null-cascade graph (T = 3) is smaller compared to that in the base- base-(k+11 (k+1) graph (T 4). However, this not always the case outlined in Appendix F Including large prime numbers 14 in the factorization of n leads to an increase in for the null-cascade graph, since shown in Table I While further discussion on the possibility of redundant counting of T can be found in Appendix
π + Ei=xt1 (2 ks /2),, as
F to demonstrate that the impact of this increase in r is not significant, the next section includes experiments where n is large prime number.
5 Numerical experiments
To show the effectiveness the proposed graphs, we conducted two experimental tests. Sec. 5.1 we examine consensus errors to asses the fundamental properties of the graphs. In Sec. 5.2 we evaluate the performance of decentralized learning of DNN models by combining DSGD with graphs.
5.1 Test Consensus error investigation
Comparison graphs. We used three network configuration kn, (15)=(15,22) 2). (17, and (30. 2). all incorporating SNFs in mixing matrices, where n n= 17 a large prime number. For comparison purposes, we employed both static and dynamic graphs, considering fair communication degree
'Otee (n, k) configurratin are also tested in Appendix
8

---

(C1) Ring
(C2) Base 0en1)
(C3) Random (C4) (k*1) periite rand
keeer
(P2) cull-cascade
Consensus error A (c)
(a)
(n,k) = (15,2)
Consensus error (
(b)
(n,k) (17,2)
Consensus error A
(c)
(n,k)=(30,2)
.00
160
10"
10"
10
1
10
10
10
10
10
12
10
10
10
10:30
10:30
10
Iteration
Iteration
Iteration
Figure 3: Comparison of consensus error
(4)
to he minimized to zero for three (n, k) configurrttiss
(C1) Ring
(C2) (ase-(k+1)
(C3) Random
(C4) (krr)ee rand.
K-p)kr exp.
(P2) Null-cascade
(c1)
CIFAR-10, (30,)=330,2)
(a2) CIFAR-10O, (25,)-(15,2)
(b2) CIFAR-100, (n,k)=(17,2)
(c2) CIFAR-10D, (n.k)-(30,2)
Test accuracy,
Test Testacco accuracy
Test accuracy
Test Testacte accuracy
Communication round
Communication round
300 193 1120 1130
500 190 100 D30 100a
round Communication round
X
wa0 2a0 100 Te
Figure 4: Convergence curves using test accuracy of global parameters for four configurations.
Table 2: Comparison the highest test accuracy using global parameters.
Datasct (hetcrogeneity level)
CIFAR-
0.1)
CIFAR- 100 0.1)
(n, A) conotiiguaa
(al) (15, 2)
(bl) (17.2) 2)
(cl)
(30, 2)
(a2) (15. 2)
(b2) (17,2)
(c2) (30, 2)
Tosted graphs
test ace.
test acc.
test acc.
test acc.
test acc.
test acc.
(C1) Ring
0.8210
0.8773
0.7902
0.7140
0.7134
0.7192
(C2) Base-(ks+1)
4
0.8469
5
0.8727
5
0.8712
0.7145
0.7190
0.7275
(C3) Random
0,5815
1
0.4249
1
0.7828
0,1781
0.0835
0.4604
(C4) (R++ (-++1)-a parrtite random match
0.8556
0.8711
0.8691
0.7204
0.7185
0.7291
(PI) k-peer exponential
2
0.8371
2
0.8609
3
0.8709
0.7163
0.7170
0.7273
(P2) Null-cascade
3
0.8660
8
0.8817
4
0.8784
0.7213
0.7203
0.7329
(k= 2). The static graphs consist of (C1) ring graph, and (C3) random graph modeled in Erdos- Rényi random graph [5), adjusted to ensure & for each configuration. The dynamic graphs include a (C2) base-(k + graph and a (C4) 1)-aarttt random match graph, which is generalization of a bipartite graph, used in [43] to allow k-peer communication. The proposed graphs consist of (PI) k-peer exponential graph and (P2) null-cascade graph. Further details are provided in Appendix G
Evaluation metric. We computed the consensus error at each iteration as A (1) D"_(a00
3)2 where x! denotes local parameter (d [d=1] 1) the i-th node, and 7 1 Σ x; is global parameter. A desirable graph leads small consensus was drawn from Gaussian distribution / (0, 1), and performed 100 independent trials for each graph.
in fewer iterations. For each i, x²
Experimental results. Figure presents the consensus error for each (n, A) conffiuuration. As (C2) base-(k:+ (k++1 1) graph and (P2) null-cascade graph exhibit finite-time convergence, their consensus errors drop to zero after r iterations. As discussed in the previous section, for null-cascade graph tends to be small when the factorization of does not include large prime numbers. As result, null-cascade graph performs well in Figures 3)a) and (c). In contrast, (C2) base-(k + 1) graph is preferable in Figure because n = 17 is a large prime number, leading to a small т. Following these two graphs in performance are (C4) (A ))pprrttee random match graph and (P1) k-peer exponential graph. When n is equal to or slightly exceeds power of (k + 1). as in (c) (n,, k) = (30. 2), the consensus error of the k-peer exponential graph becomes small. This observation aligns with Theorem 2
5.2 Test 2: Decentralized learning of DNN models
Dataset and model. We investigated decentralized learning performance of each graph using image classification benchmark tests using CIFAR-10 and CIFAR-100 with ResNet18 [8]. The

---

batch normalization layers were replaced by group normalization layers 41 to account for potential data heterogeneity in local datasets. To experimentally assess robustness against data heterogeneity, the training dataset was divided into n nodes to follow Dirichlet distribution with concentration hyperparameter a [38] We set a = 0.1, representing a scenario with strong data heterogeneity. The data distributions across the n nodes are illustrated in Appendix G
Update rules. The DSGD algorithm used in our experiments outlined in Alg. 6 Appendix G which extends the update rules 2 to support multiple local parameter updates. The graphs used are identical to those in Test The learning rate 7 was pre-tuned, as provided in Appendix G As the evaluation metric, we used the test accuracy of the global parameter x(r) = -
Experimental results. Figure 4 illustrates the convergence curves using test accuracy of the global parameter under several configurations strongly heterogeneous setting (.1=..)). The highest test accuracy during the training is summarized in Table Among the tested (n, k))conffigurattonns the newly proposed (P2) null-cascade graph consistently achieved the highest test accuracy across most settings, including cases where is large prime number. As discussed in Sec. both (P2) null-cascade graph and (C2) base-(k (k+ 1) graph ensure finite-time convergence. However, they differ in degree uniformity and the periodic interval When the gap in is small, the non-uniform degree in (C2) base-(k + 1) graph leads to unbalanced model mixing, which negatively affects training performance. In contrast, (C4) (I 1)-partite random match graph and (P1) k-peer exponential graph exhibit performance comparable to (C2) base-(k + 1) graph, despite showing clear differences consensus error in Test 1. This can be attributed the fact that the degree of (C4) remains statistically uniform, while (P1) ensures strict degree uniformity. Although (CI) ring also has uniform degree, its performance is limited by small spectral gap. Our empirical results highlight that the proposed dynamic graphs, particularly the null-cascade graph, enhance decentralized learning under heterogeneous data settings.
Conclusion
We proposed two dynamic traphs-the k-peer exponential graph and the null-cascade graph- a result revisiting the 1-peer exponential graph. This reexamination revealed two key findings: (i) finite-time convergence can be achieved through cascade of null formation at all non-zero frequencies using T circulant matrices, and (ii) the expected spectral gap remains large for any n in the k-peer exponential graph with & 2 1. Leveraging these discoveries, the null-cascade graph is constructed to ensure finite-time convergence and commutativity for any n; however, this requires k > 2. Numerical experiments image classification tasks demonstrated that the null-cascade graph achieved the highest test accuracy compared to conventional graphs across most test settings.
10

---

References
[1] Assran, M., Loizou, N., Ballas, N., and Rabbat, M. (2019). Stochastic gradient push for distributed deep learning. In International Conference Machine Learning, pages 344-353 PMLR.
[2] Chen, Y., Yuan, K., Zhang, Y., Pan, P., Xu, Y., and Yin, W. (2021), Accelerating gossip SGD with periodic global averaging. In International Conference on Machine Learning, pages 1791-1802. PMLR.
[3] Di Lorenzo, and Scutari, G. (2016). Next: In-network nonconvex optimization. IEEE Transactions on Signal and Information Processing over Networks, 2(2):120-136.
[4] Ding, L., Jin, K., Ying, B.. Yuan, K., and Yin. W. (2023). Dsgd-ceca: Decentralized sgd with communication-opiine exact consensus algorithm. In International Conference on Machine Learning, pages 8067-8089. PMLR.
[5] Erdos, P., Rényi, A., et al. (1960). On the evolution of random graphs. Publ. math. inst. hung. acad. sci, 5(1):17-60.
[6] Gao, H. and Huang, H. (2020). Periodic stochastic gradient descent with momentum for decentralized training. arXiv preprint arXiv:2008. 10435.
[7] Gray, R. M. et (2006). Toeplitz and circulant matrices: review. Foundations and Trends@ in Communications and Information Theory, 2(3):155-239,
[8] He, K.,, Zhang. X., Ren, S., and Sun, J. (2016). Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778.
[9] Horváth, S. and Richtárik, P. (2020). better alternative efficient distributed learning. arXiv preprint arXiv:2006.11077.
feedback for communication-
[10] Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K., Charles, Z.,, Cormode, G., Cummings, R., et al. (2021). Advances and open problems federated learning. Foundations and trends machine learning, 14(1-2):1-210.
[11] Karimireddy, P., Kale, S., Mohri, M., Reddi, S., Stich, S., and Suresh, A. T. (2020). SCAF- FOLD: Stochastic controlled averaging for federated learning. In International Conference Machine Learning.
[12] Koloskova, A., Lin, T., and Stich, S. U. (2021). An improved analysis of gradient tracking for decentralized machine learning. Advances Neural Information Processing Systems, 34:1 1422- 1 11435.
[13] Koloskova, A., Loizou. N., Boreiri, S., Jaggi, M.. and Stich, (2020). A unified theory of decentralized SGD with changing topology and local updates. In International Conference on Machine Learning, pages 5381-5399 PMLR.
[14] Koloskova, A., Stich, S., and Jaggi, M. (2019). Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference on Machine Learning, pages 3478-3487 PMLR.
[15] Kong, L., Lin, T.. Koloskova, A., Jaggi. M., and Stich, S. (2021). Consensus control for decentralized deep learning. In International Conference on Machine Learning, pages 5686-5696. PMLR.
[16] Lian, X., Zhang, C., Zhang, H., Hsich, C.-J., Zhang, W., and Liu, J. (2017). Can decentralized algorithms outperform centralized algorithms? A case study for decentralized parallel stochastic gradient descent. Advances in Neural Information Processing Systems.
[17] Lian, X., Zhang, W., Zhang, C., and Liu, J. (2018). Asynchronous decentralized parallel stochastic gradient descent. International Conference on Machine Learning, pages 3043-3052. PMLR.
11

---

[18] Lin, T., Karimireddy, S. P., Stich, S. U., and Jaggi, M. (2021). Quasi maasi-global momentum: Accelerating decentralized deep learning on heterogeneous data. arXiv preprint arXiv:2102.04761.
[19] Liu, Y., Stich, S. U.. Lin Roger Wattenhofer, T., and Jaggi, M. (2021). Variance reduction in decentralized training over heterogeneous data. ETH Zurich Master's Thesis, 2020-May.
[20] Lopes, C. G. and Sayed, A. H. (2008). Diffusion least-mean squares over adaptive networks: Formulation and performance analysis. IEEE Transactions Signal Processing, 56(7):1122 3136.
[21] Lu, Y. and De Sa. C. (2020). Moniqua: Modulo quantized communication in decentralized SGD. In International Conference on Machine Learning, pages 6415-6425 PMLR.
[22] Marfoq, O., Xu, C., Neglia, G., and Vidal, R. (2020). Throughput-optimal topology design for cross-silo federated learning. Advances in Neural Information Processing Systems, 33:19478- 19487.
[23] McMahan, B., Moore, E.,, Ramage, D., Hampson, S., and Arcas, B. A. (2017). Communication- efficient learning of deep networks from decentralized data. In International Conference on Artificial Intelligence and Statistics.
[24] Nedić, A., Olshevsky, A., and Rabbat, M. G. (2018). Network topology and communication- computation tradeoffs in decentralized optimization. Proceedings of the IEEE, 106(5):953-976.
[25] Nedic, A., Olshevsky, A., and Shi, W. (2017). Achieving geometric convergence for distributed optimization over vireiig graphs. SIAM Journal on Optimization, 27(4):2597-2633.
[26] Nedic, A. and Ozdaglar, A. (2009). Distributed subgradient methods for multi-agent optimiza- tion. IEEE Transactions on Automatic Control, 54(1):48-5)
[27] Niwa, K., Harada, N., Zhang, G., and Kleijn, W. (2020). Edge-consensus learning: Deep learning on P2P networks with nonhomogeneous data. In International Conference on Knowledge Discovery and Data Mining.
[28] Niwa, K., Zhang, G., Kleijn, W. B., Harada, N., Sawada, H., and Fujino, A. (2021). Asyn- chronous decentralized optimization with implicit stochastic variance reduction. In International Conference on Machine Learning, pages 8195 8204. PMLR.
[29] Oppenheim, A. V. (1999). Discrete-time signal processing, Pearson Education India
[30] Pu, S. and Nedić, A. (2021). Distributed stochastic gradient tracking methods. Mathematical Programming. 187(1):409 457.
[31] Shi, G., Li, B., Johansson, M., and Johansson, K. H. (2015). Finite-time convergent gossiping. IEEE/ACM Transactions Networking, 24(5):7722-2944
[32] Song. Z., Li, W., Jin, K., Shi, L., Yan, M., Yin, W., and Yuan, K. (2022). Communication- efficient topologies for decentralized learning with o(1) consensus rate. Advances in Neural Information Processing Systems, 35:1073-1085.
[33] Takezawa, Y., Bao, H., Niwa, K., Sato, R., and Yamada, M. (2023). Momentum tracking: Momentum acceleration for decentralized deep learning on heterogeneous data. In Transactions on Machine Learning Research.
[34] Takezawa, Y., Niwa, K., and Yamada, M. (2022). Theoretical analysis of primal-dual algorithm for non-convex stochastic decentralized optimization. In arXiv.
[35] Takezawa, Y., Sato, R.. Bao, H., Niwa, K., and Yamada, M. (2024). Beyond exponential graph: Communication-efficii topologies for decentralized learning via finite-time convergence. Advances in Neural Information Processing Systems, 36.
[36] Tang, H., Gan, S., Zhang, C., Zhang, T., and Liu, J. (2018a) Communication compression for decentralized training. Advances in Neural Information Processing Systems, 31.
12

---

[37] Tang, H., Lian, X., Yan, M., Zhang, C., and Liu, J. (2018b). D²: decentralized training over decentralized data. arXiv preprint arXiv:183..070
[38] Vogels, T., He, L., Koloskova, A., Karimireddy, P., Lin, T., Stich, S. U., and Jaggi. M. (2021). Relaysum for decentralized deep learning on heterogeneous data, Advances in Neural Information Processing Systems, 34:28004-28011
[39] Vogels, T., Karimireddy, S. P., and Jaggi, M. (2020). Practical low-rank communication compression in decentralized deep learning. Advances Neural Information Processing Systems, 33:14171-14181.
[40] Wang, J., Sahu, A. K., Yang, Z., Joshi, G., and Kar, S. (2019). Matcha: Speeding up decentral- ized sgd via matching decomposition sampling. In 2019 Sixth Indian Control Conference (ICC), pages 299-300. IEEE.
[41] Wu, Y. and He, K. (2018). Group normalization. In European Conference on Computer Vision.
[42] Xin, R. and Khan, U. A. (2019). Distributed heavy-ball: A generalization and acceleration of first-order methods with gradient tracking. IEEE Transactions on Automatic Control, 65(6):2627- 2633.
[43] Ying, B., Yuan, K., Chen, Y., Hu, H., Pan, P., and Yin, W. (2021). Exponential graph is provably efficient for decentralized deep training. Advances in Neural Information Processing Systems, 34:1 34:13975-13987.
[44] You, R. and Pu, S. (2024). B-ary tree push-pul method is provably efficient for decentralized learning on heterogeneous data. arXiv preprint arXiv:2404.05554.
[45] Yu, H., Jin, R., and Yang. S. (2019). On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization. In International Conference on Machine Learning, pages 7184-7193 PMLR.
[46] Yuan, K., Chen, Y., Huang, X., Zhang, Y., Pan, P., Xu, Y., and Yin, W. (2021). Decentlam: Decentralized momentum sgd for large-batch deep training. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 3029-3039.
[47] Zhang, G. and Heusdens, R. (2017). Distributed optimization using the primal-dual method of multipliers. IEEE Transactions on Signal and Information Processing over Networks, 4(1):173- 187.
[48] Zhao, H., Li, B., Li, Z., Richtárik, P., and Chi. Y. (2022). Beer: Fast O(1/T) rate for decentral- ized nonconvex optimization with communication compression. Advances in Neural Information Processing Systems, 35:31653-31667
[49] Zhu, T., He, F., Zhang, L., Niu, Z., Song, M., and Tao, D. (2022). Topology-aware generalization of decentralized sgd. In International Conference on Machine Learning, pages 11479-27553..
PMLR.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Limitations are discussed in Appendix
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Source code is provided supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer: [Yes]
Justification:
We provide source code as supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppp.ccppulli//guuii wwwiicccguie//eeeeeeeeeis CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide experimental setup details in Appendix G.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We provide error bars in Appendix G.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
16

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA].
Justification: Due to limitations computing resources, we prioritized increasing the variety of benchmark tests. Additional experiments be included in the revised version.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics htttp:://euurpp http:///aaap..ccoooooococtttetea
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We note the impact statement Appendix J.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: Since our paper provides dynamic graphs for communication decen- tralized learning, data or models are not provided.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the Datasets.papersstt paperswi thcode. cow/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemmodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not include crowdsourcing experiments and research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation,
or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Our paper does not include human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
19

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: We use LLMs as check for spelling and grammar.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy for what should or should not be described.
20

---

A Technical details for the k-peer exponential graph in Sec.
Technical proof' for Sec. are summarized in Sec. A. and A.2 After introducing preliminaries
regarding the calculation null frequencies using eirculant mixing matrices in Sec. A.3 several
examples of the k-peer exponential graph are illustrated in Sec. A.4
A.1 Proof of Lemma
We investigated the frequency response of expanded sequences (2). is equivalently reformulated
as hm (i) = - hs))((i - ms) using original sequence h(i). Hence, applying DFT results
Hm (c²
him(t)e (i)e
00
h(s) ms) -iwi
00
h(s)e-Jnne Jums
H (el
This indicates that the frequency response of the expanded sequence can represented by shifting the frequency response of the original sequence H(elw).
A.2 Proof of Theorem
We computed the expected consensus rate of the k-peer exponential graph. As described in Sec. 3 the k-peer exponential graph (4) consists of [logx41 (n)1 eirculant mixing matrices (")) for E 10.1...., - 1}. It can be decomposed by using DFT matrix D as
w D
(C) tmme
D,
where the eigenvalue matrix is H ())
diag((H)) Tmee (0),
((2 time (n 1)]), with
Time
n-1 N00 (i)e 2//wi// in 10.1....,n-11
H(0 (1w)
In the k-peer exponential graph, we employed filter sequence of length (k++1), where each sequence expanded the order m. (I++1).. This results the sequence [h (O)..... ., n (1) fme (n 1)} for each L {0, (0..,,..,7 T 1}. As described in (8), the frequency response (amplitude) the expanded (Ie + 1)-length MAF with order my is given by
sin sun( (k: + 1)/2)
((()) Tmny
(clw)
exp J/mak/2
(EE (0, 1, 1-.....-.1111 1}).
ls ++1
sin(wme//)
As noted in Sec. 3 the angular frequency and frequency indices in E {O,.... ... ... n 1} are related by 2wiw/n. By substituting it into the above equation, we can compute the frequency response at frequency indices in E {O...., n
sin(Trimm(( - 1)/n)
H Tmm (tw)
k+1 sin(Ti.me/n) exp jriumek/n (EE(O, 1,..,,,,,,,.1111111 7- E10..,,).
where the DC component holds [1 (0) = 1, which is the maximum eigenvalue of ( which is denoted by A (W))). The expected consensus rate corresponds to the second-largest eigenvalue of (!)), which is denoted by A₂ Az(((0), and can be computed by selecting the maximum argument
21

---

of nonzero frequency responses (amplitude), formulated as:
A2 (2
11 (9 tyme (iw)
max
me + 1)/n) exp jotumek//
max
k+ 1
sin(Ti + 1)/m)
max
(eE 10. 1}).
++1
sin(Tri.me/n)
Thus, the expected consensus rate (product of mixing matrices) can be calculated as p 1 (2(W ... w(--1))
sin(Ti + 1)/n)
exp -brummek/
1 max
k
min(Ti
t=0
r-1
sin(Tisme(k + 1)/n)
max
(10)
k
min(Ti_,me/n)
t=0
In our k-peer exponential graph, the exponential expansion me = (I + 1) is employed. Substituting
my ( 1) into I0 results in:
sin( (k: + 1)) sin(Ti (k: 1)2/n)
sin(Ti + 1)7
max
(k: + 1)
sin( L (l + 1). //) sin( (k + 1) /))
sin (k + 1)/-1/n)
sin(Ti (k: + /n)
=1 max
(11)
(LE(,,..,, 1}
(k: + 1)7
sin (iiu//))
For specific n (a power of k + namely, (k + 1)²), substituting it into (11) results in: sin(Ti (k: + 1)" + 1)")
(k: + 1)7 sin ( ///////// (k
1)r)
1.
E. n- 1}
(k + 1)T sin(Tii + 1)5)
Otherwise, for any the expected consensus rate results in:
sin(Ti + 1)7/n)
p= max
(T = [loge-1 (m)])-
(l (k 1) sin sin(Ti./n))
These results summarized in Theorem 2 Thanks the exponential expansion my (k: + 1)e. division is recursively simplified (via cancellation of units) the first reformulation of (II), which refer to the exponential expansion trick. This is crucial for demonstrating the efficiency of the k-peer exponential graph across n. and was not explored in the previous study 43
A.3 Calculation of null frequencies for circulant matrix employing MAFs
First, we review the principles underlying the 1-peer exponential graph explored in Sec. Consider a sequence of length (Ce + 1), denoted by (0), (1), ..... (cx) for & E (0, 1,.,,,1-11}
Following Definition 7 the expanded sequence with order me, resulting in n-length sequence
(9) (0), (1) (1), pmm (n 1)} Tm,
[ (1) i= O=......c
(9) h fm, (ime) =
0
herwise
A circulant mixing matrix employing this sequence is given by
h (0)
h (10) (n-1)
(1)
Prmm
Time
h (E)
(1)
( (0)
h
him (2)
(f) circ(hi (0), (1 (1).... 1110 (n-1))
h him, (2)
home (1)
(e)
h (3)
h hime (n 11)
(8)
nim (n-2 2))
mi (0)
22

---

As performed in 5
eigenvalues of this is obtained by applying DFT, as
W =D
DJ H ! tms D;
where D denotes the DFT matrix and the eigenvalue matrix
is
H
(4) tmz
diag((H (0),
H tmo (n 1))), with
(kw) tiee
Σ pme (i)e 2//w.// in E (0, 1.......,,
n n- 1}.
(12)
As mentioned in the main paper, the use of a doubly stochastic sequence ensures that Σ 1. (i) = 1, preserving the DC component H (0) = 1. This is the maximum eigen-
(f) value, since the sequence (h
1 (n 1)} is positive-definite
MAF used as a sequence (i)
Next, we identify the null frequencies when applying the MAFs discussed Sec. 3.2 Suppose that the MAF with (ce 1)-Length is employed as filter sequence:
(1)
(i-
C2 +1
Associated with this, the expanded sequence with order my results in n-length filter sequence (M (0), M (1)....,hi) / (n 1)}. As illustrated in (8), the frequency response regarding (continuous) angular frequency w is given by
sin(wme(cc++) +
H (c
exp juumce/2
Ce c++1
sin(wm:/2)
where frequency index in and angular frequency w are related by w 2xiw/n. As proven in Sec. null frequencies can be identified as follows:
B.I.
A (1)
Null frequency in is multiples of
n
excluding multiples of n within in E 10,
MAF
melce me(ce+1)'
mg
(13)
23

---

A.4 Examples of k-peer exponential graph
Example (k-peer exponential graph). Given (n, k) constructed using T T= (16) =4 circulant matrices:
(16, 1), the 1-peer exponential graph is
w circ( 1, 0,0,0
14 zeros
w circ 1.2 0, 2. 0, O,
( circ 2. 0,0,0, 2 0,0,0 0, O. 0. 0),
zeros
W cirol 1: 0,0,
O, 0, 0,
zeros
zeros
Next, null indices identified for each mixing matrix (0, 2, using 13 as:
Nrt) 3 {8};
(MAP with
16, 1, mo 2 1);
N( 9 (4, 12),
(MAF n 16, = 1,m 2 2)
N/t2 ş (2 14)
(MAF with n 16, c2 1, my 2 4/
A/t3 e (1,3, 5, 7, 11, 13, 15),
(MAF with 16, & 1,mg 8)
Combining the above four null frequency sets satisfies confirming that Example 7 satisfies finite-time convergence.
0)
(1
()
= 33
0.4
O
0.2
0.1
0.05
Figure 5: Mixing matrices of ppper exponential graph with (n, k) = (16, 1). Each graph consists of 16 nodes, depicted as black dots arranged in a circle and interconnected by lines. The colors of these lines indicate the mixing weights between nodes in (
W
W
22)
Product of all mixing matrices)
08
Amplitude
06
Frequency indices (0 n)
Figure 6: Frequency characteristics (amplitude) of each sequence.
24

---

Example 2 (k-peer exponential graph). Given (n, k) (27, the 1-peer exponential graph is
constructed using r= logg (24)] circulant matrices:
1 1 ( circ
0,0, 0,0,....0)
21 21
25 zeros
( circl $ 0, f4400 0. 0,
23 zoros
W circ 2. 0,0,0,
( ciro( 2' 0,0, 0.
zeros
18 zeroa
However, null indices for each mixing matrix {0, 2,3,4444 4) E using
form the following:
( A
(MAF
me = 14,
{
81
mi = 2) (MAF with 27, C1
A/22 (
81
135 189
(MAF with n 27, 1, 2 4),
1 5
A
27
135 189
243
297
351
405 T, (MAF with 27, cq my 8),
16 16 10
16
Since 6 is not satisfied, Example i not finite-time convergence graph.
(1
(1
(1 2)
(1
0.4
0.2
0,1
0.05
Figure 7: Mixing matrices of k-peer exponential graph with (n, = (27, 1). Each graph consists of 27 nodes, depicted as black dots arranged in a circle and interconnected by lines. The colors of these lines indicate the mixing weights between nodes in (
W
W1
2
W
Product of all mixing matrices
08
Amplitude
0.6
Frequency indices (0 m)
Figure 8: Frequency characteristics (amplitude) of each sequence.
25

---

Example 3 (k-peer exponential graph). For (n, k) = (27, 2), the 2-peer exponential graph consists of =3 mixing matrices:
w circ(
1 1 0,0,...,
3: 31 31
24 zeros
w cire( ciro($,0,0, f. 0,0,
0, 0. 0.
18 xeros
W circl3 3. 0,0,
0. 0).
Next, null frequency sets are identified for each mixing matrix {0. 1, l using 13
N 3 (9,18),
(MAF with 27, k 2, 3 1);
~ 3 (3.6.1.115211244))
(MAF with 27, l 3 3),
M [[226677401111144117110222333333
(MAF with 27, m2 32
Since this also fulfills O6. Example is confirmed to be a finite-time convergent graph
0)
(
(1
0.5
0.4
0.3
0.2
0.1
0.05
Figure 9: Mixing matrices of k-pper exponential graph with (n, k) = (27, 2). Each graph consists of 27 nodes, depicted as black dots arranged in circle and interconnected by lines. The colors of these lines indicate the mixing weights between nodes in W(())
w
Product of all mixing matrioes
Amplitude
0.6
0.
16
Frequency indices (0 m)
Figure 10: Frequency characteristics (amplitude) of each sequence.
26

---

B Technical details for null-cascade graph in Sec.
Technical proofs of lemmas and theorems in Sec. are shown in Sec. B.1
B33
Section [8.4 provides
the invariant property regarding the circulant shifting, which involves assigning maximum weight to the targeted node. Subroutines used in Alg. aare detailed Sec. B.5 Associated example graphs are illustrated in Sec. B.6
B.1 Proof of Lemma
In (8) the frequency response of MAF with communication order e and expansion order my is formulated. To determine the frequency indices at which the frequency response of the expanded
MAF becomes zero (nulls), need to find the angular frequencies such that the numerator of ( equals zero; namely, sin(wmr(cc+ 22) = O. This satisfies when wine (cent(()))))) = ΦT where 2
is an integer. This yields w mp(ec+T) Considering & ranges from 0 to me(cr+) - 1. However,
since the DC component (w 0) is not null and periodicity due to the expansion from Definition
7 Φ can be determined such that multiples of 1, excluding multiples of (ce + 1). consisting of {1..... (ce + 1) 1, 1) + 1, ................................ 2(cz 1) 2(ce + 1) I..... (me
1)(ce +
1, (me - 1)(cz + +1 1,.., me + - 1}. Thus, nulls can be obtained at multiples of 2x m=(er+1)
excluding multiples of 2 From the fact that the angular frequency w and frequency indices iw m.
are related by w = 2 /,, this can be reformulated: in can be determined such that multiples of me(ce+T]. excluding multiples of within in [0, 2T):
me
{ Null frequency in is multiples of meleeti)+ excluding multiples a within in E
[0, m)
B.2 Proof of Lemma
Recall from Definition 8 the fundamental property of SNE, which forms cr 2 nulls at ge and their conjugates Ui n ye for vi E (l...., 22/ From Definition 7 the expanded SNF with order my, null frequencies can shifted by 1/mz. Therefore, the null frequencies are identified follows:
{ Null frequency in is ton my
2 +on for 2/ {l,..., c E me
and
me
1} within is e. [0.
B.3 Proof of Theorem 3
First, we explain our proof strategy demonstrating that the null-cascade graph achieves finite-time convergence for any n. As explained in Secß] when a graph consists of 7 circulant mixing matrices as Definition]] [ achieves finite-time convergence when cascading these T mixing matrices results in null formation all non-zero frequencies i. E (1...., n - 1). as demonstrated in (6) Utilizing this principle, if we calculate set of null frequency indices for each (E E (O...., 1}) within the null-cascade graph and demonstrate that the union these sets covers all non-zero frequencies, the finite-time convergence property in the null-cascade graph can be established.
Suppose is factorized as IT (v: + 11, where u S... S S Ma+1 S... with each i E (line 2 in Alg. D. Initially, the remaining frequencies to be nullified, iy E {l..... ...77 1}. are cquivalently represented as multiples of b= within the interval [0, n) (line I in Alg. Given the factorization n, the task of nullifying all non-zero frequencies can be interpreted as applying mixing matrices to form nulls at multiples of 6, excluding multiples of b(n, + 1)-rrfeerre to frequencies associated with 24 in the main paper. This process is repeated sequentially until b reaches n. Once equals n, nullification at non-zen non-zero frequencies i f1...., is on generating filters to form nulls specifically at multiples of b excluding multiples of b(v; + 1).
1} is accomplished. Thus, the focus
In Step (lines of Alg. D we utilize MAFs with dynamic selection of communication order es and expansion order my to nullify frequencies associated with {M1,..., (x) satisfying v S According to Lemma] forming nulls frequencies associated with (. k) is straightforward. In
27

---

line 4 in Alg. 1. we sequentially select from V/ down to as ce E [ k)1)), because many nulls can be efficintlyy formed by choosing the largest possible values for both cæ and mg. In lines and 6 in Alg. [ (co, mo) are selected (with initialization b 1) as
I (M++1] (Mo+1)6
(v++1
Co VKy
mg
+1]6
Pc+1
() 1,+ ......)) (vs 1).
After generating an expanded MAF with (co, ma)) corresponding mixing matrix W is calculated
(lines 7 in Alg. D. According to Lemma 2 this mixing matrix enables to formation of nulls
at frequencies that are multiples of m1)co+1)
b, while excluding multiples of x = [Co + 1)..
Consequently, the base number to be nullified is updated to b <- b(px + 1) + 1 (line 10 in Alg.
D This process eliminates the frequencies associated with a factor Mx.
In Step 1, this process is repeated to sequentially nullify the frequencies associated with factors ( satisfying 14 k. For each factor i (L....,k), (c,, m,, given by Alg. [ caa be generalized as
C =K-hs my =
(os + 1), b= b= -IIEEt(x-0) (). (p 1).
Repeating this process (Step 1) times results in
--1 v1, mx-1 Ile [ ((x+((()))))))))) ()...) (v + 1), b (2,.. (ez + 1).
This indicates that the remaining frequencies to be nullified after the cascade of MAFs are identified multiples of 6 [I......... (v: + 1).
To nullify the remaining frequencies associated with the factors {Me+1,.... ; V>} satisfying 1/ > k Step 2 involves generating SNFs with fixed communication order Cj 2 2 specified in Definition 8 According to Lemma 3 nulls can be formed at frequencies to and their conjugates +on
where (1, ct/2] and Φ E (0,...,,M) me 1). While each SNF can generate many nulls depending on the choice of (me, qt,)),, we particularly focus on the frequencies when setting
me
0: specifically, (_t,) Lim)), where (v {l...., The selection of (me, (r,v) in Alg. me is strategically chosen to align q/. with the remaining target frequencies associated with <;(> k) (multiples of b). To generate nulls at multiples of b; Tant [1;) ) [v//ce] SNFs are required to form nulls at remaining frequencies associated with (> k), since C, = 21 After these frequencies are nullified, the base number to be nullified is updated to b = IIi (i.(1.....A-1111.. iit......... (v: + 1) (line
i9 Alg. []. By repeating this nullification process with SNFs, b, eventually becomes reaches as This comprehensive nullification at non-zero frequencies ensures that finite-time convergence is achieved within the mull-cascade graph.
b [IEE(....))) +
B.4 Invariant frequency amplitude regarding cireulant-shiftin
When using non-um non-uniform weights (e.g., SNFs introduced in Sec. 4.. assigning the maximum weight to the local model held by each node would be effective in decentralized learning. To this aim, the following lemma is effective for circulant-shifting of the filter sequence (e.g., used Alg. 3
Lemma 4 (Invariant frequency amplitude regarding circulant shifting). Suppose n-length sequence (h(0), h(1)..... h(n })} and its frequency response Hee"). Its circulant shifted sequence with order u is defined by hi) = h(l -u) mod n) and its frequency response is denoted by H (emu(e")) The frequency response (amplitude) of the circulant shifted sequence is invariant for any u.
|H = [H(e))))
Proof. Suppose that n-length sequence (h(0), h())) ......,,,nn (()] and its frequency response H ((e))) are given by
n-1
H(el)) = Σ h(() exp exp-iwi -woi
0=0
28

---

The circulant shift with shifting order is defined by (i) h((2 u) mod n). which is is
equivalent generate the following sequence: {h- ho), h_ h- (n-1) [h(u), h(u 1),-..: h(n 1), h())..................... ,,(u 1)}. The frequency response of it is given by:
H_
h h (i) exp jui
h (i + u) exp ji((it))
n-1
exp
Juu
h (i + u) exp
Jus
1=0
H (el
exp
Jun
Since |H
H(el") wul |H the frequency amplitude regarding circulant shifting
is invariant.
Based on Lemma Alg. 2 is constructed. This is a subroutine of Alg.
Algorithm 2 Circulant shifting function
1: function (t) = Cireulan(Shiftingg((())
2: Ciurculant shifting assign maximum weight to local node
3: u arg max, (h(1))
4: (0), h-u ..... (n 1)] = [h(u), ..... h(n 1)), ...())............. h(u -1)]
B.5 Subroutines to compute SNFs
subroutine used in Alg. is outlined in Alg. 3 The aim of this subroutine is to nullify the remaining frequencies associated with the factors {M 2x} satisfying 1; k by generating SNFs. As described in Definition X SNFs that form nulls at target frequencies can be obtained by solving a polynomial expression. Specifically, line 2 (calling the subroutine in Alg. 4 selects compute (me, pr,)) for 1/ E (1,...,,e, ce/2), . and lines computtee the conjugate frequency indices. Following (9) the polynomial is expressed with roots corresponding
frequency indices (ge.1..... /2, and their conjugate frequency indices {-ē .... F.,o/22 in line & yielding c--order polynomial equation of the form: 7())=* + 7(CE 1)x + 7 (CE). To ensure the doubly stochastic property
in (cr + 1)-length filter sequence, the normalized filter sequence is computed in lines 10
12 In line
14, thanks to the invariant frequency amplitude regarding circulant shifting, detailed in Lemma maximum weight assigned to the local model held by each node would be effective in decentralized
4 the
learning.
Next, we briefly explain the core functionality of Alg. for selecting (me, to nullify frequencies associated with 74. As discussed in Sec. B.3 the selection of (m&, Pe,.) is not uniquely determined. Therefore, an implementation for selecting Pt,w) is introduced in Alg. 4 which can be improved in future work. As outlined in Definition for two reasons: (i) the desire to use an even value of Gr to form pairwise nulls in the conjugate relationship for real-valued filter sequence, and (ii) the goal of achieving as many nulls as possible.
communication order is set as Cj _ in line 6
According to Lemma 3 nulls can be formed at frequencies Ke+tón and their conjugates t.
my where vi { 2) and E (O..... me 1}. While each SNF can generate many nulls depending on the choice of (me, (. we particularly focus on the frequencies when setting Φ = 0:
specifically, ( (2._ L.=). where (1' {L...., ct c2/2). To generate nulls at multiples of by. (anr(P
me me
[us/cr] SNFs are required to form nulls at remaining frequencies associated with <3(> k), since C = -. After these frequencies are nullified, the base number be nullified is updated to
b = (1.m.....
(vs + 1) (line 19 in Alg. Db.
29

---

Finally, runtime cost and implementation of Alg. 4 is briefty noted. Firstly our source code associated with Alg. 1 available on GitHub (see Abstract). Alg. I are straightforward to implement and incur negligible runtime overhead. Alg. + which is used to select the roots qe. expansions my, and communication orders ce for computing SNFs, may be complex to implement and may introduce noticeable runtime costs. This potential complexity stems from the fact that combinations of Me, Gt) are not uniquely determined, requiring a greedy search to identify suitable candidates. While we have not exhaustively evaluated the runtime cost for all possible (n, k) ko-coffiiurrttoons we confirm that for those configurations tested in our experiments (as reported in Section 5 and Appendix F), the runtime costs were negligible.
Algorithm 3 SNF: a subroutine of Alg.
1: function (0) ...., 75 (m 1) (lmm... SNF (n, k. Vs b)
2: {cg, m, pj. //.../2)) Fm(()) = SelectOrders(n,, k, Uss b)
/ Alg. $
3: for ..... smt [1) do
4: for 1 -....., Cj/ do
5:
G, = g5 8s conjugate frequency index to be nullified */
6: end for
7:
compute coefficients of polynomial equation
8:
/T/ el2m0s,v (x wi2mg).//)
- ..
+ .......... +25(0
+ 755())
9:
& compute the normalized sequence
10:
for O.... Cj do
11:
7, = (1) Σ (1)
12:
end for
13: circulant shifting after expansion with order my
14:
70()) = CirculanSSiftinng7,, (1)) 1e Alg. 2
15: end for
30

---

Algorithm 4 implementation of subroutine select roots, expansions, and communication orders
function
{cz, Mcy Ii.1.-.. (2
Select k. V4, b)
2: B E { vit11 4+11"
2n
[u//2|n] 1 frequency indices be nullified */
m++1
3: Mhase [Mc+1]5
1 base expansion order corresponding to factorization number v4 "/
4: j= 0
1 SNF index be incremented */
5: while (1) do
6:
Gj 2
1 we use an even number less than i used as communication order */
7:
Mump =
1 temporary expansion order to incrementally search */
8: > compute roots of a polynomial equation and expansion order
9:
StelectPreqIndicees are selected from the higher indices of B. If |1 cj/2, other frequencies such that interpolates
(Rj (1.......
22) f cj/2 frequency indices to be nullified
B are selected. */
10:
while (1) do
11:
Mamp 2 then
12:
for I.... c2/2 do
13:
fi munp 4i.v
1* expanded SNF used */
14:
end for end if
15:
16:
for d 1....,,, c2/2 do
17:
G. = n1 Vi 1 conjugate frequency index to be nullified */
18:
end for
19:
compute coefficients of polynomial equation
I (x /Rzo,,/")(x e = +... +
20:
21:
(0). (c()))))((),))) are positive definite real numbers then 3=3 / hampmmmpppe) selm.ppeel.....////// /* remove nullified frequency indices */
22:
23:
break
24:
else
25:
Mump Mamp + 1* expansion order increment */ end if
27: end while
> expansion order m,
29:
m, Mbuse Mamp
j = =
/" SNF index increment */
31:
if mamp 2 then
32:
Factorization 74mp = M Mmn where #1 ... S Myy and fn
33:
for V. do
34:
Cj = =]
35:
my Mibas M4e
36:
for = l...., Cy c do
37:
Ui 1/-1, end for
38:
39:
3 { Mls F (1....e))))) / remove nullified frequency indices */ 1 SNF index increment */
40:
j j +1
41:
end for
42:
end if
43:
if O (If set of frequencies be nullified is empty) then
44:
break
end if
46:
end while
(v) j
/* number of mixing matrices employing SNFs
31

---

B.6 Examples of null-cascade graph
Example (Null-cascade graph). Given (n, k)) (15, where can factorized as 5 x 3. Since k = 2, n is not composite number that can be factorized using only integers less than or equal + 1 3. The null-cascade graph consists of T 4 circulant matrices, as
( circ(3: 0,. O.....0, 3 O,
3
zeros
zercs
zeros
( cire(
-2 2n (ooos(2n-(6111) (6/15)
O, 2 (0/16/)))) O.....9
coal (0a (2T 0),
c00l (6/15))
12 zeros
( cire h- 22 2-2 c02 0, O,....9. 2-2 (67166)
2cos((m-(6/25))
12 zeros
where null responses for each f 1,, are obtained at following frequency indices:
N (1,2,4,5, 7,8, 10, 11, 11,13,144
(Step MAF with 15, m, 5),
M( (3, 2: 2 12),
(Step
15,
2,m 2. (91,1 fi,1) (6.9) (6,9))
N(2) - {6,9).
(Step 2: SMF with
15, 2, m2 1. (92,1 95,1 = (6,9)).
Combining the above four null frequency sets satisfies finite-time convergence.
confirming that Example satisfies
(1 (1= 0)
(1 1)
(I = 2)
0.3
0.2
0,05
Figure 11: Mixing matrices of null-cascade graph with (n, k) = (15, 2). Each graph consists of 15 nodes, depicted as black dots arranged in circle and interconnected by lines. The colors of these lines indicate the mixing weights between nodes in (
(2)
Product mixing matrices
0.
Amplitude
06
02
Frequency indices (0
Figure 12: Frequency characteristics (amplitude) of each sequence.
32

---

(17,2) where can be factorized as n 17. Since k 2. n is not a composite number that can be factorized using only integers less than or equal to k- = 3. The null-cascade graph consists of 8 circulant matrices, as
Example 5 caullecascade graph). Given (n.k) k)
( circ( 2 c00 200 (6711)))) 0,0, 0,0,0,0, cosl (6/ [T]
-2000(2m-13 (5/17)
0, O, 0, 2-2 2-2 cos 2x
0),
( = circ(,
0, 0.000.0000000000000000000 0, 0, 2 2 22 0,000,,,,
cos 2 (5/17)
2-2 cos 20122m15///0 (5/17)) 2 coss 2n (5/17)) 2 cos 2T (5/17)
W (2) circ
(os((xx((//1))
noad 0), (6 6/17)) 00001100001000000000000000000000
2 (os(22
( circ
2 (0s(2x(66/17)
cost (mm-((6/717)
(6/17))
( cire
2 (oos(xx(6/17))
cos 2T 0tt.://p.......................0 cost 2 17)) 0),
2 (6/12))
(() circ
(2x(17((8/17)
000,0,0,0,0,0,0,,,,00000,, 208 (8/17)) 0),
2 cos (2
2- cos (2x (20-01xx11111
( = circ
2eos(2r (8/17)
1
2-2 cost (871())
2-2 cos 2m (8/17)
cos 2 (8/17)
( = circ
2 cosl (2x cxx (2x1(7117)
0, 0, 0, 0, 0.
cool
2 2-2200(22 (7/17)
where null responses for each E 10,1,... ...., 7 are obtained at the following frequency indices:
A 3 (1, 12 22
5:
29
5
51
30
46
56
63
73
5
16),
(Step SNF with 17, 2,mo (10.1. 16.1) (5. 12)),
M(O) 9 (5, 12]
(Step 2: SNF with 17, c = 2, m. 1, (.. = (5, 12)),
W e (2, 11
3 3
23
28
40 3
15}
(Step 2: SNF with 1 = 17, 2, 3, (02,1 43, ) = (6. 11)),
A( e 16]
(Step SNF with
cq ms 1, (4s 93 = [6. 11)),
A(0 9 (3, 2: 23 14] 9 25
(Step with v2 17, ca 2, m. (4t. 9. ) (6. 11)),
A/( 9 (4, T: 13] 13]
(Sep 2: SNF with 17, 0s 2, ms 2, (06.1 (Z.) (8. (,)))
A/ a (8,9)
(Step with 17, Co mm 1, (96.1 1: 43 = (8. 9)),
AOO) e 17)
(Step 2: SNF with
17,07 2, m2 1, (0r.3. = (7. 10)).
Combining the above four null frequency sets satisfies finite-time convergence.
6 conftrming that Example S
satisfies
33

---

(1 =
(== 1)
(1= 2)
(1
03
(1=4 4)
(1
Figure 13: Mixing matrices of null-cascade graph with (n, k) (17, Each graph consists of n 17 nodes, depicted as black dots arranged in a circle and interconnected by lines. The colors of these lines indicate the mixing weights between nodes in (
W
W
W
Product of all mixing matrices
08
Amplitude iitud
0.6
Frequency indices (0 m)
Figure 14: Frequency characteristics (amplitude) of each sequence.
34

---

Example 6 (Null-cascade graph). Given (n, k) (30,2), 2), where can be factorized as 30 5 x 3 Since 2, n not composite number that can be factorized using only integers less than equal to k 3. The null-cascade graph consists of 4 circulant matrices,
W circ 3: O,
zeross
zeros
( circ(
2
meross
zoros
( circ(
- 2 cns (2x (12/30))
O, 222c
0.
2 2cas/ (0 (12/30)) 0),
1
2-2 cost (1
25 zeros
3( circ(
22x (12/30))
0.....9 2 c05 (22(312300))
2-2 2-2 cosl 2m (12/30)) 2-2 cos (12/30)
where null responses for each E (0,1,2.3) are obtained at the following frequency indices:
~10) (1,2,4,5, 2, 10, 11. 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29), (Step MAF with 30, 2, 10,
M0 (3,9, 15, 27,
(Step 1: MAF with 30, = 2,m, = 5,
A( {6, 9, 24],
(Step 2: SNF with 30, c2 2, m2 2, (42, 93,1 = (12, 18)),
Ar3) {12, 18),
(Step 2: SNF with 30, 2, (4 95.1) (12, 18)).
Combining the above four null frequency sets satisfies finite-time convergence.
confirming that Example 6 satisfies
0)
11
1
(1 3)
0.5
0.4
0.3
0,2
0.1
0.05
Figure 15: Mixing matrices of null call-ca graph with (n, k) = (30, 2). Each graph consists of n 30 nodes, depicted as black dots arranged in a circle and interconnected by lines. The colors of these lines indicate the mixing weights between nodes in (
(1)
22)
W
Product of mixing matrices
Amplitude
0.6
0.
02
14
15
16
17
18
19
20
21
22
23
Frequency indices
n)
Figure Frequency characteristics (amplitude) of each sequence.
35

---

Example (Null-cascade graph). Given (n. k) (60,4) where can be factorized as = 60 5 x 4 Since & 4. n is composite number that can be factorized using integers less than or equal to k + 1 5. The mull-cascade graph consists of = 3 circulant matrices, as
W (0)) =circ( ,,.,.,,, t
O,
5: 0.....9)
11
zerOs
11
11
W ciro 0,0, 0. 0.
0,
0,
W = ciro( 1
3 3: 3 O, O,...,0,
Beros
where null responses for each E 1,, are obtained at the following frequency indices
NOO) (1,2,33,,6,7,,88 8, 9, 12,11,11,1, 13, 14. 16, 17, 18, 19, 21, 22, 23, 24, 26, 27, 28, 29, 32, 34, 36,37, 38, 39, 41, 42, 43, 44, 46, 47, 48, 49, 51, 52, 53, 54, 56, 57, 58, 59),
(Step
60 mo 12),
M(0) 9 (5, 10, 15, 25, 35, 45, 55,,,, A/ e 40),40),
(Ste
3, m, 3) 60,
(Step 1: MAF with n 60. 2, m2 1).
Combining the above three null frequency satisfies (6. confirming that Example 7 satisfies finite-time convergence.
(1 0)
(1=1)
(1 2)
0.5
0.4
0.3
022
0.1
0.05
Figure 17: Mixing matrices of null-cascade graph with (n, k) (60,4). Each graph consists of n 60 nodes, depicted as black dots arranged in a circle and interconnected by lines. The colors of these lines indicate the mixing weights between nodes in (
w
Product of all mixing matrices
Amplitude
0.6
0.4
15
233443 25 30 37
50
Frequency indices (0
Figure 18: Frequency characteristics (amplitude) of each sequence.
36

---

Example (Null-cascade graph). Given (n, k) (60, 3), where can be factorized as 60 5 x 4 Since 3. n not composite number that can be factorized using only integers less than equal to k 4. The null-cascade graph consists of circulant matrices,
W circ
:: o,....0. 1 0 .
7.
1:
14
14
14 zeros
14
( circ( 3. 1,0.0,0000
0,0,0, 0. 0,
0, 0,
( ciro(
- -2nns (24/002
0, 22 (24) 60))
2- 2cos(22 (27-/666))) 0),
2-2 2-2 (24466)))
55 zeros
W (3) circ( 2-2 cosl
cosl 2m (24/60)) 2-2 coos c (24/66))
2 c0 (2-((6660)))
where null responses for each E (0,1,233 are obtained at the following frequency indices
NO 3 (1,2,3,5, 7,9, 10, 11, 13, 14, 15, 17, 18, 19, 21, 22, 23, 25, 26, 27, 29, 30, 31, 34, 37,38, 39, 31, 42, 43,45, 45, 46, 47, 49, 50, 51, 53, 54, 55, 57, 58, 59).
(Step 1: MAF with 60, m,
M 3 (4,8, 16, 20, 28, 40, 44,44,22,56)
(Step 1: MAF with 60, 02 2, 5);
A/(3) 3 {12, 18, 42, 48),
(Step
60, 02 m² (92.1 92.1) (24, 36)),
A/3) (24,
(Step 2: SNF with n 60, cs 2, my
(g3.1. (24, 36))
Combining the above four null frequency sets satisfies 6 finite-time convergence.
confirming that Example g sarisfies
(1=0 = 0)
OOO0
(= 1)
()
(1
0.4
0.3
0.2
0.1
0.05
Figure 19: Mixing matrices of null-cascade graph with (n, k) (60,3). Each graph consists of n 60 nodes, depicted as black dots arranged in a circle and interconnected by lines. The colors of these lines indicate the mixing weights between nodes in W
W
Product of all mixing matrices)
Amplitude
0.8
04
21
24 23
29
50
Frequency indices (0
Figure 20: Frequency characteristics (amplitude) of each sequence.
37

---

Example (Null-cascade graph). Given (n, k) (60, 2), where can be factorized as 60 5 x 3 x 2. Since k
not a composite number that can be factorized using only integers less than or equal to k + 3. The null-cascade graph consists of T = 5 circulant matrices, as
w cire(s 3: 0, 0,...,0
19 zeros
19
W ciro(s
seroos
Meros
W = cirol
2,0,,
zcros
( cire( -2000 (00-0(22-((24))) (24/000))))
.,...
cosl 2 (24/02224))))) 0),
2-2coss (24/60))
2 (24/026
55
( = circ(
22 (21/00)
1
2 2-2onn (2t (2442662(24/60) (24/60)) )
2 2 2 (24/60) 60) 2 nos (2-(224)0))
57 peros
where null responses for each & E 1,,,,233,4 are obtained at the following frequency indices
A (1,2,4,5, 8,8, 10, 11, 13, 16, 17, , 19, 22, 22, 23, 25, 26, 28, 21, 35, 40, 41, 46, 46, 49,59,,00 50,52, 53,55,55, 55,56, 56, 58, 59}, (Step 1: MAF with 60, = mg 20),
A(O) З (3,9, 15, 21, 33,39,45,51,51 (Step 1: MAF with 60, 1,m1 10);
W( 9 (6, 18, 30, 42, 54),
(Step MAF with
N(3) 9 (12, 18, 42, 48),
2: SNP with 60 mg 2, (18.1: 95,1 (24, 36)),
A/(4) (24, 36),
(Step 2: SNF with
60, c4 2, ma
(9,11.97,)) = (24, 36)).
Combining the above five null frequency sets satisfies 66. conftrming that Example 9 satisfies finite- time convergence.
O 0000
0= 0)
(=
(1=
=
(1= 4)
3.5
0.05
Figure 21: Mixing matrices of null-cascade graph with (n, k) (60, 2). Each graph consists of 60 nodes, depicted as black dots arranged in a circle and interconnected by lines. The colors of these lines indicate the mixing weights between nodes in W
1000
w1
Product mixing matrices
Amplitude
04
02
10
20
28 20 25
58-660
Frequency indices (0
Figure 22: Frequency characteristics (amplitude) of each sequence.
38

---

C Simplified algorithm to construct pase-(k+1) graph
This section consists of the following:
(i) Interpretation of the base-(k + graph. We summarized our interpretation of the base-(k ( + 1) graph based on the principles underlying the 1-peer exponential graph in Sec. C.I We found that: i) applying the simple base-(k + graph, which included in the base-(k graph, effectively mullifies frequencies except for those that multiples of specific number, and ii) the remaining non-zero frequencies can be eliminated by utilizing circulant matrices employing MAFs with an appropriate choice of length og and expansion order my.
(ii) Simplified algorithm to construct the base- (k + 1) graph: Based on the insights in Sec. C.1 new and simple algorithm to compute mixing matrices in the base-(k + graph is developed Sec.
C.1 Our interpretation of the base- (ke--k++11 + graph
(i-a) Brief introduction of the simple base-(k graph
First, we briefly explain the simple base-(k++ graph, which is included in the base-(k+ graph. Since the algorithm to compute mixing matrices in the simple base-(k graph is complex (see Alg. (34)), aim to provide an intuitive explanation of the simple base-(k+ graph through an illustrative example:
Example 10 (Simple base-(k: + 1) graph with (n, k) = 1)). First, let us decompose n using the power of (I: + 1). Consider the case when (n,k) (3, 1). Then,
be decomposed as n = (1 + 1) + (1 1)00 = + 20, resulting in the generation of two subgroups:
(x), {xa}
The simple base-(k 1) graph with (n, k) (3, 1) consists of T 3 mixing
S1.2' S2:29 mode
matrices (W(9) W(1), W(2)
WO
W0
X +x
3
0
X]
+xx+
X2
+ +X +X
1
X3
(1 = 0)
(1 = 1)
(I = 2)
1.0
0.8
0.6
0.4
0.2
0.1
Figure 23: Mixing matrices simple base- (k+1) 1) graph with (n, = (3, 1). Each graph consists of 3 nodes, depicted black dots arranged in circle and interconnected by lines. The colors of these lines indicate the mixing weights between nodes in W!())
39

---

Example 11 (Simple base- + 1) graph with (n, = (5,3)). First, let us decompose n using
the power of + 1). Consider the case when (n. (5,3). Then, can be decomposed
as 5 (3
1)1 + (3 1)00 4 + 40, resulting in the generation of two subgroups:
X2; X3, x
{s) }. The simple base- + 1) graph with (n, k) (5, consists of
91:11 nodes
S2:10 node (W(O)
mixing matrices
W W
(
W
W
X1
1
1
X1
X1 1xg
4
0
X2
+ +Xx
X3
7
7
X1 x2
x
X4
1
X1
0
0
0
X5
Note that this example corresponds to Fig. 2 in Sec.
5
(1 = 0)
(1 = 1)
(1 = 2)
1.0
0.6
0.4
0.2
0.1
Figure 24: Mixing matrices of simple base- (k + 1) graph with (n, k-) (5.3). 3). Each graph consists of n. = 5 nodes, depicted as black dots arranged in a circle and interconnected by lines. The colors of these lines indicate the mixing weights between nodes in W(
It is important note that, in the simple base-(k++1 graph. the of mixing matrices is not limited to circulant matrices. Thus, the commutativity of the 7 mixing matrices does not hold.
Examples with other (n,, k) configurations are illustrated in Sec. C.3 The simple base- + 1) graph, included the (ase-(k+1]) 1) graph, basically structured by three steps: (la): intra-subgroup averaging within each subgroup using the k- k-peer hypercube graph, which is implemented by W (2): inter-subgroup mixing of the models across subgroups, which implemented by ( and (Ib): intra-subgroup averaging using the k-pper hypercube graph, which is implemented by W
Although the simple base-(k 1) graph achieves finite-time convergence for any (n, k) combination, two issues remain: i) the periodic interval tends to be large, mainly because the twice repetition of intra-subgroup averaging, resulting (2 [log (n)]) and ii) commutativity among the mixing matrices does not hold.
(i-b) Our interpretation of the base- (k+ 1) graph
Next, we delve into our interpretation of base- (k+1 1) graph. The algorithm currently used to compute mixing matrices within the base-(k++1) graph, including the simple base-(k (k+ + 1) graph, complex (refer to Alg. 3 in (34) ). Our primary aim in this section to develop new algorithm in the following subsection that will calculate mixing matrices in the base-(k++1) graph. This new algorithm
will be based on the principles underlying the 1 1-peer exponential graph in Sec. 3 presenting a different formulation of base-(k- (k+11 graph. As an initial step, we explain our interpretation regarding Base-(k+1) 1) graph in detail below.
Let recall that the simple base-(k + 1) graph ensures finite-time convergence for any (n, k) configuration. The base-(k: + 1) graph is employed to average local models within each subgroup. Suppose that mation of μi subgroups, each containing #2 nodes. Assuming that local models within
be factorized
/2/22 which results in the for-
"The original paper (34] states the order of the periodic interval as Ollgg+ (n)). This representation remains correct since coefficients multiplied by the main component log (n) are general. However, we apply coefficient of 2 estimate accurately, reflecting the twice iteration of subgroup averaging.
40

---

each subgroup are averaged/identified using the simple base-(k + 1) graph, this results in 11, .i,..,, X1 2, X2,....
This is equivalent to a permutation that & jn & . Xpy us
He modes repeats pr-length sequence {x1, X2....
H2 nodes
nodes
X by u2 times, referred as repeated sequence. The arrangement appears follows: x1, X2,... Xpy X1, X2,.... Xpar.. X1, x
time
2
#2 times
For simple notation, suppose that P1-length sequence {1(0), ((1), h(us - 1)} and its
jy-times repeated sequence {N'(0) (1),. h(H112 1)} {h(0), (((O),,(1,.......... h(11 (),,(O) h(1).... h(41 -,),...,,((),,, h(1), h(w1 1)} are given. The DFT of the original sequence h(t) is given by
11-1
H
Σ ==
(o))e-2njo/u
where E (...... #i -1) in (i) is frequency index. Since the repeated sequence can be equivalently formulated using the original sequence, as h'(i) hii mod R1). Thus, the DFT of the repeated sequence is given by
(1))
Σ ==
n'(D)e 2nje0/Gurra)
hitb mod Mı)e -1)e-22jj0/(mp)
h(t22e +
11 = P2=0
#1
Ag h(W22) 2njita//
===0
where Ti takes #2 when i is a multiple of #1/12; otherwise, it is zero. Consequently, we obtain
H( (1) (if mod μ22 0)
H' H')))
(14)
(otherwise)
where i (O..... P1 1) in H'(1) denotes the frequency index. This indicates that many frequency components are nullified if = H1-uhthttth sequence is composed of μa times repeats of Mi -I-lngthh sequence. This is applicable the local models through the simple base-(k: + 1) graph. Since this also repeated sequence, we can
denoted by (x1, x2,...,.,, .p.............................. X1, x2..,
#2 times
recognize the effect of the simple base-(k 1) graph as null forming except the frequency indices satisfying (i mod #22 0).
Noticing that the remaining frequencies to be nullified are multiples μ22 MAFs with a suitable choice of ce-length and mę-order expansion prove beneficial. Recall that the null frequency indices with MAFs with c, ey-legtth and modorr expansion are theoretically analyzed in Sec. [3] and Appendix specifically in (3). Moreover, this approach is efficiently utilized in null-cascade graph in Sec. 4 with dynamic/suitable choice of {ce, my) ]. resulting in the forming of nulls at non-zero frequencies. This strategy is also applicable to nullify the remaining frequencies. In the next subsection, building on the ideas discussed so far, new and simplified algorithm to construct mixing matrices in the base-(k k+ 1) graph will be developed.
C.2 Simplified algorithm to construct the base-(k 1) graph
The original algorithm to construct the base-(k 1) graph is outlined in Alg. [34] however, somewhat complex. Assuming that the algorithm to construct the simple (use-(k+1] graph is given
41

---

Algorithm 5 New algorithm to construct base-(k+ 1) graph
1: Given (n,k) and 0
2: Factorization of n as n IT (v; + 1), where v1 S .... S. S k S Uk+1 S. MA where
V N.
3: (Step Applying simple base-(k:++) graph be repeated sequence (which is equivalent form nulls as in (14)
4: for >y.... do
5: > Generate mixing matrices Z E R
(*Xn) to be repeated sequence
6:
{Z(0) , (T( SinglehssCrpplleeeeeeeseseeeeddd + 1, n,, k)
7:
for j ... Tab
do
8:
W = 20)
9:
f- 1" mixing matrix index increment
10: end for
11: end for
12: Remaining frequency to be eliminated (multiples of from (4)
13: b b= IIi (v: + 1* base of frequencies to be nullified */
14: b (Step 2) Null forming using expanded MAFs for R...... do
16:
(ce, me) = (Mi, (m-+1]6)
()) [1/(ce +)
(j = 0,...... (otherwise)
17:
10
18:
W circ((h
Tiee (0). Tmm (n- 1)])
19:
{ {=t+1
/* mixing matrix index increment */
20: b= b(v: + 1)
1 base of frequencies to eliminated //
21: end for
22: function (Z (za-11) 113 Singl/BBaCGrpplapppaeesssoooor + 1,
23: > Generate simple base-(k + graph Y E +1) to make consensus among
1)) nodes.
24: (Y(0)) ( ) SimpleBeseGraphh(e + 1,k)
Alg. 2 in 25: Generate mixing matrices ((r) ( (xxx))To to be repeated sequence
26: for i 0, ...... Tab - do
n1(x,+1--1
27:
Z Σ
(r 0 0,1, 0....., 17) c JO... 0........,, 0..... 1)
n/(-5t1)--11
n/(cst1)-g-1
end for
(Alg. 2 in 34)). new and simplified algorithm for constructing the base-(k+1) graph is presented, leveraging the insights discussed in Sec. C.I
Our new algorithm for computing the base-(k++1] graphis detailed Alg. 5 In line 1, n factorized into k(s 1) components as = -I= (c: + 1), where c; E IN are ordered as co ... < Cy-1 < < Cu-1- This factorization is critical to determine the integration strategy of the simple base-(k 1)) graph and circulant matrices using MAFs. For c; > k for i K 1}. the simple base-(k- (I- 1) graph is applied (step 1). Conversely, for G; S le for E (0.... (O..... 1}. circulant matrices using MAFs are employed (step 2). Lines 3 to 11 compute mixing matrices based on the simple base-(k + graph Through Tab mixing matrices, repeated sequence of local models
5- c
X1 ..,.(e..,((((11) is generated. The application of
time
(c,+1) times
the simple base- graph is repeated for &; > k for ( 1). From (14), this cascade of the simple pase-(kk+ + 1) graph remains non-nullified frequency components i, which are multiples of 6 -I:- (q: + 1) within i e n1.. For nullifying the remaining frequencies in step 2,
42

---

circulant matrices employing MAFs with cy-length and expansion order m, are generated in lines 14 21. We used the techniques in the null-caseade graph in Alg.
Although our Alg. diverges significantly from the original algorithm (Alg. in 34 )) they generate equivalent mixing matrices. These intriguing outcomes stem from theoretical analysis of the principles underlying the 1-peer exponential graph.
C.3 Example illustrations
C.3.1 Simple base-(k + 1) graph
Example 12 (Simple base- (k: 1) graph). First, let decompose using the power of (k +
Consider the case when (n, k) = (5. 1). Then, n can be decomposed as n == 2-(1++) + +1++1), resulting in the generation of three subgroups:
(x,, X4)
{xs} }. The simple base-
S nodes S2:21 So:20
(Ic 1) graph with (n, k) (5, consists of r 5 mixing matrices (W())
W
(
W
W
1
0
+
+
0
0
0
0
7
x
+x, +Xx
0
12
1000
0
0
0
7
0
0
x x2 Xi +oc +:05
110
0
0
0
0
0
0
0
WO
W
1
X1
X2
2
0
X3
0
0
0
0
X4
X5
(==0 0)
(1
(1 =
(1= 3)
(1 4)
1.0
Figure 25: Mixing matrices of simple base-(k: 1) graph with (n, k) (5, 1). Each graph consists of n = 5 nodes, depicted as black dots arranged in a circle and interconnected by lines. The colors of these lines indicate the mixing weights between nodes in W!
43

---

Example 13 (Simple base-(k+11 graph). First. let us decompose using the power of (k + 1).
Consider the case when (n, k) (5. 2). Then, n can decomposed as
(2+1)' +2 (2+ 1)
resulting in the generation of two subgroups: X2,,, X3.
X4. X5
}. The simple base- (k: +1)
$1:31 modes
22:2-30 nodes
graph with (n, k) = (5, 2) consists of T 3 mixing matrices
W (0)
w
W
W
W7
X
X1 +
0
0
X2
X1 x1+x2
X3
X2
X4
X5
(I = 0)
(I= 1)
-1= 2)
1.0
0.8
0.6
0.4
0,2
Figure 26: Mixing matrices of simple base- (k: 1) graph with (n, k.) (5, 2). Each graph consists of n = 5 nodes, depicted as black dots arranged in a circle and interconnected by lines. The colors of these lines indicate the mixing weights between nodes in W
44

---

C.3.2 Base-(k+1) graph
Following Alg. several illustrations of the base-(k++) graph are shown.
Example 14 (Base-(k+-1 graph). First, the factorization of n. is given as: n = 15 = (2 (2+1) (4 (4+1) 1);
namely, V1 1/2 4. Since k includes a factorization number 22 4 such that vi >
Following Alg. [
the simple base- + 1) graph with (n, k) = (5, 2) is computed. From Example 13
(Y 2E are prepared.
de Holl
0
0
0
0
000
0
Y
0
2002000000
Y
0
0
D
The base-(k (k: + 1) graph consists of T = circulant matrices as
W
Σ
(
00 0, O,.... O. 1.
s0 0.......
0. 1, -.ررس
9=0
2-9
2-g
W Σ
0,
@ o,.... 0, 1, ).ا:):
7=0
2-9 &
W Σ
0. 1. (.س-ي s 0....... (3)) 30 0. 0. 0 0T)
2-9
2-9
w = ciro( 1
3. 3: 3
12 zeros
where null responses for each E 2, are obtained at following frequency indices
Un0 3 21, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14), t=0
(Null frequency indices multiples excluding multiples
characterizing frequency response the simple base-(R- + graph.
3( 3 103, (MAF with 15, m,
Combining the above null frequency sets satisfies 66) confirming that this satisfies finite-time conver- gence.
()
(1
2)
(1=
0.8
0.6
0.1
Figure 27: Mixing matrices of the simple base-(k + 1) graph with (n, k) (15, 2). Each graph consists
nodes, depicted as black dots arranged in a circle and interconnected by lines. The colors of these lines indicate the mixing weights between nodes ((
45

---

Example 15 (Base-(k +)) graph). First, the factorization of n. is given as: n 30 = (1+1) (2 - 1)- (4 + 1); namely, Vi 1, 1/2 V3 = Since
includes factorization number V/3 S the simple base- (k 1) graph with (n. k)) (5,2) 2) is computed.
such that v > k. Following Alg.
From Example
13 (Y (..)0.1.2 are prepared.
0
Collccl
0
0
10000
Y
0
Y
0
0000000
Y
D
The base-(k: 1) graph consists of 4 circulant matrices as
W
Σ6
Y
0.
1. O.
10....,.. 0, 1. 0......))
9=0
3-1
5
W Σ
(1)
@
x Ouنnn 0, 1, ).w-)
0=0
5-4
W Σ
Y (2) 2 0,
O. 1.
10....,0, 0, 1, 1,0, 0y....0)) 0)
5=0
3-9
3 = cirol 1
3,
0, 3
0,
3
1
O.
24 aeros
W circ( 2. 0.......
28
where null responses for each E E {0, 2,3,,,33, are obtained at following frequeccy indices
U (1,2, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24, 26, 27, 28, 29),
(Vull (Vill frequency indices are multiples of I, excluding multiples of 5, from 14
characterizing the frequency response of the simple base- + 1) graph,
A3 (5,10,20 20, 25), A144) {15),
(MAF with n 30, cq 2, ma 2).
(MAF with 30, ca = 1, 1)- Combining the above null frequency sets satisfies gence.
confirming that this satisfies finite-time conver-
()
(=
()
(1=
0.8
0.4
0.2
0.1
Figure 28: Mixing matrices of simple base-(k+11 graph with (n, k) (30, 2). Each graph consists of n 30 nodes, depicted as black dots arranged in circle and interconnected by lines. The colors of these lines indicate the mixing weights between nodes in ((
46

---

D A consideration regarding the benefit of commutativity
brief consideration commutativity (Definition 4 follows. Reducing the discrepancy between the global model x and local models x!"), specifically, minimizing Σi= ||x(") - x is critical
for accelerating decentralized learning. This term appears explicitly in the convergence analysis of
DSGD (implicitly included in Theorem D]. Enforcing commutativity of the graph mixing matrices can reduce this discrepancy.
To illustrate this, we reformulate the update rules of DSGD recursively, as follows:
x (r+1)) = x() -VF((")
= -x (()). W ,
W +...+
= x II ( Σ (V)
II w(r))
=1
82
Next, investigate the property of II., (+)) for finite-time convergent graph with periodic interval 7.
[Case I: Commutativity of mixing matrices is satísfied] (e.g.. k-peer exponential graph and null-cascade graph)
When commutativity of mixing matrices is satisfied, (( w((()) W(d(r-1) - for any permutation p. The product
II. =g= W(+z) can be categorized into two cases:
(Case la) When 8 5 r
(+2) = 1
(Case 1b) When 2 r 2, IT 22=8; ( I
These results indicate that no discrepancy among nodes occur for terms with index 81 [0, T + (in Case Ia). In contrast, discrepancy among nodes can occur for terms with index 81
r] (in Case lb), which leads degradation the convergence rate.
[Case 2: Commutativity of mixing matrices is NOT satisfied] (e.g., base-(k++ (k++) graph)
When we denote mod (r, r) S, the product IT
(+2) can be categorized into two cases:
(Case 2a) When $1 < r -
1. II 82=8 (x2) 1 1
(Case 2b) When 2 - + I. TT (( 1
These results indicate that no discrepancy among nodes occur for terms with index s1 [0, r - T - + (in case 2a). contrast, discrepancy among n nodes can occur for terms with index - 2,
r) (in case 2b), which leads to degradation in the convergence rate.
Comparing these two cases, the components that contribute to discrepancies among the n nodes tend to be more significant when mod (r, r) is non-zero. Although this difference may be small and therefore difficult to observe empirically, we have theoretically demonstrated the advantage of using commutative mixing matrices.
47

---

E
Convergence rate comparison using various graphs
As theoretical contribution, the convergence rates of DSGD over various graphs are summarized in These rates are derived by substituting the expected spectral gap p and periodic interval specific each graph into the convergence rate of DSGD Theorem |
Table 3
Table 3: Comparison of convergence rates of DSGD over various graphs.
Graphs
Convergence
degree of
Ct²²
R2*)
Ring 24
Lif
Vu
ne
Sn
Torus 24
I.fo
Vn C
ne?
n²
(lory()) Angggn)
long(n)
Exp. 41
-.fo
Vi 6
ne2
6//2
o²
(1org aay Angg(ni
loga(n)
A power of
1-per exp.
ne
e//2
n.a.
Vi N
o²
(oggin))
l08g(n)
1-peer hypercube 31
nc?
63/2
-.fo
A power of
(Tho
Base-(k 1)
651
6/12
1.0
F N
Vu
0²
Clogsrs (1n)
Plaaa logs i1()
10ge+1
k-peer exp.
ne? +
Pegeop 2312
Pepeep
-if
e N
Vu
Null-cascade
eV22
Tuat
2.fu 43
vk(2 2)
Vn
*I: Thor X Dimn logg++ (24)]
sin(rriik Lnsy ( /n) shown Theorem
Pipeop 16.............................. (k+11) (P0]
sin(s1/m)
2
"3: R. E -1 / (2 1k/2/ /2/.). where is factorized n II, (vy 1), where S S M x K MN S... M...
My is number, factors being less than equal
48

---

Relationships between expected consensus rate, periodic interval and (n,, k) configurations
In Sec. F.1. the relationships between the expected consensus rate the periodic interval т, and the number of nodes n are illustrated for various values of k. These illustrations reveal that the periodic interval required for achieving finite-time convergence (p = in the null-cascade graph tends increase when the factorization Nonetheless, experimental results presented in Sec. inddccate that performance is not compromised even under such scenarios. The primal reason discussed Sec. []] with additional considerations provided in Sec. F2
includes large prime numbers, as discussed in Sec. [4]
F.1 Illustrations of expected consensus rate periodic interval and (n, k) configurations
The expected consensus rate p. the periodic interval and (n, k) configurations are numerically investigated across several graphs. This examination covers broad range of n and & = {2, 3, 4). as depicted in Fig. 29 For the k-peer exponential graph, the expected consensus rate becomes one (indicating finite-time convergence) for specific n (a power of l: + 1). As n deviates from this condition, the expected consensus rate increases, as observed with configurations like (n, k) (17, 2) discussed in Sec. 5 The periodic interval for the k-peer exponential graph typically remains small, given by = [log [n)]. On the other hand, the consensus rate of both base- +1 1) graph and null-cascade graph consistently reaches one, indicating they achieve finite-time convergence for any n. However, the required periodic intervals T to achieve finite-time convergence differ between these two graphs. When the factorization of includes large prime numbers, 7 in the null-cascade graph tends to increase; not, in the null-cascade graph is generally equal to or less than that in the base- (k + 1) graph.
F.2 Additional discussion
As shown Fig. 29 the periodic interval for the null-cascade graph increases when the factorization of includes large prime numbers. Nonetheless, the experimental results presented in Sec. 5 demonstrated that the performance is not degraded even under such scenarios. The prime reason for this is discussed in the last paragraph of Sec. This suggests that balanced mixing among n nodes in the null-cascade graph leads to better experimental results.
Additionally, there is the issue of potential redundant counting of in the null-cascade graph. This arises because in the null-caseade graph is counted as the number of mixing matrices required to achieve finite-time convergence. However, a smaller т could potentially be set by accepting a modest expected consensus rate. Furthermore, repeating graph that achieves finite-time convergence twice results in doubled periodic interval, yet the expected consensus rate remains unchanged. Even though the periodic interval can doubled, this does not necessarily slow the convergence rate. Such observations indicate that rigorous determination of 7 in Assumption 4annot yet be definitively established, pointing to a direction for future research.
49

---

(C2) (kse-(k+1)
(P1) k k-pee
(P2) Null-cascade
(a) = 2
Exp. consensus rate 3
0.9
Periodic interval (r)
0.8
0.7
0.6
0.5
04
0.3
0.2
0.1
25
35
40
50
60
10
20
30
35
45
50
60
Number of nodes (n)
Number of nodes (n)
(b) =
0.9
Periodic interval (7)
Exp. consensus rate
0.8
0.7
0.5
0.4
0.2
0.1
35
50
20
Number of nodes (n)
Number of nodes (n)
(c) k = 4
10
0.9
Periodic interval (5)
Exp consensus rate
0.8
0.7
0.5
AMM
0.4
0.3
0.2
0.1
Number of nodes (n)
Number of nodes (n)
Figure 29: Relationships between expected consensus rate periodic interval т, and n with k (2,3, 4).
50

---

G Additional experiments
Data distributions of CIFAR-10 and CIFAR-100. As described in Sec. 5 the training dataset
of CIFAR-I0 and CIFAR-100 were divided into local datasets 23 (i E {I..... nn] follow
Dirichlet distribution with concentration hyperparameter a, using the source code used in [38 We set 0.1, representing scenario with significant data heterogeneity. The distributions of the
dataset for n 115, 17, 30} are illustrated in Figs. 30 and
(a) n=15
(b) n=17
(c)
Acceinces D4e
Figure 30: distributions CIFAR- training dataset when (a) 15, (b) and
(a) n=15
(b) n=17
n=30
bade
Sodo mode 10
Figure 31: Data distributions of CIFAR-100 training dataset when (a) n 15, (b)
17, and (c) 30.
Update rules based on DSGD, Our DSGD-based update rules that allow multiple local updates are summarized in Alg. 6 We set the number of inner multiple local updates to T = 100 for CIFAR-10 10 and 7 10 for C1FAR-100. The minibatch size to compute stochastic gradient was 64. noted in the main paper, we computed the test accuracy of the global parameter x Σ X; once every dozen communication rounds, for the evaluation metric.
Algorithm 6 DSGD used in the experiments in Sec.
Initialization x, _...., X,, 17, R, E [n])
2: Set mixing matrices (W(()).. (r-11))
3: for (Outer communication round) = 0, R - do
x
4: a.
5: for (Inner local updates) t = 0 O....,T do
6: x. (r,A+1) (r.t) 1) fz (r.)) c(())
|# minibatch sampling
<, (n.))) D, #1
7:
end for
(r+3)
(r.T)
8:
x
x
9:
Partial averaging
(++1) - w (mod(r;7)) (r+
10:
11: end for
http:///ggttab...oo///t////////s html
51

---

Hyperparameter tuning. For Alg. 6 the learning rate was initially pre-tuned for each dataset- model combination. To maintain consistency across various graphs and ensure fair comparison, we used a common y) across all tested graphs. For this aim, we investigated 7), which maximizes the test accuracy for each dataset-model combination, based on the results from single-node model training. Details of the associated hyperparameter settings are provided in Table 4 Through this hyperparameter tuning process, a learning rate of 1 = 0.01, which gradually reduces to 1j = 0.001 through cosine annealing, was chosen for all combinations of datasets (CIFAR-I0/ / CIFAR-100) and the model (ResNet-18).
Table 4: Hyperparameter settings for CIFAR-10/CIFAR-100 with ResNet-18
Data augmentation
RandomCrop, RandomHorizonallFiip. RandomErasing of Py PyTorch
Learning rate 7)
Grid search over 0.01, 0.001)
Momentum
0.9
Weight decay
0.005
Batch size
64
Learning rate scheduler
Cosine annealing
Learning warmup
10 epochs (17 = 5c 50)
Graphs used in experiments. Several graphs used in the experiments are summarized as follows:
(CI) Ring graph. This is static graph (r 1) and each node connects with neighboring two nodes. The mixing matrix is given by
W (0) cire( 1 3 0,.....0.33. 2)
where this holds = independently of n. Thus, we used this as comparison graph for the configurations in the main paper configurations (n, k) = (15, 2). (17,2), (30, 2).
(CI') Extended ring graph. This is static graph graphs that support k 2 2 connections, we extended the ring graph by connecting each node not only its two immediate neighbors (i.e., k = 2) but also additional adjacent nodes. For instance, when k = 3, the mixing matrix is given by
1). To enable fair comparison with other
W circ 3 0, .,. 0)
and when = 4, the mixing matrix is given by
W (0) cire(
5
5
0
0, 5.
y- 5 zeros
(C2) Base-(k +) graph. This is dynamic graph (r 2 2) and related diseussion is given in We computed the mixing matrix in the base- +1 graph using the source code on the
Sec. C3
website
(C3) Random graph. This is a static graph (r = 1), and is modeled as in the Erdos Ménosi random graph [5], adjusted to ensure & for each configuration.
(C4) (k++1 1--arttt random match graph. This is a dynamic graph that is a generalization of the bipartite random match graph used as comparison graph in [3]. to accommodate k-peer communication. In the bipartite random match graph, two randomly selected nodes are connected with undirected edges, with the assumption that is even. Unlike other graphs where connections follow a periodic pattern, the connections between two nodes vary over time without a fixed period, thus this graph does not maintain a consistent periodic interval r. To generate the bipartite random match pr) graph to allow any (n, k) configurations, i) the index (1, 2,, n)) to (p²*)(),, (2) ()) (n)) was randomly permuted, where ((r) (.) denotes the permutation function at communication round ii) the forming subgroups consisted as many (k: + 1) nodes as possible, and iii) partial average
52

---

within each subgroup after exchanging local parameters was performed. To the best of our knowledge, the expected consensus rate of the (k + papattte random match graph, has been investigated.
(P1) k-peer exponential graph. This is a dynamic graph, whose details are explained in Sec. 3
and
Appendix A
(P2) Nallecascade graph.
This a dynamic graph, whose details are explained Sec. and
Appendix B
Computing resource. We used computing servers employing 8 GPUs (NVIDIA RTX 6000 Ada (48 GB)) and 2 CPUs (AMD EPYC 9354, 3.25 GHz, 32-Core Processor).
Additional experimental results. Firstly, due to the space limitation, we picked several configura-
tions in Fig. in Sec. its complete version illustrated in Fig. 32
The corresponding highest test
accuracy is summarized in Table 2
(C1) Ring
(C2) Base-(k+1)
(C3) Random
(C4) (k+1)patttt rand.
k-peer
(P2) Null-cescade
(a1)
CIFAR-10. 10, (1,k)=(15,2)
(b1) CIFAR-10, (17,)=
(c1) CIFAR-10, (n,k)=(30,2)
0.9
0.9
0.85
0.875
Test accuracy
Test accuracy
0.85
Test accuracy
0.8
0.6
0.5
0.4
0.5
0.4
0.3
60
90
120
30
120
150
50
120
150
Iteration [k]
Iteration [k]
lteration [k]
(a2) CIFAR-100, (n,k)=(15,2)
(b2) CIFAR-100, (n,k)=(17,2)
(c2) CIFAR-100, (n,k)=(30,2)
0.72
0.72
0.73
Test accuracy
0.71
Test accuracy
0.71
Test accuracy
0.72
0.71
0.65
0.65
0.6
0.6
0.6
0.55
0.55
0.5
0.5
0.5
Iteration [k]
Iteration [k]
Iteration [k]
Figure 32:
Convergence curves using test accuracy of global parameters for three (n, conffiiguustiions with This figure is the complete version of Fig. 4 in Sec.
two datasets
Next, additional (n, -)-coniigurationns were tested in this appendix section, particularly using k > 3. We conducted five additional (n, confiiuguraai::: namely (dl) (n, k) (15, 3), (el)
(n, k) = (17, 3). (fl) (n, k) = (30, 3), (gl) (n, k) (30, 4), (h1) (n, k) = (31, 4) using CIFAR-10 10 classification task. The corresponding results are summarized in Table Table5aam 5 Fig. 33 Even among the additional (n, configuuurti with & 2 3, the proposed (P2) null-cascade graph consistently illustrated strong performance, including cases where n large prime number.
discussed in the main paper, this can be attributed to the maximized expected spectral gap under uniform degree, periodic interval
although for some (n, k) -onffiguuurtss we observed that the mixing matrices consisting of the base- [[:+] graph and the null-cascade graph are identical. As explained in Appendix this arises from the fact that the base-(k- (k+ 1) graph for certain (n, k) configurations be constructed following the design principle of the null-cascade
increased. For (n,, = (30, 4),
53

---

graph. Therefore, it is natural that the performance of the base-(k+1) graph and the cascade graph nearly identical in this case. To further investigate this, we conducted additional experiments with (n, k) (31, 4), where is large prime number. In this configuration, we observed that the null-cascade graph outperforms the base- (k: 1) graph. These additional experimental results highlight the effectiveness of the null-cascade graph across various (n, confiiuurtts
Table Comparison highest test accuracy using global parameters CIFAR-10 classification task for five additional (x, configgauatiss
(e. -ccoofigurration
(di) (n, (15,
(el) (m. (17.3
(1)) (R. (30),
(30, 41
(h1) (R. k) [31
Tested graptis
Iest acc.
lest asc.
lest acc.
tcal DUC.
Icel avo.
(CI") Extended ragg
0.8876
0.8756
0.8605
0.8544
0.8958
(2) Base-(k (1)
0.8467
0.8701
0.8640
0.8746
0.8974
(C3) Random
0,7580
0.8749
0.8747
0,8257
0.7576
(C4) (A 1)-partite mand match
0.8574
0.8780
0.8780
0.8788
0.8000
(PI) exponential
0.8532
0.8789
0.8713
0,8780
0.9031
(P2) Nall-cascade
0.8732
0.88177
0.8794
3
0.8746
0.9019
(C1') Extended Ring
(C2) Base-(k+1)
(C3) Random
(C4) (k+1)-partite rand.
(P1) k-peer exp.
(P2) Null-cascade
(d1)
CIFAR-10, (n,k)=(15,3)
(e1)
CIFAR-10, (n,k)=(17,3)
(f1) CIFAR-10, (n,k)=(30,3)
0.9
0.9
0.8
0.8
0.8
Test accuracy
0.7
Test accuracy
0.7
Test accuracy
0.7
0.6
0.6
0.5
0.5
0.4
0.4
0.3
0.3
0.2
0.2
30
60
120
150
30
00
120
150
Iteration [k]
Iteration [k]
Iteration [k]
(g1) CIFAR-10, (n,k)=(30,4)
(h1) CIFAR-10, (n,k)=(31,4)
0.9
0.9
0.8
Test accuracy
0.7
Test accuracy
0.7
0.6
0.6
0.5
0.4
0.4
0.3
30
50
90
120
150
Iteration [k]
Iteration [k]
Figure 33:
Convergence curves using test accuracy of global parameters for five additional (n, k)-
configurations.
54

---

Further additional tests using large n.
In the rebuttal phase, we performed additional experiments using large n., For (n, k.) (69, 2), data
distribution of CIFAR-10 with a = 0.1 is illustrated as follow:
bird
15:00
trog
Number of data
1250
porse
750
500
250
123456789 01155628800222333302022222222200
2039229 22215581000022222222222322222222 E8 0O3 385638 0075563888888880 9888666688
Node Index (1-n)
Figure 34: Data distributions of CIFAR-10 training dataset when v 69.
The highest test accuracy and convergence curves are illustrated as follows:
Table Comparison highest test accuracy using global parameters CIFAR-10 classification task for (n, k) = (69, 2).
(n, configguratii
(n, k) (69, 2)
Tested graphs
test
(CI') Extended ring
0.8805
(C2) Base-(k+11)
0.9213
(C3) Random
0.6267
(C4) (k+a)-- rand. match
0.9229
(P1) k-peer exponential
0.9225
(P2) Null-cascade
0.9216
(C1') Extended Ring
(C2) Base-(k+1)
(C3) Random
(C4) (k+1)partite rand.
(P1) k-peer exp.
(P2) Null-cascade
CIFAR-10, (n,k)=(69,2)
0.92
Test accuracy
0.88
0.7
0.6
0.5
0
600
1200
1800
2400
3000
Communication round
Figure 35: Convergence curves using test accuracy of global parameter for (n, = (69, 2).
55

---

H
Related works
(i) Centralized learning. In distributed model parameter training, centralized learning such as Parallel SGD (PSGD), All-Reduce, and Federated Learning (FL) [23 10 often serve as the initial approach. FL. particular, has seen significant efficiency gains due client sampling by the center server and multiple local updates performed in each client. However, in scenarios involving extensive computing resources with many nodes/clients, center server becomes a bottleneck due to the need to aggregate local model parameters from clients and distribute the global parameters back to them. To address this issue, research into decentralized learning approaches has been pursued, e.g., [T6 17].
(iii) Decentralized learning algorithms. The most widely used decentralized learning algorithm DSGD [20] 26]. and its extensions [16] I 2 [7]. Many researchers have integrated DSGD and well-known acceleration techniques, such as momentum 6 18 45 46
communication compression
techniques
39.
As illustrated in Theorem [ the convergence rate of DSGD depends on data heterogeneity (As- sumption B). To mitigate this issue, many improved algorithms have been studied, such as Gradient
Tracking (GT) and its extensions 3
25 30
12 33 48 D 37), decentralized SCAFFOLD 19
primal-dual methods [47 27
28
etc.
In this paper, we primarily used DSGD as the fundamental decentralized learning algorithm. However, proposed graphs applicable any decentralized learning algorithms.
(iii) Other graphs for decentralized learning. As illustrated in theoretical analysis for decentralized 40
33), network topology (graph) affects the convergence rate of many decentralized learning algorithms. Since the total communication costs are increased as
learning algorithms [3 12 15
22
49
constructing graphs to increase/maximize the (expected) consensus rate while maintaining a small maximum degree essential for communication-efficennn decentralized learning.
the maximum degree i increases [32
43
Several studies [32 4 40 have aimed minimize communication costs by constraining the maximum degree of an underlying graph for communication-efficcce decentralized learning. For instance, the ring graph, with its maximum degree of only 2, simple yet communication-effccient However, its consensus rate, O(L/n²), as detailed in (24), suggests it performs poorly with large n. This observation aligns with the experimental findings presented in Sec. 5 When a larger i available, the (static) exponential graph [I] may be good option. Its consensus rate is discussed in Sec. 2.2; although k is dependent on n, limiting the flexibility of (n, k) combinations. In the recent study by [4). the BTPP utilizes two spanning trees (static graphs) as communication graphs. This study analytically demonstrates finite-time convergence through multiple repeats of communication. However, it is important to note that not all combinations of (n, k) are feasible with this method.
Nowadays, employing dynamic graphs for communication-cfiee
decentralized learning is a hot
topic. We omit the discussion of works introduced in the main paper (c.g.. [3] 43 32 35)).
56

---

I Limitations and future work
First, the k-peer exponential graph achieves finite-time convergence for limited n (a power of k++1). Despite this being significant constraint, we calculated the expected consensus rate for the k-peer exponential graph for any (n,k) configuration, as detailed in Sec. and illustrated in Appendix F Figure |9 in Appendix F shows that the expected consensus rate mcrrassss when deviates from conditions where ni is a power of k+11 Consequently, employing the k-peer exponential graph may be particularly advantageous for values of n that are a power of k-11
Second, it is necessary have k 2 in the null-cascade graph, discussed in Sec. This requirement arises from setting pairwise nulls in a conjugate relationship, which results in the polynomial equation in (9). ensuring that SNFs are real numbers. an era characterized by substantial computational resources spread across multi-location data centers, the availability of a large number of nodes n and a sufficiently large maximum degree & feasible. Our null-cascade graph designed to be well-suited for this future scenario.
Third, the periodic interval r required for achieving finite-time convergence in the null-cascade graph is not always small, as discussed in Sec. 4 Including large prime numbers i4 in the factorization of increases in the periodic interval needed for finite-time convergence. Nevertheless, its impact would not be significant for the following reasons: i) uniform degree: the null-cascade graph consists of circulant matrices, resulting in a uniform degree such that every node has the same number of connections. Although the balanced mixing due to this is empirically known to influence outcomes, has not yet been considered in the advanced convergence analysis (e.g.. [33;; addressing this remains work for the future. The additional reason, ii) the possibility of redundant counting of т, can be found in Appendix F Moreover, experimental results in Sec. and Appendix demonsttatee that the null-cascade graph remains effective even when large prime numbers 1/ are included in the factorization of n.
Fourth, we report convergence curves with respect to communication rounds rather than run-time. This choice reflects compute constraints- eight GPUs single server without NVL.ink-requirin us to simulate multiple nodes per GPU (e.g., for n=30, 3 or 4 nodes/GPU). Under this setup, accurately and fairly assessing communication overheads is difficult, and these costs grow especially large as the number of neighbors k increases.
Another promising direction for future work involves leveraging non-zer non-zero spatial frequency compo- nents for personalized model training. Although this study focuses on training the global parameter (DC component), non-zero frequency components also contain valuable information that could significantly enhance model personalization, thus presenting valuable avenue for future exploration.
J Impact statement
We present dynamic graphs for communication-efficiii decentralized learning, which can be applied for training large-scale models (c.g.. Large Language Models: LLMs) across extensive distributed computing resourees, such as data centers. A potential risk of this technology is that it could enable broader range of organizations to train large-scale models, which were previously restricted to organizations with access to substantial computing resources.
57


Reviews:
[{"review_id": "QK00xKe1cp", "reviewer": "Reviewer_3NBf", "summary": "This paper tackles the problem of communication efficiency in decentralized learning by revisiting and extending the concept of the 1-peer exponential graph. The authors introduce two dynamic graph constructions, i.e., the k-peer exponential graph and the null-cascade graph. The core contribution centers on the theoretical analysis of eigenvalues of the mixing matrix. Empirical evaluations on consensus error and decentralized DNN training support the effectiveness of these new graphs, particularly the null-cascade graph.", "questions": "Apart from the comments in the weakness section, I have the following questions:\n1. In the simulation, could the authors explain why choosing $k = 2$? Is it purely an arbitrary choice of any benefits from it?\n2. Regarding the applications, could the authors provide some examples where the network topology in the decentralized learning is by user's design?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. A clear and rigorous theoretical advancement is offered in this paper. I learned the DSP techniques from this paper to analyze eigenvalues, which also provides design intuition and a principled approach to constructing efficient dynamic graphs. Proofs for spectral gap and commutativity are rigorous. \n2. Both the k-peer exponential graph and the null-cascade graph represent novel additions to the literature on decentralized graph topologies.\n\nWeaknesses:\n1. The empirical evaluations are conducted on relatively small networks (up to $n=30$ nodes). \n2. The motivation and benefits of extending from 1-peer exponential graph to k-peer graph are limited. I would expect more discussions about how this extension could bring benefits to both theoretical and numerical improvements of communication efficiency. \n3. Following the previous point, k-peer exponential graph leads to more communication costs between agents. Thus, only showing the results based on communication rounds or iterations are inadequate or unconvincing (to claim efficiency).", "was_revised": true, "final_justification": "The authors have addressed all my concerns about simulations and the motivation. The position of this work is clear to me now. I believe this work makes a meaningful contribution to the field of decentralized learning with efficient dynamic graph constructions. Therefore, I would raise my score to 5 and recommend the acceptance of this paper.", "rebuttal": "First of all, we sincerely appreciate your insightful comments. We will carefully incorporate your feedback to improve the quality of this paper.  \n\n__[W1] Empirical evaluations on relatively small networks $(n \\leq 30)$.__\n\nTo address your concern, __we additionally conducted evaluations using a relatively large network size (e.g., $n = 75$).__ The evaluation setting follows the same CIFAR-10 classification task with heterogeneous data allocation ($\\alpha = 0.1$) as in Section 5.2 (Test 2).\n\n__[CIFAR-10 classification ($\\alpha=0.1$) with $(n, k) = (75, 2)$]__\n\n|Communication round |r=5|r=100|r=200|r=300|r=400|r=500|r=600|r=700|r=800|\n|---------------- | --- | --- | --- | --- | --- | --- | --- | --- | --- |\n|(C1a) Ring|__0.1953__|0.4882|0.5173|0.5496|0.5802|0.616|0.6442|0.6735|0.7038|0.7252|\n|(C2) Base-(k+1)|0.1840|0.6036|0.7144|0.7963|0.8274|0.8527|0.8717|0.8848|0.8941|0.9003|0.9019|\n|(C4) (k+1)-pertite rand.|0.1795|0.5788|0.7118|0.7800|0.8312|0.8550|0.8732|0.8885|0.8962|\n|(P1) k-peer exp.|0.1896|0.5837|0.7121|0.7874|0.8274|0.8545|0.8736|0.8860|0.8942|\n|(P2) Null-cascade|0.1927|__0.6301__|__0.7506__|__0.8095__|__0.8417__|__0.8649__|__0.8793__|__0.8935__|__0.8995__|\n\nEven with a relatively large network ($n = 75$), the highest test accuracy was achieved using our proposed null-cascade graph. This indicates that the experimental trend remains consistent with the results reported in the original paper.\n\nWe will include additional experimental results using relatively large $n$ in the revised version, along with consensus rate investigations similar to those shown in Sec. 5.1 (Test 1). \n\n__[W2] Limited motivation and benefits of extending from 1-peer exponential graph to k-peer graph.__\n\nWe may be misunderstanding your question, but if high-throughput distributed computing resources capable of supporting fast $k$-peer communication are available, then increasing the number of connections (with a reasonably large $k$) can enable communication-efficient decentralized training of models. Thanks to your question, we realized that our motivation for designing graphs extended to $k$-peer communication may not have been clearly conveyed. In the revised version of the Introduction, we would like to improve the explanation to make this point clearer.\n\n__[W3] Only showing the results based on communication rounds or iterations is inadequate.__\n\nThank you for pointing this out. First, we would like to clarify the limitations of our computing resources: our computational setup consists of eight GPUs in a single server without NVLink connectivity. Due to these constraints, we are required to simulate multiple nodes' updates on a single GPU. For example, when $n=30$, updates from $3$ or $4$ nodes are processed on each GPU. As a result, __it is difficult to accurately and fairly evaluate the impact of communication overheads.__ Moreover, these overheads become particularly significant when the number of neighbors $k$ is large. We kindly ask you to take our computational resource limitations into consideration. We believe that our proposed graphs are well-suited for deployment on more advanced computing infrastructures that offer high throughput and/or native support for simultaneous multicasting. \n\nFor this reason, we conducted comparisons with baseline graphs that have the same maximum degree $k$, including the base-$(k+1)$ graph, static random graph, and dynamic random graph (i.e., $(k+1)$-pertite random match graph). We will revise the future work section in Appendix H to reflect this discussion.\n\n__[Q1] In the simulation, why choosing k=2?__\n\nAlthough we present experimental results with $k=2$ in the main paper, __we also provided additional experimental results for $k \\in \\{ 3, 4 \\}$ in Appendix F (see Table 5 and Figure 33).__ Our proposed graphs are not limited to the case of $k=2$. If an additional page is available, we will include these extended results in the revised version. \n\n__[Q2] Application examples.__\n\nA promising application involves __decentralized learning of machine learning models, such as deep learning models, across data center networks.__ As modern data centers are geographically distributed across multiple regions, aggregating all data to a single site is often impractical due to regulatory, privacy, or legal constraints. Therefore, effectively leveraging both the distributed computational resources and the locally stored data at these sites is essential.\n\nGiven the operational overheads associated with, e.g., parameter tuning and algorithm implementation, the simplest decentralized learning algorithm, DSGD, is frequently adopted in real-world distributed computing environments. When deploying DSGD over data center networks, one can select a communication graph to perform partial averaging of local models. In this regard, the communication graphs we propose offer significant advantages in terms of both communication efficiency and the test accuracy of the resulting models."}, {"review_id": "mr6rjii44t", "reviewer": "Reviewer_cN3U", "summary": "This paper studies communication-efficient decentralized learning by improving the expected spectral gap to reduce deviations from global averaging. This paper addresses certain limitations of the 1-peer exponential graph and propose two new dynamic graphs: the k-peer exponential graph and the null-cascade graph. The null-cascade graph achieves finite-time convergence for any n while ensuring commutativity.", "questions": "1. Why do we need the 1-peer exponential graph? What is the advantage over the other graphs with constant spectral gap near 1, especially some well-known static graphs? What is the advantage of the 1-peer exponential graph?\n\n2. The construction of Null-cascade graph is a double loop algorithm. Is constructing such networks time-consuming in practical applications?\n\n3. Do we need to run Algorithm 1 at each iteration of the dentralized algorithm (e.g., DSGD), or every $\\tau$ iterations?\n\n4. In the experiments, this paper considers the number of agents ranging from 15 to 30. What occurs when scaling to 1000+ agents?", "limitations": "The main paper is difficult to follow.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. To address the limitation of the 1-peer exponential graph that the number of nodes n should be a power of two, this paper explores the extension to the k-peer exponential graph and observe that finite-time convergence can be interpreted by the DC component, suggesting that desiring finite-time convergence is only achieved when n is a power of k+1.\n\n2. To achieve finite-time convergence for any n while preserving commutativity, this paper proposes the null-cascade graph. The effectiveness of the proposed null-cascade graph was confirmed through numerical experiments.\n\n3. This study is significant in decentralized learning because communication serves as the bottleneck in distributed optimization, making the design of communication networks to reduce overhead a significant research problem.\n\n4. This paper seems theoretically solid. It addresses the limitation of the 1-peer exponential graph in theory and thus it seems novel.\n\nWeaknesses:\n\n1. There are many static graphs with nearly constant spectral gap p such that $\\frac{1}{p}$ in Theorem 1 is not large. Why do we need to design a new complex dynamic graph?\n\n2. The proposed null-cascade graph seems complex to implement. The reviewer suggests to discuss its disadvantage in practical implementation.\n\n3. The reviewer suggests to verify the efficiency of the proposed null-cascade graph on larger networks with 1000+ agents.\n\n4. While theoritically solid, this paper's theoretical complexity creates barriers to comprehension. The main paper is difficult to follow.\n\n5. Suggest introducing more examples for the practical applications of 1-peer exponential graph and the proposed null-cascade graph in the machine learning community.\n\nIn conclusion, this paper is theoretically solid. The problem studied in this paper is significant. However, it is difficult to follow.", "was_revised": true, "final_justification": "I agree to accept this paper.", "rebuttal": "First of all, we sincerely appreciate your insightful comments. We will carefully incorporate your feedback to improve the quality of this paper.\n\n__[W1] Why do we need to design a new complex dynamic graph?__\n\nWhen the maximum degree $k$ (maximum number of each node connections) is restricted to be a small value $(k \\ll n)$, static graphs cannot achieve a spectral gap $p$ such that $1/p$ in Theorem 1 is not large. In Table 3 of Appendix D, we present the convergence rates of DSGD using various graphs, including several static graphs such as ring, torus, and exponential graphs. These results are obtained by substituting the following spectral gap into the convergence rate for DGSD given in Theorem 1:\n\nRing: $p = O(1 / n^2), k = 2, \\tau=1$, \n\nTorus: $p = O(1 / n), k = 4, \\tau=1$, \n\nExponential: $p = O(1 / \\log_{2} n), k = \\lceil \\log_{2}(n) \\rceil, \\tau=1$.\n\nAmong these static graphs, the spectral gap can be improved using the exponential graph; however, it requires $k = \\lceil \\log_{2}(n) \\rceil$ connections. Therefore, it is infeasible when $k$ is restricted to be a small value relative to $n$ (i.e., $k \\ll n$). \n\nTo address this limitation, dynamic graphs have been explored for communication-efficient decentralized learning. Notable examples include the 1-peer exponential graph, base-(k+1) graph, and EquiTopo graphs.\n\n__[W2] Discuss disadvantages of the proposed null-cascade in practical implementation.__\n\nWe emphasize that Algorithms 1-3 are not difficult to implement. However, as you pointed out, Algorithm 4--which is used to select roots $q$, expansions $m$, and communication orders $c$ to compute SNFs may be complex. This complexity arises because combinations of $(q, m, c)$ are not uniquely determined, requiring a greedy search to identify suitable candidates. To mitigate your concern, we will include a discussion of this limitation in the null-cascade graph implementations, and we will release the organized source code upon publication of this paper.\n\n__[W3], [Q4] Verify the efficiency of the proposed null-cascade graph on larger networks.__\n\nTo address your concern, __we conducted additional evaluations using a relatively large network size.__ While you suggest testing at an even larger scale (e.g., $n > 1000$), such an experiment exceeds the limits of our available computing resources. As a compromise, we selected $(n, k) = (75, 2)$. The evaluation setting follows the same CIFAR-10 classification task with heterogeneous data allocation ($\\alpha = 0.1$) as in Section 5.2 (Test 2).\n\n__[CIFAR-10 classification ($\\alpha=0.1$) with $(n, k) = (75, 2)$]__\n\n|Communication round |r=5|r=100|r=200|r=300|r=400|r=500|r=600|r=700|r=800|\n|---------------- | --- | --- | --- | --- | --- | --- | --- | --- | --- |\n|(C1a) Ring|__0.1953__|0.4882|0.5173|0.5496|0.5802|0.616|0.6442|0.6735|0.7038|0.7252|\n|(C2) Base-(k+1)|0.1840|0.6036|0.7144|0.7963|0.8274|0.8527|0.8717|0.8848|0.8941|0.9003|0.9019|\n|(C4) (k+1)-pertite rand.|0.1795|0.5788|0.7118|0.7800|0.8312|0.8550|0.8732|0.8885|0.8962|\n|(P1) k-peer exp.|0.1896|0.5837|0.7121|0.7874|0.8274|0.8545|0.8736|0.8860|0.8942|\n|(P2) Null-cascade|0.1927|__0.6301__|__0.7506__|__0.8095__|__0.8417__|__0.8649__|__0.8793__|__0.8935__|__0.8995__|\n\nEven with a relatively large network ($n = 75$), the highest test accuracy was achieved using our proposed null-cascade graph. This indicates that the experimental trend remains consistent with the results reported in the original paper.\n\nWe will include additional experimental results using relatively large $n$ in the revised version, along with consensus rate investigations similar to those shown in Section 5.1 (Test 1). \n\n__[W4] This paper's theoretical complexity creates barriers to comprehension.__\n\nWe apologize if parts of our paper were difficult to follow. Balancing accessibility with theoretical completeness within the space constraints has indeed been challenging. We would like to respectfully highlight that other reviewers found the writing to be clear. \n\n__[W5] Introducing examples for the practical applications.__\n\nA promising application involves __decentralized learning of machine learning models, such as deep learning models, across data center networks.__ As modern data centers are geographically distributed across multiple regions, aggregating all data to a single site is often impractical due to regulatory, privacy, or legal constraints. Therefore, effectively leveraging both the distributed computational resources and the locally stored data at these sites is essential.\n\nGiven the operational overheads associated with, e.g., parameter tuning and algorithm implementation, the simplest decentralized learning algorithm, DSGD, is frequently adopted in real-world distributed computing environments. When deploying DSGD over data center networks, one can select a communication graph to perform partial averaging of local models. In this regard, the communication graphs we propose offer significant advantages in terms of both communication efficiency and the test accuracy of the resulting models.\n\n__[Q1] What is the advantage of the 1-peer exponential graph?__\n\nWhen the maximum degree $k$ is constrained (e.g., to reduce communication overhead), the spectral gap of a static graph can only be improved up to a certain point. In contrast, allowing dynamically changing connections between nodes opens up the possibility of increasing the spectral gap in expectation.\n\nMotivated by this aim, prior works have explored dynamic graphs, such as 1-peer exponential graph, base-(k+1) graph, and EquiTopo graph. In our work, we further investigate more advanced dynamic graphs, including $k$-peer exp. graph and null-cascade graph.\n\n__[Q2] Is constructing such networks time-consuming in practical applications?__\n\n__[Q3] Do we need to run Algorithm 1 at each iteration?__\n\n__The communication graph is constructed based on $(n,k)$ at the initialization step, prior to the start of model training, that is, Algorithm 1 does NOT need to run at each iteration.__ This is identified in line 2 of Algorithm 6 in Appendix F. While, as you rightly pointed out, constructing such networks can be time-consuming, this is required only once at initialization. We suspect this may not have been fully apparent, and we will clarify it in the revised version."}, {"review_id": "BNt4qUhWvP", "reviewer": "Reviewer_Nrs7", "summary": "The paper examines the role of communication network topologies in decentralized learning, reinvestigating 1-peer exponential topologies and introducing an extended version: $k$-peer exponential networks followed by the nullcascade graph topology. The nullcascade topology demonstrates finite-time convergence for any possible number of nodes and connections while utilizing uniform degree subgraphs, unlike the base $(k+1)$ communication topology.", "questions": "see weaknesses", "limitations": "The proposed approach requires predefined subgraph structures based on fixed $(n, k)$ values, assuming stable, fully connected topologies.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "#### **Strengths:**\n\n- The paper is well written and easy to read, with extra information and clear examples provided in the appendix.\n- The dependence of finite-time convergence on isolating the DC component while nullifying other non-zero frequencies is a novel and interesting finding.\n- The design of MAF and SNF filters to nullify non-zero frequencies is a clear, effective approach.\n- The paper includes solid experimental studies showing better performance compared to base $(k+1)$.\n\n---\n\n#### **Weaknesses and Questions:**\n\n- The role of commutativity is not clear, even though the paper states that “commutativity necessitates strict lock-step synchronization to coordinate the periodic communication cycles among nodes.”\n  - How does commutativity specifically help decentralized training?\n  - Can asynchronous training be supported in these topologies?\n  - How can practical implementations benefit from commutative network structures in real-world decentralized training systems?\n\n- Can a filter be designed that directly zeros out undesired frequencies without cascading many filters? For example, instead of using $\\tau$ circulant matrices, is it possible to define a filter that places the required zeros at the targeted frequencies in a single communication round, potentially with fewer or different graph connections?\n\n\n- The proposed approach requires predefined subgraph structures based on fixed $(n, k)$ values, assuming stable, fully connected topologies. In dynamically changing networks where nodes may leave, join, or lose connectivity, the designed structures may no longer satisfy the required properties, limiting its practical applicability in dynamic decentralized learning environments. Is this correct?\n\n- Algorithm 4 seems complex, but the paper does not discuss the implementation or runtime cost of Algorithms 3 and 4, which is important for assessing scalability.\n\n\n- When using \\paragraph{Text}, it is clearer to end the paragraph title with a period (i.e., \\paragraph{Text.}), which visually separates the heading from the body text and improves readability.", "was_revised": true, "final_justification": "My initial score was 5, and from the first time I read the paper, I thought it had a good chance of being accepted, as it is well written and presents a novel and interesting approach. As someone working on decentralized learning, I believe their contribution is both significant and necessary for the field. Their response to my questions was also satisfactory.", "rebuttal": "First of all, we sincerely appreciate your insightful comments. We will carefully incorporate your feedback to improve the quality of this paper.\n\n__[W1] Unclear role of commutativity.__\n\n__- Can asynchronous training be supported in these topologies?__\n\nUnder __synchronized communication among $n$ nodes,__ the mixing matrices can be applied in an arbitrary order, as long as the corresponding graphs satisfy the commutativity of mixing matrices specified in Definition 4.\n\n__- How does commutativity specifically help decentralized training?__\n\nWe agree this is an important question. Given your insightful comment, we reconsider the benefit of commutativity of mixing matrices in decentralized learning, and a possible idea which may mitigate your concern is summarized as follows:\n\nFirst, we would like to emphasize that reducing the discrepancy between the global model $\\bar{x}^{(r)}$ and local models $x_{i}^{(r)}$, specifically, minimizing $\\sum_{i=1}^{n} \\| \\bar{x}^{(r)} - x_{i}^{(r)} \\|$ is crucial for improving the convergence rate of decentralized learning algorithms. This quantity explicitly appears in the convergence rate of DSGD, as stated in Theorem 1 (see proof in [12]). __Ensuring the commutativity of the mixing matrices within graphs would help reduce this discrepancy.__\n\nTo illustrate this, we reformulate the update rules of DSGD recursively, as follows:\n\n$X^{(r+1)} \n= X^{(r)} W^{(r)} - \\eta \\nabla F(X^{(r)}; \\xi^{(r)}) W^{(r)}$\n\n$= X^{(r-1)} W^{(r-1)} W^{(r)} - \\eta \\{ \\nabla F(X^{(r-1)}; \\xi^{(r-1)}) W^{(r-1)} W^{(r)} + \\nabla F(X^{(r)}; \\xi^{(r)}) W^{(r)} \\}$\n\n$\\vdots$\n\n$= X^{(0)} W^{(0)} \\cdots W^{(r)} - \\eta \\{ \\nabla F(X^{(0)}; \\xi^{(0)}) W^{(0)} \\cdots W^{(r)} + \\cdots + \\nabla F(X^{(r)}; \\xi^{(r)}) W^{(r)} \\}$\n\n$= X^{(0)} \\prod_{s=0}^{r} W^{(s)} - \\eta \\sum_{s_{1}=0}^{r} \\{ \\nabla F(X^{(s_{1})}; \\xi^{(s_{1})})  \\prod_{s_{2}=s_{1}}^{r} W^{(s_{2})} \\}.$\n\nNext, we investigate the property of $\\prod_{s_{2} = s_{1}}^{r} W^{(s_{2})}$ for finite-time convergent graph with periodic interval $\\tau$. \n\n__[Case 1: Commutativity of mixing matrices is satisfied]__\n\nWhen commutativity of mixing matrices is satisfied, $W^{(\\rho(0))} W^{(\\rho(1))} \\cdots W^{(\\rho(\\tau-1))} = \\frac{1}{n} 1 1^{T}$ for any permutation $\\rho$. The product $\\prod_{s_{2} = s_{1}}^{r} W^{(s_{2})}$ can be categorized into two cases: \n\n(Case 1a) When $s_{1} \\leq r - \\tau + 1$, $\\prod_{s_{2} = s_{1}}^{r} W^{(s_{2})} = \\frac{1}{n} 1 1^{T}$. \n\n(Case 1b) When $s_{1} \\geq r - \\tau + 2$, $\\prod_{s_{2} = s_{1}}^{r} W^{(s_{2})} \\neq \\frac{1}{n} 1 1^{T}$. \n\nThese results indicate that no discrepancy among $n$ nodes can occur for terms with index $s_{1} \\in [0, r - \\tau + 1]$ (in Case 1a). In contrast, discrepancy among $n$ nodes can occur for terms with index $s_{1} \\in [r - \\tau + 2, r ]$ (in Case 1b), which leads to degradation in the convergence rate. \n\n__[Case 2: Commutativity of mixing matrices is NOT satisfied]__\n\nWhen we denote $\\mod (r, \\tau) = \\phi$, the product $\\prod_{s_{2} = s_{1}}^{r} W^{(s_{2})}$ can be categorized into two cases: \n\n(Case 2a) When $s_{1} \\leq r - \\tau - \\phi + 1$, $\\prod_{s_{2} = s_{1}}^{r} W^{(s_{2})} = \\frac{1}{n} 1 1^{T}$. \n\n(Case 2b) When $s_{1} \\geq r - \\tau - \\phi + 2$, $\\prod_{s_{2} = s_{1}}^{r} W^{(s_{2})} \\neq \\frac{1}{n} 1 1^{T}$. \n\nThese results indicate that no discrepancy among $n$ nodes can occur for terms with index $s_{1} \\in [0, r - \\tau - \\phi + 1]$ (in case 2a). In contrast, discrepancy among $n$ nodes can occur for terms with index $s_{1} \\in [r - \\tau - \\phi + 2, r ]$ (in case 2b), which leads to degradation in the convergence rate. \n\nComparing these two cases, __the components that contribute to discrepancies among the $n$ nodes tend to be more significant when $\\mod (r, \\tau) = \\phi$ is non-zero.__ Although this difference may be small and therefore difficult to observe empirically, __we have theoretically demonstrated the advantage of using commutative mixing matrices.__ To reflect this discussion, we will revise the sentence in the Introduction regarding commutativity and add an Appendix section to explain the potential benefits of commutativity as discussed above.\n\n__[W2] Can a filter be designed that directly zeros out undesired frequencies without cascading many filters?__\n\nWhen a large value of $k$ is available, undesired frequencies can be effectively nullified without the need to cascade many filters. For instance, in the extreme case of $k = n - 1$, all non-zero frequencies can be eliminated; however, this corresponds to the complete graph, where each node is connected to all other nodes.\n\nWe highlight a fundamental trade-off between the number of nullified frequencies and the value of $k$. In practical network settings, only a relatively small $k$ (i.e., $k \\ll n$) is typically feasible. Under such constraints, __it is impossible to nullify undesired frequencies without cascading multiple filters.__\n\n__[W3] In dynamically changing networks where nodes may leave, join, or lose connectivity, the designed structures may no longer satisfy the required properties. Is this correct?__\n\nYes, our problem setting is to construct dynamical graphs given $(n, k)$; namely, dynamically-changing $(n, k)$ scenarios are out of scope.\n\n__[W4] Discussion of implementation or runtime cost of Algorithms 3 and 4.__\n\nFirst, we assume that our graph is constructed at the initialization step of decentralized learning. Since we do not consider dynamically changing networks, as you pointed out in [W3], we believe that computational cost would not pose a serious issue. \n\nSecond, __we emphasize that the runtime cost of Algorithms 1-4 is negligible for many $(n, k)$-configurations.__ Algorithms 1-3 are straightforward to implement and incur negligible runtime overhead. Algorithm 4, which is used to select the roots $q$, expansions $m$, and communication orders $c$ for computing SNFs, may be complex to implement and may introduce noticeable runtime costs. This potential complexity stems from the fact that combinations of $(q, m, c)$ are not uniquely determined, requiring a greedy search to identify suitable candidates. While we have not exhaustively evaluated the runtime cost for all possible $(n, k)$-configurations, we confirm that for those configurations tested in our experiments (as reported in Section 5 and Appendix F), the runtime costs were negligible. To further address this concern, we will include runtime measurements for the $(n,k)$-configurations used in our experiments and will release the corresponding source code upon the publication of this paper.\n\n__[W5] Missing period in paragraph title.__\n\nAs you suggested, we separate the paragraph title from the body using period in the revised version."}, {"review_id": "wfoRcYMWF5", "reviewer": "Reviewer_6S3u", "summary": "This paper re-visited well-studied one peer exponential graph and extended it to k peer. Using Steerable Nulling Filters, authors are able to propose the null-cascade graph which has finite-time convergence for any n. The authors present numerical experiments verifying their claims for both consensus errors and deep learning setting.", "questions": "1. In reference [26], it should be O(1) instead of o(1).\n2. Adding more intuition and explanation about MAF and SNF would be helpful.\n3. Adding the missing reference.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: \n1. The authors re-stated some basic definitions/theorems from the one peer exponential graphs, which is a good refresher in case some readers are not familiar with decentralized learning.\n2. Although the definition of the k-peer exponential graph is a trivial extension of the one peer case, the authors proposed a necessary condition using Fourier transform in the frequency space. They also found the expected spectral gap of the k-peer exponential graphs.\n3. To support the case when n is not power of k+1, authors proposed null-cascade graph and showed they have expected spectral gap 1. \n4. The authors tested their algorithm for consensus errors. The outcome is consistent with their claim. From the plots, one can clearly observe that it has finite time convergence. The null cascade graph also performed well on CIFAR10 and CIFAR10 in the deep learning setting.\n\nWeaknesses:\n1. The optimal rate for any n has been achieved in for example [1]. The authors should at least mention this work.\n2. The extension from 1 peer exponential graph to k peer is quite straightforward. \n3. The authors included little intuition and explanation about MAF. Specifically, \"We notice that (4) is a MAF with (k + 1) uniform weights and its expansions\" needs more details. \n4. The authors only discussed spectral gap of the null cascade graph. While having some deep learning experiments, the authors did not prove the method converge in the deep learning setting, unlike many previous work, [1, 2, 3].\n\n\n[1] Ding et al. DSGD-CECA: Decentralized SGD with Communication-Optimal Exact Consensus Algorithm, 2023.\n\n[2] Ying et al. Exponential graph is provably efficient for decentralized deep training, 2021. \n\n[3] Song et al. Communication efficient topologies for decentralized learning with O(1) consensus rate, 2023.", "was_revised": true, "final_justification": "The authors have addressed all my concerns. I believe this work makes a meaningful contribution to the field of decentralized learning.", "rebuttal": "First of all, we sincerely appreciate your insightful comments. We will carefully incorporate your feedback to improve the quality of this paper.\n\n__[W1] The optimal rate for any $n$ has been achieved in for example [1]. [1] Ding et al. DSGD-CECA: Decentralized SGD with Communication-Optimal Exact Consensus Algorithm, 2023.__\n\nAs you suggested, a missing reference [1] will be cited in the revised version. We believe that our study offers advantages by proposing graphs that maximally leverage distributed computing resources capable of supporting multi-peer communication with $k \\geq 2$.\n\n__[W2] The extension from 1-peer exponential graph to $k$-peer is quite straightforward.__\n\nWe believe that Section 3, which extends from 1-peer exponential graph to $k$-peer exponential graph, plays a crucial role in establishing the connection between the expected spectral gap and the Discrete Fourier Transform (DFT). While, as you pointed out, the extension from the 1-peer to be $k$-peer exponential graph may not represent a major novelty on its own, __its importance lies in enabling a novel analysis of the expected spectral gap through the DFT of the employed filters,__ specifically, the Moving Average Filters (MAFs) that underlie the $k$-peer exponential graph.\n\nBuilding on this foundation, Section 4 extends this idea by incorporating Steerable Null Filters (SNFs) alongside MAFs, leading to the formulation of the proposed null-cascade graph. In this context, the $k$-peer exponential graph serves as a critical conceptual and technical milestone towards the development of the null-cascade graph.\n\n__[W3] [Q2] Adding more intuition and explanation about MAF and SNF would be helpful.__\n\nWhile the application of DFT to the filters (e.g., MAFs and SNFs) is standard practice in the signal processing community, it may be unfamiliar to many researchers in the machine learning field. Therefore, we will include more intuitive explanations of MAFs and SNFs, along with their frequency characteristics, in the Appendix of the revised version.\n\n__[W4] The authors only discussed spectral gap of the null-cascade graph.__\n\n__See Table 3 in Appendix D, which presents the convergence rates of DSGD with various graphs,__ including our proposed graphs: the $k$-peer exponential graph and the null-cascade graph. These convergence rates can be derived by substituting the expected spectral gap $p$ and the periodic interval $\\tau$ into the convergence expression of DSGD given in Theorem 1. Due to space constraints, we have omitted these details from the main paper.\n\n__[Q1] In [26], it should be O(1) instead of o(1).__\n\nThank you for pointing this out. This will be modified in the revised version."}]

Author rebuttal:

Meta-review: This work develops new dynamic graphs for communication-efficient decentralized learning. Building on the 1-peer exponential graph, the authors propose the k-peer exponential and null-cascade graphs, with the latter guaranteeing finite-time convergence for any number of nodes and demonstrating superior empirical performance. 

During the rebuttal, the authors provided detailed experiments and derivations that clarified the reviewers’ concerns. All reviewers  recommend accepting the paper.
Decision: Accept (poster)