GLASU: A Communication-Efficient Algorithm for Federated Learning with Vertically Distributed Graph Data
Authors: Xinwei Zhang
Mingyi Hong
Jie Chen
Venue: Submitted to ICLR 2023 (2023)
Keywords: Federated Learning
Graph Neural Network
Feature Distributed Federated Learning

Abstract: Vertical federated learning (VFL) is a distributed learning paradigm, where computing clients collectively train a model based on the partial features of the same set of samples they possess. Current research on VFL focuses on the case when samples are independent, but it rarely addresses an emerging scenario when samples are interrelated through a graph. For graph-structured data, graph neural networks (GNNs) are rather competitive machine learning models, but a naive implementation in the VFL setting causes a significant communication overhead; moreover, the analysis is faced with a challenge caused by the biased stochastic gradients. In this paper, we propose a model splitting method that splits a backbone GNN across the clients and the server and a communication-efficient algorithm, GLASU, to train such a model. GLASU adopts lazy aggregation and stale updates to skip aggregation when evaluating the model and skip feature exchanges during training, greatly reducing communication. We offer a theoretical analysis and conduct extensive numerical experiments on real-world datasets, showing that the proposed algorithm effectively trains a GNN model, whose performance matches that of the backbone GNN when trained in a centralized manner.

Under review as a conference paper at ICLR 2023
GLASU: A COMMUNICATION-EERICER. ALGORITHM FOR FEDERATED LEARNING WITH VERTICALLY DISTRIBUTED GRAPH DATA
Anonymous authors Paper under double-blind review
ABSTRACT
Vertical federated learning (VFL) is a distributed learning paradigm, where com- puting clients collectively train model based on the partial features of the same set of samples they possess. Current research on VFL focuses on the case when samples are independent. but it rarely addresses emerging scenario when ples are interrelated through a graph. For graph-structured data, graph neural net- competitive machine learning models, but naive implementa-
works (GNNs) tion in the VFL setting causes a significant communication overhead. Moreover, the analysis of the training is faced with challenge caused by the biased stochas- tic gradients. In this paper, we propose a model splitting method that splits a back- bone GNN across the clients and the server and a communication--ffiiieenn algo- rithm, GLASU, to train such model. GLASU adopts lazy aggregation and stale updates to skip aggregation when evaluating the model and skip feature exchanges during training, greatly reducing communication. We offer theoretical analy- sis and conduct extensive numerical experiments on real-world datasets, showing that the proposed algorithm effectively trains a GNN model, whose performance matches that the backbone GNN when trained in a centralized manner.
INTRODUCTION
Vertical federated learning (VFL. is a newly developed machine learning scenario in distributed optimization, where clients share data with the same sample identity but each client possesses only a subset of the features for each sample. The goal is for the clients to collaboratively learn model based on all features. Such a scenario appears in many applications, including healthcare, finance, and recommendation systems (Chen et al. 2020b Liu et al. (022). For example, in healthcare, each hospital may collect partial clinical data of patient such that their conditions and treatments are best predicted through learning from the data collectively; in finance, banks or e-commerce providers may jointly analyze a customer's is credit with their trade histories and personal information; and in recommendation systems, online social/review platforms may collect a user's comments and reviews left at different websites to predict suitable products for the user.
Most of the current VFL solutions (Chen et al. 2020b Liu al.. 2022) treat the case where sam- ples are independent, but omit their relational structure. However, the pairwise relationship between samples emerges in many occasions and it can be crucial in several learning scenarios, includ- ing the low-labeling-rate scenario in semi-supervised learning and the no-labeling scenario in self- supervised learning. Take the financial application as an example: customers and institutions are related through transactions. Such relations can be used to trace finance crimes such as money laun- dering, assess the credit risk of a customer, and even to recommend products to them. Each bank and e-commerce provider can infer the relations of the financial individuals registered to them and create a relational graph, in addition to the individual customer information they possess.
One of the most effective machine learning models to handle relational data is graph neural networks (GNNs) (Kipf & Welling 2016, Hamilton et al. 2017 Chen et al. 2018 Velickovic et al. 2018 Chen et al. 2020a). This model performs neighborhood aggregation in every feature transformation layer, such that the prediction of graph node is based on not only the information of this node but also that of its neighbors. Although GNNs have been used in federated learning, majority

---

Under review as a conference paper at ICLR 2023
Server
Client 3
Client 2
Client
Full fenture:
Full grap::
Figure 1: Data isolation of vertically distributed graph strph-strueture data over three clients.
of the cases therein are horizontal: each client possesses a local dataset of graphs and all clients collaborate to train unified model to predict graph properties, rather than node properties (He al. [202T] BBaram & Rekik [202]]XX Xie et al. [2021). Our case is different. We are concerned with subgraph level, vertical federated learning (Zhou et al. 2020 Ni et al.) 202I): each client holds subgraph the global graph, part of the features for nodes in this subgraph, and part the whole model; all clients collaboratively predict node properties. Our vertical setting is exemplified by not only the partitionning of node features, but also the (sub)graphs among the nodes.
The setting under our consideration is fundamentally challenging, because fully leveraging features within neighborhoods causes an enormous amount of communication. One method to design and train GNN is that each client subgraph and the server aggregates these representations to make predictions (Zhou et al. 2020). The drawback of this method is that the partial features of node outside one client's neighborhood are not used, even if this node appears in another client's neighborhood. Another method to train GNN to simulate centralized training: transformed features of each node are aggregated by the server, from where neighborhood aggregation is performed (Ni et al. 2021). This method suffers the communication overhead incurred in each layer computation.
local GNN extract node representations from its
In this work, we propose federated GNN model and communication-effiiiee training algorithm, named GLASU, for federated learning with vertically distributed graph data. The model split across the clients and the server, such that the clients can use a majority of existing GNNs as the backbone, while the server contains no model parameters. The server only aggregates and dissem- inates computed data with the clients. The communication frequency between the clients and the server is mitigated through lazy aggregation and stale updates (hence the name of the method), with convergence guarantees. Morcover, GLASU can be considered as a framework that encompasses many well-known models and algorithms as special cases, including the work of Liu et al. (2022) when the subgraphs one are skipped, the work of Ni et al. (2021) when no aggregations are skipped, and centralized training when only single client exists.
absent, the work of Zhou al.] (2020) when all aggregations but the final
We summarize the main contribations of this work below:
Model design: We propose a flexible, federated GNN architecture that is compatible with a ma- jority of existing GNN models.
We propose the communicatoon-eficiien GLASU algorithm train the model. Therein, lazy aggregation saves communication for each joint inference round, through skipping some aggregation layers in the GNN; while stale updates further save communication by allowing the clients to use stale global information for multiple local model updates.
Algorithm design:
Theoretical analysis: We provide theoretical convergence analysis for GLASU by addressing the challenges of biased stochastic gradient estimation caused by neighborhood sampling and corre- lated update steps caused by using stale global information.
Numerical results: We conduct extensive experiments, together with ablation studies, demon- strate that GLASU can achieve a comparable performance as the centralized model on multiple datasets and multiple GNN backbones, and that GLASU effectively saves communication.
2

---

Under review as a conference paper at ICLR 2023
1.1 PROBLEM SETUP
Consider M clients, indexed by m = 1,..., M, each of which holds a part of a graph with the node feature matrix X E I. Nxd and the edge set E. Here, N is the number of nodes in the graph and d is the feature dimension. We assume that each client has the same node set and the same set of training labels, y, but different private edge set &m and non-overlapping node feature matrix Xm E xdd,, such that & = m==1 the client dataset Dm (Xm, Em. and the full dataset as D = (X, &, y J- The task is for the clients to collaboratively infer the labels of nodes in the test set. See Figure [| for an illustration.
- &ms X = [X1...., X. and = Em dmm We denote
1.2 GRAPH CONVOLUTIONAL NETWORK
The graph convolution network (GCN) (Kipt & Welling, 2016) is a typical example of the family of GNNs. Inside GCN, graph convolution layer reads
H + 1] (A(E) HIJ W!I..
(1)
where a-) denotes the point- point-wise nonlinear activation function, AEE E NNN denotes the adja- cency matrix defined by the edge set & with proper normalization, H|l E R Nxd[f denotes the node representation matrix at layer I, and W E x=d[() denotes the weight matrix at the same layer. The initial node representation matrix H[O] X. The classifier is denoted as ý = f [H) W with weight matrix W[L] and the loss function is denoted as f(y,)) 9). Therefore, the overall model parameter is W = (W[O).... WIL - 1], W[Z].
Mini-batch training of GCN (and GNNs in general) faces scalability challenge, because to compute one or a few rows of [T. (i.e., the representations of mini-batch), requires more and more rows of H[LLLLO 1]. H 2]. recursively, in light of the multiplication with A(E) in ( This is known as the explosive neighborhood problem unique to graph-structured data. Several sampling strategies were proposed in the past to mitigate the explosion; in this work we adopt the layer-wise sampling proposed by FastGCN (Chen et al.] 2018). Starting from the output layer L, which is associated with a mini-batch of traming nodes, SIL]. we iterate over the layers backward such that at layer we sample a subset of neighbors for Sll + 1). namely S[]]. In doing so, at each layer we form a bipartite graph with edge set [(S + S(1) (i.j))l E S|I 1).5 E S[]].. Then, each graph convolution layer becomes
+ 1||ST + 1]] a ((((S) 1], SVD) H [S WH)).
(2)
where A +
+1. ST)) E R ((++)) [S|]]] is a properly scaled submatrix of A and H[[][[
denotes the rows of H[] corresponding S(]]. Such mini-batch sampling and training procedure
fundamentally differs from the usual mini-batch training for non-graph data in VFL.
1.3 RELATED WORKS
Federated learning on graph data generally fall under two categories, horizontal and vertical. The horizontal case can be considered graph-level, where each client possesses collection of graphs and all clients collaborate to train unified model to predict graph properties (Zhang et al.) 2021 He
al. 2021 Bayram Rekik 202T Xie al. 202T Applications include predicting molecula lar properties (ie et al. 2021) and learning connectional brain templates (Bayram & Rekik 2021 On the other hand, the vertical case can be considered subgraph-level, where each client holds subgraph of the global graph, a part of the node features, and a part of the whole model (Zhou ett al. 22200) Ni et al. 2021). The clients aim to collaborativeyy train global model with the partial features and subgraphs to predict node properties (see Figure []. Existing methods either fail to fully leverage the neighborhood information (Zhou et al. (0200) or incur expensive communication (Ni et al. 202T). Our approach addresses these shortcomings.
An additional scenario that does not fit into the above common categories is a node-level federated learning: the clients are connected by graph and thus each of them is treated as a node. In other words, the clients, rather than the data, are graph-str strpp-structured. For example, in Lalitha et al. (2019) and Meng et al. (201), each client performs learning with its own data and they exchange data
3

---

Under review as a conference paper at ICLR 2023
through the communication graph; whereas in Caldarola al. (2021) and Rizk & Sayed (2021) the server maintains the graph structure and uses a GNN to aggregate information (either models or data) collected from the clients.
2 PROPOSED APPROACH
In this section, present the proposed model and the training algorithm GLASU for federated learning on vertically distributed graph data. The neighborhood aggregation in GNNs poses com- munication challenges distinct from conventional VFL. To mitigate this challenge, propose lazy aggregation and stale updates to effectively reduce the communication between the clients and the server, while maintaining comparable prediction performance as centralized models. For notational simplicity, we present the approach by using the full-graph notation (I) but note that the implemen- tation involves neighborhood sampling, where more precise notation should follow (2) and that one can easily change the backbone from GCN to other GNN architectures.
2.1 GNN MODEL SPLITTING
We split the GNN model among clients and the server, approximating a centralized model. Specifically, each GNN layer contains two sub-layers: the client GNN sub-layer and the server aggregation sub-layer. At the 1-th layer. each client computes the local feature matrix
[ []] = a (A(Em) Hm Wmll)
with the local weight matrix Wm [1) and the local graph Em, where we use the superscript + to denote local representations before aggregation. Then, the server aggregates the clients' representations and outputs H[| 1] as
H + 1] Agg H [].............. ................................ H (4).
where Agg(.) is an aggregation function. In this paper, only consider parameter- free aggrega- H [ = M Σm= + [ and con- catenation Cat(H [4, [ [4) = H [..... H [4]]. The server broadcasts the aggregated H to the clients that computation proceeds to the next layer. In the final layer, each client computes a prediction. This layer the same among clients because they receive the same HL..
tions, examples of which include averaging Avg H [1]
The aggregation operations of choice have few advantages.
Parameter-fie Since the operations do not contain any Icarnable parameters, the server does not need perform gradient computations.
Memory-less: In the backward pass, these operations do not require data from the forward pass to back-propagate the gradients. For averaging, the server back back-propagater 3 H + to each client, while for concatenation, the server back-propagates the corresponding block of aH( + 1].
imm-lemen:: The server implementation is obviously easy because of the parameter-fire free and memory-less nature. Morcover, they enable parallelization and pipelining.
We illustrate in Figure the split of GNN layer among the clients and the server. Although our approach resembles federated split learning (SplitFed) (Thapa et al.) (022). there is a fine distinc- tion. In SplitFed, each client can collaborate with the server to perform inference model updates without accessing information from other clients; while in our case, all clients collectively perform the job. Our approach also differs from conventional VFL that splits the local feature processing and the final classifier among the clients and the server respectively, such that each model update re- quires a single U-shape communication (Chen et al. 2020b). our case, due the graph structure, each GNN layer contains one client-server interaction and the number of interactions equal to the number GNN layers (we will relax this in the following subsection).
Note that there are two types of aggregations in model. One is the neighborhood aggregation (multiplying with matrix A(E,)) as a signature of GNNs, that occurs in each client locally and incurs communication between the clients and the server. The other relates the communi- cation that happens when the server gathers the clients' partial representations and broadcasts back the aggregated representation.
4

---

Under review as a conference paper at ICLR 2023
Server Aggregation Layer
Server Agg. Layer (Skipped)
Server Agg. Layer
RE11
H[1]
H[L]
Client 3
Client
83
Client 2
Client 2
92.
Client GNN Layer 2
Client
81
Classitier
Client Layer
16,10
Client Data D
Illustration of the split model on M 3 clients with lazy aggregation. In the model, the second server aggregation layer is skipped due to lazy aggregation, and the graph size used by each layer gradually decreases due neighborhood sampling.
Figure 2:
2.2 LAZY AGGREGATION
The development in the preceding subsection approximates centralized model, but it is not com- munication friendly because each layer requires one round of client-server communication. We propose two communication-sawe strategies in this subsection and the next. We first consider lazy aggregation, which skips aggregation in certain layers.
aggregation each layer, specify subset of K indices, I (4,-.., Ix] C [L], such that aggregation performed only at these layers. That is, at a layer E I, the server performs aggregation and broadcasts the aggregated representations the clients, serving as the input to the next layer:
Instead of performing
Hm [1 1] H(1 + 1];
while layer & I, each client uses the local representations as the input the next layer:
H + 1] = H
By doing so, the model skips the server aggregation sub-layer between 4. and 4+1. such that the amount of communication reduced from ((L) OK)).
There is subtlety caused by neighborhood sampling: it requires additional rounds of commu- nication. Neighborhood sampling done similarly to FastGCN (see Section 1.2p. but note that whenever server aggregation is performed, it must be done the same set of sampled nodes across clients. Hence, the server takes the union of the clients' index sets S...(x.] [4x] and broadcasts S144] m=1 Sm[42] to the clients. On the other hand, when server aggregation is skipped at an layer & I, each client can use own set of sampled nodes, S,, [1). that may differ across clients. Such procedure is more flexible than conventional VFL., where strict sample synchronization is enforced. The sampling procedure summarized in Algorithm in the appendix.
2.3 STALE UPDATES
To further reduce communication, we consider stale updates, which skip aggregation in certain iterations and use stale node representations perform model updates. The key idea fix the mini-batch, including the sampled neighbors at each layer, for training Q iterations. In every other Q iterations, the clients store the aggregated representations at the server aggregation layers. Then, in the subsequent iterations, every server aggregation is replaced by local aggregation between client's up-to-date node representations and other clients' stale node representations. By doing so, the clients and the server only need to communicate once in every Q iterations.
Specifically, let a round of training contain Q iterations and use t to index the rounds. At the beginning of each round, the clients and the server jointly decide the set of nodes used for training at each layer. Then, they perform joint inference on the representations H [[] at every layer I I. Each client will store the "all but m" representation H'. .n!? through extracting such
5

---

Under review as a conference paper at ICLR 2023
Algorithm Training Procedure. All referenced algorithms are detailed in the appendix.
for t O,..., T do
2:
Server/Client: Sample {St 1 with Algorithm 2
1 t> 0
3: Client: W
W
-
4:
Server/Client:
H m + hhe = JointLnference(WW (W Dn, (S (o)) (Algorithm
5: for -= 0........
do
6:
for clients in parallel do
7:
Wha++ LocalUpdate(WW) (W Dm, 1 Bi (H-m. 1 + 1)}ez). (Algorithm
8:
end for end for
9:
end for
11:
Output: (WL.)M m==1
information from the aggregated representations H 1]:
H m + 1] = Extract (H + 1]. (.,H..1)))
For example, when the server aggregation is averaging, the extraction is
1 M
Extract H [[ (1) H
H
Afterward, the clients perform Q iterations of model updates, indexed by 0.... Q - 1. on the local parameters W
m in parallel, using the stored aggregated information H²m!! + 1] whenever server aggregation is supposed to happen. In other words, the server aggregation is replaced by computation done locally, thus reducing a significant amount of communication. Because H' H'm,, !!
is computed by using stale model parameters (W "'''mm zim at all iterations + 0, this approach called "stale updates."
The details are summarized in Algorithm) 1 with subroutines given in Appendix
2.4 SPECIAL CASES
interesting to note that our model and the training algorithm encompass several well-known models and algorithms as special cases.
Conventional VFL. VFL algorithms can be viewed as a special case of the proposed algorithm, where A(E..) 7 for all m. In this case, neighhorhood sampling is needed and GLASU reduces to Liu et al. (002)).
2220 is special case of our model, with K = 1; i.e., no communication is performed between the server and the clients except the final prediction layer. In this case, the clients omit the connections absent in the self subgraph but present in other clients' subgraphs. The model of Ni et al. (202T) is also special case of our model. with K L. This case requires communication at all layers and is less efficient.
Existing VFL algorithms for graphs. The model of Zhou
Centralized GNNs. When there is a single client (M = 1), our setting is the same as centralized GNN training. Specifically, by letting K and properly choosing the server aggregation function Agg(-), our split model can achieve the same performance as centralized GNN model. Of course, using lazy aggregation (K + L) and choosing the server aggregation function as concatenation or averaging will make the split model different from a centralized GNN.
2.5 PRIVACY
Our training algorithm GLASU enables privacy protection because it is compatible with existing privacy preserving approaches, including secure aggregation (SA) and differential privacy (DP).
SA [Bonawitz et al. 2017 Hardy et al. (017) is form secure multi-party partt computation approach used for aggregating information from group of clients, without revealing the information of any

---

Under review as a conference paper at ICLR 2023
individual. This can be achieved by homomorphic encryption (Li et al. 2010 Hardy et al. 2017). 7 In our case, when the server aggregation is averaging, homomorphic encryption can be directly applied.
DP (Wei et al. 2020 is probabilistic protection approach. By injecting stochasticity to the local outputs, this approach guarantees that any attacker cannot distinguish the sample from the dataset up to certain probability. DP can be applied either solely in combination with SA to our algorithm in the server-client communication, to offer privacy protection on the client data.
3 CONVERGENCE ANALYSIS
With lazy aggregation and stale updates, GLASU is guaranteed to converge. To start the analysis, denote by S = {S [0]==,m== the samples used at round t (which include all sampled nodes at different layers and clients); by S = ss [L] the batch size; and by L(W; S) the training objective, which evaluated at the overall set of model parameters across clients, W = [WmJm=i and batch of samples, S.
The loss function & is Gy-smooth with T.g-Lipschitz gradient; and client's prediction function fm is G-ssmooth with L Lipschitz gradient. A2: The training objective L(W: is bounded below by finite constant C. A3: The samples S are sampled from D following Algorithm 2 in Appendix A
few assumptions are needed (see Appendix B.1 for formal statements). A1:
For any round l and iteration g in the round, GLASU admits the following convergence guarantee. Theorem 1. Under assumptions AI-A3, by running Algorithm 7 with o Co-(1-2QAM) with
probability least p 6, the averaged gradient norm is bounded by:
1 T-1Q-1
DD 2(C(W0.)) --) 28nM (Co + M +Q) o, (3)
ΣE
TQ Q=0
nTQ
where Co = GeLy + G is constant and a is a function of logo(T//5)) Ly, Lgg Gy and Gg-
The detailed proofs are presented in Appendix R Two key challenges the analysis are: 1) the stochastic gradient estimation of the network is biased (i.e., Es (LW;;S) * VL(W; D)), even in centralized models; and 2) the stale updates in one communication round are correlated, as they are updated with the same samples. Hence, the general unbiasedness and independence assumptions on the stochastic gradients the analysis of SGD-type algorithms do not apply. Instead, we follow the analysis inmaezeani al. (2020) to bound the variance of the stochastic gradient in centralized GCN training, and extend the analysis in Liu et al. (2022) for VFL with correlated updates to our case with biased gradients.
NUMERICAL EXPERIMENTS
In this section, conduct numerical experiments variety of datasets and demonstrate the effectiveness of GLASU training with distributed graph data. We first compare the performance of GLASU with those tackling related settings under different assumptions on data distribution and communication. Then, we conduct ablation studies to show the equal criticality the three components (GNN backbone, lazy aggregation, and stale updates) of GLASU. The experiments are conducted on a distributed cluster with three Tesla V100 GPUs communicated through Ethernet.
4.1 DATASETS
We use seven datasets (in three groups) with varying sizes and data distributions: the Planetoid col- lection (Yang et al. 2016), the HeriGraph collection (Bai et al. (2022), and the Reddit dataset (Hamil- ton et al., 2017). Each dataset in the HeriGraph collection (Suzhou, Venice, and Amsterdam) con- tains data readily distributed: three subgraphs and more than three feature blocks for each node. Hence, we use three clients, each of which handles one subgraph and one feature block. For the other four datasets (Cora, PubMed and CiteSeer in the Planetoid collection; and Reddit), each tains one single graph and thus we manually construct subgraphs through randomly sampling the edges and splitting the input features into non-overlapping blocks, that each client handles one
7

---

Under review as a conference paper at ICLR 2023
Dataset
# (Sub)graphs
Nodes
# Edges
# Features
Classes
Cora
1
2, 708
10, 556
1, 4.3
PubMed
1
19, 717
88, 648
500
CiteSeer
1
3,327
9, 104
3, 703
Suzhou
3
137
916, 496
979
Venice 3
2,951
534,513
979
Amsterdam
3
727
2,17 171
979
Reddit
232, 965
114,
615, 892
602
41
Table I: Dataset summary. For a dataset that contains single graph, each the clients holds sampled subgraph from it. For the HeriGraph datasets, there are M 3 clients, each of which holds a given subgraph.
Dataset
Cent. (%)
StAl. (%)
Sim. (%)
GLASU-I (%)
GLASU-4 (%)
Cora
80.9 0.6
74.6
80.1
81.0
80.3 1.3:12
PubMed
84.9 + 0.6
0.5
1.2
82.3 + 1.6
83.8 + 1.8
CiteSeer
70.2
6.54
70.0 1.2
68.8
Suzhou
0.3
0.9
0.6
92.7 1.4
9.8
Venice
0.5
3.1
9.3
92.2 - 0.6
91.0
Amsterdam
94.6
5
0.8
93.1 = 0.8
94.9
Reddit
95.6 + 0.1
87.3
9.7
95.7 1 0.6
94.7 1.1
Table Test accuracy (%) on different datasets. The compared algorithms are Centralized training (Cent.), Standalone training (StAL.), Simulated centralized training (Sim.), GLASU with no stale updates, i.e., Q = (GLASU-1), and GLASU with stale updates Q = (GLASU-4).
subgraph and one feature block. The dataset statistics are summarized in Table and more details are given in Appendix C.T
4.2 RESULTS
We compare GLASU with three training methods: a) centralized training, where there is only single client (M = 1), which holds the whole dataset without any data distribution and communi- cation; b) standalone training, where each client trains model with its local data only and they do communicate; c) simulated centralized training (Ni et al. (021), where each client possesses the full graph but only the partial features, so that it simulate lates centralized training through server aggregation each GNN layer. None of these compared methods fits VFL but they offer good refer- ences for understanding the performance of VFL. on graph data. Except for centralized training, the number clients through grid search. See Appendix C
3. The number of training rounds, T, and the learning rate 7) are optimized for details.
We use GCNII (Chen et 2020a) as the backbone GNN. One layer of GCNII reads
+ H H[+11= = ((1- (())))=((()-))))))
(a- 3/1 + B(())))
which effectively includes two residual connections. This backbone reduces over-smoothing and results in better prediction accuracy than GCN. We set the number of layers L 4 and the mini- batch size S = 16. For neighborhood sampling, sample three neighbors per node in S(1 and take the union of the sampled neighbors to form S(I). For lazy aggregation, we set
Table repoors the classification accuracy of GLASU and the compared training methods, after five runs. As expected, standalone training produces the worst results, because each client uses only local information and misses edges and node features present in other clients. The centralized training and its simulated version lead to similar performance, also as expected. Our method GLASU is quite comparable with these two methods. Using stale updates (Q = is generally outperformed by stale updates, but occasionally it is better (see PubMed and Amsterdam). The gain in using stale updates occurs in timing, as will be demonstrated in the ablation study next.
8

---

Under review as a conference paper at ICLR 2023
4.3
ABLATION STUDY
To further investigate how each component of the proposed approach affects the performance, we conduct ablation study the backbone GNN model, b) the lazy aggregation parameter K, and c) the stale update parameter Q. The experiments use PubMed and Planetoid for illustration.
Backbone model: We compare the performance GLASU on three backbone models: GCN, GAT (Velickovic et al. 22118), and GCNII The learning rate for each backbonoe is tuned to their best performance. The test accuracy on PubMed is shown in Figure We see that GLASU can take different GNNs as the backbone and reach similar prediction performance.
Lazy aggregation: We investigate the performance of GLASU with different numbers of aggre- gation layers. We use 4-layer GCNII as the backbone and set K = 1, 4. The test accuracy and the runtime are listed Table 3 We observe that the runtime decreases drastically when using fewer and fewer aggregation layers; from K 4 to K = 1, the reduction in runtime is 37.4% for PubMed and 58.2% for Amsterdam. Meanwhile, there appears to be sweet spot in terms of accuracy: K 2 performs the best.
PubMed
# Layer
K
==2
Test Accuracy
Accuracy (%)
82.5 + 1.0
83.8 1.8
82,2 0.7
0.6
Runtime (s)
130 + 12
96.6 9.9
81.3 + 6.5
Amsterdam
0.4
GAT
# Layer
K =
==2
K =
GCN
Accuracy (%)
93.6 + 0.7
94.9 0.4
92.0 + 1.7
GCNI
Runtime (s)
913 + 76
544
382 + 35
128
256
384
512
Commmniicatin T
Table 3: Test accuracy and runtime of GLASU with dif- ferent number of lazy aggregation layers K = 4, 2, 1 on PubMed and Amsterdam.
Figure 3: Test accuracy with different backbone GNNs on PubMed.
Stale updates: To investigate the time saving due to the use of stale updates, we experiment with few choices of Q: 8. and 16. We report the time reach the same test accuracy in Table We see that stale updates help speed up training by using fewer communication rounds; this trend occurs on the Amsterdam dataset even when taking Q large as 16. The trend also noticeable on PubMed, but at some point (Q 8) it is reverted, likely because it gets harder and harder to reach desired prediction accuracy. We speculate that the target 82% can never be achieved at Q = 16.
Stale Update
Q=2 2
Q
==4
Q=8
Q=
Accuracy (%)
82.5 + 1.6
82.0 2.4
82.1 + 0.3
N/A
PubMed
Runtime (s)
66.1 + 5.0
43.8 4.0
88.9 7.4
> 128
Accuracy (%)
89.2 0.4
8.7
90.7
=.5 0.5
90.3 + 1.1
Amsterdam
Runtime (s)
1323 + 44
521
44
250 24
Table 4: Runtime of GLASU with different number of stale updates Q 2, 6, 16, when reaching 82% test accuracy on PubMed and 89% on Amsterdam.
CONCLUSION
We have presented a flexible model splitting approach for VFL with vertically distributed graph data and proposed a communication-eeficiee algorithm, GLASU, to train the resulting GNN. Due to the graph structure among the samples, VFL on GNNs incurs heavy communication and poses an extra challenge in the convergence analysis, as the stochastic gradients are no longer unbiased. To overcome these challenges, our approach uses lazy aggregation to skip server-client communication and stale global information to update local models, leading to significant communication reduc- tion. Moreover, our analysis makes no assumptions on unbiased gradients. We provide extensive experiments to show the flexibility of the model and the communication saving in the training.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Nan Bai, Pirouz Nourian, Renqian Luo, and Ana Pereira Roders. Heri-graphs A dataset creation framework for multi-modal machine learning on graphs of heritage values and attributes with social media. ISPRS International Journal of Geo-Information, 11(9))469, 2022.
Hizir Can Bayram and Islem Rekik. A federated multigraph integration approach for connectional brain template learning. In International Workshop on Multimodal Learning for Clinical Decision Support, pp. 36-47. Springer, 2021.
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy- preserving machine learning. In proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1175-1191, 2017.
Debora Caldarola, Massimiliano Mancini, Fabio Galasso, Marco Ciccone, Emanuele Rodolå, and Barbara Caputo. Cluster-driven graph federated learning over multiple domains. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2749-27555 2021.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 2018.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph con- volutional networks. In International Conference on Machine Learning, pp. 1725-1735, PMLR, 2020a.
Tianyi Chen, Xiao Jin, Yuejiao Sun, and Wotao Yin. Vafl: a method of vertical asynchronous federated learning, arXiv preprint arXiv:2007.0660 2020b.
Will Hamilton, Zhitao Ying, and Jure Leskovee. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Stephen Hardy, Wilko Henecka, Hamish Ivey-Law, Richard Nock, Giorgio Patrini, Guillaume Smith, and Brian Thorne Private federated learning on vertically partitioned data via entity resolution and additively homomorphic encryption. arXiv preprint arXiv:
2017.
Chaoyang He, Keshav Balasubramaniaan Emir Ceyani, Carl Yang. Han Xie, Lichao Sun, Lifang He, liangwei Yang, Philip S Yu, Yu Rong, et al. Fedgraphnn: A federated learning system and benchmark for graph neural networks. arXiv preprint 1rXiv:2104.07144 2021.
Thomas N Kipf and Max Welling, Supe-supe classification with graph convolutional net- works. arXiv preprint arXiv: 1609.02000 2016.
Anusha Lalitha, Osman Cihan Kiline, Tara Javidi, and Farinaz Koushanfar. Peer-to-peer federated learning on graphs. arXiv preprint arXiv: 1901.1113.,1. 2019.
Fengjun Li, Bo Luo, and Peng Liu. Secure information aggregation for smart grids using homomor- phic encryption. In 2010 first IEEE international conference on smart grid communications, pp- 327-332. IEEE, 2010.
Yang Liu, Xinwei Zhang, Yan Kang, Liping Li, Tianjian Chen, Mingyi Hong, and Qiang Yang. Fedbcd: A communication-effice collaborative learning framework for distributed features. IEEE Transactions Signal Processing, 2022.
Chuizheng Meng, Sirisha Rambhatla, and Yan Liu. Cross-node federated graph neural network for spatio-temporal data modeling. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 1202-1211, 2021.
Xiang Ni, Xiaolong Xu, Lingjuan Lyu, Changhua Meng, and Weiqiang Wang. A vertical federated learning framework for graph convolutional network. arXiv preprint vrXiv:2206. /593, 2021.
Morteza Ramezani, Weilin Cong, Mehrdad Mahdavi. Anand Sivasubramaniam, and Mahmut Kan- demir. Gen meets gpu: Decoupling "when to sample" from "how to sample". Advances in Neural Information Processing Systems, 33: 13:18882-1188 18882218492, 2020.
10

---

Under review as a conference paper at ICLR 2023
Elsa Rizk and Ali H Sayed. A graph federated architecture with privacy preserving learning. In 2021 IEEE 22nd International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), pp. 131-135. IEEE, 2021.
Chandra Thapa, Pathum Chamikara Mahawaga Arachchige. Seyit Camtepe, and Lichao Sun. Splitfed: When federated learning meets split learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 8485-8493, 2022.
Joel A Tropp. An introduction matrix concentration inequalities. Foundations and Trendso in Machine Learning, 8(1-2)11-30, 2015.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. stat, 1050:4, 2018.
Kang Wei, Jun Li, Ming Ding. Chuan Ma, Howard H Yang, Farhad Farokhi, Shi Jin, Tony QS Quek, and Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. IEEE Transactions on Information Forensics and Security, 15:3454-3469, 2020.
Han Xie, Jing Ma, Li Xiong, and Carl Yang- Federated graph classification over non-iid graphs. Advances in Neural Information Processing Systems, 34:1 18389999-188,,, 2021.
Zhilin Yang. William Cohen, and Ruslan Salakhudinov. Revisiting semi sumi-supeeeised learning with graph embeddings. In International conference on machine learning, pp. 40 48. PMLR, 2016.
Huanding Zhang, Tao Shen, Fei Wu, Mingyang Yin, Hongxia Yang, and Chao Wu. Federated graph learning-a position paper. arXiv preprint arXiv:2105. 1009, 2021.
Jun Zhou, Chaochao Chen, Longfei Zheng. Huiwen Wu, Jia Wu, Xiaolin Zheng, Bingzhe Wu, Ziqi Liu, and Li Wang. Vertically federated graph neural network for privacy-preserving node classification. arXiv preprint 2005 2020.

---

Under review as a conference paper at ICLR 2023
A SUBROUTINES IN ALGORITHM
Algorithm Sampling Procedure
Client:
Server:
for = ,,..,, do
Uniformly and independently sample
Receive(S[(::)
indices S from training set. Broadcast(S[L). for k K 1,,...... do
Set Sm [4] = S14]-
for forl=10 14 1,. 1...., --1 do
Uniformly randomly sample indices S. []] from neighbors of Sm 1].
Aggregate(Snn (4.).
Compute S14x] = U Sm!(a].
end for
Broadcast( (S(4)).
Send(S 11) ifk 2.
end for
end for
Output: (sm1)
Algorithm 3 JointInference
Client:
Server: for / E I do
Input: W m. Dm [Sm!!E.
Set H [0] X,
Smm [0]
H + gg H 11 ..... H B).
for 1 = ... L do
Broadcast H + 1]. end for
1 = o (E + H,))
if E I then
Send H [4] to server
Receive H m +
H_m + 1 = Extract H. + 1), H
else
Set Hm + 1] H m
end if'
end for Output: (H_ml 1]1EE
Algorithm 4 LocalUpdate
Input: W Dm, (4) (H' m [1 + 1]her
Set H m [0] = Xm [St 05 [0]]
for 1 = O.... L do
H [1] = a (E
1), St []]) L (1)
if f then
Set H + 1| Agg H [1 + 1]. H H.g. (!])
else
Set (1 + 1| Hia.
end if
end for
Compute loss Lt.y = E f' (L), (L)) Output: W4.++1 mn Wh. 1/ Wt.
B PROOFS FOR SECTION
B.1 ASSUMPTIONS
Assumption 1 (Smooth function and Lipschitz gradient). The loss function Gmooth with Lepiipschitz gradient, iee. | W) Syy W G₁ w w'l Sw W) Vw-lly,S, W L W W VW,W W
12

---

Under review as a conference paper at ICLR 2023
and each client's prediction funciiioo fm is G-smoothh with Li-Lisschitz gradient. i.e, fl W mm) - -m (S, W Vw.,. fm (S, Wm) Vw.., (S, Wm ml S Ly l| - W''ll, Assumption 2 boundr-bounedd function), The training objective is bounded below; that is, there exists a constant L > 00 such that for all { (W,, m)) it satisfies that
Wm)ll S GG [ Wm
WWm. W m. V m.
C((W }) 2 -
Assumption 3 (Uniform sampling). At each iteration t, the server and the clients uniformly sample nodes (Sm with [S[]]| = -S, according to Algorithm 2
B.2 PROOF OF THEOREM
[
We first note the following useful relation:
||a b1|² ||a c bll² < (1 + a) ||a - cl (1 - ||c b1] Va
(4)
For notation simplicity, let us denote the expectation conditioned on all the information before iter- ation as
E'I
1 / ..... W0.0 S S"
denote the "all-but-m" vector as (+)-m: (e.g., the collection of all client parameters except for client m W Wm {W m² mm)mmm); denote the client model updated with data as (S): denote the gradient evaluated with data S on parameter Wm m VL(W, (S), S); and denote the stacked (VS,W((S),S)
gradient of all clients
VL(W M ()). Then, the update rule can
be rewritten as:
W = ( - G
(5)
addition, let us define a virtual model sequence updated with fill data as W(D), i.e.
w = w <V (D),
(6)
We can bound the variance the stochastic gradient at any round and iteration g = with the following lemma:
Lemma 1 (Bounded variance). Under Assumptions variance of the stochastic gradient is bounded by:
with probability at least p 1 6, the
E' [|VL(W: VL(W: D)
S a,
A w independent of St.
(2d)
2dd
1 s
2d
where a = 64G log
+ 1281.
G
log
8
8
The main technique for proving this lemma is to use the matrix Bernstein inequality (Tropp) 2015)
bound the variance the stochastic gradients and the variance of the expectation for each client. The proof steps of Lemma | follows the same steps in the proof' for Lemmas and of Ramezani al. 2020), so we omit them here.
Further, we bound the Lipschitz constant of the total loss function in the following lemma:
Lemma (Lipschitz gradient). Under Assumptions 7 the full gradient and each partial gradient of the objective L(W,S) S) are Lipschitz continuous with uniform constant Co = Ge + G LL,L,
WwW, S) LwW' (."" < C. IW -W'l, WW,W W" Vw.., L(W, S) Vw. (WW
C W - w V W',
The proof of Lemma 2 is given below in Section B.3
With the above results, we begin our proof for Theorem
!
First, applying Lemma 2 we have:
L(W+.t1 D) L( (VL(W*', _ w
Co
W w
2
(8)
(VL(W"' D). G.
Con² |G
2
(8)
(|VL da |
|| D) - GL0 + Con
|
| |
|V(("'., -
13

---

Under review as a conference paper at ICLR 2023
where step (a) applies the update rule of Algorithm 4 and step (b) uses the fact that (a, b)
[|a|1 + [b11 ||a b1l).. Taking expectation, we have:
B'[2(W' D) L(W . D) - " E / D)
2 " (1 C/C) E' || + E' VL(W4.9, G
2
E' || D)
V .) 1
(1 (1- - (co0
EE' G + G E G
2
(6)
D)1
- 11 -1- -1 - G + E² G E'' -E'
7
1
E VL( D) - E G .
E'
E G G1
2
!
E'
VL(W.. D)1
1 - n | + C2
E* G E'' 1
Term
1 100 + 20,
E'
VL(W D) E' 1
(9)
where step (a) uses the fact that B(X)² ( + B(X-)) E(X))²
and step (b)
uses
with
=. Next, we bound Term and Term 2 in the above inequality separately.
B.2.1 BOUND OF TERM 1
First, we can rewrite B'I| - E' G as:
G - E G
E
Et [| Es (S)
(a)
M
(10)
E+
(D),
A
where step (a) uses the fact that E(X- - E(X))² < E(X 2)² for all constant Y. Then, bound A as follows. When = 0, by Lemma
we obtain that A I a holds with probability
1 - 5. In general, when y 2 have:
A
|IC (S)) -VCW (D). s']
+ 2
VL(W |]]
(11)
20 g.
[|W w (D)) 2 (C). vL(W D.1l"
(6) 208
[w wh + 20,
which holds with probability 1 - 6. Here, step (a) applies Lemma 2 to the first term and step (b)
applics Lemma to the second term. Then, we bound EE || - w in the above equation as:
B (S who (D))
W E'
v L(W Wi (8)), - Wio
v VL Wf (D), D)
7
m
0
14

---

Under review as a conference paper at ICLR 2023
E
WL (8))
VZ (D), D))
(0)
4-1 Σ
S 17 Q
E'
(5*), V (D), D)
0'=0
9-1
14
(12)
m
7'=0
where in step (a) we expand the updates to W with (5) and 6 step (b) cancels WLD and rearrange the terms; and step (c) applies the Cauchy-Schwand inequality. At this point, we have the following relations:
M
G EE' G
A
Ab
S
A < 2C6'12
Σ d'=0
A
20, V 2 1.
Note that g S Q. By choosing 2n 1. which implies that 17 S substituting the terms, we have the following bounds:
and by recursively
V2QC,*
n o. 14
1 $ 2+ 442r1 + 3
3 a,
(13)
14Mo
Ei| 4
- E' G M
2 + + 1
+ 3
0
3
This completes bounding the term B| G
E'' 1.
B.2.2 BOUND OF TERM 2
We have the following series of relations:
EA VL(W D) - E G 2
Σ
E. (W.,.( D) - Es (S).
m=1
(4)
Et Es Vw L(W Es (S).
(b)
M
C/ E
Es
- w
m=1
Σ m=1
c E Es
Σ
w wt.0
ml
m'sm
M
17
C/ E Es
Es
VL(WLd (') - (S),
m
L
W L.
(S): (S):
(
1/ C3
Σ Σ
M g-1
E' Es
VL(W
(*))
(S) (S)
m=19'=0
+
Σ
(s):
m m
15

---

Under review as a conference paper at ICLR 2023
M 9-1
@ TM + +1
Σ
EE' Es
(59)
m=
=
9-1 1
_ TM + +1)C89
Σ
E
o'=0
9-1
= - + 1)08a
E'
G
-
E²
o + +|
(14)
v'=0
where step (a) uses Assumption Jensen's inequality, that is
3 which states that is uniformly sampled from D, and applies
||E Vw.. ((W - Es (S)
< Es
(V)
step (b) applies Lemma 2 and uses the fact that ( 5*) evaluated on (S') and
w : in step (c) we expand the update steps until 1,0 with (5: step (d) applies Cauchy-Schward
inequality; in step (e) we reorder the sum and apply the i.i.d. Assumption 3 to S, S and in step (g)
plug in the definition of G. This completes bounding the term E' / D) - E' G
B.2.3 PROOF OF THE MAIN RESULT
Substituting the last term in 9 with 14) we obtain that the following holds with probability (1 5)e:
E' [(Wwott D) - C(W.. D)
" E' (VL(W",, 2 Co) |
2
+ 72 E² | E² 10
1 1 (M + 1 Σ Ed
| - E EE'G''
|
E GMaa |?]
2Cb
7'=0
S 7 E' ||/C
"7 (1
nL)
|E 1
2
+ Co |M + 1)0/9
Σ E² E G | 40=0
8-1
2Co
+ Cn (1 (1 Co) (M + 1) 1022) 1)=
14Mg 3
where in the second inequality, we set 1 S /200,' plug in and use the fact that q S Q. Averaging over O,........... O....,T and g = 0, ....., Q 1 and reorganizing the terms, we obtain:
E VC( 9 D)| nTQ
2 B[C(W") C((WT
TQ
1 1 Co (1 + (1 + n)) - (M +1) 1) 1))
Q-1Q-1
Σ
Σ
E
E
G
TQ
t=0
+ 2n/Co (1+ (1 + n/)) (C+)C))
(M 1) .nQ2 14Mo
2
3
which holds with probability at least holds with probability at least
(1-6)TQ, Let = 8' 8/TQQ E (0, 1); then, the above equation
(1 - 8' /TTTQ) T2 8/TQ x TQ = 1-8
Let
1 - Cu (1 (1 C6)) (M 1) Q²) 2 0,
16

---

Under review as a conference paper at ICLR 2023
(1) S VM+ICO
and apply Assumption 2
Then, we have
+ E D)]
T-1Q-1
2(C(W") -r)
28nM (Co + VM + o, (15)
TQ Q=0
nTQ
which holds with probability least 1 5, where
64 log 2dTQ
(c)+ + 5) log [2TQQ +11
128L3
This completes the proof of Theorem !
B.3 PROOF FOR LEMMA 2
In this subsection, we prove
Vww(WW) Vw-c(w') S C. || w
and
Vw.. C(W) - Vw <(W') Co l W
Note that Vw.., C(W) is sub-vector of VL(W"), so Vw ((W) Vw ((W))
5
W(W) LW Therefore, only need to prove the first inequality.
The gradient VZ(W) can be expanded as
VC(W) fm W)) (S, W)) Vwfm W) ve(fm) (mm)),
(16)
where in the last equation we omit the irrelevant variables. Then, we have
[VC(W) V<(W") [[V(())) V. (W) - v((()) ('m)) (V((f)) (m (W) Vf,(w))) + V((F)) fm (W"]
[[VE(m)) (1 (W) V. V., [[VV( V((S))) (w")
IAS W
(17)
[[VE(m)) Fm (W) V (w)) (W)]+ - VELW)IIT(
G.L, ( Wll + L, fm (W) (W))l Gj
(GoLy + + W - w'l.
where step (a) uses the fact that ||0 + bl < ||||| + |6] step (b) uses the fact that ||ab]] < ||a|] |[b]|
and in step (c) we apply Lemma (that is, for any G-smooth function g. its gradient is bounded as | < G) to the first and the fourth terms and Lipschitz gradient to the second and the third terms.
This completes the proof of Lemma
C EXPERIMENT DETAILS
C.1 DETAILS OF THE DATASETS
Planetoid Yang et al. 2016): This collection contains three citation datasets: Cora, PubMed, and CiteSeer. Fach dataset contains one citation graph, where the nodes represent papers and edges represent citations. The node features are a bag of words and the classification target is the pa- per category. In the experiment, each client holds a non-overlapping block node features and a subgraph that results from uniformly sampling 80% of the edges.
HeriGraph (Bai et al. 2022 : This collection contains three multi--oddl graph datasets, each of which is constructed from heritage data posted social media for particular city (Suzhou, Ams- terdam, and Venice). Each post contains user information, timestamp, geolocation, image, and text annotation. The posts are connected to form three subgraphs: a social subgraph, spatial subgraph,
17

---

Under review as a conference paper at ICLR 2023
and temporal subgraph. The social subgraph is formed based friendship and common-interss relations of the users. The spatial subgraph is formed based on the spatial proximity of the geolo- cations. The temporal subgraph is formed based the temporal proximity of the posts. Each post has three blocks image features and possibly text features; for classification, it belongs to one of nine heritage attributes. In the experiment, each client holds one of the three subgraphs and of the three image feature blocks.
Reddit (Hamilton et al. 2017): Reddit large online community where users post and comment on different topics. Each node represents a post and the features are the text of the post. Two posts are connected if the same user comments on both. The classification target is the community (subreddit) that a post belongs to. Similar to Planetoid, in the experiment, each client holds a non- overlapping block of node features and a subgraph that results from uniformly sampling 80% of the edges.
C.2 DETAILS OF THE HYPERPARAMETRE
Here we provide a list of hyperparameters for grid search in Table 5 The optimal set of hyperpa- rameters for each setting is tuned according the range listed in the table.
Hyperparameter
Grid search range
Hidden dimension of H[/]
{128, 192, 256, 384)
Batch size S
[16, 32}
Neighborhood sample size
(2.3, 4, 6, 8}
Training rounds T
(512, 640, 1024, 1152, 3200]
Learning rate 77
(1,2,3.5,5,
{10- 110 -00
Table 5: Hyperparameter grid search range for the numerical experiments.
18


Reviews:
[{"review_id": "fxbiBJb3QCs", "reviewer": "Reviewer_42nY", "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 investigates vertical FL on graph neural networks. A communication-efficient vertically-distributed training algorithm called GLASU was proposed, where the main idea for communication saving is lazy aggregation and stale updates. It was proved that the proposed algorithm can converge given that the loss function is smooth with Lipschitz gradient, lower-bounded and the sampling is uniform. Several experiments were conducted.", "summary_of_the_review": "This paper proposed GLASU, a communication-efficient vFL algorithm on graph neural networks. The convergence of GLASU is proved and some experiments are conducted. However, neither the theorem nor the experiment can prove that the communication cost is reduced. Also, the experiments are not strong enough to support the claim. Hence, the quality of the paper can be further improved.", "strength_and_weaknesses": "Strength: This paper is written clearly and reader-friendly. The mathematical proof of the theorem looks solid.\n\nWeaknesses: The most severe weakness of the paper is that the theorem and experiment did not support the motivation of the algorithm.\n\n    1. Communication-efficient. The motivation of the GLASU algorithm is to save communication. However, neither the theorem nor the experiment discuss the communication cost, which undermines the contribution of the paper.\n    2. Privacy is an important aspect in federated learning. But privacy is not discussed in this paper.\n    3. The experiment results are not clear enough. For example, in Table 2 and table 4, it is hard to see how Q affects the results. In Table 3, it is hard to see how K affects the results. The experiment results are not strong enough to support the claims of the paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": {}}, {"review_id": "WdPBDJwCwM", "reviewer": "Reviewer_q1q8", "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": "The paper focuses on learning graph neural networks (GNN) under the federated (FL) scheme. As for FL under vertically distributed data, \"each client holds a subgraph of the global graph, part of the features for nodes in this subgraph, and part of the whole model; all clients collaboratively predict node properties.\" The paper proposes lazy aggregation and stale updates to reduce the communication frequency between clients and the server.", "summary_of_the_review": "The novelty is lacking and the advantage of the proposed learning scheme is not clear.\n\nUpdate: I thank the authors' response. I will keep my initial review.", "strength_and_weaknesses": "Issues:\n1. The problem set up as it pertains to GNNs and vertical data is not well-motivated.\n2. The empirical evaluation is limited to one GNN model, GCNII (simple and deep convolutional network), and 3 clients of FL.\n3. The splitting of graph and features is not well explained.", "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": {}}, {"review_id": "TNT8k07-yEd", "reviewer": "Reviewer_jr7W", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The author works on the vertical federated learning for graph data. The author proposes a model splitting method to split the model to server and clients, and communication-efficient techniques such as lazy aggregation and stale updates for efficient training. Empirical results show similar performance to centralized training but a smaller wall-clock training time.", "summary_of_the_review": "The author proposes how to split model to server and clients for VFL on graph data, and proposes lazy aggregation and stale updates for communication efficiency. However, the novelty of those techniques is incremental, given the vast amount of communication-efficient works in distributed training.", "strength_and_weaknesses": "Strength:\nThe proposed method reduce the communication time via the proposed communication-reduction technique.\n\nWeaknesses/questions:\n1. The model splitting method is very straightforward (including both the averaging and concatenation), and it can hardly be counted as a novel method to me. \n2. The proposed lazy aggregation and stale updates are not novel techniques. They have been commonly adopted in distributed training.\n3. Is there any further elaboration of the theorem1? How does it compared to centralized training, standalone training, or existing VFL methods? What is the theoretical benefits?\n4. 3 clients in HeriGraph is so small. Does the proposed method scale to more clients? What is the client settings in other datasets?\n5. What are the real applications of VFL on graph data? Please introduce it along with the applications of horizontal FL in the first graph in related works.\n6. Is there any memory concern when \"Each client m will store the “all but m” representation\" ?", "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": {}}, {"review_id": "EdiMhJAxX33", "reviewer": "Reviewer_Hn4F", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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 method of communication-efficient federated learning framework for a vertically distributed graph. Specifically, a lazy aggregation rule is proposed to reduce the communication rounds. A new strategy called stale updates skips aggregation in specific iterations to reduce the cost during vertical training. ", "summary_of_the_review": "In general, the studied problem is interesting and important. In addition, the methodology is principled with three major merits as discussed above. However, the work still has some unaddressed concerns to well justify its technical and empirical contributions.", "strength_and_weaknesses": "Pros:\n1.The paper proposes a communication-efficient GLASU algorithm for federated GNN in a VFL manner.\n\n2. The extensive theoretical analyses are derived to validate the performance guarantees of the proposed method.\n\n3. The algorithm is evaluated on a number of real-world graph datasets to demonstrate the effectiveness of the proposed approach for VFL on graph data.\n\n\nCons:\n1.\tDuring the training, the clients have to send the aggregated embeddings to the server, which might cause privacy issues, like inference attacks or recovery attacks. It would be better if the author could discuss this in more detail.\n2.\tBased on my understanding, each client needs to train a local W by minimizing the loss function, which means that each client should hold labels which is a very strong assumption cause in real-world cases, one client usually kept the labels.\n3.\tThe most significant advantage of GNN is that it can aggregate the features through neighbors. However, the proposed method directly concatenates the embeddings of the sub-layer, and the embedding is generated by local clients who keep only partial edges of the whole graph. I do not think the average or concatenation operation can replace or approximate the propagation rule in GNN.\n4.\tFor lazy aggregation, how to choose the indices of K. Furthermore, the embedding of each layer is dependent, and the gradients are calculated by following the chain rules. If skipping one layer, how to keep the consistency of the gradient updates is a big concern.\n5.\tThe paper lacks clarity on how stale updates work and why the proposed method can work without influencing performance.\n6.\tFor Theorem, when T approaches infinite, the gradient norm is still upper-bounded by the second term, and it can not show that the proposed method will finally converge.\n7.\tThe experiments have no running time and accuracy compared with SOTA methods. Moreover, figure 3 shows an unexplainable pattern. It would be better if the author could discuss it in more detail.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": {}}, {"review_id": "5Ogj743izrX", "reviewer": "Reviewer_nqTt", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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 tackles the vertical Federated Learning (FL) scenario for graph-structured data. In particular, the authors first propose to update the node features calculated from every layer of Graph Neural Network (GNNs), distributed to multiple clients, simultaneously (i.e., at l-th layer, all clients share their node representations from the (l-1)-th layer, and then update the l-th layer node representations). After that, to make such the FL framework communication-efficient, the authors propose not only the lazy aggregation that shares node representations only at the particular layers, but also the stale update that receives node features of other clients from the server at the particular interval. The authors evaluate the proposed GLASU on the vertical subgraph-level FL scenarios, showing the effectiveness and the efficiency of GLASU.", "summary_of_the_review": "This is a borderline paper: the tackled problem is under-explored and the proposed method has a reasonable design choice; whereas, the experiment is weak, the novelty is mild, and the proposed GLASU might not be applicable to real-world scenarios.", "strength_and_weaknesses": "### Strengths\n* The tackled problem of vertical subgraph FL for graph-structured data is under-explored.\n* The proposed subgraph FL scheme with two algorithms for making it communication-efficient is novel, and interesting.\n* The authors make effort to theoretically analyze the convergence bound of the proposed GLASU, which is challenging since the estimated stochastic gradient is biased in vertical subgraph FL.\n\n### Weaknesses\n* The biggest concern is that every client participating in FL should be in the same stage, to share node representations of specific layers simultaneously between different clients, which is not realistic. Also, considering such the point, it is unclear whether the proposed GLASU, evaluated with 3 clients, is scalable to the larger number of clients (e.g., 10 or 30, which are not large though). I suggest authors to experiment with larger client numbers.\n* This paper is not positioned well against existing subgraph FL. In particular, there are several subgraph-level FL [1, 2, 3], and the considered vertical FL scenario is not the only subgraph-level FL. Therefore, I suggest authors to discuss clear differences between the previous subgraph-FL [1, 2, 3], and the targeted vertical subgraph FL. \n* The baselines are somewhat weak. The authors compare three baselines, and two (i.e., centralized and local training) of them are not the FL models. Also, the other compared baseline (i.e., Sim) is not directly comparable to the proposed GLASU, since they use different local subgraphs. I am wondering the authors can evaluate discussed methods (Zhou et al., 2020; Liu et al., 2022) by adapting them to the used experimental setups.  \n\n---\n\n[1] FedGNN: Federated Graph Neural Network for Privacy-Preserving Recommendation, KDD 2020.\n\n[2] Subgraph Federated Learning with Missing Neighbor Generation, NeurIPS 2020.\n\n[3] Personalized Subgraph Federated Learning, arXiv 2021.", "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