Multigraph Topology Design for Cross-Silo Federated Learning
Authors: Tuong Khanh Long Do
Binh Xuan Nguyen
Toan Tran
Erman Tjiputra
Quang D. Tran
Hien Nguyen
Vuong Pham
Anh Nguyen
Venue: Submitted to ICLR 2023 (2023)
Keywords: Federated Learning
Topology Design
Multigraph

Abstract: Cross-silo federated learning utilizes a few hundred reliable data silos with high-speed access links to jointly train a model. While this approach becomes a popular setting in federated learning, designing a robust topology to reduce the training time is still an open problem.
In this paper, we present a new multigraph topology for cross-silo federated learning. We first construct the multigraph using the overlay graph. We then parse this multigraph into different simple graphs with isolated nodes. The existence of isolated nodes allows us to perform model aggregation without waiting for other nodes, hence reducing the training time. We further propose a new distributed learning algorithm to use with our multigraph topology. The intensive experiments on public datasets show that our proposed method significantly reduces the training time compared with recent state-of-the-art topologies while ensuring convergence and maintaining the accuracy.

Under review as a conference paper at ICLR 2023
MULTIGRAPH TOPOLOGY DESIGN FOR CROSS-SILO FEDERATED LEARNING
Anonymous authors Paper under double-bling review
ABSTRACT
Cross-silo federated learning utilizes a few hundred reliable data silos with high- speed access links to jointly train model. While this approach becomes popular setting in federated learning, designing a robust topology to reduce the training time is still an open problem. In this paper, we present a new multigraph topol- ogy for cross-silo federated learning. We first construct the multigraph using the overlay graph. We then parse this multigraph into different simple graphs with isolated nodes. The existence of isolated nodes allows us to perform model ag- gregation without waiting for other nodes, hence reducing the training time. We further propose a new distributed learning algorithm to use with our multigraph topology. The intensive experiments public datasets show that proposed method significantly reduces the training time compared with recent state-of-the topologies while ensuring convergence and maintaining the accuracy.
INTRODUCTION
Federated learning entails training models via remote devices or siloed data centers while keeping data locally to respect the user's pri- vacy policy (Li et al., 2020a). According to Kairouz al. (2019), there two popular training scenarios: the cross-device scenario, which encompasses variety (millions or even billions) of unreliable edge devices with lim- ited computational capacity and slow connec- tion speeds; and the cross-silo scenario, which involves only few hundred reliable data silos with powerful computing resources and high- speed access links. Recently, cross-silo sce- nario becomes popular in different federated learning applications such as healthcare (Xu al., 2021), robotics (Nguyen et al., 2021; Zhang et al., 2021c), medical imaging (Cour- tiol al., 2019; Liu et al., 2021), and fi- nance (Shingi, 2020).
4000
100
3000
70.14
67.21
72.56
71.05
71:13
75
18564
Accurscy (8)
2000
1480.5
Time
1000
590.8
590.8
84.7
STAR
(ATCHA(+)
MST
8-MBST
RING
OURS
Mothods
Wall-dock Time
Accuracy
Comparison between different topolo- gies FEMNIST dataset and Exodus net- work (Miller et al., 2010). The accuracy and to- tal wall-clock training time (or overhead time) are reported after 6, 400 communication rounds.
Figure 1:
In practice, federated learning is promising research direction where we can utilize the ef- fectiveness of machine learning methods while respecting the user's privacy. Key challenges in federated learning include model convergence, communication congestion, and imbalance of data distributions different silos (Kairouz al., 2019). A popular federated training method central node that orchestrates the training process and aggregates contributions of all clients. Main limitation of this client-server approach is that the server node potentially represents a communica- tion congestion point in the system, especially when the number of clients is large. To overcome this limitation, recent research has investigated the decentralized (or peer-to-peer) federated learn- ing approach. In the aforementioned approach, the communication is done via peer-to-pes topology without the need for a central node. However, main challenge of decentralized federated learning is to achieve fast training time, while assuring model convergence and maintaining the model accuracy.
set

---

Under review as a conference paper at ICLR 2023
In federated learning, the communication topology plays an important role. A more efficient topol- ogy leads to quicker convergence and reduces the training time, quantifying by the worst-case con- vergence bounds in the topology design (Jiang et al., 2017; Nedié et al., 2018: Wang & Joshi, 2018). Furthermore, topology design is directly related to other problems during the training process such as network congestion, the overall accuracy of the trained model, energy usage (Yang al., 2021; Nguyen et al., 2021; Kang et al., 2019). Designing a robust topology that can reduce the training time while maintaining the model accuracy still an open problem in federated learning (Kairouz et al., 2019). This paper aims to design a new topology for cross-silo federated learning, which is one of the most common training scenarios in practice.
Recently, different topologies have been proposed for cross-silo federated learning. In (Brandes, 2008), the STAR topology is designed where the orchestrator averages all models throughout each communication round. Wang et al. (2019) propose MATCHA to decompose the set of possible communications into pairs of clients. At each communication round, they randomly select some pairs and allow them to transmit models. Marfoq et al. (2020) introduce the RING topology with the largest throughput using max-plus linear systems. While some progress has been made in the field, there are challenging problems that need to be addressed such congestion access links (Wang et al., 2019; Yang et al., 2021), straggler effect (Neglia et al., 2019; Park et al., 2021), or identical topology in all communication rounds (Jiang et al., 2017; Marfoq et al., 2020).
In this paper, we propose a new multigraph topology based on the recent RING topology (Marfoq al., 2020) to reduce the training time for cross-silo federated learning. Our method first constructs the multigraph based on the overlay of RING topology. Then we parse this multigraph into simple graphs (i.e.. graphs with only one edge between two nodes). We call each simple graph is state of the multigraph. Each state of the multigraph may have isolated nodes, and these nodes can do model aggregation without waiting for other nodes. This strategy significantly reduces the cycle time in each communication round. To ensure model convergence, we also adapt and propose a new distributed learning algorithm. The intensive experiments show that our proposed topology significantly reduces the training time in cross-silo federated learning (See Figure 1).
2 LITERATURE REVIEW
Federated Learning. Federated learning has been regarded as a system capable of safeguarding data privacy (Konečný et al.. 2016; Gong al., 2021: Zhang et al., 2021b; Li et al., 2021b). Contempo- rary federated learning has centralized network design in which a central node receives gradients from the client nodes to update global model. Early findings of federated learning research include the work of Konečný et al. (2015), as well as a widely circulated article from McMahan & Ramage (2017). Then Yang et al. (2013); Chaley-Shwart. & Zhang (2013); Ma et al. (2015); Jaggi et al. (2014), and Smith et al. (2018) extend the concept of federated learning and its related distributed optimization algorithms. Federated Averaging (FedAvg) was proposed by McMahan et al. (2017), its variations such as FedSage (Zhang et al., 202 aa) and DGA (Zhu et al., 2021b), other recent -fate-of-the-art model aggregation methods (Hong et al., 2021; Ma et al., 2022: Zhang et al., 2022; Liu et al., 2022; Elgabli et al., 2022) are introduced to address the convergence and non-llI (non- identically and independently distributed) problem. Despite its simplicity, the client-server approach suffers from the communication and computational bottlenecks in the central node, especially when the number of clients is large (He et al., 2019; Qu et al., 2022).
Decentralized Federated Learning. Decentralized (or peer-to-peer) federated learning allows each silo data to interact with its neighbors directly without a central node (He et al., 2019). Due to its nature, decentralized federated learning does not have the communication congestion at the central node, however, optimizing fully peer-to-peer network is challenging task (Nedić & Olshevsky, 2014; Lian et al., 2017; He et al., 2018; Lian et al., 2018: Wang et al., 2019; Marfoq et al., 2020; 2021; Li et al., 2021a). Noticeably, the decentralized periodic averaging stochastic gradient de- scent (Wang& & Joshi, 2018) is proved to converge at a comparable rate to the centralized algorithm while allowing large-scale model training (Wu et al., 2017; Shen et al., 2018; Odeyomi & Zaruba, 2021). Recently, systematic analysis of the decentralized federated learning has been explored by (Li et al., 2018b; Ghosh et al., 2020; Koloskova et al., 2020).
Communication Topology. The topology has a direct impact on the complexity and convergence of federated learning (Chen et al., 2020). Many works have been introduced to improve the effective-
2

---

Under review as a conference paper at ICLR 2023
ness of topology, including star-shaped topology (Brandes, 2008; Konečný et al., 2016; McMahan
et al., 2016: 2017: Kairouz et al., 2019) and optimized-shaper topology (Neglia et al., 2019; Wang et al., 2019; Marfoq et al., 2020; Bellet et al., 2021; Vogels et al., 2021: Huang et al., 2022). Par- ticularly, a spanning tree topology based on Prim (1957) algorithm was introduced by Marfoq et al. (2020) to reduce the training time. As mentioned by Brandes (2008), STAR topology is designed where an orchestrator averages model updates in each communication round. Wang et al. (2019) introduce MATCHA speed up the training process through decomposition sampling. Since the duration of communication round is dictated by stragglers effect (Karakus et al., 2017: Li et al., 2018a), Neglia al. (2019) explore how to choose the degree of a regular topology. Marfoq et al. (2020) propose RING topology for cross-silo federated learning using the theory of max-plus linear systems. Recently, Huang et al. (2022) introduce Sample-induced Topology which is able to recover effectiveness of existing SGD-based algorithms along with their corresponding rates.
Multigraph. The definition of multigraph has been introduced as a traditional paradigm (Gibbons, 1985; Walker, 1992). A typical "graph" usually refers to a simple graph with no loops multiple edges between two nodes. Different from a simple graph, multigraph allows multiple edges between two nodes. In deep learning, multigraph has been applied in different domains, including cluster- ing (Martschat, 2013; Luo et al., 2020; Kang et al., 2020). medical image processing (Liu et al., 2018; Zhao al., 2021; Bessadok al., 2021). traffic flow prediction (Lvv al., 2020; Zhu al., 2021a), activity recognition (Stikic et al., 2009), recommendation system (Tang et al., 2021), 1), and cross-domain adaptation (Ouyang et al., 2019). In this paper, we construct the multigraph to enable isolated nodes and reduce the training time in cross-silo federated learning.
3 PRELIMINARIES
3.1 FEDERATED LEARNING
In federated learning, silos do not share their local data, but still periodically transmit model updates between them. Given N siloed data centers, the objective function for federated learning is:
N P.lEE [11 (w, E:),
min WER'
(I)
where (,, E.) is the loss of model The coefficient y; > 0 specifies the relative importance of each silo. Recently, different distributed algorithms have been proposed to optimize Eq. (Konecný et al., 2016; McMahan al., 2017; Li et al., 2020b; Wang et al., 2019; Li et al., 2019; Wang & Joshi, 2018; Karimireddy et al., 2020). In this work, we use DPASGD (Wang & Joshi, 2018) algorithm to update the weight of silo in each training round as follows:
Rdd & is input sample drawn from data silo i.
Ejenturn Ar, (k), w: (k) ax Σ VL, (ws {() (k))
if = 0 (mod + 1),
w: (k: +
otherwise.
where b is the batch size, i, denote the silo, is the number of local updates, og > is a potentially varying learning rate at k-th round, A E NNN is consensus matrix with non-negative weights, and N is the in-neighbors set that silo has the connection to.
3.2 MULTIGRAPH FOR FEDERATED LEARNING
Connectivity and Overlay. Following Marfoq et al. (2020), we consider the connectivity G. (V,Ec) as graph that captures possible direct communications among silos. Based on its definition, the connectivity is often a fully connected graph and is also a directed graph. The overlay Go is a connected subgraph of the connectivity graph, i.e., Go (V,E)), where E, &c. Only nodes directly connected in the overlay graph Go will exchange the messages during training. We refer the readers to Marfoq al. (2020) for more in-deep discussions.
Multigraph. While the connectivity and overlay graph can represent different topologies for feder- ated learning, one of their drawbacks is that there only one connection between two nodes. In our
3

---

Under review as a conference paper at ICLR 2023
(a) Connectivity
(b) Overlay
(c) Multigraph
(d) State of Multigraph
Figure 2: Example of connectivity, overlay, multigraph, and state of our multigraph. Blue node is an isolated node. Dotted line denotes a weakly-connected edge.
work, construct a multigraph 9m Em) from the overlay Go. The multigraph contain multiple edges between two nodes (Chartrand & Zhang, 2013). In practice, we parse this multigraph different graph states, each state is simple graph with only one edge between two nodes.
In the multigraph Gm. the connection edge between two nodes has two types: strongly-connected edge and weakly-conneeted edge (Ke-xing al., 2016). Under both strongly and weakly con- nections, the participated nodes can transmit their trained models to their out-neighbours M, or download models from their in-neighbours N However, in strongly-connected edge, two nodes in the graph must wait until all upload and download processes between them are finished to do model aggregation. On the other hand, in weakly-comnected edge, the model aggregation process in each node can be established whenever the previous training process is finished by leveraging up-to-dated models which have not been used before from the in-neighbours of that node.
State of Multigraph. Given a multigraph Gm, we can parse this multigraph into different sim- ple graphs with only one connection between two nodes (either strongly-connect or weakly- connected). We call each simple graph as state 9% of the multigraph.
Isolated Node. A node is called isolated when all of its connections to other nodes are weakly- connected edges. The graph concepts and isolated nodes are shown in Figure
3.3 DELAY AND CYCLE TIME IN MULTIGRAPH
Delay, Following Marfoq et al. (2020), delay to an edge e(i,j) the time interval when node receives the weight sending by node i, which can be defined by:
d(i, = T +(+,))+ + O(i
(3)
where (1) denotes the time to compute one local update of the model; the number of local updates; ji is the link latency; M is the model size; Oii is the total network traffic capacity.
However, unlike other communication infrastructures, the multigraph only contains connections between silos without other nodes such as routers or amplifiers. Thus, the total network traffic
capacity O(i,j) = min Cup(() Cox(j) where CUp and Cdn denote the upload and download | |A
link capacity. Note that the upload and download can happen in parallel.
Since multigraph can contain multiple edges between two nodes, we extend the definition of the delay in Eq. to de (i, j). with i is the k-th communication round during the training process,
if (ex(i.)) = and es (i.j) = 1) or k max(u T=()).4((t.) - (t..). TM(9m) + d (i,))),
(i
(f, and ex ct-1 ef and ex-1(i,j)
du (i.i)
Tx())))
otherwise
where e(i,j) indicates connected edge, e(i.j) = indicates strongly-connecten edge; The (9 is the cycle time at the k-th computation round during the training process.
4

---

Under review as a conference paper at ICLR 2023
Cycle Time. The cycle time per round is the time required to complete communication round (Marfog et al., 2020). In this work, we define the cycle time per round is the maximum delay between all silo pairs with strongly-conmected edges. Therefore, the average cycle time of the entire training is:
R-1
(G =
Σ
max JEN;
(dx (1.1))
(5)
vie
k=0
where N + is an in-neighbors silo set of i whose edges are strongly-connected.
4 METHODOLOGY
Our method first constructs the multigraph based on an overlay. Then we parse this multigraph into multiple states that may have isolated nodes. Note that, our method does not choose isolated nodes randomly, but relies on the delay time. In our design, each isolated node has a long delay time in current communication round. However, in the next round, its delay time will be updated using Eq. 4, and therefore can become a normal node. This strategy allows us to reduce the waiting time with isolated nodes, while ensuring that isolated nodes can become normal nodes and contribute the training in the next communication round.
4.1 MULTIGRAPII CONSTRUCTION
Algorithm 1: Multigraph Construction
Input: Overlay Go (V,E.):
Maximum edge between two nodes t.
Output: Multigraph Gm. (V, Em):
List number of edges between silo pairs L.
// Computte delay
overlay
D, t NULL
foreach e(i, E & do
d(i,j) f- Using Eq. 3
Append jii.j) into D.
// Construct multigraph
dmin min Do) // find smallest delay
Em + NULL // multiset of edges C(lV), [V] + (0)
foreach ef,, & do
n(i.j) min round
d(i.i)
// find number of edges for (i, 5)
duin
& - NULL // temporary edge
11
Append j) = into &
foreach (n(i,j) 1) do
Append e(i.j) = 0 into &
14
Append & into &m
Chi,j) t n)i,j).
return G. (V, Em): C.
Algorithm 1 describes our methods to generate the multigraph 9m with multiple edges between silos. The algorithm takes the overlay 9o as input. Similar Marfoq et al. (2020), we use the Christofides algorithm (Monnot al., 2003) to obtain the overlay.
Algorithm 1, we focus on establishing multiple edges that indicate different statuses (strongly- connected or ceakly-connected), To identify the total edges between silo pair, we divide the delay d(i,j) by the smallest delay dmin over all silo pairs, and compare it with the maximum number of edges parameter t (t 5 in experiments). We assume that the silo pairs with longer delay will have more to increase the number of weakly-connected edges, which generate isolated nodes to speed up
edges, hence potentially becoming the isolated nodes. Overall, we aim

---

Under review as a conference paper at ICLR 2023
the training process. Note that, from Algorithm 1, each silo pair in the multigraph should have one strongly-commected edge and multiple weakly-connece edges. The role of the coongly-connettdd edge is make sure that two silos have good connection in at least one communication round.
///'
7- Overlay
/-
/
Communication Round
==1
==
à =
h ==
(a)
States
Multigraph
Communication
k
3 k 4
(b)
The comparison between RING (Marfoq et al., 2020) topology and our multigraph topol- ogy in each communication round. (a) RING uses the same overlay each round. (b) Our proposed multigraph is parsed into different graph states. Each graph state is used in communication round. Lines denote strongly-comnected edges, dotted lines denote weakly-connecte ones, and the blue color indicates isolated nodes.
Figure 3:
4.2 MULTIGRAPH PARSING
In Algorithm 2, we parse multigraph 9m into multiple graph states G Graph states are essential to identify the connection status of silos in specific communication round to perform model aggre- gation. In each graph state, our goal is to identify the isolated nodes. During the training, isolated nodes update their weights internally and ignore all weakly-comnected edges that connect to them.
To parse the multigraph into graph states, we first identify the maximum of states multigraph Smax by using the least common multiple (LCM) (Hardy et al., 1979). We then parse the multigraph into Smax states. The first state is always the overlay since we want to make sure all silos have a ease the training. The reminding states parsed there
reliable topology at the beginning is only one connection between two nodes. Using our algorithm, some states will contain isolated nodes. During the training process, only one graph state is used in communication round. Figure illustrates the training process in each communication round using multiple graph states.
4.3 MULTIGRAPH TRAINING
The original DPASGD algorithm (Wang & Joshi, 2018) can not directly used with our multigraph because the learning process will be terminated when it first meets an isolated node. To overcome this problem, we introduce an upgraded version of DPASGD, namely, DPASGD++ (See Algorithm for details). In each communication round, a state graph G" is selected in a sequence that identifies the topology design used for training. We then collect strongly-connected edges the graph edges need to wait for neighbors, while
state G in such way that nodes with the isolated ones can update their models. Formally, the weight in DPASGD++ is updated as:
(Ic EseNt Ac,w; (k h), (k) an E VL, (k) (k)
ifk 0 (mod v 1) IN
(6)
otherwise.
where (A: h) is the index of the considered weights; h is initialized to 0 and is changed when the condition in Eq. 7 is met, i.e.,
h= h if ek-n(i.j)

---

Under review as a conference paper at ICLR 2023
Through Eq. and Eq. 7, at each state, if a silo is not an isolated node, it must wait for the model from its neighbor to update its weight. a silo is an isolated node, it can use the model in its neighbor from the (k h) round to update its weight immediately.
Algorithm 2: Multigraph Parsing
Algorithm DPASGD++ Algorithm
Input: Multigraph 9. (V, Em):
Input: List of multigraph states S; Initial weight w,(0) for each
List edge numbers between silo pairs L.
Output: List of multigraph states
silo i
S = { = E.
Maximum training round K.
Smar f- (C (Hardy et al., 1979)
= 0// states counting
L L; 5m <- NULL
variable
for k: = to K- do
// Establish states
G + Select e-th 9 S
for 8 = = 0 8 Smar do
NULLL/ temporary edge set
c= c c
if c 2 sizeof(S) then
foreach e(t.j) Em do
| c=
if [ ] then
for N <- strongly-
N do
7
Append e(i,j) = into &
else
edges list of using Pm.
L Append e(i,j) = 0 into & if [i.j] = then
1/ The loop below is
parallel
11
C j] = Cli
foreach silo N do for 0 to do
else
[[i, =
11
Wip f Sampling from
local dataset of
Append & into Em
12
w,(k + 1) -- Update
model using Eq. 6.
return S 19 (V, E } by using e.
5 EXPERIMENTS
5.1 EXPERIMENTAL. SETUP
Datasets. We use three datasets in our experiments to evaluate our multigraph topology: Senti- ment140 (Go et al., 2009), iNaturalist (Van Horn et al., 2018), and FEMNIST (Caldas et al., 2018 8). All datasets and the pre-processing process are conducted by following recent works (Wang et al., 2019) and (Marfoq et al., 2020). Details of our experimental setup is in Appendix D.
Network. Following Marfoq et al. (2020), we consider five distributed networks in our experiments: Exodus, Ebone, Géant, Amazon (Miller et al., 2010) and Gaia (Hsich al., 2017). The Exodus, Ebone, and Géant are from the Internet Topology Zoo (Knight et al., 2011). The Amazon and Gaia network are synthetic and are constructed using the geographical locations of the data centers.
Baselines. We compare our multigraph topology with recent state-of-the-art topology designs: STAR (Brandes, 2008), MATCHA (Wang et al., 2019), MATCHA(+) (Marfoq et al., 2020), MST (Prim, 1957), 8-MBST (Marfoq et al., 2020), and RING (Marfoq et al., 2020).
5.2 RESULTS
Table I shows the cycle time of our method in comparison with other recent approaches. This table illustrates that our proposed method significantly reduces the cycle time in all setups with different networks and datasets. In particular, compared to the state-of-the-art RING (Marfoq et al., 2020), our method reduces the cycle time by 2.18. 1.5, 1.74 times in average in the FEMNIST, iNaturalist, Sentiment140 140 dataset, respectively. Our method also clearly outperforms MACHA, MACHA(+), and MST by a large margin. The results confirm that our multigraph with isolated nodes helps to reduce the cycle and training time in federated learning.
7

---

Under review as a conference paper at ICLR 2023
Table Cycle time (ms) comparison between different typologies. () o) indicates our reduced times compared with other methods.
Topology Design
Dataset
Network
STAR
MATCHA
MATCHA(+)
MST
5-MBST
RING
Ours
Gaia
289.8 (L 18.5)
166.4 (L 10.6)
166.4 (L 10.6)
77.2 4.9)
77.2 (4
(4
15.7
FEMNIST
Amazon
98.8 (4 7.3)
57.7 (422)
57.7 (42422
28.7 (4221)
28.7 (4.2.1)
20.3 (4 1.5)
13.6
Géant
132.2 (L 11.0)
(13.)
102.3 8.5)
40.1 (1333)
40.1 (1.33)
27.7 (L3)
12.0
Exodus
265.2 (L 21.9)
211.5 (1.70)
17.5)
74.0
(1
24.7 2.00)
12.1
Ebone
190.9 15.0)
61.5 61.5
112.6 8.9)
60.9 (4 4.8)
60.9 (L
18.5 1.5)
12.7
Gaia
390.9 (.75))
(L.33)
(L.33)
138.1 (..2
138.1 2.0)
118.1 (L 1.7)
68.6
iNaturalist
Amazon
288.1 (L53.5
123.9 1.5)
123.9 1.5)
89.7 (4 1.1)
89.7 (L L.)
81.3 (L 1.0)
81.3
Géant
622.3 9.1) 9.1)
107.9 1.6)
452.5 6.6)
101 (L 1.5)
101 (L 1.5)
109 (1 1.6)
68.1
Exodus
911.9 (L 14.6)
145.7 2.3)
145.3 (1)) (1
145.3 (L 2.3)
103.9 (4 1.7)
62.6
Hhone
901.7 (4 13.9)
122.5 (L 1.9)
(4 8.9)
121.8 (4 1.9)
121.8 (4. 1.9)
95.3 ( 1.5)
64.9
Sentiment 140
Gaia
323.8 (4 10.5)
(4
186 (4 6.0)
96.8 3.11) (L13
76.8 (L 2.5)
31.0
Amazon
(1.22)) 4.446
48.4 (1
48.4 (L 1.4)
40.0 (L 1.1)
35.8
Géant
310.5 (L 10.3)
66.6
222.6 (L
59.7 (4.0))
59.7 2.0)
54.9 (L 1.8)
30.3
Exodus
495.4 (1 17.7)
104.3 (173)
346.3 (1 12.4)
104.1 (4
104.1 (.7)
50.6 1.8)
28.0
Ebone
(44.2(415.3)
81.1 (L.2.8)
262.2 (L
54
80.5 (.))
43.9 () 1.5)
29.1
From Table 1, our multigraph achieves the minimum improvement under the Amazon network in all three datasets. This can be explained that, under the Amazon network, proposed topology does not generate many isolated nodes. Hence, the improvement is limited. Intuitively, when there are no isolated nodes, multigraph will become the overlay, and the cycle time of our multigraph will be equal to the cycle time of the overlay in RING.
5.3 ABLATION STUDY
Convergence Analysis. Figure shows the training loss versus the number of communication rounds and the wall-clock time under Exodus network using the FEMNIST dataset. This figure illustrates that our proposed topology converges faster than other methods while maintaining the model accuracy. We observe the same results in other datasets and network setups. We provide the proof of convergence of our proposed method Appendix
In our method, the maximum number of edges between two nodes in Algorithm mainly affects the number of isolated nodes. This leads trade-off between the model accuracy and cycle time. Table 2 illustrates the effectiveness of this parameter. When = 1, we technically consider there are no weak connections and isolated nodes. Therefore, method uses the original overlay from RING. When t is set higher,
Cycle Time and Accuracy Trade-off.
increase the number of isolated nodes, hence decreasing the cycle time. In practice, too many isolated nodes will limit the model weights to be exchanged between silos. Therefore, models at isolated nodes are biased to their local data and consequently affect the final accuracy.
Multigraph RING vs. Random Strategy. The isolated nodes plays important role in method as we can skip the model aggregation step in the isolated nodes. In practice, we can have trivial solution
create isolated nodes by randomly removing some nodes from the overlay of RING. Table 3 shows the experiment results in two scenarios on FEMNIST dataset and Exodus Network: i) Randomly remove some silos in the overlay of RING, and ii) Remove most inefficient silos (i.c., silos with the longest delay) in the overlay of RING. Note that, in RING, one overlay used all communication rounds. From Table 3, the cycle time reduces significantly when two aforementioned scenarios are applied. However, the accuracy of the model also drops greatly. This experiment shows that although randomly removing some nodes from the overlay of RING a trivial solution, it can not maintain model accuracy. On the other hand, our multigraph not only reduces the cycle time of the model, but also preserves the accuracy. This is because our multigraph skip the aggregation step of the isolated nodes in a communication round. However, in the next round, the delay time of these isolated nodes will be updated, and they can become the normal nodes and contribute to the final model.
8

---

Under review as a conference paper at ICLR 2023
Table 2: Cycle time and accuracy trade- off with different value of t, i.c., the maximum number of edges between two nodes.
Table 3: The cycle time and accuracy of multi- graph vs. RING with different criteria.
#Removed Nodes
Cycle
Methods
Criteria
Acc (%)
Time (ms)
Topology RING
Cycle time (ms)
Acc( %)
Baseline
24.7
71.05
24.7
71.05
23.1
70.63
Randomly
24.7
71.05
remove silos
5
21.7
68.57
3
13.5
71.08
in overlay
10
18.8
64.23
RING
20
13.0
61.2
5
12.1
71.13
Multigraph
22.5
70.71
8
11.9
69.27
Remove most inefBeiint silos
(ours)
5
19.5
68.37
10
11.9
69.27
15.8
63.13
20
11.9
69.27
20
11.2
61.48
30
11.9
69.27
Multigraph (ours)
12.1
71.13
20"
Train Loss
HST
HATCHA?
Train ACC (%)
Cycla Tima
10%
Tannee Time
20
6-HSST RIG
STAR
MATC
30"
30t
30'
15%
13
2003
4000
6000
2003
4000
6000
Capacity (bitts)
Capacity (bit's)
Rounds
Rounds
(a) Homogeneous access link capacity
100
STMI HET
Train ACC (%)
Train Lass
MOST RING
Time
30
M6TC
300
Training
201
MST
SAISTT
186
OU15
100
Time (6)
200
100
400
100
Time (5)
200
10
107 Capacity (bitls)
107
121
Capecity
107
10
(a) Train Loss
Train Accuracy
(b) 10 Gbps Orchestra access capacity
Figure 4: Convergence analysis our multi- graph under communication rounds (top row) and wall-clock time (bottom row). All access links have the same 10 Gbps capacity. The train- ing time is counted until the training process of all setups finishes 6, 400 communication rounds.
Figure 5: The effect of access link capacity cycle time and training time of different ap- proaches. (a) All access links have the same Ghps capacity. (b) One orchestra node has
fixed 10 Gbps access link capacity. All setups
are trained for 6, 400 communication rounds.
Access Link Capacities Analysis. Following Marfoq et al. (2020), we analyse the effect of access link capacity on our multigraph topology. Access link capacity is related the bandwidth when packages are transmitted between silos. Figure 5 shows the results under Exodus network and FEMNIST dataset two scenarios: all access links have the same Gbps capacity and one orchestra node has a fixed 10 Gbps access link capacity. From Figure 5, we can see that our multigraph topology slightly outperforms RING when the link capacity low. However, when the capacity between silos is high, then our method clearly improves over RING. In all setups, our method archives the best cycle time and training time.
CONCLUSION
We proposed a new multigraph topology for cross-silo federated learning. Our method first con- structs the multigraph using the overlay. Different graph states are then parsed from the multigraph and used in each communication round. Our method reduces the cycle time by allowing the isolated nodes in the multigraph to do model aggregation without waiting for other nodes. The intensive experiments on three datasets show that our proposed topology achieves new state-of-the art results in all network and dataset setups.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Aurélien Bellet, Anne-Marie Kermarrec, and Erick Lavoic. D-cliques: Compensating nonidneess in decentralized federated learning with topology. arXiv, 2021.
Alaa Bessadok, Mohamed Ali Mahjoub, and Islem Rekik. Brain multigraph prediction using topology-aware adversarial graph neural network. Medical Image Analysis, 2021.
Ulrik Brandes. On variants shortest-pathh betweenness centrality and their generic computation. Social Networks, 2008.
Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H Brendan McMa- han, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. arXiv, 2018.
Gary Chartrand and Ping Zhang. first course in graph theory. Courier Corporation, 2013.
Jianmin Chen, Xinghao Pan, Rajat Monga, Samy Bengio, and Rafal Jozefowicz. Revisiting dis- tributed synchronous sgd. arXiv, 2016.
Mingzhe Chen, H Vincent Poor, Walid Saad, and Shuguang Cui. Wireless communications for collaborative federated learning. IEEE Communications Magazine, 2020.
Pierre Courtiol, Charles Maussion, Matahi Moarii, Elodie Pronier, Samuel Pilcer, Meriem Sefta,
Pierre Manceron, Sylvain Toldo, Mikhail Zaslavskiy, Nolwenn Le Stang, et al. Deep learning- based classification of mesothelioma improves prediction of patient outcome. Nature medicine, 2019.
Anis Elgabli, Chaouki Ben Issaid, Amrit Singh Bedi, Ketan Rajawat, Mehdi Bennis, and Vaneet Aggarwal. Fednew: A communication-effiiie and srivacy-preservngg newton-type method for federated learning. In ICML, 2022.
Avishek Ghosh, Jichan Chung, Dong Yin, and Kannan Ranchandran. An efficient framework for clustered federated learning. In NIPS, 2020.
Alan Gibbons. Algorithmic graph theory. Cambridge university press, 1985.
Alec Go, Richa Bhayani, and Lei Huang. Twitter sentiment classification using distant supervision. CS224N project report, Stanford, 2009.
Xuan Gong, Abhishek Sharma, Srikrishna Karanam, Ziyan Wu, Terrence Chen, David Doermann, and Arun Innanje. Ensemble attention distillation for privacy-preservie federated learning. In ICCV, 2021.
Godfrey Harold Hardy, Edward Maitland Wright, et al. An introduction to the theory of numbers. Oxford university press. 1979.
Chaoyang He, Conghui Tan, Hanlin Tang, Shuang Qiu, and Liu. Central server free federated learning over single-sided trust social networks. arXiv, 2019.
Lie He, An Bian, and Martin Jaggi. Cola: Decentralized linear learning. NIPS, 2018.
Junyuan Hong, Haotao Wang, Zhangyang Wang, and Jiayu Zhou. Efficient split-mix federated learning for on-demand and in-situ customization. In ICLR, 2021.
Kevin Hsieh, Aaron Harlap, Nandita Vijaykumar, Dimitris Konomis, Gregory Ganger, Phillip Gibbons, and Onur Mutlu. Gaia: Geo-distributed machine learning approaching lan speeds. In USENIX Symposium on Networked Systems Design and Implementation, 2017.
Yan Huang, Ying Sun, Zehan Zhu, Changzhi Yan, and Jinming Xu. Tackling data heterogeneity: A new unified framework for decentralized sgd with sample-induced topology. ICML, 2022.
Martin Jaggi, Virginia Smith, Martin Takác, Jonathan Terhorst, Sanjay Krishnan, Thomas Hofmann, and Michael I Jordan. Communication--ffcciee distributed dual coordinate ascent. In NIPS, 2014.
10

---

Under review as a conference paper at ICLR 2023
Zhanhong Jiang, Aditya Balu, Chinmay Hegde, and Soumik Sarkar. Collaborative deep learning in fixed topology networks. NIPS, 2017.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. arXiv, 2019.
Jiawen Kang, Zehui Xiong. Dusit Niyato, Han Yu, Ying-Chang Liang, and Dong In Kim. Incentive design for efficient federated learning mobile networks: contract theory approach. In IEEE VTS Asia Pacific Wireless Communications Symposium, 2019.
Zhao Kang, Guoxin Shi, Shudong Huang, Wenyu Chen, Xiaorong Pu, Joey Tianyi Zhou, and Zenglin Xu. Multi-graph fusion for multi-view spectral clustering. Knowledge- Based Systems, 2020.
Can Karakus, Yifan Sun, Suhas Diggavi, and Wotao Yin. Straggler mitigation in distributed opti- mization through data encoding. NIPS, 2017.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In ICML, 2020.
Cao Ke-xing, Li Zhao-xing, Li Xin, and Lv Zhi-han. Weak connection edges independent discrimi- nant of rapid spanning tree recommendation of social network community. International Journal of Multimedia and Ubiquitous Engineering, 2016.
Simon Knight, Hung X Nguyen, Nickolas Falkner, Rhys Bowden, and Matthew Roughan. The internet topology zoo. IEEE Journal on Selected Areas in Communications, 2011.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. unified theory of decentralized sgd with changing topology and local updates. In ICML, 2020.
Jakub Konečný, Brendan McMahan, and Daniel Ramage. Federated optimization: Distributed opti- mization beyond the datacenter. arXiv, 2015.
Jakub Konecný, H Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated optimization: Distributed machine learning for on-device intelligence. CoRR, 2016.
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv, 2016.
Chengxi Li, Gang Li, and Pramod K Varshney. Decentralized federated learning via mutual knowl- edge transfer. IEEE Internet of Thingy Journal, 2021a.
Qinbin Li, Bingsheng He, and Dawn Song. Model-contrastive federated learning. In CVPR, 2021b.
Songze Li, Seyed Mohammadreza Mousavi Kalan, A Salman Avestimehr, and Mahdi Soltanolkotabi. Near-optimal straggler mitigation for distributed gradient methods. In JEEE International Parallel and Distributed Processing Symposium Workshops, 2018:t 8a.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 2020a.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogencous networks. In MLSys Conference, 2020b.
Xiang Li, Wenhao Yang. Shusen Wang, and Zhihua Zhang. Communication-efficine local decen- tralized sgd methods. arXiv, 2019.
Youjie Li, Mingchao Yu, Songze Li, Salman Avestimehr, Nam Sung Kim, and Alexander Schwing. Pipe-sgd: A decentralized pipelined sgd framework for distributed deep net training. NIPS, 2018b.

---

Under review as a conference paper at ICLR 2023
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsich, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. arXiv, 2017.
Xiangru Lian, Wei Zhang. Ce Zhang, and Ji Liu. Asynchronous decentralized parallel stochastic gradient descent. In ICMI., 2018.
Chang Liu, Chenfei Lou, Runzhong Wang, Alan Yuhan Xi, Li Shen, and Junchi Yan. Deep neural network fusion via graph matching with applications model ensemble and federated learning. In ICML, 2022.
Quande Liu, Cheng Chen, Jing Qin, Qi Dou, and Pheng-Ann Heng. Feddg: Federated domain gen- eralization on medical image segmentation via episodic learning in continuous frequency space. In CVPR, 2021.
Ye Liu, Lifang He, Bokai Cao, S Yu Philip, Ann B Ragin, and Alex D Leow. Multi-view multi-graph embedding for brain network clustering analysis. In AAAI, 2018.
Dongsheng Luo, Jingchao Ni, Suhang Wang, Yuchen Bian, Xiong Yu, and Xiang Zhang. Deep multi-graph clustering via attentive tross-graph association. In International Conference on Web Search and Data Mining, 2020.
Mingqi Lv, Zhaoxiong Hong, Ling Chen, Tieming Chen, Tiantian Zhu, and Shouling Ji. Temporal multi-graph convolutional network for traffic flow prediction. IEEE Transactions Intelligent Transportation Systems, 2020.
Chenxin Ma, Virginia Smith, Martin Jaggi, Michael Jordan, Peter Richtárik, and Martin Takác. Adding vs. averaging in distributed primal-dual optimization. In ICML, 2015.
Xiaosong Ma, Jie Zhang. Song Guo, and Wenchao Xu. Layer-wised model aggregation for person- alized federated learning. In CVPR, 2022.
Othmane Marfoq, Chuan Xu, Giovanni Neglia, and Richard Vidal. Throughput-optimal topology design for cross-silo federated learning. In NIPS, 2020.
Othmane Marfoq, Giovanni Neglia, Aurélien Bellet, Laetitia Kameni, and Richard Vidal. Federated multi-task learning under mixture of distributions. In NIPS, 2021.
Sebastian Martschat. Multigraph clustering for unsupervised coreference resolution. In Association for Computational Linguistics Proceedings of the Student Research Workshop, 2013.
McMahan and Ramage. Google ai blog: Federated learning: Collaborative machine learning without centralized training data, 2017.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficeent learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, 2017.
Brendan McMahan, Eider Moore, Daniel Ramage, and Blaise Agüera y Arcas. Federated learning of deep networks using model averaging. arXiv, 2016.
Frederic P. Miller, Agnes F, Vandome, and John McBrewster. Amazon Web Services. Alpha Press, 2010.
Jérôme Monnot, Vangelis Th Paschos, and Sophie Toulouse. Approximation algorithms for the traveling salesman problem. Mathematical methods of operations research, 2003.
Angelia Nedić and Alex Olshevsky. Distributed optimization over time-varying directed graphs. IEEE Transactions Automatic Control, 2014.
Angelia Nedić, Alex Olshevsky, and Michael Rabbat. Network topology and communication- computation tradeoffs in decentralized optimization. IEEF, 2018.
12

---

Under review as a conference paper at ICLR 2023
Giovanni Neglia, Gianmarco Calbi, Don Towsley, and Gayane Vardoyan. The role of network topology for distributed machine learning. In IEEE INFOCOM Conference on Computer Com- munications, 2019.
Anh Nguyen, Tuong Do, Minh Tran, Binh X Nguyen, Chien Duong, Tu Phan, Erman Tjiputra, and Quang D Tran. Deep federated learning for autonomous driving. arXiv, 2021.
Olusola Odeyomi and Gergely Zaruba. Differentially-private federated learning with long-term budget constraints using online lagrangian descent. In IEEE World Al loT Congress, 2021.
Yi Ouyang, Bin Guo, Xing Tang, Xiuqiang He, Jian Xiong, and Zhiwen Yu. Learning cross- domain representation with mulli-graph neural network. arXiv, 2019.
Jung Wuk Park, Dong-Jun Han, Minseok Choi, and Jaekyun Moon. Sageflow: Robust federated learning against both stragglers and adversaries. NIPS, 2021.
Robert Clay Prim. Shortest connection networks and some generalizations. The Bell System Tech- nical Journal, 1957.
Liangqiong Qu, Yuyin Zhou, Paul Pu Liang, Yingda Xia, Feifei Wang, Ehsan Adeli, Li Fei-Fei, and Daniel Rubin. Rethinking architecture design for tackling data heterogeneity in federated learning. In CVPR, 2022.
Shai Shalev-Shwarz and Tong Zhang. Stochastic dual coordinate ascent methods for regularized loss minimization. Journal of Machine Learning Research, 2013.
Zebang Shen, Aryan Mokhtari, Tengfei Zhou, Peilin Zhao, and Hui Qian. Towards more efficient stochastic decentralized learning: Faster convergence and sparse communication. In ICML, 2018.
Geet Shingi. A federated learning based approach for loan defaults prediction. In ICDMW, 2020.
Virginia Smith, Simone Forte, Ma Chenxin, Martin Takáč, Michael Jordan, and Martin Jaggi. Cocoa: general framework for communication-effiieen distributed optimization. Journal of Machine Learning Research, 2018.
Maja Stikic, Diane Larlus, and Bernt Schiele. Multi-graph based semi-supervised learning for tivity recognition. In International Symposium on Wearable Computers, 2009.
Hao Tang, Guoshuai Zhao, Xuxiao Bu, and Xueming Qian. Dynamic evolution of multi-graph based collaborative filtering for recommendation systems. Knowledge-Basse Systems, 2021.
Grant Van Horn, Oisin Mac Aodha, Yang Song. Yin Cui, Chen Sun, Alex Shepard, Hartwig Adam, Pietro Perona, and Serge Belongie. The inaturalist species classification and detection datasct. In CVPR, 2018.
Thijs Vogels, Lie Hc, Anastasiaa Koloskova, Sai Pranceth Karimireddy, Tao Lin, Scbastian U Stich, and Martin Jaggi. Relaysum for decentralized deep learning heterogeneous data. NIPS, 2021.
Richard Walker. Implementing discrete mathematics: combinatorics and graph theory with mathe- matica. The Mathematical Gazette, 1992.
Jianyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of communication-effiiinn sgd algorithms. In ICLRW, 2018.
Jianyu Wang, Anit Kumar Sahu, Zhouyi Yang, Gauri Joshi, and Soummya Kar. Matcha: Speeding up decentralized sgd via matching decomposition sampling. In Indian Control Conference, 2019.
Tianyu Wu, Kun Yuan, Qing Ling, Wotao Yin, and Ali H Sayed. Decentralized consensus optimiza- tion with asynchrony and delays. IEEE Transactions on Signal and Information Processing over Networks, 2017.
Jie Xu, Benjamin S Glicksberg, Chang Su. Peter Walker, Jiang Bian, and Fei Wang. Federated learning for healthcare informaties. Healthcare Informatics Research, 2021.
13

---

Under review as a conference paper at ICLR 2023
Haibo Yang, Minghong Fang, and Jia Liu. Achieving linear speedup with partial worker participa- tion in non-iid federated learning. ICLR, 2021.
Tianbao Yang, Shenghuo Zhu, Rong Jin, and Yuanqing Lin. Analysis of distributed stochastic dual coordinate ascent. arXiv, 2013.
Ke Zhang, Carl Yang, Xiaoxiao Li, Lichao Sun, and Siu Ming Yiu. Subgraph federated learning with missing neighbor generation. NIPS, 2021a.
Lin Zhang, Yong Luo. Yan Bai, Bo Du, and Ling- Yu Duan. Federated learning for non-iid data via unified feature learning and optimization objective alignment. ICCV, 2021b.
Lin Zhang, Li Shen, Liang Ding, Dacheng Tao, and Ling-Ya Yu Duan. Fine-tuning global model via data-free knowledge distillation for non-iid federated learning. In CVPR, 2022.
Zijian Zhang, Shuai Wang, Yuncong Hong, Liangkai Zhou, and Hao. Distributed dynamic map fusion via federated learning for intelligent networked vehicles. In ICRA, 2021c
Bo-Wei Zhao, Zhu-Hong You, Lun Hu, Leon Wong, Ba-Ya Ji, and Ping Zhang. A multi-graph deep learning model for predicting drug-disease associations. International Conference on Intelligent Computing. 2021.
Kun Zhu, Shuai Zhang, Jiusheng Li, Di Zhou, Hua Dai, and Zeqian Hu. Spatiotemporal multi-graph convolutional networks with synthetic data for traffic volume forecasting. Expert Systems with Applications, 2021a.
Ligeng Zhu, Hongzhou Lin, Yao Lu, Yujun Lin, and Song Han. Delayed gradient averaging: Toler- ate the communication latency for federated learning. NIPS, 2021b.
14

---

Under review as a conference paper at ICLR 2023
SUMMARY OF THE APPENDIX
This appendix contains additional materials for the paper "Multigraph Topology Design for Cross- Silo Federated Learning". We include mathematical proofs, experimental setup details, additional results, and further discussions. The appendix organized as follows:
Section A provides the theoretical proofs to show that our DPASGD++ algoritt converges in all cases.
Section illustrates the wall-clock time comparison between our DPASGD++ algorithm and other optimizers.
Section C discusses the complexity of our proposed Algorithm 1, Algorithm 2, and Algo- rithm 3 in terms of both theory and practice.
Section D provides detailed experiment setups in our experiments.
Section includes additional experimental results, including accuracy analysis (Sec- tion I),,, and additional results other datasets (Section E.2)
Section discusses relevant issues to our work, such as privacy concerns, limitations, and broader impact.
A CONVERGENCE ANALYSIS
The decentralized periodic averaging stochastic gradient descent (DPASGD) (Wang & Joshi, 2018) a popular algorithm for training federated learning setup since allows local-update in each silo during the learning process. For the convenience, re-write the equation for updating the weight of silo i each training round of DPASGD updated as follows:
[EEN; ue W (k), w. (k) - axt Eh VL; W: (k), (1) E (k)
if (mod 1),
w; (A: 1)
otherwise.
where b is the batch size; i.j denote the siloes, is the number of local updates, 0g is potentially varying learning rate at k-th round, A E NxN is a consensus matrix with non-negative weights, and N the in-neighbors set that silo has the connection to.
The original DPASGD algorithm can not be directly used with our multigraph because it was not designed to handle the isolated node. We have proposed the DPASGD++ algorithm (Algorithm 3) to overcome this problem.
We next theoretically show in the following propositions that our proposed DPASGD++ is general case for DPASGD, and will become the original DPASGD with some certain conditions. There- fore, our DPASGD+ will ensure the convergence the federated training process when using our multigraph topology.
Proposition 1. Assuming that all states of multigraph contains only strongly-connected edge, ie.. e(i,j) = 1, vii E 9m- Then, DPASGD++ described in Eq. 6 becomes the original DPASGD (Wang & Joshi, 2018).
Proof. In deed, e((,j) 1,V(i.)) E Sm. from Eq. 7 and Eq. 6 we have 0, and then DPASGD++ becomes the original DPASGD (Wang & Joshi, 2018).
O
Proposition Assuming that all states of multigraph contains only weukly-connected edge (all nodes are isolated), i.e. e(i,j) O, v(i.j) Gm and |N*+| 1, 1i E Gm- Then, DPASGD+ becomes DPASGD (Wang & Joshi, 2018) when DPASGD has u - oc, and we have
w; (k: +1) = w; (k)) akk b h=l
1
V w: (k) (B))
(9)
15

---

Under review as a conference paper at ICLR 2023
Proof. Given the assumption that | 1, Vi Ims by combining this with Eq. 6, and noting that the first case in Eq. is violated, we obtain
Wi (A: + 1) = w; (k: Otk
Vi
Wi w. (k), (h (k))
4=1
B WALL-CLOCK TIME ILLUSTRATION
Figure illustrates the wall-lock time that needs to finish the corresponding communication round between our DPASGD++ and other methods. We can see that by utilizing the isolated node, our DPASGD++ takes less time for computation compared to other methods.
211
22
23
24
35
Worker 1
Worker 3
Worker
Worker 5
(a) Distributed synchronous SGD (D-SGD) (Chen et al., 2016)
Wall clock time
21
42
344
26
27
31g
Worker
Worker
Worker
Aun:
24
(b) Cooperative SGD (DPASGD) (Wang & Joshi, 2018)
clock
40g
34
2gg
28
2100 211
R13
Worker
Laokute
Worker
Aus: V. (Test only)
Our introduced DPASGD++
Figure 6: Comparison in wall-clock time between three different learning schemes, including Dis- tributed synchronous SGD (Chen al., 2016), Cooperative DPASGD (Wang & Joshi, 2018), and our introduced DPASGD++.
C ALGORITHM COMPLEXITY
It is trivial to that the complexity of proposed Algorithm 1, Algorithm 2, and Algorithm On?)). In practice, since the cross-silo federated learning setting has only a few hundred silos (n 500) (Kairouz et al., 2019), the time to execute algorithms is just a tiny fraction of training
16

---

Under review as a conference paper at ICLR 2023
time. Therefore, proposed topology still can significantly reduce the overall wall-clock training time.
D EXPERIMENT SETUP
Network. Table 4 shows the statistic of five distributed networks in our experiments: Exodus, Ebone, Géant, Amazon (Miller al., 2010) and Gaia (Hsieh al., 2017). The Exodus, Ebone, and Géant are from the Internet Topology Zoo (Knight et al., 2011). The Amazon and Gaia network are synthetic networks that are constructed using the geographical locations of the data centers.
Network
#Silos
#Maximum Links
Gaia (Hsich et al., 2017)
11
55
Amazon (Miller et al., 2010)
22
231
Géant (Knight et al., 2011)
40
61
Exodus (Knight al., 101
79
147
Ebone (Knight al., 2011)
87
161
Table 4: The network setups in experiments.
Datasets. Table 5 shows the dataset setups in details. We three standard federated datasets in our experiments, including: centiment140 (Caldas et al., 2018), iNaturalist (Van Horn et al., 2018), and FEMNIST (Caldas al., 2018). All datasets and the pre-processing process are conducted by following Marfoq et al. (2020).
Dataset
FEMNIST
Sentiment140
iNaturalist
Task
Image Classification
Sentiment Analysis
Large-scale Image Classification
#Samples
805M
1,600M
450M
Model
Marfoq' CNN
LSTT
ResNet18
#Params
1,2M
4,8M
1 11,2M
Batch size
128
512
16
Model size
4.62
18.38
42.88
Table 5: Dataset statistic and model details in experiments. The model size is in Mbits.
Implementation. We PyTorch with the MPI backend in implementation. The maximum number of edges between two nodes / is set to in all experiments. Our source code and trained models will be released.
Hardware Setup. Since measuring the cycle time is crucial to compare the effectiveness of all topologies in practice, we and report the cycle time all baselines and our method on the same NVIDIA Tesla P100 16Gb GPUs. No overclocking is used.
E ADDITIONAL EXPERIMENT RESULTS
E. ACCURACY ANALYSIS
In federated learning, improving the model accuracy is not the main focus of topology designing methods. However, preserving the accuracy also important to ensure model convergence. Table shows the accuracy of different topologies after 6, 400 communication training rounds the FEM- NIST dataset. This table illustrates that our proposed method achieves competitive results with other topology designs.
17

---

Under review as a conference paper at ICLR 2023
Table 6: Accuracy comparison between different topologies. The experiment is conducted using the FEMNIST dataset. The accuracy is reported after 6, 400 communication rounds in all methods.
Topology
Network
MATCHA(+)
MST
3-MBST
RING
Ours
Gaia
69.09
68.43
68.86
68.95
68.2
68.45
Amazon
69.59
69.06
69.65
70.37
69.78
69.63
Géant
68.91
63.57
69.44
68.94
69.3
68.98
Ebone 69.66
64.48
71.91
70.62
70.29
70.23
Exodus
70.14
67.21
72.36
72.19
71.05
71.13
STAI
STAR
WATIOA"
0.6
MATCHAA
0.6
Train Loss
VST
6-MBST
VIST
G-MOST RING
Validate ACC
RING
0.4
GTAR
Validate
0.4
STAR NATIMA
OURS
NATCHA
NST
0.2
6 6-MBST RIN OURS
RIN
OURS
2006
4000
6000
2000
4000
6000
2000
4008
6000
2000
4000
6000
Rounds
Rounds
Rounds
Rounds
STAR
5TMR
MATCHA'
0.0
MATCHA
0.6
Thain loss
MBST
Validate Acc
STAR
Validate
STAA
HATOMA"
MATCHAT
Train
HST
B-MBST
I-MEST
200
400
100
200
300
400
200
300
400
Time (5)
Time (5)
Time (s)
Time (s)
(a) Train Loss
(b) Train Ace
(c) Validate Loss
(d) Validate Acc
Figure 7: The comparison of our multigraph and other methods on the convergence w.r.. communi- cation rounds (top row) and wall-clock time (bottom row). Amazon network and FEMNIST dataset used. The wall-clock time is counted until the training process of all setups reaches 6, 000 com- munication rounds. Best viewed in color.
E.2 ADDITIONAL RESULTS
Figure 7, Figure 8, and Figure show more experiment results of our multigraph and other methods on different datasets and network setups. These figures show that our multigraph achieves state-of- the-art accuracy compared to other methods (top row) while significantly reducing the total wall- clock time (bottom row).
F FURTHER DISCUSSION
Limitations. Since our multigraph designed based on RING (Marfoq et al., 2020) overlay, our method inherits both the strengths and weaknesses of RING. We can see that the "lower bound" of our multigraph is the overlay of RING when there are no isolated nodes. In this case, all states in our multigraph are the input overlay. Hence, there is no improvement. Furthermore, compared to RING, our multigraph is more sensitive
low bandwidth capacity setup (Figure 5).
Privacy Concerns. The privacy of federated learning has been discussed in many papers (Li et al., 2021a; Kairouz al., 2019). Generally, any federated learning topologies (such as ours) can be ac- companied by any privacy preservation methods (Marfoq et al., 2020). Since method focuses optimizing topology, studying the privacy concern not our main focus. In practice, our proposed topology potentially enhance privacy it reduces the data exchanges between nodes.
Broader Impacts. Decentralized inference mechanisms are a workable alternative that balances utility with erucial normative values like privacy, transparency, and accountability. Given the ease of access to sensitive data, large-scale centralized data sources are not feasible to uphold the best interests and privacy of the users. We hope that using our proposed topology, reduce the
18

---

Under review as a conference paper at ICLR 2023
STAR
0.8
STAR
0.4
Train Locs
E-MBST
0.4
6-MSST
Vol Vollddte ACC
RING
ST4R
Validate
RIN
ST64
CUPS
OURS
0.0
RPG
RING
OURS
0.0
OURS
300
1000
1500
500
1,000
1500
500
1000
1500
500
1000
1500
Rounds
Rounds
Rounds
S16A
0.6
STAR
Train Loos
Vol Polldots Acc
RING CURS
Acc
STAR
Validate
STAA
6.2
NATCHA
OURS
MST
KATCHA"
0.MB51
0.0
100
200
300
100
200
300
200
200
300
100
200
300
Time (s)
Time (5)
Time (s)
Time (5)
(a) Train Loss
(b) Train Ace
(c) Validate Loss
(d) Validate Ace
Figure& 8: The comparison of our multigraph and other methods on the convergence w.r.t. communi- cation rounds (top row) and wall-clock time (bottom row). Exodus network and iNaturalist dataset are used. The wall-clock time is counted until the training process of all setups reaches 1, 500 com- munication rounds. Best viewed in color.
STAR
STAR
0.69
Moli Ha*
0.6
0 0.00
NA. CHA
Train Loge
RMC
Train Ace
RNG
STAR MATTHA
0.67
CUTS
0:67
OUTS
Velicitte
S
0.60
0.66
BNG OUDS
0.0
5200
10000
11000
20000
1000
10:00
15000
20000
5000
10000
15000
23020
Rounds
Rounds
Rounds
Rounds
STAR
0.69
0.6
0.000
0.6
0.00
HEST
Train Ace
0.68
MATOHA
Valiateeee
MST
NST
0.68
0.60
0.2
3 HRSTT
0URS
0.65
500
1000
1500
2000
500
1,000
1500
2000
500
1000
1500
2000
500
1000
1500
2000
(s)
(a) Train Loss
(b) Train Acc
(c) Validate Loss
(d) Validate Acc
The comparison of our multigraph and other methods on the convergence w.r.t. commu- nication rounds (top row) and wall-clock time (bottom row). Exodus network and Sentiment 40 dataset are used. The wall-clock time counted until the training process of all setups reaches 20, 000 communication rounds. Best viewed in color.
Figure 9:
training time of the whole network, and consequently would bring direct benefits in real-world applications such as saving energy when training model, reducing waiting time, and potentially reducing the privacy breach when exchanging data between silos.
19


Reviews:
[{"review_id": "jKOp7reRPXg", "reviewer": "Reviewer_rd7C", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed a new multigraph topology for cross-silo federated learning in a decentralized network. Specifically, the proposed method extends the overlay graph with weak connections based on the delay time and improved DPASGD algorithm to process isolated nodes for time reduction.", "summary_of_the_review": "The paper is organized very well. The paper’s targeting problem is very scarce, thus the contribution to the federated learning community is limited. The novelty is sourced from the combination of multigraph and federated learning. ", "strength_and_weaknesses": "Strength. \n1. Using multigraph topology in federated learning is a novel idea.\n2. This paper is well written.\n\nWeaknesses:\n1. The targeting scenario is very narrow. It requires a cross-silo federated setting with a peer-to-peer network and a graph topology. \n2.  It is unclear In the main result of table 1, accuracy results should also be provided to show that the proposed algorithm could achieve comparable accuracy with less training time.\n3. Below paper could be discussed in the related work. It is a similar idea to graph-based aggregation on federated learning [1]. \n\n[1] Personalized Federated Learning with A Graph\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "i5uGHD32P-x", "reviewer": "Reviewer_7Rwz", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies how to speed up cross-silo federated learning, in which different silos need to have multiple peer-to-peer communication/synchronization at each round. Following previous works, this paper proposes a new efficient communication topology based on multigraph. Extensive experiments on multiple datasets validate the effectiveness of the proposed method.", "summary_of_the_review": "I like the proposed algorithm and it seems that it can be an important baseline in the future. But I do think the current draft is not ready to be published. Both the key insights and technical details are incomplete and unclear. The authors are supposed to perform more studies around the proposed algorithm. More details can be found in the weakness section.", "strength_and_weaknesses": "**Strength**\n- The proposed topology design based on multigraphs is novel. It may have great impact on future research on this topic.\n- The experiments are kind of comprehensive, which include three different datasets and five different communication networks.\n\n\n**Weakness**\n- Clarity on key insights\n    - While I feel the proposed algorithm in this paper looks interesting and novel, and the experimental results are promising, I found that it is hard to get the key ideas behind the algorithm. If I understand correctly, the benefits of the proposed algorithm lie in two aspects: (1) at each round, the activated graph is just a subgraph of the overlay, thus there are less communication links; (2) for the isolated nodes, we will not let them continue performing local training. Instead, they will average with the latest available neighbor models. This can help to improve the convergence. Unfortunately, these two benefits are not clearly stated in the paper. And I believe there might be more benefits hidden in the paper. Even for an expert, it may be difficult to effectively get what are the key insights behind the algorithm.\n- Clarity on technical details: I found that the authors may omit a lot of technical details or explanations.\n    - It is unclear to readers how you derived equation 4. It is hard to interpret it without any explanations. For example, what does it mean by \"$d_k(i,j) = d_k(i,j)$\" on the first line. Do you update $d_k(i,j)$ based on its previous values at $k-1$, $k-2$?\n    - The authors mentioned that in order to overcome the problem of DPASGD, they propose some new techniques. However, how and why these techniques can overcome the problem are unclear.\n    - Related to the above point, it would be better to clearly state why DPASGD has the problem. The authors mentioned that DPASGD will terminate when a node is isolated. As far as I know, this is not true, as long as the expected graph over all rounds is connected. Then, DPASGD won't have the divergence problem.\n    - How do you measure the cycle time? If you want to measure the real time, then you must have the same number of machines as the number of silos. On some networks, there is about 80 silos. Does that mean you ran experiments on a cluster of 80 machines? If not, the reported numbers will be just simulation results. The authors should provide full details on how they simulate the numbers.\n    - It is unclear how you implemented the MATCHA algorithm. Basically, MATCHA has a hyper-parameter to tune the communication time per round. How did you choose this hyper-parameter?\n- Incomplete study: I felt there are still many questions remaining. The authors are supposed to address them in order to make the paper complete and self-contained.\n   - The authors just stated the steps of the multi-graph parsing algorithm. But we should also know its parsing properties. For example, as the authors mentioned, \"Using our algorithm, some states will contain isolated nodes.\" It would be better to show either theoretically or empirically how the exact number of states have isolated nodes in different type of graphs. Does this number depend on the number of edges, maximal degree, or something else? Answering these questions would help us to better understand the benefits of the proposed algorithm and when is proper to apply it.\n   - Similarly, we readers know little things about the DPASGD++ algorithm. The authors claim that it ensures model convergence. However, this claim is not supported in the main paper. Ideally, one should have a convergence analysis to support this claim. The authors provided one in the Appendix, which is very weak. It says DPASGD++ is equivalent to DPASGD when all states are strong edges and all states are weak edges. This conclusion is obvious and is not interesting. If it is equivalent to DPASGD, then there is no need to have a new algorithm. Therefore, the interesting part is something in between. What happens when some states are strong and others are weak. Without a convergence analysis, it is possible that DPASGD++ can just diverge in some cases.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "MrLE3Lbm74y", "reviewer": "Reviewer_QFKN", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers designing dynamic network topologies to improve the training time and performance of the cross silo FL training. The authors propose an algorithm and verify its effectiveness through empirical evaluation.", "summary_of_the_review": "Overall, the presentation of the paper makes it difficult to comprehensively judge the quality of the paper and the proposed method. In order to improve the paper, I strongly suggest the authors improve the presentation, make the paper more self-contained and give more details about the algorithm designs, limitations and the interplay between the optimization and dynamic topology. Moreover, a more rigorous experimental section is also needed.", "strength_and_weaknesses": "- Strength: This is an interesting problem, especially the dynamic topology part which is under-explored.\n- Weakness: \n   - The paper is poorly written and to some extent not self contained. Many of the pieces necessary for developing the method/algorithm are defined or presented without context. This makes the paper difficult to follow. As an example I was not able to follow why eq. 4 holds and the explanations around it was definitely not sufficient. \n  - In algorithm 1, it is not clear what is the exact motivation behind the algorithm, what are the constraints the extracted topologies need to satisfy, and how do the authors know that it does exactly what is designed to do. It is presented just as is without much context. The same is also true (to a lesser extent) about Algorithm 2.\n  - It is not clear if such dynamic topological changes would still allow the overall optimization algorithm to converge to a unified solution over the network? In fact, the interplay between the optimization method and dynamical topology which seems to be an important aspect of such algorithms is not even discussed in the paper. How do the algorithms scale with the number of participating silos? do global models converge? what are the conditions needed for the model to converge correctly? And are they satisfied by the proposed algorithms?\n  - In the experiments, the results only show the train loss and train accuracy, while for ML models the test loss and test accuracy are more important. Also, regarding the distributed training procedure it is not clear what train loss and train accuracies are reported? Are these measured at the nodes (with local models) and then averaged? or are they with the global model? Why there are no error bars reported? Are the results averaged over multiple runs?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject