{'fraction_non_alphanumeric': 0.02863739288727079, 'fraction_numerical': 0.013497313856946233, 'mean_word_length': 4.953872587893207, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Personalized Subgraph Federated Learning

In real-world scenarios, subgraphs of a larger global graph may be distributed across multiple devices or institutions, and only locally accessible due to privacy restrictions, although there may be links between them. Recently proposed subgraph Federated Learning (FL) methods deal with those missing links across private local subgraphs while distributively training Graph Neural Networks (GNNs) on them. However, they have overlooked the inevitable heterogeneity among subgraphs, caused by subgraphs comprising different parts of a global graph. For example, a subgraph may belong to one of the communities within the larger global graph. A naive subgraph FL in such a case will collapse incompatible knowledge from local GNN models trained on heterogeneous graph distributions. To overcome such a limitation, we introduce a new subgraph FL problem, personalized subgraph FL, which focuses on the joint improvement of the interrelated local GNN models rather than learning a single global GNN model, and propose a novel framework, FEDerated Personalized sUBgraph learning (FED-PUB), to tackle it. A crucial challenge in personalized subgraph FL is that the server does not know which subgraph each client has. FED-PUB thus utilizes functional embeddings of the local GNNs using random graphs as inputs to compute similarities between them, and use them to perform weighted averaging for server-side aggregation. Further, it learns a personalized sparse mask at each client to select and update only the subgraph-relevant subset of the aggregated parameters. We validate FED-PUB for its subgraph FL performance on six datasets, considering both non-overlapping and overlapping subgraphs, on which ours largely outperforms relevant baselines.


Introduction
A graph, which defines the relationships among instances, can model a wide range of structured data including social [7], co-purchasing [24], and collaboration networks [36]. Most of the previous works on graph representation learning focus on a single graph, whose nodes and edges collected from multiple sources are stored in a central server. For instance, in a social network platform, every user, with his/her social networks, contributes to creating a giant network consisting of all users and their connections. However, in some practical scenarios, each user/institution collects its own private graph, which is only locally accessible due to privacy restrictions. For instance, as described in Zhang et al. [46], each hospital may have its own patient interaction network to track their physical contacts or co-diagnosis of a disease, however, such a graph may not be shared with others. An obvious challenge for such a scenario is how to deal with potentially missing edges between subgraphs [42,43,46] that are not captured by individual data owners, that may carry important information (See Figure 1 (A)).
How can we then collaboratively train, without sharing actual data, a neural network with its subgraphs distributed across multiple participants (i.e., clients) over different devices or institutions? The most straightforward way is to perform Federated Learning (FL) with Graph Neural Networks (GNNs). In Figure 1: (A) An illustration of local subgraphs distributed across multiple participants with overlapping nodes, missing edges and community structures between subgraphs. (B) Existing subgraph FL [42,43,46] expands the local subgraphs to tackle the missing edge problem, but collapse incompatible knowledge from heterogeneous subgraphs. (C) Our personalized subgraph FL focuses on joint improvement of local models working on interrelated subgraphs, such as ones within the same community, by selectively sharing knowledge across them. (Right:) Results on knowledge collapse, where local models belonging to two small communities (Comm 1 and 2) suffer from large performance degeneration by existing subgraph FL (e.g., FedGNN [42,43] and FedSage [46]). A personalized FL method, FedPer [2] also underperforms ours since it only focuses on individual model's improvement without sharing local personalization layers between similar subgraphs. particular, in such an FL framework, each client will individually train a local GNN on the private local data, while a central server aggregates the locally updated GNN weights from multiple clients into one, and then transmits it back to the clients. Recent subgraph FL methods work in such a manner [42,43,46] while additionally tackling the problem of missing edges between subgraphs. This is done as illustrated in Figure 1 (B), where the local subgraph is expanded either by exactly augmenting the relevant nodes from the other subgraphs at the other clients [42,43], or by estimating the nodes using the node information in the other subgraphs [46]. However, such sharing of node information may compromise data privacy and can incur high communication costs.
Also, there exists an even more serious issue that has been overlooked by the existing subgraph FL methods. We observe that they suffer from large performance degeneration (See Figure 1 right), due to a lack of consideration of the heterogeneity among the subgraphs, which is natural since subgraphs comprise different parts of a global graph. Notably, there could be multiple communities within a global graph, each of which is formed by a group of densely connected subgraphs with similar characteristics (Figure 1 (A)). For example, some of patient networks from hospitals can be grouped by their specialized sectors according to the disease categories, namely psychiatric or ophthalmology.
Motivated by this challenge, we introduce a novel problem of personalized subgraph FL, whose goal is the joint improvement of interrelated local models trained on the interconnected local subgraphs, for instance, subgraphs belonging to the same community (See Figure 1 (C)), by sharing weights among them. However, tackling personalized subgraph FL is challenging, since we do not know which subgraph each client has, due to their local accessibility. To resolve this issue, we use functional embeddings of GNNs on random graphs to obtain similarity scores between two local GNNs, and then use them to perform weighted averaging of the model weights at the server. However, the similarity scores only tell how relevant each local model from the other clients is, but not which of the parameters are relevant. Thus we further learn and apply personalized sparse masks on the local GNN at each client to obtain only the subnetwork, relevant for the local subgraph. We refer to this subgraph FL framework as FEDerated Personalized sUBgraph learning (FED-PUB).
We extensively validate our FED-PUB on six different datasets with varying numbers of clients, under both overlapping and disjoint subgraph FL scenarios. The experimental results show that ours significantly outperforms relevant baselines. Further analysis shows that our method can discover community structures among subgraphs, and the subgraph-specific masking localizes the knowledge with respect to subgraphs belonging to each community. Our main contributions are as follows: • We introduce a novel problem of personalized subgraph FL, which aims at collaborative improvements of the related local models (e.g. subgraphs belonging to the same community), which has been relatively overlooked by previous works on graph and subgraph FL. • We propose a novel framework for personalized subgraph FL, which performs weighted averaging of the local model parameters based on their functional similarities obtained without accessing the data, and learns sparse masks to select only the relevant subnetworks for the given subgraphs. • We validate our personalized subgraph FL framework on six real-world datasets under two different settings, demonstrating its effectiveness over existing subgraph FL baselines.

Related Work
Graph Neural Networks Graph representation learning with Graph Neural Networks (GNNs) [11,49,44,19,3], which aims to learn the representations of the nodes, the edges, and the entire graph, is an extensively studied topic. Most existing GNNs are formulated under the message passing scheme [9] that iteratively represents a node by aggregating features from its neighboring nodes as well as itself. For example, Graph Convolutional Network (GCN) [23] approximates the spectral graph convolutions [13], yielding a mean aggregation over neighboring nodes. Similarly, for each node, GraphSAGE [12] aggregates the features from its neighbors to update the node representation. Graph Attention Network (GAT) [40] leverages the attention mechanism [4] to allocate more weights on the most relevant neighbors during aggregation. Such advances in GNNs have led to large successes on node and link prediction tasks [23,48]. However, they are not directly applicable to the real-world systems with locally distributed graphs, where graphs from different sources are not shared across participants, which gives rise to federated learning approaches to train GNNs.
Federated Learning Federated Learning (FL) [31,26,41,20,25], whose objective is to learn a model by aggregating model weights trained on local data, is an essential approach for our distributed subgraph learning problem. To mention a few, FedAvg [31] locally trains a model for each client and then transmits the trained model to a server, while the server aggregates the model weights from local clients and then sends the aggregated model back to them. However, since the locally collected data from different clients may largely vary, heterogeneity is a crucial issue. To tackle this, FedProx [26] proposes the regularization term that minimizes the weight differences between local and global models, which prevents the model from diverging by overfitting to the local training data. However, when the local data is extremely heterogeneous, it is more appropriate to collaboratively train a personalized model for each client rather than learning a single global model [2,29,27,47,6]. FedPer [2] is such a personalized FL method, which shares only the base layers while having local personalized layers for each client, to keep the local knowledge. Unlike the commonly studied image and text data, graph-structured data is defined by connections between instances, and consequently introduces additional challenges: missing edges and shared nodes between private subgraphs.
Graph Federated Learning Few recent studies propose to use the FL framework to collaboratively train GNNs without sharing graph data [14], which can be broadly classified into subgraph-and graph-level methods. Graph-level FL methods assume that different clients have completely disjoint graphs (e.g., molecular graphs), and recent works [45,15] focus on the heterogeneity among non-IID graphs (i.e., difference in graph labels across various clients). In contrast to graph-level FL methods that have similar challenges to general FL scenarios, the subgraph-level FL problem we target has a unique graph-structural challenge, that there exist missing yet probable links between subgraphs, since a subgraph is a part of a larger global graph. To deal with such a missing link problem among subgraphs, existing methods [42,43,46] augment the nodes by requesting the node information in the other subgraphs, and then connecting the existing nodes with the augmented ones. However, this scheme could compromise data privacy constraints, and also increases communication overhead across clients. Unlike existing subgraph FL that focuses on the problem of missing links, our subgraph FL method tackles the problem with a completely different perspective, focusing on discovering subgraph communities [35,10,34], which are groups of densely connected subgraphs.

Personalized Subgraph Federated Learning
We provide the general descriptions of Graph Neural Networks (GNNs) and Federated Learning (FL), and then define our novel problem of personalized subgraph FL lying at the intersection of them.
Graph Neural Networks A graph G = (V, E) consists of a set of nodes V with n elements and a set of edges E with m elements along with its node feature matrix X ∈ R n×d , where each column represents a d-dimensional feature for each node. Further, (u, v) ∈ E represents an edge from a node u to a node v. Then, given the graph, Graph Neural Networks (GNNs) [9,11] generally represent each node based on features from its neighbors as well as itself, formally defined as follows: where H (l) v is the feature matrix for node v at l-th layer, N (v) denotes a set of adjacent nodes of node v: N (v) = {u ∈ V | (u, v) ∈ E}, AGGREGATE aggregates the features of v's neighbors, and UPDATE updates the node v's representation given its previous representation and the aggregated representations from the neighbors. H (1) is initialized as input node features X.

Federated Learning
The objective of Federated Learning (FL) is to collaboratively train a model with local private data. Let assume that we have K participants with locally collected data that is not accessible from others: where X i is a data instance, y i is its corresponding class label, and N k is the number of data instances at k-th client. Then, for decentralized training with local data, a popular FL algorithm, FedAvg [31], works as the following three steps: 1. (Initialization) At the initial communication round r = 0, the central server first selects K clients that are available for training, and initializes their local model parameters as the global parameter θ, represented as follows: θ k is the parameters for k-th client. 2. (Local Updates) Each active local model performs training on private local data D k to minimize the task loss L(D k ; θ (0) k ), consequently updating the parameters θ (Global Aggregation) After local training, the server aggregates the locally learned knowledge with respect to the number of training instances, i.e.,θ (1) k with N = k N k , and distributes the updated global parametersθ (1) to the local clients selected at the next round.
This FL algorithm iterates between Step 2 and 3 until reaching the final round R.
Challenges in Subgraph FL While the above FL works well on image and text data, due to the unique structure of graphs, there exist nontrivial challenges for applying this FL scheme to graphstructured data. In particular, unlike with an image domain where each instance X i is independent from the other images, each node v in a graph is always influenced by its relationships to adjacent nodes N (v). Moreover, a local graph G i could be a subgraph of a larger global graph G: G i ⊆ G. In such a case, there could be missing edges between local subgraphs in two different clients: (u, v) with u ∈ V i and v ∈ V j for clients i and j, respectively. To tackle this missing edge problem, few existing subgraph FL methods [42,46] estimate the nodes from a local subgraph G k based on the node information from the subgraphs at other clients G i ∀i = k, and then extend the existing nodes with the estimated ones. However, this augmentation scheme incurs high communication costs as it requires sharing node information across clients, which may also violate data privacy constraints [1].
Yet, there exists another issue that makes subgraph FL even more challenging. Assume that we have a global graph consisting of all the subgraphs. Then, there exists communities of such subgraphs [35,10,34], where subgraphs within the same community are more densely connected to each other than subgraphs outside the community. Formally, a global graph G can be decomposed into T different communities: C i ⊆ G ∀i = 1, ..., T , where i-th community C i = (V i , E i ) consists of densely connected nodes. Then, in a subgraph FL problem, each client has a local subgraph G j that belongs to at least a single community 2 : C i = J j=1 G j . Note that, based on the theory of network homophily [32], such connected subgraphs within the same community have similar properties, while subgraphs in two opposite communities are not. Such distributional heterogeneity across communities may lead a naive FL algorithm to collapse incompatible knowledge across different communities.
Personalized Subgraph FL To prevent the above knowledge collapse issue, we aim to personalize the subgraph FL algorithm by performing weighted averaging of the local model parameters at the server, rather than learning a single set of global parameters; thereby capturing the subgraph community structures among interrelated subgraphs. Formally, the objective of existing subgraph FL [42,43,46,28] is as follows: min Gi⊆G L(G i ; θ). However, a major drawback of such a scheme is that, since subgraphs in two different communities with sparse connections are extremely heterogeneous due to network homophily [32], finding a universal set of parameters (i.e., θ) that work on all tasks will result in finding a suboptimal parameter set. To address such limitations of existing subgraph FL, we formulate a novel problem of personalized subgraph FL, formalized as follows: where θ i is the weight for subgraph G i belonging to community C, and α ij is the coefficient for weight aggregation which we will specify in Section 4.1. This formulation promotes the collaborative learning across multiple local models that work on the interrelated subgraphs that belong to the same community, by assigning larger weights on them. we forward randomly generated graphs to models f (Ḡ; θ), and then obtain the functional embeddings of them h, which are then used to estimate the similarities between subgraphs. The similarities are used in the weight aggregation, resulting in the personalized model weightsθ. (C) Weight Masking: the transmitted weights from the server to clientsθ are masked and shifted by local masks for localization to the local subgraph distribution.

Federated Personalized Subgraph Learning (FED-PUB) Framework
Our goal of personalized subgraph FL is to jointly improve the local models trained on the interconnected local subgraphs forming the community structures. To this end, we propose to compute subgraph similarity scores for detecting communities, and to mask subgraph-irrelevant weights.

Subgraph Similarity Estimation for Detecting Subgraph Community
We aim to reflect the community structure consisting of a group of densely connected subgraphs, by sharing more weights among subgraphs in the same community, as formalized in equation 2. Due to network homophily where similar instances in the graph are more associated with each other [32], the subgraphs within the same community should have similar properties. Therefore, if one can measure the subgraph similarities, we can group the similar ones into the community. However, measuring the similarity between local subgraphs is a seemingly impossible goal since we do not know which subgraph each client has due to local accessibility. How can we then compute subgraph similarities, without accessing them? To this end, we aim to approximate the subgraph similarity at local clients using auxiliary information obtained from the local GNN models that work on the subgraphs.

Subgraph Similarity Estimation with Model Parameters
For measuring the similarity between subgraphs at each client, without accessing them, we may use the model parameters as proxies, as follows: where θ is a flattened parameter into the vector, and S is a similarity measure. This may sound reasonable since the GNN model trained on the subgraph will embed its knowledge into its parameters. However, this scheme has a crucial drawback that similarity measured in the high-dimensional parameter space is not meaningful due to the curse of dimensionality [5], and that the cost of calculating the similarity between parameters grows rapidly as the model size increases (See Figure 3).

Subgraph Similarity Estimation with Functional Embedding
To tackle the limitations of using parameter distance, we propose to measure the functional similarity of neural networks by feeding the same input to every local client and then calculating the similarities using their outputs, inspired by a work for neural network search [18]. The main intuition is that we can consider the transformation defined with a neural network as a function, and we measure the functional similarity of two networks by the distance of their outputs for the same input. However, unlike the previous work [18] that tackles image classification, which uses Gaussian noises as inputs, we use random graphs as inputs as we work with GNNs. Formally, letG = (Ṽ,Ẽ) be a random community graph obtained from a stochastic block model [16], where subgraphs within the community have more edges between them than edges across the communities. Further,Ṽ is randomly initialized from the normal distribution. Then, the similarity between two functions defined by GNNs at clients i and j is defined as follows: whereh is the averaged output of all node embeddings for inputG with AVG operation to reduce the dimensionality of the output from n × d to d, for n nodes with d-dimensional node features.
Personalized Weight Aggregation based on Subgraph Similarity With equation 3, the remaining step is then to share the model weights between models working on similar subgraphs belonging to the same community. However, entirely ignoring the model parameters from different communities may result in exploiting only the local objective while ignoring globally useful weights, which may result in performance degeneration. Therefore, we perform weighted averaging of all the local models from the other clients based on their functional (subgraph) similarities, as follows ( Figure 2 (B)): where α ij is a normalized similarity between clients i and j, and τ is a hyperparameter for scaling the unnormalized similarity score. Note that increasing the value of τ (e.g., 10) will result in model averaging done almost exclusively among subgraphs detected as belonging to the same community.
This personalized scheme handles two challenges in subgraph FL. First, in contrast to the global weight aggregation scheme which easily collapses the knowledge from heterogeneous communities into a single model, our subgraph FL allows the models belonging to different communities to obtain model weights that are beneficial for each community. Also, the missing edges between subgraphs that have been explicitly handled by previous works [42,43,46] could be also implicitly considered by assigning larger weights to models within the same community (See Figure 10). This also enhances data privacy while minimizing the communication costs between probably linked subgraphs.

Adaptive Weight Masking for Selecting Subgraph-Relevant Parameters
With the previous similarity matching scheme, we can effectively group GNN models that belong to the same community, thus preventing the collapsing of irrelevant knowledge from other communities. However, the scalar weighting scheme only considers how much each local model from other clients is relevant for the subgraph task, but not which parameters are relevant. Thus we propose a scheme to select only the relevant parameters from the aggregated model weights transmitted from the server.
Personalized Parameter Masking We perform selective training and updating of the aggregated parameters by modulating and shifting them, using sparse local masks. Let µ k be a local mask for a client k. Then, our local model weight is obtained by modulating the weights from the server, as follows: θ k =θ k µ k , where is an element-wise multiplication operation between the globally given weightθ k and the local mask µ k . Note that the local mask is a free variable and is not shared across clients. Also, we initialize µ k as ones, in order to start training with the globally initialized model parameters. We then further promote sparsity on the mask, which brings two key advantages. First, we can transmit only the partial parameters, that have not been sparsified at the client to the server rather than sending all parameters, thus reducing the communication costs. Moreover, if local masks are sufficiently sparse, the local models can be trained faster, given that zero-skipping operations are supported (Figure 2 (C)). To take these benefits, we use L 1 regularizer on µ k when performing local optimization (See Section B.3 for details on sparsification), as shown in equation 5.
Preventing Local Divergence with Proximal Term As masks are trained only with limited local data without parameter sharing, they may be easily overfitted to the training instances in each client.
To alleviate this issue, we adopt the proximal term proposed in Li et al. [26] that regularizes the locally updated models θ k to be closer to the globally given modelθ k , therefore, preventing the model from extremely drifting to the local training distribution. To sum up, at k-th client, our objective function including sparsity and proximal terms with L 1 and L 2 losses is denoted as follows: where L is the conventional cross-entropy loss function, and λ 1 and λ 2 are scaling hyper-parameters.

Experiments
We now experimentally validate our FED-PUB on six different datasets under both the overlapping and disjoint subgraph scenarios with varying client numbers, with node classification tasks.

Experimental Setups
Datasets Following the experimental setup from Zhang et al. [46], we construct the distributed subgraphs from the benchmark dataset by dividing it into the number of participants, each of which has a subgraph that is a part of an original graph. Specifically, we use six datasets: Cora, CiteSeer, Pubmed and ogbn-arxiv for citation graphs [38,17]; Amazon-Computer and -Photo for product graphs [30,39]. We then divide the original graph into multiple subgraphs using the METIS graph partitioning algorithm [21] that can specify the number of subsets (i.e., clients for FL). For the non-overlapping scenario where there are no duplicate nodes between subgraphs, we directly use the output from the METIS as it provides the non-overlapping partitions. Meanwhile, for the overlapping scenario where nodes are duplicated between subgraphs, we randomly sample the subgraphs multiple times from the partitioned graph. For more details, please see Section B of the appendix.  4 . We then measure the node classification accuracy on subgraphs at the client-side, and then average the performance across clients. We provide further details in Section B of the appendix.

Experimental Results
Main Results Table 1 shows the node classification performance under the overlapping subgraph scenario, in which our FED-PUB statistically (p > 0.05) significantly outperforms all the baselines. In particular, while FedGNN and FedSage are two pioneer works for the subgraph FL problem, they significantly underperform personalized FL methods including ours, especially at the larger number of clients. This is even surprising as they share node information between clients for handling the missing edge problem, yet we suppose such inferior performance comes from naive averaging of local weights without consideration of community structures. While personalized FL baselines including FedPer and GCFL show decent performance by alleviating the knowledge collapse between subgraphs with local parameters or clustering, they still largely underperform ours as they are not concerned with the aggregation between similar subgraphs that form a community (i.e., GCFL uses a bi-partitioning scheme where it iteratively divides a group of subgraphs within the same community into two disjoint sets). We then further conduct the experiments on the disjoint subgraph scenarios  (f) ogbn-arxiv Figure 5: Convergence plots for the non-overlapping node scenario. We visualize the test accuracy curves for all six datasets corresponding to Table 2, over 100 communication rounds with 10 clients.
(non-overlapping scenario), where nodes are not overlapped between subgraphs, which makes the subgraph FL problem more heterogeneous. As shown in Table 2, FED-PUB consistently outperforms all existing baselines in such a challenging scenario, demonstrating the efficacy of ours.
Fast Local Convergence As shown in Figure 4 and 5, our FED-PUB converges rapidly, compared against baselines including personalized FL models. We conjecture that this is because, not only ours accurately identifies subgraphs forming the community and then shares weights largely across them for promoting the joint improvement of them, but also masking subgraph-irrelevant weights received from the server for localization to local subgraphs, demonstrated in the next two paragraphs.
Accurate Community Detection We aim to show whether FED-PUB accurately groups subgraphs comprising a community during weight aggregation. If two different subgraphs have many missing edges or have similar label distributions, we usually regard those two as within the same community [35,10,34]. Thereby, as shown in Figure 6 (a) and (b), there are four different communities by the interval of five, and the last two communities further comprise a larger community. Then, as shown in Figure 6 (c) and (d), FED-PUB detects obvious four communities at the first few rounds, and then captures the larger yet somewhat less-obvious community consisting of two smaller communities.
Ablation Study To analyze the contribution of each component, we conduct the ablation studies. As shown in Figure 7, we observe that each of our subgraph similarity matching and weight masking significantly improves the performances from the naive FedAvg, while the performance is much improved when using both together. However, the benefit from each component is different across overlapping and non-overlapping scenarios. In particular, in the former scenario where a group of highly overlapped subgraphs usually comprise a community, similarity matching for community detection is more beneficial since capturing the community would promote the joint improvement of subgraphs belonging to the same community. However, in the non-overlapping scenarios, subgraphs within the same community become lesser similar, thus selectively using the aggregated model weights from the server with personalized weight masks improves the performance a lot.
Communication Efficiency Another notable advantage of using the sparse masks is that we can reduce the communication costs at every FL round, as well as the model size for faster training, which we demonstrate in Table 8. In particular, Table 8 shows that existing subgraph FL methods require more than two times larger communications costs, measured by adding both the client-to-server and server-to-client costs, compared against the naive FedAvg, since they require to transfer additional node information between clients for estimating the probable nodes on the subgraphs. Contrarily, our FED-PUB has significantly lower communication costs and lower model sizes by using the sparse masks on the model weights: transmitting and training with only the partial parameters not sparsified at the client. Further, as shown in ours variants in Table 8, we can manage the trade-off between the model sparsity and the performance by controlling the hyperparameter for sparsity regularization, λ 1 .  Clients   1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20 Clients (a) Missing edges 1 2 3 4 5 6 7 8 91011121314151617181920   Clients   1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20 Clients (b) Label similarity 1 2 3 4 5 6 7 8 91011121314151617181920   Clients   1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20 Clients (c) Round at 5   1 2 3 4 5 6 7 8 91011121314151617181920   Clients   1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20 Clients (d) Round at 30 Figure 6: The heatmaps of the community structure on the overlapping node scenario with Cora (20 clients). Dark color indicates high similarity. (a) and (b) represent the data-level community structures, captured by our FED-PUB in (c) and (d) at round 5 and 30.      Varying Local Epochs As shown in Figure 9, when we increase the number of communication rounds and the local steps, the model diverges to the local subgraphs (i.e., overfitting), due to the small number of training instances and the direct connection between training and test nodes: struggle to generalize to the test instances. However, our model with the proximal term in equation 5 alleviates this issue, therefore, maintaining the highest local performance. Notably, the performance with five local epochs is inferior to the performance of one epoch, which indicates that increasing the local epochs does not always bring advantages and properly tuning them is important for subgraph FL.
Handling Missing Edges To measure whether FED-PUB can handle the missing edge problem: information is not shared between two neighboring subgraphs due to the missing edges, we use the local model trained on the local subgraph for evaluating the performance on its neighboring subgraph, in which the local subgraph has the most missing edges to its neighboring subgraph. Specifically, in Figure 10, (Neighbor) denotes the subgraph performance evaluated by its neighbor model, while (Local) denotes the subgraph performance from its own local model. Then, the high performance on (Neighbor) measure means two associated subgraphs share meaningful knowledge without having explicit edges between them, thereby solving the missing edge problem. Note that, existing subgraph FL explicitly augments the nodes and edges for capturing the potential information flow over the missing edges between subgraphs, while ours implicitly shares weights a lot across similar subgraphs within the same community. Figure 10 shows that ours achieves the significantly superior performance on the neighboring subgraph problem against subgraph FL baselines, which confirms that ours has an advantage on the missing edge problem by meaningfully sharing knowledge between two subgraphs having potentially missing edges, without explicitly estimating them.

Conclusion
We introduced a novel problem of personalized subgraph FL, which focuses on the joint improvement of local GNNs working on interrelated subgraphs (e.g. subgraphs belonging to the same community), by selectively utilizing knowledge from other models. The proposed personalized subgraph FL is highly challenging due to 1) difficulty of computing similarities between local subgraphs that are only locally accessible, and 2) knowledge collapse among local models that work on heterogeneous subgraphs during weight aggregation. To this end, we proposed a novel personalized subgraph FL framework, referred to as FEDerated Personalized sUBgraph learning (FED-PUB), which computes the similarities across subgraphs using functional embeddings of their local GNNs on random graphs, and uses them to perform a weighted average of the local models for each client. Further, we mask out globally given weights to focus on only the relevant subnetwork for each client (or community). We extensively validated our framework on multiple benchmark datasets with both overlapping and nonoverlapping subgraphs, on which our FED-PUB significantly outperforms relevant baselines. Further analyses show the effectiveness of the subgraph similarity matching for detecting the community structures, as well as the weight masking for tackling the subgraph heterogeneity. We provide the limitations and potential societal impacts of our work in Section D of the appendix. them as the subgraph for one particular client. This procedure is performed five times to generate five different yet overlapped subgraphs for five clients, per one split subgraph obtained from METIS.

B.3 Implementation Details
Implementation Details on Sparse Masks As described in Section 4.2, we propose to sparsify the local personalized mask µ k for each client k, for taking advantages of efficiencies in communication and prediction costs. In this paragraph, we additionally provide the detailed implementation specifications on sparse masks during the training and test phases of our FED-PUB. First, in training, we regularize the local mask µ k to be sparse by minimizing the L 1 Norm of it along with its scaling parameter λ 2 to the local loss L, represented in equation 5. However, this regularization scheme might not be enough to exactly make a subset of local masks zero. Therefore, in the test phase, we use the threshold scheme, where elements (neurons) of µ k below a certain threshold (i.e., λ 2 ) are set to zero. By doing so, we can transmit only the partial parameters to the server, but also can predict with only the partial parameters, therefore, effectively reducing communication and prediction costs.
Common Experimental Details For all experiments, we stack two layers of Graph Convolutional Network (GCN) [23] and one linear classifier layer. Also, the number of hidden dimensions is set to 128, the learning rate is set to 0.001, and all clients participate in federated training for every round. Then, all models are optimized with Adam optimizer [22]. To obtain functional embeddings in our FED-PER framework, we randomly generate a community graph from a stochastic block model [16]. Specifically, we sample five different graphs each of which has 100 nodes, where the probability of edges within the single graph is 0.1, while the probability of edges between the different graphs is 0.0. The node features for the sampled community graph are randomly initialized from the normal distribution. Note that the randomly sampled graphs are initialized at the server-side and the server distributes such graphs to all clients, while the client calculates its model's functional embedding and then transmits the obtained embedding to the server. Furthermore, for all experiments about our FED-PUB, we set the λ 1 and λ 2 for L 1 and L 2 losses for sparsity and proximal terms as 0.001. Notably, while we can tune such two scaling hyperparameters, we observe that those two values show satisfactory performances across all datasets without further specific tuning to each dataset.

Experimental Details on Synthetic Graphs
We perform two experiments on synthetic graphs, which are shown in Figure 1 and Figure 3 of the main paper. In particular, in the experiment of Figure 1, there are three communities that have different label distributions (e.g., the nodes in the first community have label 0, whereas the nodes in the last community have label 2), and each community has 5/5/40 non-overlapped subgraphs. Also, there are 50 clients, and each client has one of 50 subgraphs. Each subgraph consists of 30 nodes, and the edges between two nodes are sampled from the probability of 0.5. Also, in the experiment of Figure 3, there are two communities that have different label distributions, and each community has 5/15 non-overlapped subgraphs. Also, there are 20 clients, and each client has one of 20 subgraphs. Each subgraph consists of 30 nodes, and the edges between two subgraphs within the same community are sampled from the probability of 0.7, whereas the edges between two subgraphs from different communities are sampled from the probability of 0.01. For all experiments, the number of local epochs is set to 3, and the number of total rounds is set to 100. In our FED-PER including its variants of using parameter and gradient, the scaling hyperparameter for calculating the similarity in equation 4 (i.e., τ ) is set to 10.
Experimental Details on Real-World Benchmark Graphs For small datasets, namely Cora, CiteSeer and PubMed, we set the number of local training epoch as 1, and the number of total rounds as 100. Also, for larger datasets, such as Computer, Photo and arxiv, we set the number of total rounds as 200, while the number of local epochs is set to 2 for Photo and arxiv, and set to 3 for Computer. In the overlapping node scenario, we set the similarity scaling hyperparameter (i.e., τ ) as 5 for all our models. Meanwhile, we set the similarity scaling hyperparameter (i.e., τ ) as 3 in the non-overlapping node scenario for all our models. We generally observe that, the larger τ value works better for the overlapping node scenario, in which different subgraphs are easily grouped together, compared to the non-overlapping node scenario. Finally, we report the test performance of all models at the best validation epoch, and the performance is measured by the node classification accuracy.
Computing Resources For all experiments, we use PyTorch [33] and PyTorch Geometric [8] as deep learning libraries. We use two types of GPUs: GeForce RTX 2080 Ti and TITAN XP for training each model. The runtime of our framework depends on the number of clients, and also workers for processing clients' jobs, as well as the number of local epochs and rounds. In general, we use 10 or 20 workers (i.e., simultaneously training 10/20 local models for 10/20 clients), and the single run of our algorithm for 50 clients with 1 local epoch and 100 total rounds takes less than 2 hours.  Figure 11: Analysis on hyperparameters λ1 and λ2, with corresponding model sparsity and performance.

C Additional Experimental Results
C.1 Results of λ 1 and λ 2 Experiments In Figure 11, we further explore the effects of hyperparameters λ 1 and λ 2 on the Cora dataset with the overlapping node scenario, where the number of local epochs is set as 2 and the number of clients is set as 10. In particular, λ 1 value can control the degree of the model sparsity, thus, to see its efficacy, we fix λ 2 value while varying λ 1 , and then measure both the model sparsity and performance. As shown in Figure 11 left, higher λ 1 values significantly increase the model sparsity, meanwhile, the model performance is slightly decreased.
The results indicate that we should consider the trade-off between the sparsity and the model performance, when choosing the λ 1 value. On the other hand, λ 2 value is designed to prevent the excessive knowledge drift to the local subgraph distributions, and, to verify its effectiveness, we fix λ 1 value while varying λ 2 . As shown in Figure 11 right, too small lambda values lead to the performance degeneration, thus choosing the sufficiently large λ 2 values (e.g., 1e-1) would lead to the performance improvement. Also, we further observe that the sparsity does not depend on λ 2 value, thus the effects of λ 1 and λ 2 are orthogonal and complementary.

D Limitations and Potential Societal Impacts
In this section, we discuss the limitations and potential societal impacts of our work.
Limitations While our personalized subgraph FL framework, namely FED-PUB, is generally applicable regardless of the types of subgraphs (e.g., unipartite graphs or bipartite graphs), our experiments are mainly done with unipartite graphs which are the most popular graph representation learning settings. However, the behaviors of our FED-PUB on the other types of graphs, such as bipartite graphs, would be interesting to further see, which is but not been explored so far, and we leave this as future work.
Potential Societal Impacts The FL scheme is important for preserving users' privacy, and, while this scheme is actively studied in the image and language domains, it gets little attention for graphs. In particular, the subgraph FL, which we mainly target, has unique challenges on missing nodes, edges, and their community structures, and we believe which are sufficiently tackled in our work.
Then, the potential positive impact of our work on society is that, our method affects various domains that use graphs, such as social networks, recommendation networks, and patient networks, to name a few. Note that we would like to emphasize the importance of our subgraph FL scheme, especially in social and recommendation networks. In the current real-world applications, all the user's interactions with other users for social networks and with other products for recommendation networks may be stored in the server. However, this may not preserve the user's privacy, but also has potential risks of a leak of user data from the server, such that storing the user's data in the server is not recommended, for example, from the data protection regularizations such as GDPR 5 . Then, by applying our subgraph FL framework to this domain, we expect such problems could be resolved by not storing user's interaction data to the server, but only sharing the locally trained models with clients.
However, the transmitted model parameters from the client to the server may hold the privacysensitive information, and, while this is not the main focus of this work (i.e., we assume that model parameters are transmittable without compromising privacy as in many FL works [31,26,2]), the research community may need to put further attention about whether the model parameters is safe, and how to make them safe if the model parameters contain privacy-sensitive information.