Towards Federated Learning of Deep Graph Neural Networks
Authors: Zhihua Tian
Yuan Ding
Rui Zhang
Jian Liu
Kui Ren
Venue: Submitted to ICLR 2023 (2023)
Keywords: federated learning
graph representation learning
deep graph neural networks

Abstract: Graph neural networks (GNNs) learn node representations by recursively aggregating neighborhood information on graph data. However, in the federated setting, data samples (nodes) located in different clients may be connected to each other, leading to huge information loss to the training method.
Existing federated graph learning frameworks solve such a problem by generating missing neighbors or sending information across clients directly. None are suitable for training deep GNNs, which require a more expansive receptive field and higher communication costs.
In this work, we introduce a novel framework named  $Fed^2GNN$ for federated graph learning of deep GNNs via reconstructing neighborhood information of nodes. Specifically, we design a graph structure named rooted tree. The node embedding obtained by encoding on the rooted tree is the same as that obtained by encoding on the induced subgraph surrounding the node, which allows us to reconstruct the neighborhood information by building the rooted tree of the node. An encoder-decoder framework is then proposed, wherein we first encode missing neighbor information and then decode it to build the rooted tree.
Extensive experiments on real-world network datasets show the effectiveness of our framework for training deep GNNs while also achieving better performance for training shadow GNN models

Under review as a conference paper at ICLR 2023
TOWARDS FEDERATED LEARNING OF DEEP GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Graph neural networks (GNNSs learn node representations by recursively aggre- gating neighborhood information on graph data. However, in the federated setting. data samples (nodes) located in different clients may be connected each other, leading to huge information loss to the training method. Existing federated graph learning frameworks solve such a problem by generating missing neighbors or sending information across clients directly. None are suitable for training deep GNNs, which require a more expansive receptive field and higher communication costs. In this work, we introduce novel framework named Fed ated graph learning of deep GNNs via reconstructing neighborhood information of nodes. Specifically, we design a graph structure named rooted tree. The node embedding obtained by encoding on the rooted tree is the same as that obtained by encoding on the induced subgraph surrounding the node, which allows us to reconstruct the neighborhood information by building the rooted tree of the node. An encoder-decoder framework then proposed, wherein we first encode missing neighbor information and then decode it to build the rooted tree. Extensive experi- ments on real-world network datasets show the effectiveness of our framework for training deep GNNs while also achieving better performance for training shadow GNN model
GNN for feder-
INTRODUCTION
Recently, Graph Neural Networks (GNNs) have attracted significant attention due to their powerful ability for representation learning of graph-structured data (Hamilton et al. 2017a Kipf Welling 2017 Hamilton et al.) 2017b). Generally speaking, it adopts recursive neighborhood aggregation (or message passing) scheme to learn node representations by considering the node features and graph topology information together (Xu et al.) 2018). After k iterations of aggregation, node captures the information within the node's s k-hop neighborhood.
Similar to learning tasks of other domains, training well rell-performed GNN model requires its train- ing data to be not only sufficiently large but also heterogeneous for better generalization of the model. However, in reality, heterogeneous data often separately stored in different clients and cannot be shared due to policies and privacy concerns. To that end, recent works have proposed fed- erated training of GNNs (Zhang et al. 2021 Peng et al., 2021 Yao & Joe-Wong 2022 Chen al.) 2022). They typically consider a framework wherein each client iteratively updates node represen- tations with a semi-supervised model on its local graph; the models are then aggregated
central
server. The main challenge is that data samples (nodes) located in different clients may be connected each other. Hence, non-trivial to consider the connected nodes (i.c.. neighbor nodes) located in other clients when applying node updates. Although existing works focus on recovering missing neighborhood information for nodes, they either only consider immediate neighbors (Zhang et al., 2021 Peng et al., 2)21) require communication costs to increase exponentially as the neighbors' distance increases (Yao & Joe- Wong 2022, Chen et al., 2022). None of them are suitable for train- ing deeper GNN models, which require more expansive receptive field and have been shown to be beneficial for representation learning for graph-structured data (Li et al. 2019 Liu et al. 2020
!Code available
https: httpps://ww..drostt com / wttp://...c.././a.ea/eeaaaaaaaat xsm F zip?
d1

---

Under review as a conference paper at ICLR 2023
Zhou al. 2020a). For GNNs, the receptive field of node representation is its entire neighbor- hood. Moreover, Yao & Joe- Wong 2022) also requires calculating the weighted matrix in advance, which is not available in practice.
In this work, we aim to fundamentally address the above limitations of existing federated graph learning methods by proposing a novel framework named Fed The key idea lies in designing principled approach to reconstructing the neighborhood information of nodes that considers both structure-bert based (i.e., graph topology) and feature- based information (i.e., node features). For the structurebbase information,
propose novel graph structure named rooted tree, which has more regular structure than the original structure of the node neighborhood. More importantly, the node embedding obtained by encoding the rooted tree is the same that obtained by encoding on the node's s ego-graph (i.e., the induced subgraph surrounding the node). Such a property allows us easily reconstruct the structure-based information by building the rooted tree of the node.
For the feature-based information, since the structure of the node neighborhood changes, we aim generate features of the nodes in the rooted tree. Inspired by the structure of the rooted tree, we design a protocol wherein clients recursively transmit information across each other. The data transmitted in the k-th round correspond nodes in the k+11-t layer of the rooted tree. Furthermore, we utilize the encoder-decoder framework to reduce the communication costs such that it grows only linearly as the number of iterations increases. information and sends the output to other clients. Other clients build the rooted tree by decoding the received information. By merging all trees into the local graph (with the rooted node as an anchor), each client obtains complete graph on which applying graph representation learning has limited information loss. In summary, we make the following contributions:
more detail, each client first encodes the
We introduce Ged an framework for federated training of GNNs to solve node-level pre- diction tasks. We achieve such a goal by devising a principled approach to reconstructing missing neighborhood information that considers both structure-based and caature-based information.
To reconstruct the structure- based information, we propose a novel graph structure named rooted tree, which is easier to construct than the original irregular structures of the node neighborhood. More importantly, the node embedding obtained by encoding on the rooted tree the same as that obtained by encoding on the node's ' ego-graph.
To reconstruct the Deature-based information, we propose an encoder-decoder framework to reduce communication costs while having limited information loss.
We conduct extensive experiments to verify the utility of Fed The results show that it is effective for training deep GNNs while achieving better performance for training shadow GNN models.
We outline related works in Section 2 before introducing the problem statement of federated graph learning in Section 3 We then introduce Fed in Section 4 wherein we first introduce the structure of the rooted tree and then presents the neighborhood reconstruction process. We analyze its performance experimentally in Section 5 and concluding in Section
RELATED WORKS
Graph Neural Networks (GNNs) learn representation for each node in the graph using set of stacked graph convolution layers. Each layer gets an initial vector for each node and outputs a new embedding vector by aggregating vectors of neighbor nodes followed by a non-linear transform. After k aggregations, the source of information encoded in the representation of a node essentially comes from its k-hop neighborhood. Following the above framework, which usually called mes- sage passing, several GNN models have been proposed, such as GCN (Kipf & Welling (017), GraphSAGE (Hamilton et al.) 2017b), GAT /Velickovic et al.) 2018), and so on. However, unlike the learning tasks in other domains, simply stacking graph convolution layers usually suffer from an omor-smgg issue, leading to even worse performance. Surprisingly, with the research on the above issues, several works (Liu et al. 2020 Li et al. 2019 Zhou et al. 2020b) propose effec- tive deep GNNs and obtain better performance on graph learning tasks. Its excellent performance suggests its great potential for federated learning distributed subgraph data.
2

---

Under review as a conference paper at ICLR 2023
Federated Learning (FL) is privacy computing technology that enables collaborative machine learning without exposing private data. It was first proposed by (McMahan et al. 2017)'s 's FedAvg, which allows clients to collaboratively train a common model while each of them only possesses local dataset. During training, each client periodically uploads the local update to the server. The server then aggregates the updates to global model and distributes the model to clients for further training. Recently personalized federated learning (Finn et al. 2017 et al., 2020), which aims to learn heterogeneous models for different local tasks, also attracted attention from the community. However, our paper focuses on learning a global model from multiple clients for a common task. Hence, we mainly borrow the idea of FedAvg to train GNNs collaboratively.
Federated Graph Learning aims solve the graph learning problem on distributed subgraph data. Recent researchers have made progress on federated graph learning, and several frameworks have been proposed (Fu al. 2022 Liu & Yu 2022). (Zhang al., 2021) proposed framework named FedSage+, which utilizes a neighbor generator to recover cross-client neighbors of subgraphs. How- ever, they only consider immediate neighbors and can not fully recover the cross-client information. FedGraph (Chen et 2022) develops a cross-client graph convolution operation to enable embed- ding sharing among clients, which requires sending updated embedding in every iteration during model training. FedGCN (Yao & Wong, 2022) solves such problem by proposing to transmit the aggregated features of the cross-subgraph neighbor nodes directly. However, it assumes that the weighted matrix is calculated in advance and requires communication costs to increase expo- nentially as the number of layers increases. Baek et al., (Baek et al.] 2022) propose a personalized federated subgraph learning method, mainly focusing on heterogeneous subgraphs. In more detail, it develops an aggregation method based on similarity among clients. However, it does not consider the missing neighbor information. In summary, none of the existing works are suitable for federated learning for deep GNNs; we are the first to achieve such a goal.
3 PROBLEM STATEMENT.
Given an attributed non-directed graph 9 (V,E, where V is the vertex set, E is the edge set, and X' include the node features. Each node has feature v. X with corresponding label y; for the downstream task, e.g., node classification. We have Fa E Rdz,
In the FL system, assume there exist central server S and M clients Pp.P [M] where [M] represents (1,..,,M M) for any M E N+ The server only maintains a graph learning model with no graph data stored, and each client holding a subgraph Gp = (Vp, Xp), where Vp. Ey, X, are subset of V, V,E,a X' respectively. We assume no overlapping nodes shared across clients, namely ViP n V/ = 0, Vp. q E [M] p * q, and all subset constitute the full set, i.e.U Vp = V. Given a node e E V, we define its k-hop neighborhood as the nodes which have shortest paths of length from v. Let c(v) denote the index of the client that contains node v and Nr, denote the I-hop neighborhood of v. For any node u E V. we assume Petu) knows all v's 1 1-hop neighbors even they are distributed across different clients. The set of neighborhoods contained in the same client as v is denoted as NY¹ and the set of other neighborhoods is denoted as Noo No WNN.. We name Pe(v) as the active client and other clients (Pot)) li E Nop) as passive clients of v for ease of expression.
4 METHODS
In this section, we propose a novel framework for federated learning of deep GNNs (Fed The framework relies on a principled approach to reconstructing neighborhood information, with the core idea of building rooted trees for all nodes. After constructing all trees, we can get complete local graphs, on which applying graph representation learning has no neighborhood information loss. The FedAvg (McMahan et al. 2017) algorithm is then adopted to train GNN on complete local graphs. Next, we start with designing a rooted tree of a node and then show how to build the tree with an encoder-decoder framework.
4.1 DESIGN OF THE ROOTED TREE
Given a K Kllayer GNN model, learns node representation by recursively aggregating neighbor- hood information around the node. After K times aggregation, it could encode information from the
3

---

Under review as a conference paper at ICLR 2023
ma
m1
m2
mg
m
m2
mg
m
m
my
m
m
(a) Rooted tree with 1-hop neighborhood
(b) Rooted tree with 2-hop neighborhood
(c) Rooted tree with 3-hop neighborhood
Figure 1: Examples of constructing rooted trees with different neighborhood for node i.
k-hop subgraph of the node, wherein the subgraph is often called the ego-graph, In order to recon- struct the missing neighborhood information for each node, the rooted tree is designed by following two principles: (1) it could fully preserve the neighborhood information, i.e., the node embedding obtained by encoding on the rooted tree is the same as that obtained by encoding on the node's ' ego- graph, and (2) has an easy-to-build structure. To that end, we design the rooted tree by unfolding the ego-graph for each node.
An example of constructing rooted trees with 1,2,3-hop neighborhoods is depicted in Figure T Specifically, for node i E G, we first set as the rooted node. We then can set i's 1-hop neighbors m N as nodes in the second layer of the rooted tree (Figure[[(a)). The third layer, intuitively, can be constructed using m's neighbors for each m E NN However, note that is also included in Nu and connected to as the father note of m. Hence, we exclude and connect the remaining nodes in Nm.. to to further construct the rooted tree (Figure (b)). Following the above procedure, we construct the k + 1-th (k > 1) layer by connecting the neighbors nodes in the k-th layer to itself except for its father node. Finally, for a K K-layer GNN model, we construct rooted tree with K + layers.
Proposition 1. Given K-layer CNN model, for any node i and its corresponding ego-graph, can construct a K + 1-layer rooted tree following the above procedure such that i's embedding obtained by encoding the rooted tree the same as that obtained by encoding on its ego-graph.
It's worth noting that the rooted tree is actually an undirected graph. For any node on the tree, it treats its father node and children nodes one-hop neighbors and recursively aggregates their information to update its embedding. Meanwhile, the nodes in the k-th layer of the rooted tree have the complete neighborhood information of K+1 - hops, and the rooted node at the first layer have the complete K K-hop neighborhood information. Thus, for a K-layer GNN model, a rooted node has the same embedding as obtained by encoding on its K-hop ego-graph. Meanwhile, although the degree of nodes in the last layer changes, which affects the convolution results of nodes at K-th layer to models like GCN (Kipf Welling, 2017). we can manipulate the edge weight to guarantee the correctness of the convolution process. Details are presented in Appendix [A]
In practice, we aggregate the leaf nodes into single node. does not affect the encoding process when applying the sum function to aggregate features of neighbor nodes. Meanwhile, we only construct the rooted tree of missing neighborhood information. For instance, assume that nodes i, mm, m,, in Figure located in the same client while node m2 locates in a different client. We can construct the rooted tree i by only considering the my branch in the second layer. Although my also acts i's 2-hop neighbor node, affecting i's encoding result through the path my -m which does not exist i's rooted tree, we solve this problem by merging the rooted trees and my into the original subgraph, wherein the path m2 my exists in my 's rooted tree. Finally, by merging rooted trees of all nodes into the local graph (with the rooted node as an anchor), we obtain a complete graph.
4.2 NEIGHBORHOOD RECONSTRUCTION
To construct the rooted tree of K + layers, we have clients recursively transmit information across each other for K iterations. Meanwhile, an encoder-decoder framework further used reduce communication costs. An visual illustration of the information transmitting process across clients presented in Figure 2 For ease of presentation, we start from 1-hop and 2-hop neighborhood reconstruction and then generalize to K K-hop neighborhood reconstruction.
One-hop neighhorhood Reconstruction. Constructing rooted tree with 1-hop neighborhood in-
4

---

Under review as a conference paper at ICLR 2023
k-1
Decoder
Transmit 1-hop neighbor
Transmit 2-hop neighbor information
3. Transmit 3-hop neighbor information
4. Construct the rooted tree the complete graph
Figure 2: Visual illustration of the information transmitting process across clients and the approach to get the complete graph by constructing a rooted tree. The information transmitted between clients encoded and represented by the bold arrow.
formation only requires the features of 1-hop neighbors of the rooted node. According to the ex- pression of 1-layer GNN model presented below,
Σ MEN,U())
Im (., = o((
Σ Im
Σ w()).
MENTU())
MENT
It is sufficient for the passive client P. send Em EN;" 1_(c(m)]am, to the active client, where the indicator 1. [=]]]]] is 1 z = c(m) and zero otherwise. The active client then sums all received information to get f == Em ENT" I' and treats it pseudo node to construct the rooted tree. We treat the sum function an encoder and do not require decoder here. The same idea is also presented in (Yao & Joe- Wong 2022). However, it assumes that the weight matrix is calculated in advance, which unavailable when training GCN (Kipf & Welling 2017) models in practice since the degrees of neighbor nodes in other clients are usually unknown.
Two-hop neighborhood Reconstruction. Constructing the rooted tree of 2-hop neighborhood in- formation is a continuation of the process of 1-hop neighborhood Reconstruction. Specifically, for all i G, we assume Pe(e) knows f! already.
Our intuition lies the expression of a 2-yeyer GNN.
i a Σ ol Σ mENiU()) (m)
I.y (,W()))())
=o(( Σ o(l
Σ fEN
Σ 2))
Σ o
Σ I 22W(1)))((2
MENTUp)
JENT
MENT
jENuLU(m)
(2)
Although three items are missing to get St. including the missing one-hop information ΣjEN Tj as well as the missing two-hop information Vm NN, E Ij and Vm E EVT", EEjEA,,mm) Tj. only the third item remains unknown for Pa(s) after constructing the 1-hop neighborhood for all nodes. To that end, we have passive clients encode the missing information first and send the result to the active client. Specifically, for a passive client Ps, who owes a subset A C No calculate af == Emerço 1=[c(m)) EyEN,,. Dj and send o to the active client Pa(i)- Patt) then sum all received information get 2? := Emen?" EjEN... Tj. By minis i's information, Pa(a) gets f = 2? | a which is the sum of features of nodes in the third layer of the rooted tree, where represents the size of set.
Given f and f-2 we design a decoder & to extract features of nodes in the second layer and third layer of the rooted tree simultaneously. Specifically, the decoder is designed to achieve the following capability:
oi ((CONCAT()). (()) = {CONCAT( HN E ENP).
where H \(8) ΣjEN,N() 3. is the neighbour information of m except for According to the dimension of features, we can split the outputs into two sets G; {2m |m E NYP) and H, {u (i)
vi) im ) corresponding features of nodes in the second and third layer of the rooted tree. The rooted tree can easily constructed by connecting nodes G; to the rooted node and nodes in H; the corresponding node in G;-
5

---

Under review as a conference paper at ICLR 2023
Generalizing to K-hop neighborhood reconstruction
Following the derivation for the I-hop and 2-hop cases, one can similarly generalize the method to reconstruct K K-hop neighborhood. For every node i E V, denote R, k [K] as the set of neighbor nodes in the k 1-th layer of the rooted tree for the missing neighborhood. To construct the rooted tree, we first get the sum of features of nodes in each layer ff EmERt 2m, k [K] and then input them to the decoder to reconstruct the entire neighborhood information (Figure 2). Mcanwhile, denote No, l E [K] as the set of neighbor nodes the k + 1-th layer of the rooted tree for the entire neighborhood, R C .V² We further denote n = EmENY Im,
[K].
Protocol D in the Appendix F depicts the process of getting S.a. The core idea that the k-hop neighbor information of any node i contained in the - 1-hop neighbor information of i's neighbor nodes. To that end, we only require passive participants send information to the active participant. Specifically, for every node i E V. denote C, = (ppl3m E NN,,, s.t. p c(m)} as the set of passive participants for node i. We first get f (line 3-8) and f? (line 13-20) following the process described above. Meanwhile, We also get ui, 1 := uu; ft (line 9-10) and p Vi := nz f? (line 19-20), where τ/2 denotes neighbor information without loss for node i. To construct fü. we have passive client Pp E C₁ sends g3 := Emexp Lp[c(m))) p the active client. After summing all received information, it is then required to minus (IA, 1) ft', wherein f! is missed 1- hop neighbor information that already exists in the second layer the rooted tree. Meanwhile, as each dp contains i's information without loss, it is required minus |A! n/ and finally get 1a -Eppec. & (LA 1)) | n/! (line 22). Similarly, na = PP,Eccu(((()) of (IN + [VT' - 1) 14 (line 23), and 11²² = p - (line 24). Repeating the above procedure, we can get f for any > 3.
The decoding process is challenging, tree and reconstruct the edges between them. To achieve such goal, we propose an algorithm to reconstruct the neighborhood with the help of multiple decoders Φx, k [K- 1], where da can extract features of k-hop neighborhood information. In more detail, 6R is designed to achieve the following capability:
need to decode feature information of nodes in the rooted
6x (CONCAT (1.
f.K)
-CCONCAT S1
Σ
Σ E4IEE Mle-1 IEENK MIk-z]
E
xix) 14 E N
lEt1 I.N,, M1x-1
(4)
where 4. k E [K] corresponding to h-hop neighbor nodes.
Algorithm 2 the Appendix [F] presents the pseudo-code of the construction process.
We first concatenate fr.k k E R] (line 4) and input it to &i (line 9). We split the outputs into two sets G1, H.. where G. = (6r,14 E ..T) and H! (CONCAT(EI Vi) Sizs... LisEM,, 1(0 EineNin W0K (0 14 E ATT). The sec- ond layer of the rooted tree for is constructed by generating nodes with features cor- responding to elements in G We then input each vector in H! Ø2 to decode fea- tures of nodes in the next layer (line 8-12). Specifically, for every l E N.P, we input the corresponding vector to Φ2 and get two sets G CCONCAT(EIsENN; M4r
(/r,1/2 NG, Mij) and H1 M4) Ei.! Lissii Mh) LixEViR Mix 2) a1x)) E Ni, MiJ). The third layer is constructed by generating nodes with features corresponding to elements in G? and connecting them to 41. Repeat the above procedure, we can fully construct the first K layers of the rooted tree. The last layer is constructed by directly generating nodes with features corresponding to elements in H.K and connecting them 1--
4.3 DESIGN OF EXCODER-DECODER.
In the design of our encoder-decoder framework, we use the sum function as encoder, which has the advantage of no need to lear. So the active client can learn an end-to-end decoder with the training dataset generated from her local graph. Although decoders o,, i E [K] extract features of nodes in different layers separately, they are designed by the same principle, i.e., extract node' features and the corresponding neighbor information simultaneously. The main difference is that the

---

Under review as a conference paper at ICLR 2023
scope of the neighbor information is different, where Φ1 extracts K - 1-hop neighbor information while ΦK-1 extracts 1-hop neighbor information. To that end, is only needed to train Φ1 and apply it to extract features of nodes in all layers.
For case of presentation, we show the training process of Φ1 when K = 2. Specifically, we consider the following principle to reconstruct the 1-hop and 2-hop neighborhood information simultane- ously. We have
min 61 EV
Σ M (I(i)) s.t. X₁ Σ Chaiee
hEY;
where X; CONCAT( f?). Y, (CONCAT (sm: HN | m E NN," and M( -) is the loss function that measures the loss to reconstruct set Y,. The task of learning Φ1 is hard to characterize, and there are two fundamental challenges: First, as the distribution of node degrees is often long-tailed in real-world networks, the size of each set may vary differently. Second, a match- ing problem has to be solved to compare two equal-sized sets, which is costly if the set size is large. The first problem is easy to solve. As each node knows its neighbor nodes, the active client can sam- ple at most neighbor nodes and ask passive clients to send the information of sample nodes only. For the second problem, we transform the decoding task into learning the probability distribution of the neighborhood information from a source distribution. Specifically, for node i, the neighbor- hood information is represented an empirical realization of i.idd sampling of d, elements from Pi, where P. - ग. Emex, CONCAT (Tmm HN.. ((3)) and the source distribution Q _ EmeN; P(m)) Therefore, we adopt
M (Y; Φ (X+)) = W (x.))),
(6)
where W2 is the 2- 2-Wassrsteein distance (Villani 2009).
We make use of the architecture of a U-Net network (Ronneberger et al. 2015 to construct the decoder, which has the advantage of generating features of all neighbors in one forward pass. A
theoretical analysis of the capability of the decoder is stated in Theorem 4.1 (See the proof in Ap- pendix B reproduced in Theorem 2.1 in (Lu & Lu| (020)).
Theorem 4.1. For any 0, the support of the distribution P, lies in bounded space of Rd, and Q is absolutely continuous with respect to the Lebesgue measure, there exists a feed-forward neural network u(-): Rdd + (and thus its gradient Vu(-) Rd + Rd with large enough width and depth (depending on c) such that W2 (Pi, (Vu) Q.) <.
The decoder Φ1 requires knowing the number of missing neighbors in advance, which is unavailable for the active client when applying it to extract features of k-hop (k > 1) neighhors. To that end, we use a predictor to predict the number of neighbors. Specifically, predictor du takes &m and áx Vi as inputs to predict the size of [W MiHl. Denote as the loss function. Φu is joint training with di by optimizing the following loss function:
M (X.))
Σ mEN
Eldalim, AN... Mo), WW ((H)).
In practice, we adopt the empirical Wasserstein distance that can provably approximate the popula- tion one. For node i, for every forward pass, the model will get |Y|| outputs denoted as E.,...,&u Inspired by the work of (Tang et al. 2022), which propose an auto-encoder framework for graph data, we adopt the surrogated loss defined follow:
Y!
min Σ Eell
s.t. π is bijective mapping: [[Y]]] - [[Y]]]-
Meanwhile, the original node features could be high-dimensional, and reconstructing them directly may introduce a lot of noise. Instead, we may first map node features into a latent space. In more detail, all clients could collectively learn a model and map features to a low dimension with linear layers in the model.
5 EXPERIMENTS
In this section, we conduct extensive experiments to evaluate Fed focusing on the following research questions: RQI: How does Fed perform in comparison state-of-the-ar federated
7

---

Under review as a conference paper at ICLR 2023
Table 1: Summary of node classification accuracy results in percent (GCN, GraphSAGE).
Model
Cora
MSAcademic
DBLP
GCN
M-5
M-10
M-15
M--5
M-1
M-15
M-5
M-10
M-15
FodArg
86 02422.0.0 55
39:21.35
77.8811.00
93.03:2..15
90.78:0060 64
87 $7.94:20.00 61
84.29:10.30
82,02:0.31
79.57:00.77
FodAvg-Full
86 4970.337
X2 8.41.84
51.5541.57
93.50:+0.13
92.12+0.36
01-25-00.00
84.72+00 34
K3.40==0.22
82. 4.-20.22
Fed'GNN
86.15+0.51
1.76
12.25
93,5940.14
92.12+0.43
91.81+0.09
84.90+0.18
84.02=0.08
83.42:+0.19
Central
87.88 2:0488
93.72 20.14
85.01 2:0.00
Model
MSAcudemic
DBLP
GraphSAGE
M-5
M-15
M-10
FedArg
816110.1 19
81.37:10.83
77.62:1066
93.29:10.16
91.17:00.9
89.0610.80
83.82:10.2 27
82/13::0.11
81.51:10.15
FollAy-Full
85. 1940..1
83.4):00.70
808420060
93,40:::.100
91 99400.74
90.53:1105
84.25::0.
83.74=0.18
03.00:50.16
FedSagss
84.66-00776
03.54++0.70
82.39+0.50
92.59:0.222
91.32-40.05
89.97=0.16
79.96+00.05
N0.79-00699
81.18-00.7
FNd
86.07=00.9
84.22:00.66
80.66:0.9
93,1440.55
91.04=1.37
90.01+1.24
84.28:+0.19
83.36=00266
83.07=00.13
Central
87.15 -7.65
94.76 10.19
84,51 =0 23
Table 2. Summary of mode classification accuracy results percent (5 deep ONN).
Model
Corn
MSAcademic
DBLP
DAGNN
M-10
M-10
FedAvg
87.62:20.54
84.04200778
81.42:0:90
93.71::0.26
92.63:0.20
90.57=0.881
84.49:00007
83 63.26:20.07
82.38:20.15
Full
67.65=00.45
86. 06.7900.56
85 20+0.997
94.1520026
93.40+0-42
92.57=0.87
84.74:0.00 09
84 34:34+0:11
84.41=00.10
FedSage+
83.87=1114
83,0610.75
9121110.24
91.00-0.06
80/4610.26
80.7411..0
GNN
00.41=0.20
86.78:0077
86.72+1.02
94.01=0.011
93.65:0.47
92.89-0.36
84.56:20.00
84. 94.16::0:21
83.91=00.09
Central
88.15 +0.54
94.56 #0.14
85.04 +0.35
graph learning baselines for training 2-layer GNNs? RQ2: How does Fed perform on deep GNNs compared to baselines? RQ3: What are the impacts of the max node degree d to Fed'GNN"
5.1 EXPERIMENTAL SETTING
We conduct experiments on three citation network datasets, Cora (Sen al. 2008 MSAca- demic (Shchur et al. 2018), and DBLP (Fu et al. 2020). We randomly split all datasets with 40% training set, 30% validation set, and 30% testing set. To synthesize the distributed subgraph sys- tem, we generate hierarchical graph clusters on each dataset with the Louvain algorithm (Blondel al. 2008) following the work of FedSage+ (Zhang al. (00TT. We consider three scenarios of M 5, 10, 15. The statistics of datasets are presented in Appendix
We compare GNN with four baselines to demonstrate its effectivvnesss All experiments were repeated ten times with different random seeds.
Central learning: models are trained in centralized manner with global graph dataset.
FedAvg: models are trained by utilizing the FedAvg algorithm on distributed subgraph data.
FredAvg-Full, models are trained by utilizing the FedAvg algorithm, but the node representations have no neighborhood information loss. This baseline
line with FedGCN (Yao Joe- Wong 2022 's goal in terms of accuracy and represents the target of our framework.
FedSage+ (Zhang et al. 202I): a federated graph learning framework with the idea of generating cross-subgraph neighbor nodes.
5.2 PERFORMANCE FOR 2-LAYER (RQ1)
We conduct experiments on two GNN models: GCN Kipt & Welling 2017) and Graph- SAGE (Hamilton et al., 201 7b). and compare the performance of Fed Ged with all baselines.
The results are depicted Table It shows that Fed has the best performance over FedAvg and is better than FedSage+ in most cases. Meanwhile, Fed has comparable performance with FedAvg-full, corroborating the effectiveness of our method for reconstructing neighborhood information.
5.3 PERFORMANCE FOR DEEP GNNS (RQ2)
We conduct experiments evaluate the performance of our framework for deep GNNs. We adopt the model DAGNN proposed in (Liu et al.) 2020). which has better performance for node repre- sentation learning than GCN (Kipf & Welling 2017) many dataset. Table presents the results
8

---

Under review as a conference paper at ICLR 2023
Accuracy
Fedhig
Peckug Pu
8
Pu
10
20
ayers
layers
Node Degree
(a) Cora
MSAcademic
(c) DBLP
Max Node Degree
Figure 3: Results of Fed for training deep GNNs with different
Figure 4: Accuracy v.s.
number of layers.
Max Node Degree
when the number of layers 5. shows that Fed still has good performance even for deep GNNs, demonstrating the effectiveness of our methods for reconstructing neighborhood in- formation. Meanwhile, another important observation emerging from the results that learning for DAGNN significantly bridges the gap between central learning and federated learning the Cora dataset. Specifically, as can be observed in Table ! the gaps between central learning and Fed is 4.58% when M = 10 and 5.68% when M 15 for GCN model,while the gaps are only 1.37% and 1.43% for deep GNNs. Such an observation assay the benefits brought by DAGNN in the federated setting.
We further conduct experiments for DAGNN with different depths. The results are illustrated in Figure 3 It shows that node representation learning on Cora and DBLP datasets benefits from training the DAGNN model. Mcanwhile, applying DAGNN on the MSAcademic dataset degrades the performance in central learning. Both of the observations are aligned with the results (Liu et al. 2020). However, federated graph learning the MSAcademic dataset could benefit from applying deeper DAGNN, probably because deep GNNs have a better generalization ability and compensate for the federated learning. Moreover, Red'GNN still performs better than FedAvg and has comparable performance with FedAvg-full, showing that our method is effective for federated learning of deep GNNs.
5.4 IN-DEPTH ANALYSIS FOR FND(333))33
In Figure we present results on studying the impact of max node degree for Fed The size of d not only affects the efficiency of reconstructing neighborhood information but also affects of performance of downstream tasks. We experiment on models with a different number of layers with the Core dataset and try q varies from to 20. It shows that the performance of FNd GNN robust to the max node degree, with large d only leading slightly better performance them small d.
Finally, to further understand the effectiveness of our proposed framework for federated graph learn- ing, perform convergence analysis in Appendix E The results show that the method has a sim- ilar converge rate as FedAvg-full, indicating that we can indeed recover the missing neighborhood. Meanwhile, we conduct experiments on training the decoder locally or collectively; the results show that the decoder has good generalization ability.
6 CONCLUSION
In this work, we address the limitations of existing works of federated learning on graph-structured data and propose a new framework that can better tackle the issue of missing cross-client neighbor- hood information during training. Our framework utilizes the idea of reconstructing neighborhood information that considers both structured-batt allows us to train deep GNNs in the federated setting, leading to better performance for node rep- resentation learning. Extensive experiments have been conducted to verify the effectiveness of our framework, which consistent with theoretical analysis. Though framework manifests good performance, confronts potential privacy concerns as other works in federated learning. Solving such problem could be promising direction in the future.
and feature-based information. Such an advantage

---

Under review as a conference paper at ICLR 2023
REFERENCES
Jinheon Back, Wonyong Jeong, Jiongdao Jin, Jachong Yoon, and Sung Ju Hwang. Personalized subgraph federated learning. CoRR, abs/2206. 10206, 2022. doi: 10.48550/rriiv22266.00m
URL http:////oo..rr11........ http://wwwwwwv......... 10206
Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast un-
folding of community hierarchies in large networks. CoRR, abs/0803.0476, 2008. URL
http:://rxivy www.oorg/ba....ooooo..e /0a0//000..om 00000000066606..0
Fahao Chen, Peng Li, Toshiaki Miyazaki, and Celimuge Wu. Fedgraph: Federated graph learn- ing with intelligent sampling. IEEE Trans. Parallel Distributed Syst. 33(8):1775-1786, 2022. doi:
URL https:
3125565
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In Doina Precup and Yee Whye Teh (eds.). Proceedings of the 34th Interna- tional Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 1126-1135. PMLR, 2017. URL http::/proceedinng/ wmw.iinnss.......m.mmmm.mmmm..mm mlrr. wwwss/ http///innnaaa.aa...
Xingbo Fu, Binchi Zhang, Yushun Dong, Chen Chen, and Jundong Li. Federated graph machine learning: A survey of concepts, techniques, and applications. CoRR, abs/2207.11812 2022. doi: 2207. 11812
10.48550/rrXiw.2207.1188
URL/https: /
Xinyu Fu, Jiani Zhang. Ziqiao Meng, and Irwin King. MAGNN: metapath aggregated graph neural network for heterogeneous graph embedding. In Yennun Huang. Irwin King, Tie- Yan Liu, and Maarten van Steen (eds.), WWW '00: The Web Conference 2020. Taipei, Taiwan, April 20-24, 2020, pp. 2331 2341. ACM IW3C2, 2020. doi: 10.1145//33642333333997 URL https: 7/doi org/ 00 1141/13364322 3380297
William L. Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Meth- ods and applications. IEEE Data Eng. Bull., 40(3):52-74 74, 2017a. URL httt::/ssite:
Computer org. http://bbbll////ea/a/ /sept pdf
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs In Isabelle Guyon, Ulrike Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Informa- tion Processing Systems 2017, December 4-9, 2017, Long Beach, CA. USA, pp. 1024- 1034, 2017b. URL https::/pproceediii
http://www...co....oooeooooeerrr cc/ppaperr22///aaas
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. Openkeview.net, 2017. URL httpssss:: //openzeview wtrr (t
Guohao Li, Matthias Müller, Ali K. Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? In 2019 IEFF/CVF International Conference on Computer Vision, ICCV 2019, Seoul, Korea (South), October 27 November 2, 2019, pp. 9266-9275 IEEF, 2019, doi: 10.1109//CCV. 2019.00936. URL htttts/://// /ooi wow. 1119/101CCCCC 2019 00936
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. In Inderjit S. Dhillon, Dimitris S. Papail- iopoulos, and Vivienne Sze (eds.), Proceedings of Machine Learning and Systems 2020, MI.Sys 2020, Austin, TX. USA, March 2-4, 2020. misys.org. 2020. URL httpsttt htttpss:/pprcceednggs misys. wwwpoo/g//booooooooo /16. pdf
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Rajesh Gupta, Yan Liu, Jiliang Tang, and B. Aditya Prakash (eds.), KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23-27, 2020, pp. 338-348. ACM, 2020. doi: 10. 011144/339488.34000000 URL https: :ttess://do/ doi. orq/ 10. 00.1145/339440 3403076
10

---

Under review as a conference paper at ICLR 2023
Rui Liu and Han Yu. Federated graph neural networks: Overview, techniques and challenges. CoRR, abs/2202.07256, 2022. URL htttps:/ wttp://...wraa//////////// 2tt.:////aax....oor//////222222
07256
Yulong Lu and Jianfeng Lu. A universal approximation theorem of deep neural networks for express- ing probability distributions. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria- Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, De- cember 6- 12. 2020, virtual, 2020. URL https:::/prrcceeegsss....t
wwt.a/uurrs.....aarpeooeee cc/paper/ 3000///5522000E3333cc33131eeeee. Abw.aaatt..bttttt............
Brendan McMahan, Eider Moore, Daniel Ramage. Seth Hampson, and Blaise Agüera y Arcas. Communication-efficieee learning of deep networks from decentralized data. In Aarti Singh and Xiaojin (Jerry) Zhu (eds.), Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, 20-22 April 2017, Fort Lauderdale, FL, USA, vol- ume 54 of Proceedings of Machine Learning Research, pp. 1273-1282. PMLR, 2017. URL 17m.mml
mww. wtw.eeiiiing.mm..........
Liang Peng, Nan Wang, Nicha C. Dvorek, Xiaofeng Zhu, and Xiaoxiao Li. Fedni: Federated graph learning with network inpainting for population- disease prediction. CoRR, abs/2112.101ee 2021. URL http:::://axxvv.v...... abs 221./211111.1 10166
Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. In Nassir Navab, Joachim Hornegger, William M. Wells III and Alejandro F. Frangi (eds.), Medical Image Computing and Conputer-Asiisted Inter- vention MICCAI 2015 18th International Conference Munich, Germany, October 5 9, 2015, Proceedings, Part III, volume 9351 of Lecture Notes in Computer Science, pp. 234-241. Springer, 2015. doi: 10. 000007797888331-245544444 0 978-3-319-24574-22
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rad. Collective classification in network data. AI Mag., 29(3);33-106, 2008 doi: 10. 10.9/m//. v2913.2157. httts:tt::////
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski. and Stephan Güinnemann. Pitfalls of graph neural network evaluation. CoRR, abs/1811.05866 2018. URL http:://axiv.
org/ 1811. 05868
Mingyue Tang, Pan Li, and Carl Yang. Graph auto-encoder via neighborhood wasserstein recon- struction. In The Tenth International Conference on Learning Representations, ICLR 2022, Vir- tual Event, April 25-29, 2022. OpenReview.net, 2022. URL httpss://penreevier net/ 2
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. BRLhhtps::/ wttp://i/.pp.eeeee.e.e.e URLnttp:://peeeee...er net wttp:///oommmdddd
Cédric Villani. Optimal transport: old and new, volume 338. Springer, 2009.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Ste- fanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Jen- nifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, ICMI. 2018, Stockholmsmüssun, Stockholm, Sweden, July 10-15, 2018, vol- ume 80 of Proceedings of Machine Learning Research, pp. 5449-5458. PMIR, 2018. URL. www.essmmm.r...mmm
ktttp://pee httt:://proceedingg mll. www.....rss......mm..m...m..m..e pwwss/ressseee. /v00 11880xuul/e xul8c. html
Yuhang Yao and Carlee Joe- Wong. Fedgen: Convergence and communication tradcoffs in feder-
ated training of graph convolutional networks. CoRR, abs/2201.114333, 2022. URL https:
//arxiv.cm //aaxii.or//aba.e...... /2001. 12433
Ke Zhang, Carl Yang. Xiaoxiao Li, Lichao Sun, and Siu-Ming Yiu. erated learning with missing neighbor generation. In Mare Aurelio
Subgraph fed- Ranzato, Alina
11

---

Under review as a conference paper at ICLR 2023
Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Ad- vances in Neural Information Processing Systems 34: Annual Conference on Neural In- formation Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp. 6671-6682, 2021. URL htt.httss://prrceedii neurips cc/ wwtppppppppppppppetttttt /2021/r/222///// /
Kaixiong Zhou, Xiao Huang, Yuening Li, Daochen Zha, Rui Chen, and Xia Hu. To- wards deeper graph neural networks with differentiable group normalization. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tice -ien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020a. URL 3Bddcballsee2aaccoo222ccca -bw.rrtttbsstttt.ttt
new..eeiiinnnnn...nn....e..... htc/paper/222//aasht
Kaixiong Zhou, Xiao Huang, Yuening Li, Daochen Zha, Rui Chen, and Xia Hu. To- wards deeper graph neural networks with differentiable group normalization. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 4917-4928. Curran Asso- ciates, Inc., 2020b. URL /t//ssttss////rrceddnnggg neurips cc wttppr/w.sss.ccpppe/////////e/
/ctpppppr/222//51le
A FED*GNN FOR GCN MODEL
The rooted tree recovers the structure- sanuc information of one node. However, in practice, the last layer of the rooted tree is not fully splitted, which change the degrees of nodes the last two layers. Specifically, the nodes in the last layer has constant degree 2 (including self-loop) and the nodes the second to last layer has a constant degree (including self-loop), which affects the encoding process models such as GCN (Kipf Welling 2017). Surprisingly, we can slightly change the encoding process and manipulate the edge weight to solve the problem.
Recall that the representation of GCN model is formulated H (R) ((()). In the 1-hop neighborhood reconstruc-
(EjENiU()) ((X))) 11 tion phase, instead of sending EmeNpy 1=(c(m)]=m directly, the passive client P. sends Emex." 1z(c(m)] Pen to the active client, and ΣmENç" Ng(c(m)] [=(c(m)]EJEN.. V(N in the 2-hop neighborhood reconstruction phase. With decoder, get two set N,P) and Hi (ESENGAO VINS++ im &N We represent
G. ViNm++1
the h-hop neighbors
3..2 and 2-hop neighbors as EjeN. IA
Vi-i Vmn E V(NG++I)
We further manipulate the edge weight between node and the generated neighbor nodes including 1-hop neighbors m E A and the corresponding 2-hop neighbor jm connecting to m. For pair of nodes A, B, we denote the message passing from A B A + B. In undirectd graphs, message passing between two nodes bidirectionally, hence we present the weights of A + B and B + A separately. We have the following results:
Direction
Weight
Direction
Weight
+ m
m +i
(NNI-I) (mml+))
v3 N
/
Im - m
A
((((N..
Note that the message passing from m - jm does not affect the encoding process for note i; we omit it here.
12

---

Under review as a conference paper at ICLR 2023
Proof. For easy of presentation, for every node V, denote D, the degree of including self loop. For a two layer GCN model, we have:
0. = E VD;-
Dm 02 E
1
33 (2((1)))()))
VDm D3
mENiU()
JENmU(m)
=0il( Dj
02((
+
Σ
VD, VD 1y
Di
Dm
JEN.
02(
02((
Im
+
Σ jeNm
VD D, 2 (
VD.
Dm
Dm
mEA,
In our methods, we manipulate the edge weight and features of neighbors, such that encoding result the Equation 9
V3r, waa)
ń = a (T
02((
24 +
Σ
Di
Di
v3D;
VDm
JEN,
V3Im
V32,
v3D, 02((
(10)
Dm VDm
D; VDm
m mEN,
v
V2n
W W(()))
22
VDJ
JEN
Note that is the ReLU function, rearranging the above formula, we can get Equation 9
B PROOF OF THEOREM 4.
Theorem 4.1 is reproduced from Theorem 2.1 in Lu & Lu (2020), which is stated as below:
Theorem B.1. (Theorem 2. in La & Lu (2200). Let P and be the target and the source distri- butions respectively, both defined on Rá Assume that Q is absolutely continuous with respect to the Lebesgue measure and Ex-Pl X co, it holds that for any given approximation error E, there exists positive integer n O g and fully connected and feed-forward deep neural network u(() of depth I, = [lgg n] and width N- 2 2llog2 n), with d inputs and single output and with ReLU activation such that Wi ((Vu) 2, P) S.
To prove Theorem 4.1 we only need to verify the conditions presented in the above theorem. We need to show that p= PP has a bound Ex-p| X < oo and Q is absolutely continuous with respect to the Lebesgue measure. Furthermore, we also need to show the connection between Wi(,.) and :2(..))
Proof. P= P; has a bounded 3-order moment because the support P is in a bound space Rd
Q Q, is absolutely continuous with respect to the Lebesgue measure because P; is absolutely continuous with respect to the Lebesgue measure.
Last, we show the connection between Wi (:.)) and Wy(..)). Note that the support P. P. is bounded, i.e., Vo E supp(P), there exist C' E co, s.t. ||0|| < C. According to (Lu Lu 2020). Q = (Vu) Q also has bounded support. Wlog, we have 48 E supp(@), ||ô]| < C. Then, we show that
13

---

Under review as a conference paper at ICLR 2023
1/xx2 1 1 (3222122(2222)
@) inf
,Er(P,2)
2x2'
[/ 2 112 - 2112211(,227)
- 2C
inf
2ET(P.K)
[/ 17 21 d7 (2,
s 2C dd
inf TEr(P.0)
2C 3CV
< 20. e.
As C and ddz are constant, we have (P, 2) 0 The first inequality because
| 22 I | + 1 = 2C. The second inequality is because
dx
inf (E(():))
1 11 dy (2, 2*)
= lim
v de 2
drs - (z.Z))
Z
1-000
2x2'
(There exists sequence of measures (x) achieving the infimum)
/ 2x2'
2 lim
1 7111 d76 (7, )
inf (P.(P
[ 1 111 dr (2,
C DATASET STATISTICS
In this section, we present details of the datasets used in our experiments. We conduct experiments on three citation network datasets, Cora (Sen et al. 2008), MSAcademic (Shchur et al. 2018), and DBLP (Fu et al., 2020). We summarize the statistics of the datasets in Table Mcanwhile, summarize the statistics of subgraphs obtained by the Louvain algorithm (Blondel et al. 2008) in Table & Statistics of the datasets, where [V] represents the number of nodes, |E| represents the number of edges, | represents the number of features and Classes the number of label classes.
also
Dataset
[
|
Classes
Cora MSAcademic
2,708
5,429
1,433
18,333
81,894
6,805
15
DBLP
17,716
52,867
1,639
Table 4: Statistics of subgraphs, where [V] represents the average number of nodes, |g] represents the average number of edges and A|E| is the total number of the cross-client edges.
Dataset
Cora
MSAcademic
DBLP
M=5
M=10
M=15
M=5
M=10
M=15
M=5
M=10
M=15
V
542
271
181
3667
1833
1222
3543
1772
1181
946
443
254
13933
6099
3409
8898
4358
2826
A
697
1002
1613
12230
20906
30765
8379
9287
10471
D HYPER-PARAMETER SETTING
In Table we present the descriptions of parametrss and the range of them used our experiments. The details of hyper-parameters settings used in experiments shown in Table
14

---

Under review as a conference paper at ICLR 2023
Table Hyper-parametee range of GNN and Decoder
Hyper-parameter
Description
Range
Learning rate Dropout rate L2 regularization Hidden dimension
The learning rate for Adam optimization
[0.1, 0.01, 0.001]
The Dropout rate
[0.0, 0.25, 0.50, 0.75] [1 [1-10-3, 10 -
The L2 regularization
The hidden layer dimensions of GNN
[16, 32]
M
Number of clients in federated learning
[5. 10, 15]
Epoch
Training epochs, also federated learning rounds
200
Delta
Louvain split parameter
40
Hyper-parameter
Description
Range
Max node degree
[3, 5, 10, 15, 20]
Pool size
The pool size of Decoder
[2, 3, 4]
Blocks
Blocks number of Separator
[4, 5]
Separator Ir
Learning rate of Separator training Learning rate of Predictor training training epochs of Decoder
1- 1-1033
Predictor Ir
1 10-2
Decoder epoch
[20, 50, 100, 200]
Table 6: Hyper-parameter setting
GCN
GraphSAGE MSAcdemic
Hyper-parameter
Cora
MSAcdemic
DBLP
Cora
DBLP
Learning rate
0.01
0.1
0.01
0.01
0.01
0.01
Dropout rate
0.5
0.0
0.75
0.5
0.0
0.75
L2 regularization
10 3
10
1
10
1 10-3
10
Hidden dimension
16
16
32
16
16
32
Epoch
200
200
200
200
200
200
Delta
40
40
40
40
40
40
d
10
10
10
10
10
10
Pool size
3
2
3
3
Blocks
Separator Ir
1 10-3
1 10-3
1 10-3
10-3
1 10-3
10
Predictor Ir
1 10
1 10
1 10
1 10
1 -00
1. 10
Decoder epoch
200
200
200
50
20
100
15

---

Under review as a conference paper at ICLR 2023
Louvain Split
Random Split
Louvain Split
Random Split
1.4
heaning
1.2
Cernal karning
1.0
reshophhl
1.0
Fadieg
808
3.8
30e
62
Pushig-Phl
Tren
Feslig Podlog
0.6
0.4
120 140
20 40 60
80
100
120 140
0.0
20
100 120 140
Train Epochs
Treen Epeciai
(a) Train accuracy curves
(b) Loss curves
Figure 5: Average accuracy curves and loss curves on DBLP. M 10
17:6
$1.04
Number of Cients
Number of Cients
10
5350
TacAkg
Fastig
Loodl Doods
Locol Dccodior
Decader
Fedemned Decrrder
70
75
80
85
70
75
80
85
Teal Acouracy 194)
Tesll Accunasy (9)
(a) Decoders on Cora
(b) Decoders DBLP
Figure 6: Decoder training methods study
E ADDITIONAL EXPERIMENTS
E.I CONVERGENCE STUDY
In this subsection, we repeat five times experimental runs and show the average (a) train accuracy curves and (b) loss curves in Figure demonstrate the convergence of our model. In addition to the Louvain split method applied in the previous work (Zhang et al.) (02T). we also apply the random split method, which randomly selects nodes to form subgraphs and maintains only the edges between the selected nodes in the subgraph.
The results show that Ged model achieves almost the same convergence as the FedAvg- -ull baseline. Since nodes are randomly selected form subgraphs, there will be more cross-client edges in the subgraphs under the random split method. Therefore, our experimental results will be more evident under the random split method.
E.2 DECODER TRAINING METHODS STUDY
In this subsection, we study the training methods of the decoder by comparing the test accuracy obtained under different decoder training methods. We tried locally trained decoders and federated trained decoders and set baselines FedAvg for comparison. We conduct experiments on Cora and DBLP datasets using the hyper-parameters setting in Tablç As shown in Figure 6 the federated trained decoder only slightly better that the locally trained decoder, showing that the decoder has a good generalization ability to decode information from unseen data.
E.3 COMMUNICATION COST
Communication cost is widely recognized as major bottleneck for federated learning. Particularly in federated graph learning, additional communication across clients may be required recover missing neighborhood information. Recall that each client recursively aggregates information from its neighbor nodes during the information transmitting process our methods; the communication is O(ndK), where is the number of nodes, d is the average degree of all nodes, and K is the number of layers of a GNN model.
We conduct experiments to evaluate the communication cost on real-world datasets with the base- lines of FedGCN (Yao & Joe- Wong 2022) and FedGraph (Chen et al. (022). which have the com- munication cost of O(nd") and O(ndT', where T >> k is the number of iterations. We ignore the influence of feature dimension since all methods can reduce the feature dimension in advance. The
results presented in Figure
16

---

Under review as a conference paper at ICLR 2023
Cora
MSAcademic
DBLP
to
10"
Communcction cast
to"
10'
10"
10¹
10'
10*
16"
10"
to
10²
10"
2
3
4
5
2
3
4
2
Number of layers
Number of layers
Number
FedECN-5
FadGON-15
FadPGNN-110
Fantrraph-5
FodGraph-155
FadPONIN-5
FudPENN-15
FodGraph-110
Figure 7: Communication cost of Fed GNN in comparison with FedGCN (Yao & Joe-Wong 2022 and FedGraph (Chen et al. 2022 for training models with different number of layers and different number of clients.
Cora
MSAcademic
DBLP
1.28
15
1.00
buildingte
building time
ring Sine
(s)
Time
Time
0.50
0.25
0
8
3
Number of layers
Number of layers
Number layers
Figure 8: Average tree-building time and training time of all clients.
We vary the number of GNN layers and the number of clients. It shows that our methods have the lowest cost in all settings. Meanwhile, partitioning clients requires more communication costs since more nodes have missing neighborhood information.
E.4 EFFICIENCY OF CONSTRUCTING ROOTED TREES
Constructing the rooted tree for node is simple. Algorithm presents the pseudo-code of the process for one tree. It mainly consists of sequence of predicting processes of the decoder d. For each vector E H the decoder takes as input and outputs G and H (line 9 in Algorithm 2)- The K + 1-th layer of the tree is constructed by generating nodes with features corresponding to elements in G and connecting them to g corresponding to
In practice, the vectors in the set 11 can be fed to the decoder simultaneously. Meanwhile, we can even input all H's 's (of different root nodes) into the decoder to construct the rooted trees simulta- neously. To that end, building rooted trees of K layers for all nodes requires the decoder to predict only - times.
We conduct experiments evaluate the efficiency of the tree-building process and report the average tree-building time and training time for all clients. All experiments are implemented on a server equipped with an A100 GPU, The results are presented in Figure g shows that the tree-building time increases as the number of layers grows. Indeed, as the number of layers increases, the number of generated nodes increases exponentially. hence requiring more time. However, is still efficient to build rooted trees for all nodes, which only requires few seconds.
F ADDITIONAL PROTOCOL AND ALGORITHM
17

---

Under review as a conference paper at ICLR 2023
Protocol 1: Neighbor information transmission
Input: Pp has data Gp (Vp: Ep, Xp), [M], X, { Vi E vp); depth K; neighborhood
function N : + 2 the set of passive participants C, (Pp jm NT s.t. p c(m) for each i E U 1
Output: Information of k-hop neighbors f. k [K], i u Vp.
for i E UM V/p do
[1, 1 < Z4
for Pp E C. do
Pp sends of + EmENDo 1 1p(c(m)lum to Po(o)
end
f! E Epeec &b
1 - (PPeC((Peca)
10
1 t mh
lt
11
end
12
for k = 2. do
for i E UM Vp do
13
14
for P, E C, do
Pp sends oe EmEN.oD Ip(o(mi)ut Polo)
16
end k == 2 then
f + Σp,ec. 1/ WV f!--
- +- EppECLU(PocL o5 - (1, + (N?)) 16-2
n/t t nx 8
21
else
f:t + Σp,eC, op - (W, - 1) ff pk=2 |N. - - k-2
22
1 + Eppecc(((o) oi (W, + WN - 1) 1. k-2
23
t + 2 -K
24
end
end
end
18

---

Under review as a conference paper at ICLR 2023
Algorithm 2: Rooted tree construction
Input:
Node and its neighbor information f! f? ..... f.K decoders Φk. h E [K 1] trained
in advance; An operator ZIP which iterate over two set in parallel and producing a set of tuples with an item from each one.
Output: The rooted tree for i.
G {z,}
H {CONCAT(F) fi.....,Kk)
for k = K 1] do
Gh <
1K-1 + 0
for (gh ,1²)) E ZI HH0kt do
G. C.H-ople (x(1²)
G*
10
Hk+1 + g
11
12
Generating nodes with features corresponding elements in G and connecting them
13
if = K then
Generating nodes with features corresponding to elements in H and connecting them to gx k-1
end
16
end
17 end
19


Reviews:
[{"review_id": "pv_dhO7fGi", "reviewer": "Reviewer_53S9", "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": "This paper tackles the subgraph-level Federated Learning (FL), where each client has the individual subgraph of the larger global graph. Then, to tackle this task, the authors propose to reconstruct the neighborhood information of the subgraph based on the rooted tree structure. In particular, the rooted tree for the particular node in the local client has the information for its neighboring nodes in the other clients, which is done by aggregating information of nodes in that other clients as well as the nodes in the local client. After that, the authors decode the neighborhood structure of the subgraph with the information in the rooted tree. The experimental results show that the proposed method outperforms the subgraph FL baseline, namely FedSage+. ", "summary_of_the_review": "The biggest concern is that the proposed method is not applicable to real-world scenarios (See first two weaknesses). Also, the evaluation of using one subgraph FL baseline is weak, and the analysis of communication costs is further required. Therefore, I cannot recommend the acceptance.", "strength_and_weaknesses": "### Strengths\n* The concept of the rooted tree structure for encoding the neighboring information for nodes in both the local client and the other clients is interesting. \n* The experimental results show that the proposed method outperforms the recent subgraph FL baseline, namely FedSage+.\n\n### Weaknesses\n* The proposed subgraph FL method is unrealistic, and not applicable to real-world scenarios. In particular, for the node in the local client, the authors define its neighboring nodes in other clients, and use the information of nodes in other clients based on the edge between the local client and the other clients. However, in privacy-preserving FL, since we cannot share information across clients, we cannot have the information whether two nodes in two different clients have the edge or not.\n* Also, the proposed information transmitting process between clients is unrealistic. To share k-hop neighboring information across clients, every client participating in FL should be in the same forwarding process. In other words, when the proposed method shares the information of 2-hop neighborhoods, every client should calculate the 1-hop neighborhood information and share them simultaneously. However, in realistic FL, it is unnatural to share k-hop neighborhood information of all clients simultaneously (i.e., one particular client may update k-hop neighborhood information, meanwhile, the other client may update (k-3)-hop neighborhood information). \n* The authors point out that one particular limitation of existing subgraph FL is the communication cost. However, since the proposed method considers k-hop neighborhoods of the root node and consequently all clients should recursively transmit k-hop node information, it seems the proposed one is also highly slow. \n* The compared baseline is weak. The authors compares only one subgraph FL baseline, namely FedSage+. I am wondering the authors can further compare the discussed relevant works in the paper: Peng et al., 2021; Yao & Joe-Wong, 2022; Chen et al., 2022.\n* There is a related work [1], which tackles the missing neighborhood problem, yet does not rely on neighborhood expansion. This work should be discussed. \n\n---\n\n[1] Personalized Subgraph Federated Learning, arXiv 2022.\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "X8LpnGyJ6V", "reviewer": "Reviewer_SQ7X", "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": "The authors develop a method for federated learning of deep GNNs. The main idea is to reconstruct the neighborhood information of nodes using a graph structured named rooted tree, and use the rooted tree for encoding neighborhood information. ", "summary_of_the_review": "The paper proposes to build rooted tree for each node in a GNN for federated learning. The approach in general makes sense. However, the practicality of the proposed method might be somewhat limited.", "strength_and_weaknesses": "The authors claim that the node embedding obtained by encoding on the rooted tree is the same as that obtained by encoding on the induced subgraph surrounding the node. This is captured in proposition 1. The proof is included in Appendix A. One suggestion is, given the importance of the proposition, it is necessary to include at least a sketch version of it in the main doc. \n\nI don’t quite get the challenge of the proposed setting. This paper assumes that every node knows its one-hop neighbors, no matter whether the neighbors are in the same host or different host. Is that a reasonable assumption? If yes, the information can of course help to identify k-hop neighborhoods. Is that a challenging setting? \n\nThe authors criticize Yao & Joe-Wong, 2022 for making the assumption that the weight matrix is calculated in advance. Which weight matrix? There are no detailed explanations. Given a similar idea were proposed in that paper, it is important for the authors to explain the underlying reasoning.\n\nBuilding a root tree for each node is expensive. The authors do not seem to have experimental evaluations to evaluate the efficiency of the proposed method. What were the criteria of experiments for comparing different methods? The same amount of running time, or same number of iterations? ", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "2wN19ZwEgA", "reviewer": "Reviewer_YSgt", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "The authors propose a federated learning model for learning deep GNNs to solve node-level prediction tasks. Their idea is based on reconstructing the neighborhood information of nodes that accounts for neighborhood graph structure as well as their features in a principled manner. For aggregating neighborhood structure information, they proposed a rooted tree graph approach, whose node embedding is the same as the node’s eco-graph. Reconstructing feature-based information for a given node is handled by an encoder-decoder framework with some information loss. Their experiments show improvement over SOTA.\n\nUpdate: The authors have addressed my questions to certain extent and I've updated my ratings to reflect the same. Although, due to my lack of breadth in federated learning, the confidence in my assessment is on the lower end.", "summary_of_the_review": "I think this work is novel, clearly presented and interesting. Although, I am not entirely confident about the scalability of their approach and have listed some of my concerns in the comments above. I will be happy to reconsider my ratings after replies from the authors. ", "strength_and_weaknesses": "Pros:\n1. The related works are well explained with their strengths and drawbacks nicely pointed out. \n2. The construction of the rooted tree and then the procedure to do k-hop neighborhood reconstruction seems correct, though I have not verified the proofs given in the Appendix.\n3. The set of experiments chosen are well thought-off, although I do share certain concerns with the size of the datasets. \n\nComments: \n1. (Fig error) In fig.1(b) the node below (i) should be (m2). Also, please number all the equations.\n2. Can you please comment on the scalability of the method? The experimental datasets are very small sized graphs. In general, it will be of interest to the readers to get a sense of the time required for rooted tree construction, aggregation steps etc.? \n3. How does the memory requirement scale while creating the rooted tree for every node? Do you foresee issues with larger graphs in this regard?\n4. Any best practice on choosing the value of K (layers)  ?\n5. How can one do BFS vs DFS tradeoff while aggregating neighborhood information using the rooted tree graph structure? \n\nI think this work is novel, clearly presented and interesting. Although, I am not entirely confident about the scalability of their approach and have listed some of my concerns in the comments above. I will be happy to reconsider my ratings after replies from the authors. \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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject