Personalized Subgraph Federated Learning
Authors: Jinheon Baek
Wonyong Jeong
Jiongdao Jin
Jaehong Yoon
Sung Ju Hwang
Venue: NeurIPS 2022 Submitted (2022)
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 parts of a global graph. For example, a subgraph may belong to one of the communities within the larger global graph. A naive subgraph FL in such a case will collapse incompatible knowledge from local GNN models trained on heterogeneous graph distributions. To overcome such a limitation, we introduce a new subgraph FL problem, personalized subgraph FL, which focuses on the joint improvement of the interrelated local GNN models rather than learning a single global GNN model, and propose a novel framework, FEDerated Personalized sUBgraph learning (FED-PUB), to tackle it. A crucial challenge in personalized subgraph FL is that the server does not know which subgraph each client has. FED-PUB thus utilizes functional embeddings of the local GNNs using random graphs as inputs to compute similarities between them, and use them to perform weighted averaging for server-side aggregation. Further, it learns a personalized sparse mask at each client to select and update only the subgraph-relevant subset of the aggregated parameters. We validate FED-PUB for its subgraph FL performance on six datasets, considering both non-overlapping and overlapping subgraphs, on which ours largely outperforms relevant baselines.

A graph, which defines the relationships among instances, model wide range of structured data 25 including social [7], co-purchasing [23], and collaboration networks [36]. Most the previous works on graph representation learning focus single graph, whose nodes and edges collected from Personalized Subgraph Federated Learning
Anonymous Author(s)
Affiliation Address
email
Abstract
real-world scenarios, subgraphs larger global graph may be distributed across multiple devices institutions, and only locally accessible due to privacy strictions, although there may be links between them. Recently proposed subgraph Federated Learning (FL) methods deal with those missing links across private local subgraphs while distributively training Graph Neural Networks (GNNs) on them. However, they have overlooked the inevitable heterogeneity among subgraphs, caused by subgraphs comprising different parts of a global graph. For example, subgraph may belong
3
5
of the communities within the larger global graph. A naive subgraph FL in such case will collapse incompatible knowledge from local GNN models trained on heterogeneous graph distributions. To overcome such a limitation, we introduce a new subgraph FL problem, personalized subgraph FL, which focuses on the joint improvement of the interrelated local GNN models rather than learning a single global GNN model, and propose a novel framework, FEDerated Personalized s 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 personalized sparse mask 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.
10
11
12
13
14
15
16
17
18
20
21
22
Introduction
23
27 multiple sources are stored in a central server. For instance, social network platform, every user, with his/her social networks, contributes creating giant network consisting of all users and their connections. However, in some practical scenarios, each user/institution collects its own private graph, 30 which is only locally accessible due privacy restrictions. For instance, as described in Zhang et al.
29
31 [45], each hospital may have its own patient interaction network to track their physical contacts or
32 co-diagnosis of a disease, however, such graph may not be shared with others. An obvious challenge
33 for such scenario is how to deal with potentially missing edges between subgraphs [42, 45] that are captured by individual data owners, that may carry important information (See Figure (A)).
34
35 How can we then collaboratively train, without sharing actual data, a neural network with its subgraphs distributed across multiple participants (i.e., clients) different devices institutions? The most straightforward way is to perform Federated Learning (FL) with Graph Neural Networks (GNNs). In particular, in such an FL framework, each client will individually train local GNN on the private
37
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

Rensite en Syzihatt Gragha
Commanndy Beaclt
Community
Communby
Knowledge
Communty&&
Community 8
3
CHEZ e Cree CIec
Local AARLAAY 2911
Subgrrohh
Suhgrapa Exparaion
Caluboration
User
Community Structuro
Existing Subgraph
(C) Parsonalized Subgraph
Commanzettoo Souads
Local Accorac (66)
Figure 1: (A) An illustration of local subgraphs distributed across multiple participants with overlapping
nodes, missing edges and community structures hetween subgraphs. (B) Existing subgraph FL. methods [42, 45] expand the local subgraphs to tackle the missing edge problem, but collapse incompatible knowledge from heterogencous subgraphs. (C) Our personalized subgraph FL focuses the joint improvement of local models working on interrelated subgraphs, such as ones within the same community, by selectively sharing knowledge across them. (Right:) Knowledge collapse results. where local models belonging to two small communities (Comm 1 and 2) suffer from large performance degeneration by existing subgraph FL (e.g.. FedGNN [42] and FedSage+ [45]), A personalized FL method, FedPer [2] also underperforms ours since only focuses on individual model's improvement without sharing local personalization layers between similar subgraphs.
39 local data, while a central server aggregates the locally updated GNN weights from multiple clients
40 into one, and then transmits it back to the clients. Recent subgraph FL methods work in such manner [42, 45] while additionally tackling the problem of missing edges between subgraphs. This is done as illustrated in Figure 1 (B), where the local subgraph is expanded either by exactly augmenting the relevant nodes from the other subgraphs at the other clients [42], or by estimating the nodes using
41
42
43
44 the node information in the other subgraphs [45]. However, such sharing of node information may compromise data privacy and can incur high communication costs.
45
Also, there exists more important challenge that has been overlooked by the existing subgraph FL methods. We observe that they suffer from large performance degeneration (See Figure right), due
47
48 lack of consideration of the heterogeneity among the subgraphs, which is natural since subgraphs comprise different parts of a global graph. Notably, there could be multiple communities within
49
50 global graph, each of which is formed by a group of densely connected subgraphs with similar
51 characteristics (Figure (A)). For example, some of patient networks from hospitals can be grouped
52 by their specialized sectors according to the discase categories, namely psychiatric or ophthalmology.
53 Motivated by this challenge, we introduce a novel problem of personalized subgraph FL, whose goal
54 the joint improvement of interrelated local models trained on the interconnected local subgraphs,
55 for instance, subgraphs belonging to the same community (See Figure/ (C)), by sharing weights among them. However, tackling personalized subgraph FL is challenging. since we do not know which subgraph each client has, due to their local accessibility. To resolve this issue, we use functional embeddings of GNNs on random graphs to obtain similarity scores between two local GNNs, inspired by a work for neural network search that effectively represents entire neural networks in the vector space [17], and then use them perform weighted averaging of the model weights at the server.
57
58
59
60
61 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
82
63 on the local GNN at each client to obtain only the subnetwork, relevant for the local subgraph. We refer to this subgraph FL framework as FEDerated Personalized s sUBgraph learning (FED-PUB).
64
65 We extensively validate our FED-PUB on six different datasets with varying numbers of clients, under both overlapping and disjoint subgraph FL scenarios. The experimental results show that ours significantly outperforms relevant baselines. Further analysis shows that our method can discover community structures among subgraphs, and the subgraph-specifie masking localizes the knowledge with respect to subgraphs belonging to each community. Our main contributions are as follows:
87
88
69
70 We introduce a novel problem of personalized subgraph FL, which aims at collaborative improve- ments of the related local models (e.g. subgraphs belonging to the same community), which has been relatively overlooked by previous works on graph and subgraph FI..
71
72
73 We propose a novel framework for personalized subgraph FI., which performs weighted averaging
74 of the local model parameters based their functional similarities obtained without accessing the
75 data, and learns sparse masks to select only the relevant subnetworks for the given subgraphs.
76 We validate our personalized subgraph FL framework on six real-world datasets under two different settings, demonstrating its effectiveness over existing subgraph FL basclines.

---

78 2 Related Work
79
Graph Neural Networks Graph representation learning with Graph Neural Networks (GNNs) [10.
80
48, 43, 18, 31, which aims to learn the representations of the nodes, the edges, and the entire graph, is
81
an extensively studied topic. Most existing GNNs under the message passing scheme [8] iteratively represent a node by aggregating features from its neighboring nodes as well as itself. For exam- ple, Graph Convolutional Network (GCN) [22] approximates the spectral graph convolutions [12], yielding a mean aggregation over neighboring nodes. Similarly, for each node, GraphSAGE [11] aggregates the features from its neighbors to update the node representation. Such advances in GNNs node and link prediction tasks [22, 47]. However, they are not directly
85
84
85
86
have led to successes 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 train GNNs.
87
88
89
Federated Learning Federated Learning (FL) [32, 41, 19, 24], aiming to learn a model by aggregat- ing model weights trained on local data, is an essential approach for our distributed subgraph learning problem. To mention a few, FedAvg [32] locally trains a model for each client and then transmits the trained model to a server, while the server aggregates the model weights from local clients and then sends the aggregated model back to them. However, since the locally collected data from different clients may largely vary, heferogeneity is crucial issue. To tackle this, FedProx [25] proposes the regularization term that minimizes the weight differences between local and global models, which prevents the model from diverging by overfitting to the local training data. However, when the local data is extremely heterogencous, it is more appropriate to collaboratielly train a personalized model for each client rather than learning a single global model [2. 30, 26, 46, 6]. FedPer [2] is such a personalized FL method, which shares only the base layers while having local personalized layers for each client, to keep the local knowledge. Unlike the commonly studied image and text data, strputttuucture data is defined by connections between instances, and consequently introduces additional challenges: missing edges and shared nodes between private subgraphs. Note that, re- garding architectures, there is literature [29, 27, 38, 49] that leverages outputs of neural networks for predictin//miniiizing outputs across different client models; however, we use functional outputs of neural networks to identify interconnected subgraphs, thus ours differs from them methodologically.
90
91
93
94
85
96
97
98
99
100
101
102
103
104
105
106
Graph Federated Learning Few recent studies propose to use the FL framework to collaboratively train GNNs without sharing graph data [13]. which can be broadly classified into subgraph- and graph-level methods. Graph-level FL methods assume that different clients have completely disjoint graphs (c.g., molecular graphs), and recent works [44, 14] focus on the heterogeneity among non-III graphs (i.c., difference in graph labels across various clients). In contrast to graph-level FL methods that have similar challenges to general FL scenarios, the subgraph-leve FL. problem we target has a unique graph-structural challenge, that there exist missing yet probable links between subgraphs, since subgraph is part of a larger global graph. To deal with such a missing link problem among subgraphs, existing methods [42, 45] augment the nodes by requesting the node information in the other subgraphs, and then connecting the existing nodes with the augmented ones. However, this scheme could compromise data privacy constraints, and also increases communication overhead across clients. Unlike existing subgraph FL that focuses the problem of missing links, our subgraph FL method tackles the problem with completely different perspective, focusing on discovering subgraph communities [35, 9, 34], which are groups of densely connected subgraphs.
107
108
110
112
113
114
115
116
117
118
119
3 Personalized Subgraph Federated Learning
120
We provide the general descriptions of Graph Neural Networks (GNNs) and Federated Learning (FL), and then define our novel problem of personalized subgraph FL lying at the intersection of them.
122
123
Graph Neural Networks A graph 9 = (V,E) consists of a set of nodes V with n elements and a set of edges& with m elements along with its node feature matrix X E IR where each column represents d-dimensional feature for each node. Further, (u, v) e E represents an edge from node
124
125
126
u to a node v. Then, given the graph, Graph Neural Networks (GNNs) [8, 10] generally represent each node based on features from its neighbors as well as itself, formally defined as follows:
H (+1)- = (PDATE (1) (H, (H,)), AGGREGATE ( ({ (H :
Vu E N())))))
(I)
where ("(") is the feature matrix for node u at 1-th layer, (v()) denotes a set of adjacent nodes of node 2: (o) fu E V (u, v) E E}, AGGREGATE aggregates the features of v's neighbors, and UPDATE updates the node v's representation given its previous representation and the aggregated representations from the neighbors. (!) is initialized as input node features X.
128
130
131
3

---

132
Federated Learning The objective of Federated Learning (FL) is to collaboratively train a model with local private data. Let assume that we have K participants with locally collected data that not accessible from others: DE= = ( ; Yi 1;=1 where X; is data instance, yi is its corresponding class label, and N& is the number of data instances at k-th client. Then, for decentralized training with local data, a popular FL algorithm, FedAvg [32], works as the following three steps:
133
134
135
136
137
(nitializationn 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
138
0, represented as follows: % 0²0) Vk, where 0 is the parameters for k-th client.
139
140
2.
(Local Updates) Each active local model performs training on private local data D2 to minimize
the task loss (D2;; 0()), ) consequently updating the parameters 0 + 0 v/V.C
141
142
3. (Global Aggregation) After local training, the server aggregates the locally learned knowledge
with respect the number of training instances, i.e., T()) N Σド= 0g with N E. Nk.
143
and distributes the updated global parameters T¹)) to the local clients selected the next round.
144
145
This FL. algorithm iterates between Step 2 and until reaching the final round R.
146
Challenges in Subgraph FL While the above FL works well on image and text data, due the
147
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 from the other images, each node v in a graph is always influenced by its relationships to adjacent nodes (v). Moreover, a local graph G; could be subgraph of larger global graph G: G, S G. In such a case, there could be missing edges between local subgraphs in two different clients: (u, v) with u E V; and v E V for clients and j. respectively. To tackle this missing edge problem. few existing subgraph FL methods [42, 45] estimate the nodes from a local subgraph G based on the node information from the subgraphs at other clients G, Vi A k. and then extend the existing nodes with the estimated ones. However, this augmentation scheme incurs high communication costs as it requires sharing node information across clients, which may also violate data privacy constraints [1].
148
149
150
151
152
153
154
155
156
157
Yet, there exists another issue that makes subgraph FL even more challenging. Assume that we have a global graph consisting of all the subgraphs. Then, there exists communities of such subgraphs [35,
158
159
9. 34], where subgraphs within the same community are more densely connected to each other
160
than subgraphs outside the community. Formally, a global graph G can be decomposed into T
161
different communities: C, S G vi = -..... T. where i-th community C. = (V,, E consists of densely connected nodes. Then, in a subgraph FL problem, each client has a local subgraph G, that belongs to at least a single community": : C. = U Gj. Note that, based on the theory of network homophily [33], such connected subgraphs within the same community have similar properties, while subgraphs in two opposite communities are not. Such distributional heterogeneity across communities may lead a naive FL. algorithm to collapse incompatible knowledge across different communities.
162
163
164
165
186
167
Personalized Subgraph FL To prevent the above knowledge collapse issue, we aim to personalize the subgraph FL algorithm by performing weighted averaging of the local model parameters at the server, rather than learning a single set of global parameters; thereby capturing the subgraph community structures among interrelated subgraphs. Formally, the objective of existing subgraph FL [42, 45, 28] is as follows: ming Ea,gg L(G,;)) However, a major drawback of such scheme is that, since the subgraphs in two different communities with sparse connections are extremely heterogeneous due to network homophily [33], finding a universal set of parameters (i.e., 0) that work on all tasks will result in finding suboptimal parameter set. To address such limitations of existing subgraph FL, we formulate a novel problem of personalized subgraph FL, formalized as follows:
188
189
170
171
172
173
174
175
min.o.) Ea.g ((G 0, + E any0, with 0ak >> ast for G2 S C and Gj g C, (2)
K
176
where 0: is the weight for subgraph G; belonging to community C, and oi is the coefficient for weight aggregation which will specify in Section 1. This formulation promotes the collaborative learning across multiple local models that work on the interrelated subgraphs that belong to the same community, by assigning larger weights on them.
177
178
179
For simplicity, we assume that a subgraph belongs to only a single community, however, the formulation does not change even when subgraph can belong multiple communities.

---

Community
Model
0,
Community
Random Graphs.
User
Subgraph
Model 2
fiz
0g
High Simiantyy
Nodel
0g
TIG. 8c
(A) Community Structure
(B) Subgraph Similarity Matching in Server
(C) Weight Masking in Client
Figure 2: (A) Two communities, each of which consists of one/two subgraphs. (B) Client Similarity Matching: we forward randomly generated graphs models f(G; 0). and then obtain the functional embeddings of them h. which are then used to estimate the similarities between subgraphs. The similarities are used in the weight aggregation, resulting in the personalized model weights 0. (C) Weight Masking: the transmitted weights from the server clients are masked and shifted by local masks for localization to the local subgraph distribution.
4
Federated Personalized Subgraph Learning (FED-PUB) Framework
180
Our goal of personalized subgraph FL is jointly improve the local models trained the inter- connected local subgraphs forming the community structures. To this end, we propose to compute subgraph similarity scores for detecting communities, and to mask subgraph-irrelevan weights.
182
189
184
4.1
Subgraph Similarity Estimation for Detecting Subgraph Community
We aim to reflect the community structure consisting of a group of densely connected subgraphs, by sharing more weights among subgraphs in the same community, as formalized in equation 2. Due to network homophily where similar instances in the graph are more associated with each other [33], the subgraphs within the same community should have similar properties. Therefore, one can measure the subgraph similarities, we can group the similar ones into the community. However, measuring the similarity between local subgraphs is challenging since we do not know which subgraph each client has due local accessibility. How can then compute subgraph similarities, without accessing them? To this end, we aim to approximate the subgraph similarity at local clients using auxiliary information obtained from the local GNN models that work on the subgraphs.
186
188
190
192
193
194
Subgraph Similarity Estimation with Model Parameters For measuring the similarity between subgraphs at each client, without accessing them, we may use the model parameters as proxies, as follows: 5i, = (0, f/) e[| II||;; (I) where 0 is flattened pa- rameter into the vector, and is similarity measure. This may sound reasonable since the GNN model trained on the subgraph will
195
196
197
198
Time (Seec)
200
embed its knowledge into its parameters. However, this scheme has
notable drawhack that similarity measured in the high-dimension parameter space is not meaningful due to the curse of dimension- ality [4], and that the cost of calculating the similarity between parameters grows rapidly as the model size increases (See Figure 3).
12
512
1004
2046
202
of Hidden Dimensions
Figure 3: Effectiveness (top) and efficiencies (bottom) of different similarity measurements.
204
205
Subgraph Similarity Estimation with Functional Embedding To tackle the limitations of using parameter distance, we propose to measure the functional similarity of neural networks by feeding the same input to every local client and then calculating the similarities using their outputs, inspired by a work for neural network search [17]. The main intuition is that we can consider the transformation
206
207
208
209
defined with neural network as a function, and we measure the functional similarity of two networks
210
by the distance of their outputs for the same input. However, unlike the previous work [17] that tackles image classification, which uses Gaussian noises as inputs, we use random graphs as inputs
211
as we work with GNNs. Formally, let G = (²,, 8) be a random community graph obtained from a stochastic block model [15], where subgraphs within the community have more edges between them
212
213
than edges across the communities. Further, 1 is randomly initialized from the normal distribution. Then, the similarity between two functions defined by GNNs at clients and j is defined as follows:
214
215
h h
S(i
h Af 0.)) and h, AVG(f((::
(3)
where h is the averaged output of all node embeddings for input & with AVG operation to reduce the dimensionality of the output from x d to d, for n nodes with d-dimensional node features.
216
5

---

218
Personalized Weight Aggregation based on Subgraph Similarity With equation 3, the remaining step then to share the model weights between models working on similar subgraphs belonging to the same community. However, entirely ignoring the model parameters from different communities may result in exploiting only the local objective while ignoring globally useful weights, which may result in performance degeneration. Therefore, we perform weighted averaging of all the local models from the other clients based on their functional (subgraph) similarities, as follows (Figure 2 (B)):
219
221
222
223
exp(T ((i.))) 0. E, aij Oz. az En exp(T -S(, k))
(4)
224
where Ouj is a normalized similarity between clients i and j. and is a hyperparameter for scaling the unnormalized similarity score. Note that increasing the value of r (e.g., 10) will result in model averaging done almost exclusively among subgraphs detected as belonging to the same community.
225
226
This personalized scheme handles two challenges in subgraph FL. First, in contrast to the global weight aggregation scheme which easily collapses the knowledge from heterogeneous communities into a single model, our subgraph FL allows the models belonging to different communities to obtain model weights that are beneficial for each community. Also, the missing edges between subgraphs that have been explicitly handled by previous works [42, 45] could be also implicitly considered by assigning larger weights to models within the same community (See Figure 10). This also enhances data privacy while minimizing the communication costs between probably linked subgraphs.
228
230
232
238
234
4.2
Adaptive Weight Masking for Selecting Subgraph-Relene Relevann Parameters
235
With the previous similarity matching scheme, we can effectively group GNN models that belong to the same community, thus preventing the collapsing of irelevant 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 scheme to select only the relevant parameters from the aggregated model weights transmitted from the server.
237
239
240
Personalized Parameter Masking We perform selective training and updating of the aggregated parameters by modulating and shifting them, using sparse local masks. Formally, let μ4 be local mask for client k. Then, our local model weight is obtained by modulating the weights from the server, as follows: O₂ = Og O Pt where @ is an element-wise multiplication operation between the globally given weight 0% and the local mask fxx Note that the local mask is a free variable and is not shared across clients. Also, we initialize Mr as ones, in order to start training with the globally initialized model parameters without modification. We then further promote sparsity
241
243
245
247
the mask, which brings two key advantages. First, we can transmit only the partial parameters, that have not been sparsified at the client the server rather than sending all parameters, thus reducing the communication costs. Moreover, if local masks are sufficiently sparse, the local models can be trained faster, given that zero-skipping operations are supported (Figure 2 (C)). To take these benefits in sparsity, we use L regularizer on #4 when performing local optimization, as shown in equation 5.
249
250
251
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. [25] that regularizes the locally updated models 02 to be closer to the globally given model 0g. therefore, preventing the model from extremely drifting to the local training distribution. To sum up. at k-th client, our objective function including sparsity and proximal terms with L1 and L2 losses is denoted as follows:
253
255
257
min nu L(Dx; 0x m4) + A1ll + A 0 0x112.
(5)
258
where L is the conventional cross-entropy loss function, and a and \ are scaling hyper-parameters.
5
Experiments
260
We now experimentally validate our FED-PUB on six different datasets under both the overlapping and disjoint subgraph scenarios with varying client numbers, with node classification tasks.
262
5.1
Experimental Setups
Datasets Following the setup from Zhang et al. [45], we construct the distributed subgraphs from the benchmark dataset by dividing it into the number of participants, each of which has a subgraph that is a part of an original graph. Specifically, use six datasets: Cora, SiteSeer, Pubmed and
264

---

Implementation Details We set the GCN [22] with two layers as the base GNN for all models. We perform federated learning 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 21, 3) depending on the dataset size (c.g.. Computer is three while CiteSeer is ? We use the Adam optimizer [21] for model optimization. Table I: Results on the overlapping node scenario. The reported results are mean and standard deviation over three different runs. Only the statistically significant performances
0.05) are highlighted in bold.
Cora
CiteSeer
Puhmed
Methods
10 Clients
36 Clients
50 Clients
10 Client
3a Clients
50 Clients
1B Cheents
30 Clients
50 Clients
Loual
73.08 0.25
71 0.12
75.63 2
0.08
64.54 0.42
56.68 = 11.4
0.16
50.54 0L11
Peddog
76.48 0.36
53.99
4: 4.53
69:43
0.15
66.15
0.64
66.51
1.00
82.67
0.11
$2.05
0.12
50.24
0.35
PedProx
2:550-0000
51.38 2 1.74
26.27
4: 9.04
69:39
0.35
06.11
0.75
66.53
0.45
53.63
0.17
52.03
0.13
50.50
2: 0.45
Fallerr
mo
0.10
78.34 0.26
7341
7663
0.39
64.92
0.18
50.77
0.12
51.36
POIINN
2:335
26.91
4 0.82
08:72
4:030
59
08
1522
58.98
0.58
$4.25
0477
52,62 0.22
$1.35
2: 0.10
FolSage+
77.52.00..0
$1.99
1
68.75
65:97
0.02
61.91
0.90
00.11
0.64
PUB (wrs)
79.60 0.11
75.40 0.54
77.84
70.55 0.20
68.33 0.45
69.21
86.70
85.36 0.10
54.44 0.12
Canson-Cumpterr
AmaressPlute
ogbu-arsh
Methods
Clients
30 Clients
Clients
Clients
30 Clients
Clients
Clients
30 Cleents
50 Clients
Local
$8.50 0:330
36 g: 0:00
87.4
0:00
97.17 0:122
10.16 = 0.12
90:42 = 0.15
67.50 = 0.07
61.32 = 0.04
60.06 :: 0.04
76.72
FalAsy
0.19
76.
0.67
14.10
75.35
89.17
0.40
59.56
0.16
TedPer
89.31 11 0:04
XT 10
1 0:25
22 3 0:27
02.88
3 0:24
91 21
0.16
90.92
0.38
83.97
0.0%
02:29
0.04
01.26 8- 0.11
78.42
87 34 0:00
0:10
0.11
0.08
FAIGIN
18:15:2000 0.00
87.01
78.90
0.04
60.51
FedSage+
39:24 0.15
81
1: 1,20
76.72
a 0.79
92.70
88.09
0.99
72.41
1.36
10.24
0.02
59,50
0.12
00.95
1 0.09
73.12
FED PUB (Duss)
39.98 &: 0.08
39.15 J: 0.00
88.76 3 0.14
93.23 1 0,07
92.01 =: 0.07
91.71 = 0.11
64.18
0.04
63.34
0.12
62.55 21 0.12
79.55
(a) Cora
(b) CiteScer
(c) Pubmed
(d) Computer
(c) Photo
( ogbn-arxiv
Figure 4: Convergence plots for the overlapping node scenario. We visualize the test accuracy curves for all
six datascts corresponding to Table 1, over 100 communication rounds with 10 clients.
266
ogbn-arxiv for citation graphs [39, 16]; Computer and Photo for product graphs [31, 40). We then divide the original graph into multiple subgraphs using the METIS graph partitioning algorithm [20]. Note that, unlike the Louvain algorithm [5] presented in Zhang et al. [45] 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, thus making more reasonable experimental settings in subgraph FL (See Section C.2 of the supplementary file).
267
268
269
270
271
272
For the ove-ollllapinng scenario where there are no duplicate nodes between subgraphs, we use the output from the METIS as it provides the non-overlapping partitions. Mcanwhile, for the overlapping scenario where nodes are duplicated among subgraphs, we randomly sample the subgraphs multiple times from the partitioned graph. For more details, please see Section B of the supplementary file.
273
274
275
Baselines 1) FedAvg [32] and 2) FedProx [25]: The most popular FL baselines. 3) FedPer [2]: A
277
personalized FL baseline without sharing personalized layers. 4) FedGNN [42] and 5) FedSage+ [45]:
Subgraph FL baselines which we mainly target. 6) GCFL [44]: A graph FL baseline which learns completely disjoint graphs as in clustered FL [37], adopted for subgraph FL. 7) Local: A baseline
279
without sharing weights with other clients. 8) FED-PUB: Our personalized subgraph FL including subgraph similarity matching and weight masking. See Section B of the supplementary file for details.
281
282
283
284
285
286
287
We then measure the node classification accuracy on subgraphs at the client-side, and then average the performance across clients. We provide further details in Section B of the supplementary file.
288
289
5.2
Experimental Results
290
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 basclines including FedPer and GCFL show decent performance by alleviating the knowledge collapse between subgraphs with local parameters or clustering, they still largely underperform ours as they are not concerned with the aggregation between similar subgraphs that form community (i.e., GCFL uses a bi partitioning scheme where it iteratively divides a group of subgraphs within the same community
292
293
284
285
296
297
298
299
300
We found communication rounds and local epochs are important factors prevent overfitting of all models.
7

---

Table 2: Results on the non-overlapping node scenario. The reported results are mean and standard deviation over three different runs. Only the statistically significant performances (p 0.05) arc highlighted in bold.
Cora
CiteSeer
Pubmed
Methods
5 Clients
16 Clients
20 Clients
Clients
16 Clients
24 Chients
Cllenns
Chennt
2B Clients
Loual
51 0.21
70.44
0:24
a
0.05
67.82 0.13
65.00 =
54.04
$2.81 0.39
$2.65 0.03
Peddig
74,45 5.64
69.19 1:
69:50 4:
71.05
0.60
62,61
3.59
64.68
1.85
79.40
0.11
52.71
0.29
50.57
0.25
PedProx
72.05 4.56
60.15 4 7.04
45 4 6.31
71:73
1:11
03.33
3.25
64.85
1.25
70.45
0.25
52.55
0.34
50.50
2 0.25
Folleer
0.40
6:333
56-64
76.66
70.54
1:057
08.01
0.12
54.18
0.19
53.94
0.36
POIINN
11.51:00.00 0.08
70.12
4 0.99
70.10
4:322
69:00-2:00
55.52
3.37
52.23
6.60
79.52
022
53:25 0.65
$1.61
2: 0.59
FolSage+
72.97
6903
97
0.69
03.61
3:00
61:46
0.74
79.57
80.82
PUB (wrs)
$3.70::0.01
81.75 61.54
0.36
0:44
72.35 0.53
67.62
86.79
$6.28 0.15
55.53 a 0.30
Amazon-Cuppen Computer
AmaressPlute
ogbu-arsh
Methods
Clients
10 Clients
Clients
Clients
10 Clients
Clients
Clients
10 CBents
20 Clients
Local
22 0:11
86.1 0:17
N9
51 it 0:30
91.67
a 0:009
91.00 :: 0.02
90:47 = 0.15
16.76 = 0.07
54.92
0.00
68 1: 0.05
19.57
FallAy
89.89:5
3.71
1:27
83.81
1.00
1.30
80.02
K3.32
64.37
0.15
63.05
TedPer
6967 0.54
89
1 000
8798 1 0:43
01.64
2: 6:37
91 01:20-0
0:25
90:99
0,86
56.87
0.05
54.99
0.15
56.66 1- 0.11
19.93
5.0.6
+
0:29
0:35
90.70
65.08
70.00
FAIGIN
88.18
87.13
FedSage+
15.04 0.00
80.50-1
1:001:10 1
70:42
a 0.55
90.77
2 0.44
70.81
8:24
50.58
1.15
10:00
0.09
64.52
0.14
03:31 1: 0.20
73.47
FED PUB (Dus)
90.74 1: 0.05
90.55 J: 0.13
90.12 1 0.09
93.29 0.19
92.73 =2 0.18
91.92
0.12
67.77
0.09
66.58 = 0.05
66.64 1: 0.12
$1.59
Cora
(b) CiteSeer
Pubmed
Computer
Photo
(1 ogbn-arxiv
Figure 5: Convergence plots for the non-overlapping node scenario. We visualize the test accuracy curves for
all six datasets corresponding to Table 2. over 100 communication rounds with 10 clients.
into two disjoint sets). We then further conduct the experiments on the disjoint subgraph scenarios overlaparg 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.
302
304
Fast Local Convergence As shown in Figure 4 and 5, our FED-PUB converges rapidly, compared against baselines including personalized FL models. We conjecture that this is because, not only ours accurately identifies subgraphs forming the community and then shares weights largely across them weights received
306
307
308
for promoting the joint improvement of them, but also masking subgraph-irrelewe from the server for localization local subgraphs, demonstrated in the next two paragraphs.
309
310
Accurate Community Detection We aim to show whether FED-PUB accurately groups subgraphs comprising community during weight aggregation. If two different subgraphs have many missing edges or have similar label distributions, we usually regard those two as within the same commu- nity [35, 9, 34]. Thereby, as shown in Figure 6 (a) and (b), there are four different communities by the interval of five, and the last two communities further comprise a larger community. Then, as shown in Figure 6 (c) and (d), FED-PUB detects obvious four communities at the first few rounds, and then captures the larger yet somewhat less-obvious community consisting of two smaller communities.
311
312
313
314
315
316
317
Ablation Study To analyze the contribution of each component, we conduct the ablation studies. As shown in Figure 7, we observe that each of our subgraph similarity matching and weight masking significantly improves the performances from the naive FedAvg, while the performance is much improved when using both together. However, the benefit from each component is different across overlapping and non-overlapping scenarios. In particular, in the former scenario where a group of highly overlapped subgraphs usually comprise community, similarity matching for community detection is more beneficial since capturing the community would promote the joint improvement of subgraphs belonging to the same community. However, in the non-overlapping scenarios, subgraphs within the same community become lesser similar, thus selectively using the aggregated model weights from the server with personalized weight masks improves the performance lot.
318
319
321
322
323
325
326
327
Communication Efficiency Another notable advantage of using the sparse masks is that we can reduce the communication costs at every FL round, as well as the model size for faster training, which we demonstrate in Table 8. In particular, Table 8 shows that existing subgraph FL methods require more than two times larger communications costs, measured by adding both the client-to-serve and server-to-dee cerver-to-client costs, compared against the naive FedAvg, since they require to transfer additional node information between clients for estimating the probable nodes on the subgraphs. Contrarily, our
328
329
330
331
332
333
FED-PUB has significantly lower communication costs and lower model sizes by using the sparse
334
masks on the model weights: transmitting and training with only the partial parameters not sparsified
325
at the client. Further, as shown in ours variants in Table 8, we can manage the trade-off between the
336
model sparsity and the performance by controlling the hyperparameter for sparsity regularization, A
8

---

Rewalt Duea 2e
Rocale en Oun clood
Cieents
Clesnta
Cieente
Chests
Citent
Clentt
Chents
Cottunication Rounds
Communtiotion Reunds
(a) Missing edges
(b) Label similarity
(c) Round 5
(d) Round at 30
Overlapping
(b) Non-overlapiing
Figure 6: The heatmaps of the community structure on the overlap- ping node scenario with Cora (20 clients). Dark color indicates lots of missing edges between subgraphs (a) or high similarities labels
Figure 7: Ablation studies of our FED- PUB both the overlapping (a) and non- overlapping (b) subgraph scenarios, on
(b). (c) and (d) are functional similarities captured by our FED-PUB. the Cora dataset.
Performance on Pubmed (20 Cilento)
Performance arste Clents)
Medel
Acc. [%c
Model Size [%]
Cost|:]
Lacel Aosureey 190
FedAug
76.48= = 0.36
100.00 + 0.00
100.00 +: 0.00
FoMGNN
70.63 + 0.83
100.00 + 0.00
214,94 0.00
FedSages
77:52 = 0.46
100000 + 0.000
276.84 + 0.00
OCFL
78.84 1: 0.26
100.00 1 0.00
100,00 1: 0.00
5
hay Pilyssigtten
Ours (A-
77.36 1 0.99
25.13 1 0.34
37,70 1 0.56
FBirE Parck
Ours (y==ee-11
79.46
1: 0,4]
42.59 1: 1:33
63.89 1: 1.99
Ours (Ay=5e-1) 11 79,89
0.12
$1.07 à 0.52
85.61 à 0.78
40
00
50
100
30 60
HD founds
Figure& 8: Analysis on efficiencies of communi- Figure 9: Varying the local Figure 10: Performance on cation costs and model sizes.
epochs with accuracy curves.
neighboring subgraphs.
Varying Local Epochs As shown in Figure 9, when we increase the number of communication rounds and the local steps, the model diverges to the local subgraphs (i.e., overfitting), due to the small number of training instances and the direct connection between training and test nodes: struggle to generalize to the test instances. However, our model with the proximal term in equation 5 alleviates this issue, therefore, maintaining the highest local performance. Notably, the performance with five local epochs is inferior to the performance of one epoch, which indicates that increasing the local epochs does not always bring advantages and properly tuning them is important for subgraph FL.
338
340
341
342
343
344
Handling Missing Edges To measure whether FED-PUB can handle the missing edge problem: information is not shared between two neighboring subgraphs due to the missing edges, we use the local model trained on the local subgraph for evaluating the performance on its neighboring subgraph, in which the local subgraph has the most missing edges to its neighboring subgraph. Specifically, in Figure 10, (Neighbor) denotes the subgraph performance evaluated by its neighbor model, while (Local) denotes the subgraph performance from its own local model. Then, the high performance on (Neighbor) measure means two associated subgraphs share meaningful knowledge without having explicit edges between them, thereby solving the missing edge problem. Note that, existing subgraph FL explicitly augments the nodes and edges for capturing the potential information flow over the missing edges between subgraphs, while ours implicitly shares weights a lot across similar subgraphs within the same community. Figure 10 shows that ours achieves the significantly superior performance on the neighboring subgraph problem against subgraph FL baselines, which confirms that ours has an advantage on the missing edge problem by meaningfully sharing knowledge between two subgraphs having potentially missing edges, without explicitly estimating them.
346
348
349
350
351
352
353
354
355
356
357
358
6
Conclusion
359
We introduced a novel problem of personalized subgraph FL., which focuses on the joint improvement of local GNNs working on interrelated subgraphs (e.g. subgraphs belonging the same community), by selectively utilizing knowledge from other models. The proposed personalized subgraph FL is highly challenging due to 1) difficulty of computing similarities between local subgraphs that only locally accessible, and 2) knowledge collapse among local models that work on heterogeneous subgraphs during weight aggregation. To this end, we proposed a novel personalized subgraph FL framework, referred to as FEDerated Personalized s 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 weighted average of the local models for each client. Further, we mask out globally given weights focus on only the relevant subnetwork for each client (or community). We extensively validated our framework on multiple benchmark datasets with both overlapping and non- overlapping subgraphs, on which our PED-PUB significantly outperforms relevant baselines. Further analyses show the effectiveness of the subgraph similarity matching for detecting the community structures, as well as the weight masking for tackling the subgraph heterogeneity. We provide the limitations and potential societal impacts of our work in Section D of the supplementary file.
360
351
362
363
384
385
386
367
368
389
370
372
9

---

References
374
375
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H 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, pages 308-318, 2016.
376
377
378
[2] Manoj Ghuhan Arivazhagan, Vinay Aggarwal, Aaditya Kumar Singh, and Sunav Choudhary. Federated learning with personalization layers, 2019.
379
380
[3] Jinheon Baek, Minki Kang, and Sung Ju Hwang. Accurate learning of graph representations with graph multiset pooling. In 9th International Conference Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
382
383
[4] Richard Bellman. Dynamic programming. Science 153(37311:34-377 1966.
384
[5] Vincent D 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):P1008,, 2008.
385
386
387
[6] Fengwen Chen, Guodong Longr, Zonghan Wu, Tianyi Zhou, and Jing Jiang. Personalized federated learning with structure. arXiv preprint arXiv:2203.000 203.00829, 2022.
388
389
[7] Laxman Dhulipala, Igor Kabiljo, Brian Karrer, Giuseppe Ottaviano, Sergey Pupyrev, and Alon Shalita. Compressing graphs and indexes with recursive graph bisection. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016, pages 1535-1544. ACM, 2016.
391
393 [8] Justin Gilmer, Samuel S. Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning, ICML. 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 1263-1272. PMLR, 2017.
394
395
396
[9] M. Girvan and M. E. J. Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 99(12):7811-7826, 2002.
398
389
[10] William L. Hamilton. Graph representation learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 1459)
400
401
[11] William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on 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, pages 1024-1034, 2017.
402
403
[12] 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.
406
407
[13] 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.077 00,45,.,, 2021.
408
409
410
[14] Chaoyang He, Emir Ceyani, Keshav Balasubramanian, Murali Annavaram, and Salman Aves- timehr. Spreadgnn: Serverless multi-task federated learning for graph neural networks. AAAI, 2022.
411
[15] Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social Nenworks, 5(2):109-137 1983. ISSN 0378-8733.
414
415
[16] Weihua Hu, Matthias Fey, Marinka Zitiik, 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, 13:22118-22133 2020.
416
417
[17] Wonyong Jeong, Hayeon Lee, Geon Park, Eunyoung Hyung, Jinheon Baek, and Sung Ju Hwang. Task adaptivee neural network search with mota-contrastive learning. In Advances in Neural Information Processing Systems, 2021.
419
10

---

421
[18] 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, editors, Advances in Neural Information Processing Systems, Curran Associates, Inc., 2021.
422
425
424
volume 34, pages 7534-7546.
425
[19]
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda Theertha Suresh. SCAFFOLDD: stochastic controlled averaging for federated learning. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 5132-5143. PMLR, 2020.
426
428
430
[20] George Karypis and Vipin Kumar. Metis unstructured graph partitioning and sparse matrix ordering system, version 2.0. Technical report, 1995.
432
[21] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
434
[22] Thomas N. Kipf and Max Welling. Semi- supervise classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. 2017.
436
438
[23] Jure Leskovec, Lada A. Adamic, and Bernardo A. Huberman. The dynamics of viral marketing. ACM Trans. Web, 1(1):,, 2007.
440
[24] Qinbin Li, Bingsheng He, and Dawn Song. Model-contrastive federated learning. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2021, virtual, June 19-25, 2021, pages 10713-10722. Computer Vision Foundation IEEE, 2021.
442
443
[25] 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, Mys 2020, Austin, 7X, USA, March 2-4, 2020. misys.org. 2020.
444
445
446
[26] Paul Pu Liang, Terrance Liu, Liu Ziyin, Nicholas B. Allen, Randy P. Auerbach, David Brent, Ruslan Salakhutdinov, and Louis Louis-Philippe Morency. Think locally, act globally: Federated learning with local and global representations, 2020.
447
448
449
[27] 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.
450
451
452
[28] Zhiwei Liu, liangwei Yang. Ziwei Fan. Hao Peng, and Philip S Yu. Federated social recom- mendation with graph neural network. arXiv preprint arXiv:2111.10778. 2021.
453
454
[29] Disha Makhija, Xing Han, Nhat Ho, and Joydeep Ghosh. Architecture agnostic federated learning for neural networks. arXiv preprint wrXiv:220..0755, 2022.
455
456
[30] Yishay Mansour, Mehryar Mohri, Jae Ro, and Ananda Theertha Suresh. Three approaches for personalization with applications to federated learning, 2020.
457
458
[3]] Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. Emage-based recommendations on styles and substitutes. In Proceedings of the 38th international ACM SIGIR conference research and development in information retrieval, pages 43-52, 2015.
459
460
461
[32] H. Brendan McMahan, Fider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas.
462
Communication-effiiiee learning of deep networks from decentralized data. In AISTATS, 2017.
463
[33] Miller McPherson, Lynn Smith-Lovin, and James M Cook, Birds of a feather: Homophily in social networks. Annual review of sociology. 27(1):415 2001.
465
[34] Mason A Porter, Jukka-Pekka Onnela, Peter J Mucha, et al. Communities in networks. Notices of the AMS, 108 2009.
11

---

467
[35] Filippo Radicchi, Claudio Castellano, Federico Cecconi, Vittorio Loreto, and Domenico Parisi. Defining and identifying communities in networks. Proceedings of the national academy of sciences, 101(9):2658-28)) 2663, 2004.
488
[36] José J. Ramasco, S. N. Dorogovtsev, and Romualdo Pastor-Satorras. Self-organization of collaboration networks. Phys. Rev. E, 70:036106, Sep 2004.
471
472
[37] Felix Sattler, Klaus-Robert Müller, and Wojciech Samek. Clustered federated learning: Model- agnostic distributed multitask optimization under privacy constraints. IEEE transactions neural networks and learning systems, 32(8):3710-3722 2020.
474
475
[38] Felix Sattler, Tim Korjakow, Roman Rischke, and Wojeiech Samek. Fedaux: Leveraging unlabeled auxiliary data in federated learning. IEEE Transactions on Neural Networks and Learning Systems, 2021.
478
477
[39]
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. magazine, 29(3):93-999 93, 2008.
479
480
[40]
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.05886. 2018.
482
[41] Hongyi Wang. Mikhail Yurochkin, Yuekai Sun, Dimitris Papailiopoulos, and Yasaman Khaz- aeni. Federated learning with matched averaging. In International Conference on Learning Representations, 2020.
483
484
485
[42] Chuhan Wu, Fangzhao Wu, Yang Cao, Yongfeng Huang, and Xing Xie. Fedgnn: Federated graph neural network for preeaccpreeeriing recommendation. KDD, 2021.
487
[43] 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):4224, 2021.
488
[44] Han Xie, Jing Ma. Li Xiong, and Carl Yang. Federated graph classification non-iid graphs. In Advances in Neural Information Processing Systems, volume 34, pages 18839-18852. Curran Associates, Inc., 2021.
481
[45] 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, pages 6671-6682. Curran Associates, Inc., 2021.
495
496
[46] Michael Zhang, Karan Sapra, Sanja Fidler, Serena Yeung, and Jose M. Alvarez. Personalized federated learning with first order model optimization. In International Conference Learning Representations, 2021.
498
499
[47]
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems 31: Annual Conference Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 5171-5181, 2018.
501
503
[48] 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 applications. AI Open, 1:57-81, 2020.
504
505
506
[49] Zhuangdi Zhu, Junyuan Hong, and Jiayu Zhou. Data-free knowledge distillation for het- erogeneous federated learning. In International Conference on Machine Learning, pages 12878-12889 PMLR, 2021.
507
508
12

---

Checklist
509
510
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
512
513
(b) Did you describe the limitations of your work? [Yes] We discuss them in Section D of the supplementary file.
514
515
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We discuss them in Section D of the supplementary file.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
518
519
2. If you are including theoretical results...
520
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
521
(b) Did you include complete proofs of all theoretical results? [N/A]
522
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] We provide the code, data, and instructions in the supplementary material.
524
528
(b) Did you specify all the training details (c.g., data splits, hyperparameters. how they were chosen)? [Yes] We specify all the training details in Section B of the supplementary file.
527
528
529
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [Yes] We report the main results with mean and standard deviations, with multiple runs.
531
532
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] We include the computational costs and resources in Section B of the supplementary file.
533
534
535
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
536
(a) your work uses existing assets, did you cite the creators? [Yes]
537
(b) Did you mention the license of the assets? [N/A]
538
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
539
540
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
541
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
543
544
5. If you used crowdsoureing or conducted research with human subjects...
545
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
546
547
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
548
549
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "i3TQduj1KP", "reviewer": "Reviewer_gnhR", "summary": "Aiming to solve the data heterogeneity problem in subgraph federated learning (FL), this paper presents a novel research problem, namely personalised subgraph FL. Focus on this personalised FL scenario, the authors propose a new learning method named FED-PUB. To train local models effectively, FED-PUB considers two key designs, i.e., functional embedding-based similarity estimation and adaptive parameter masking. Extensive experiments validate the effectiveness of FED-PUB.", "questions": "1. What is the meaning of J in Eq. (2)? If J is the number of subgraphs within a community, how to find a specific community for each subgraph during model training? And does that mean the aggregation is only executed within the subgraph in a community?\n2. In Line 45, the authors claim that the algorithms in [40] and [43] may compromise data privacy. Is there any further evidence to prove that?\n3. In the formulation of existing subgraph FL (Line 169) and personalized FL (Eq. (2)), what is the optimized parameter? It's better to highlight this under the \"min\" operation.\n4. Could you provide a theoretical analysis for the techniques proposed in this paper?", "limitations": "The authors have discussed the limitations and potential negative social impacts in Appendix D.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n1. The research problem is interesting.\nThis paper first proposes to study the personalized problem of graph federated learning. The novel research problem is interesting and challenging, which may inspire future studies in the community.\n2. The experiments are extensive.\nThe authors conduct sufficient experiments to compare the performance with baseline methods and discover the property of the proposed method. The proposed method achieves outstanding results, which proves its effectiveness.\n\nCons:\n1. The novelty of the proposed method is limited.\nDespite some interesting designs in the proposed model, the core idea of this paper is not novel enough and similar to some existing works. For instance, using shared data to calculate the similarity between local models has been proposed in [*1]. There is a branch of works that incorporate auxiliary data to assist the federated training procedure, such as [*2], [*3], and [*4].\n[*1] Makhija, Disha, et al. \"Architecture Agnostic Federated Learning for Neural Networks.\" arXiv preprint arXiv:2202.07757 (2022). (Accepted by ICML 2022)\n[*2] Lin, Tao, et al. \"Ensemble distillation for robust model fusion in federated learning.\" Advances in Neural Information Processing Systems 33 (2020): 2351-2363.\n[*3] Sattler, Felix, et al. \"Fedaux: Leveraging unlabeled auxiliary data in federated learning.\" IEEE Transactions on Neural Networks and Learning Systems (2021).\n[*4] Zhu, Zhuangdi, Junyuan Hong, and Jiayu Zhou. \"Data-free knowledge distillation for heterogeneous federated learning.\" International Conference on Machine Learning. PMLR, 2021.\n2. The relationship between the key design (i.e. weight masking) and the research problem is unclear.\nThe authors claim that the weight masking mechanism is to select the relevant parameters for each subgraph. However, it seems like a general solution for personalized FL under heterogeneity and is less relevant to the specific subgraph FL problem. Although it brings some performance improvement, how it benefits the node classification problem is unknown.\n3. The motivation behind personalized subgraph FL is not convictive enough.\nIn the introduction section, the authors use an intuitive explanation (with Fig 1) and a tiny experiment on the synthetic dataset to demonstrate the heterogeneity problem and further show the need for personalized subgraph FL. However, how serious the heterogeneity problem on real-world datasets under the subgraph FL setting is still unknown. The real-world experiments, to a certain extent, demonstrate the issue, but what if the clients' number is much smaller than 10? Maybe more comprehensive experiments will better show the significance of personalized FL.\n4. The capability of dealing with missing edges is over-claimed.\nIn Sec 4.1 (Line 230) and Sec 5.2 (Line 348), the authors claim that FED-PUB can handle the missing edges problem in an implicit manner. This is not persuasive enough. In Fig 10, we can still find that FED-PUB(neighbor) has sub-optimal performance, and the performance gap between (local) and (neighbor) is similar among different methods. In another word, the good performance in this setting cannot prove that the performance gain is caused by handling the missing edges problem. ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "auZDhY46SWU", "reviewer": "Reviewer_we3U", "summary": "This paper introduces a personalized FL framework to train graph neural network model across subgraphs owned by different clients. The authors argue that the heterogeneity of subgraphs will cause the unexpected knowledge collapse when using the same global model to fit all the data from different subgraphs. The authors first group subgraphs into different communities and then train personalized model parameters for clients in each community by introducing adaptive aggregation weights and unique parameter masks. Experimental results support the advantage of the proposed method FED-PUB on six datasets.", "questions": "See Weakness.\nPlus, why not compare with FedSage+ [43]?", "limitations": "See Weakness.", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\tCompared with existing popular methods, the proposed framework achieves competitive results on six popular federated graph benchmarks in a more communication efficient and privacy-preserved manner, without sharing features or embeddings of nodes in graphs. \n\tThe method to identify the similarity between subgraphs is novel, which uses input-based functional similarity instead of the inner of model parameters (i.e. cossim) to estimate the communities of user data. \n\tThe proposed method can potentially handle the missing edges problem by only consider the model aggregation in the same community for each client, since the edges and neighbors are dense in the same community.\n\nWeaknesses\n\tThis work tackles the heterogeneity of different subgraphs by mitigating incompatible knowledge collapse when using only one global model to fit all the data. However, the explaination for this incompatibility between different communities is not adequate. I wonder whether the too small model size or the missing edges between nodes cause such incompatibility. Maybe the direct model training on the whole datasets is needed as the oracle case to show such incompatibility.\n\tThe proposed method is not validated in the cases where the nodes and edges of the whole graph are uniformly distributed across clients. Due to the complex distribution of graph data in practice, the performance of the method in such case or cases where there are not obvious communities should be also considered. \n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "SCVMP7IrQm6", "reviewer": "Reviewer_cN7m", "summary": "This paper proposes an algorithm for personalized FL subgraph learning, FED-PUB.\n\nThe server compute similarities among clients based the output of the local GNNs using random graphs as inputs. It then use them to perform weighted averaging for models.\n\nEach client also learns a personalized sparse mask to select and update only part of the aggregated parameters.\n\nExperiments show the performance.", "questions": "1. Why not directly use local node label distributions to calculate the similarities among clients? The authors could add a comparison with this method.\n\n2. The non-overlapping node scenario is more challenging since it is more heterogeneous. Why does FedAvg (Table 2) in non-overlapping have better performance than FedAvg (Table 1) in overlapping.\n\n3. In Appendix B.3, for small datasets, namely Cora, CiteSeer and PubMed, the experiments set the number of local training epoch as 1. The setting is equal to distributed training. Why does FedAvg perform poorly in this setting? Is it due to missing edges?\n\n\n\n", "limitations": "The intuition of weighted aggregation by similarity has been widely adopted. But the mechanism of similarity calculation by a single random input is not convincing to me. A performance comparison with other similarity methods (label similarity, gradient similarity, model similarity) will also be very helpful. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The weighted aggregation based on similarities of outputs of random graphs is interesting.\n2. The personalized sparse mask looks helpful.\n3. Code is provided.\n\nWeaknesses:\n1. The advantages by using outputs of random graphs are not convincing to me. The random graph based on SBM has too much randomness. Especially with random node features with normal distribution.\n2. The code only provides fedavg and fedpub. \n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5jKdm5NEJG", "reviewer": "Reviewer_rAFu", "summary": "The paper deals with Federated Learning (FL) for graphs. Specifically, the authors investigate FL for heterogeneous graph distributions that can arise when the local graphs belong to different communities within the larger global graph. To tackle the threat of knowledge collapse of the server's GNN model, the introduced method, FED-PUB, tries to identify interrelated local graphs through functional embeddings and aims for their joint improvement. A weighted averaging on the server-side and locally learned weight masks achieve the combined local improvement. The authors evaluate FED-PUB on six different datasets.", "questions": "- The results for FedSage are worse compared to the original publication. How does FED-PUB perform for the subgraph division from [43](<https://proceedings.neurips.cc/paper/2021/hash/34adeb8e3242824038aa65460a47c29e-Abstract.html>)?\n- The functional embeddings on random graphs, what are the failure cases of this approach? What if the graph distribution of these random graphs is off? SBM surely does not capture real-world graph properties. How does this translate?\n- What is the effect of local graph size vs. heterogeneity and how well are the chosen graphs suited for/ support the presented method.\n- Why is it not enough to average parameters according to similarity (Eq.4)? Please clarify the importance of local masks $\\mu$ (4.2)?\n  \nMinor:\n\n- Can you quantify to what degree training runs faster using local masks $\\mu_k$?\n- What is the influence of the scaling parameter $\\tau$ (Eq.4)?\n- Why this specific choice of $S(i,j)=\\frac{h_i h_j}{\\lVert h_i \\rVert \\lVert h_j \\rVert}$ (Eq.3)?\n- How are communication costs computed, cf. 52?\n- What does the colouring indicate for Fig.6a \"Missing edges\"?", "limitations": "-", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n- Combination of FL with the graph-theoretical concept of communities\n- An improved design to ensure data privacy and security via functional embeddings of random graphs\n- Providing a different perspective on the graph FL problem by aiming to improve local graph models\n\nWeaknesses/Open Aspects:\n\n- Please provide graph statistics to investigate the diversity of your evaluation settings across the six datasets\n- Please elaborate on the theory of network homophily and the specific statements you build your arguments on, cf. citation [31]\n- Please clarify the necessity of personalized sparse masks and quantify the drift to the local training distribution. Please provide insights for the specific choice of $\\lambda_2$.\n- For a more transparent comparison, the authors should analyse FED-Pub on the graph partitioning presented in [43]\n\nMinor:\n\n- There is a gap between the provided real-world motivation and the artificially constructed client graphs. Please give some insight into how well the shown setting translates to real scenarios.\n\n### Originality\n\nThe topic of FL for graphs has been picked up only recently (most papers are from 2020 and 2021). Within this evolving research field, the authors introduce the challenge of appropriately dealing with heterogeneous graphs on the client-side. The authors combine graph FL with the well-defined notion of community detection from graph theory to address heterogeneous local graphs.\n\n### Quality\n\n- The authors motivate their work well, and the shown evaluation fits their claims\n- The methods used are appropriate and clear.\n- The presented work is complete with multiple references to the supplement materials\n  \nNegatives:\n\n- The claims on community detection and network homophily should be supported with additional theory. The authors, however, provide good intuition why their introduced setting and evaluation are valid.\n- The authors lack the chance to discuss weaknesses in the paper's main text.\n\n### Clarity\n\n- The paper is well written\n- The authors present their work well structured\n- The test is mostly self-contained\n\nMinor:\n\n- Introduction to GNNs is relatively shallow\n- The authors exaggerate at times, \"Seemingly impossible task\" (4.1), \"an even more serious issue\" (1.), and \"crucial drawback\"\n- Cite the inspiration paper [17] earlier\n\n### Significance\n\n- Dealing with FL, this work is essential for areas where data is not publically available due to privacy constraints.\n- The benchmark for overlapping and non-overlapping subgraphs is new and can inspire future evaluations for graph FL\n- The connection to graph theory (community) is valuable\n  \nNegatives:\n\n- For a more transparent comparison, the authors should analyse FED-Pub on the graph partitioning preneted in [43]", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject