Subgraph Federated Learning with Missing Neighbor Generation
Authors: Ke ZHANG
Carl Yang
Xiaoxiao Li
Lichao Sun
Siu Ming Yiu
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: graph mining
federated learning
subgraph node classification
neighbor prediction
generative model

Abstract: Graphs have been widely used in data mining and machine learning due to their unique representation of real-world objects and their interactions. As graphs are getting bigger and bigger nowadays, it is common to see their subgraphs separately collected and stored in multiple local systems. Therefore, it is natural to consider the subgraph federated learning setting, where each local system holds a small subgraph that may be biased from the distribution of the whole graph. Hence, the subgraph federated learning aims to collaboratively train a powerful and generalizable graph mining model without directly sharing their graph data. In this work, towards the novel yet realistic setting of subgraph federated learning, we propose two major techniques: (1) FedSage, which trains a GraphSage model based on FedAvg to integrate node features, link structures, and task labels on multiple local subgraphs; (2) FedSage+, which trains a missing neighbor generator along FedSage to deal with missing links across local subgraphs. Empirical results on four real-world graph datasets with synthesized subgraph federated learning settings demonstrate the effectiveness and efficiency of our proposed techniques. At the same time, consistent theoretical implications are made towards their generalization ability on the global graphs.

Subgraph Federated Learning with Missing Neighbor Generation
Ke Zhang Carl Yang' Xiaoxiao Li², Lichao Sun Siu Ming Yiu'
Emory University, 2 University of British Columbia, 'Lehigh University, 'University of Hong Kong
kzhang20cs hhu.kkk j. www.rraaannemory...oooooo xiaoxiao licelee...@ee..... ubc. ca, 1is2210lehigh edu, smyluêcs hku.
Abstract
Graphs have been widely used in data mining and machine learning due to their unique representation of weal-world objects and their interactions. As graphs are getting bigger and bigger nowadays, it is common to see their subgraphs separately collected and stored in multiple local systems. Therefore, it is natural consider the subgraph federated learning setting, where each local system holds small subgraph that may be biased from the distribution of the whole graph. Hence, the subgraph federated learning aims to collaboratively train powerful and generalizable graph mining model without directly sharing their graph data. In this work, towards the novel yet realistic setting of subgraph federated learning, we propose two major techniques: (1) FedSage, which trains a GraphSage model based on FedAvg to integrate node features, link structures, and task labels multiple local subgraphs; (2) FedSage+, which trains missing neighbor generator along FedSage to deal with missing links across local subgraphs. Empirical results four real-world graph datasets with synthesized subgraph federated learning settings demonstrate the effectiveness and efficiency of our proposed techniques. At the same time, consistent theoretical implications are made towards their generalization ability the global graphs.
Introduction
Graph mining leverages links among connected nodes in graphs to conduct inference. Recently, graph neural networks (GNNs) have gained applause with impressing performance and generalizability in many graph mining tasks 229
16 20 32). Similar to machine learning tasks in other domains, attaining werf-oerf GNN model requires its training data to not only be sufficient but also fol- low the similar distribution as general queries. While in reality, data owners often collect limited and biased graphs and cannot observe the global distribution. With heterogeneous subgraphs separately stored in local data owners, accomplishing a globally applicable GNN requires collaboration.
Federated learning (FL) 17 35). targeting training machine learning models with data distributed in multiple local systems to resolve the information-sile problem, has shown its advantage in enhancing the performance and generalizability of the collaboratively trained models without the need of sharing any actual data. For example, FL has been devised in computer vision (CV) and natural language processing (NLP) to allow the joint training of powerful and generalizable deep convolutional neural networks and language models on separately stored datasets of images and texts [19
6
18
39 B
Motivating Scenario. Taking the healthcare system as example, shown in Fig. I residents of a city may go to different hospitals for various reasons. demographics and living conditions, as well as patient interactions, such as co-staying in a sickroom and co-diagnosis of a disease, are stored only within the hospitals they visit. When any healthcare problem is to be studied in the whole city, e.g., the prediction of infections when pandemic occurs,
result, their healthcare data, such as
Corresponding author.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

HospRalA
Joindy training without sharing graph data
HosptalB
Medical Administaatin Center
City daagnose
Hospiall C
HosphalD
Figure I: A toy example of the distributed subgraph storage system: In this example, there are four hospitals and medical administration center. The global graph records, for a certain period, the city's 's patients (nodes), their information (attributes), and interactions (links). Specifically, the left part of the figure shows how the global graph is stored in each hospital, where the grey solid lines are the links explicitly stored in each hospital, and the red dashed lines are the cross- hospital links that may exist but without sharing actual data, the system obtains a globally powerful graph mining model.
stored in any hospital. The right part of the figure indicates our goal that
single powerful graph mining model is needed to conduct effective inference over the entire global patient network, which contains all subgraphs from different hospitals. However, is rather difficult to let all hospitals share their patient networks with others to train the graph mining model due to conflicts of interests and privacy concerns.
In such scenarios, it is desirable to train powerful and generalizable graph mining model over multiple distributed subgraphs without actual data sharing. However, this novel yet realistic setting brings two unique technical challenges, which have never been explored so far.
How to jointly learn from multiple local subgraphs? In considered scenario, the global graph is distributed into a set of small subgraphs with heterogeneous feature and structure distributions. Training a separate graph mining model on each subgraph may not capture the global data distribution and is also prone to overfitting. Moreover, it is unclear how to integrate multiple graph mining models into a universally applicable one that can handle any queries from the underlying global graph.
Challenge I:
Solution 1: FedSage: Training GraphSage with FedAvg. To attain powerful and generalizable
graph mining model from small and biased subgraphs distributed in multiple local owners, we develop framework of subgraph federated learning, specifically, with the vanilla mechanism of FedAvg [21] As for the graph mining model, we resort to GraphSage 11.. due to its advantages of inductiveness and scalability. We term this framework as FedSage.
Challenge 2: How to deal with missing links across local subgraphs? Unlike distributed systems in other domains such as CV and NLP, whose data samples of images and texts isolated and independent, data samples in graphs are connected and correlated. Most importantly, in a subgraph federated learning system, data samples in each subgraph can potentially have connections those in other subgraphs. These connections carrying important information of node neighborhoods and serving as bridges among the data owners, however, are never directly captured by any data owner.
Solution FedSage+: Generating missing neighbors along FedSage. To deal with cross- subgraph missing links, we add missing neighbor generator top of FedSage and propose novel FedSage+ model. Specifically, for each data owner, instead of training the GraphSage model on the original subgraph, it first mends the subgraph with generated cross-subgrapp missing neighbors and then applics FedSage on the mended subgraph. To obtain the missing neighbor generator, each data owner impairs the subgraph by randomly holding out some nodes and related links and then trains the generator based on the held-out neighbors. Training the generator on an individual local subgraph enables it to generate potential missing links within the subgraph. Further training the generator in our subgraph FL setting allows it to generate missing neighbors across distributed subgraphs.
We conduct experiments on four real-world datasets with different numbers of data owners to better simulate the application scenarios. According to our results, both of our models outperform locally trained classifiers in all scenarios. Compared to FedSage, FedSage+ further promotes the performance of the outcome classifier. Further in-depth model analysis shows the convergence and generalization ability of our frameworks, which is corroborated by our theoretical analysis in the end.

---

2
Related works
Graph mining. Graph mining emerges its significance in amalyzing the informative graph data, which range from social networks to gene interaction networks [3] 33 34 24]. One of the most frequently applied tasks on graph data is node classification. Recently, graph neural networks (GNNs), e-g. graph convolutional networks (GCN) [T6] and GraphSage Ii. improved the state-of-the-ar in node classification with their elegant yet powerful designs. However, as GNNs leverage the homophily of nodes in both node features and link structures conduct the inference, they are vulnerable to the perturbation on graphs 4 40 41]. Robust GNNs, aiming at reducing the degeneration in GNNs caused by graph perturbation, are gaining attention these days. Current robust GNNs focus on the sensitivity towards modifications on node features [ 42 15 or adding/removing edges on the graph [37]. However, neither of these two types recapitulates the missing neighbor problem, which affects both the feature distribution and structure distribution.
To obtain node classifier with good generalizability, the development of domain adaptive GNN sheds light on adapting a GNN model trained on the source domain to the target domain by leveraging underlying structural consistency 38 36 28 However, in the distributed system we consider, data owners have subgraphs with heterogeneous feature and structure distributions. Moreover, direct information exchanges among subgraphs, such as message passing, are fully blocked due to the missing cross-subgraph links. The violation of the domain adaptive GNNs' assumptions on alignable nodes and cross-domain structural consistency denies their usage the distributed subgraph system.
Federated learning. FL is proposed for cross cross-insiiuttional collaborative learning without sharing raw data [17 (2]] FedAvg [21] is efficient and well-studied FL method. Similar to most FL methods, is originally proposed for traditional machine learning problems (35 to allow collaborative training on silo data through local updating and global aggregation. The ecently proposed meta-learning framework [9] [3 14
that exploits information from different data sources to obtain a general model attracts FL researchers [8. However, meta-learning aims to learn general models that easily adapt to different local tasks, while we learn generalizable model from diverse data owners to assist in solving a global task. In the distributed subgraph system, to obtain globally applicable model without sharing local graph data, we borrow the idea of FL to collaboratively train GNNs.
Federated graph learning. Recent researchers have made some progress in federated graph learning. There are existing FL frameworks designed for the graph data learning task [22 27
30 [2]
design graph-level FL schemes with graph datasets dispersed over multiple data owners, which are inapplicable to our distributed subgraph system construction. (27) proposes an FL method for the recommendation problem with each data owner learning on a subgraph of the whole recommendation user-item graph. It considers a different scenario assuming subgraphs have overlapped items (nodes), and the user-item interactions (edges) are distributed but completely stored in the system, which ignores the possible cross-subgraph information lost in real-world scenarios. However, we study a more challenging yet realistic case in the distributed subgraph system, where cross-subgraph edges are totally missing.
In this work, consider the commonly existing yet not studied scenario, i.e., distributed subgraph system with missing cross-subgraph edges. Under this scenario, we focus on obtaining a globally applicable node classifier through FL. on distributed subgraphs.
3 FedSage
In this section, we first illustrate the definition of the distributed subgraph system derived from real-world application scenarios. Based on this system, we then formulate our novel subgraph FL. framework and vanilla solution called FedSage.
3.1 Subgraphs Distributed in Local Systems
Notation. We denote a global graph as G = {V, E, X), where V is the node set, X is the respective node feature set, and E is the edge set. In the FL system, we have the central server S, and M data owners with distributed subgraphs. G; = [V, E,, X.} is the subgraph owned by D,, for i E [M].
Problem setup. For the whole system, we assume V .U... To simulate the scenario with most missing links, we assume no overlapping nodes shared across data owners, namely V; n VV 0 for Vi,j E [M] and i / j. Note that the central server S only maintains a graph mining model with no actual graph data stored. Any data owner D; cannot directly retrieve u E Vú from another data
3

---

owner Dj. Therefore, for an edge Cv.u E E, where E V; and E Vj. Cr & E, Eg, that is, Cv,u might exist in reality but is not stored anywhere in the whole system.
For the global graph G = [V, F,, } every node v E V has its features Top E X and one label y/ Y for the downstream task, e.g., node classification. Note that for V, v's feature 2, E gd and respective label Yo is a dy dyydinnnsional one-hot vector. In a typical GNN, predicting node's label requires an ego-graph of the queried node. For a node v from graph G, we denote the queried ego-graph of G(v), and (G(u), yo) De.
With subgraphs distributed in the system defined above, we formulate our goal as follows.
Goal.
The system exploits an FL framework to collaboratively learn on isolated subgraphs in all data owners, without raw graph data sharing, obtain global node classifier F. The learnable weights @ in F is optimized for queried ego-graphs following the distribution of ones drawn from the global graph G. We formalize the problem as finding o" that minimizes the aggregated risk M
= arg min ((F())) = M Σ Ra(F(())),
1
where R2 is the local empirical risk defined as
R. (F)) E B(G,, [((FF((d G.), Y.M,
where l is a task-specific loss function
Σ FE
((0: (t),
3.2 Collaborative Learning Isolated Subgraphs
To fulfill the system's 's goal illustrated above, we leverage the simple and efficient FedAvg framework [21] and fix the node classifier F as GraphSage model. The inductiveness and scalability of the GraphSage model facilitate both the training on diverse subgraphs with heterogeneous query distributions and the later inference upon the global graph. We term the GraphSage model trained with the FedAvg framework as FedSage.
For queried node v E V. globally shared K-layer GraphSage classifier F integrates v and its K-hop neighborhood on graph to conduct prediction with learnable parameters & {00 1p" 1k=1- Taking subgraph G; an example, for V, with features as ho Fy, at each layer k [K], F computes v's representation h.: as
h = (0+ (he (fh Vu E Naa (v)))))
where No. (v) is the set of e's neighbors on graph G,, || is the concatenation operation, Agg(.) the aggregator (e.g., mean pooling) and a is the activation function (e.g., ReLU).
With F outputting the inference label T. Softmax(h,5 for E Vi, the supervised loss function 1(01-) is defined as follows
_ I(d)G, yo) Cy V vo) = (yo log Te + (1 - yo) log (1 Vo)]
(2)
where CE(() is the cross entropy function, Gz(U) is u's K-hop ego-graph G,, which contains the information of u and its K-hop neighbors on G;-
In FedSage, the distributed subgraph system obtains shared global node classifier F parameterized by Φ through eq epochs of training. During each epoch I, every D; first locally computes di <- E V)'), where V/¹ C V; contains the sampled training nodes for epoch I,
17 (()) ((G) (V and 77 is the learning rate; then the central server S collects the latest {øvlé E [M]]; next, through averaging over { E [M]], S sets @ as the averaged value; finally, S broadcasts @ to data owners and finishes one round of training F. After e, epochs, the entire system retrieves F' as the outcome global classifier, which is not limited to biased towards the queries in any specific data owner
yo)(w
Unlike FL on Euclidean data, nodes the distributed subgraph system can have potential interactions with each other across subgraphs. However, as the cross-subgraph links cannot be captured by any data owner the system, incomplete neighborhoods, compared to those on the global graph, commonly exist therein. Thus, directly aggregating incomplete queried ego-graph information through FedSage restricts the outcome from achieving the desideratum of capturing the global query distribution.

---

NeighGen
Graph mending
H
Ha
hide
dGen
GNN
N
GNN
FNN
P
fGen
6
61
Figure 2: Joint training of missing neighbor generation and node classification.
4 FedSage+
In this section, we propose a novel framework of FedSaget, Le., subgraph FL with missing neighbor generation. We first design missing neighbor generator (NeighGen) and its training schema via graph mending. Then, we describe the joint training of NeighGen and GraphSage to better achieve the goal in Section [3.1] Without loss of generality, in the following demonstration, take NeighGen,, ie., the missing neighbor generator of D,, as an example, where E [M].
4.1 Missing Neighbor Generator (NeighGen)
Neural architecture of NeighGen. As shown in Fig. 2 NeighGen consists of two modules, ie., an encoder Hf and generator 4 We describe their designs in details in the following.
4: A GNN model, i.e., K-layer GraphSage encoder, with parameters 0 For node E V2 on the input graph G;, H computes node embeddings Z; = [2 zu = h 2p E Rdd, E Vi} according to Eq. ① by substituting G with 8 and G,,
Hº: A generative model recovering missing neighbors for the input graph based on the node embedding. H contains dGen and fGen, where dGen is linear regression model parameterized by 0² that predicts the numbers of missing neighbors N; ( E N, E Vi). and fGen is feature generator parameterized by of that generates a of N, feature vectors X; {āo| Rd, My E N₁ E V.). Both dGen and fGen are constructed as fully connected neural networks (FNNs), while fGen is further equipped with Gaussian noise generator N(0, that generates d_ d--dimensional noise vectors and a random sampler R. For node V,, fGen is variational, which generates the missing neighbors' features for after inserting noises into the embedding 2., while R ensures fGen to output the features of a specific number of neighbors by sampling Th, feature vectors from the feature generator's output. Mathematically,
have
nh = (((")T ne), and F. R (a ((0F)T. (Z. N(O, 1)), m.))
Graph mending simulation. For each data owner in our system, we assume that only a particular set of nodes have cross- sussgaub missing neighbors. The assumption is realistic yet non-trivial for it both seizing the quiddity of the distributed subgraph system, and allowing us to locally simulate the missing neighbor situation through graph impairing and mending process. Specifically, to simulate graph mending process during the training of NeighGen, in each local subgraph G3 we randomly hold out 4% of its nodes V C Vi and all links involving them E. {euv/uu /u V or V.a} E,, to form an impaired subgraph, denoted as G, G; = V,, E,, X, contains the impaired set nodes V. = V/ V. the corresponding nodes features X, = X₁ \ X and edges E, = E, \ E
Accordingly, based on the ground-truth missing nodes V and links E. the training of NeighGen the impaired graph G; boils down to jointly training dGen and fGen as below.
-" -
L.
ΣΣ
(1 x. x..1)), (4) PE seNa,(onny
min
[
M.
where L is the smooth LI distance 10 and 25 Rd. the p-th predicted feature in T... Note that, NG. (v) n 1.th contains n. nodes that are t's neighbors G, missing into NG (v) V. which can be retrieved from hhh and EN, provides ground-truth for training NeighGen.
5

---

To retrieve G;; from G,, data owner D; performs two steps, which are also shown in Fig. 2 1) D; trains NeighGen on the impaired graph G; w.r.t. the ground-true hidden neighbors Vi 2) D; exploits NeighGen to generate missing neighbors for nodes on G; and then mends G2 into G., with generated neighbors. On the local graph G, alone, this process can be understood as data augmentation that further generates potential missing neighbors within G,- However, the actual goal is to allow NeighGen to generate the cross-subgraph missing neighbors, which can be achieved via training NeighGen with FL and will be discussed in Section 4.3
Neighbor Generation.
4.2 Local Joint Training of GraphSage and NeighGen
While NeighGen is designed to recover missing neighbors, the final goal of our system is to train node classifier. Therefore, we design the joint training of GraphSage and NeighGen, which leverages neighbors generated by NeighGen assist the node classification by GraphSage. We term the integration of GraphSage and NeighGen on the local graphs as LocSaget.
After NeighGen mends the graph G₁ into Gj, the GraphSage classifier F is applied on G₁,, according to Eq. (I) (with G; replaced by G)). Thus, the joint training of NeighGen and GraphSage is done by optimizing the following loss function
L == +X
= ==--==--- x + + C
(5)
where Ld and L are defined in Eq. and L is defined in Eq. 2 (with G; substituted by G)).
The local joint training of GraphSage and NeighGen allows NeighGen to generate missing neighbors in the local graph that are helpful for the classifications made by GraphSage. However, like GraphSage, the information encoded in the local NeighGen is limited to and biased towards the local graph, which does not enable it to really generate neighbors belonging to other data owners connected by the missing cross-subgraph links. To this end, it is natural to train NeighGen with FL. as well.
4.3 Federated Learning of GraphSage and NeighGen
Similarly to GraphSage alone, as described in Section 3.2 can apply FedAvg the joint training of GraphSage and NeighGen, by setting the loss function to L and learnable parameters to {0s, 04, 04,01, 0f, However, we observe that cooperation through directly averaging weights of NeighGen across the system can negatively affect its performance, i.e., averaging the weights of a single NeighGen model does not really allow to generate diverse neighbors from different subgraphs. Recalling our goal of constructing NeighGen, which is to facilitate the training of centralized GraphSage classifier by generating diverse missing neighbors in each subgraph, we do not necessarily need a centralized NeighGen. Therefore, instead of training single centralized NeighGen, we train local NeighGen; for each data owner D,. In order to allow each NeighGen, to generate diverse neighbors similar to those missed into other subgraphs Gj.j E [M] \ (i), we add cross- coos--ubbgaph feature reconstruction loss into fGen, as follows:
2/ = 3 VI
min
Σ min (1) - Iull3)
(6)
VER. pF( NeNo, (0)))
"EV,
JE[M]/
where u E Vj. E [M] (i) is picked as the closest node from G, other than G; to simulate the neighbor of o E Vú missed into G₁.
As shown above, to optimize Eq. (6). D, needs to pick the closest from Gj. However, di- rectly transmitting node features X, in Dy to D; not only violates our subgraph FL system con- straints on no direct data sharing but also is impractical in reality, as it requires each D, to hold the entire global graph's 's node features throughout training NeighGenn, Therefore, to allow D, to update NeighGen; using Eq.
(6) without direct access to X,. for E V., Dj locally computes Epe(. min (1141) Zz, ) Iz, l1)) and sends the respective gradient back to D..
During this process, for E V.. to federated optimize Eq. 6 only Hº H.'s input 2u. and the D, 's locally computed model gradients of loss term Epe(..] m (1) - xu 1l) are transmitted among the system via the server S. For data owner D;, the gradients received from D3 are then weighted by a and combined with the local gradients as Eq. (6) to update the parameters of H of NeighGen, In this way, D; achieves the federate training of NeighGen, without raw graph data

---

sharing. Note that, due to NeighGen's 's architecture of a concatenation of Н and H the locally preserved GNN H. can prevent other data owners from inferring Z, by only seeing p.. Through Eq. (6) NeighGen; is expected to perceive diverse neighhorhood information from all data owners, so as to generate more realistic cross-subgraph missing neighbors. The expectedly diverse and unbiased neighbors further assist the FedSage in training globally applicable classifier that satisfies our goal in Section 3.1
Note that, to reduce communications and computation time incurred by Eq. (6. batch training can be applied. Appendix shows the pseudo code of FedSaget.
Experiments
We conduct experiments on four datasets to verify the effectiveness of FedSage and FedSage+ under different testing scenarios. We further conduct case studies to visualize how FedSage and FedSage+ assist local data owners in accommodating queries from the global distribution. Finally, we also provide more in-depth studies on the effectiveness of NeighGen in Appendix D.
5.1 Datasets and experimental settings
We synthesize the distributed subgraph system with four widely used real-world graph datasets, i.e., Cora [25], Citeseer (25). PubMed (22), and MSAcademic [26]. To synthesize the distributed subgraph system, we find hierarchical graph clusters on each dataset with the Louvain algorithm [2] and use the clustering results with 5, and 10 clusters of similar sizes obtain subgraphs for data owners. The statistics of these datasets are presented in Table
Table 1: Statistics of the datasets and the synthesized distributed subgraph systems with M 3, 5, and 10. #C row shows the number of classes, [Vi and [E rows show the averaged numbers of nodes and links in all subgraphs, and AE shows the total number of missing cross-subgraph links.
Data
Cora
Citescer
PubMed
MSAcademic
V
2708
3312
19717
18333
E
5429
4715
44338
81894
M
3
5
10
3
5
10
3
5
10
3
5
10
VI
903
542
271
1104
662
331
6572
3943
1972
6111
3667
1833
E,
1675
968
450
1518
902
442
12932
7630
3789
23584
13949
5915
AE
403
589
929
161
206
300
5543
6189
6445
11141
12151
22743
We implement GraphSage with two layers using the mean aggregator [5). The number of nodes sampled in each layer of GraphSage is 5. We use batch size 64 and set training epochs to 50. The training-validatte validatiootttetiinng ratio is -0%%20%%-20% due to limited sizes of local subgraphs. Based on our observations in hyper-parameter studies for a and the graph impairing ratio h, we set h% E [3.4%, 27.8%] and a=1. All As are simply set to 1. Optimization done with Adam with a learning rate of 0.001. We implement FedSage and FedSage+ in Python and execute all experiments on a server with 8 NVIDIA GeForce GTX 1080 Ti GPUs.
Since we are the first to study the novel yet important setting of subgraph federated learning, there are no existing baselines. We conduct comprehensive ablation evaluation by comparing FedSage and FedSage+ with three models, i.e., 1) GlobSage: the GraphSage model trained on the original global graph without missing links (as an upper bound for FL framework with GraphSage model alone). 2) LocSage: one GraphSage model trained solely on each subgraph, 3) LocSage+: the GraphSage plus NeighGen model jointly trained solely on each subgraph.
The metric used in our experiments is the node classification accuracy on the queries sampled from the testing nodes on the global graph. For globally shared models of GlobSage, FedSage, and FedSage+, we report the average accuracy over five random repetitions, while for locally possessed models of LocSage and LocSaget, the scores are further averaged across local models.
5.2 Experimental results
Overall performance. We conduct comprehensive ablation experiments to verify the significant promotion brought by FedSage and FedSage+ for local owners in global node classification, as
7

---

Table 2: Node classification results four datasets with M =3, and 10. Besides averaged accuracy, we also provide the corresponding std.
Cora
Citesser
Model
M=3
M=5
M=10
M=3
M=5
M=10
LoeSage
0.5762
0.4431
0.2798
0.6789
0.5612
0.4240
(+000302)
(+0.0847)
(+000080)
(+0.054)
(+0.086)
(+:00859)
LocSage+
0.5644
0,4533
0,2851
0.6848
0.5676
0,4323
(t0,0219)
(+0,047)
(#0.0080)
(=0.0517)
(+0007144
(=0.0715)
FedSage
0.8656
0.8645
0.8626
0.7241
0.7226
0.7158
(+0.0043)
(+0.0050)
(+0.0103)
(+000002)
+0.0066)
(=0.0053)
FedSage+
0.8686
0.8648
0.8632
0.7454
0.7440
0.7392
(+0.0054)
(+0.0051)
(+0.0034)
(+0.0038)
(+0.0025))
(+0.0041)
GlobSage
0.8701 (#0.0042)
0.7561 (=0.0031)
PubMed
MSAcademic
Model
M=3
M=5
M=10
M=3
M=5
M=10
LocSage
0.8447
0.8039
0.7148
0.8188
0.7426
0.5918
(+0.0047)
(+0.0337)
(+0.0951)
(+0.0331)
(=0.0790)
(+0.1005)
LocSage+
0.8481
0.8046
0.7039
0,8393
0.7480
0.5927
(=0.0041)
(10.0318)
(+0.0925)
(=000330)
(=0.0810)
(#0.1094)
FedSage
0.8708
0,8696
0,8692
0,9327
0.9391
0,9262
(+0.0014)
(+0.0035)
(+0.0010)
(+0.0005)
(+0.0007))
(=0.0009)
FodSage+
0.8775
0,8755
0.8749
0,9359
0.9414
0.9314
(+.00)))
(+0.0047)
(+000013)
(+0.0005)
(+0.0006)
(=000009)
GlobSage
0.8776(+0.0011)
0.8527
0,8468
0,8686
0.0686
03534
0 0.8524
0. 0.8701
0.8701
0.7338
CiteSeer
0.718
CiteSeer
0:7276
10.7454
0.7561
0.7561
0.8514
0.8694
PubMed
0.8755
PubMed
0.8755
FesSagei, p-0.1
0.9324
0.9211
MSAcademic
FasSspee: 1n1
FatSegee,
0. 0.9359
9261
MSAcademic
Tertsege-ht-190
0.9359
009307
0.9681
0.70
1.30 Node classification accuracy
3.55
0.50
0.55
030
0.95
0.70
0.75
0.00
oas
200
0.25
1:00
Node classification accuracy
(a) Hyper-parameter study for with h
15%.
(b) Hyper-parameter study for with 1.
Figure 3: Node classification results on four datasets under different and h values with M=3.
shown in Table 2 The most important observation emerging from the results is that FedSage+ not only clearly outperforms LocSage by an average 23.18%, but also distinctly overcomes the cubss-subgraph missing neighbor problem by reducing the average accuracy drop from the 2. 1% of FedSage to 1.28%, when compared with GlobSage (absolute accuracy difference).
The significant gaps between locally obtained classifier, i.e., LocSage or LocSage+, and a federated trained classifier, i.e., FedSage or FedSage+, assay the benefits brought by the collaboration across data owners in our distributed subgraph system. Compared to FedSage, the further elevation brought by FedSage+ corroborates the assumed degeneration brought by missing susss-uu links and the effectiveness of our innovatively designed NeighGen module. Notably, when the graph is relatively sparse (e.g., s,, see Citeseer Table []. FedSage+ significantly exhibits its robustness resisting the cross-subgraph information loss compared to FedSage. Note that the gaps between LocSage and LocSage+ are comparatively smaller, indicating that our NeighGen serves more than a robust GNN trainer, but is rather uniquely crucial in the subgraph FL setting.

---

chrs,
Gass
Locsege:
class
Ground
Glds:
Clsss
FedSage
LocSages
FedSagch
LocSagea
LocSages
GbeSage
0.0
0.2
0.4
0.6
0.8
1.
0.0
0.2
0.4
0.8
1.
(a) Local model predictions
(b) Global ground-truth vs. model predictions
Figure 4: Label distributions on the PubMed dataset with M=5.
1.0
2.5
FedBage Globsage Locfagg Locdlage!
FesSiage
0.8
FauSager
700 Nocanody
0.8
Loon Velue
GlobSage
LoeSage
Tim
150
LocSage+
Fediage Fedtage
100
GeeSage
60
0.0
20
60
100
20
40
80
%
20
40
80
100
Trainnng Epoch
(a) Accuracy curves
(b) Loss curves
(c) Training time
Figure 5: Training curves of different frameworks (GlobSage provides upper bound).
studies. We compare the downstream task performance under different and values with three data owners. Results shown in Fig. where Fig. 3 (a) shows results when is fixed as 15%, and Fig. (b) shows results under a=1.
Fig. 3 (a) indicates that choosing proper a, which brings the information from other subgraphs in the system, can constantly elevate the final testing accuracy. Across different datasets, the optimal a constantly around 1, and the performance is not influenced much unless is extreme values like 0.1 or 10. Referring to Fig. ()),, we can observe that either a too-small (1 (%) or a too- (30%) hiding portion degrade the learning process. too-small h not provide sufficient data for training NeighGen, while too-large lt can result in sparse local subgraphs that harm the effective training of GraphSage. Referring back the graph statistics in Table in the paper, the portion of actual missing edges compared to the global graph is within the range of [3.4%, 27.8%], which explains why a value like 15% can mostly boost the performance of FedSage+.
Case studies. To further understand how FedSage and FedSage+ improve the global classifier over LocSage, we provide case study results on PubMed with five data owners in Fig. 4 For the studied scenario, each data owner only possesses about 20% of the nodes with rather biased label distributions, shown in Fig. (a). Such bias is due to the way synthesize the distributed subgraph system with Louvain clustering, which is also realistic in real scenarios. Local bias essentially makes hard for any local data owner with limited training samples to obtain generalized classifier that globally useful. Although with 13.9% of the links missing among the system, both FedSage and FedSage+ empower local data owners in predicting labels that closely follow the ground-trus global label distribution as shown in Fig. (b). The figure clearly evidences that our FL models exhibit their advantages in learning consistent with the observed performances in Table and our theoretical implications in Section G
realistic label distribution our goal in Section 3.1 which is
For Cora dataset with five data owners, we visualize testing accuracy, loss convergence, and runtime along 100 epochs in obtaining F with FedSage, FedSage+, GlobSage, LocSage and LocSaget. The results are presented in Fig. 5 Both FedSage and FedSage+ can consistently achieve convergence with rapidly improved lesting accuracy. Regarding runtime, even though the classifier from FedSage+ learns from distributed mended subgraphs, FedSage+ does not consume observable more training time compared to FedSage. Due to the additional communications and computations in subgraph FL, both FedSage and FedSage+ consume slightly more training time compared to GlobSage.

---

Implications on Generalization Bound
In this section, we provide a theoretical implication for the generalization error associated with number of training samples, i.e., nodes in the distributed subgraph system, following Graph Neural Tangent Kernel (GNTK) [7] on universal graph neural networks. Thus, we are motivated to promote the FedSage and FedSage+ algorithms that include nodes in the global graph through collaborative training with FL.
Setting. Our explanation builds on generalized setting, where we assume a GNN F with layer- wise aggregation operations and fully-connected layers with ReLU activation functions, which includes GraphSage as special case. The weights of F, 6, is i..dd sampled from a multivariate Gaussian distribution (O, I). For Graph = {V, , E, },, we define the kernel matrix of two nodes u, V as follows. Here we consider F is in the GNTK format.
Definition 6.1 (Informal version of GNTK on node classification (Definition B.2)) Considering in the overparameterized regime for an GNN F, F is trained using gradient descent with infinite small learning rate. Given n nodes with corresponding labels as training samples, we denote ① E Raxa as the the kernel matrix of GNTK. Que is defined as
{ (OF(O, G,u)
F(O, ((O,G,)) }}
Que = -EENNO)
E RR.
06
06
Full expression of @ is shown in the Appendix B. The generalization ability in the GNTK regime depends on the kernel matrix O We present the generalization bound associated with the number of training samples in Theorem 6.2
Theorem 6.2 (Generalization bound) Given n truining samples of nodes (us, M:) drawn i.i.d. from the global gruph G, consider any loss function 1. R x IR + [0, 1] that is 1-Lipschitz in the first argument such that Iyy, y) = 0. With probability least generalization error of GNTK for node classification be upper-bounded by
and constant E (0, 1), the
LD(F) = [n (u (FF,), v'), v) 2 O(1/n9).
Following the generalization bound analysis in 77. we use standard generalization bound of kernel methods of [I, which shows the upper bound our GNTK formation error depends on that of y TTO "y (-1lly and tr(@). where y is the label vector. Appendix C shows the full version of the proofs.
Implications. We show the error bound of GNTK on node classification corresponding to the number of training samples. Under the assumptions in Definition 6.1 our theoretical result indicates that more training samples bring down the generalization error, which provides plausible support for goal of building globally useful classifier through FL in Eq. (3.1). Such implications also consistent with our experimental findings in Fig. 4 where our FedSage and FedSage+ models can learn more generalizable classifiers that follow the label distributions of the global graph through involving more training nodes across different subgraphs.
7 Conclusion
This work aims at obtaining generalized node classification model in a distributed subgraph system without direct data sharing. To tackle the realistic yet unexplored issue of missing cross-subgraph links, we design novel missing neighbor generator NeighGen with the corresponding local and federated training processes. Experimental results evidence the distinguished elevation brought by our FedSage and FedSage+ frameworks, which is consistent with our theoretical implications.
Though FedSage manifests advantageous performance, it confronts additional communication cost and potential privacy concerns. As communications are vital for federated learning, properly reducing communication and rigorously guaranteeing privacy protection in the distributed subgraph system can both be promising future directions.
Acknowledgments and Disclosure of Funding
This work is partially supported by the internal funding and GPU servers provided by the Computer Science Department of Emory University. We thank Dr. Pan Li from Purdue University for the suggestions on the design of our NeighGen mechanism.
10

---

References
[1] Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. JMLR, 3:463 482, 2002.
[2] Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks. JSTAT, 2008(10): 2008
[3] Liang Chen, Jintang Li, Qibiao Peng, Yang Liu, Zibin Zheng, and Carl Yang. Understanding structural vulnerability in graph convolutional networks. IJCAI, 2021.
[4] Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. ICML, 2018.
[5] CSIRO's Data61. Stellargraph machine learning library. wwarggraphsttellrrgee
https://githi: com/
2018.
[6] Qi Dou, Tiffany Y So, Meirui Jiang, Quande Liu, Varut Vardhanabhuti, Georgios Kaissis, Zeju Li, Weixin Si, Heather HC Lee, Kevin Yu, et al. Federated deep learning for detecting covid-19 19 lung abnormalities ct: a privacy-preserving multinational validation study, NPJ digital medicine, 4:1-11, 2021.
[7] Simon S. Du, Kangcheng Hou, Ruslan Salakhutdinov, Barnabás Póczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels, In NeurIPS, 2019.
[8] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized federated learning: A meta-learning approach. NeurlPS, 2020.
[9] Chelsea Finn, Picter Abbeel, and Sergey Levine. Modcl-agnostic meta-learning for fast adapta- tion of deep networks. In ICML, 2017.
[10] Ross Girshick. Fast r-cnn. In 2015.
[11] William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurlPS, 2017.
[12] Chaoyang He, Keshav Balasubramanian, Emir Ceyani, Carl Yang, Han Xie, Lichao Sun, Lifang He, Liangwei Yang, Philip S Yu, Yu Rong, Peilin Zhao, Junzhou Huang, Murali Annavaram, and Salman Avestimehr. Fedgraphnn: A federated learning system and benchmark for graph neural networks. arXiv preprint arXiv:2104.07145 2021.
[13] Chaoyang He, Shen Li, Mahdi Soltanolkotabi, and Salman Avestimehr. Pipetransformer. Automated elastic pipelining for distributed training of transformers. arXiv preprint arXiv:2102.03166 2021.
[14] Timothy M Hospedales, Antreas Antoniou, Paul Micaelli, and Amos J Storkey. Meta-learning in neural networks: A survey. TPAMI, 2021.
[15] Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In SIGKDD, 2020.
[16] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
[17] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Chal- lenges, methods, and future directions. IEEE SPM, 37:50-60, 2020.
[18] Xinle Liang, Yang Liu, Tianjian Chen, Ming Liu, and Qiang Yang. Federated transfer reinforce- ment learning for autonomous driving. arXiv preprint 19X.vv19/0.06000 2019.
[19] Quande Liu, Cheng Chen, Jing Qin, Qi Dou, and Pheng-Ann Heng. Feddg: Federated domain generalization on medical image segmentation via episodic learning in continuous frequency space. arXiv preprint arXiv:2103.060300 2021.

---

[20] Gongxu Luo. Jianxin Li, Hao Peng, Carl Yang, Lichao Sun, Philip Yu, and Lifang He. Graph entropy guided node embedding dimension selection for graph neural networks. In IJCAI, 2021.
[21] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. commuuiccation-fffciee learning of deep networks from decentralized data. In AISTATS, 2017.
[22] Galileo Namata, Ben London, Lise Getoor, and Bert Huang. Query-driven active surveying for collective classification. In MLG workshop, 2012.
[23] Alex Nichol, Joshua Achiam, and John Schulman. On first-order meta-leaming algorithms. arXiv preprint (atb:::803000000 2018
[24] Saif Ur Rehman, Asmat Ullah Khan, and Simon Fong. Graph mining: A survey of graph mining techniques. In ICDIM, 2012.
[25] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008.
[26] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojehevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint /8/
2018.
[27] Chuhan Wu, Fangzhao Wu, Yang Cao, Yongfeng Huang, and Xing Xie. Fedgnn: Federated graph neural network for privacy-preserving recommmnattooooonnonoo arXiv preprini arXiv:2102.04925, 2021.
[28] Man Wu, Shirui Pan, Chuan Zhou, Xiaojun Chang, and Xingquan Zhu. Unsupervised domain adaptive graph convolutional networks. In WWW, 2020.
[29] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. TNNLS, 2020.
[30] Han Xie, Jing Ma, Li Xiong, and Carl Yang. Federated graph classification over non-iid graphs. In NewrlPS, 2021.
[31] Carl Yang, Haonan Wang, Ke Zhang, Liang Chen, and Lichao Sun. Secure deep graph generation with link differential privacy. In IJCAI, 2021.
[32] Carl Yang, Yuxin Xiao, Yu Zhang, Yizhou Sun, and Jiawei Han. Heterogeneous network representation learning: A unified framework with survey and benchmark. TKDE, 2020.
[33] Carl Yang. Jieyu Zhang. and Jiawei Han. Co-embedding network nodes and hierarchical labels with taxonomy based generative adversarial nets. In ICDM, 2020.
[34] Carl Yang. Peiye Zhuang, Wenhan Shi, Alan Luu, and Pan Li. Conditional structure generation through graph variational generative adversarial nets. In NeurIPS, 2019.
[35] Qiang Yang. Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. TIST, 1092):1-19, 2019.
[36] Yizhou Zhang, Guojie Song, Lun Du, Shuwen Yang, and Yilun Jin. DANE: domain adaptive network embedding. In IJCAI, 2019.
[37] Dingyuan Zhu, Ziwei Zhang, Peng Cui, and Wenwu Zhu, Robust graph convolutional networks against adversarial attacks. In SIGKDD, 2019.
[38] Qi Zhu, Yidan Xu, Haonan Wang, Chao Zhang, Jiawei Han, and Carl Yang. Transfer learning of graph neural networks with ego-graph information maximization. In NeurIPS, 2021.
[39] Xinghua Zhu, Jianzong Wang, Zhenhou Hong, and Jing Xiao. Empirical studies of institutional federated learning for natural language processing. In EMNLP, 2020.
[40] Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In SIGKDD, 2018.
[41] Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. In ICLR, 2019.
[42] Daniel Zügner and Stephan Günnemann. Certifiable robustness and robust training for graph convolutional networks. In SIGKDD, 2019.
12


Reviews:
[{"review_id": "mIzomqdmmjJ", "reviewer": "Reviewer_sPrn", "summary": "This paper proposed a generalized node classification model over a distributed sub-graph system without data-sharing. The FedSage is a globally shared K-layer graph classifier model, trained with average gradients over distributed sub-graphs without data-sharing. The awareness of potentially existing links between sub-graphs motivate the authors to design a  missing neighbor model to help improve the performance of the node classifier model named FedSage+, which has been empirically shown to outperform the FedSage. \n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "NeighGen, consisting of fGen and dGen, is the model proposed to mend the impaired graph and predict the missing neighbors features. fGen is the linear model (parameter multiplying the feature of node i) to predict the missing neighbors of  node i. And dGen tries to predict the missings based on the output of fGen. As they are both simple supervised linear models  (one layer neural network), their effectiveness to  achieve the author’s primary goal - predicting the missing neighbors’ node features, can be questionable. I would expect the author to conduct simple intermediate experiments to show the power of NeighGen on predicting missing neighbors.\n\nSome notations are not defined before use in this section, although I could infer from context. For example, line 183 $\\tilde{x}_i$, the number of missing neighbors for node i, Similarly in the eq. (5), $\\tilde{n}_v$ is the estimated/predicted number of missing neighbors and $n_v$ is the ground truth number of missing neighbors for node v. Does the $x^q_v$ represent the raw node features for node v in eq(5)?\nI also want to know the details about how the dGen model outputs the integer number as it tries to approximate the true missing neighbors numbers.\n\nSince dGen is a supervised model, I would expect the author to present some statistical results to validate that this linear regression dGen model indeed achieves its goal - predicting the number of missing neighbors.\n\nFor section 4.3, I am a little confused about the definition of “without data sharing ”.  For example, in the appendix of FedSage + algorithm, on the data owner side, they all send the node features to the Server, will this behavior violate the rule of “no data sharing”. If this is the case, can a Server directly collect all the information from data owner and process , then distribute the results/trained model to all data owners. \n\nIn table 2, Cora dataset, the FedSage+ outperforms the GlobalSage, which collects all the information without any missing links. What do you think are possible reasons for this?\n \nMinor Problems and Typos:\nEq.4, the second $\\tilde{n}^i$ should be $\\tilde{n}_i$\nLine 118, to be rigorous, $i \\neq j$ can’t be neglected although that’s obvious from context.\n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10 hours"}, "extra_text": {}}, {"review_id": "ZefxV_As2Nf", "reviewer": "Reviewer_ehQP", "summary": "This paper proposes a federated learning framework for training federated GNNs under the scenario where each dataholder holds disjoint a disjoint subgraph. The paper introduces FedSAGE, which extends GraphSAGE to the federated setting, and FedSAGE+, which further enhances FedSAGE with a missing neighbor generator. The key insight of FedSAGE+ is that the links between subgraphs will be missing, and the neighbor generator is trained to generate missing neighbors. The authors demonstrate their framework using experiments on Cora, Citeseer, Pubmed and MSAcademic, where FedSAGE+ shows improvement over LocalSAGE without the missing neighbor generation. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**: \n- **Novel setting**. I think this paper considers a novel setting of training GNNs in a federated manner, i.e. each party holds a subgraph, and different subgraphs are disjoint, which motivates the problem of missing links. This should be a novel problem setting to consider the topic. \n- **Clarity**: This paper is in general well written and easy to follow. \n\n**Weaknesses**: \n- **Unclear how to deal with missing edges.** I appreciate the authors' setting of missing neighbors. However, throughout the paper, I can only see that the authors try to reconstruct the missing nodes $V_i^h$, but not the missing edges $E_i^h$ through optimization. Therefore, I am unclear about how the generated pseudo nodes $\\tilde{X}_i$ are connected to the remaining of the graph $\\hat{G}_i$. Therefore, I cannot clearly see how the missing neighbor generation is done and contributes to the overall model learning. \n- **Privacy Concerns**. In Eqn. 7, one term of the optimization objective involves $\\sum_{j\\in [M]\\backslash i}\\min_{v_q\\in V_j^h}\\|x_v^p-x^q\\|_2^2$. From my point of view, optimizing this requires the knowledge of $x^q$, which are features from other subgraphs. Does that leak privacy (node features)? From my point of view, it does. Please point out if I have any misunderstandings. \n- **Lack of appropriate model analysis**. Please justify the need to use separate NeighGen functions, as no ablation studies on it is done. Also, no ablation studies on parameters are done. I particularly want to see the ablation studies on $\\alpha$ in Eqn. 7, as this parameter is related to the use of information from other subgraphs. Also, I want to see the ablation studies on $h$ to see the potential limitations of this model. \n\n**Minor Comments**: \n- I was wondering how you manage to train GraphSAGE on Cora and Pubmed to >90\\%. From my experience, if you use the split given by DGL, in general, I can only achieve a little >80\\%. Please justify the need to use another split. \n- Figure 3b, I cannot see the point to show the global distribution of labels, as even if you have the same predicted label distribution, the performance may differ a lot. \n- The formulation in Eqn. 1 seems unnecessarily complex. I find it hard to understand, and the notations are not used afterwards. \n- Plesse consider using larger datasets, such as Reddit, OGB-products. As Cora, Citeseer, Pubmed are somehow small. \n\nTo summarize, due to the limitations in modeling edge information, and the possible leakage of private features, I cannot recommend acceptance at this time. \n\n===================UPDATE============================\n\nThe authors successfully address my confusions and concerns through the discussion. I am willing to raise the score from 4 to 6. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are stated. ", "review_text": "", "extra_scores": {"ethical_concerns": "No. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "8AFV-s-Ur2S", "reviewer": "Reviewer_VByp", "summary": "This paper investigates the problem of subgraph federated learning, with the goal of obtaining a generalized node classification model in a distributed subgraph system without data sharing. To handle this issue, the authors propose a novel framework named FedSage, with interweaving the GraphSage and FedAvg. Besides, a novel missing neighbor generator NeighGen is proposed to tackle the realistic yet unexplored issue of missing cross-subgraph links. Extensive experiments demonstrate the effective performance of FedSage.", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: Conceptually, this paper studies a novel and important setting of graph federated learning, where smaller subgraphs of a larger global graph are separately owned by different local data owners. The setting is well-motivated with an example of healthcare network distributed in individual hospitals (although no real experiments are done in this setting). Technically, this paper then focuses on an interesting and realistic challenge that the links across subgraphs are missing / not collected by any data owner. This challenge is indeed unique for federated learning on graph data with this subgraph setting, and the authors developed novel techniques to address it. Empirically, the authors conducted experiments on four real-world network datasets from the smaller commonly benchmarked ones and some larger ones. The results show consistent performance improvements of the proposed FedSage+ algorithm, but why the improvements are larger in some particular settings are not that clear.\n\nQuality: The techniques developed in this paper are novel and rich. The leverage of GraphSage with FedAvg is straightforward, and the joint training with the NeighGen model for missing link prediction is new. I also find the particular design of NeighGen pretty novel and interesting, which I have not seen in existing works on GNNs, while the joint prediction of numbers of missing links and virtual missing neighbors is reasonable. Section 4.3 is clear but required some reading to really understand, and the sharing of a NeighGen model is probably conceptually related to meta learning, which is not made clear by the authors. The experiments are comprehensive and mostly convincing, although more detailed analysis could be done with the efficiency (I doubt the algorithm with a shared NeighGen, although without many missing links to predict, can still encounter significant communication overhead, which makes Figure 4(c) not perfectly convincing).\n\nClarity: This paper is overall very well organized, although the detailed writings are occasionally hard to understand, maybe due to some unnecessarily lengthy sentences. Some typos can also be fixed through more careful proofreading.\n\nSignificance: This paper focuses on a realistic setting of subgraph federated learning, with identifying and addressing the unique challenge of missing cross-subgraph links. The novel NeighGen module provides a good remedy, and might be of broader interest to the GNN community beyond federated learning. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please see Main Review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies federated learning of graphs. It is assumed that the nodes of the graph are separated between the parties and cross-party edges are not observed. The authors suggest algorithms for learning in this scenario and experiment with them on several datasets.

The reviewers had some concerns about this work, but the authors have used the discussion to explain some ideas. This allowed the reviewers to reach a consensus that this work is above the acceptance threshold.



Decision: Accept (Spotlight)