FedGCN: Convergence-Communication Tradeoffs in Federated Training of Graph Convolutional Networks
Authors: Yuhang Yao
Weizhao Jin
Srivatsan Ravi
Carlee Joe-Wong
Venue: NeurIPS 2023 poster (2023)
Keywords: Federated Graph Learning;
TL;DR: Federated training of graph convolutional networks with high accuracy and super low communication cost

Abstract: Methods for training models on graphs distributed across multiple clients have recently grown in popularity, due to the size of these graphs as well as regulations on keeping data where it is generated. However, the cross-client edges naturally exist among clients. Thus, distributed methods for training a model on a single graph incur either significant communication overhead between clients or a loss of available information to the training. We introduce the Federated Graph Convolutional Network (FedGCN) algorithm, which uses federated learning to train GCN models for semi-supervised node classification with fast convergence and little communication. Compared to prior methods that require extra communication among clients at each training round, FedGCN clients only communicate with the central server in one pre-training step, greatly reducing communication costs and allowing the use of homomorphic encryption to further enhance privacy. We theoretically analyze the tradeoff between FedGCN's convergence rate and communication cost under different data distributions. Experimental results show that our FedGCN algorithm achieves better model accuracy with 51.7\% faster convergence on average and at least 100$\times$ less communication compared to prior work.

FedGCN: Convergene--oommuncttion Tradeoffs in Federated Training of Graph Convolutional Networks
Yuhang Yao Carnegie Mellon University yuhangya@andrew. cmu. edu
Weizhao Jin University of Southern California reizhaoj@usc. edu
Srivatsan Ravi University of Southern California sravi@isi.o
Carlee Joe- Joe-Wong
Carnegie Mellon University cj cjoevong@andrew. cmu. edu
Abstract
Methods for training models on graphs distributed across multiple clients have recently grown in popularity, due the size of these graphs well regulations on keeping data where is generated. However, the cross-client edges naturally exist among clients. Thus, distributed methods for training model on single graph incur either significant communication overhead between clients or a loss available information the training. We introduce the Federated Graph Convolu- tional Network (FedGCN) algorithm, which uses federated learning to train GCN models for semi-supervised node classification with fast convergence and little communication. Compared to prior methods that require extra communication among clients each training round, FedGCN clients only communicate with the central server in one pre-training step, greatly reducing communication costs and allowing the of homomorphic encryption further enhance privacy, We theoretically analyze the tradeoff between FedGCN's convergence rate and commu- nication cost under different data distributions. Experimental results show that our FedGCN algorithm achieves better model accuracy with 51.7% faster convergence on average and least 100x less communication compared to prior work!]
Introduction
Graph convolutional networks (GCNs) have been widely used for applications ranging from fake news detection in social networks anomaly detection sensor networks (Benamira et al, 2019 Zhang al.) 2020). This data, however, can be too large store single server, e.g., records of billions of users' website visits. Strict data protection regulations such as the General Data Protection Regulation (GDPR) in Europe and Payment Aggregators and Payment Gateways (PAPG) in India also require that private data only be stored in local clients. In non-graph settings, federated learning has recently shown promise for training models on data that kept at multiple clients (Zhao al. 2018 |ang et al. (021). Some papers have proposed federated training of GCNs (He et al.) 202 la Zhang al.] 2021). Typically, these consider a framework in which each client has access a subset of a large graph, and clients iteratively compute local updates to semi-supervised model on their local subgraphs, which are occasionally aggregated a central server. Figure [left) illustrates the federated node classification task of predicting unknown labels of local nodes in each client.
CCode in
cow/ htal:yyyyyyoFedGeee
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Server
Client k -1
Global GNN
Client k +
L.d.
Local Graph
Local Graph
Client lc
Local Graph
non-i.id.
Cross-client Edges
Cross-client Edges
Figure I: Federated GCN training schematic for node classification, with colors indicating the known labels of some nodes. Nodes in graph (shown as circles) are distributed across clients, and dashed lines show cross-client edges between nodes at different clients. Arrows in the left figure indicate that each client can exchange updates with central server during the training process to predict the unknown labels of the grey nodes in each client. At right, we show a graph with i.i.d (top) and non-i.i.d (bottom) data distribution across clients, which affects the number of cross-client edges.
The main challenge of applying federated learning to GCN training tasks involving single large graph is that cross-client edges exist among clients. In Figure [ for example, we see that some edges will connect nodes different clients. We refer to these "cross-client edges".
Such cross-client edges typically are stored in both clients. Intuitively, this is due to the fact that edges are generated when nodes clients interact with each other. Thus, the interaction record, though not personal node characteristics, is then naturally stored at both nodes, i.e., in both clients. For example, graph may represent buying behaviors (edges) that exist between users (nodes) in two countries (clients). Users in one country want to buy items in another country. The records of these transactions between users in different countries (i.e., the cross-client edges) are then stored in both clients. Due to the General Data Protection Regulation, however, sensitive user information (node features including name, zip code, gender, birthday, credit card number, email address, etc.) cannot be stored in another country. Yet these cross-client edges cannot be ignored: including cross-country transactions (cross-client edges) is key for training models that detect international money laundering and fraud. Another example is online social applications like Facebook and LinkedIn. Users in different countries can build connections with each other (e-g., a person in the United States becoming Facebook friends with a person in China). The users in both the U.S. and China would then have record of this friendship link, while the personal user information cannot be shared across countries.
However, GCNs require information about node's neighbors to be aggregated in order to construct an embedding of each node that is used accomplish tasks such as node classification and link prediction. Ignoring the information from neighbors located at another client, as in prior federated graph training algorithms (Wang et al., 2020a; He al. 202Tb), may then result in less accurate models due to loss of information from nodes at other clients.
Prior works federated or distributed graph training reduce cross-client information loss by commu- nicating information about nodes' neighbors at other clients in each training round (Scardapane et al. 2020. Wan et al. 2022 Zhang al. 202T), which can introduce significant communication overhead and reveal private node information to other clients. We instead realize that the information needed to train a GCN only needs to communicated once, before training. This insight allows us further alleviate the privacy challenges of communicating node information between clients (Zhang et al. 2021). Specifically, we leverage Homomorphic Encryption (HE), which can preserve client privacy in federated learning but introduces significant overhead for each communication round; with only one communication round, this overhead is greatly reduced. Further, in practice each client may contain several node neighbors, e.g., clients might represent social network data in different countries, which cannot leave the country due to privacy regulations. Each client would then receive aggregated feature information about all of node's neighbors in a different country, which itself can help preserve privacy through accumulation across multiple nodes. the extreme case when nodes only have one cross-client neighbor, we can further integrate differential privacy techniques (Wei et al. 2020). We

---

propose the FedGCN algorithm for distributed GCN training based on these insights. FedGCN greatly reduces communication costs and speeds up convergence without information loss, compared
with existing distributed settings (Scardapane et al. 2020 Wan et al. 2022 Zhang et al.) 2021)
In some settings, we can further reduce FedGCN's required communication without compromising the trained model's accuracy. First, GCN models for node classification rely on the fact that nodes of the same class will have more edges connecting them, as shown in Figure (right) If nodes with each class tend to be concentrated at single client, a version of the non-i.i.d. (non-independent and identically distributed) data often considered in federated learning, then ignoring cross-clien edges discards little information, and FedGCN's communication round may be unnecessary. The model, however, may not converge, as federated learning may converge poorly when client data is non- i..d. (Zhao et al.] 2018). Second, GCN models with multiple layers require accumulated information from nodes that are multiple hops away from each other, introducing greater communication overhead. However, such multi-hop information may not be needed in practice.
We analytically quantify the convergence rate of FedGCN with various degrees of communication, under both i.i.d. and non-i.idd client data. To the best of our knowledge, we are the first to analytically illustrate the resulting tradeoff between fast convergence rate (which intuitively requires more information from cross-client edges) and low communication cost, which we do by considering a stochastic block model (Lei and Rinaldo 2013 Keriven et al.) 2020) of the graph topology. We thus quantify when FedGCN's s communication significantly accelerates the GCN's convergence.
In summary, work has the following contributions:
We introduce FedGCN, an efficient framework for federated training of GCNs to solve node-level prediction tasks with limited communication and information loss, which also leverages Fully Homomorphic Encryption for enhanced privacy guarantees.
We theoretically analyze the convergence rate and communication cost of FedGCN com- pared to prior methods, as well as its dependence on the data distribution. We can thus quantify the usefulness of communicating different amounts of cross-client information.
Our experiments on both synthetic and real-world datasets demonstrate that FedGCN out- performs existing distributed GCN training methods in most cases with a fast convergence rate, higher accuracy, and orders-of-magnitude lower communication cost.
We outline related works in Section bbefoe introducing the problem of node classification in graphs in Section We then introduce FedGCN in Section 4 and analyze its performance theoretically (Section and experimentally (Section 6) before concluding in Section
2 Related Work
Graph neural networks aim to learn representations of traph-structured data (Bronstein et al. 2017).
GCNs (iiff and Welling 2016). GraphSage (Hamilton et al.] 2017). and GAT /Veličković et al. 2017) perform well on node classification and link prediction. Several works provide a theoretical
anal analysis of GNNs based on the Stochastic Block Model (Zhou and Amini 2019 Lei and Rinaldo
2013 Keriven et al. 2020). We similarly adopt the SBM to quantify FedGCN's performance.
Federated learning was first proposed in McMahan et al. (2017)'s 's widely adopted FedAvg algorithm, which allows clients to train a model via coordination with central server while keeping training data at local clients. However, FedAvg may not converge data from different clients non-i.i.d. (Zhao)
et al.
2018 Li et al. 2019a Yang et al. 202T). We show similar results for federated graph training.
2021a). Unlike learning tasks in which multiple graphs each constitute a separate data sample and are distributed across clients (e.g., graph classification (Zhang al., 2018), image classification (Li et al. 2019b), and link prediction (Yoo et al. (2023), FedGCN instead considers semi-supervised tasks on single large graph (e.g.. for node classification. Existing methods for such tasks generally ignore the resulting cross-client edges (He et al., 2021a). Scardapane et al. (2020)'s 's distributed GNN proposes a training algorithm communicating the neighbor features and intermediate outputs of GNN layers among clients with expensive communication costs. BDS-GCN (Wan et al. 2022) proposes sample cross-client neighbors. These methods may violate client privacy by revealing per-node information to other clients. FedSage+ (Zhang et al. 2021) recovers missing neighbors for the input graph based
Federated learning on graph neural networks is a topic of recent interest (He et al.
3

---

on the node embedding, which requires fine-tuning linear model of neighbor generation and may not fully recover the cross-client information. It further vulnerable to the data reconstruction attack. compromising privacy.
All of the ahove works further require communication at every training round, while FedGCN enables the private recovery of cross-client neighbor information with single, pre-training communication round that utilizes HE. We also provide theoretical bounds on FedGCN's convergence.
3 Federated Semi-Supervised Node Classification
In this section, we formalize the problem of node classification on a single graph and introduce the federated setting in which we aim to solve this problem.
We consider graph 9 EV, where V [N] is the set of N nodes and & is the of edges. The graph is equivalent to a weighted adjacency matrix A E NNN, where A.₃ indicates the weight of an edge from node to node j (if the edge does not exist, the weight is zero). Every node E V has feature vector 2; E Rd, where d represents the number of input features. Each node i in subset ytrain C V has a corresponding label y/ used during training. Semi- cuni--upervised node classification aims to assign labels to nodes in the remaining set V Vtrasn based on their feature vectors and edges to other nodes. We train a GCN model to do so.
GCNs (Kipf and Welling 2016 consist of multiple convolutional layers, each of which constructs a node embedding by aggregating the features of its neighhoring nodes. Typically, the node embedding matrix ( for each layer 1 = 2, L is initialized to H (0) X. the matrix of features for each node (i.e., each row of X corresponds to the features for one node), and follows the propagation rule
H(++) o( (A (1) W Here (' are parameters be learned, is the weighted adjacency matrix, and Φ is an activation function. Typically, ø is chosen as the softmax function in the last layer, so that the output can be interpreted as the probabilities of a node lying each class, with ReLU activations in the preceding layers. The embedding of each node i E V at layer I + 1 is then
(1+1) = Φ ( h
EEAN Aigh w()) JEA
(I)
which can be computed from the previous layer's embedding h for each neighbor j and the weight A.j on edges from node to node j. For GCN with T. layers in this form, the output for node will depend on neighbors up to I. steps away (i.e., there exists path of no more than I. edges to node i). We denote this set by N² (note that é E NT¹) and refer to these nodes as L-hop neighbors of i.
To solve the node classification problem in federated settings (Figure D}. we consider, as usual in federated learning, a central server with K clients. The graph 9 (V,E) is separated across the K clients, each of which has a sub-graph G3 = (Ve, Ex). Here K V/- = V and V/ nv- = Ø for vi + j E [K] i.e., the nodes are disjointly partitioned across clients. The features of nodes in the set Vi can then be represented as the matrix X₁- The cross-client edges of client k. Eg. for which the nodes connected by the edge are at different clients, are known to the client k. We use Virain C Vk to denote the set of training nodes with associated labels yı- The task of federated semi-supervised node classification is then to assign labels to nodes in the remaining set V V Virain for each client k.
As seen from 11. in order to find the embedding of the i-th node in the 1-th layer, we need the
previous layer's embedding h for all neighbors of node i. In the federated setting, however, some of these neighbors may be located at other clients, and thus their embeddings must be iteratively sent to the client that contains node for each layer every training round. He al. (202 la) ignore these neighbors, considering only GR and Ex in training the model, while Scardapaae et al. (2020); Wan al. (2022); Zhang et al. (20TT) require such communication, which may lead to high overhead and privacy costs. FedGCN provides a communication effficiin method to account for these neighbors.
Federated Graph Convolutional Network
In order to overcome the challenges outlined in Section 3 we propose our Federated Graph Convolu- tional Network (FedGCN) algorithm. In this section, we first introduce our federated training method with communication at the initial step and then outline the corresponding training algorithm.

---

Federating Graph Convolutional Networks. In the federated learning setting, let c(i) denote the index of the client that contains node and W denote the weight matrix of the 1-th GCN layer of e(x)
client c(t). The embedding of node at layer + 1 is then h ((+1) o (EjeN, Ayh (1) W c(i)
Note that the weights wilh a(t) may differ from client to client, due to the independent local training in federated learning. For example, we can then write the computation of a 2-layer federated GCN
as D. Φ (EeN, A.já (EmEN; Ajman w(() d()) Wa(e) To evaluate this 2-layer model, it then
suffices for the client ls = e(t) to receive the message EmEN, Ajm We can write these messages
Aijz and JEN;
Σ
Σ mEN,
A J.
JEN./i
which are the feature aggregations of 1- and 2-hop neighbors of node i respectively. This information does not change with the model training, as it simply depends on the (fixed) adjacency matrix A and node features æ. The client also naturally knows Aeji,, which is included in & U
One way to obtain the above information to receive the following message from clients a that contain at least one two-hop neighbor of k:
Σ L((())) and NN, I(((m)) A Ajm JEM
meN,
Here the indicator (c(m)) is 1f c(m) and zero otherwise. More generally, for L-layer GCN, each layer requires Vj E /N edges up to L. hops away from node i, is needed for normalization of A.
Tc(c(m)) Am- Further, E i.e., the set of
To avoid the overhead of communicating between multiple pairs of clients, which can also induce privacy leakage when there is only one neighbor node in the client, can instead send the aggregation of each client to the central server. In the 2-layer GCN example, the server then calculates the sum of neighbor features of node i as EJEN, Aijæz = Ex= E EjeN. [e(C))) A.j The server can then send the required feature aggregation in (2) back to each client k. Thus, we only need to send the accumulated features of each node's 's (possibly multi-hop) neighbors, in order to evaluate the GCN model. If there are multiple neighbors stored in other clients, this accumulation serves to protect their individual privacy [ For the computation of all nodes V/ stored in client h with an I--layer GCN, the client needs to receive (EjEN. Aij ) where No, is the set of I--hop neighbors of nodes VA-
FedGCN is based on the insight that GCNs require only the accumulated information of the L-hop neighbors of each node, which may be communicated in advance of the training. In practice, however, even this communication may be infeasible. If L. is too large, I--hop neighbors may actually consist of the entire graph (social network graphs have diameters < 10), which might introduce prohibitive storage and communication requirements. Thus, we design FedGCN to accommodate three types of communication approximations, according to the most appropriate choice for given application:
No communication (0-hop): If any communication is unacceptable, e.g., due to overhead, each client simply trains on GR and ignores cross-client edges, as in prior work.
One-hop communication: If some communication is permissible, we may use the accu- mulation of feature information from nodes' 1-hop neighbors, (Ejex, A Jie,, to approximate the GCN computation. 1-hop neighbors are unlikely introduce significant memory or communication overhead as long as the graph is sparse, e.g. social networks.
Two-hop communication: the information from 2-hop neighbors, {EjeN; Aijæ Hie,s, and perform the aggregation of L-layer GCNs. As shown in Figure 2 the 2-hop approximation does not decrease model accuracy in practice compared to L-hop communication for L-hop GCNs, up to < 10.
To further improve model performance, we can communicate
IIn the extreme case when the node only has one neighbor stored in other clients, we can drop the neighbor, which likely has minimal effect on model performance, add differential privacy to the communicated data.
5

---

0.8
0.70
0.7
Test Accuracy
Test Pocuracy
0.6
0.5
0.4
FedSiNg hop) (
Certninaa DPN
0.3
0.50
10
Number of Layers. Cora
Number of Layers, Ogbn-Arxiv
Figure 2: Test Accuracy of GCNs with different numbers of layers, using centralized and FedGCN training on Cora (left) and Ogbn-Arxiv (right) datasets with 10 clients and non-i.id partition. Com- municating 2-hop information in FedGCN is sufficient for up to 10-layer GCNs. In Ogbn-Arxiv, BatchNormid added between GCN layers to ensure consistent performance (Hu et al. 2020).
Why Not T.-hop Communication? Although FedGCN supports L--hop communication, commu- nicating I--hop neighbors across clients requires knowledge of the T, hop neighborhood graph structures, which may incur privacy leakage. If T. is large enough, T--hop neighbors may also cover the entire graph, incurring prohibitive communication and computation costs. Thus, in practice we restrict ourselves to 2-hop communication, which only requires knowledge of I-hop neighbors. Indeed, Figure [ shows that even on the Dgbn-Arxiv dataset, which has more than one million edges, adding more layers and k-hop communication does not increase model accuracy for L 2 and & 2 2. Thus, it is reasonable to use 0, I, or 2-hop communication with I 3-layer GCNs in practice.
Secure Neighbor Feature Aggregation. To guarantee privacy during the aggregation process of accumulated features, we leverage Homomorphie Encryption (HE) to construct a secure neighbor feature aggregation function. HE (Brakerski et al.) [014 Cheon et al.) (017) allows computing party to perform computation over ciphertext without decrypting it, thus preserving the plaintext data.
The key steps of the process can be summarized as follows: (i) all clients agree on and initialize a HE keypair, (ii) each client encrypts the local neighbor feature array and sends it to the server, and (iii) upon receiving all encrypted neighbor feature arrays from clients, the server performs secure neighbor
feature aggregation [jjN; Ana = ΣΣ EjEN; (e(((()) A.yæy where I-] represents
the encryption function. The server then distributes the aggregated neighbor feature array each client, and (iv) upon receiving the aggregated neighbor feature array, each client decrypts it and moves to the model training phase. We can also use HE for secure model gradient aggregation function during the model's ' training rounds, which provides extra privacy guarantees.
Since model parameters are often floating point numbers and node features can be binary (e.g.. one-hot indicators), a na've HE scheme would use CKKS (Cheon al., 2017) for parameters and integer schemes such BGV (Brakerski et al. 2014) for features. To avoid the resulting separate cryptographic setups, we adopt CKKS with a rounding procedure for integers and also propose an efficient HE file optimization, Boolean Packing, that packs arrays of boolean values into integers and optimizes the cryptographic communication overhead. The encrypted features then only require twice the communication cost of the raw data, compared 20x overhead with general encryption.
Training Algorithm. Based on the insights in the previous section, we introduce the FedGCN training algorithm (details are provided in Appendix A):
Pretraining Communication Round The algorithm requires communication between clients and the central server at the initial communication round.
1. Each client k sends its encrypted accumulations of local node features, [[E I4 (c(())) Aey.l D. the server.
2. The server then accumulates the neighbor features for each node i, EEjEN, AGæ,
k= >x=n [EjeN, Ie(e()) A. _,,,()))AA,,,,I..
K
Each client receives and decrypts the feature aggregation of its one-hop. [[E A Jiev, and if needed two-hop, neighbors KK A,,,,
Federated Aggregation After communication, FedGCN uses the standard FedAvg algo- rithm McMahan et al. (2017) ) to train the models. Other federated learning methods, e.g. as proposed by Reddi et al. 2000 Fallah et al. (2020), easily replace this procedure.

---

5 FedGCN Convergence and Communication Analysis
In this section, we theoretically analyze the convergence rate and communication cost of FedGCN for ii.d. and non-i.id. data with O-, 1-, and 2-hop communication.
We first give formal definition of the i.i.d. and non-i.i.d. data distributions, using citribbution-bassee label imbalance (Hsu et al. 2019: Li et al., (0022. Figure 3 visualizes eight example data distributions across clients. For simplicity, we assume the number of clients K exceeds the number of node label classes C, though Section o experiments support any number of clients. We also assume that each class contains the same number of nodes and that each client has the same number of nodes.
Definition 5.1. Each client k's label distribution is defined [p1 denotes the fraction of nodes of class c at client k and Ee Pe = 1.
P2
Pc] R where Pa
Definition 5.2. Clients' data distributions are i. d. when nodes are uniformly and randomly assigned to clients, i.e., each client's label distribution is [1/C
1/C1. Otherwise, they are non i.i.d.
Non-i.i.d. distributions include that of McMahan et al. 2017) in which pj 1 p + & for some i = 1.2, ... C and & otherwise, where p E [0. is a control parameter; or the Dirichlet distribution (Hsu al. 2019) (ir(3/C), where 2 0s control parameter. With these distributions, each client has one dominant class. If p 0 or 3 + oc, all nodes at client have the same class.
Lakd Dumtoon
p=1
Nowdid p-b.
Nevcil p-84
Nascid pw0
idd 1000000
Nessial 00100
Savcid
Neeidd pw1
Figure 3: Example client data distributions. Different colors represent different node label classes. Client data is generated from the data distribution with different parameters p and [3 respectively. We use || to denote the & norm if x is vector, and the Frobenius norm if æ is matrix. Given model parameters w and K clients, we define the local loss function f& (un) for each client k; and the
global loss function ((w) = >imm (ww) which has minimum value f"
Assumption 5.3. (A-Lipschitz Continuous Gradient) There exists a constant À > 0, such that [V] - [+)(l)] S 2l/W v/I. Vw, v IR and k E [K].
Assumption 5.4. (Bounded Global Variability) There exists a constant dG 2 0, such that the global variability of the local gradients of the cost function [( - f S aG. Vk E [K], v
Assumption 5.5. (Bounded Gradient) There exists constant G 2 0, such that the local gradients of the cost function [vxx)) S G. vk E [K], Vt.
Assumptions 5.3
5.4 and 5.5 are standard in the federated learning literature (Li et al. 2019a Yu
iet al. 2019; Yang el al. 2021) We consider a two-layer GCN, though our analysis can be extended to more layers. We work from Yu et al. (2019)'s convergence result for FedAvg find:
Theorem 5.6. (Convergence Rate for FedGCN) Under the above assumptions, while training with K clients, T global training rounds, E local updates per round, and a learning rate 17 S }, we have
T EE (IVS
2 TT (f (ww) - -f") + A A K nil Tiocal Iglobll 112 + 2n² (4)
where 8 is the minimum value of Tiocat K X A A Ax Igins = X AT
The convergence rate is thus bounded by the difference of the information provided by local and global graphs //ooot - Igooblli ll. which upper bounds the global variability [VV(( - (Sw))] By 1- and 2-hop communication. the local graph A is closer to A. resulting in faster convergence.
Table bounds ||4toca Iotos|l for FedGCN trained on an SBM (stochastic block model) graph, in which we assume N nodes with C classes. Nodes in the same (different) class have an edge between them with probability a (μO). Appendix D details the full SBM. Appendix H derives Table [
A CClients with i.i.d. label distributions may still have global variability ae > 0 due to having finite samples.
*Our analysis applies any federated training algorithm with bounded global variability Yang et al. 2021
7

---

Non-i.i.d
i.i.d.
0-hop
(1
2)
(1 (1-p)
(1 ka Na B+1
1-hop
(1 Z.( + Cap +
B
+ (1- (1-
(1 ęz + co + cu)
B
2-hop
K3 + Cap + ch
Ba
(1-
(1 K4 (1 + + cp)
No
B
Table Convergence rate bounds of FedGCN with the Stochastic Block Model and data distribution from McMahan et al. (017) We define Ca = (1=#)aN(K and Cp = paNN(K-1) for the SBM; a.V CK
K
constant, Ca > Cn and Cy O. More hops speed up the convergence from the order of to 6 (highlighted as purple and green). Communication helps more when data is more i.d with factor Cop (highlighted as blue). Non-i.i.d. data implies longer convergence time with factor (1 p)
results; the SBM structure allows us develop intuitions about FedGCN's convergence with different hops, simply by knowing the node features and graph adjacency matrix (i.e., without knowing the model). Appendix F derives corresponding expressions for the required communication costs. We validate these results in experiments and Appendix G, and make the following key observations:
Faster convergence with more communication hops: 1-hop and 2-hop communication accelerate the convergence with factors (1 + CoP + c,,)² and (1 + CoP + c2,), respectively, When the i.idd control parameter p increases, the difference among no (0-hop), 1-hop, and 2-hop communication increases: communication helps more when data is more i.i.d.
More hops are needed for cross-device FL: When the number of clients K increases, as in cross-device federated learning (FI.), the convergence takes longer by factor gz, but 2-hop communication can recover more edges in other clients speed up the training.
1
One-hop is sufficient for cross-silo FL: the number of clients K is small, approximation methods via one-hop communication balance the convergence rate and communication overhead. We experimentally validate this intuition in the next section.
Experimental Validation
We experimentally show that FedGCN converges to accurate model with less communication compared to previously proposed algorithms. We further validate Section 5]s thcoretical observations.
6.1 Experiment Settings
We use the Cora (2708 nodes, 5429 edges), Citeseer (3327 nodes, 4732 edges), Ogbn-ArXiv (169343 nodes, 1166243 edges), and igbn-Proddutt (2449029 nodes, 61859140 edges) datasets to predict document labels and Amazon product categories (Wang et al.] [220b;] Hu et al. (020)).
Methods Compared. Centralized GCN assumes single client has access to the entire graph.
Distributed GCN (Scardapane et al. 2020 trains GCN in distributed clients, which requires commu- nicating node features and hidden states of each layer. FedGCN (0-hop) (Section 4 is equivalent to federated training without communication (FedGraphnn) (Wang et al. 22000a] [Zheng et al.) 2021
He et 2021a). BDS-GCN (Wan al. (2022) randomly samples cross-client edges each global training round, while FedSage+ (Zhang el al. (021) recovers missing neighbors by learning a linear predictor based on the node embedding, using cross-client information in each training round. is thus an approximation of FedGCN (1-hop), which communicates the 1-hop neighbors' information across clients. FedGCN (2-hop) communicates the two-hop neighbors' information across clients.
We consider the Dirichlet label distribution with parameter 3, as shown in Figure 3 Citeseer,
For Cora and a 2-llyer GCN with Kipf and Welling 2016)'s hyper-parameters. For Ogbn-Arxiv and Ogbn-Products, we respectively use a 3-layer GCN and a 2-layer GraphSage with Hu et al. (2020)'s 's setups and extended results, including an evaluation of the HE overhead, are in Appendix E and G.
We average results over 10 experiment runs. Detailed experimental
6.2 Effect of Cross- Client Communication
We first evaluate our methods under i.i.d. (3 10000) and non-i.i.d. (3 = 100, 1) Dirichlet data distributions on the four datasets illustrate FedGCN's performance relative to the centralized, BDS-GCN, and FedSage+ basclines under different levels of communication.
8

---

Com, TD chiens
Cheseer, 10 chients
Centralized GCN
00,066
0.6014=0.0051
3=1
_ = 100
3= 10000
8=1
8= 100
== 10000
FeuGCNN(Ubbo))
BDS-GCN
0.7098-+0.0143
0.7467+000017
0.7479--0.018
0.6709-000184
0.6996+0.0122
0.6082
FedSage+
US026100000
F0.0075
0,796 10.007
10.007
0.6855 1 00.0221
00008
FeuGCNN hop)
1.00M
0,009 E0,007
100077
0.7006 1.0077
0.6891 1000007
0.69%
FedGCN((-hop)
08004
0.0054
000006
0.0033
0,6933 0,0069
0.6948 0.0032
Ogba-Arxis, elients
Ogba-Procucts. clients
Centralized GCN
0.71000082
0.705K
3=1
/3 = 100
==
J
J3
(odOCN((--oo))
0.0981+00.004
000001-000017
0.0001
000089
0.66%-+-.0008
0.658-1000008
BDX GCN
0.6769 10.086
0.6899 10,0024
U.688K 0.0015
0.699610.001 10.0019
0.6952 I 0.0012
0.6952 0.0009
FodSage+
E0:005
10:011
10002
0.0041100001
10.0000
FedoCN(T-hop)
0.7 0.7001
0.6009-0.0038
0.700
0.00490000016
0.7057=0.0005
0.0004
Fed0CN/2-bop)
0.075
0.6972-50.0075
0.70171-00001
0.7053+0.002
0.7057
0.0006
Table 2: Test Accuracy on four datasets, for (. = 10000) and non-i.i.d. (3 100, 1) data.
FedGCN (1-hop.2-hop) performs best i.i.d. and non-i.i.d. data, and FedGCN (0-hop) has the most
information loss. We assume FedSage+'s 's linear approximator perfectly learns neighbor information.
As shown in Table FedGCN(1-, 2-hop) has higher test accuracy than FedSage+ and BDS-GG DCS.GCN. reachiing the same test accuracy as centralized training in all settings. FedGCN(I- 2-hop) is able to converge faster to reach the same accuracy with the optimal number of hops depending on the data distribution. In such cross-silo setting (10 clients), FedGCN(I-hoo) achieves good tradeoff between communication and model accuracy. FedGCN (0-hop) performs worst the i.i.d. and non-i.i.d. settings, due to information loss from cross-client edges.
Why Non-i.id Has Better Accuracy in O-hop? In Table with 10 clients, O-hop has better accuracy since non-i.i.d. has fewer cross-client edges (less information loss) than i.i.d as in theoretical analysis.
Accuracy
0.70
0.88
0.72
Centralized GCN
FadGON)
FedGON
FedSager
BDS-GON
DOON
Acouracy
0.88
0.72
0.66
Centralized BCN
FedGCN((1hop)
FedGON DGON
FedSage+
BDS-OCN
0.68
0.72
Centralized DCN
FedGCN1 hhpp hhop FedGON
FedSage-
BDS-GCN
DGON
0.64
0.66
0.82
0.62
0.64
0.80
0.80
0.58
FedGGN//-hool
0.58
FedGCNO-hool
0.60
F /edGCN/o-hhop
940 w0'nn" 10"10 10"10" 10' 10 Communication Cost, $ 10000
G10"
10 10" 10' 10' 10' 10'10"
Gip 10 10" 10"1"" 10 10' 10'10"
Communication Cost, 8= 100
Communication Cost, $
Figure 4: Test accuracy vs. communication cost until convergence of algorithms the i...d, partial- ii.d. and non-i.i.d. settings for the OGBN-ArXiv dataset. FedGCN uses orders of magnitude less communication (at least 100x) than BDS-GCN and FedSage+, while achieving higher test accuracy.
Communication Cost vs. Accuracy. Figure 4 shows the communication cost and test accuracy of different methods the OGBN-ArXiv dataset. FedGCN (0-, 1-, and 2-hop) requires little communication with high accuracy, while Distributed GCN, BDS-GCN and FedSage+ require communication at every round, incurring over 100x the communication cost of any of FedGCN's variants. FedGCN (0-hop) requires much less communication than 1- and 2-hop FedGCN, but has lower accuracy due information loss, displaying convergence-commuiicci Both 1- and 2-hop FedGCN achieve similar accuracy as centralized GCN, indicating that a 1-hop approximation of cross-client edges is sufficient in practice achieve accurate model.
tradeoff.
0.80
0.80
0.80
Accuracy
0.75
Accuraci
0.75
Test Accuracy
FedGCN(O-hop) hoppp)
FedGCN((-hap)) FedGCN) 1-hop)
FedGCN(D-hop)
0.70
0.70
FodGGN((1hhg)
FedGCN(1 (-hap)
FodGGN((-hop)
0.85
0.65
Fod
0.85
0.60
0.80
0.55
20
40
60
80
100
100
120
140
160
180
Number of Clients
Number of Clients
Number of Clients
Figure 5: Test accuracy with the number of clients on the Cora dataset.

---

Cross-Silo and Cross-Device Training, As shown in achieve similar test accuracy in the cross-silo setting with few clients, though 1 I-hop communication has lower communication costs. However, in the cross-device setting with many clients (Fig- right,, the 1-hop test aceuracy drops with more clients, indicating that 2-hop communication may be necessary to maintain high model accuracy, as suggested by our theoretical analysis.
1-hop and 2-hop communication
7 Conclusion & Future Directions
We propose FedGCN, a framework for federated training of graph convolutional networks for semi- supervised node classification. The FedGCN training algorithm is based the insight that, although distributed GCN training typically ignores cross-client edges, these edges often contain information useful to the model, which can be sent in single round of communication before training begins. FedGCN allows for different levels of communication to accommodate different privacy and overhead concerns, with more communication generally implying less information loss and faster convergence, and further integrates HE for privacy protection. We quantify FedGCN's convergence under different levels of communication and different degrees of non-i..d. data across clients and show that FedGCN achieves high accuracy on real datasets, with orders of magnitude less communication than previous algorithms.
Although the FedGCN can overcome the challenges mentioned above, it mainly works on training accumulation-basse models like GCN and GraphSage. There are several open problems in federated graph learning that need to be explored.
Federated Training of irentton-based GNNs Attention-based GNNs like GAT (Graph attention network) require calculating the attention weights of edges during neighbor feature aggregation, where the attention weights are based on the node features on both sides of edges and attention parameters. The attention parameters are updated at every training iteration and cannot be simply fixed at the initial round. How to train attention-based GNNs in federated way with high performance and privacy guarantees is an open challenge and promising direction.
Neighbor Node and Feature Selection to Optimize System Performance General federated graph learning optimizes the system by only sharing local models, without utilizing cross-devics graph edge information, which leads to less accurate global models. On the other hand, communicating massive additional graph data among devices introduces communication overhead and potential privacy leakage. To save the communication cost without affecting the model performance, one can select key neighbors and neighbor features to reduce communication costs and remove redundant information. For privacy guarantee, if there is one neighbor node, it can be simply dropped to avoid private data communication. FedGCN can be extended by using selective communication in its pre-training communication round.
Integration with L-hop Linear GNN Approximation methods To speed up the local com- putation speed, L-hop Linear GNN Approximation methods use precomputation to reduce the training computations by running a simplified GCN (A T.X XW in SGC Wu et al. 2 [AXW, X ...., X in SIGN Frasca et al. (020)), and IIX in PPRGo Bojchevski et al, (2020) where II is the pre-computed personalized pagerank), but the communication cost not reduced if we perform these methods alone. They are thus a complementary approach for efficient GNN training. FedGCN (2-hop. I-hop) changes the model input (A and X) to reduce communication in the FL setting, but the GCN model itself is not simplified. FedGCN can incorporate these methods to speed up the local computation, especially in constrained edge devices.
Acknowledgement
This research was supported by the National Science Foundation under grant CNS- 1909306,, Cloud- bank support through CNS-1751075, and the Lee-Stanziale Ohana Fellowship by the ECE department Carnegie Mellon University. The authors would like to thank Jiayu Chang, Cynthia (Xinyi) Fan, and Shoba Arunasalam for helping with the coding.
10

---

References
Adrien Benamira, Benjamin Devillers, Etienne Lesot, Ayush K Ray, Manal Saadi, and Fragkiskos D) Malliaros. 2019. Semi-supervised learning and graph neural networks for fake news detection. In 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM). IEEE, 568-569.
Alcksandar Bojchevski, Johannes Gasteiger, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberczki, Michal Lukasik, and Stephan Günnemann. 2020. Scaling graph neural networks with approximate pagerank. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2473..47..
Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. 2014. (Leveled) fully homomorphic encryption without bootstrapping. ACM Transactions on Computation Theory (TOCT) 6, 3 (2014), 1-36.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. 2017. Geometric deep learning: going beyond euclidean data, IEEE Signal Processing Magazine 34, (2017), 18-42.
Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. 2017. Homomorphic eneryption for arithmetic of approximate numbers. In International conference on the theory and application of cryptology and information security. Springer, 437
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. 2020, Personalized federated learning with theoretical guarantees: A model-agnostic meta-learning approach. Advances in Neural Information Processing Systems 33 (2020), 3557-3568.
Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, and Federico Monti. 2020. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004.1 11198 (2020).
William L Hamilton, Rex Ying, and Jure Leskovec. 2017. Inductive representation learning large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems. 1025-1035.
Chaoyang He, Keshav Balasubramanian, Emir Ceyani, Carl Yang. Han Xie, Lichao Sun, Lifang He, Liangwei Yang, Philip S Yu, Yu Rong, et al. 2021a. Fedgraphnn: A federated learning system and benchmark for graph neural networks. arXiv preprint arXiv:2104.07145 (2021).
Chaoyang He, Emir Ceyani, Keshav Balasubramanian, Murali Annavaram, and Salman Avestimehr. 2021b. Spreadgnn: Serverless multi-task federated learning for graph neural networks. arXiv preprint arXiv:2 100i2220000024433 (2021).
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. 2019. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint arXiv: 11ti:19990003335 (2019).
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020. Open graph benchmark: Datasets for machine learning on graphs.
Advances in neural information processing systems 33 (2020),
Nicolas Keriven, Alberto Bietti, and Samuel Vaiter. 2020. Convergence and stability of graph convolutional networks on large random graphs. arXiv preprint arXiv:2006.0188 011688 (2020).
Thomas N Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 1609.629079077 (2016).
Jing Lei and Alessandro Rinaldo. 2015. Consistency of spectral clustering in stochastic block models. The Annals of Statistics 43, 1 (2015), 215-237.
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. 2019b. Deepgens: Can gens go as deep as cnns?. Proceedings of the IEEE/CVF international conference on computer vision. 9267-9276.

---

Qinbin Li, Yiqun Diao, Quan Chen, and Bingsheng He. 2022. Federated learning on non-iid data silos: An experimental study. 2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE, 965-978.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. 2019a. On the conver- gence of fedavg on non-iid data. arXiv preprint arXiv:1907.02188 (2019).
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. 2017. Communication--fficienn learning of deep networks from decentralized data. Artificial intelligence and statistics. PMLR, 1273-1282.
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H Brendan McMahan. 2020. Adaptive federated optimization. arXiv preprint arXiv:2003.00295 (2020).
Simone Scardapane, Indro Spinelli, and Paolo Di Lorenzo. 2020. Distributed Graph Convolutional Networks. arXiv preprint arXiv:2007.066 .06281 (2020).
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017. Graph attention networks. arXiv preprint 109903 (2017).
Cheng Wan, Youjie Li, Ang Li, Nam Sung Kim, and Yingyan Lin. 2022. BNS-GCN: Efficient full- graph training of graph convolutional networks with partition-parallliis and random boundary node sampling. Proceedings of Machine Learning and Systems 4 (2022), 673-693.
Binghui Wang, Ang Li, Hai Li, and Yiran Chen. 2020a. Graphfl: federated learning framework for semi-supervised node classification graphs. arXiv preprint arXiv:2012.04187 (2020).
Kuansan Wang, Zhihong Shen, Chiyuan Huang, Chieh-Har Wu, Yuxiao Dong, and Anshul Kanakia. 2020b. Microsoft academic graph: When experts are not enough. Quantitative Science Studies 1, (2020), 396-413.
Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H Yang, Farhad Farokhi, Shi Jin, Tony QS Quek, and H Vincent Poor. 2020. Federated learning with differential privacy: Algorithms and performance analysis. IEEE Transactions on Information Forensics and Security 15 (2020), 3454-3469.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. 2019. Sim- plifying graph convolutional networks. In International conference machine learning. PMLR, 6861-6871.
Haibo Yang, Minghong Fang, and Jia Liu. 2021. Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning. arXiv preprint arXiv:2101. (2021).
Yuhang Yao, Mohammad Mahdi Kamani, Zhongwei Cheng, Lin Chen, Carlee Joe- Wong, and Tianqiang Liu. 2023. FedRule: Federated Rule Recommendation System with Graph Neural Networks. In Proceedings of the 8th ACM/EEEE Conference on Internet of Things Design and Implementation. 197-208.
Hao Yu, Sen Yang, and Shenghuo Zhu. 2019. Parallel restarted SGD with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33. 5693-5700.
Ke Zhang, Carl Yang. Xiaoxiao Li, Lichao Sun, and Siu Ming Yiu. 2021. Subgraph federated learning with missing neighbor generation. Advances in Neural Information Processing Systems 34 (2021).
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. 2018. An end-to-end deep learning architecture for graph classification. In Thirty-second AAAI conference on artificial intelligence.
Weijia Zhang, Hao Liu, Yanchi Liu, Jingbo Zhou, and Hui Xiong. 2020. Semi-supervised hierarchical recurrent graph neural network for city-wide parking availability prediction. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 34. 1186-1193.
12

---

Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. 2018. Federated learning with non-iid data. arXiv preprint
(2018).
Longfei Zheng, Jun Zhou, Chaochao Chen, Bingzhe Wu, Li Wang, and Benyu Zhang. 2021. ASFGNN: Automated separated-federated graph neural network. Peer-to-Peet Networking and Applications 14, 3 (2021), (692-1704)
Zhixin Zhou and Arash A Amini 2019. Analysis of spectral clustering algorithms for community detection: the general bipartite setting. The Journal of Machine Learning Research 20, (2019), 1774-1820.
13


Reviews:
[{"review_id": "dMnzHsugM9", "reviewer": "Reviewer_PXRJ", "summary": "The paper presents FedGCN, a framework designed for federated training of graph convolutional networks (GCNs) specifically for semi-supervised node classification. The proposed method aim to  communicate cross-client neighbor information just once before training initiates, diverging from previous methods that demanded communication in each round. This shift significantly reduces communication overhead and expedites convergence. FedGCN provides the flexibility to choose between 0-, 1-, or 2-hop neighbor communication to strike an optimal balance between overhead and model accuracy. Empirical results highlight FedGCN's effectiveness and minimal communication cost in comparison with previous techniques.", "questions": "Please address my concerns in **Weaknesses**.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. Reducing the training communication during distributed training of graph neural networks is a crucial problem when dealing with super large graphs.\n2. The experiment is thorough, albeit with small-scale graph datasets.\n3. The presentation is clear, well-structured, and easy to follow. I personally appreciate the results in Figure 3 and its presentation format.", "weaknesses": "1. The motivation is not clear. In the abstract, the motivation \"keeping data where it is generated\" and \"a single connected graph cannot be disjointly partitioned onto multiple clients\" is contradictory. We don't need to partition the graph; the graph itself has multiple partitions. If this is the case, where should we store the connection information for two nodes on different partitions since we need to \"keep data where it is generated\"? The idea of \"keeping data where it is generated\" also contradicts the proposed \"X-hop communication\". (Note that I accept the motivation that the graph is so large that it cannot be stored in one machine.)\n2. The assumptions are not well grounded, well-explained, or empirically verified. The three assumptions - a) Lipschitz Continuous Gradient, b) Bounded Global Variability, and c) Bounded Gradient - are extremely strict. Even though this paper claims most of them are standard assumptions of FL, this is far from convincing to me. Since all the assumptions form the upper bound of the main claim (Equation (4)), this should be well addressed and treated.\n3. The technical contribution may be limited. If I understand correctly, when rewriting the GCN equation to Equation (2), this paper removes the activation function in the first layer (otherwise, we would have to transform the hidden representation during training). This operation makes the proposal essentially a type of SGC [1]. If this is the case, the technical contribution may be limited.\n\n4. The experiments appear to be quite weak.\n- a. One of the motivations of this paper is the large size of the graph. However, the graphs used in the experiments are all small (even 'tiny' for Cora, CiteSeer).\n- b. Since the graphs are small, the communication cost will be negligible.\n- c. There are some important baselines missing. [2]\n\n\n[1] Simplifying graph convolutional networks, ICML2019. \\\n[2] Learn Locally, Correct Globally: A Distributed Algorithm for Training Graph Neural Networks, ICLR 2022", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful suggestions! We plan to incorporate them into our manuscript, as we detail below, and we believe that our reply will resolve your concerns.\n\n>**For weakness 1: motivation is not clear**\n\n“Keeping data where it is generated” refers to typical data constraints in federated settings where the graph data and its node features are naturally stored in the local clients, which preserves the privacy of users.\n\nIn these settings, the cross-client edges typically exist in both clients. Intuitively, this is due to the fact that edges are generated when nodes at clients interact with each other. Thus, the interaction record, though not personal node characteristics, is naturally stored at both nodes, i.e., in both clients. We provide examples (Amazon and Facebook, see rebuttal to Reviewer BmP4) and will use them to clarify this point in the paper's introduction.\n\nThe reviewer's comment that \"keeping data where it is generated contradicts the proposed X-hop communication\" exactly captures the main challenge of our paper: we believe that FedGCN's method of communication allows models to learn with cross-client edges, without revealing sensitive information across clients. \"X-hop communication\" is used to communicate averaged information with encryption rather than sending sensitive user features directly.\n\nIn writing \"a single connected graph cannot be disjointly partitioned onto multiple clients\" we mean to say that the cross-client edges must exist. We agree that the sentence is a bit confusing. We will modify the abstract accordingly.\n\nAs mentioned in Line 31, the main challenge of applying FL to GCN training involving a single large graph is that cross-client edges exist among clients.\n>**For weakness 2: the assumptions are not well-grounded, well-explained, or empirically verified**\n\nLipschitz Continuous Gradient, Bounded Global Variability, and Bounded Gradient are standard assumptions for FL analysis [1-6]. For example, [6] incorporates them as assumption 1, assumption 2, and Eqn. 14 of Appendix B.2, \n\n$$\\mathbb{E}[\\mathcal{L}(\\bar{\\theta}^{t+1})]\\leq\\mathbb{E}[\\mathcal{L}(\\bar{\\theta}^t)]+\\mathbb{E}[\\langle\\nabla\\mathcal{L}(\\bar{\\theta}^t),\\bar{\\theta}^{t+1}-\\bar{\\theta}^t\\rangle]+\\frac{L}{2}\\mathbb{E}[\\|\\bar{\\theta}^{t+1}-\\bar{\\theta}^t\\|^2].$$\n\nThey are “very standard non-convex, non-iid FL assumptions” (mentioned by reviewer z8YN (strength 4) and reviewer d6pK(strength 2)), and we believe they constitute the state-of-the-art FL convergence analysis.\n\nThat said, we also agree that these non-convex assumptions are still relatively strict, since how to provide FL analysis without such assumptions is still an open problem. We will add discussion of these limitations to our paper. In brief, Bounded Global Variability and Bounded Gradient allow the convergence analysis to accommodate data distribution heterogeneity, a core challenge of FL [1-3]. The bounded gradient assumption in particular holds for certain activation functions, e.g., sigmoid functions, and bounded input features. Lipschitz Continuous Gradient is a technical condition on the shape of the loss function that is standard for non-convex analysis. It in fact relaxes the assumption of (strongly) convex loss functions that were previously common in analyzing FL and stochastic gradient descent [1]. Our theory is also based on [2]’s convergence result for FedAvg. We hope our theory can open the area of theoretical analysis of federated graph learning.\n>**For weakness 3: the technical contribution may be limited**\n\nWe do not remove the activation function in the 1st layer. After getting the neighbor feature aggregation, the GCN computation is exactly the same as the centralized training given the same parameter $W$. Eqn. 2 shows only the aggregation of neighbor features; this aggregation is then passed into the activation function as usual in GCNs.\n\nAs mentioned in our conclusion, the paper \"Simplifying GCNs\" aims to speed up the local computation by simplifying the GCN computation as $A^kXW$, which is an approximation of GCN. FedGCN can incorporate such methods to speed up local training.\n>**For weakness 4.a,4.b: graphs used in the experiments are all small, communication cost is then negligible**\n\nAs mentioned in section 6.1, we experiment on Ogbn-ArXiv (169,343  nodes, 1,166,243 edges), and Ogbn-Products (2,449,029 nodes, 61,859,140 edges). We respectfully claim that a graph with 2,449,029 nodes and 61,859,140 edges is not “small”. [6] also uses Ogbn-ArXiv. We note that Ogbn-Products is bigger than all datasets used in [6].\n\nAs described in Appendix E.3, experiments are done in a p3d.16xlarge instance with 8 GPUs (32GB memory for each GPU) and 10 g4dn.xlarge instances (16GB GPU memory in each instance). One run of the Ogbn-Products experiment can take 20 min by full-batch GPU graph training. CPU training is impossible in this case. Experiments take two weeks to finish all data points of Ogbn-Products. For communication cost, please refer to rebuttal to reviewer BmP4 in Question 2.\n>**For weakness 4.c: some important baselines missing**\n\nThank you for mentioning the paper[6]. It proposes distributed graph training with global correction. For the global correction part, the server stores global graph information and node features, which causes serious privacy leakage in our federated setting. Although the paper studies a different setting, we will cite the paper and discuss it accordingly.\n\n[1] On the Convergence of FedAvg on Non-IID Data. ICLR 2019.\n\n[2] Parallel restarted SGD with faster convergence and less communication. AAAI 2019.\n\n[3] Achieving Linear Speedup with Partial Worker Participation in Non-IID FL. ICLR 2021.\n\n[4] Sharper convergence guarantees for asynchronous sgd for distributed and federated learning. NeurIPS 2022.\n\n[5] FeDXL: Provable FL for Deep X-Risk Optimization. ICML 2023.\n\n[6] Learn Locally, Correct Globally: A Distributed Algorithm for Training Graph Neural Networks, ICLR 2022"}, {"review_id": "Yi9GuRY2pT", "reviewer": "Reviewer_d6pK", "summary": "The paper introduces a technique to facilitate the federated learning of graph convolution networks. The key idea is to send aggregated node features to each client before the federated learning. The approach involves transmitting these features to each client in an encrypted manner to ensure privacy.\n\nOverall, I find the method proposed and the theoretical analysis interesting. The results look good. Some key details of the method might need to be clarified. I tend to accept this work. ", "questions": "1. If the convergence-communication tradeoff is controlled by the number of hops, it appears that achieving a continuous or fine-grained tradeoff control might not be possible. What happens if the convergence achieved with 1-hop aggregations is poor while the communication required for 2-hop aggregations is excessive? How does the proposed technique address such scenarios?\n\n2. Could you provide further details on how the communication costs are computed in Figure 4? \n\n3. The author uses the term \"cross-silo\" to refer to a small number of clients and \"cross-device\" to refer to a large number of clients. It would be helpful to define the boundary between these two categories. How many clients are considered the minimum for classifying them as \"cross-devices\"?", "limitations": "Not discussed. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper proposes an improved framework for learning graph ConvNets federately. The results demonstrate the effectiveness.\n- The theoretical convergence analysis is provided which illustrates a convegence-coomunite tradeoff. ", "weaknesses": "Technical details\n---\nThere are a few technical details that the authors may want to clarify for a better understanding of the proposed technique.\n\nIn equation (2), the authors claim that only feature aggregations of 1- and 2-hop neighbors of node $i$ are needed to evaluate the 2-layer GCN. It would be helpful if the authors could elaborate more on **why 1- and 2-hop aggregations are sufficient**. Is this an exact or approximate evaluation of the GCN model? Additionally, since GCN incorporates non-linearity in the model, it would be valuable to articulate how 2-hop feature aggregations can be directly used for evaluation.\n\nIn equation (3), regarding client $k$, it would be beneficial for the authors to clarify whether they compute 1-hop feature aggregations for all nodes $V$ or only for the nodes belonging to client $k$, denoted as $V_k$. In line 222, the authors mention $V_k$, but it seems that it should be $V$ instead. Otherwise, it appears impossible to obtain the cross-edge aggregation for node $i$.\n\nProof sketch\n---\nIt might be beneficial to provide a sketch of the proof to demonstrate the idea of how to prove the bounds in Table 1. How does the number of hops involved in the analysis? Currently, results are up to 2-hops, is it possible to get results for the high numbers of hops? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your recognition that the method and proofs are interesting! We are very happy to elaborate on more technical details and proof sketches.\n>**Technical details: why feature aggregations of only 1- and 2-hop neighbors of nodes are sufficient to evaluate the 2-layer GCN?**\n\nBased on Equation 1,\n\n$\\mathbf{h}^{(l+1)}\\_i=\\phi\\left(\\sum_{j\\in\\mathcal{N}\\_{i}}\\mathbf{A}\\_{ij}\\mathbf{h}\\_j^{(l)}\\mathbf{W}^{(l)}\\right), $\n\nas mentioned in line 127, for a GCN with L layers, the output for node i will depend on neighbors up to L steps away  (i.e., there exists a path of no more than L edges to node i). So feature aggregations of 2-hop neighbors give an exact evaluation for 2-layer GCN.\n>**Technical details: how 2-hop feature aggregations can be directly used for evaluation?**\n\nThe 2-layer GCN computation for node $i$ is\n$$\\mathbf{\\hat{y}}\\_i=\\phi\\left(\\sum_{j\\in\\mathcal{N}\\_i}\\mathbf{A}\\_{ij}\\phi\\left(\\sum_{m\\in\\mathcal{N}\\_j}\\mathbf{A}\\_{jm}\\mathbf{x}_m^T \\mathbf{W}^{(1)}\\_{c(i)}\\right)\\mathbf{W}^{(2)}\\_{c(i)}\\right).$$\n\n$\\sum_{m\\in\\mathcal{N}\\_j}\\mathbf{A}\\_{jm}\\mathbf{x}\\_m^T$ includes both 1-hop feature aggregation $\\sum_{j\\in\\mathcal{N}\\_i} \\mathbf{A}\\_{ij}\\mathbf{x}\\_j$, and 2-hop feature aggregation \n$\\left\\\\{\\sum_{m\\in\\mathcal{N}\\_j}\\mathbf{A}\\_{jm}\\mathbf{x}\\_j\\right\\\\}\\_{j\\in\\mathcal{N}\\_{i}/i}$. The 2-hop feature aggregation is directly added in $\\sum_{m\\in\\mathcal{N}\\_j}\\mathbf{A}\\_{jm}\\mathbf{x}\\_m^T$. After completing the aggregation of this information, it then goes to the non-linear activation layer $\\phi(\\cdot)$. \n>**Technical details in equation 3: For client $k$, compute 1-hop feature aggregations for all nodes $V$ or only for the nodes $V_k$ belonging to client $k$?**\n\nAs in line 222, each client $k$ sends its encrypted accumulations of local node features, \n$$\\left[\\left[ \\left\\\\{\\sum_{j\\in\\mathcal{N}\\_i}\\mathbb{I}\\_k(c(j))\\cdot\\mathbf{A}\\_{ij}\\mathbf{x}\\_j\\right\\\\}\\_{i\\in{\\mathcal{V}\\_k}}\\right]\\right],$$ \nto the server based on its local nodes $V_k$. The server then aggregates such information for all clients and the accumulated information for all nodes $V$. After that, the server selects the required 2-hop neighbor feature aggregation for each node $i$ and sends it back to the client $k$. \n\n>**Sketch of proof to demonstrate the idea of how to prove the bounds in Table 1**\n\nStep 1: As in Theorem 5.6, the analysis for general graphs relies on bounding the difference of the information provided by local and global graphs $\\|I_{local}-I_{glob}\\|$. \n\nStep 2: To further quantify such differences, we adopt the Stochastic Block Model (SBM) for analyzing the graph topology. \n\nStep 3: As shown in Appendix H.3.2, the information difference can be separated into two components: the difference in the number of nodes (different number of data samples) and the difference in node label distribution  (IID or Non-IID). \n\nStep 4: By calculating the two components under the SBM, we can then derive the equations (each one has two components) in Table 1.\n>**Proof Sketches: How does the number of hops involved in the analysis?**\n\nAs in Theorem 5.6, Appendix H.1 (1-layer case) and Appendix H.2 (2-layer case), the difference of the information provided by local and global graphs $\\|I_{local}-I_{glob}\\|$ can be written as $\\|K\\mathbf{X}_k^T\\mathbf{A}_k^T\\mathbf{A}_k\\mathbf{X}_k-\\mathbf{X}^T\\mathbf{A}^T\\mathbf{A}\\mathbf{X}\\|$ for the 1-layer case and $\\|K\\mathbf{X}_k^T\\mathbf{A}_k^T\\mathbf{A}_k^T\\mathbf{A}_k \\mathbf{A}_k\\mathbf{X}_k-\\mathbf{X}^T\\mathbf{A}^T\\mathbf{A}^T\\mathbf{A}\\mathbf{A}\\mathbf{X}\\|$ for the 2-layer case. \n\nIt can be extended to the L-hop case by expanding $\\mathbf{A}^T\\mathbf{A}$, though the computation (deriving the analytical form) will be increasingly tedious as the number of hops increases.\n\nWe already have a cleaner version of the proof and we will also include the above proof sketch in the paper.\n>**Question 1: What happens if the convergence achieved with 1-hop aggregations is poor while the communication required for 2-hop aggregations is excessive?**\n\nThis is an interesting future direction. The most natural way to make the communication tradeoff more granular is to perform neighbor sampling with probability $p$ to reduce the communication overhead [1]. Currently, we are communicating with all neighbors in the graph. We will include this direction as future work.\n\n[1] BNS-GCN: Efficient full-graph training of graph convolutional networks with partition-parallelism and random boundary node sampling.\n>**Question 2: Could you provide further details on how the communication costs are computed in Figure 4?**\n\nIt is calculated by the overall length of arrays needed to be sent, which is independent of the implementation. E.g. the client needs to send an array {1, 0, 1, 0} to the server, the communication cost is then 4. In this way, the cost can be independent of the implementation. Compression techniques may make the actual communication cost lower than the array size, but their efficacy will depend on the specific data to be transmitted, and thus we do not consider them here. The code is also provided to reproduce.\n\nIn Fig. 4. the communication cost of distributed GCN can be 10^9 for Ogbn-Arxiv, which works out to several GBs of communicated data. For Ogbn-Products (2,449,029 nodes), it is hundreds of GBs. FedGCN requires 100X less communication cost. \n\nIn practical businesses (e.g. billions of nodes in Amazon and Facebook), the communication cost of distributed methods is prohibitive with extremely high latency at every training round. FedGCN's single pre-communication round can thus greatly improve performance.\n>**Question 3: How many clients are considered the minimum for classifying them as \"cross-devices\"?**\n\nWe borrowed this terminology from [2], and there is no clear definition in the FL community. Generally speaking, \"more than 100 clients\" is cross-device, and \"less than 100 clients\" is cross-silo.\n\n[2] Federated Learning Tutorial, NeurIPS 2020\n"}, {"review_id": "EY2z3xJMWk", "reviewer": "Reviewer_z8YN", "summary": "The authors propose a secure federated protocol over GCNs which are split across federated clients. To use the features of a node's neighbors present in other clients (of which both clients are mutually aware of an edge), the accumulation of neighbor features through the adjacency matrix is encrypted via some public key encryption scheme (such as homomorphic encryption), sent to the server, aggregated, and then sent back to the client, where it is decrypted and used to approximate the classical message passing GCN calculation. Feature accumulations of 0-hop, 1-hop, or 2-hop neighbor information may be used. The approach is studied over benchmarked over several well-known graph datasets and compared against other federated approaches, where the method (either 1-hop or 2-hop) is superior to non-FedGCN strategies. ", "questions": "1. If the encryption scheme requires rounding/quantization, this will affect the convergence rate as information transmission is imperfect. This is because the act of encryption-decryption is acting as a compression operator [1]. Many hallmark gradient compression algorithms study the effects of quantizing model parameters/updates on convergence, and it depends on the accuracy of the recovery. Is the encryption/decryption protocol simply assumed to be perfect? If not, can this be incorporated into the convergence guarantee?\n\n\n\n\n[1] Stitch et al., 2018 \"Sparsified SGD with Memory.\"", "limitations": "Discussed. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. Narrative is very nicely presented -- review of GCNs is nicely condensed and would be understandable for researchers outside of this particular area. \n\n2. Algorithm is astoundingly simple, takes advantage of well-known public encryption schemes, protects client data features from one-another and from the server. \n\n3. The method outperforms other federated algorithms over a wide array of benchmarks. There is apparently no need to accumulate anything beyond 2-hop features. \n\n4. Convergence guarantee is provided with very standard non-convex, non-iid FL assumptions. ", "weaknesses": "1. The one neighbor case wasn't adequately addressed. If the graph is heavily partitioned so there are many cross-client edges leading to a single neighbor, dropping the neighbor might not be appropriate. It was suggested differential privacy could be added to the single-neighbor accumulation but this will certifiably affect convergence, which would have been interesting to study.\n\n2. The need for quantization/rounding via the encryption scheme was a bit rushed -- the decryption might not be perfect (see questions). ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We highly appreciate your opinions especially \"Algorithm is astoundingly simple\", which is also our goal in designing the algorithm.\n\n>**For weakness 1: the one neighbor case wasn't adequately addressed.**\n\nWe agree that there could be cases when the graph is heavily partitioned and also nodes have one neighbor in other clients, although such cases are likely unusual in natural federated graphs. It is promising to potentially incorporate differential privacy in this extreme setup to provide an adequate privacy guarantee [1][2]. We are planning to include more discussions in the paper on tradeoffs between privacy and utilities from applying differential privacy.\n \n[1] Releasing Graph Neural Networks with Differential Privacy Guarantees. Transactions on Machine Learning Research 2023.\n[2] Federated learning with differential privacy: Algorithms and performance analysis. Transactions on Information Forensics and Security 2020.\n\n>**For weakness 2 and question 1: encryption scheme**\n\nAs in Appendix G.2, the encrypted data can be exactly recovered and does not have a performance drop. The rounding we refer to here is merely a conversion from using floating point representation of binary values back to binary numbers. For example, we might have 1.000000000000003 in our CKKS scheme to represent the binary value of 1, where the error is introduced in the floating point representation and CKKS scheme errors, but the magnitude of these errors is usually negligible such that we can easily “round” them to their true values. This need of conversion is because we only use the CKKS scheme (approximation scheme for real numbers) in our system to avoid extra overheads and system complexity from using different HE schemes for different types of values (for example, using CKKS for real numbers while using BGV for integers or using FHEW for boolean values).\n"}, {"review_id": "STbeaXbT5y", "reviewer": "Reviewer_BmP4", "summary": "The manuscript studies a semi-supervised node classification task using graph convolutional networks (GCNs). Specifically, motivated by the growth of the input graph (data) size, this paper considers a federated learning setting in which training is performed in a distributed manner, by partitioning the underlying graph and assigning each subgraph to a corresponding client. To deal with the communication overhead of the cross-client edges connecting graph nodes which need to be known for the target task, the paper proposes an algorithm that the central server first aggregates the information needed for each node in a client and then sends it to the designated node, rather than sending each information multiple times. The manuscript analyzes the tradeoff between the convergence rate of the algorithm and the communication overhead; in addition, a significant reduction on the communication cost with a reasonable accuracy is demonstrated through the experiment.", "questions": "+ The reviewer is wondering how the communication cost is measured in experimental validation (e.g., units).\n+ Is the idea of aggregating cross-client edge information at the central server and sending the aggregated information (instead of sending each multiple times) to each client first proposed by this manuscript?", "limitations": "+ The assumption that the cross-client edges of client $k$, denoted by $\\mathcal{E}_k^c$, are known to the client $k$ seems impractical due to the privacy issues.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "+ The problem is of sufficient interest since GNNs takes large-scale graphs as inputs, which can come with a heavy computational burden and may require huge storage costs.", "weaknesses": "+ It seems like the empirical results demonstrate that the proposed algorithm comes with a marginal gain compared to FedSage+ (Zhang et. al. 2021). ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your valuable comments!\n\n>**For weakness: marginal gain of accuracy compared to FedSage+**\n\nWe agree that FedSage+ often achieves good accuracies. However, the main contribution of FedGCN is that it requires 100X less communication cost by using a pre-training communication round, without compromising accuracy. FedGCN can also ouperform FedSage+ in some settings. Ideally, FedSage+ can have a close performance to that of FedGCN(1-hop), as shown in Table 2. However, as in Fig. 5, FedGCN(2-hop) has 5% better accuracy than FedGCN(1-hop) (the upper bound of FedSage+) as the number of clients increases, which means FedGCN needs more hops of communication in such a cross-device setting to achieve high accuracy. We expect that it will outperform FedSage+ more dramatically in such a setting.\n\n>**Question: how the communication cost is measured?**\n\nIt is calculated by the overall length of arrays needed to be sent, which is independent of the implementation. E.g. the client needs to send an array {1, 0, 1, 0} to the server, the communication cost is then 4. In this way, the cost can be independent of the implementation. Compression techniques may make the actual communication cost much lower than the array size. The code is also provided to reproduce.\n\nIn Fig. 4. the communication cost of distributed GCN can be 10^9 for Ogbn-Arxiv, which works out to several GBs of communicated data. For Ogbn-Products (2,449,029 nodes), it is hundreds of GBs. FedGCN requires 100X less communication cost. \n\nIn practical businesses (e.g. billions of nodes in Amazon and Facebook), the communication cost of distributed methods is prohibitive with extremely high latency at every training round. FedGCN's single pre-communication round can thus greatly improve performance.\n\n>**Question: Is the idea of server aggregation of cross-client edge first proposed by this manuscript?**\n\nYes. A preliminary version of FedGCN required clients to communicate with each other to aggregate the cross-client edge information, which has privacy leakage. To resolve the issue, we designed the current server aggregation scheme after realizing that the server can perform such aggregation and the homomorphic encryption can also prevent privacy leakage on the server side.\n\n>**Cross-client edges are known to the client seems impractical**\n\nThe cross-client edges typically exist in both clients, which we believe is common and practical. Intuitively, this is due to the fact that edges are generated when nodes at clients interact with each other. Thus, the interaction record, though not personal node characteristics, is then naturally stored at both nodes, i.e., in both clients. We provide some examples below and will use them to clarify this point in the paper’s introduction.\n\nFor example, in Amazon, a graph may represent buying behaviors (edges) that exist between users (nodes) in two countries (clients). Users in one country want to buy items in another country. The records of these transactions between users in different countries (i.e., the cross-client edges) are then stored in both clients. Due to General Data Protection Regulation (GDPR), however, sensitive user information (node features including name, zip code, gender, birthday, credit card number, email address, etc.) cannot be stored in another country. Including cross-country transactions (cross-client edges) is key for training models that detect international money laundering and fraud.\n\nAnother example is online social applications like Facebook and LinkedIn. Users in different countries can build connections with each other (e.g., a person in the United States becoming Facebook friends with a person in China). The users in both the U.S. and China would then have a record of this friendship link, while the personal user information cannot be shared across countries."}]

Author rebuttal:

Meta-review: The paper is well written and made some interesting contribution for federated learning in graph neural networks. The authors are encouraged to polish the paper to clarify the motivation of the work, and clearly present and motivate their assumptions.
Decision: Accept (poster)