Personalized Subgraph Federated Learning
Authors: Jinheon Baek
Wonyong Jeong
Jiongdao Jin
Jaehong Yoon
Sung Ju Hwang
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph Representation Learning
Graph Neural Networks
Federated Learning
Subgraph Federated Learning

Abstract: 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 communities of a global graph, therefore, consequently collapsing the 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.

Under review as a conference paper at ICLR 2023
PERSONALIZED SUBGRAPH FEDERATED LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
In real-world scenarios, subgraphs of 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 sub- graph Federated Learning (FL) methods deal with those missing links across pri- vate local subgraphs while distributively training Graph Neural Networks (GNNs) on them. However, they have overlooked the inevitable heterogeneity among sub- graphs, caused by subgraphs comprising different communities a global graph, therefore, consequently collapsing the incompatible knowledge from local GNN models trained on heterogeneous graph distributions. To overcome such a lim- itation, introduce 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 novel framework, FEDerated Personalized sUBgraph learning (FRD-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. Fur- ther, learns a personalized sparse mask each client 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, which ours largely outperforms relevant baselines.
INTRODUCTION
Most of the previous Graph Neural Networks (GNNs) (Hamilton, 2020) 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. (2021), 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. How data, a neural network with its subgraphs distributed across multiple participants (i.c., clients)? The most straightforward way to perform Federated Learning (FL) with GNNs. Specifically, each client will individually train a local GNN on the private local data, while a central server aggregates locally updated GNN weights from multiple clients into one, and then transmits it back to the clients.
then collaboratively train, without sharing actual
However, an important challenge for such the subgraph FL scenario is how to deal with potentially missing edges between subgraphs that are not captured by individual data owners. but may carry im- portant information (See Figure (A)). Recent subgraph FL. methods (Wu et al., 2021a; Zhang et al., 2021) additionally tackle this problem by expanding the local subgraph from other subgraphs, as il- lustrated in Figure (B). In particular, they expand the local subgraph either by exactly augmenting the relevant nodes from the other subgraphs at the other clients (Wu et al., 2021a), or by estimating the nodes using the node information in the other subgraphs (Zhang et al., 2021). However, such sharing of node information may compromise data privacy and can incur high communication costs.
Also, there exists more important challenge that has been overlooked by existing subgraph FL. We observe that they suffer from large performance degeneration (See Figure right), due to the heterogeneity among subgraphs, which is natural since subgraphs comprise different parts of a global

---

Under review as a conference paper at ICLR 2023
Results Syrth ohe Gropha
Bach Oommunddy Beselt
Communityy
Communhy
Knowledge Collase
Communiyy
Community
User 2
Comm #1 Conz #5 Conta
User Subgroph
Sutgrapa
Calahsrator Each Community
Lelgen
Eadine
node
Subgingh
(A) Community Structure
[B) Existing Subgraph FL (C) Our Personalized Subgraph FL
Loca/Acesracy
30 55 70
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 methods (Wu et al., 202 la; Zhang et al., 2021) expand the local subgraphs to tackle the missing edge problem, but collapse incompatible knowledge from heterogeneous subgraphs. (C) Our personalized subgraph FL focuses on the joint improvement of local models working on interrelated subgraphs, such ones within the same community, by selectively sharing the knowledge across them. (Right:) Knowledge collapse results, where local mod- els belonging to two small communities (Communities and 2) suffer from large performance degeneration by existing subgraph FI., such as FedGNN (Wu et al., 2021a; 2022) and FedSage+ (Zhang et al., 2021). A personalized FI. method, FedPer (Arivazhagan et al., 2019), also underperforms ours since it only focuses on individual model's improvement without sharing local personalization layers between similar subgraphs.
graph. Specifically, two individual subgraphs - for example, User 1 and 3 subgraphs in Communities A and B respectively in Figure (A) - are sometimes completely disjoint having opposite properties. Meanwhile, two densely connected subgraphs form a community (e.g.. User and 2 subgraphs within the Community A of Figure (A)), in which they share similar characteristics. However, it challenging to consider such heterogeneity arising from community structures of a graph.
Motivated by this challenge, we introduce novel problem of personalized subgraph FL, whose goal to jointly improve the interrelated local models trained on the interconnected local subgraphs, for instance, subgraphs belonging to the same community, by sharing weights among them (See Figure (C)). However, implementing such selective weight sharing is challenging, since we do not know which subgraph each client has, due to its 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 to 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 analyses show that our method can discover community structures among subgraphs, and the masking scheme localizes the knowledge with respect to the subgraph of each client. Our main contributions are as follows:
We introduce a novel problem of personalized subgraph FL, which aims at collaborative improve- ments of the related local models (c.g. subgraphs belonging the same community), which has been relatively overlooked by previous approaches on graph and subgraph FL..
We propose 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 framework on six real-world datasets under both overlapping and nve-ovellap node scenarios, demonstrating its effectiveness over existing subgraph FL baselines.
2 RELATED WORK
Graph Neural Networks Graph Neural Networks (GNNs) (Hamilton, 2020; Zhou et al., 2020; Wu al., 2021b; Jo et al., 2021; Baek et al., 2021), which aim to learn the representations of nodes, edges, and entire graphs, are an extensively studied topic. Most existing GNNs under a message passing scheme (Gilmer et al., 2017) iteratively represent node by aggregating features from its neighboring nodes as well as itself. For example, Graph Convolutional Network (GCN) (Kipf & Welling, 2017) approximates the spectral graph convolutions (Hammond et al., 2011), yielding mean aggregation over neighboring nodes. Similarly, for each node, GraphSAGE (Hamilton et al., 2017) aggregates the features from its neighbors to update the node representation. While they lead
2

---

Under review as a conference paper at ICLR 2023
to successes node classification and link prediction tasks for single graphs, they are not directly applicable to real-world systems with locally distributed graphs, where graphs from different sources not shared across participants, which gives rise to federated learning approaches to train GNNs.
Federated Learning Federated Learning (FL) (Li et al., 2021) is an essential approach for our dis- tributed subgraph learning problem. To mention a few, FedAvg (McMahan et al., 2017) locally trains model for each client and then transmits the trained model to 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 crucial issue. To tackle this, FedProx (Li et al., 2020) proposes the regularization term that minimizes the weight differences between local and global models, which prevents the model from diverging the local training data. However, when the local data is extremely heterogeneous, it is more appropri- ate collaboratively train a personalized model for each client rather than learning a single global model. FedPer (A (Arivazhagan et al., 2019) is such a method, which shares only the base layers while having local personalized layers for each client, to keep the local knowledge. Furthermore, share the learned knowledge between heterogeneous clients, recent studies propose to distill the outputs from clients (Lin et al., 2020; Sattler et al., 2021: Zhu et al., 2021), or directly minimize the differ- ences of their model outputs (Makhija et al., 2022). However, 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 collabora- tively train GNNs without sharing graph data (He et al., 2021), which can be broadly classified into subgraph- and graph-level methods. Graph-level FL methods assume that different clients have com- pletely disjoint graphs (e.g., molecular graphs), and recent work (Xie et al., 2021; He et al., 2022) focuses on the heterogeneity among non-Ill) 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 exists missing yet probable links between subgraphs, since a subgraph is a part of a larger global graph. To deal with such missing link problem among subgraphs. existing methods (Wu et al., 2021a; Zhang et al., 2021) 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 may 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 prob- lem with a completely different perspective, focusing on exploring subgraph communities (Girvan & Newman, 2002; Radicchi al., 2004), which are groups of densely connected subgraphs.
3 PROBLEM STATEMENT
We provide 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 n nodes V and a set of m edges along with its node feature matrix X E Ra where each row represents a d-dimensional node feature. (u, v) & represents an edge from node to node v. Then, GNNs (Hamilton, 2020) generally represent each node based on features from its neighbors as well as itself, as follows:
H!!1 = UPDATE' (H', AGGREGATEE ((H,, : Vu N(v))))
(I)
where H is the feature matrix for node v at 1-th layer, (v) denotes a set of adjacent nodes of node 2: ((v)= fu E V (u, v) E), AGGREGATE aggregates the features of e's neighbors, and UPDATE updates the node u'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 goal of Fl. is to collaboratively train model with local data. Let assume we have K clients with locally collected data inaccessible from others: Dj {X,, y: Ng where X; is a data instance, y; is its corresponding class label, and N₂ is the number of data instances at k-th client. Then, popular FL algorithm, FedAvg (McMahan et al., 2017), works follows:
1. (Anitialization) 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
0, represented as follows: (()) (0)) Yk, where o(0) is the parameters for k-th client.
3

---

Under review as a conference paper at ICLR 2023
2. (Local Updates) Each active local model performs training on private local data Dj. to minimize the task loss [(D;; x²) consequently updating the parameters ( <- 0 vyV.
3. (Global Aggregation) After local training, the server aggregates the locally learned knowledge with respect to the number of training instances, i.e., ((1) No and distributes the updated global parameters ((1) to the local clients selected at the next round.
N k= @ with N Σx No.
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 graph- structured data. In particular, unlike with an image domain where each instance X; is independent to the other images, each node in a graph is always influenced by its relationships to adjacent nodes (u).. Moreover, local graph G, could be a subgraph of larger global graph G: G2 S G. In such a case, there could be missing edges between subgraphs in two different clients: (u, v) with u E V; and v E V; for clients i and j, respectively. To tackle this problem, existing methods (Wu al., 2021a; Zhang et al., 2021) estimate the nodes of local subgraph G2 based on the node information from subgraphs at other clients G, Vi # 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 (Abadi al., 2016).
Yet, there exists more challenging issue. Assume that we have global graph consisting of all sub- graphs. Then, there are communities of such subgraphs (Radicchi et al., 2004; Girvan & Newman, 2002; Porter et al., 2009), where subgraphs within the same community are more densely connected to each other than subgraphs outside the community. Formally, a global graph 9 can be decomposed into I' different communities: C S G Vi I....,T, T, where i-th community C, (V,, E,) consists of densely connected nodes, Then, in a subgraph FL problem, a local subgraph G, belongs to at least
one community: C; = دز Gj. Note that, based on the theory of network homophily (McPherson et al., 2001), such connected subgraphs within the same community have similar properties, while subgraphs in two opposite communities are not. Such distributional heterogeneity of communities may lead 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 personalized weight averaging of local model parameters; thereby capturing the community structure among interrelated subgraphs. To be formal, the objec- tive of existing subgraph FL (Wu et al., 2021 la; Zhang et al., 2021; Liu et al., 2021) is as follows: min5 Σg.gg L(G;; 0). However, finding universal set of parameters (i.e., 0) that works all tasks will result in finding a suboptimal parameter set, since subgraphs in two different communities with sparse connections are extremely heterogeneous due to the network homophily. To address this limitation, we formulate novel problem of personalized subgraph FL, formalized as follows:
K
Σ C(G, 0, + p O (0. G.E9
mii
Σ
O 0g
with askk > ag for G3 S C and G g C, (2)
where O, is the weight for subgraph G; belonging community C. Ouj is the coefficient for weight aggregation between clients and j. which can promote the collaborative learning across multiple local models working interrelated subgraphs that belong to the same community, by assigning larger weights on them. However, this scalar coefficient aij cannot inform us which elements of the aggregated weight are relevant subgraph G,. Therefore, we further multiply to the trainable sparse vector l4; with element wise multiplication o to shift and filter out irrelevant weights from subgraphs of heterogeneous communities. We will specify how to obtain a and μ Section
4 FEDERATED PERSONALIZED SUBGRAPH LEARNING FRAMEWORK
To realize our goal of personalized subgraph FL (equation 2), we propose to compute subgraph sim- ilarities for detecting communities, and to mask weights from subgraphs in unrelated communities.
4.1 SUBGRAPH SIMILARITY ESTIMATION FOR DETECTING SUBGRAPH COMMUNITY
We aim to capture the community structure consisting of a group of densely connected subgraphs. Note that, due to network homophily where similar instances in the graph are more associated with
4

---

Under review as a conference paper at ICLR 2023
Community B
Model
hg
Community
Random Graphs,
--//G%)
User Subgraph
User Subgraph
Plodel z:
02
User
High Simianty ho
Sulgraph
Model 3
0g
(A) Community Structure
(B) Subgraph Similarity Matching Server
(C) Weight Masking In Client
Figure 2: (A) Two communities, where Community A and B consist of one and two subgraphs. respectively. (B) Client Similarity Matching: we first forward randomly generated graphs to models f(G; f.), and obtain functional embeddings ht, which are then used to estimate subgraph similarities. Then, the similarities are used weight aggregation, resulting in personalized model weights 0, (C) Weight Masking: transmitted weights from the server to clients 0, are masked and shifted by local masks J4, for localization to the local subgraph.
each other (McPherson et al., 2001), subgraphs within the same community should be similar. In other words, one can measure subgraph similarities, we can group similar ones into the commu- nity. However, measuring similarity between local subgraphs is challenging since do not know which subgraph each client has due to local accessibility. How can we then compute subgraph sim- ilarities, without accessing them? To this end, we propose approximate the similarity at local clients using auxiliary information obtained from the local GNN models working on the subgraphs.
Subgraph Similarity Estimation with Model Parameters For measuring the similarity between local subgraphs, without access- ing them, we may use the model parameters proxies, as follows: []]][[)]||@ where 0 is parameter flatten into vector, and S is a similarity measure. This may sound reason- able since the GNN model trained on the subgraph will embed its knowledge into its parameters. However, this scheme has a notable drawback that similarity measured in the ligh-dimensional parame- ter space is not meaningful due to the curse of dimensionalityy (Bell- man, 1966), and that the cost of calculating the similarity between parameters grows rapidly as the model size increases (See Figure 3).
Pararaater
Gradlest
Finclia
((i.j) = (0,
Time (Swe)
115 1008
2005
# of Hidden Dimensions
Figure 3: Effectiveness (top) and efficiencies (hottom) of different similarity measurements.
Subgraph Similarity Estimation with Functional Embedding To tackle the limitation of using parameter distance, we propose to measure the functional similarity of neural networks by feeding the same input to every local model and then calculating the similarities using their outputs, inspired by neural network search (Jeong et al., 2021). The main intuition is that we can consider the trans- formation defined with neural network as a function, and measure the functional similarity of two networks by the distance of their outputs for the same input. However, unlike the previous work, which uses Gaussian noises as inputs for image classification, we random graphs inputs we work with GNNs. Formally, let G (²,E) be random community graph designed by stochastic block model (Holland et al., 1983), where subgraphs within the community have more edges be- tween them than edges across the communities (See Appendix B.3 for initialization details). Then, the similarity between two functions defined by GNNs at clients and j is defined as follows:
h hj S(i.j) [1 [11l"
h, = AVG(f(ā; (.))))) and h, = AV
(3)
where h is the averaged output of all node embeddings for input & with average operation, AVG. We provide additional discussions with results on similarity estimation in Appendix C.6 and C.7.
Personalized Weight Aggregation with 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 model parameters from different communities may result in exploiting only the local objective while ignoring globally useful weights, which results in suboptimal performance (See Appendix C.8 for details). Therefore, perform weighted averaging of local models from all clients based on their functional similarities, as follows (Figure 2 (B)):
K
exp(r S(i,))
0, -
Σ
aij Oj, J=1
ais exp(T S(i,
5

---

Under review as a conference paper at ICLR 2023
where aij is normalized similarity between clients i and j, and is a hyperparameter for scaling the unnormalized similarity score. Note that increasing the value of r (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 global weight aggregation which collapses the knowledge from heterogeneous communities, our subgraph FL al- lows the models belonging to different communities to obtain individual parameters that are benefi- cial for each community. Also, missing edges (i.e., a lack of information sharing) between intercon- nected subgraphs, which are explicitly handled by expanding local subgraphs in existing works (Wu al., 202 la: Zhang et al., 2021), could be implicitly considered by largely sharing the knowledge among models of probably linked subgraphs within the same community (See Figure 6 and 9). This enhances data privacy while minimizing communication costs between subgraphs.
4.2 ADAPTIVE WEIGHT MASKING FOR SELECTING SIBGGRAPH-RELEVAN PARAMETERS
Based on the previous similarity matching scheme, we effectively group GNNs 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 masking them, using sparse local masks (Figure (C)). Formally, let μ, be a local mask for client i. Then, our local model weight is obtained by modulating the weights from the server, as follows: 0, = 0, C pi. where O is an element-wise multiplication operation between the globally given weight 0, and the local mask μ4: Note that μ4 is free variable and not shared across clients. Also, we initialize μı; as ones, in order to start training with the globally initialized model parameters without modification. We then further promote sparsity on the mask, to take two 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. Also, if local masks are sufficiently sparse, local models can be trained faster, when zero-skipping operations are supported. To take these benefits in sparsity, we use L1 regularizer on μt; when performing local optimization (See Appendix B.3 for details on sparsification), 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. (2020) that regularizes the locally updated model 0, to be closer the globally given model 0., therefore, preventing the model from extremely drifting to the local training distribution. To sum up, at i-th client, our objective function including sparsity and proximal terms with L1 and L2 losses is denoted as follows:
min L(G;; 01, p:) A ||:| + >all0; 0.112. (0,)4:)
(5)
where is a conventional cross-entropy loss function, and X and A2 are scaling hyper- paramersr.
5
EXPERIMENTS
We now experimentally validate our FED-PUB on six different datasets under both the overlapping and disjoint subgraph scenarios with varying client numbers, on node classification tasks.
5.1
EXPERIMENTAL SETUPS
Datasets Following the experimental setup from Zhang et al. (2021), we construct distributed subgraphs from the benchmark dataset by dividing it into the number of participants: each FL. par- ticipant has a subgraph that is a part of an original graph. In particular, we use six datasets: Cora, CiteSeer, Pubmed and ogbn-arxiv for citation graphs (Sen et al., 2008; Hu et al., 2020); Computer and Photo for product graphs (McAuley et al., 2015; Shchur et al., 2018). We then divide the original graph into multiple subgraphs using the METIS graph partitioning algorithm (Karypis, 1997). Note that, unlike the Louvain algorithm (Blondel et al., 2008), used in Zhang et al. (2021), that requires to further merge partitioned subgraphs into particular numbers of subgraphs since it cannot specify the number of subsets (i.e., clients for FL.), the METIS algorithm can specify the number of subsets,

---

Under review as a conference paper at ICLR 2023
Table 1: Results on the overlapping node scenario. The reported results are mean and standard deviation over three different runs. The statistically significant performances (p > 0.05) are emphasized in bold.
Corn
Citebeer
Puhmed
Methods
18 Clients
30 Clients
50 Clients
10 Clinus
30 Clients
50 Clients
10 Clicnts
30 Clisnts
50 Clisnts
73.98 0.25
71.65
76.63
0.08
64.54 0.42
56.68 = 0.44
$2.32
50.72 0.16
50.54
0.11
PedAng
46,86. 1:3:6
53
1 0:58
4.53
6h
0.6
16.11
1.00
K2.67
0.11
K0,00 01.1
00.26 0.35
PalPhix
2
51
2 1.74
36.27 4-9.04
00.30
0:335
66.11
0.75
56.53
0.43
53.63
0.17
80.03
0.13
50.50
2: 0.46
FolFer
78.73.0033
6:244
6:337
67.64
0.10
78:84 0.20
25
7661
09.65
0.39
64.90
0.18
0.30
K3.50
0.25
60.37
0.12
61
PeUUNN
000
61 18 3:335
26
8 1002
02:21
8 0:30
1:32
54.00
0.98
04:25
007
02.02
0.23
$1.85
0.10
FolSagce
77.52 0.46
31.99
0:42
35.45
68.73
0.46
63.97
0.02
63:03
0.30
52.77
62.14=0.11
50.31
0.68
FED PUB (Our)
79.00 0.12
75:40 0.54
77.84 1
70.58 0.20
68.33 0.45
09.31 0.30
85,70
85.36 0.10
$4.54 0.12
Campot-Camptter
Photo
oghinersi
Methods
10 Clients
38 Clients
90 Clients
10 Clients
30 Clients
50 Clients
10 Clicuts
30 Clicatts
50 Clients
Arg.
Local
58.50 0.20
0.20
56.65 1: 0,00
87.04 1 0.02
92.17
0.12
90.16 =: 0.12
90:42 = 0.15
02.52 = 0.07
51.32 =: 0.04
00.04 2: 0.04
76.72
0:32
24.10
0.08
FedProk
13.444 0.30
83.84
0:899
76.00
2 6.7
02.67
2:03 2.1.
89.17
0.40
72.36
2.66
63.53
0.11
59.86
0.16
61.12
2: 0.04
13.38
Podtirr
0:04
00 0:335
5K.21
01.88
01:21
0.16
0000
0.38
81.97
0.04
61
7K:42
PeIGNN
15.15
2:09
$7.00
0.30
83.06
2 0.88
91.47
0.11
87.91
1.34
78.90
6.46
63.08
0.19
60.09
0.04
60.51 0:11
73.65
FodSages
59:24
2 0.15
81.33
2: 1.20
76.72
4 0.39
92.76
2 0.05
88.09
0.59
72.41
= 1.36
03.24
= 0.02
59.90
0.12
60.95
2: 0.09
73.12
PUB (Uurs)
89.15
0:06
0:14
0.07
V2.01
0.07
91.71
0.12
62.55
Q.12
(a) Cora
(b) CiteSeer
(c) Puhmedd
(d) Computer
(e) Photo
(1) oghn-aari arxiv
Figure 4: Convergence plots for the overlapping node scenario. We visualize the test accuracy curves for all
six datasets corresponding to Table 1, over 100 communication rounds with 30 clients.
thus making more reasonable experimental settings in subgraph FL (See Appendix C.2). For the non-overlapping scenario where there are no duplicate nodes between subgraphs, we use the output from the METIS as it provides non-overlapping partitions. Meanwhile, for the overlapping scenario where nodes are duplicated among subgraphs, we randomly sample the subsets (i.c., subgraphs) of the partitioned graph multiple times. For more details on datasets, please refer to Appendix B.
Baselines and Our Model 1) FedAvg (McMahan et al., 2017) and 2) FedProx (Li et al., 2020):
The most popular FL baselines. 3) FedPer (Arivazhagan et al., 2019): A personalized FL baseline without sharing personalized layers. 4) FedGNN (FedPerGNN) (Wu et al., 2021a; 2022) and 5) FedSage+ (Zhang et al., 2021): Subgraph FL. baselines which we mainly target. 6) GCFL (Xie et al., 2021):: A graph FL baseline which works on completely disjoint graphs (i.c., graph-level FL) as in clustered FL (Sattler et al.. 2020), adopted for subgraph FL. 7) Local: A baseline without sharing weights with other clients. 8) FED-PUB: Our personalized subgraph FL including subgraph similarity matching and weight masking. We provide further descriptions in Appendix B.2.
Implementation Details We use the two layer GCNs (Kipf & Welling, 2017) as the base GNN for all models. We perform FL over 100 communication rounds for Cora, CiteSeer and Pubmed datasets, while 200 rounds for Computer, Photo and arxiv datasets, considering the size of datasets. The local training epoch is selected in the range of [1, 2, 3) depending on the dataset size (e.g., Computer three while CiteSeer is one)². We use the Adam optimizer Kingma & Ba (2015) for model optimization. We then measure the node classification accuracy on subgraphs at the client- side, and then average the performance across clients. See Appendix B.3 for more details.
5.2 EXPERIMENTAL RESULTS
Main Results Table 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 issue between subgraphs with local parameterization or clustering, they still largely underperform ours as they are not concerned with aggregation between similar subgraphs that form community (i.e., GCFL uses bi partiiiitinn scheme, which iteratively divides group of subgraphs within the same
FedGNNN is extended to FedPorGNN, where the core algorithm of averaging all client gradients is the same. We found communication rounds and local epochs are important factors prevent overfitting of all models.
7

---

Under review as a conference paper at ICLR 2023
Table 2: Results on the nor-overla node scenario. The reported results are mean and standard deviation over three different runs. The statistically significant performances (p > 0.05) are emphasized in bold.
Cara
Citebeer
Puhmed
Methods
5 Clicnis
18 Clients
20 Clients
Clints
10 Clients
20 Clients
Clients
I0 Clients
20 Clients
$1 0.21
79.94
0.24
50.30
0.05
67.82
0.13
15.58 =
54.04
=
$2.65
0.03
PodAng
74
5.64
69 1 0.87
60
1:58
0.00
61.61
3:30
54.88
185
19.40
0.11
K2:11 01.2
00.97 0.25
PalPhix
72.03
4.56
40 2 7.04
48 2 6.81
71:73
1:11
63.33
3.25
64.85
1.35
70.45
0.25
$2.55
0.24
50.50
0.25
FolFer
0.40
7044
0.27
0.31
51477
78.66
79:21
10:00
0.57
09:01
0.12
06.33
0.33
64:18
0.19
63.96
PeUUNN
41:11 0:04
70 12
8 1:00
70
8: 122
09/00
8 0.2
56 52
3.17
51.23
6.00
09.52
022
K3.25
0.00
$1.01
FolSagce
72.97
65:05 1.59
57.97
70.74
0.69
63.63
3.10
65.46
0.74
70.57
12.62
50.32
FED PUB (Our)
83,70 0.19
01.54
81.75
0:36
72,08 0.44
72.3 0.53
67.62 0.12
86.79
86.28 0.15
85.55 i: 0.30
Camputer
Photo
oghnnarsi
Methods
5 Clionts
18 Clients
20 Clients
5 Clicuts
10 Clienis
30 Clients
Clients
10 Clicats
20 Clients
Arg.
Local
59 0.13
38.91 1: 0.17
89.52
1 0.30
91.67 1 0.09
91,80
=: 0.02
90:47 = 0.15
16.76 = 0.07
64.92 =: 0.09
05.06 :: 0.05
79:57
24.20
61.15
3:11
65.54
0.10
68:24
FedProk
55.25
1:27
83:81 2: 1.09
73.05
4: 1.30
90.38
2: 0.44
80.92
4.64
83.33
0.29
65.21
0.20
64.37
0.18
63.03 2: 0.044
72.81
Podtirr
59.77 1.0.4
0:44
S1
196-1:633 0:45
04:44
0:0:7
01
0.3
00:50
0.66
56.87
9003
PeIGNN
18.0844 2:15
88.15
6:441
85.16
2 6.13
90.25
2 3.7.70
K7.12
2.01
51.00
4.45
65:47
0.22
64.21
0.52
63.30
2: 0.05
75.23
FodSage
35.04
4: 0.61
80.50
2: 1.30
70.42 4 0.85
90.77
4 0.44
76,81
= 8.24
$0.58
1.15
05.09
0.09
64.52
0.14
63:31
0:200
73.47
PUB (Uurs)
90.55
0:09
0.19
V3.73 0.18
91.92
0.05
66.64
$1.59
(0) Cora
(b) CiteSeer
(c) Pubmed
(d) Computer (c) Phoco
(f) ogbn-arxiv
Figure 5: Convergence plots for the non-overlapping node scenario. We visualize the test accuracy curves
for all six datasets corresponding Table 2. over 100 communication rounds with 10 clients.
community into two disjoint sets). We then further conduct the experiments on the disjoint subgraph scenario (i.c., 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 can accurately identify subgraphs forming the community and then share weights substantially across them for promoting the joint improvement, but also masking out subgraph-imeleeant weights received from the server for localization to local subgraphs, demonstrated in the next two paragraphs.
Community Detection We aim to show whether the proposed FED-PUB can group subgraphs comprising a community during the personalized weight aggregation. Note that, if two different subgraphs have many missing edges or have similar label distributions, we usually consider those two within the same community (Radicchi et al., 2004: Girvan & Newman, 2002: Porter et al., 2009). 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 larger community. Then, as shown in Figure (c) and (d), our 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 ablation studies. As shown in Figure 7, we observe that each of our subgraph similarity matching and weight masking schemes significantly improves the performances from the naive FedAvg, while the performance much improved when using both together. However, the benefit from each component is differ- ent across overlapping and non-overlapping scenarios. In particular, in the former scenario where a group of densely 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 sce- nario, two individual subgraphs become more heterogeneous, thus selectively using the aggregated model weights from the server with personalized weight masks improves the performance a lot (See additional results and discussions on heterogeneity with sparse weight masks in Appendix C.4).
Communication Efficiency Another notable advantage of using sparse masks is that we can re- duce the communication costs at every FL round, as well as the model size for faster training. In particular, as demonstrated in Table 3, existing subgraph FL methods require more than two times larger communications costs, measured by adding both the sieenttto-server and server-to-cliens costs, compared against the naive FedAvg, since they require to transfer additional node information be- tween clients for estimating the probable nodes on the subgraphs. Contrarily, our FED-PUB has significantly lower communication costs and lower model sizes by using sparse masks model
8

---

Under review as a conference paper at ICLR 2023
Eunzka Cora Cleesd
Tamzla Cora
Ciivets
Chissta
Chisats
Clivente
30 27 37 43 3
Ma
30 24 33 Taunda
(a) Missing edges (b) Label similarity
(c) Round 5 (d) Round 30 (a) Overlapping
(b) Non-owerlapping
Figure 6: The heatmaps of the community structure overlap- ping node scenario with Cora (20 clients). Dark color indicates lots of missing odges between subgraphs (a) or high similarities in labels (b). (c) and (d) are functional similarities captured by our FED-PUB.
Figure 7: Ablation studies of the pro- posed FED-PUB on both overlapping (a) and non-overlapping (b) subgraph scenarios, on the Cora dataset.
Perfermance
Clteenst
Model
Acc. [%]
Model Size (%)
Cost [%
FodArg
76.48 0.36
100,00
0.00
100,00
0,00
Lock Nomeu Conerrn 1i
ReGGMN
70.65 0.85
100,00
0.00
214.54
0.00
FedSage+
0.45
0.00
276.84
0.00
78.84 0.25
100.00
0.90
100.00
Eanc
Ours (1yabe-1)
77.36
0.99
25.13
37.70 0.56
Ours Du-77-11
79.46
42,59
63.89
Ours (Ay55ell
79.89
0.12
57.07
0.52
85.61 0.78
10
20
30
6D
BD
100
10 20 30 0i 30 MI 7O DD TO 100
Communicttion
Table 3: Analysis on efficiencies of communi- Figure 8: Varying the local Figure 9: Performance on cation costs and model sizes with sparse masks. epochs with accuracy curves. interrelated subgraphs.
weights:
transmitting and training only the partial parameters not sparsified at the client. Further, we can manage the trade-off between the model sparsity and the performance by controlling the hy- perparameter for sparsity regularization, X1 (See Appendix C.I for more hyperparameter analyses).
Varying Local Epochs As shown in Figure 8, when increase the number of communication rounds and the local steps, the model diverges to the local subgraph (i.e., overfitting) due to the small number of training instances and the direct connection between training and test nodes: struggling 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 important for subgraph FL.
Handling Missing Edges The missing edge problem, where two interconnected subgraphs cannot share information due to missing edges between them, is a unique challenge in subgraph FL (See Appendix C.9 for more discussions). To tackle this, existing subgraph FL explicitly augments nodes and edges for capturing the information flow over missing edges between interconnected subgraphs, while ours implicitly shares weights a lot across similar subgraphs within the same community. To measure their efficacy, we evaluate the performance on the neighboring subgraph, which has the most missing edges to the local subgraph, based on its local model weight. Specifically, in Fig- ure (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 (Neigh- bor) measure means two associated subgraphs share meaningful knowledge without having actual edges between them, thereby solving the missing edge problem. Figure 9 shows that ours achieves the superior performance on the neighboring subgraph problem against subgraph FL baselines, ver- ifying that ours has an advantage on the missing edge problem by sharing meaningful knowledge between subgraphs having potentially missing edges, without explicitly estimating them.
6 CONCLUSION
We introduced novel problem of personalized subgraph FL,, which focuses the joint improve- ment of local GNNs working on interrelated subgraphs (e.g. subgraphs belonging to the same com- munity), 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 heteroge- neous subgraphs during weight aggregation. To this end, we proposed novel personalized subgraph FL framework, called 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 community and client. We extensively validated our framework on multiple benchmark datasets with both overlapping and non-overlapping subgraphs,
which our FED-PUB significantly outperforms relevant baselines. Further analyses show the effectiveness of the subgraph similarity matching for detecting the com- munity structures, as well as the weight masking for tackling the subgraph heterogeneity.
9

---

Under review as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
We attach the source code of our FED-PUB framework in the supplementary file. Also, we provide every detail of experimental setups including datasets, models, and implementations Appendix B.
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Manoj Ghuhan Arivazhagan, Vinay Aggarwal, Aaditya Kumar Singh, and Sunav Choudhary. Fed- erated learning with personalization layers, 2019.
Jinheon Back, Minki Kang, and Sung Ju Hwang, Accurate learning of graph representations with graph multiset pooling. 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
Richard Bellman. Dynamic programming. Science, 153(3731):34 1966.
Vincent Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008 (10):P00008, 2008.
P. Erdós and A Rényi. On the evolution of random graphs. In PUBLICATION OF THE MATHE- MATICAL INSTITUTE OF THE HUNGARIAN ACADEMY OF SCIENCES, pp. 17-61, 1960.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings the 34th International Conference on Machine Learning. ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 1263-1272. PMLR, 2017.
M. Girvan and M. E. J. Newman. Community structure social and biological networks. Proceed- ings of the National Academy of Sciences, 99(12):7821-7226 2002.
William L. Hamilton. Graph representation learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 14(3):1-159, 2020.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 1024- 1034, 2017.
David K. Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):129-150, 2011.
Chaoyang He, Keshav Balasubramanian, Emir Ceyani, Carl Yang, Han Xie, Lichao Sun, Lifang He, Liangwei Yang. Philip S Yu, Yu Rong, et al. Fedgraphnn: A federated learning system and benchmark for graph neural networks. arXiv preprint arXiv:2104.07745: 2021.
Chaoyang He, Emir Ceyani, Keshav Balasubramanian, Murali Annavaram, and Salman Avestimehr. Spreadgnn: Serverless multi-task federated learning for graph neural networks. AAAI, 2022.
Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First
steps. Social Nenworks, 5(2):109-137, 1983, ISSN 0378-8733.
Weihua Hu, Matthias Fey, Marinka Zimik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:221 1122118-213,, 2020.
10

---

Under review as a conference paper at ICLR 2023
Wonyong Jeong, Hayeon Lee, Geon Park, Eunyoung Hyung, Jinheon Back, and Sung Ju Hwang. Task-adaptive neural network search with meta-contrastive learning. In Advances in Neural In- formation Processing Systems, 2021.
Jachyeong Jo, Jinheon Back, Seul Lee, Dongki Kim, Minki Kang, and Sung Ju Hwang. Edge representation learning with hypergraphs. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information P Processing Systems, volume 34, pp. 7534-7546 7546. Curran Associates, Inc., 2021.
George Karypis. Metis: Unstructured graph partitioning and sparse matrix ordering system. Tech- nical report, 1997.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd Inter- national Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In 5th International Conference on Learning Representations. ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
Qinbin Li, Zeyi Wen, Zhaomin Wu, Sixu Hu, Naibo Wang, Yuan Li, Xu Liu, and Bingsheng He. A survey on federated learning systems: vision, hype and reality for data privacy and protection. IEEE Transactions on Knowledge and Data Engineering, 2021.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. In Proceedings of Machine Learning and Systems 2020, MLSys 2020, Austin, TX, USA, March 2-4, 2020. mlsys.org, 2020.
Tao Lin, Lingjing Kong, Sebastian U Stich, and Martin Jaggi. Ensemble distillation for robust model fusion in federated learning. Advances in Neural Information Processing Systems, 33:2351-2363, 2020.
Zhiwei Liu, Liangwei Yang, Ziwei Fan, Hao Peng, and Philip S Yu. Federated social recommenda- tion with graph neural network. arXiv preprint arXiv:2111.1077 2021.
Disha Makhija, Xing Han, Nhat Ho, and Joydeep Ghosh. Architecture agnostic federated learning for neural networks. arXiv preprint arXiv:2202.07755 2022.
Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. Image-based rec- ommendations on styles and substitutes. In Proceedings of the 38th international ACM SIGIR conference on research and development in information retrieval, pp. 43-52, 2015.
H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Communication-effiieenn learning of deep networks from decentralized data. In AISTATS, 2017.
Miller McPherson, Lynn Smith-Lovin and James M Cook. Birds of feather: Homophily in social networks. Annual review of sociology, 27(1):415-444 444, 2001.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy. Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, reg--performance deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019.
Mason A Porter, Jukka-Pekka Onnela, Peter J Mucha, et al. Communities in networks. Notices of the AMS, 168)117 2009.
Filippo Radicchi, Claudio Castellano, Federico Cecconi, Vittorio Loreto, and Domenico Parisi. Defining and identifying communities in networks. Proceedings of the national academy of sci- ences, 101(9))2658 2663, 2004.
11

---

Under review as a conference paper at ICLR 2023
Felix Sattler, Klaus-Robert Müller, and Wojciech Samek. Clustered federated learning: Model- agmostic distributed multitask optimization under privacy constraints. IEEE transactions on neu- ral networks and learning systems, 32(8):3710-372 2020.
Felix Sattlrr Tim Korjakow, Roman Rischke, and Wojeiech Samek. Fedaux: Leveraging unla- beled auxiliary data in federated learning. JEEE Transactions on Neural Networks and Learning Systems, 2021.
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
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint / 2018.
Duncan J Watts and Steven H Strogatz. Collective dynamics of 'small-world networks. weeet--rrrdneetwwrkks nature, 393 (6684))440-444 442, 1998.
Chuhan Wu, Fangzhao Wu, Yang Cao, Yongfeng Huang, and Xing Xie. Fedgnn: Federated graph neural network for privacy-preserving recommendation. KDD, 2021a.
Chuhan Wu, Fangzhao Wu, Lingjuan Lyu, Tao Qi, Yongfeng Huang, and Xing Xie. A federated graph neural network framework for 13(1):1-10, 2022.
personalization. Nature Communications,
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. IEEE Trans. Neural Networks Learn, Syst., 32 (1):4-24, 24, 2021b.
Han Xie, Jing Ma, Xiong, and Carl Yang. Federated graph classification over non-iid graphs. In Advances in Neural Information Processing Systems, volume 34, pp. 18839-18852. Curran Associates, Inc., 2021.
Ke Zhang, Carl Yang, Xiaoxiao Li, Lichao Sun, and Siu Ming Yiu. Subgraph federated learning with missing neighbor generation. In Advances in Neural Information Processing Systems, volume 34, pp. 6671-6682. Curran Associates, Inc., 2021.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applica- tions. Al Open, 1:57-81, 2020.
Zhuangdi Zhu, Junyuan Hong, and Jiayu Zhou Data-free knowledge distillation for heterogencous federated learning. In International Conference on Machine Learning, pp. 12878-12889, PMLR, 2021.
12

---

Under review as a conference paper at ICLR 2023
Table 4: Dataset statistics. We report the number of nodes, edges, classes, clustering coefficient, and het- erogeneity the original graph and splitted subgraphs on both overlapping and overlappinn node scenarios. Note that Ori denotes the original graph, and Cli denotes the number of clients.
Overlapping mode scenario
Cora
CiteSeer
Pubmed
Ori
10 ClI
Cli
50 CH
Ori
10 ClI
30 CII
ClI
Ort
10 Cli
30 ClI
50 Cli
Classes
6
Nodes
2,485
207
124
2,120
530
177
106
19.717
4,920
1.643
986
Edges
10.138
1,249
379
215
7,358
889
293
170
88.648
10,675
3,374
1.902
Clustening Coefficiont
0.238
0.133
0.129
0.125
0,170
0.088
0.087
0.096
0.000
0.035
0.034
0.035
Heterogencity
NIA
0.297
0.567
0,613
NIA
0.278
0.494
0.547
NIA
0.210
0.383
0.394
ogbe-arsiv
Amaron-Compuue Computerr
Amszon-Phaote
Ori
10 Cli
30 Cli
50 CBi
Ori
10 Cii
30 Cli
50 CI6
Ori
CB
30 Cli
50 Cli
Classes
40
10
8
Nodes
169 343
42,336
14.112
8,467
13,381
3,345
1,115
669
7.487
1,872
624
374
Edges
2, 2.315,50 SU8
282,083
83,770
44,712
491,556
59,236
16,684
8.999
238,086
29,223
8,735
4,840
Clustering Coefficient
0.226
0.177
0.185
0.191
0.351
0.337
0.348
0.359
0.410
0.380
0.391
0.400
Heterogeneity
NIA
0.315
0.606
0.615
N/A
0.327
0.577
0.614
N/A
0.306
0.696
0.684
Now-overlapping
Cora
CiteSeer
Pubmed
Ori
5 Cli
Cli
20 Cli
Ori
5 Cli
10 Cli
Cli
Ori
5 Cli
Cli
Cli
Classes
7
6
Nodes
2,485
497
249
124
2.120
424
212
106
19.717
3,943
1,972
986
Edges
10.138
1,866
422
7,358
1,410
675
326
$3.648
16.374
7,671
3.607
Clustering Coelliciont
0.238
0.250
0.250
0.363
0,170
0.175
0.178
0.180
0.060
0.063
0.066
0.067
Heterogensity
NIA
0.590
0.606
0.665
N/A
0.517
0.541
0.568
NIA
0.362
0.392
0.424
ogha-arxiv
Amazon- Camazon-Comppen Computer
Amazon-Ploon Photo
Ori
5 CII
CII
20 CH
Oni
5 CH
10 CII
CII
Ori
5 Ci
10 CII
CII
Classes
10
10
8
Nodes
169.5 343
33,860
16,934
8,467
13,381
2,676
1,338
669
7,487
1,497
740
374
Edgess
2. 2.315 598
410,,948
182
86,755
491
84,480
36 1336
15,633
238.086
43,138
19.322
8.547
Clustering Coefficiont
0.225
0.247
0.259
0.269
0.351
0.385
0.398
0.418
0,410
0.4.7
0.457
0.477
Heterogencity
NIA
0.593
0.615
0.637
NIA
0.604
0.612
0.647
NIA
0.684
0.681
0.751
A ALGORITHMS
In this section, we provide algorithms of the proposed subgraph similarity estimation and adaptive weight masking in our FED-PUB framework. In particular, weight masking, performed in the client, shown Algorithm 1. Also, similarity matching, working on the server, is shown in Algorithm 2.
Algorithm FED-PUB Client Algorithm
Algorithm FED-PUB Server Algorithm
1: R: the numher of rounds, E: the number of 1:
Function RunServer()
epochs, K: the number of clients, Ge: local data 2: initialize (1)
for client ft: model function for client i, A; 3: for each round r = 1,2,..., do for Vi in parallel do
model parameters for client i, f4s: weight masking 4:
parameters for client i. S(.): similarity matching 5:
if
1 then
function, scaling factor for similarity matching.
6:
0
(1++1)
RunClient (((r)
else
Function RunClient(0.))
((r)
Σ S(L.))
- ((p()-((1A)) 0,
3: 0: t- 0, @ μai
4: for each local epoch from 1 to E do
9:
0 (r+1) RunClient ((
5: 0, O. 1 (G.;
10:
end if
6: end for
end for
7: return 8,
12: end for
B EXPERIMENTAL SETUPS
In this section, we first provide the descriptions of six different benchmark datasets that we use, along with their preprocessing setups and statistics for FL in Subsection B. Then, we explain the baselines and our proposed FED-PUB in detail in Subsection B.2. Lastly, we further describe the implementation details of experiments on synthetic and real-world graphs, as well as additional experimental details functional similarities and sparse masks in Subsection B.3.
B. DATASETS
We report statistics of six different benchmark datasets (Sen et al., 2008; Hu et al., 2020; McAuley al., 2015; Shchur et al., 2018), such as Cora, CiteSeer, Pubmed, and ogbn-arxiv for citation graphs;
13

---

Under review as a conference paper at ICLR 2023
Computer and Photo for amazon product graphs, which we use in our experiments for both the over- lapping and non-overlapping node scenarios, in Table 4. Specifically, in Table 4, we report the number of nodes, edges, classes, and clustering coefficient for each subgraph, but also the hetero- geneity between the subgraphs. Note that, to measure the clustering coefficient, which indicates how much nodes are clustered together, for the individual subgraph, we first calculate the clustering coefficient (Watts & Strogatz, 1998) for all nodes, and then average them. On the other hand, to measure the heterogeneity, which indicates how disjointed subgraphs are dissimilar, we calculate the median Senson-Shannon divergence of label distributions between all pairs of subgraphs.
For dataset splits, we randomly sample 20% nodes for training. 35% for validation, and 35% for testing, for all datasets except for the arxiv dataset. This is because the arxiv dataset has the relatively larger number of nodes as shown in Table 4, thus we randomly sample 5% nodes for training, the remaining half of the nodes for validation, and the other nodes for testing.
We then describe how to partition the original graph into multiple subgraphs, whose number the same as the number of clients (i.e., FL participants). In general, we use the METIS graph partitioning algorithm (Karypis, 1997) to divide the original graph into multiple subgraphs. which can control the number of disjoint subgraphs as parameters. Consequently, in the non-overlapping node scenario, the disjoint subgraph for each client is directly obtained by the output of the METIS algorithm (i.e., if we set the parameter value for METIS as 10, then we can obtain 10 different disjoint subgraphs, each of which is given to each client). On the other hand, in the overlapping node scenario where nodes are duplicated across different subgraphs, disjoint subgraphs for 10 clients, 30 clients, and 50 clients, respectively, with the METIS algorithm. After that, in the one splitted subgraph, we randomly sample half of the nodes and their associated edges, and then use them as the subgraph for one particular client. This procedure is performed five times to generate five different yet overlapped subgraphs, per one splitted subgraph from METIS.
first divide the original graph into 2, 6, and 10
B.2 BASELINES AND OUR MODEL
This method (McMahan et al., 2017) is the FL baseline, where each client locally updates a model and sends it to a server, while the server aggregates locally updated models with respect to their numbers of training samples and transmits the aggregated one back to the clients.
FedAvg:
2. FedProx: This method (Li et al., 2020) is the FL baseline, which prevents the local model from drifting to the local data by minimizing weight differences between local and global models.
3. FedPer: This method (Arivazhagan al., 2019) is the personalized FL baseline, which shares only the base layers, while keeping the personalized classification layers in the local side.
4. FedGNN: This method (Wu et al., 2021 is the subgraph FL. baseline, which expands the local subgraph by exactly augmenting the relevant nodes from other clients. In the original paper, the authors consider the nodes, which have shared neighboring nodes, over two individual clients as the relevant nodes, and then augment them. However, in our non-overlapping node scenario, since nodes are unique across different clients, we measure the similarities between nodes in different clients, and then augment them having the similarity above the threshold (e.g., 0.5).
5. FedSage+: This method (Zhang et al., 2021) is the subgraph FL baseline, which expands the local subgraph by generating additional nodes with the local graph generator. To train the graph generator, it first transmits the local node representations to other clients, and then calculates the gradient of distances between the transmitted node representations and the other client's 's node features. Then, the gradient is sent back to the local client, used to train the graph generator.
6. GCFL: This method (Xie al., 2021) is the graph FL baseline, which targets completely disjoint graphs (e.g., molecular graphs) as in image tasks. In particular, it uses the bi-partitioning scheme, which divides a set of clients into two disjoint client groups based on their gradient similarities. Then, the model weights are only shared between grouped clients having similar gradients, after partitioning. Note that this bartartiti scheme is similar to the scheme proposed in clustered- FL. (Sattler et al., 2020) for image classification, and we adopt this for our subgraph FL..
Local:
This method the non-FL baseline, which only locally trains the model for each client, and does not share any weights between clients.
8. FED-PUB: This is our FEDerated Personalized sUBgraph learning (FED-PUB) framework, which not only estimates the similarity between client subgraphs with their models' functional embeddings for detecting subgraph community structures, but also adaptively masks received weights from the server to filter subgraph-irrelevant weights from heterogeneous communities.
14

---

Under review as a conference paper at ICLR 2023
B.3 IMPLEMENTATION DETAILS
Implementation Details on Functional Embeddings The functional embeddings are key ingre- dients in the proposed FED-PUB framework, to capture community structures of interconnected subgraphs leveraged in personalized weight aggregation (See Section 4.1). To obtain such the func- tional embeddings, the graph input of GNNs is required, which we randomly generate via stochas- tic block model (Holland et al., 1983). Specifically, we first sample five individual subgraphs, each of which has 100 nodes, in which the probability of edges within the single graph is 0.1, while the probability of edges between different graphs is 0.01. Also, we initialize the node features with the normal distribution of 1.0 mean and 1.0 variance. Note that this randomly sampled graph is initial- ized at the server-side at once, and the server distributes it to all clients. Then, the client calculates its model's 's functional embedding. and then transmits only the output embedding to the server.
Implementation Details on Sparse Masks As described in Section 4.2, we propose to sparsify the local personalized mask μ4, for each client i, for taking the benefit in communication and pre- diction costs. In this paragraph, we additionally provide the detailed implementation specifications on sparse masks during training and test phases of our FED-PUB. First, in training, we regularize the local mask j4g to be sparse by minimizing the L1 Norm of it along with its scaling parameter 2 to the local loss C, 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 thresh- old scheme, where elements (neurons) of μ4 below certain threshold (i.c., A2) 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 both communication and prediction costs.
Common Implementation Details for Experiments For all experiments, we stack two layers of Graph Convolutional Network (GCN) (Kipf & Welling, 2017) and one linear classifier layer. Regarding hyperparameters, the number of hidden dimensions is set to 128, and the learning rate is set to 0.001. All models are optimized with Adam optimizer (Kingma & Ba, 2015). Also, all clients participate in FL at every round. For all experiments about our FED-PUB, we set λ and X2 values for L, and L2 losses in equation 5 for sparsity and proximal terms as 0.001. While we can tune such two scaling hyperparameters, we observe that those default values show satisfactory performances across all datasets without specific tuning to each dataset (See Appendix C. for more analyses).
Implementation Details on Synthetic Graph Experiments We perform two experiments on syn- thetic graphs, which are shown in Figure 1 and Figure 3. In particular, in the experiment of Figure 1, there are three communities that have different label distributions (e.g., nodes in the first community have label O, whereas nodes in the last community have label 2), and three communities consist of 5/5/40 non-overlapped subgraphs, with 50 clients. 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 Fig- ure 3, there are two communities that have different label distributions, and two communities have 5/15 non-overlapped subgraphs, with 20 clients. 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 FL rounds is set to 100. In our FED-PER including its variants of using parameter and gradient for subgraph similarity estimation, the scaling hyperparameter (i.e., T) for the similarity in equation 4 is set to 10.
Implementation Details on Real-World Graph Experiments For relatively 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. For larger datasets, such Computer, Photo and arxiv, set the number of total rounds as 200, while the number of local epochs is set to for Photo and arxiv, and set to for Computer. In the overlapping node scenario, we set the similarity scaling hyperparameter (i.e., T) as 5 for all our models. Meanwhile, we set the similarity scaling hyperparameter (i.e., T) as 3 in the non-overlapping node scenario for all our models. We observe that, the larger value performs better for the overlapping node scenario, in which different subgraphs are easily grouped together, compared to the disjoint node scenario. Finally, we report the test performance of all models the best validation epoch, and the performance is measured by the node classification accuracy.
Computing Resources For all experiments, we use PyTorch (Paszke et al., 2019) and PyTorch Geometric (Fey& & Lenssen, 2019) as deep learning libraries. We use two types of GPUs: GeForce
15

---

Under review as a conference paper at ICLR 2023
A
Accuracy [%]]
Sparsity [%]
Ag
Accuracy [%]
Sparsity
3e-1
le.3
79.62
0.23
28.93 1: 0.52
7e-1
le.3
78.68 =: 0.59
$6.94 =: 0.29
5e-1
16-3
79,42
0.37
42.38 0.35
7e-1
le-2
78.56 + 0.08
56.61
0.32
7e-1
le.3
78.68
0.39
56.94 1: 0.29
7e-1
le:1
79.46 1: 0.41
57.41 a: 1.33
96-1
1o:3
77.36
0.99
74.87 0.34
7c-1
1c-0
79.31 = 0.45
57.28 0.16
Figure 10: Analysis on hyperparameters A and A2. with corresponding model sparsity and performance.
RTX 2080 Ti and TITAN XP, for training models. Note that the runtime of our framework also depends the number of workers for processing clients' jobs in parallel. In general, we use 10 or 20 workers (i.e., simultaneously training 10 or 20 local models for 10 or 20 clients), and the single run of our algorithm for 50 clients with local epoch and 100 total rounds takes less than 2 hours.
C ADDITIONAL EXPERIMENTAL RESULTS
In this section, we provide additional experimental results sensitive analysis of hyperparameters in Section C.I: varying graph partitioning schemes in Section C.2 and C.3; varying random graph inputs in Section C.6; and varying similarity estimation schemes in Section C.7. In addition to them, we also analyze the subgraph heterogeneity itself in Section C.4 and its relationship to the graph size in Section C.5, as well the impact of missing edges to the task performance in Section C.9.
C.1 RESULTS ON VARYING THE SCALING HYPERPARAMETERS IN LOss FUNCTION
In Figure 10, we explore the effects of hyperparameters A and Xg on the Cora dataset with the overlapping node scenario, where the number of local epochs is set as 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 d2 value while varying Åι, and then measure both the model sparsity and performance. As shown in Figure 10 left, higher A 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 selecting À value. On the other hand, A2 value is designed to prevent the excessive knowledge drift to the local subgraph distribution, and, fix λ value while varying X2. As shown in Figure 10 right, small
to verify its effectiveness, lambda values lead to the performance degeneration, thus choosing the sufficiently large X2 values (e.g.. le-1) would yield the high performance. Further, we observe that the sparsity does not depend on X2 value, thus the effects of X and X2 are orthogonal and complementary.
C.2 RESULTS ON LOUVAIN GRAPI PARTITIONING ALGORITIIM
To validate our FED-PUB on different graph partitioning set- tings, we use another experimental setup from Zhang et al. (2021), which uses Louvain algorithm (Blondel et al., 2008) for partitioning the entire graph into several subgraphs for FL clients. Before explaining experimental results, we would like point out that there is drawback gorithm presented in Zhang et al. (2021), unlike the METIS algorithm (Karypis, 1997) that we use, for subgraph FL sce- narios. Specifically, since the Louvain algorithm cannot spec- ify the number of graph partitions, the number of subgraphs on the CiteSeer dataset is 38, where three of them have less than ten nodes. Then, based on those 38 disjoint subgraphs, to generate the particular number of clients (e.g.. 10). Zhang et al. (2021) randomly merge the different subgraphs without considering their graph properties. Therefore, even though each partitioned subgraph has its unique structural rolefcharacteristicc. the reconstructed 10 subgraphs from the original 38 subgraphs have mixed properties (i.c., two incompatible subgraphs could be merged), which is suboptimal. However, as described the Datasets paragraph of Section 5.1, the METIS that we use can specify the number of partitions, thus more appropriate for making experimental settings for subgraph FL.
Table 5: Results on experimental set- tings of Louvain graph partitioning al- gorithms, following Zhang et al. (2021).
Local
64.66 0.22
1.39
$4.77 0.17
Faldng
51885 1.400
69:23 (.77
32.43 1..1
the Louvain al-
Fodtoss
72:09 1..20
1..9
82.69 0.34
85022
01.21 16.59
02.0=0036
FedSoger
12:30-1000
08.00=001
=0.0000000
GEEL
10.55
61.20-0.11
00.0=0.11
As shown in Table 5, we conduct experiments with the Louvain graph partitioning algorithm (Blon- del al., 2008: Zhang al., 2021), on Cora, CiteSeer, and PubMed datasets with the number of clients as 10. The results show that our FED-PUB consistently outperforms all the other basclines on the different graph partitioning setting, thus the effectiveness of our FED-PUB becomes obvious.
16

---

Under review as a conference paper at ICLR 2023
C.3 RESULTS ON RANDOM GRAPH PARTITIONING ALGORITHM
One might be curious about experiments on uniform partitions of graphs, instead of splitting the graph with sophisticated par- titioning algorithms (e.g., METIS and Louvain algorithms). Therefore, in this subsection, we explain why this random par- titioning setting is unrealistic, and then show the performances on this random setting. To be specific, if we partition the en- tire graph of the CiteSeer dataset into different subgraphs uni- formly at random, the number of nodes of each subgraph be- comes larger than the number of edges (e.g.. 211 nodes yet 72 edges per subgraph, thus some nodes do not have any edges),
Table 6: Results experimental set- tings of the random graph partitioning.
Methods
CiteSeer with 10 Clients
Local
44,27
FedAvg
60.84 = 0.80
FodPoox
59.38 1.66
FedPer
60.04 0.93
FeeGNN
54.64 1.67
FedSago+
61.03 0.11
GCFL.
53.15 1.82
FED-PUB (Ours)
63.63 :: 0.86
which is uncommon in practice. However, we further perform experiments the random split set- ting with 10 different clients on the CiteSeer dataset, and then report the results in Table 6. As shown in Table 6, the gap between baselines and model is reduced compared to the non-overlapping and overlapping scenarios in Table and Table 2. This is because there is no specific community structure in this random setting; however, our FED-PUB still consistently outperforms all baselines.
C.4 ANALYSES ON DISTRIBUTION SHIFTS BETWERN SURGRAPHS WITH SPARSE MASKS
To see the distributional shifts between subgraphs in our subgraph FL, we measure label differences between subgraphs with the over the overlapping and non-overlapping scenarios. Then, the results show that the distance (i.e., divergence value) among subgraphs within the same community is 0.384 while the distance between subgraphs belonging to different communities is 0.639 for the non-overlapping node scenario. On the other hand, for the overlapping node scenario, the distance among subgraphs within the same community is 0.047 while the distance between subgraphs belonging to different communities is 0.528. Thus, these results confirm that heterogeneity of subgraphs even within the same community is extremely larger in the non-overlapping setup (0.384) compared to the overlapping setup (0.047).
divergence on the Cora dataset with 20 different clients
Then, from the above result, we can further argue that personalized weight aggregation from similar- ity matching is not enough in disjoint subgraph FL problems, since the model weight received from completely heterogeneous subgraphs might not be meaningful to the local subgraph task, especially in the non-overlapping setting. However, in such the extremely heterogeneous case, personalized weight masking scheme is obviously helpful, since it can filter out irrelevant information transmitted from the other heterogeneous subgraphs, while allowing the model to maintain the locally helpful information in its parameters. This result is also aligned with the results in Figure 7 of the abla- tion study that, the personalized weight masking scheme brings huge performance improvements in the non-overlapping setting with high heterogeneity between subgraphs, whereas the personalized weight aggregation scheme is more beneficial in the overlapping setting with low heterogeneity.
Lastly, to directly see the efficacy of sparse masks in subgraph FL, we empirically analyze whether they can indeed filter irrelevant weights received from heterogeneous communities and subgraphs. To do so, measure how many parameters erogeneous) subgraphs, as well as between the two most similar subgraphs, for the Cora dataset with 20 clients on the non-overlapping node setting. For the two most similar subgraphs within the same community, 75% parameters are shared. Meanwhile, for the two heterogeneous subgraphs from two opposite communities, 73% parameters are filtered by sparse masks. These results demonstrate that sparse masks can prevent the knowledge collapse from subgraphs of heterogeneous communities.
shared between the two most dissimilar (i.e., het-
C.5 ANALYSES ON LOCAL GRAPH SIZE VS HETEROGENEITY
To see how much heterogeneity issues are severe in terms of the number of clients, we first analyze the exact amount of heterogeneities with respect to the client numbers. In par- ticular. following the reported statistics in Table 4, when we increase the number of clients in both the overlapping and non-overlapping node scenarios, the heterogeneity across subgraphs becomes severe and problematic for personalized subgraph FI., and thus becomes an important issue to tackle.
Table 7: Results Cora, CiteSeer, and PubMed datasets on non-overlapping see- narios, with the number of clients of 3.
Methods
Coea
UniSeet
PilMes
Local
$1.73 #.44
68 0
84.11 =
RalPaic FedPer
78.01 0.21
04 0:23
85 50 0.18
2.13
00.3
21.36
0.15
RalSagoe
77.20 1.96
60.55
0:12
63.65 0.23
OCPL.
$2.67 0.744
68.85 0..5
96:30 0.15
PED
$4.55 0.225
90.66
0.
17

---

Under review as a conference paper at ICLR 2023
Note that one might be curious about whether our FED-PUB is still effective, when the heterogeneity issue is less significant. Thus, we further conduct the experiment in the setting where the number of clients is 3 on Cora, CiteSeer, and PubMed datasets of the non-overlapping node scenario. As shown in Table 7, compared to the results in Table 2 with client numhers of 5, 10, and 20, the performance gaps between our FED-PUB and baselines are much reduced. However, our FED-PUB consistently outperforms all baselines with large margins even when the number of clients is small, since there still exists incompatible knowledge across clients, which our FED-PUB effectively handles with personalized weight aggregation and local weight masking schemes.
clearly observe that
C.6 RESULTS ON VARYING THE GRAPH INPUTS FOR FUNCTIONAL. EMBEDDINGS
As described in Section B.3, to obtain the functional embed- ding, we use the same random graph for all client models, which is initialized by a stochastic block model (Holland et al., 1983) with node features initialized by the normal distribu- tion. The underlying assumption on using the random graph is that such randomness may not yield any bias on the functional space, unlike existing node features of the particular subgraph. In other words, we expect our random graphs are helpful for effectively capturing the similarities among subgraphs.
Table 8: Results varying the graph inputs for functional embeddings, over overlapping and non-overlapping node scenarios with 20 clients on Cora.
Graphs
Overlapping
Non Overlapping
SBM ER
0.937
0.810
0,920
0.712
One
0,822
0.656
Feature
0.897
0.632
In this subsection, to experimentally validate the above statement, we compare various graph inputs used for calculating the functional embeddings, as follows: 1) SBM denotes the random graph gen- erated by the Stochastic Block Model (SBM) like ours; 2) ER denotes the random graph generated by the Renoi (ER) model (Erdōs & Rényi, 1960); 3) One denotes the random graph having only one node; 4) Feature denotes the graph where node features are initialized by the existing ones in the client. We then measure the performances of those four schemes by calculating the corre- lation coefficient between label distributions and estimated similarities of subgraphs (i.e., the high correlation coefficient means that the estimated similarities from functional embeddings are similar to the actual label distributions) on the Cora dataset of non-overlapping and overlapping node sce- narios with 20 clients, which are reported in Table 8. Specifically, as shown in Table 8, compared to the One scheme that uses only one node for calculating the functional embeddings. SBM and ER schemes that use more large numbers of randomly initialized nodes can accurately capture the similarities between subgraphs. This result demonstrates that sufficient amount of randomness is required to capture the model's functional space. Also, compared to the Feature scheme that uses existing node representations to calculate the functional embeddings, SBM and ER random models show superiority in capturing similarities among subgraphs, which verifies that randomness indeed helps obtain accurate functional embeddings of models without incurring bias.
C.7 RESULTS ON VARYING THE SIMILARITY ESTIMATION SCHEMES
As shown in Figure 3, our functional embeddings are not only effective but also efficient in capturing similarities between subgraphs, compared against using the parameter and gradi- ent similarities. Additionally, while one might consider us- ing the label distributions as the proxy for similarity estima- tion between clients, since labels are private local data stored in the client, this scheme may violate the privacy constraint of FL. However, to see their actual performances in the real- world dataset, we additionally conduct experiments on the pa- rameter, gradient, and label similarities, on the Cora dataset of the overlapping node scenario with the number of clients as 30, and then compare the results with our functional similarities at 20, 40, 60, and 80 rounds.
Table 9: Results on varying the similar- ity calculation schemes: parameter, gra- dient, label, and our functional embed- ding. on the overlapping node scenario with 30 clients of the Cora dataset.
Rounds
Medel
30
40
60
80
Feddug
29.96
32,89
47.84
52.42
Paraneter
20.94
35.89
47.08
52.28
Gradient
33.93
51.09
52.77
58.14
Label
65.97
74.31
76.50
76882
Function (FED-PUB)
67.82
73.51
74.66
75.90
As reported in Table 9, we can observe that the models, which utilize the parameter and gradient for calculating the similarities between subgraphs, show comparable performance to the naive FedAvg model, and inferior than our functional and label similarity schemes. However, even though the label similarity model uses sensiiive local information (i.e., label distributions of every client), the performance of our FED-PUB that utilizes the functional embeddings from the privacy-free random
18

---

Under review as a conference paper at ICLR 2023
Table 10: Results the overlapping node scenario with 10 clients (top) and non-overlapping node scenario with 30 clients (bottom), where we report results with mean and standard deviation over three different runs.
Methods
Cora
CiteSeer
PuhMed
Computer
Photo
obgn arxiv
Overlapping Node Scenario
FED-PUB with Explicit Community
80.45 0.73
69.50 0.20
84.76 2: 0.14
90.31 0.06
92.67 0.08
64.56 0.12
FED-PUB with Implicit Community
81.54 a 0.12
72.35 0.53
86.28 a: 0.18
90.55 = 0.13
92.73 0.18
66.58 2: 0.08
Non-Overlapping Node Scenario
FED PUB with Explicit Community
76.59 a: 0.39
67.57 a: 0,51
83,20 4: 0.45
87.84 a: 0.42
91.26 0.25
61,52 #: 0.06
FED PUB with Implicit Community
75.40 + 0.54
68.33 a 0.45
85.16 a: 0.10
89.15 0.06
92.01 + 0.07
63.34 a 0.12
graph is similar the performance of the label model. Therefore, along with the results in Figure 6, these comparison results on similarity schemes further verify the effectiveness of our functional embedding scheme in capturing the similarities among subgraphs, for identifying their communities.
C.8 ANALYSES ON IMPLICIT AND EXPLICIT COMMUNITIES FOR WEIGHT AGGREGATION
As formalized in Equation 4 and described in Section 4.1, for personalized weight aggregation based on the functional similarities between clients, implicitly model the community structures by performing weight aggregation over all available clients. However, one can alternatively perform explicit weight aggregation, by grouping similar subgraphs within the community first and then per- forming weight aggregation among clients within the community. To see which strategy is superior, we compare the performances of our variants: implicit and explicit community detection for weight aggregation. Note that, for the implicit setup, we use the formulation defined in Equation 4 without any modification. Meanwhile, for the explicit setup, we exclusively perform weight aggregation between clients, having the functional similarity score above 0.5, which we regard as forming the community, with the same normalization trick in Equation 4 after identifying communities.
As shown in Table 10, we observe that the model, which implicitly captures the community struc- tures during weight aggregation, consistently outperforms the other explicit one, except for only one case: Cora with the overlapping node scenario. We believe such the exceptional case the Cora dataset with the overlapping node scenario might be because, the information in the other communi- ties is especially not useful for this particular setup: therefore, completely ignoring them contributes to the improved performance. Except for this, the results in Table 10 confirm that implicit modeling of community structures is generally better for personalized weight aggregation in subgraph FL..
C.9 IMPACTS OF MISSING EDGES TO THE PERFORMANCE DEGENERATION
In this subsection, we empirically demonstrate that, due to the missing edge problem, all FL methods, which observe edges only within each subgraph, show inferior performances than the Oracle method, which trains on the entire graph including missing edges. To validate this claim, we first train the Oracle model on the connected global graph, and then evaluate it on disjoint subgraphs over all clients, on the Cora dataset of both Non-overlappin overlapplg and Overlapping node scenarios with varying the client numbers. As shown in Table 11, the Oracle model outperforms all the other methods, while our FED-PUB achieves the closest performance to the Oracle. The above results bring us to conclude that, due to the problem of missing edges, all FL methods, which trains with edges only within each subgraph, are inferior than the Oracle method. Note that this conclusion further suggests that the missing edge problem negatively affects the incompatible knowledge issue. Specifically, since all client models trained on the partial subgraphs, which are parts of the larger global graph, the trained parame- ters in the client and the aggregated parameters in the server might not capture globally meaningful knowledge the knowledge that is helpful to the other clients, while the Oracle model can capture.
Results on Von-Overlapping and Overlap- ping node scenarios with varying the number of clients on Cora. The Oracle model is not comparable, which trains with the global graph including missing edges.
Table 1I:
Nor-owerlggiing
Overlapping
Model
5 Clients 20 Clients
10 Clients
50 Clients
Oraale
85.07
85,47
85.08
85.28
Local
81,30
73.98
76.63
FedAvg
74.45
69.50
76.48
53.99
FedGNN
81.51
70.10
70.63
56.91
FedSago+
72.97
57.97
77.52
55.48
FEI-PUB (Ours)
83.70
81.75
79.60
77.84
19

---

Under review as a conference paper at ICLR 2023
D DISCUSSION ON 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, generally ap- plicable regardless of subgraph types (e.g., unipartite graphs or bipartite graphs), our experiments are mainly done with unipartite graphs, which are the most popular setups. However, the efficacy of our FED-PUB on the other types of graphs, such as bipartite graphs, would be interesting to investigate, which have but not been explored so far, and we leave this as future work.
Potential Societal Impacts The FL mechanism is important for preserving user's privacy, and, while this mechanism is actively studied in image and language domains, it gets little attention in graphs. However, we believe that work comprehensively investigates and sufficiently tackles unique challenges in subgraph FL, such as missing nodes, edges, and their community structures.
Then, the potential positive impact of work on society is that, ours can contribute various domains that utilize graph-structured data, such as social, recommendation, and patient networks. Note that we would like emphasize the importance our subgraph FL scheme, especially in social and recommendation networks. In the current real-worke application, all user's interactions with other users in social networks and with other products in recommendation networks may be stored in the server. However, this may not preserve the user's privacy, but also has potential risks of user data leakage from the server, such that storing user's s data in the server is not recommended by existing data protection regularizations such as GDPR 3. Then, by applying this domain, we expect such problems could be alleviated by not storing user's interaction data in the server, but only sharing the locally trained machine learning models from client subgraphs.
subgraph FL framework to
However, the transmitted model parameters from the client to the server may hold information. While eliminating it is not the main focus of our work (i.e., assume that model parameters are transmittable without compromising privacy as in many FL works (McMahan et al., 2017: Li et al., 2020; Arivazhagan al., 2019)), the research community may need put further effort on whether the model parameters are safe, and how to make them more safe if they are not.
inups://gdprinfoo.eu
20


Reviews:
[{"review_id": "s7xk0sBQKB", "reviewer": "Reviewer_TrJG", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a personalized method for subgraph learning with multiple clients in different communities. The key idea is to measure the similarity between each customer pair and use that similar information for succeeding updates. Empirical results demonstrate superior performance on test accuracy.", "summary_of_the_review": "This paper proposed a personalized idea for subgraph federated learning. My concern is that the accuracy gain may come from user information leakage. And there is no systematic discussion regarding the privacy-accuracy tradeoff.", "strength_and_weaknesses": "Strengths: \n1. This paper proposes an implicit method to exploit the community structure within the graph using pairwise similarity scores on clients. With this method, we can properly handle missing edges and subgraph heterogeneity with a reasonable performance gain in accuracy.\n\n2. Some implementation refinements, such as masking and regularizations, are applied to achieve better performance.\n\nWeaknesses:\n1. The method may sacrifice the user's privacy by calculating personalized information on the server side. From Equation (4), even though the information among different clients are mixed together on the server's side, there is a chance that personal data can leak since the mixing rule encourages aggregating similar clients. However, the paper needed to articulate the tradeoff between privacy and accuracy.\n\n2. The paper should have explicitly modeled a rigid community structure on the server's side. Instead, it uses an implicit similarity measurement that can potentially measure more complicated structures, such as overlapping communities. However, the empirical analysis needed to show a deeper insight using the similarity structure.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Ns2q9TvM0ht", "reviewer": "Reviewer_jjc2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the non-iid subgraphs of the clients in an FL course and proposes a novel pFL algorithm to tackle this challenge. The idea of measuring subgraph similarity via functional embeddings' similarities is novel, and the adaptive masking is synergistic and seems to be helpful. The authors have conducted extensive empirical studies, which confirms the effectiveness of FED-PUB and the rationale behind its components.", "summary_of_the_review": "This paper is completed and \"standard\". Techniques introduced in this paper are naturally motivated and sound helpful. However, the lack of a rigorous theoretical analysis makes me feel it is still below the bar of ICLR. I strongly encourage the authors to supplement such an indispensable part.", "strength_and_weaknesses": "Strengths:\n1. This paper is well-written, with each figure, table, and paragraph being very self-contained.\n2. The proposed method, FED-PUB, is the first one to exploit the functional embeddings for measuring subgraph similarities. Meanwhile, the authors introduce the client-wise learnable mask to further personalized the GNN models, in addition to the subgraph similarity-based cluster-based pFL aggregation.\n3. The empirical studies in this paper is solid, with SOTA federated graph learning algorithm as a baseline, public datasets, and in-depth analysis from various perspectives.\n\nWeaknesses:\n1. It seems that there is no theoretical analysis about the effect of similarity measure, not to mention the eventual generalization risk. Actually, the relationship between graph data and the model parameters is intricate. Although the similarity in functional space seems to be a reasonable proxy, why it is useful needs to be analyzed and answered.\n2. The masking scheme is not that novel to personalized federated learning. Thus, the technical contribution(s) of this paper seems to be insufficient (only the subgraph similarity measurement).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "9gQWImDH11", "reviewer": "Reviewer_PHC3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Unlike the existing subgraph federated learning methods that overlook the heterogeneity among subgraphs, this paper proposes a personalized subgraph federated learning framework named FED-PUB, which enhances collaborative learning of subgraphs within the same community. To this end, it captures the communities based on functional embeddings of clients, then employs personalized sparse masks on the local GNN. Empirical results on six public datasets demonstrate the effectiveness of the proposed method. ", "summary_of_the_review": "Due to the limited technical novelty and misleading descriptions of related works, I recommend reject.", "strength_and_weaknesses": "Pros:\n\tThe motivation of this paper, i.e., considering the heterogeneity among subgraphs in the subgraph federated learning, is reasonable and has rarely been explored.\n\tThe ideas are technically sound.\n\tExtensive experiments show the superiority of the proposed method compared to other subgraph federated learning methods.\n\nCons:\na)  The idea that performs subgraph federated learning among similar subgraphs is relatively incremental, limiting this paper's novelty.\nb)  Some notations are confusing such as θ vs θ_i on page 4.\nc)  The functional embeddings are key ingredients in the proposed FED-PUB, and the authors utilize a randomly sampled graph as the input of GNNs at each client. However, the influence of different random graphs is missing.\nd)  At the beginning of model training, the functional embeddings derived from each client may not be accurate, resulting in the inaccurate grouping of communities. How does the proposed method deal with this situation?\ne)  The description of baselines is incorrect. For example, FedPerGNN/FedGNN actually introduces a trusted third-party server to augment subgraphs, rather than based on the similarity between the nodes in the local client and the nodes in other clients. Furthermore, FedGNN is a method based on heterogeneous user-item bipartite graphs, and it is unclear how the authors apply it to homogeneous graphs (e.g., Cora). Therefore, it is better to provide a detailed description of experimental settings.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject