{'fraction_non_alphanumeric': 0.03625483984512495, 'fraction_numerical': 0.008119206852047402, 'mean_word_length': 4.630334258158277, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Subgraph Federated Learning with Missing Neighbor Generation

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.


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 [29,11,16,20,32]. Similar to machine learning tasks in other domains, attaining a well-performed GNN model requires its training data to not only be sufficient but also follow 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 at training machine learning models with data distributed in multiple local systems to resolve the information-silo 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,13].
Motivating Scenario. Taking the healthcare system as an example, as shown in Fig. 1, residents of a city may go to different hospitals for various reasons. As a result, their healthcare data, such as 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 a pandemic occurs, Figure 1: A toy example of the distributed subgraph storage system: In this example, there are four hospitals and a medical administration center. The global graph records, for a certain period, the city'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 are not stored in any hospital. The right part of the figure indicates our goal that without sharing actual data, the system obtains a globally powerful graph mining model. a 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, it is rather difficult to let all hospitals share their patient networks with others to train the graph mining model due to conflicts of interests.
In such scenarios, it is desirable to train a 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.
Challenge 1: How to jointly learn from multiple local subgraphs? In our 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.
Solution 1: FedSage: Training GraphSage with FedAvg. To attain a powerful and generalizable graph mining model from small and biased subgraphs distributed in multiple local owners, we develop a 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 are 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 to 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 2: FedSage+: Generating missing neighbors along FedSage. To deal with crosssubgraph missing links, we add a missing neighbor generator on top of FedSage and propose a 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-subgraph missing neighbors and then applies 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.

Related works
Graph mining. Graph mining emerges its significance in analyzing the informative graph data, which range from social networks to gene interaction networks [31,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) [16] and GraphSage [11], improved the state-of-the-art in node classification with their elegant yet powerful designs. However, as GNNs leverage the homophily of nodes in both node features and link structures to 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 [3,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 a 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 in the distributed subgraph system. Federated learning. FL is proposed for cross-institutional collaborative learning without sharing raw data [17,35,21]. FedAvg [21] is an efficient and well-studied FL method. Similar to most FL methods, it 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,23,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 a generalizable model from diverse data owners to assist in solving a global task. In the distributed subgraph system, to obtain a 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 [12,27,30]. [12] 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, we 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.

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 a vanilla solution called FedSage.

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.
Problem setup. For the whole system, we assume V = V 1 ∪· · ·∪V M . To simulate the scenario with most missing links, we assume no overlapping nodes shared across data owners, namely V i ∩ V j = ∅ for ∀i, j ∈ [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 i cannot directly retrieve u ∈ V j from another data owner D j . Therefore, for an edge e v,u ∈ E, where v ∈ V i and u ∈ V j , e v,u / ∈ E i ∪ E j , that is, e v,u might exist in reality but is not stored anywhere in the whole system.
For the global graph G = {V, E, X}, every node v ∈ V has its features x v ∈ X and one label y v ∈ Y for the downstream task, e.g., node classification. Note that for v ∈ V , v's feature x v ∈ R dx and respective label y v is a d y -dimensional one-hot vector. In a typical GNN, predicting a 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 v as G(v), and (G(v), y v ) ∼ D G .
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, to obtain a 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 φ * that minimizes the aggregated risk where R i is the local empirical risk defined as where is a task-specific loss function

Collaborative Learning on Isolated Subgraphs
To fulfill the system's goal illustrated above, we leverage the simple and efficient FedAvg framework [21] and fix the node classifier F as a 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 a queried node v ∈ V , a globally shared K-layer GraphSage classifier F integrates v and its K-hop neighborhood on graph G to conduct prediction with learnable parameters φ = {φ k } K k=1 . Taking a subgraph G i as an example, for v ∈ V i with features as h 0 where N Gi (v) is the set of v's neighbors on graph G i , || is the concatenation operation, Agg(·) is the aggregator (e.g., mean pooling) and σ is the activation function (e.g., ReLU).
With F outputting the inference label where CE(·) is the cross entropy function, G i (v) is v's K-hop ego-graph on G i , which contains the information of v and its K-hop neighbors on G i .
In FedSage, the distributed subgraph system obtains a shared global node classifier F parameterized by φ through e c epochs of training. During each epoch t, where V t i ⊆ V i contains the sampled training nodes for epoch t, and η is the learning rate; then the central server S collects the latest {φ i |i ∈ [M ]}; next, through averaging over {φ i |i ∈ [M ]}, S sets φ as the averaged value; finally, S broadcasts φ to data owners and finishes one round of training F . After e c epochs, the entire system retrieves F as the outcome global classifier, which is not limited to or biased towards the queries in any specific data owner.
Unlike FL on Euclidean data, nodes in 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 in 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 F from achieving the desideratum of capturing the global query distribution. Figure 2: Joint training of missing neighbor generation and node classification.

FedSage+
In this section, we propose a novel framework of FedSage+, i.e., subgraph FL with missing neighbor generation. We first design a 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, we take NeighGen i , i.e., the missing neighbor generator of D i , as an example, where i ∈ [M ].

Missing Neighbor Generator (NeighGen)
Neural architecture of NeighGen. As shown in Fig. 2, NeighGen consists of two modules, i.e., an encoder H e and a generator H g . We describe their designs in details in the following.
and fGen is a feature generator parameterized by θ f that generates a set of N i feature vectors Both dGen and fGen are constructed as fully connected neural networks (FNNs), while fGen is further equipped with a Gaussian noise generator N(0, 1) that generates d z -dimensional noise vectors and a random sampler R. For node v ∈ V i , fGen is variational, which generates the missing neighbors' features for v after inserting noises into the embedding z v , while R ensures fGen to output the features of a specific number of neighbors by sampling n v feature vectors from the feature generator's output. Mathematically, we have Graph mending simulation. For each data owner in our system, we assume that only a particular set of nodes have cross-subgraph 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 a graph impairing and mending process. Specifically, to simulate a graph mending process during the training of NeighGen, in each local subgraph G i , we randomly hold out h% of its nodes Accordingly, based on the ground-truth missing nodes V h i and links E h i , the training of NeighGen on the impaired graphḠ i boils down to jointly training dGen and fGen as below.
where L S 1 is the smooth L1 distance [10] and Neighbor Generation. To retrieve G i from G i , data owner D i performs two steps, which are also shown in Fig. 2: 1) D i trains NeighGen on the impaired graphḠ i w.r.t. the ground-true hidden neighbors V h i ; 2) D i exploits NeighGen to generate missing neighbors for nodes on G i and then mends G i into G i with generated neighbors. On the local graph G i alone, this process can be understood as a data augmentation that further generates potential missing neighbors within G i . 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.

Local Joint Training of GraphSage and NeighGen
While NeighGen is designed to recover missing neighbors, the final goal of our system is to train a node classifier. Therefore, we design the joint training of GraphSage and NeighGen, which leverages neighbors generated by NeighGen to assist the node classification by GraphSage. We term the integration of GraphSage and NeighGen on the local graphs as LocSage+.
After NeighGen mends the graph G i into G i , the GraphSage classifier F is applied on G i , according to Eq. (1) (with G i replaced by G i ). Thus, the joint training of NeighGen and GraphSage is done by optimizing the following loss function where L d and L f are defined in Eq. (4), and L c is defined in Eq.
(2) (with G i substituted by G i ).
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.

Federated Learning of GraphSage and NeighGen
Similarly to GraphSage alone, as described in Section 3.2, we can apply FedAvg to the joint training of GraphSage and NeighGen, by setting the loss function to L and learnable parameters to {θ e , θ d , θ f , φ}. 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 it to generate diverse neighbors from different subgraphs. Recalling our goal of constructing NeighGen, which is to facilitate the training of a centralized GraphSage classifier by generating diverse missing neighbors in each subgraph, we do not necessarily need a centralized NeighGen. Therefore, instead of training a single centralized NeighGen, we train a local NeighGen i for each data owner D i . In order to allow each NeighGen i to generate diverse neighbors similar to those missed into other subgraphs G j , j ∈ [M ] \ {i}, we add a cross-subgraph feature reconstruction loss into fGen i as follows: where u ∈ V j , ∀j ∈ [M ] \ {i} is picked as the closest node from G j other than G i to simulate the neighbor of v ∈V i missed into G j .
As shown above, to optimize Eq. (6), D i needs to pick the closest u from G j . However, directly transmitting node features X j in D j to D i not only violates our subgraph FL system constraints on no direct data sharing but also is impractical in reality, as it requires each D i to hold the entire global graph's node features throughout training NeighGen i . Therefore, to allow D i to update NeighGen i using Eq. (6) without direct access to X j , for v ∈V i , D j locally computes and sends the respective gradient back to D i .
During this process, for v ∈V i , to federated optimize Eq. (6), only H g i , H g i 's input z v , and the D j 's locally computed model gradients of loss term p∈[ nv] min u∈Vj (||H g i (z v ) p − x u || 2 2 ) are transmitted among the system via the server S. For data owner D i , the gradients received from D j are then weighted by α and combined with the local gradients as in Eq. (6) to update the parameters of H g i of NeighGen i In this way, D i achieves the federate training of NeighGen i without raw graph data sharing. Note that, due to NeighGen's architecture of a concatenation of H e and H g , the locally preserved GNN H e i can prevent other data owners from inferring x v by only seeing z v . Through Eq. (6), NeighGen i is expected to perceive diverse neighborhood 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 a 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 A shows the pseudo code of FedSage+.

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.

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 3, 5, and 10 clusters of similar sizes to obtain subgraphs for data owners. The statistics of these datasets are presented in Table 1. 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-validation-testing ratio is 60%-20%-20% due to limited sizes of local subgraphs. Based on our observations in hyper-parameter studies for α and the graph impairing ratio h, we set h% ∈ [3.4%, 27.8%] and α=1. All λs are simply set to 1. Optimization is 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., 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 LocSage+, the scores are further averaged across local models.

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  shown in Table 2. The most important observation emerging from the results is that FedSage+ not only clearly outperforms LocSage by an average of 23.18%, but also distinctly overcomes the cross-subgraph missing neighbor problem by reducing the average accuracy drop from the 2.11% of FedSage to 1.28%, when compared with GlobSage (absolute accuracy difference).
The significant gaps between a 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 cross-subgraph links and the effectiveness of our innovatively designed NeighGen module. Notably, when the graph is relatively sparse (e.g., see Citeseer in Table 1), FedSage+ significantly exhibits its robustness in 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.  Hyper-parameter studies. We compare the downstream task performance under different α and h values with three data owners. Results are shown in Fig. 3, where Fig. 3 (a) shows results when h is fixed as 15%, and Fig. 3 (b) shows results under α=1. Fig. 3 (a) indicates that choosing a proper α, which brings the information from other subgraphs in the system, can constantly elevate the final testing accuracy. Across different datasets, the optimal α is constantly around 1, and the performance is not influenced much unless α is set to extreme values like 0.1 or 10. Referring to Fig. 3 (b), we can observe that either a too-small (1%) or a too-large (30%) hiding portion can degrade the learning process. A too-small h can not provide sufficient data for training NeighGen, while a too-large h can result in sparse local subgraphs that harm the effective training of GraphSage. Referring back to the graph statistics in Table 1 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, as shown in Fig. 4 (a). Such bias is due to the way we synthesize the distributed subgraph system with Louvain clustering, which is also realistic in real scenarios. Local bias essentially makes it hard for any local data owner with limited training samples to obtain a generalized classifier that is 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-true global label distribution as shown in Fig. 4 (b). The figure clearly evidences that our FL models exhibit their advantages in learning a more realistic label distribution as our goal in Section 3.1, which is consistent with the observed performances in Table 2 and our theoretical implications in Section 6.
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 LocSage+. The results are presented in Fig. 5. Both FedSage and FedSage+ can consistently achieve convergence with rapidly improved testing 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 more nodes in the global graph through collaborative training with FL.
Setting. Our explanation builds on a generalized setting, where we assume a GNN F with layerwise aggregation operations and fully-connected layers with ReLU activation functions, which includes GraphSage as a special case. The weights of F , φ, is i.i.d. sampled from a multivariate Gaussian distribution N(0, I). For Graph G = {V, E, X}, we define the kernel matrix of two nodes u, v ∈ 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 Θ ∈ R n×n as the the kernel matrix of GNTK. Θ uv is defined as Full expression of Θ is shown in the Appendix B. The generalization ability in the GNTK regime depends on the kernel matrix Θ. We present the generalization bound associated with the number of training samples n in Theorem 6.2. Following the generalization bound analysis in [7], we use a standard generalization bound of kernel methods of [1], which shows the upper bound of our GNTK formation error depends on that of y Θ (−1) y 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 our goal of building a globally useful classifier through FL in Eq. (3.1). Such implications are 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.

Conclusion
This work aims at obtaining a 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 a 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.

A FedSage+ Algorithm
Referring to Section 4.3, FedSage+ includes two phases. Firstly, all data owners in the distributed subgraph system jointly train NeighGen models through sharing gradients. Next, after every local graph mended with synthetic neighbors generated by the respective NeighGen model, the system executes FedSage to obtain the generalized node classification model. Algorithm 1 shows the pseudo code for FedSage+. Collect 10: for D i ∈ {D 1 , . . . , D M } in parallel do 12: for D i ∈ {D 1 , . . . , D M } in parallel do 14: Aggregate gradients as FedSage for mended subgraphs on epoch t

17:
Collect φ i ← LOCALUPDATEC(D i , φ, t) from all data owners 18: Broadcast φ ← 1  Train NeighGen i by optimizing Eq. (6). 30: Send φ i to Sever B Full Version of Definition 6.1 Notation. We denote the whole graph G = {V, E, X} and |V | = n. To perform node classification on G, we consider a GNN F with K aggregation operations 2 and each aggregation operation contains R fully-connected layers. We describe the aggregation operation below.
Definition B.1 (Aggregation operation, (AGG)) For ∀k ∈ [K], AGG aggregates the information from the previous layer and performs R times non-linear transformation. With denoting the initial feature vector for node u ∈ V as h (0,R) u = x u ∈ R d , for an AGG with R = 2 fully-connected layers, the AGG can be written as: where c σ ∈ R is a scaling factor related initialization, c u ∈ R is a scaling factor associated with neighbor aggregation, σ(·) is ReLU activation, and learnable parameter φ k,r ∈ R m×m for ∀(k, r) ∈ [K] × [R]\{(1, 1)} as φ 1,1 ∈ R k×d .
For notation simplicity, GNN F here is considered in GNTK format. The weights of F , φ is i.i.d. sampled from a multivariate Gaussian distribution N (0, I). For node u ∈ V , we denote u's computational graph as G u = {V u , E u , X u } and |V u | = n u . Let a, b denote inner-product of vector a and b. We are going to define the kernel matrix of two nodes u, v ∈ V as follows.
Definition B.2 (GNTK for node classification) Considering in the overparameterized regime for an GNN F , F is trained using gradient descent with infinite small learning rate. Given n training samples of nodes with corresponding labels, we denote Θ ∈ R n×n as the the kernel matrix of GNTK. For ∀u, v ∈ V , Θ uv is the u, v entry of Θ and defined as In GNTK formulation, an AGG B.1 needs to calculate 1) a covariance matrix Σ(G u , G v ); and 2) the intermediate kernel values Θ(G u , G v ) Now, we specify the pairwise value in Σ(G u , G v ) ∈ R nu×nv and Θ(G u , G v ) ∈ R nu×nv . For ∀k ∈ [K] and ∀r ∈ [R], Σ indicate the corresponding covariance and intermediate kernel matrix for rth transformation and kth layers.
are the input features of node u and v. Denote the scaling factor for node u as c u . Θ (l) (R) (G u , G v ) can be calculated recursively through the aggregation operation given in [7]. Specifically, we have the following two steps.
Step 1: Neighborhood Aggregation As the AGG we defined above, in GNTK, the aggregation step can be performed as: Step 2: R transformations Now, we consider the R ReLU fully-connected layers which perform non-linear transformations to the aggregated feature generated in step 1. The ReLU activation function σ(x) = max{0, x}'s derivative is denoted asσ(x) For r ∈ [R], u, v ∈ V , we define covariance matrix and its derivative as Thus, we have can be viewed as kernel matrix of GNTK for node classification. The generalization ability in the NTK regime and depends on the kernel matrix.

C Missing Proofs for Theorem 6.2
In this section, we provide the detailed version and proof of Theorem 6.2. To prove the generalization bound, we make the following assumptions about the labels.
Assumption C.2 For each i ∈ [n], the labels y i = [y] i ∈ R satisfies The following Lemma C.3 and C.4 give the bounds for y Θ (−1) y and tr(Θ).
Lemma C.3 (Bound on y Θ (−1) y) Under the Assumption C.2, we have Proof. Without loss of generality, we consider a simple GNN (K = 1, R = 1) in Section B and define the kernel matrix for on the computational graph G u , G v node u, v ∈ V as Following the proof in [7] and assuming h u 2 = 1, we have 2π . Then, We denote Φ 2k as the feature map of the kernel at degree 2k . Following the proof in [7], we have As Θ is a positive semidefinite matrix, we have y Θ (−1) y ≤ y Θ (−1) y.
We define y Under Assumption C.2, label y i can be rewritten as

Then we have
When k = 0, we have When k ≥ 1, we have The bound of tr(Θ) is simpler to prove.
Proof. We have Θ ∈ R n×n . For each u, v ∈ V , as Lemma C.3 shown that Combine Combining Theorem C.1, Lemma C.3 and Lemma C.4, it is easy to see for a constant c ∈ (0, 1) :

D Detailed ablation studies of NeighGen
In this section, we provide in-depth NeighGen studies to empirically explain its power in the cross-subgraph missing neighbor generation. Specifically, we first show the intermediate results of NeighGen by boiling down the generation process into the missing cross-subgraph link generation by dGen and the missing cross-subgraph neighbor feature generation by fGen. Next, we experimentally verify the necessity of training locally specialized NeighGen. Finally, we provide FL training hyper-parameter study on batch size and local epoch to emphasize the robustness of FedSage+.

D.1 Intermediate results of dGen and fGen.
In this section, we study the two generative components in NeighGen, i.e., dGen and fGen, to explore their expressiveness in reconstructing missing neighbors. Especially, we analyze the outputs from dGen and fGen separately to explain how NeighGen assists in the missing cross subgraph neighbor generation process.
As described in Section 4, both dGen and fGen are constructed as fully connected neural networks (FNNs) whose depths can be varied according to the target dataset. In principle, due to the expressiveness of FNNs [29], dGen and fGen with even very few layers have the power to approximate complex functions. The node degree and feature distributions, on the other hand, are often highly relevant to the graph structure and less complex in nature. In Fig. 6 and Table 3, we provide intermediate results on how dGen and fGen are able to recover missing neighbor numbers and features, respectively.
Additional details for dGen. Fig. 6 shows the break-down performance of dGen on the MSAcademic dataset with M=3, which clearly shows the effectiveness of dGen in recovering the true number of missing neighbors. Notably, though the original output of dGen is a float number, we simply apply the round function to retrieve the integer number of missing neighbors for reconstruction.
Additional details for fGen. As described in Section 4.1, based on the number of missing neighbors generated by dGen, fGen further generates the feature of missing neighbors, thus recovering the incomplete neighborhoods resulting from the subgraph federated learning scenario. Regarding to our ultimate mission in missing neighbor generation as described in Section 4, i.e., locally modeling the original global graph during graph convolution, we evaluate fGen by comparing the NeighGen generated neihgbors with the neihgbors drawn from original whole graph and the ones from original subgraph. Specifically, we present the L 2 distance between the averaged feature distributions of neighborhoods from these three types of graphs to show how the NeighGen generated missing neighbors narrow the gap. For simplicity, we use N (v), N i (v), and N i (v) to represent the first-order neighbors of nodes v ∈ V drawn from the global graph G, the original subgraph G i , and the mended subgraph G i respectively. Smaller values indicate the locally drawn neighbors (N i (v) or N i (v)) being more similar to the true neighbors from the global graph (N (v)). The results in Table 3 clearly show the effectiveness of fGen in recovering the true features of missing neighbors.

D.2 Usage of local specialized NeighGens
To empirically explain why we need separate NeighGen functions, we contrast the downstream task performances between FedSage with a globally shared NeighGen, i.e., FedSage with NeighGen obtained with FedAvg, and FedSage with FL obtained local specialized NeighGens, i.e., FedSage+. We conduct ablation experiments on four datasets with M =3, and the results are in Table 4. The results clearly assert our explanation in Section 4.3, i.e., directly averaging NeighGen weights across the system degenerates the downstream task performance, which indicates the insufficiency of FedAvg in assisting local data owners in the diverse neighbor generation.  Table 5 and 6. Every result is presented as Mean (± Std Deviation).   Table 5 and 6 both evidence the reliable, repeatable therapeutic effects that FedSage+ consistently further elevates FedSage in the global node classification task. Notably, in Table 5, when batch sizes are as small as 16 and 1, FedSage+ accomplishes even higher classification results compared to the centralized model GlobSage due to the employment of NeighGen. Table 5 reveals the graph learning model can be affected by different batch sizes. As GlobSage is trained on a whole global graph, rather than a set of subgraphs, compared to FedSage and FedSage+, it suits a larger batch size, i.e., 64, than 1 or 16. Both FedSage and FedSage+, where every data owner samples on a limited subgraph, fit better in batch sizes 16. Remarkably, when the batch size equals 1, FedSage is prone to overfit to local biased distribution, while FedSage+ resists the overfitting problem under the NeighGen's assistance, i.e., generating cross-subgraph missing neighbors. Table 6 provides the relation between the local epoch number and the downstream task performance. For FedSage, more local epochs degenerate the outcome model with more biased aggregated local weights, while FedSage+ maintains a relatively more stable performance in the downstream task. Table 6 empirically evidences that the missing neighbor generator in FedSage+ provides further generalization and robustness in resisting rapid accuracy loss brought by higher local epochs.
Similar to results in Table 2, Section 5, FedSage and FedSage+ exhibit competitive performance even compared to the centralized model. Findings in Table 5 and 6 further contribute to a better understanding of the robustness in FedSage+ compared to vanilla FedSage.