GLASU: A Communication-Efficient Algorithm for Federated Learning with Vertically Distributed Graph Data
Authors: Xinwei Zhang
Mingyi Hong
Jie Chen
Venue: Accepted by TMLR ()

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. In this work, we train a graph neural network (GNN) through VFL, where each client owns a part of the node features and a different edge set. This data scenario incurs a significant communication overhead, not only because of the handling of distributed features but also due to neighborhood aggregation in a GNN. Moreover, the training analysis is faced with a challenge caused by the biased stochastic gradients. 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 communication in neighborhood aggregation and in model updates, respectively, greatly reducing communication while enjoying convergence guarantees. We conduct extensive numerical experiments on real-world datasets, showing that GLASU effectively trains a GNN that matches the accuracy of centralized training, while using only a fraction of the time due to communication saving.

Published in Transactions on Machine Learning Research (04/2024)
GLASU: A Communication-Eficcin Algorithm for Federated Learning with Vertically Distributed Graph Data
Xinwei Zhang"i
zhan6234 @umn. edu
Department of Electrionl and Computer Engineering University of Minnesola
Mingyi Hong"
mhong edu
Department of Electrical and Computer Engineering University of Minnesola
Jie Chen
chenjii Cimiiiiuusmmmmmmmmmmmm com
MIT-IBM Watson AI Lab
IBM Research
Reviewed on OpenReview: https: openreview. net/ net/forum? forum? id= LH12222222
Abstract
Vertical lederated learning (VFL) is 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. In this work, we train graph neural nefwork (GNN) through VFI., where each client owns part of the node features and different edge set. This data scenario incurs a signifi- cant communication overhead, not only because of the handling of distributed features but also due to neighborhood aggregation in GNN. Moreover, the training analysis is faced with a challenge caused by the biased stochastic gradients. 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 communication neighborhood aggregation and in model updates, respectively, greatly reducing communication while enjoying convergence guarantees. We conduct extensive numerical experiments real-world datasets, showing that GLASU ef- fectively trains GNN that matches the accuracy of centralized training, while using only fraction of the time due to commuication saving.
1 Introduction
Vertical federated learning (VFL) is newly developed machine learning scenario in distributed optimization, where clients share data with the same sample identity but each client possesses only 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.
Most of the current VFL solutions (Chen et al. 2020b Liu et al. 2022 treat the case where samples are independent, but omit their relational structure. However, the pairwise relationship between samples
"This work was done while X. Zhang was intern at MIT-IBM Watson AI Lab, IBM Research. 1M. Hong and X. Zhang partially supported by NSF grant EPCN-2311007 and CNS-2003033. This work also part of AI-CLIMATE: "AI Institute for Climato-Land Interactions, Mitigation, Adaptation, Tradcoffs and Economy," and supported by USDA National Institute of Food and Agriculture (NIFA) and the National Science Foundation (NSF) National AT Research Institutes Competitive Award no. 2023-67021-3983

---

Published in Transactions on Machine Learning Research (04/2024)
emerges many occasions, and it can be crucial in several learning scenarios, including the low-labeling-rate scenario in semi-supervised learning and the no-labeling scenario in self-supervised learning.
Consider, for example, a large technology company with multiple services under different subsidiaries, which offers news recommendations to its subscribed users. For each service (video, music, workspace, search tools, etc.) held by one subsidiary, the users could form different connections to each other and generate different historical information with the same user account. It naturally creates multiple vertically split graphs, each held by one subsidiary: professional network where users are connected through occupational ties; a personal network where users are connected through personal life interactions; follower network where a user is follower of another on social media, etc. Further, the user data in cach graph may contain different features (e.g., oecupation-related, life-related, and interest-related, respectively). In this scenario, the portion of overlapping nodes should be large, as the users could access different products and services with the same account. To offer personal recommendations, the company sets up a server that communicates with each client (i.e., cach subsidiary's data center), to train a model that predicts multiple labels for cach user without revealing each client's 's raw local data. See Figure] 1 for an illustration.
One of the most effective machine learning models for such a prediction task is graph neural networks (GNNs) (Kipf & Welling 2016; HHmmiton et al.) 2017 Chen et al. 2018 Velickovic et al. [2018] Chen jet al. 2020a). This model performs neighborhood aggregation in every feature transformation layer, such that the prediction of graph node is based not only the information of this node but also that of its neighbors.
Server
Client
Client
Client
VFL on graph-structured data is not as well stud- ied as that on other data, in part because of the challenges incurred by an enormous amount of com- munication. The communication overhead comes not only from the aggregation of the partial fca- sures/representations of a datum in federated learn- ing, but also from the neighborhood aggregation unique to GNNs. That is, communication occurs in each layer of the neural network, so that the latest representation of a neighboring node can be used to update the representation of the center node. One solution to reduce communication that each client uses a local GNN to extract node representations from its own graph and the server aggregates these representations to make predictions (Zhou al. 2020). The drawback of this method is that the partial features of node outside used, even if this node appears in another client's neighborhood. Another solution is to simulate centralized training: intermediate representations of cach 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's computation.
Full feature:
Full graph:
Figure 1: Data isolation of vertically distributed graph-structured data over three clients.
client's neighborhood are not
In this work, we propose GLASU for communiattion-cficinnt VFL on graph data. The GNN model is 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 disseminates processed data (e.g., node embeddings) 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). For an L-layer GNN, GLASU communicates partial node representations only in K layers and in every other Q iterations, enjoying the reduction of communication by a factor of QL/K. GLASU can be considered as a framework that encompasses several well-known models and algorithus as special cases, including Liu et al. (2022) when the graphs are absent, Zhou et al. (2020) when all aggregations but the final one are skipped (K = 1), Ni et al. (2021) when no aggregations are skipped (K- L), and centralized training when only a single client exists.
2

---

Published in Transactions on Machine Learning Research (04/2024)
With the enjoyable reduction in communication, another difficulty is the convergence analysis, which admits two challenges: the biased gradient caused by neighborhood sampling in training GNNs and the correlated updates due to the use of stale node representations. We conduct an analysis based on the error decomposition of the gradient, showing that the training admits a convergence rate of (((Q)) where T is the number of training rounds, each of which contains Q iterations.
We summarize the main contributions of this work below:
1. Model design:
We propose flexible, federated GNN architecture that is compatible with majority of existing GNN backbones.
2. Algorithm design: We propose the communication--fiiiee GLASU algorithm to 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.
3. Tcalretical analysis: We provide theoretical convergence analysis for GLASU by addressing the challenges of biased stochastic gradient estimation caused by neighborhood sampling and correlated update steps caused by using stale global information. To the best of our knowledge, this is the first convergence analysis for federated learning with graph data.
4. Numerical results: We conduct extensive experiments on seven datasets, together with ablation studies, to demonstrate that GLASU can achieve a comparable performance as the centralized model on multiple datasets and multiple GNN backbones, and that GLASU effectively saves communication and reduces training time.
2 Problem, background, and related works
Problem setup: Consider M clients, indexed by m = I,..., M, each of which holds a part of a graph with the node feature matrix E R xd and the edge set E. Here, N is the number of nodes in the graph and d is the feature dimension. The number of clients is restricted by the feature dimension and is typically small. We assume that each client has the same node set and the same set of training labels, y, but different edge set Em and a non-overlapping node feature matrix Xm E RNNdd such that & = Um &m. X [X...., XM), and d Em= dm- We denote the client dataset as Dn, = (Xm, Em.y) and the full datasct as yy) The task for the clients to collaboratively infer the labels of nodes in the test set.
2.1 Graph convolutional network
The graph convolution network (GCN) (Kipf & Welling 2016 a typical example of the family of GNNs. Inside GCN, a graph convolution layer reads
H =0 (A(E)) H[] W(1).
(1)
where (-) denotes the point-wise nonlinear activation function, A(E) NxN denotes the adjacency matrix defined by the edge set & with proper normalization, H[] E Nxddl denotes the node representation matrix at layer I, and W[1] E [dd[))4[++] denotes the weight matrix at the same layer. The initial node representation matrix H() = X. The classifier denoted as y = [H),, ((T)) with weight matrix W(.) and the loss function denoted as f)y,)). Therefore, the overall model parameter is W = (W(O).... W[L - 1), W[L]).
Mini-bbtch training of GCN (and GNNs in general) faces a scalability challenge, because computing few rows of H[L) (i.e., the representations of a mini-batch) requires more and more rows of H - 1]. H[L - ......, 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 training nodes, S(L). we iterate over the layers backward such that layer I, we sample subset of neighbors for Si + 1), namely S(1]. In doing so, at each layer, we form bipartite graph with edge set E[] ((i.j) E S(1 + 1) S(I).
3

---

Published in Transactions on Machine Learning Research (04/2024)
Then, each graph convolution layer becomes
H + 1||S|/ + 1]] = a A(E))) H[[[S]] wii),,
(2)
where (EE E [ is properly scaled submatrix of (()) and H H[] denotes the rows of H[ corresponding to the sampled neighbor set S(q].
2.2 Related works
Vertical federated learning is learning paradigm where the features of the data are distributed across clients, who collaborate to train model that incorporate all features (Liu et al
2022 Chen et al. 2020b; Xu et al.) 2021 Thus, the
Romanini et al. 2021 Yang et al.) 2019b Gu et al.) 2021 Yang et al. 2019: 9a global model is split among clients and the key challenge is the heavy communication costs on exchanging partial sample information for computing the losses and the gradients for each sample. Most works consider simple models (e.g., linear) because complex models incur multiple rounds of communication for prediction.
Federated learning with graphs includes four scenarios. The graph-level scenario is horizontal, where each client possesses collection of graphs and all clients collaborate to train a unified model (Zhang et al,, Xie et al. 2021 The task is to predict graph properties
202 He et al.) 2021 Bayram & Rekik 2021
(such as molecular properties).
The subgraph-level scenario could be either verlical or horizontal. In the vertical scenario, each client holds a part of the node features, a part of the whole model, and additionally a subgraph the global graph (Zhou ct al., 2020 Ni al.] 2021p. The clients aim to collaboratively train a global model (combined from those of each client) to predict node properties (such as the category of paper in citation network). Our work addresses this scenario.
The subgraph-lene,, horizontal scenario, on the other hand, considers training GNN for node property prediction in a distribuled manner: a graph is partitioned and each client. holds one partition (Zhang et al. 2021b; Wu et al. 2021 Chen et al. 2022 Yao & Joe- Wong, 2022 Moreover, each client holds all features of the nodes that it possesses. A challenge to address is the aggregation of information along edges crossing different clients. This scenario differs from the vertical scenario in that features are not partitioned among clients and the graph partitions do not overlap.
The fourth scenario is node-level: the clients are connected by graph and thus each of them is treated node. In other words, the clients, rather than the data, are graph-structured It is akin to decentralized learning, where clients communicate to each other via the graph to train a unified model (Lalitha et al. 2019 Meng et al. 2021
Caldarola et al. 2021 Rizk & Sayed 2021).
Please see Appendix A for in-depth discussions of the related works.
3 Proposed approach
In this section, we present the proposed model and the training algorithm GLASU for federated learning on vertically distributed graph data. The neighborhood aggregation in GNNs poses communication challenges distinct from conventional VFL. To mitigate this challenge, we 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 implementation involves neighborhood sampling, where more precise notation should follow (2) and that one can easily change the backbone from GCN to other GNNs.
3.1
GNN model splitting
We split the GNN model among the 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
4

---

Published in Transactions on Machine Learning Research (04/2024)
Server Aggregation Layer
Server Agg. Layer 2 (Skipped)
Server Agg. Layer L
H
HELHI
H[1]
H[C]
Client 3
Client 3
93
Client
Client 2
92
Client 1 GNN Layer 2
Client
91
Classifier
Client GNN Layer
15,
[,[0]:
Client Data D3
Figure Illustration of the split model on M clients with lazy aggregation. In the model, the second server aggregation layer is skipped and the graph size used by each layer gradually decreases, due to neigh- borhood aggregation (inverse of neighborhood sampling).
the /-th layer, each client computes the local feature matrix
H H a (A(Em) Hmll Wmll!)
with the local weight matrix W [1] and the local graph Em, where we use the superscript + to denote local reprosentations before aggregation. Then, the server aggregates the clients' representations and outputs
H[| [] as
H + 1] Agg H
H M),
where Agg(-) is an aggregation function. In this paper, only consider parameter-free aggregations, in- cluding averaging and concatenation. The server broadcasts the aggregated H( 1] to the clients so that computation proceeds to the next layer. the final layer, each client computes a prediction. This layer is the same among clients because they receive the same H(L).
The two aggregation operations of our choice render a rather simple implementation of the server. They bring in two advantages: parameter-free and memory-less. Since the operations do not contain any learnable parameters, the server does not need to perform gradient computations. Morcover, in the backward pass, these operalions do not require data from the forward pass to back-propagate the gradients (memory-less)) Specifically, for averaging, the server prok-propsgates 37 WHH++1JC to each client, where L denotes the loss; while for concatenation, the server back-propagatos the corresponding block of VH[+I)
1
Concatenation more flexible as it does not require the outpul of the GNN layers al different clients have the same length. With less restriction on the output feature length, the clients can have more flexibility in the layer width in model design that GLASU can accommodate client hardware heterogeneity. In terms of communication and computation complexity, concatenation requires more communication and computation resources than averaging. Instead of broadcasting the averaged feature, the server needs to broadcast the longer concatenated feature to the clients. Moreover, the clients need to have GNN layers with larger input to process the concatenated features. If the output feature sizes of all client models are the same, then averaging can be viewed as a special case of concatenation followed by an averaging operation. our experiments, we fix the clients' layer output dimension to be the same and use averaging as is more communication efficient and computation/ maaatiionmmmmmo--rreedllll
We illustrate in Figure 2 the split of each GNN layer among the clients and the server. Note the dif- ference of our approach from cxisting approaches. Our model splitting resembles federated split learning (SplitFed) (Thapa et al. 2022). In SplitFed, each client can collaborate with the server to perform inference or model updates without accessing information from other clients; whereas 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 requires single U-shape communication (Chen et al. 2020b). In our case, due to the graph structure, each GNN
5

---

Published in Transactions on Machine Learning Research (04/2024)
layer contains one client-server interaction and the number of interactions is equal to the number of GNN layers (we will relax this in the following subsection).
3.2 Lazy aggregation
The development in the preceding subsection approximates centralized model, but it is not communi- cation friendly because each layer requires one round of client-server communication. We propose two communication-savinng strategies in this subsection and the next. We first consider lazy aggregation, which skips aggregation in certain layers.
Instead of performing server aggregation each layer, we specify a subset of K indices, I= (l.....,l4 1x) c [4], such that aggregation is performed only these layers. That is, at layer / Z, the server performs aggregation and broadcasts the aggregated representations to the clients, serving as the input to the next layer: Hm! 1] Hi + 1]; while at a layer & I, each client uses the local representations as the input to the next layer: H.. 1 + H By doing so, the amount of communication is reduced from O(L) to O(K).
There are subtleties caused by neighborhood sampling, similar to those faced by FastGCN (see Section 2.1 First, requires additional rounds of communication to synchronize the sample indices, bocause whenever server aggregation is performed, it must. be done on the same set of sampled nodes across clients. Hence, in the additional communication rounds, the server takes the union of the clients' index sets Sn, [ and broadcasts S[4] = U Sm [4]] to the clients. Second, when server aggregation skipped at a layer & I, each client can use its own set of sampled nodes, Sm. [4], which may differ from each other. Such a procedure is more flcxible than conventional VFI. where sample features generally processed synchronously. The sampling procedure is summarized in Algorithm 2
3.3
Stale updates
To further reduce communication, we consider stale updates, which skip aggregation in certain iterations and use stale node representations to perform model updales. The key idea is to use the same 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 replaced by a local aggregation between a 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 every Q iterations.
Specifically, let 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 a joint inference on the representations H [4] at every layer E Z. Each client m will store the "all but m" representation H' [ + +1] through extracting such information from the aggregated representations H 1]: H' n || +1 Extract(HH H (I).
For example, when the server aggregation is averaging, the extraction is
1 Extract(H', 1], H (1)+ H [[1+]]]]] M
H [1]
Afterward, the clients perform Q iterations of model updates, indexed by q = 0, ... Q- on the local pa- rameters W in parallel, using the stored aggregated information H' +1 to perform local computation, replacing server aggregation. The name "stale updates" comes from the fact that H'm,( + 1] is computed by using stale model parameters (w fm at all iterations q * O. The extraction and the local updates are summarized in Algorithm 3 and Algorithm 4 respectively.

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithm Training Procedure. All referenced algorithms are detailed in Appendix ??.
for 0, ...... .T do Server /Client (Algorithm
2
Sample {S Mo
1
t>0
0
Client: W
w
==0
Server Client (Algorithm
3
(H" IJherr JointInfereneeWWn Dm, (S) (())))
for o,...,Q, Q do
Client (Algorithm Wha+1
LocalUpdate(Wing Dm, (8 (4) (H 1]her).
end for end for Output: (WTO)M m==1
Algorithm Sampling Procodure
Client:
1: Server:
for k = .,,.. do
2: Uniformly and independently sample indices S(L] from training set.
Receive(S((x)).
Set Sm14k] = S[4)]
3: Broadcast(S[L)).
5:
for 1= 4 - 1,....4444 do
4: for h = K l.... do
6:
Uniformly randomly sample indices Sm [4] from neighbors of Sm + 1].
5: Aggregate(S.m/ [4])-
6: Compute S[44]
U Sm 14].
end for Send(Sm if 2.
7: Broadcast(S[1.,
8: end for
end for 10: Output: {8m 1S
Algorithm 3 Jointenference
Client:
Server:
Input: W.,. m. Dm. {Sm [] []
2: for 1 E I do
3: Set Hm.[0] = Xm Sm [0]
3: H[+ Agg H 14 ...... l1).
4: for = O, ......... L do
Broadcast H[ + 1].
5: H [1] = o (AE + Sm ([W.
5: end for
i I then
Send [ to server
Receive Hm 11 [1]
[1 + H_m
Extract + 1]. (1)
10: clse
11: Set H [ 11+1 1]= =
12:
end
13: end for
14:
Output: (H-ml [1+ 1]]iez

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithm 4 LocalUpdate
1: Input: W Dm, 1 1 (H' 1lkez
2: Set [0 = Xm [0]]
m
for = .,....,..
do
HI = (A(E(S)) 11, S (1 H
e I then
Set H + 1] Agg H ml 11. H.at [[]
(!)
7: clse
8: Set H + H
9: end
10: end for
11: Compute loss Lig = S [I], fm H (L) Wm (L])
12: Output: WLg+1 WT. 11 1. wt. L..
3.4 Summary
The overall training procedure is summarized in Algorithm For communication savings, lazy aggregation brings in a factor of L/K and stale updates bring in a factor of Q. Therefore, the overall saving factor is QL/K. Note that the algorithm assumes that all clients have the training labels. If the labels can be held by only one client (say, A), slight modification by broadeasting the gradient with respect to the final-layer output possessed by A, suffices. See Appendix B for details.
3.5 Special cases
It is interesting to note that GLASU encompasses several well-known methods as special cases.
Conventional VFL. VFL algorithms can be viewed as a special case of GLASU, where A = I for all m. In this case, no neighborhood sampling needed and GLASU reduces Liu et al. (2022).
Existing VFL algorithms for graphs. The model of Zhou et al. (002)) special case of GLASU, with K = 1; i.e., no communication is performed 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.) 22021h is also special case of GLASU, with K = This case requires communication at all layers and is less efficient.
Centralized GNNs. When there is a single client (M = 1), our setting is the same as centralized GNN training. Specifically, by letting K L and properly choosing the server aggregation function Agg(-), our split model can achieve the same performance (K + L) and choosing the server aggregation function concatenation averaging will make the split model different from a centralized GNN.
centralized GNN model. Note that using lazy aggregation
3.6 Privacy protection
Although this paper focuses on the utility side of FL and addresses a unique but unresolved issue pertaining graph neural networks: the enormous communication overhead due neighborhood aggregation inside GNN model (besides the usual model communication problem faced by vertical FL), in this section, we provide brief discussion on how privacy protection mechanisms be applied to our GLASU algorithm.
First, let us clarify that the aim of differentially private GNN training is to protect local graph data. Specifically, we want to protect the data from node inference attacks (ie., identifying if one node feature appears in some client's 's local subgraph.) this case, GLASU can combine a secure aggregation method with a differentially private mechanism to guard against node inference attacks.
Secure Aggregation (SA) (Bonawitz al. 2017 Hardy al. 2017) is a form of secure multi parti-pprtyy com- putation approach used for aggregating information from a group of clients, without revealing the information
8

---

Published in Transactions on Machine Learning Research (04/2024)
of any individual. This can be achieved by homomorphic encryption (Li et al. 2010 Hardy et al. 2017 In our case, when the server aggregation is averaging, homomorphic encryption can be directly applied.
Differential Privacy (DP) (Wei et al. 2020) is a probabilistic protection approach. By injecting stochas- ticity into the local outputs, this approach guarantees that an attacker cannot distinguish the sample from the dataset up to certain probability. DP can be applied either solely or combination with SA to our algorithm in the server-client communication, offer privacy protection for the client data.
Specifically, for the DP mechanism, perturbation needs to be added to the first node aggregation layer; that is, for the smallest 1 in the set of aggregation layers, H(2 + 1] SecAgg H + wi,.... H [1] + Wwr where . 1) and the aggregation Agg proposed in Sec. 3.1 is replaced by a secure aggregation SecAgg (such as homomorphic encryption). With this scheme, the client's 's raw node features can stay private by properly choosing the noise variance o², which depends on the scnsitivity of the output of the I-th layer, the maximum degree of the nodes, and the number of training rounds T.
the injected noise Wm m = I,..., M follows a normal distribution NN0 o²
4 Convergence analysis
In this section, we analyze the convergence behavior of GLASU under lazy aggregation and stale updates. To start the analysis, denote by S = (S [ the samples used at round (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 is evaluated at the overall set of model parameters across clients, W {W m samples, S.
[Wm)M. mmm1,, and batch of
A few assumptions are needed (see Appendix C.1 for formal statements). A1: The loss function & is Gr- smooth with Læ-Lipschitz gradient; and a client's prediction function fm Gy-smoohh with Li-Lisschitz gradient. A2: The training objective L(W;D) is bounded below by a finite constant L.. A3: The samples S are uniformly sampled from the neighbor set in each layer.
Theorem 1. Under assumptions A1 A3, by running Algorithm 1 with constant step size n S CO (1+ M)=1, with probobility at least 1 - 8, the averaged squared gradient norm is bounded by:
1 T-1Q-1
2Ac TTQ
28 (Co + -V+ + 6,
E (D
TQ
where AC L(W0.)) L" Co GrL, + L, and a > 0 is function of log(TQ/6)) Lg Gy and Gg. Remark 1. There are two key challenges in the analysis. (1) Owing to neighborhood sampling, the stochastic gradient is biased (i.c., Es VL(W;S) + VL(W; (2) The stale updates in one communication round are correlated, as they use the same mini-batch and samples. Hence, the general unbiasedness and independence assumptions on the stochastic gradients in the analysis of SGD-type of algorithms do not apply. We borrow the technique by Ramezani et al. (2200) to bound the error of the stochastic gradient through the bias- variance decomposition and extend the analysis by Liu et al. (2022) for VFL with correlated updates to
establish our proof. For details, see Appendix
Remark 2. To better expose the convergence rate, assuming that Q is upper bounded by VM+I* one may
set 17 25MChoTQ: such that
3Ac
Q-1 TQ t=0 9=0
7Cc 3TQ
E S <8/
Ignoring the logarithmic factor log(TQ/8) in a, the above bound states that the squared gradient norm decreases as ((TQ)-1) Note that this bound holds only when T is sufficiently large, because the choice of 7) must satisfy the condition of Theorem [1
Remark 3. Basod on the precoding remark, we see that achieve c-stationarity, the number of model updates is QT ( That is, as long as Q obeys the upper bound, running more local updates (Q) reduces the amount of communications (T). To the best of our knowledge, this is the first result for VFL on graph data.
9

---

Published in Transactions on Machine Learning Research (04/2024)
Table 1: Datasets. Each of the HeriGraph datasets (Suzhou, Venice, Amsterdam) contains three naturally formed subgraphs. For other datascts, each contains one single graph and each client holds a sampled subgraph of it.
Dataset
# Nodes
# Edges
# Feat.
# Class
Cora
2, 708
10, 556
1, 1,433
PubMed
19, 717
88, 648
500
CiteSeer
3,327
9, 104
3, 703
Suzhou
137
916, 496
979
Venice
2, 951
534, 513
979
Amsterdam
3, 727
1, 2,1, 171
979
Reddit 232, 965
114, 615, 892
602
Remark 4. While have analyzed the impact of stale updates (Q), lazy aggregation (K) does not play role in convergence, because it does not affect model updates. Instead, it affects model accuracy in manner similar to how changing neural network impacts the prediction accuracy.
Remark 5. If we consider the impact of the number of clients, the factor M in the numerator of the bound indicates a slowdown when more clients participale training, Similar results are seen in FedBCD (Liu et al., 2022), but therein one can use a large batch size $ to counter the slowdown. For graphs, however, S does not appear in the bound because of the biased gradient estimation. Nevertheloss, we note that unlike other federated scenarios, in VFL, M is very small because it is limited by, e.g., the feature length.
5 Numerical experiments
In this section, conduct numerical experiments variety of datasets and demonstrate the effectiveness of GLASU in training with distributed graph data. We first compare its performance with related methods, including those tackling a different assumption on the data distribution and communication pattern. Then, we examine the communication saving owing to the use of lazy aggregation and stale updates. We further showcase the flexibility of GLASU through demonstration with different GNN backbones and varying clients. The experiments are conducted on a distributed cluster with three Tesla V100 GPUs communicated through Ethernet.
5.1 Datasets
We use seven datasets (in three groups) with varying sizes and data distributions: the Planetoid collec- tion Yang et al. 2016), the HeriGraph collection (Bai et al. 2022 and the Reddit dataset (Hamilton al., 2017 Each dataset in the HeriGraph collection (Suzhou, Venice, and Amsterdam) contains 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 contains one single graph and thus we manually con- struct subgraphs through randomly sampling the edges and splitting the input feat into non-overlapping blocks, so that cach client handles one subgraph and one feature block. The datasct statistics are summarized in Table 1 and more details are given in Appendix D.I
5.2 Accuracy
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 communication; (b) standalone training (Zhou et al. 2020). where cach client trains a model with its local data only and they do not communicale; (c) simulated cent ralized training NNi et al., 2021}, where each client possesses the full graph but only the partial features, so that simulates centralized training through server aggregation in each GNN layer. Methods (b) and (c) are typical VFL methods; they are also special cases of our mothod (sce Section 3.5). Except for centralized training, the number of clients M- 3. The number of training rounds, T, and the learning rate y are optimized through grid search. See Appendix D.2 for details.
10

---

Published in Transactions on Machine Learning Research (04/2024)
Table 2: Test accuracy (%). The compared algorithms are Centralized training (Cent.); Standalone training (StAL); Simulated centralized training (Sim.): GLASU with no stale updates, i.c., Q (GLASU-1); and
GLASU with stale updates Q (GLASU-4).
Dataset
Cent.
StAl.
Sim.
GLASU-1
GLASU-4
Cora
80.9 0.6
74.6 0.5
80.1 1.2
81.0 - 1.3
80.3 1 1.2
PubMed
84.9 0.6
77.2 + 0.5
82.7 12.7:11 1.2
82.3 = 1.6
83.8 1.8
CiteSeer
70.2 0.8
64.4 0.5
70.0 1.2
70.0 1.7
68.8
Suzhou
94.3 0.3
51.6 0.9
93.5
92.7 1.4
90.4 0.8
Venice
95.7 + 0.5
2.1
9.3
92.2 12.20006 0.6
1.6
Amsterdam
94.6 + 0.1
59.8 + 1.0
0.8
93.1 = 0.8
94.9
Reddit
95.6 + 0.1
87.3 = 0.3
0.7
95.7 = 0.6
94.7
Table 3: Test accuracy (%), runtime (seconds), and saving in runtime (%) under different numbers of lazy The saving with respect
aggregation layers (K 4, 2, 1).
Left: PubMed; right: Amsterdam.
Layer
K = 4
==2
==1
K 4
K =
K =
Accuracy
82.5 1.0
83.8 1.8
82.2 0.7
93.6 + 0.7
94.9
92.0 + 1.7
Runtime
130+10 12
96.6 9.9
81.3 = 6.5
913 + 76
544 + 44
382 + 35
Saving
25.7
37.5
40.4
58.2
We use GCNII CCen et al.) 2020ah the backbone GNN. GCNII improves over GCN through including two skip connections, one with the current layer input and the other with the initial layer input. We set the number of layers L = 4 and the mini-batch size $ = 16. For neighborhood sampling, the sample size is three neighbors per node on average. We set K = 2; i.e., lazy aggregation is performed in the middle and the last layer.
Table 2 reports the average classification accuracy of GLASU and the compared training methods, repeated five times. 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, because server aggregation (or its equivalence in centralized training) on each GNN layer takes effect. Our method GLASU, which skips half of the aggregations, yields prediction accuracy rather comparable with these two methods. Using stale updates (Q = 4) is generally outperformed by no stale updates (Q 1), but occasionally better (sce PubMed and Amsterdam). The gain in using lazy aggregation and stale updates occurs in timing, as will be demonstrated next.
5.3 Communication saving
To further investigate how the two proposed techniques affect the model performance and save the commu- nication, we conduct a study on (a) the lazy aggregation parameter K and (b) the stale update parameter Q.
Lazy aggregation: We use a 4-yyyr GCNII as the backbone and set K = 1,2,4. The aggregation layers are "uniform" " across the model layers. That is, when K = 1, server aggregation performed on the last layer; when K 2, on the middle layer and the last layer; and when K 4, on all layers. The test accuracy and runtime are listed in Table 3. We observe that the runtime decreases drastically when using fewer and fewer aggregation layers: from K = 4 to K 1, the reduction is 37.5% for PubMed and 58.2% for Amsterdam. The accuracy is comparable in all cases.
We experiment with a few choices of Q: 2, 4, 8, and 16. We report the time to reach the same test accuracy threshold in Table 4 We see that stale updates help speed up training by using fewer communication rounds, corroborating Remark 3 of the thcory in Scction 4 This trend occurs on the Amsterdam dataset even when taking Q as large as 16. The trend is also noticcable on PubMed, but some point (Q =8) it is reverted, likely because it gets harder and harder to reach the accuracy threshold.
Stale updates:
11

---

Published in Transactions on Machine Learning Research (04/2024)
Table 4: Runtime (seconds) and the test accuracy (%) reach the same accuracy threshold under different numbers of stale updates (Q 2, 6, 16). Top: PubMed (threshold: 82%); bottom: Amsterdam (threshold:
89%).
# Stale
Q
=
Q 8
Q 16
Accuracy
82.5 + 1.6
2.4
82.1 1 0.3
N/A
Runtime
66.1 + 5.0
43.8 1 4.0
88.9 + 7.4
128
# Stale
Q = 2
Q = 4
Q = 8
Q = 16
Accuracy
89.2 0.4
89.3 = 0.7
90.7 + 0.5
90.3 = 1.1
Runtime
1323 + 44
521 + 44
324 + 31
250 = 24
Table Test accuracy (%) of Centralized training (Cent.), Stan- dalone training (StAL.), and GLASU under different numbers of clients (M 3, 5, 7). Top: CiteSeer; bottom: PubMed.
Test Accuracy
# Client
M 3
M = 5 M =7
0.6
Cent.
70.2 + 0.8
0.4
StAL
64.4 0.5
44.6 0.3
36.6 + 0.8
GAT
GLASU
68.8 + 3.3
69.5 1.4
69.4 0.7
0.2
GCN
# Client
=
M
M =
GCNI
Cent.
84.9 = 0.6
128
256
384
SLAL
77.2 0.5
73.8 0.5
67.0 + 1.3
Communication T
GLASU
83.8 1.8
84.6 0.4
84.4 1 0.2
Figure 3: Test accuracy under three back- bone GNNs on PubMed.
16. This observation is consistent with Remark 2 of the theory, requiring to be upper bounded to claim (((TQ)-1) convergence.
We speculate that the target 82% can never be achieved at
5.4 Flexibility
To demonstrate the flexibility of GLASU, conduct experiments to show the performance under (a) different GNN backbones and (b) different numbers of clients, M.
Backbone model: We compare three backbones: GCN, GAT (Velickovic et al. 2018 and GCNII, which are representative GNNs. The learning rate for each backbone is tuned to its best performance. The test accuracy over training rounds is plotted in Figure We see that GLASU can take different GNNs as the backbone and reach a similar prediction performance, despite that the convergence curves are not all similar. For example, the convergence histories of GCN and GCNII are quite close, whereas that of GAT experiences roughness.
We set M = 3, 5, and investigate the change of performance for different training methods. Hyperparameters are tuned to achieve the optimal accuracy under fixed number of epochs. Table 5 suggests that the performance of standalone training decreases as M increases, which is expected because each client has fewer features while server aggregation not performed. Meanwhile, the performance of GLASU not affected and it stays comparable with that of centralized training. We note that is unrealistic to set M arbitrarily large, because M limited by the feature length and also in practice, is determined by data ownership.
Number of clients:
6 Conclusion
We have presented flexible model splitting approach for VFL with vertically distributed graph data and proposed communication-effiiees algorithm, GLASU, to train the resulting GNN. Due to the graph struc-
12

---

Published in Transactions on Machine Learning Research (04/2024)
ture, 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 reduction. Our analysis makes no assumptions on unbiased gradients. We provide extensive experiments to show the flexibility of the model and the communication saving in training, without compromise on the model quality.
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.
Hizr 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, Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for learning. In proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1175 1191, 2017.
machine
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-2758, 2021.
Chuan Chen, Weibo Hu, Ziyue Xu, and Zibin Zheng, Fedgl: federated graph learning framework with global self-supervision. arXiv preprint vrXi::2105.08100, 2021.
Fahao Chen, Peng Li, Toshiaki Miyazaki, and Celimuge Wu. Fedgraph: Federated graph learning with
intelligent sampling. IEEE Transactions on Parallel and Distributed Systems, 33(6):1775-1786, 2022. doi:
10.1109/TPDS.200 STTDDS.222.3125555
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via impor- tance sampling. In International Conference on Learning Representations, 2018.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, pp. 1725-1735. PMLR, 2020a.
Tianyi Chen, Xiao Jin, Yuejiao Sun, and Wotao Yin. Vafi: a method of vertical asynchronous federated learning. arXiv preprint wxXx:2007706088 2020b.
Bin Gu, An Xu, Zhouyuan Huo, Cheng Deng, and Heng Huang. Privacy-preserving asynchronous vertical federated learning algorithms for multiparty collaborative learning. JEEE transactions on neural networks and learning systems, 2021.
Will Hamilton, Zhitao Ying, and Jure Leskovec. 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 vertically partitioned data via entity resolution and additively homomorphic encryption. arXiv preprint ar XrXi::1711.1100
2017.
Chaoyang He, Keshav Balasubramanían, Emir Ceyani, Carl Yang, Han Xie, Lichao Sun, Lifang He, Liangwei Yang, Philip S Yu, Yu Rong, et al. Fedgraphmn: A federated learning system and benchmark for graph neural networks. Xr preprinl arXiv:2104.07144 2021.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint or Xie: 609. 02907, 2016.
13

---

Published in Transactions on Machine Learning Research (04/2024)
Anusha Lalitha, Osman Cihan Kiline, Tara Javidi, and Farinaz Koushanfar. Pecr-to-peer federated learning on graphs. Xiv preprint orXix:1911.111 191111173,, 2019.
Fengjun Li, Bo Luo, and Peng Liu. Secure information aggregation for smart grids using homomorphic encryption. In 2010 first IEEE international conference on smart grid communications, pp. 327-332.
IEEE, 2010.
Yang Liu, Xinwci Zhang, Yan Kang, Liping Li, Tianjian Chen, Mingyi Hong, and Qiang Yang. Fedbcd: A communication-effcienn collaboralive learning framework for distributed features. IEEE Transactions on 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 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 arXiv:2106. 11593, 2021.
Morteza Ramezani, Weilin Cong, Mehrdad Mahdavi, Anand Sivasubramaniam, and Mahmut Kandemir. Gen meets gpu: Decoupling "when to sample" from "how to sample". Advances in Neural Information Processing Systems, 33:18482 18492, 2020.
Elsa Rizk and Ali Н Sayed. A graph federated architecture with privacy preserving learning. In 2021 IEEE 22nd International Workshop on Signal Processing Advances in Wireless Communicalions (SPAWC), pp- 131-135. IEEE, 2021.
Daniele Romanini, Adam James Hall, Pavlos Papadopoulos, Tom Titcombe, Abbas Ismail, Tudor Cebere, Robert Sandmann, Robin Roehm, and Michael A Hoeh. Pyvertical: A vertical federated learning frame- work for multi-headed splitnn. arXiv preprint arXiv:2104.044 00489, 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 to matrix concentration inequalities. Foundations and Trends3 in Machine Learning, 8(1-2):1-230 2015.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. stat, 1050:4, 2018.
Binghui Wang, Ang Li, Hai Li, and Yiran Chen. Graphíl: A federated learning framework for semi-supervised node classification graphs. arXiv preprint KKi:22012004887 2020.
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. 1EEE Transactions on Information Forensies and Securily, 15:3454 3469, 2020.
Chuhan WU, Fangzhao Wu, Yang Cao, Yongfeng Huang, and Xing Xie. Fedgun: Federated graph neural network for privacy-preservigg recommendation. arXiv preprint arXim:1100 102.00020000 04925, 2021.
Han Xie, Jing Ma, Li Xiong, and Carl Yang- Federated graph classification over non-iid graphs. Advances Neural Information Processing Systems, 34:18839-18852, 2021.
Runhua Xu, Nathalie Baracaldo, Yi Zhou, Ali Anwar, James Joshi, and Heiko Ludwig. Fedv: Privacy- preserving foderated learning over vertically partitioned data. In Proceedings of the 14th ACM Workshop on Artificial Intelligence and Securily, pp. 192, 2021.
Kai Yang, Tao Fan, Tianjian Chen, Yuanming Shi, and Qiang Yang. A quasi-newton method based vertical federated learning framework for logistic regression. Xrx preprint ar Xiv: 191200013,, 2019a.
14

---

Published in Transactions on Machine Learning Research (04/2024)
Shengwen Yang, Bing Ren, Xuhui Zhou, and Liping Liu. Parallel distributed logistic regression for vertical federated learning without third-party coordinator. arXiv preprint arXin: 1911199119944 2019b.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pp- 40-48. PMLR, 2016.
Yuhang Yao and Carlee Joe- Jong. Fedgen: Convergence and communication ion tradeoffs in federated training graph convolutional networks. arXiv preprint arXiv:2201.12433, 2022.
Huanding Zhang, Tao Shen, Fei Wu, Mingyang Yin, Hongxia Yang, and Chao Wu. Federated graph learning a position paper. arXiv preprint 2it::21005.10099 2021a.
Ke Zhang, Carl Yang, Xiaoxiao Li, Lichao Sun, and Siu Ming Yiu. Subgraph federated learning with missing neighbor generation. Advances in Neural Information Processing Systems, 34:6671-6682, 2021b.
Longfei Zheng, Jun Zhou, Chaochao Chen, Bingzhe Wu, Li Wang, and Benyu Zhang, Asfgnm: Automated separated-fedeerated graph neural network. Peer-lo-Pees Nelworking and Applications, 14(3):1692 1704, 2021.
Jun Zhou, Chaochao Chen, Longlei Zheng, Huiwen Wu, Jia Wu, Xiaolin Zheng, Bingzhe Wu, Ziqi Liu, and Li Wang. Vertically federated graph neural network for privacy- seracy-preserving node classification. arxiv preprint ar 200: 1 11903, 2020.
15

---

Published in Transactions on Machine Learning Research (04/2024)
A Related works
Vertical federated learning is a learning paradigm where the features of the data are distributed across clients. The model is split among the clients and therefore, the key challenge the heavy communication burden in exchanging the partial sample information.
Gu et al. 2021 Chen et al. (0220b Xu et al. 2021); Yang et al 2019b) consider linear combination of the features (c.g.: SVM, linear regression, logistic regression) and develop asynchronous communication-cffcion
protocols to aggregate the partial features. These methods can hardly be generalized to complex models in a highly nonlinear nature (e.g. multi-layer perceptrons and convolutional neural networks), because they require multiple rounds of communications. (Yang et al. (2019a) use the second-order Taylor expansion to lincarize the training objective for efficient communication. All these methods assume that one round of communication is sufficient for exchanging partial information, too simplistic and ineffective for graph neural networks.
Federated learning with graphs is a broad subject due to the flexibility of graphs. There are generally four scenarios. Some are related to graph-structured data while some are to graph-struct ured clients. See Figure for an illustration.
Server
Server
Licei
Client
Teer
Clici I
Clarri
Cleer
Sakor:
Filent
Ciectonr Nolo
(a) Graph-level
(b) Subgraph-level, vertical (c) Subgraph-lovel, horizontal
(d) Node-level
Figure 4: Four scenarios of federated learning with graphs.
(1) Graph-level (horizontal). In this scenario, each client possesses a number of graphs and all clients collaborate to train a unified model. Xie et al. (2021) apply federated learning to molecular graph property prediction with decentralized data. He et al. (2021) design a coding platform for training and evaluating graph-level federated learning algorithms. Bayram & Rekik (2021) study the scenario that multiple hospitals collaborate to train GNN model for connectional brain templates. Wang et al. (2200) use model-agnostic mela-learning (MAML) approach to deal with heterogeneous graphs and train common model among clients. Zheng et al. (2021) study the setting where each client holds a heterogeneous graph dataset, a heterogencous GNN feature extractor, and a common classifier. In this case, the clients train the local model with local datasets and upload the parameters of the classifier to the server. The server performs model averaging and optimizes the hyperparameters for local training.
Different from the sccnario addressed by our paper, each client's data are independent; hence, cach client can separately perform local training without gradient sharing.
(2) Subgraph-level, vertical. In this scenario, each client possesses a fraction of the graph information, particularly, partial edges and partial node features. Each client holds a partial model, which is responsible for the features and the induced subgraph it possesses. We focus on this scenario in the paper.
One way for the clients to collaboratively train the model is that they cach uses a separate local GNN to extract node representations (Zhou al. 2020). Then, the server aggregates these representations to make the prediction. In this approach, the local node representations are obtained by using a local graph, failing to capture the information from neighboring nodes in other clients' graphs. Another way of collaboration is to simulate centralized training (Ni et al. 2021). In this approach, the clients communicate the node representations after each layer computation, causing a large communication overhead.
(3) Subgraph-level, horizontal. In this scenario, each client holds a partition of the graph and all features of the nodes in the partition. Because the features are not split across clients, this scenario is not vertical; if we consider each node to be data sample, it fits the usual horizontal definition of federated learning. A
16

---

Published in Transactions on Machine Learning Research (04/2024)
critical challenge to address is how to economically communicate information of neighboring nodes crossing
partitions, hop by hop.
In Chen et al. [2021], the clients send their local model, the predicted labels, and the node representations to the server for global semi-s cemi-supervised learning that assists local model training. In Chen et al.] (2022)
an active node sampling method proposed along with reinforcement learning, to improve the performance of local stochastic training. In Yao Joe- Wong] (2022), the clients first communicate the raw aggregated node features necessary for local training and then perform local training with federated model averaging.
In Zhang et al. (2021b); each client holds ego-graple with missing neighbors and trains a neural network to predict the information of these missing nodes, by federated Icarning. Then, each client utilizes the generated pseudo neighbor information for GNN training. In Wu et al. (2021), each client holds one user- item ego -ro-graph, part the entire recommendation system graph. The clients jointly train a unified model with prreecy-preserving methods, using differentially private SGD updates and encrypted node sampling.
(4) Node-level. In this scenario, the clients are connected by a (communication) graph. The setting is akin to decentralized learning. The data at hand may be grapb-structured or not.
In Lalitha ct al. (2019) Meng et al. (2021,; , the clients run federated learning algorithms locally and commu- nicate models/ gradients through the graph. In the latter work, the clients possess interconnected time-series data. Each of them processes the local data and the server utilizes the underlying graph structure to run a GNN to improve global prediction. In Caldarola et al. (2021); ; Rizk & Sayed (2021), the underlying graph structure kept by the server, which uses GNN to perform aggregation on the model or data collected by the clients.
prodels/gradients
B Modified subroutines when only one client holds the labels
Without loss of generality, we assume that the labels are held by client Algorithms are modified to Algorithms 5
7 respectively.
For sampling (Algorithm 5) client 1, rather than the server, generates the sampled node indices for training.
For Infernnee (Algorithm G/, client computes the mini-batch loss and the partial gradient with respect to the node representation of the last layer, H,[4], and broadcasts it to all other clients through the server. We require that server aggregation is performed on the last layer; that is, for other nodes, Hn [L] = Ag [L- [],...,,H,[Z 1)). Then, the partial gradient with respect to H, [L] (that is, (1, is sufficient for computing the gradients of the model parameters on all these clients. To this, note that the clients > do not have the classifier W.. Wm[4]. Hence, we have
V W Lm = OW
l [L], [Z), W (Z]))
(ylS, [1]. fi (H,, [L], Wi(L))) ow, m
H [4]
ÖH [4]
dL1
0H. [
(3)
0H1
aw
[
Therefore, client 1 broadcasts C1 to all other clients through the server.
For LocalUpdate (Algorithm 7 clients m follow the chain rule to compute the second term inside the inner product of 3 and update the local model parameters.
17

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithm 5 Sampling Procedure (Modified)
1: Client:
1: Server:
m = then
2: Recieve sample indices S(L] from client.
Uniformly and independently sample indices S[L] from training set.
3: Broadcast(S[L)).
4: for h = K ,,,.. do
end if
5: Aggregate(SmIlk
5: for k= k......? , do
6: Compute S(4,]
U Sm [4x]
6: Receive(S((4).
7: Broadcast
7: Set S., [k] = S-
8: end for
8: for 1=4 - 1,...,44- do
Uniformly randomly sample indices S.n [1] from neighbors of Sm 1].
10: end for
11: Send(Sm 11) if k 2.
12: end for
13: Output: {Sm 11
Algorithm JointInference (Modified)
1: Client:
Server:
Input: W m. Dm, {Sm 1
2: for I E do
3: Set Hm[0] = xm [m [0]
3:
=[[+]]=Aps H, 11 ..., H7)
4: for = O........ L do
Broadcast H + 1].
H [1] = a (E
Sm (]W.,, !!)
end for
if / E I then
Receive V 1
S from client Broadcast [ Ct.0
Send [ to server
Receive H. [[++) +1
H_m [1 + 1] Extract + 11, (1)
10: else
11: Set H [ -11+]=HH
12: end
13: end for
14: if 1 then
15: Compute loss c10 = ( Wi(L))
16: Send 11
C2.0 to server
17: else
18: Receive V (2
c..0 from server
19: end if
20: Output: HH m + 1]} 11 c/.0
18

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithm 7 LocalUpdate (Modified)
Input: W mn ( [1] (H'-ml 1JeE V 1 2..
2: Set H [0] X.
(m [0]]
3: for == 0, L do
4:
H = ( (E + 11.5% H (.)
5: i E I then
Set H. + = Agg H + 1], ....
else
Set H + H 1
end if
10: end for
11: if m = then
12: Compute loss c/. = (y|s fm (H [L]] [L, (ml)))
13: else
14: Compute partial loss based on V 1 c by using the chain rule: C. V c1
15: end
16: Output: Wis+1 w of V w Ct.
C Proofs for section
C.1 Assumptions
Assumption 1 (Smooth function and Lipschitz gradient). The loss function is Gr-smooth with Le- Lipschitz gradient, i.e.,
| W) - S, W'll S Ge w V W) Vw-ely,S, W'll S Le |W w'l. W.W'
and each client's prediction function fm Gsmoohhh with Ly Lipschitt gradient, i.e.,
(S, W m) - (S, W Wnn)l S Gy [ m W V...fmle W.) Vw fm (S, W W $ L, | m W A W W m. m.
Assumption 2 (Lower-bounde objective). The training objective is bounded below; that is, there erists constant. L -00 such that for all (W.),, it satisfies that
C(W 2
Assumption 3 (Uniform sampling). At each ileration I, the server and the clients uniformly sample modes (S.m oor with [S[T]] S, according to Algorithm
C.2 Proof of Theorem 1
We first note the following useful relation:
||a + b112 = |aa c = oll + +11+ d ||c b11 Va 0.
(4)
For notation simplicity, let us denote the expectation conditioned on all the information before iteration as
E Es W WO. W St-1
S
denote the "all-but-m" vector as (-)-my (e.g., the collection of all client parameters except for client
is W m (Wme m mm denote the client model updated with data S as (S.(S); denote the gradient
19

---

Published in Transactions on Machine Learning Research (04/2024)
evaluated with data S on parameter Wm as VL(W (S), and denote the stacked gradient of all clients as G (S), ... WL(WMM(S) S) Then, the update rule can be rewritten as:
Wh+ w n
(5)
In addition, let define virtual model sequence updated with full data W(D) ie.,
W = "VV
(6)
We can bound the variance of the stochastic gradient at any round t and iteration q = with the following lemma:
Lemma 1 (Bounded variance). Under Assumptions with probability at least p = 1- 8, the variance of the stochastic gradient bounded by:
E
- -V( Sa,
W independent of S'
(7)
where
2d + 128L; (c) + 5)) log
2d 8
+ 2)
a = L log
(8)
8
The main technique for proving this lemma is use the matrix Bernstein incquality (Tropp 2015 to bound the variance of the stochastic gradients and the variance of the expectation for each client. The proof steps of Lemma 1 follows the same steps in the proofs for Lemmas and 6 of Ramezani et al. 2020 omit them here.
Further, we bound the Lipschitz constant of the total loss function in the following lemma:
Lemma 2 (Tipschitz gradient). Under Assumptions the full gradient and each partial gradient of the objective S(W,S) are Lipschitz continuous with uniform constant Co GeLs + GGLe:
VwC(WW, S) - V C S]]| & Co [W W A W, W www.f(WW55 - Vw, w(w, s) S Co W W A W,W, Ww m.
The proof of Lemma is given below in Section
C.3
With the above results, we begin our proof for Theorem
First, applying Lemma 2 we have:
L(Wtatt D) - L(W">, D) s (VL(W*. D), Wh++1 wha) + Co (VL(W" D), G*.) Con
Wh++1 w
2
|
(9)
(b) (|VZLW''., ",)l + |
| -
+ Con G
3/5 VC(W"' D) [1 - ,,6o)
|| G
7 2
VC(W*. D) c
where step (a) applies the update rule of Algorithm and step (b) uses the fact that (a, 1/ [Iall + 1|b12 - l|a - b Taking expectation, we have:
E'(L(W D) L(W (/w'",D))) D) <
" E² /L(WC.,
! (1- Co) E' G + g² VL(W6., D) G
2
(
E² 3'lv D)|| + E VL(W'. D) -
1(1 (Coo
E' . 2 +
2
20

---

Published in Transactions on Machine Learning Research (04/2024)
(6) 7 E'
VL(W D)[2 -1- -1 + 1 -E G'
!
(1
1
E
VL(W". D) - | + (1 CC) E | G G G2
2
E
VL(W D)1
b/2 2 - -1 + 1/ C E G - E' G
2
Term
1 Co
+
E'
VL(W D) E'' 1
(10)
2Co
Term 2
where step (a) uses the fact that B(X)²= we bound Term and Term the above inequality separately.
(EX))) and step (b) uses 4 with a = -7C.. Next,
C.2.1 Bound of term First,
we can rewrite E E²' Gi:al1 as:
B - E G -= Σ
E'
VL(W" Es VL(W (S),
M
(11)
E
WVC(W (D)
where step (a) uses the fact that E(X - B(X))² < E(X - Y)² for all constant Y. Then, we can bound A as follows. When 0, by Lemma we obtain that A S holds with probability - In general, when g 2 1, we have:
2B
VL(W (S',
+ +2
(VL(W" -VC |)]
(12)
20 g
|| (D) + +2 -
20 E.
|| wD)
+
which holds with probability - 8. Here, step (a) applics Lemma to the first term and step (b) applics Lemma to the second term. Then, we bound E² (S*) w w (D)] in the above equation as:
E
W g. (S*)
w (D)](
(0)
E'
W1.0 n
VL VLWLL (S), (8))
W 17
Wh. (D).
1
gt
VL(W (8'), VCCC-LC (D) (D), D))
(0)
92Q
Σ
E
(5) (S) VL(W!.
VL(W!!
(D), D) (
0==0
21

---

Published in Transactions on Machine Learning Research (04/2024)
q-1 1744
1.9 A
(13)
m
9'=0
where in step (a) we expand the updates to w with (5) and (G); step (b) cancels W m and rearrange the terms; and step (c) applics the Sauchy-Schware inequality. At this point, we have the following relations:
E' E² GO G
A
A 20, Sa,
And s 20
A + 20, V q 2 1.
Note that 9 Q. By choosing Cz s the terms, we have the following bounds:
and by recursively substituting 1, which implies that n v2QC,
14 A. & 2 44 C8 + 3 g as
3 0.
(14)
14Mo 0 5
G - E G v M. 2+ 4q 12 + 3 "
cd
3
This completes bounding the term B|| G E' G3.
C.2.2 Bound of term 2
We have the following series of relations:
E²
VL D) E' G G
Σ E' [w. D) Es (S)
M
E² Es
Vw (w., Es ($)
m=1
(6)
M
C6 E
Es
- w w
m=1
M
Σ m=1
c EL'
Es
-
Σ
whig(s)) - W
mmmm
M
c n"
VC(W (C( - (S),
Es
m=1
2 W ( SS):
Σ
m' fm
(d)
S 1/ 9
Σ
M r-p
Σ
E'
Es
(VV,) (S)
0'=0
VL(WLY (S): (S):))
M q-1
(c) PM 1)C8g
E'
Es
tid (S) ?
E G 3 (M + 1)C89
22

---

Published in Transactions on Machine Learning Research (04/2024)
@ Tf + 1)089
Σ E² G
E² G + | G 19]
(15)
where step (a) uses Assumption inequality, that is
3 which states that S is uniformly sampled from D, and applics Jensen's 's
Es Vw.. ((W - Es 3S)
I Es Vw.. ((W.
(S):
step (b) applies Lemma 2 and uses the fact that VL( (S'), is evaluated on WLr(S") and W in
step (c) we expand the update steps until 1, O with 5 : step (d) applies Cauchy-Schwarz inequality; in step
(e) we reorder the sum and apply the iid. Assumption 3 to S;S;; and in step (g) we plug in the definition
of G. This completes bounding the term E' VL(W"., D) E'' G
C.2.3 Proof of the main result
Substituting the last term in [10 with 15
we obtain that the following holds with probability (1 - 8)2:
E'[c(W D) - L(w', D) S
E² /LC(W 3/2 (1-
|| Gl
2
+ n²C E² G - E G
1 + r/Co 12 + 1)69 Σ E
G -
E Gh. -
E G ["]
-
2Cu
S " E' /L || "
(1 nL)
|E' G
2
2
1 + no
1/² 12(M + 1)089 Σ E² E G |
20n
+ :2 (1 (1+ r1)) (M + 1) n122
14Mo
2
3
where in the second inequality, we set - v20c plug in (4),, and use the fact that S Q. Averaging over t= o..... T --1 1 and q- = O....,.. Q 1 and reorganizing the terms, we obtain:
T Q-11
E
D)1l S B(c(W9) C((T-)
2 1/TQ
TQ
1= 0=0
1 C (1 + (1 + n)) (M 1) Q2)
T-1Q-1
Σ
Σ
E
E'
TQ
1=0 q=0
+ 2n/oo (1+ (1+ (M + 1) -102
14Mo
3
which holds with probability at least (1 (1- Let 6 6= 8TQ E (0, 1); then, the above equation holds with probability at least
(1 - 61'8) TQ > 8/TQQ x TQ = 1
Let
1- no (1 C1) (M + 1) Q²) 2 0,
( S (6-(++MMQT))
1 and apply Assumption 2 Then, we have
2(C(W))-() L*) 28 (Co + VM + +QQ nTQ
TQ
E
o,
(16)
23

---

Published in Transactions on Machine Learning Research (04/2024)
which holds with probability at least - 6, where
a = L3 log 2dTQ + 12812 (G++})
[/++3 11
:) (olg (2TQ )
8
This completes the proof of Theorem
C.3 Proof for Lemma
In this subsection, we prove
[VW Vw C / w
and
Vw.. Vw.,C(W) - Vw, ((W' Co |W W - W
Note that Vw.. C(W) is [VW) Vw-((W))) Therefore, only need to prove the first inequality.
sub-vector of VL(W),
V ((w) Vw ((W))
The gradient VC(W) can be expanded as
VL(W)- = Jm, W)) VS(Sm(S, W)) Vw W) V((fm)) V.m(
(17)
where in the last equation omit the irrelevant variables. Then, have
[V((W) VC(W)) [f) V (w) - V((")) (W")) (Ve(m) - fm (W"]l
[V((m) (m
[V((f)) (Vfm V... ||| [( ve(f(.)) (m))
(18)
( ([V((()) - V [VE(fm))I fm (W) v.
G.L, w/ll Le (W)) - fmm)lll
0 (GoLy + L. |W - wll.
where step (a) uses the fact that ||a + b11 < |a||| + ||b|| step (b) uses the fact that |ab|| < ||||| |b]|] and in step (c) we apply Lemma 2 (that is, for any G-smooth function its gradient is bounded as ||V < G) to the first and the fourth terms and Lipschitz gradient to the second and the third terms. This completes the proof Lemma
Experiment details
D.1 Details of the datasets
Planetoid (Yang al. 2016): This collection contains three citation datasets: Cora, PubMed, and CiteSeer. Each dataset contains one citation graph, whore the nodes represent papers and edges represent citations. bag of words and the classification target is the paper category. In the experiment, each client holds non-overlapping block of node features and subgraph that results from uniformly sampling 80% of the edges.
The node features
HeriGraph (Bai et al. 2022): This collection contains three multi-modal graph datasets, each of which is constructed from heritage data posted on social media for particular city (Suzhou, Amsterdam, and Venice). Each post contains user information, timestamp, geolocation, image, and text annotation. The posts are connected form three subgraphs: social subgraph, spatial subgraph, and a temporal subgraph. The social subgraph is formed based friendship and common-interest relations of the users. The spatial
24

---

Published in Transactions on Machine Learning Research (04/2024)
subgraph is formed based the spatial proximity of the geolocations. The temporal subgraph is formed based on the temporal proximity of the posts. Each post has three blocks of image features and possibly text features; for classification, it belongs to one of nine heritage attributes. In the experiment, each client holds one the three subgraphs and one of the three image feature blocks.
Reddit. (Hamilton al. 2017|: Reddit. a large online community where users post and comment on different topics. Each node represents post and the features are the text of the post. Two posts are connected if the same user comments both. The classification target is the community (subreddit) that post belongs to. Similar to Planetoid, in the experiment, each client holds non-overlapping block of node features and a subgraph that results from uniformly sampling 80% of the edges.
D.2 Details of the experiments
Here provide list of hyperparameters for grid search in Table G The optimal set of hyperparameters for each setting is luned according to the range listed in the lable. A summary of the details of the dalasets is given in Table !
Table 6: Hyperparameter grid search range for the numerical experiments.
Hyperparameter
Grid search range
Hidden dimension of H(]
{128, 192, 256, 384)
Batch size S
{16, 32}
Neighborhood sample size
(2,3, 4, 8,
Training rounds T
(512, 640, 1024, 3200
Learning rate y
(1,2,3,5,5,7,8) (10 10 10-3)
25


Reviews:
[{"review_id": "mVx6gCdfPv", "reviewer": "Reviewer_e65R", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ Studying VFL over graph data is of importance and practical impact.\n+ The proposed GLASU method is well-presented and easy to follow.\n+ Both theoretical analysis and experimental results are shown to justify the effectiveness of GLASU.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes GLASU, a novel approach to Vertical Federated Learning (VFL) with graph data, addressing the communication overhead encountered in training graph neural networks (GNNs) in VFL. Traditional VFL methods fail to consider the relational structure between samples, which is crucial in many applications like healthcare and finance. GLASU overcomes these limitations by proposing a model-splitting method alongside a communication-efficient algorithm that employs lazy aggregation and stale updates. Theoretical analysis and experiments on synthetic and real data justify GLASU's effectiveness.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- It would be great also to discuss the capability of GLASU to support heterogeneous clients/hardware, e.g., some clients may have larger memory and can compute faster than others.\n- It would be great to motivate the problem using 1-2 real-world applications, e.g., which types of graph data are distributed across clients in a vertical manner?\n- It would be great to discuss how users may determine the number of stale updates hyperparameter Q, as GLASU's performance seems to be affected by the values of Q.", "broader_impact_concerns": "There is no concern on the ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "8QV9oWMlUT", "reviewer": "Reviewer_XCzH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strengths of this paper lie in the exposition. They explain well how their method generalizes existing methods. The experimental evaluation seems thorough - however I am not familiar with GCN & VFL datasets. The only weakness I can identify in the experimental section is the small number M of clients considered. I have not analyzed their proof in detail, however I appreciate how the authors connect their empirical insights to theory.\n\nWeakness: The only novelty I observe method-wise is the layer-communication sampling and feature re-use. While is not a accept/reject criterium, I nevertheless feel that the paper is quite \"light\".\nI might be too far away from the GCN & VFL field, but I would like to understand the relevance of this problem better. The authors provide the example of siloed company-internal client networks. Is there really such a use-case? When are companies required to keep their internal databases siloed this way? If the authors could include additional, more-detailed use-cases (in the appendix), then the paper would be more approachable.\n\nCould the authors explain why it is necessary to build the union over the sub-sampled nodes? I imagine that this negatively influences scaling with M. If the server aggregates across different nodes per client, could the \"missing\" nodes be substituted by 0 in spirit of dropout?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors consider a special case of vertical federated learning, where each node's features of a graph are distributed among clients as well as the edge set for those partial features are different across clients. Within this special case, the authors generalize the methods of Ni et al. (2021) who communicate in all layers of the network and Zhou et al. (2020), who communicate only once, therefore allowing to interpolate these two cases. Furthermore they introduce the notion of clients operating on stale features of other clients to reduce communication further.\nThe authors further provide convergence analysis for their algorithm and provide experimental evidence for the trade-offs they introduce.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- I am missing a comparison of the concatenation vs. averaging aspect to their method, did I miss it?\n- I would like to understand concrete GB communicated experiments to understand how practicable this method is to potential out-of-data-center applications. \n- I would like to see empirical results on scaling of M to larger values, but I don't see it as critical. E.g. the CiteCeer data-set seems to have some room to split features further.", "broader_impact_concerns": "No", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Fk7Mtnbq4a", "reviewer": "Reviewer_Nd4c", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths: \n- The motivation of this paper is very clear. The paper tackles the problem of VFL on graphs, which is a practical scenario where different organizations have a set of overlapping users with distinct features, and the users are connected with different links. Moreover, the authors identify a practical problem that each layer of the federated GNN requires client-server communication, which leads to very large communication overhead. These motivations are clear and practical. \n- The proposed technique seems simple and easy to implement. In addition, the experimental results seem good with good accuracy and less time needed. \n- The paper is generally well-written and easy to follow. \n\n## Weaknesses: \n- From my perspective, the setting of this paper seems narrow. It is very rare for a number of organizations to have exactly the same set of users, and thus, there has to be a lot of users who cannot be included in the VFL. How many overlapping users can be benefitted, and how other users can benefit from the VFL is a practical question but is not well answered. The authors use primarily manually partitioned data for the experiments, further leaving the question unanswered. \n- Why GLASU is related to node sampling is not very clear. From my perspective, it is also OK to perform full-graph training (i.e. we train all all nodes instead of sampling a few nodes), especially because the datasets are relatively small (even reddit can be put on a single GPU like V100). The authors may want to clarify the need for node sampling (e.g. FastGCN sampling). The authors may strengthen the point of node sampling with some larger graphs in the experiments. \n- From my perspective, GLASU seems like a trade-off between accuracy (i.e. up-to-date embeddings and gradients) VS efficiency. Therefore, I expect to see some more discussions on the trade-off. For example, in Table 2 and Table 3, I would like to see some more results on, e.g., the number of iterations needed for convergence, the total/per iteration communication quantity, etc. \n- Some experimental results do not seem to make sense. I can understand that $K=4$ may not be optimal, as setting $K$ to a lower value may resemble some regularization effects like DropEdge. However, how $Q>1$ achieves better accuracy is beyond me (e.g. Table 3, Q=8 is generally better than Q=4, and on Amsterdam, Q=8 is better than Q=2). These results may require some more explanation. \n- I am fully aware that TMLR does not require a technique to be 'novel'. However, I have to point out that this paper draws insights heavily from existing works like FedBCD (Liu et al. 2022), such as the stale update technique and the theoretical analysis. Therefore, the additional insights of this paper maybe somewhat limited. **Note again that this should not be a weakness according to TMLR requirements.**", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes GLASU, a method for communication-efficient VFL over graph data. The main motivation of this paper is that VFL combined with neighborhood aggregation in GNN causes a very large communication overhead, and takes measures to reduce the communication overhead, including lazy aggregation and stale update. Theoretical proof is given to prove the convergence of GLASU (although I may not have the expertise to evaluate its correctness). Numerical experiments with multiple GNN backbones, 7 datasets, and different parameter settings of $Q, K$ are given to showcase the effectiveness of the proposed GLASU.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Discuss how many nodes may be aligned and held jointly by multiple organizations in practice. Also, discuss how non-aligned nodes can benefit from VFL. \n2. Justify the relation between GLASU and node sampling algorithms; or use larger datasets to more properly motivate the need for node sampling algorithms. \n3. Show more trade-offs between accuracy, convergence, communication, etc. (e.g. communication quantity, training iterations, etc. ) in Tables 2 and 3. \n4. Explain why larger staleness may lead to better accuracy.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers vertical federated learning, where each node's features of a graph are distributed among clients, and the edge set for those partial features are different across clients. It proposes a model-splitting method and a communication-efficient algorithm with lazy aggregation and stale updates.

All reviewers think the problem is interesting and the proposed methods are solid. One major concern from two reviewers is about the practical value of the setting. In practice, different institutes might not be willing to share information of their own data, and the overlap of the corresponding graph might be small. I agree with the reviewers that the provided examples by the authors might not be a good one, but also think that the proposed setting indeed has some potential practical values. I encourage the authors to replace the currently used example with another one, maybe considering the same institute holding data in different sites, which can be a more suitable example.

Other than the above, I agree with the reviewers that the proposed techniques are solid. Thus, I recommend accept with minor revision according to the reviewer comments.
Decision: Accept (poster)