Decoupled Subgraph Federated Learning
Authors: Javad Aliakbari
Johan Östman
Alexandre Graell i Amat
Venue: ICLR 2025 Poster (2025)
Keywords: Federated Learning
Subgraph Federated Learning
Inter-Connected Graphs
GNN
Decoupled GCN
Primary area: learning on graphs and other geometries & topologies

Abstract: We address the challenge of federated learning on graph-structured data distributed across multiple clients. Specifically, we focus on the prevalent scenario of interconnected subgraphs, where inter-connections between different clients play a critical role. We present a novel framework for this scenario, named FedStruct, that harnesses deep structural dependencies. To uphold privacy, unlike existing methods, FedStruct eliminates the necessity of sharing or generating sensitive node features or embeddings among clients. Instead, it leverages explicit global graph structure information to capture inter-node dependencies. We validate the effectiveness of FedStruct through experimental results conducted on six datasets for semi-supervised node classification, showcasing performance close to the centralized approach across various scenarios, including different data partitioning methods, varying levels of label availability, and number of clients.

of the most prevalent scenarios, Published as a conference paper at ICLR 2025
DECOUPLED SUBGRAPH FEDERATED LEARNING
Javad Aliakbari
Johan Östman
Alexandre Graell Amat!
Chaameers University of Technology
Al Sweden
ABSTRACT
We address the challenge of federated learning on graph-structured data distributed across multiple clients. Specifically, we focus on the prevalent scenario of in- terconnected subgraphs, where interconnections between different clients play a critical role. We present novel framework for this scenario, named FEDSTRUCT, that harnesses deep structural dependencies. To uphold privacy, unlike existing methods, FEDSTRUCK eliminates the necessity of sharing or generating sensitive node features or embeddings among clients. Instead, it leverages explicit global graph structure information to capture inter-node dependencies. We validate the fectiveness of FEDSTRUCT through experimental results conducted on six datasets for semi-supervisee node classification, showcasing performance close to the cen- tralized approach across various scenarios, including different data partitioning methods, varying levels of label availability, and number of clients.
INTRODUCTION
Many real-world data are graph-structured, where nodes represent entities and edges capture their re- lationships. For example, anti-money laundering, nodes symbolize accounts and edges correspond to confidential transactions.
Graph neural networks (GNNs) are specialized neural networks for graph-structure data, showing success in fields such as drug discovery, social networks, or traffic flow modeling (Stokes et al.) 2020 Fan et al. 2019: Jiang and Luo| 2022). In many practical applications, graph data inherently distributed across multiple clients, i.e., the global graph encompasses multiple, non-overlapping subgraphs. For example, in anti-money laundering, local graphs represent internal transactional networks of financial institutions.
For this and many other applications, data sharing among clients is often restricted due to privacy, regulations, proprietary restrictions. Federated learning (FL) (McMahan et al. 2017) offers a way to utilize global graph-structured data while maintaining data privacy. Various flavors of federated GNNs exist (Liu et al.) (2022). This paper focuses subgraph federated learning (SFL) (Zhang et al. (021). where clients hold disjoint subgraphs that together form a global graph with interconnections between the different local subgraphs.
Training a GNN involves aggregating feature represen- lations of neighboring nodes to generate more expres- sive embeddings (Kipf' and Welling 2017 Hamilton et al. 2017: Veličković et al.) 2018) In SFL, a key challenge facilitating training when some neighboring nodes, whose information is crucial for training, reside in other clients without sharing raw data across clients. This setup falls under the well-known communication- aerracy-accuraae trilemma (Chen et al., 2020) which necessitates solutions that preserve the privacy of lo- cal data and supports minimal communication overhead between clients and the central server, while achieving high accuracy for the end-to-end task.
100
Camsos CXM Ripee boand)
63
7g
83
6R86
5454 49
41.4411
3E3T
3636
Cora
Chamellon
Amazon- Ratings
Figure Node classification accurncy. For all datisetss, FEDSTRUCT exhibiis performance close to the centralized setting (CENTRAL CNN).
Several approaches have been proposed to address this trilemma (Zhang et al. 202T) (FEDSAGEH
(Peng al. 2022) (FEDNI), (Chen et al., 2021 Du and Wu 2022 Lei et al. 2023) Yao al. 2024

---

Published as a conference paper at ICLR 2025
(FEDGCN), (Back al. 2023 (FEDPUB). However, except (Back et al. 2023). these methods rely
on sharing node features or embeddings between clients, which raises significant privacy concerns. Moreover, there are challenges related to performance. as the global model needs to accurately aggregate distributed knowledge, and communication cost, as transmitting features or embeddings between clients be resource-intensive.
To address privacy risks, inspired by/Cui et al. (022)) we observe that the global graph structure alone can be highly informative and is less sensitive than node features. This opens up the possibility of training robust classifiers without exposing raw data, achieving high performance that surpasses that of standard FL.
We address the problem of subgraph FL for node classification within global graph containing multiple, uon-overlapping, subgraphs belonging different clients. More preciscly, we consider the prevalent scenario where wross-uubgraph interconnections are known (such as in transaction networks). However, we assume that neither the server nor the clients have knowledge of the global graph connections the node features, i.e., the node features and intra-connections for each subgraph remain private. Our contributions include:
Our contribution.
Building on the observation above, we propose a novel SFL framework, named FEDSTRUCT, that exploits deep structural dependencies and tackles the key challenges of privacy, performance, and communication cost. To safeguard privacy. FEDSTRUCT decouples graph structure and node feature information: Unlike existing approaches, FEDSTRUCT eliminates the need for sharing or generating node features or embeddings. Instead, leverages global graph structure information to capture inter-node dependencies among clients. FEDSTRUC minimizes structural information exchanged between clients, limiting privacy leakage and reducing communication complexity while achieving utility close to centralized approach.
We introduce a method to generate deseddepnndent node structure embeddings, coined HOP2VEc that adapts to the graph and demonstrates competitive performance compared to task-agnostic methods such as NODE2 VFC (Grover and Leskovec 2016). graphlet counting (Pržul 2007), or
the technique used in FEDSTAR (Tan et al. [2023).
By integrating a decoupled GCN and leveraging deep structural dependencies within the global graph, we effectively tackle the semi-supervised learning scenario. Further, FEDSTRUCT relies on non-local neighbor-extense
and inter-layer combination, techniques commonly used to handle heterophilic graphs (Zheng et al. 2022). To the best of our knowledge, FEDSTRUCT is the first
SFL framework capable of handling heterophilic graphs.
We validate the effectiveness of PEDSTRUCT on six datasets for semi-supervised node classifi- cation, showcasing excellent performance close centralized approach in multiple scenarios with different data partitioning methods, availability of training labels, and number of clients. Particularly. FEDSTRUCT yields outstanding performance in scenarios with limited number of labeled training nodes. In heavily semi- semi-supervised settings, it significantly outperforms both FRDSAGE: and FEDPUR. Moreover, it achieves peformance close to that of FEDCGN (which does not provide privacy and assumes server access to the global adjacency matrix) (see Figure IT The source code is publicly available in the Github Link
RELATED WORK
SFL with no knowledge of cross-subgraph interconnections. Relevant works include Zhang
cet al. 2021) (FEDSAGE+), (Peng et al. (022) (FEDNI), (Zhang et al. 2024) (FEDDEP), (Back al. 2023) (FEDPUB), and Zhang et al. 2022 Liu al. 2023). FEDSAGE+ the first method for
subgraph FL. generates features for missing 1-hop neighbors across subgraphs using a variational
autoencoder. FEDNI extends this by using GAN generate higher-quality node features. The in-painting idea is further expanded to handle heterogeneous graphs in (Zhang et al.) 2022) and missing links in (Liu et al. 2023). FEDDEP builds on FEDSAGE+ by generating embeddings that methods, capture deeper structural information (up to k-hop neighbors). A limitation of in-painting like FEDSAGE+ and FEDNI, is the unpredictable quality of the generated features, which can either lead to poor models expose sensitive information through confident predictions. FEDPUB avoids in in-painting by employing personalized aggregation based on the functional similarity between client models.
SFL with knowledge of cruss-subgraph interconnections. Relevant works include Yao et al. 2024 (FEDGCN), (Lei al. 2023) (FEDCoG), and (Chen al. 2021 Du and Wu 2022). FEDGCN
2

---

Published as a conference paper at ICLR 2025
securely transmits cross-client neighbor information once before training, preventing the server from accessing local data but exposes aggregated node features to neighboring clients. This can risk data leakage since node features often contain meaningful patterns. FEDCOG decouples local subgraphs into internal and border graphs, with graph convolution divided between them. It requires sharing intermediate embeddings, effectively performing a convolution on the global graph. Other methods employ sampling techniques to address the challenges of SFL (Chen et al. 2021 Du and Wu (202)).
In summary, all prior approaches rely on sharing original or generated node features or embeddings (except FEDPUB) and assume homophily, which often does not hold in real-world settings.
Structural information in GNNs. Recent studies have revealed limitations in the capacity of GNNs to capture the structure of the underlying graph. To overcome this obstacle, some works explicitly incorporate structural information into the learning, showing superior performance compared to standard GNNs (Bouritsas et al., [2023] Tan et al. (023). To increase GNN's representation power, Bouritsas et al. (2023) introduces structural information to the aggregation function. The authors demonstrate that the proposed architecture is strictly more expressive than standard GNNs. FED- STAR (Tan et al.) 2023) presents an FL scheme where clients share explicit structural information to enhance local performance. No work has leveraged explicit structural information in SFL.
3 PRELIMINARIES
Graph notation. We consider a graph denoted by 9 - EV,E, Y)), where V is the set of n nodes, E the set of edges, X e Raadd the node feature matrix, and Y E Raxe the label matrix. For each node E V, we denote by Dr E Rd its corresponding feature vector and by yv E IR its corresponding one-hot encoded label vector. We consider a semi-supervised learning scenario and denote by V C V the set of nodes that possess labels. The labels of the remaining nodes are set to O. We also denote by (g)() = [u[(u, v) E E the neighbors of node
For given matrix M, let Ma. be its (u, v)-th element. The topological information of the whole graph is described by the adjacency matrix A E Rax*, where Aur 1 if (u, r) E E. We define the diagonal matrix of node degrees as D E RT*", where Dan = Σn Aue- Furthermore, we denote by
Á = A + I the solf- adjacency matrix, and by Å = D A the normalized self- adjaceney matrix, where dun = Evev Awe. We also define [m] = mm).
GNNs. Modern GNNs use neighborhood aggregation followed by learning transformation to itera- tively update node representations at each layer. Let hi be the feature embedding of node at layer 1, with h Ty. At layer E [L] of the GNN we have h (!) (N) AGG ({ [1(-")) Vu E Ng(C0)
Nott) O0). where O AGG! and !PD denote the learnable weight matrix, aggregation function, and update function associated with layer I, respectively.
and h. ( (1) (n!-1), h (1)
Decoupled GCNs. A significant limitation of GNNs is over-smoothing (Liu et al. 2020; Dong et al. 2021), which results in performance degradation when multiple layers applied. Over-smoothing is characterized by node embeddings becoming inseparable, making challenging to distinguish between them. This phenomenon is attributed the interweaving of the propagation and update steps within each GNN layer (Liu et al.) 2020 Dong et al.] 22021). To address over-smoothing, well-known solution (hereafter referred as decoupled GCN) is decouple the propagation and update steps (Liu et al., 2020 Dong et al. 2021). Let fe (-) be a multi layer perceptron (MLP) network with learning parameters O. decoupled GCN can be described with the model
H(L) AF)(X),
where (X) = (((f) Vu E V), with || being the concatenation operation, and denotes the transpose operation. A is the L-hop combined adjacency matrix and it can be computed as
1.
Ā -
A
1=1
The elements of reflect the proximity of two nodes in the graph, with 3 determining the contribution of each hop. Parameters (8:) f/ can be set manually or learned during training.
3

---

Published as a conference paper at ICLR 2025
4 SYSTEM MODEL
We consider a scenario where data is structured according to a global graph 9 = (V, EV,E X, Y), which is distributed among K clients such that each client owns smaller local subgraph. We denote by Gj = (V,, , E,, E, X,, Y;) the subgraph of client i, where V; C.V is the set of nodes that reside client i, referred set of nodes that do not reside in client but have at least one connection to nodes in V.. We call these nodes external nodes. Importantly, client does not have access the features of nodes in V Furthermore, & represents the set of edges between nodes owned by client (intra-connections), & the set of edges between nodes of client and nodes of other clients (interconnections), X; E Rmxxd the node feature matrix, and Y; E R x the label matrix for the nodes within subgraph g, and we denote by Vi2 the set of nodes that possess labels. Similar to graph G. Ngg. (v), A (1) and ( denote the set of local neighbors, the local adjacency matrix, and the local diagonal matrix for subgraph G,
as internal nodes, for which client i knows their features. V is the
4.1 FEDERATED LEARNING
The FL problem can be formalized as learning the model parameters that minimize the aggregated loss across clients,
e = arg min (()),
(3)
with
K O)), and (( = Σ CE(y 9w),
((0) = 1
(4)
VEV.
where CE the cross-entropy loss function between the true label y, and the predicted label De.
The model 0 is trained iteratively over multiple epochs. At each epoch, the clients compute the local gradients (o and send them to the central server. The server updates the model through gradient descent,
K
θ レ 0 (VoL(O,,
Vol(O)= =
VoL(
(5)
V
where À is the learning rate.
5 FEDSTRUCT: STRUCTURE-EXPLOTIIE SUBGRAPH FEDERATED LEARNING
In this section, we introduce FEDSTRUCT, a novel SFL framework designed to leverage inter-node dependencies among clients while safeguarding privacy. The central concept of FEDSTRUCT is to harness explicit information about the global graph's ss underlying structure to improve node label prediction while ensuring that neither the server nor the clients have access the node features. More precisely, at each client i E [K], node prediction is performed for a node E V; as
g. = softmax h, + Zv²
(6)
where h is the node feature embedding (NFE) and nn is the node structure embedding (NSE), which encodes structural information of the nodes. Also Z = ((2], Ve E V), where Z is the structure embedding matrix (SEM) containing NSEs.
The NFEs h are computed locally at each client by a GNN model based on the local node features X; and local connection &, as
h FGNNe. (X, &, v) fe, (v).
The NSEs n, are generated based on the structural information of the global graph and clients need to collaborate to obtain them. Their is anticipated to enhance node classification compared the case of a classifier solely relying on NFEs. We describe how to generate NSEs in Sec. 5.1
The FEDSTRUCT framework is illustrated in Figure 2 and described in Alg. in App.
4

---

Published as a conference paper at ICLR 2025
Global
Local graple
Stractuoe secodia
Anguoeated local
Tedested baralig
Fal
Lieistrede
Sociase
stretree cotesting
Figure 2: Geneml design of the PROSTRUCT fimmeuork Global Graph: undartying graph consisting of interconeetted sibgraphs. Local graphs: cliests' subgraphi fiattuee labelsi, Structure encuding: Generales mode siructure for Augmented local graphs: Generate nede feature enbeddiings and mode structure embeddings. Federated Itarning: Federstdd learning step exploiting mode feature emheddings and mode strictare embhlddiggs.
sngmented with external
clients.
5.1 NODE STRUCTURE FEATURES, NODE STRUCTURE EMBEDDINGS, AND NODE PREDICTION
Node structure features. To generate NSEs, our proposed method relies node structure features (NSFs), which encapsulate structural information about the nodes, such as node degree and local neighborhood connection patterns, as well as positional information such distance other nodes in the graph. For each node E V. the corresponding NSF, E R is function of the set of edges E, S. @NSF (v. E). We define the matrix containing all NSFs as [|(sT] Ye V). Function QNSF can be defined through various node embedding algorithms, e.g., one-hot degree vector (Xu al., 2019 Cui et al., 2022), graphlet degree vector (GDV) (Pržulj 2007). NODE2 (Grover and Leskovec 2016). 6). or as in FEDSTAR (Tan et al., 2023) (we will refer to the NSF technique in TTan
ctt al. 2023) as FEDSTAR). We describe these different node embeddings in App. A In Sec. Sec. [5.5 we
introduce method to generate task-dependent NSFs, which, in contrast to methods such as GDV and NODE2 does not require knowledge of the global graph.
Node structure embeddings. Obtaining the NSEs requires structural information from nodes in other clients, which, with a standard GNN would involve numerous communication rounds during the training. By using decoupled GCN, it is possible precompute the necessary structural infor- mation for generating NSEs, thereby significantly reducing communication overhead. Consequently, FEDSTRUCT leverages decoupled GCN define the NSEs. Specifically, for client e [K] and node e E V,, let ge, (8,) be an MLP network applied to NSF 8,. Using Eq. Z is obtained as
Z = sGNNo, (S,E) = (S),
(8)
where Ge, (S)
(sw)), Yu E V), and Ā is the L-hop combined adjacency matrices for graph defined in Eq. Note that computing Z requires the L-hop combined adjacency matrix Å, which is not locally available. However, since A remains static during the training, it can be precomputed once before training begins. We address this in Sec.5.44
Node prediction. Upon the creation of the NSEs, each client computes the label predictions through Eq. For a node E V. expanding Eq. 8 leads to
2, Σ
Avn.oo (s.),
(9)
WEV
where Avn is the (v, w)-th element of Å. Using Eq.
9 in Eq, 6 leads to
ÿe softmax Σ
A Arago, (s.) ) + fa, (v))
(10)
NEV
Optimization. We optimize the learning parameters, 0 (0:](0,), by solving Eqs. 3 with y. in
Eq. using stochastic gradient descent. The local gradients are provided in Prop. 3 App.
5.2 DECOUPLED GRAPH CONVOLUTIONAL NETWORK AND FILTERING
Using a DECOUPLED GCN not only allows to precompute A, but also makes the GNN more adaptable to heterophilic graphs. To illustrate this, we see the decoupled GCN as a filter. Consider
the eigendecomposition of the normalized self-loop adjacency matrix Å (defined in Sec. 3
n
Á= ÜÂOT - EiaraT.
(11)
==1
5

---

Published as a conference paper at ICLR 2025
(a) The L hop combined adjacency matris of the Cora dasaset
(b) The pruned L hup combined adjacency matrix of the Cora datzset
Vigure Comparison
L-hop vombined uljacency the geuning, the mai community stuucuure of the graph preserved.
original pruned
Allhouh detnils lost
where ú is the j-th eigenvector corresponding to the eigenvalue dy. Using Eq. 11 Eq. obtain
Ā= Ú
Σ Bi dJ =ŪAT
1=0
where A a diagonal matrix with entries
À T(A) diag (T()))...,TT(i..
with ((x)= = -t Bix Therefore, Eq. 8 can be re-written as
z z= = (T())))
(12)
where ÜT, is the graph Fourier transform of imput signal Ge, (S). Eq. 12 corresponds to the filtering of the input signal (S) with the polynomial filter T(Å). The parameters {5i can be used to facilitate the learning process by filtering for the relevant signal. For instance, low-pass filter is suitable for homophilic graphs, whereas higher frequencies may be required for heterophilic graphs to capture information from nodes multiple hops away.
In practice, calculating the eigenvalue decomposition of Á in the decentralized setup expensive as the computational complexity of the eigenvalue decomposition of an n x matrix is O(n)). Therefore, we use Eq. to calculate Z.
5.3 PRUNING
The exact computation of the L-hop combined adjacency matrix À scales with Onn)), making impractical for very large networks. However real-world graph-structure sparse. Moreover, as shown in Sec. 5.2 Á is a filtered version of Å and is, therefore, of low rank, Figure 3a Inspired by this, introduce estimation method that significantly reduces the computation complexity of calculating while maintaining its general structure.
datasets are often
The key idea to apply a pruning technique when calculating Å' for E [Lg]. Specifically, we choose an integer < n and retain only the top p n values of matrix A' at each iteration, reducing complexity from Le n to Le p- In Figure 3 compare À to its pruned version (p 30) on Cora. As can be seen, pruning mostly removes off-diagonal connections (links between nodes in different communities), while preserving the main community structure of the graph. As shown in Sec. this does not negatively impact the learning process, nodes in the same community tend to have similar information, allowing the model maintain its performance.
n.
5.4 STRUCTURAL INFORMATION SHARING
For given client i, training FEDSTRUCT involves computing VoC,(0) and predicting node labels v. Vu V. We denote by A [I(TT, Ye V.) client i's local partition of A, where A [1 Yu E V). By observing that Eq. 10 depends only on A and S, we have the following proposition.

---

Published as a conference paper at ICLR 2025
Proposition 1. For client i, training FEDSTRUCT, i.e., computing (ue, Ye E vi} and (o),(0), requires only the local partition A and S.
Prop. (proved in App. C.2) states that clients do not require knowledge of the global adjacency matrix predict a node's 's label or compute gradients. Instead, only the local partition of the global L- hop combined adjacency matrix, A is required to operate FEDSTRUCT. Combined with the heavy pruning operation, which effectively prunes A this approach significantly limits the structural information shared between elients. Optionally, homomorphic encryption may be used. As a result, is very difficult to reconstruct other clients' adjacency matrices from the pruned A enhancing privacy. Additionally, due to graph isomorphism, A cannot be leveraged uniquely reconstruct other clients' adjacency matrices, further reinforcing privacy. Clients have to collaboratively calculate A In App. D we provide an algorithm and an example to obtain A before training begins.
5.5 HOP2VEC: TASK- DEKENEEEN NODE STRUCTURE EMBEDDING
Well-known NSF methods like NODE2 and GDV require knowledge of the L-hop neighborhood of node, are task agnostic, and hinge homophily assumption (see App. To circumvent these shortcomings, we propose VOP2VEC, a novel method to generate task-dependent NSFs that captures structural information beyond direct neighbors without requiring knowledge of the I--hop neighborhood and is applicable to heterophilic graphs.
The idea behind HOP2VEC is view NSFs as learnable features. To this end, NSFs are randomly initialized and updated during the training of FEDSTRUCT. More precisely, for fixed 0, the NSFs are optimized by solving
S = arg min L(),S)
(13)
5
The optimization is carried out through gradient descent,
S - --5-\V5
(14)
where A denotes the learning rate.
Using HOP2VEC, we note that the learning of ge, (sw) (see Sec. 5.1 c.g., Eq. is equivalent to the learning of sa. i.e., the purpose of passing the NSFs through the sGNN generate task dependenndd NSEs. Since the NSFs Jev are subject to optimization, we can integrate the learning parameters
of go. (8.) into 8,, and rewrite Eq, 10
y softmax
Amusn So (o)(v)
(15)
To operate FEDSTRUCT, in Sec. 5.4
client only need access to Ald as shown in Prop.
2
Proposition 2. Let C, in Eq. 4
use the cross-entropy loss and let S = [[(s]] Vg E V)
represent the matrix containing NSFs generated by HOP2VEC, Additionally, let ÿo be as Eq. 15 The gradient V (0, S) is given by
ss = Σ Av. y0)
(16)
VE
Proof. See App.
C.3
The FEDSTRUCT framework with HOP2VEC is described in Alg. 2 in App.
5.6 COMMUNICATION COMPLEXITY
In T we present the communication complexity of FEDSTRUCT alongside that of FEDSAGE# We divide the communication complexity into two parts: a pre-training component, accounting for events taking place before the training initiated, and an online component accounting for the actual training phase. In the table, parameters E, K, and n represent the number of training rounds, clients,
In Eq. 13 we made explicit that the loss function L(0) (introduced in Eq, and Fq. through the estimated labels ÿo (see Eq. 10
is contingent on S
7

---

Published as a conference paper at ICLR 2025
Communication Complexity of FunSmucT..
ALGORITHM
PRE-TRAINING
TRAINING
PEDSTRUCT FEDSTRUCT HOP2VEC
O(K d. + La K pp OiL K p.p.
O(E K 10)
O K 10 E K d
FEDSAGE+
0
OEE K² 10)
+ E d.d..).))
and nodes in the graph, respectively. Parameter d is the node feature size (all feature dimensions are assumed be equal to d), and [@] is the number of model parameters (all model parameters are assumed to be of the same order).
As seen in Table [ the online complexity of FEDSTRUCT is significantly lower than that of FED- S AGE+ which is on the order of n. The online complexity of FEDSTRUCT with HOP2 however, also on the order of n. The pre-training complexity of FEDSTRUCT is on the order of Lıg p-1 n. Overall the complexity of FEDSTRUCT is the same of FEDSAGE+, i.., the order of n.
EVALUATION
To demonstrate the performance and versatility of FEDSTRUCT, we conduct experiments on six datasets pertaining to node classification under scenarios with varying amounts of labeled training nodes, ii) number of clients, iii) number of layers, and iv) data partitioning methods. 'hhe inter- connections between clients heavily depend on the latter. The datasets considered are: Cora (Sen) al., 2008), Citeseer (Sen et al. 2008), Pubmed (Namata et al., 2012). Chameleon (Pei et al. 2020), Amazon Photo Shchur et al. 2018), and Amazon Ratings (Platonov et al. 2023). Statistics of the different datasets are provided App.
Experimental setting. We focus on strongly semi-supervised setting where data is split into training. validation, and test sets containing 10%, 10%, and 80% of the nodes, respectively. We artificially partition the datasets into interconnected subgraphs that are then allocated to the clients. Here, consider a random partitioning, which assigns nodes subgraphs uniformly at random. This partitioning constitutes a very challenging setting as the number interconnections high and, hence, the learning scheme must exploit such connections, and relevant in, e.g., transaction networks, where accounts do not necessarily have a preference to interact with nodes in the same subgraph. In App. F]] we also provide details and results for two other partitionings using the Louvain algorithm, as in (Zhang et al. 2021), and the K-means algorithm (Lei et al. 2023).
To provide upper and lower benchmarks, all experiments are also conducted for centralized setting utilizing the global graph and localized setting using only the local subgraphs. In App. F we also give results for an MI.P approach to highlight the importance of utilizing the spatial structure within
the data. For the GNN, we rely on GRAPHS AGE (Hamilton et al.) (017) with two or three layers,
depending on the dataset (decoupled GCN performs similarly as shown in Table 6 in App. E We
further compare FEDSTRUCT to vanilla FL (FEDSGD GNN), FEDPUB, and FGE+ Zhang
et al., 202T). which do not exploit cross-client interconnections, and FEDGCN Yaoo et al. 2024) as an SFL method that exploits interconnection. For FEDCGN, it is important note that the server must access the global adjacency matrix to aggregate encrypted node features (shared by the clients) and forward the result. Moreover, the homomorphic eneryption only protects against the server, not against the clients, which have access to aggregated node features of other clients, constituting breach of privacy as recently shown (Ngo al. 2024).
For FEDSTRUCT, we consider three methods to create NSFs: one-hot degree vector (DEG), FEDSTAR (FED*), and the task-dependent approach proposed in Sec. [.1 HEC2VEC (H2V), see App. for details. For H2V, we also provide the performance of the non-pruned version (FEDSTRUCT (H2V), F), for comparison. Throughout, we set the filter parameters (see Sec. 5.2) 3 and 3 otherwise, effectively filtering out links between dissimilar nodes. While these parameters could be optimized for specific graphs, we chose this setup demonstrate the robustness of FEDSTRUCT.
Overall performance. In Table we report the node classification accuracy, after model convergence, on the different datasets for a random partitioning over 10 independent runs. The accuracy difference between central GNN and local GNN provides insights into the potential gains by utilizing FL. For example, on the Cora and Amazon Ratings datasets with 10 clients, the gap is 43.78 78% and 9.05%, respectively. For these datasets, FEDSGD GNN closes the gap 16.94% and 5. 5.24%, respectively. FEdS yields similar performance as FEDSGD GNN for all datasets. FEDPUB also exhibits similar performance due the low number of labeled nodes and random partitioning, detecting
8

---

Published as a conference paper at ICLR 2025
Table 2: Node classfication accurccy with random partilioning, Nodes are split into train val test as 10% 10% 90%, For each result, the meun and standard deviation shown for 10 independent runs. The upp performance highligghted black bold, and the second best blue bold. Edge homuphily ruio (h) given brackets.
CORA 0.81)
CITESRER (h 0.74)
PUBNED (ft 0.80)
CENTRAL GNN
82.94 1,26
09.37 1.07
12 1.15
CLLINTS
10 CILUNTS
20 CLJITS
CLIENTS
10 CLIENTS
20 CLIENTS
5 CLLINNS
ID CLIENTS 20 CLIENTS
FenSGD GNN
67.55 1.05 66 001 1.51 64.47 1.26 64.
64.501 0.50 63.38 0.76 67.911 1.09
84.741
84.664 0.22 84.55 0.52
PEOSAGES
68.034 0.87
66.33+
1.09
64.64 1.72
64.38-
0.91
63.93
0.97 63.63+
1.24
84.61
0.35
84.64+
0.37 84.45 0.37
FEDPUS
67.594 1,16
61.824
1.84
48.474
2.66
64,501
0,95 62.911
0,76 52.081
3,78
82.161
0.49
82.391
0.41
82.30.1 0.44
PHDGCN-2Hop
#2.21
0.95
82.90:t
0.95
82.39:
1.26
70.20
1,13
70,49
1.03
0.81 70,42
K5.46
1169
N5.73+
0.77
85.90
0.50
PEnSTRUCT (DmG)
72.24: 0.81
69
891::
1.85
66.01::
1.82
65.354
1.05
63.54
0.64
62.34
84.03
84.01
0.38
83.641 0.36
PROSIRUUT (Pasw)
72.25:
0,90
69.61:
1.87
66.13#
65.544
1.07
63.38:
0.90
61.97
0.89
83.98:
94.02+
0.35
83.69 0.47
TEDSTRUCT (I12V)
79.34:1
0.85
79.27:1:
0.90
78.47:1
66.20.1
0.83
65.43.1
0.95
61.33
0.92
84.671
85.02.1
85.241
0.40
PEDSTRUCT (12V)-F
79.99.1
1.04
79.88:1
0,92 78.80:1
1.48
66.15
1.09 65.931
0.81 64.9611
0.79
85.24
0.44
85,79
0.60
86.09 0.42
LOCAL GNN
49.36
1.56
39.244 1.64 $1.02+ 1.63 49.00+ 1.52 39.88 1.62 32.724 1.12 79.00 0.67 75.27 0.59 70.74 0.43
CHAMELEON (A- 0.23)
AMAZON PHOTO (h 0.82)
AMAZON RATINGS th 0.38)
CENTRAL GNN
54.381 1,96
94,10 0.30
41,421 0,80 CLIENTS
CILDNNSS
10 CILINTS 20 CLJINTS
CLINNTS 20 CLUDNT
FRnSGD GNN
40 40.23:t 1.89
36 801: 1.70 $4.624 1.47 92.174
0.37 01.551 0.34 00:721 0.37 37.06
0.69
15.961 0.46
36.31 0.54
PEOSAGE+
40.05 2.11
36.324 1.59 34.68
1.69
92.184
0.33
91.33
0.47 90.65 0.59
37.01
0.75
35.85+
0.39
36.17 0.33
PEDPUB
40.151 1.44
33.31:1:
1.37 28.34:1
1.13
90.191
0.38
88.051
0.68
85.5331
0.74
36.551
0.63
35.721
0.60
38.1811 0.93
FuDGCN-2Hap
50.35d 1.92
48.77
1.73 49.35:
93.76.
0.23
93.724
0.41
93.724
0.54
40.87
40.784
0.56
40.35 0.59
PEDSTRUCT (Dea)
44.33-4 1,56
41.824
1.78
40.13- 1.85
90.73-
0.32
89.72
0.43
89.42
0.48
29.35
0.47 38.67
0.66
38.31 0.54
TEDSTRUCT (FED-)
44.71:1 1.44
41.89:1
1.67
40.06.1
2.02
90.754
0.36
89.78.1
0.38
89.14:2 0.38
39.31
38.651
0.44 38 38.36.1 0.58
PUnSTROCT (HEV)
53.33: 2.25
52.60:t
1.25
51.85
1.26
91.14
0.46
90.93
0.27
91.25
0.38
41.14
0.43
40.97
0.64
40.55 0.25
PEDSTRUCT (122)-F
53.20:1 1997
53.09:1
1.85
$1.89. :: 1.09
90.5741
0.54
90.744
0.29 91.29 : 0.58
41.13 0.37
41.07.1
0.56
40.83 0.36
LOCAL GNN
35.634 1.79 29.60-+
1.25 23.70 0.66 97.91 0.05 77.124 1.75 60.44 0.98 44.32 0.46 32.80++ 0.45 31.68 0.52
FEEDGNN lacks privacy as the server must have access to the global adjacency matris and ageregated node features and hop structures are shared between claenis. which also conctitutes a privacy breach shown in Ngo al (024) Morcover, the official implementttiion overooks isolated external neighbors removal, poteniallyy calancing prodiction performaace above actual capabilities.
communities in this setup cannot be done efficiently. Moreover, FEDGCN is included as a method that considers the enter-connection between nodes. This method, relying on server access to the global adjacency matrix (see App. C.4). shares 2-hop aggregated node features with other clients and, therefore, it is not private.
From Table 2 it can be seen that FEDSTRUCT further improves performance compared to FEDSGD GNN and FEDSAGE+. The improvement is significant for the Cora and Chameleon datasets. For Chameleon and 20 clients, FEDSTRUCT with HOP2 V achieves an accuracy of 52.76% compared to 34.33% for FEDSAGE+ The table also shows that the performance improves with NSFs able to collect more global information as can be seen by the improvements between DEG, FED*, and H2V. Notably, FEDSTRUCT achieves performance close to that of the non -oivprivate framework FEDGCN and the centralized approach. Also, notice that for Chameleon and maaazon-ratingee two heterophilic graphs, FEDSTRUCT outperforms FEDGCN.
Compared to, e.g., FEDSGD GNN, FEDSTRUCT remains robust to increasing number of clients and, as shown in App. F across different partitioning methods, highlighting its ability to exploit inter- client connections. Furthermore, FEDSTRUCT (H2V) exhibits only slight reduction in performance compared to FEDSTRUCT (H2V)-F, while significantly reducing communication complexity (see Sec. (.6). Additional results, including federated averaging and central decoupled GCN, are provided in App. for various partitionings, varying number of labeled training nodes, and degrees of heterophily.
6.1 IMPACT OF THE NUMBER OF LABELED TRAINING NODES
As noted by Liu et al. 20200, decoupled GCN addresses over-smoothing, Dong al. (2021) further showed its suitability for semi- semi-supervised learning by leveraging pscudo-labels from unlabeled nodes. Figure 4 (a). shows FEDSTRUCT'S performance on Cora for varying NSF generators and labeled node ratios, using a 100-009-990 - 3% train-val-tess split, where x is the percentage of labeled nodes.
FEDSTRUCT with H2V comes close CENTRAL GNN across all labeled node fractions, performing well even with just 5% labeled nodes, achieving a top-1 accuracy of 76%. In contrast, FEDS AGE+ and FEDPUB show sharp decline, dropping from a top-1 accuracy of 75% with 50% labeled nodes
9

---

Published as a conference paper at ICLR 2025
FERTR00 2000
Figure Accuracy training-rati CoRa with madkea partitioning and 10 clients: (b) Accuracy number propagation layers CORA with K-means partitionnng eliesss; (c) Accuracy vs number clients CHAMELEON with randen partitioning (d) Accuracy on CHAMELEON clients for various partitioning methols.
to top-1 I accuracy of 60% and 50%, respectively, with 5% labeled nodes. Finally, can be seen that LOCAL GNN deteriorates with fewer labels.
6.2 IMPACT OF THE NUMBER OF LAYERS IN THE DECOUPLED GCN
We evaluate the impact of the number of GNN/decoupled GCN layers the Cora dataset. We com- pare FEDSTRUCT with different NSEs to CENTRAL GNN and FEDSGD GNN (using GRAPHSAGE). We also assess FEDS TRUCT'S performance when only NSEs are used during inference (H2V s). We consider a setup with K-means partitioning and 10 clients.
Figure (b) shows that GNNs suffer from oversmoothing after just a few layers, limiting the ability to use distant nodes. In contrast, FEDSTRUCT'S performance remains stable across a varying number of layers, suggesting effective use of distant nodes. FEDSTRUCT (H2V s) performs poorly with fewer than 10 or more than 30 layers, peaking between 10-20 layers. This is due to the NSEs being unable to capture extended neighborhoods with few layers, and over-smoothing with many layers. H2V S achieves 75% accuracy, while H2V reaches 80%, indicating that while NSEs provide useful information, NFEs are necessary to achieve performance close to CENTRAL GNN.
6.3 IMPACT OF THE NUMBER CLIENTS AND PARTITIONING METHOD
Next, we evaluate the impact of the number of clients on the performance of FEDSTRUCT with different NSEs, alongside FEDSGD GNN, FEDPUB, and FEDGCN, using the Chameleon dataset with random partitioning. As shown in Figure 4 (c), FEDSTRUCT and FEDGCN show stable performance as the number of clients increases. FEDSTRUCT's ability to leverage deeper structures allows it to perform nearly as well as CENTRAL GNN. In contrast, FEDPUB and FEDSGD degrade with more clients, with FEDPUB performing the worst due to the increased difficulty in predicting communities as the number of clients grows.
In Figure (d), we present the performance on Chameleon with clients under different partition- ing methods. FEDSTRUCT consistently achieves the best performance across all scenarios. even surpassing CENTRAL GNN with the less challenging Louvain partitioning. Both FEDSTRUCT and FEDGCN (which does not provide privacy) exhibit robustness across different partitioning methods, while the other frameworks are more sensitive to the choice of partitioning.
7 CONCLUDING REMARKS
We introduced FEDSTRUCT, framework for SFL that decouples node and structure features, explicitly exploiting structural dependencies. FEDSTRUCT effectively addresses the privacy- communication-utill trilemma as follows:
Privacy: Unlike other SFL frameworks, which require sharing original or generated node fea- tures and/or embeddings among clients, FEDSTRUCT eliminates this need and minimizes sensitive information sharing. Privacy considerations are detailed in App. G.I
FEDSTRUCT performs close to centralized approach, excelling in supervisee learning with few labeled nodes, and significantly outperforms earlier methods like FEDSAGE: and FEDPUB in challenging scenarios. It is also robust across different partitionings, client numbers, and heterophily.
Utility:
Communications: FEDSTRUCT'S communication overhead scales linearly with the number of nodes, comparable benchmarks like FEDSAGE+.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was partially supported by the Swedish Research Council (VR) under grants 2020-03687 and 2023-05065, by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation, and by the Swedish innovation Agency (Vinnova) under grant 2022-03063.
The computations were enabled by resources provided by the National Academic Infrastructure for Supercomputing in Sweden (NAISS), partially funded by the Swedish Research Council through grant agreement no. 2022-06725.
REFERENCES
Sami Abu-El-Haija. Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg. and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In ICML, 2019.
Jinheon Baek, Wonyong Jeong, Jiongdao Jin, Jaehong Yoon, and Sung Ju Hwang. Personalized subgraph federated learning. In ICMI,, 2023.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Trunsuctions on Puttern Analysis & Machine Intelligence, 45(1), 2023.
Fahao Chen, Peng Li, Toshiaki Miyazaki, and Celimuge Wu. Fedgraph: Federated graph learning with intelligent sampling. IEEE Transactions on Parallel and Distributed Systems, 177 2021.
Wei-Ning Chen, Peter Kairouz, and Ayfer Ozgur. Breaking the communicaion-pivxcyyauuugg trilemma. Neurips, 33, 2020.
Hejie Cui, Zijie Lu, Pan Li, and Carl Yang. On positional and structural node features for graph neural networks non-attributed graphs. In Proceedings of the 3 ACM International Conference on Information & Knowledge Management, 2022.
Hande Dong, Jiawei Chen, Fuli Feng, Xiangnan He, Shuxian Bi, Zhaolin Ding, and Peng Cui. On the equivalence of decoupled graph convolution network and label propagation. In Proceedings of the Web Conference, 2021.
Bingqian Du and Chuan Wu. Federated graph learning with periodic neighbour sampling. In IEEE International Symposium on Quality of Service (IWQoS), 2022.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Erie Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The world wide web conference, 2019.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In International conference on Knowledge discovery and data mining (SIGKDD), 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Neurips, 30, 2017.
Weiwei Jiang and Jiayun Luo. Graph neural network for traffic forecasting: A survey, Expert Systems with Applications, 207, 2022.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Runze Lei, Pinghui Wang, Junzhou Zhao, Lin Lan, Jing Tao, Chao Deng. Junlan Feng, Xidian Wang, and Xiaohong Guan. Federated learning over coupled graphs. IEEE Transactions on Parallel and Distributed Systems, 34(4), 2023.
Li Liu, Jiaping Chen, Songbai Zhu, Jie Zhang, and Congpin Zhang. Federated graph learning with cross subsrah missing links recovery. In IEEE International Conference on Information Technology, Big Data and Artificial Intelligence (ICIBA), volume 3, 2023.
11

---

Published as a conference paper at ICLR 2025
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In International conference on knowledge discovery data mining (SIGKDD), 2020.
Rui Liu, Pengwei Xing, Zichao Deng, Anran Li, Cuntai Guan, and Han Yu. Federated graph neural networks: Overview, techniques and challenges. arXhv:2202.07256, 2022.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication- -ffficiiinn learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, 2017.
Galileo Namata, Ben London, Lise Getoor, Bert Huang, and U Edu. Query- active surveying for collective classification. In International workshop on mining and learning with graphs (MLG), volume 8, 2012.
Chac-Hoanp Ngo, Johan Östman, Giuseppe Durisi, and Alexandre Graell Amat. Secure aggregation is not private against membership inference attacks. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 2024.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-GCN: Geometric graph convolutional networks. In ICLR, 2020.
Liang Peng. Nan Wang, Nicha Dvornck, Xiaofeng Zhu, and Xiaoxiao Li. Fedni: Federated graph learning with network inpainting for population-base bbaeed disease prediction. IEEE Transactions Medical Imaging, 2022.
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look evaluation of gnns under heterophily: Are really making progress? In ICLR,, 2023.
Nataša Pržulj. Biological network comparison using graphlet degree distribution. Bioinformatics, 23 (2), 2007.
Leonardo FR Ribeiro, Pedro HP Saverese, and Daniel R Figueiredo. struc2vec: Learning node representations from structural identity. In International conference on knowledge discovery and data mining (SIGKDD), 2017.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification network data. Al magazine, 29(3), 2008
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv: 1..1: 1.08688, 2018.
Jonathan M Stokes, Kevin Yang, Kyle Swanson, Wengong Jin, Andres Cubillos-Ruiz, Nina M Donghia, Craig R MacNair, Shawn French, Lindsey Carfrae, Zohar Bloom-Ackermann, et al. A deep learning approach antibiotic discovery. Cell, 180(4), 2020.
Yue Tan, Yixin Liu, Guodong Long, Jing Jiang. Qinghua Lu, and Chengqi Zhang. Federated learning on non-iid graphs via structural knowledge sharing. AAAI conference on artificial intelligence, volume 37, 2023.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
Yuhang Yao, Weizhao Jin, Srivatsan Ravi, and Carlee Joe-Wong. Fedgen: Convergence- communication tradeoffs in federated training graph convolutional networks. Neurips, 36, 2024.
Ke Zhang, Carl Yang, Xiaoxiao Li, Lichao Sun, and Siu Ming Yiu. Subgraph federated learning with missing neighbor generation. Neurips, 34, 2021.
Ke Zhang, He Xie, Zishan Gu, Xiaoxiao Li. Lichao Sun, Siu Ming Yiu, Yuan Yao, and Carl Yang. Subgraph federated learning over heterogeneous graphs. In FedGraph, 2022.
12

---

Published as a conference paper at ICLR 2025
Ke Zhang, Lichao Sun, Bolin Ding, Siu Ming Yiu, and Carl Yang. Deep efficient private neighbor generation for subgraph federated learning. In Proceedings of the 2024 SIAM International Conference Data Mining (SDM), pages 806-8 814. SIAM, 2024.
Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Philip S Yu. Graph neural networks for graphs with heterophily: A survey. arXiv:2202.07082. 2022.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily graph neural networks: Current limitations and effective designs. Neurips, 33, 2020.
13

---

Published as a conference paper at ICLR 2025
Table 3: Comparing NSP generatee algoritims
DATA
DEG
GDV
NODE2VEC
FED*
HOP2VEC
TASK DEPENDENT
X
X
GLOBAL PROPERTIES
V
X
FAST
X
NO PARAMETER TUNING
V
LOCALLY COMPUTABLE
X
V
A NODE STRUCTURE FEATURE GENERATION
In this appendix, we provide some background on the creation of NSFs. The simplest method considered in this paper is the one-hot degree encoding (DEG), which simply creates vector with single non-zero entry whose position indicates the node degree. Naturally, the one-hot encoding is unable to capture anything beyond 1-hop neighbors.
Graphlet degree vectors (GDVs) go beyond the 1-hop neighborhood by representing the local structure of node within the node structure feature (NSF). This is achieved by, for each node, counting the number of occurrences within a pre-defined set of graphlets (Pržulj 2007). Although GDV is more expressive than DEG, this approach suffers from high complexity the number of graphlets grows very fast with the number of nodes.
NODE2VEC is an unsupervised node embedding algorithm that creates NSFs from random walks in the graph by capturing both local and global properties (Grover and Leskoved 2016). It uses controlled random walks to explore the graph, generating node sequences similar to sentences in language. For each node in the graph, multiple random walks are performed creating a large corpus of node sequences. These sequences are then used train a skip-gram model predict the context of given node, i.e., the neighboring nodes in the random walks. Once trained, the NSFs are obtained by querying the skip-gram model with node and extracting latent representation.
FED+ is proposed in (Tan et al. 2023) to capture structural similarities in the context of federated graph classification. In particular, for each node in a local graph-structured data record, clients create NSF by concatenating NSFs created from DEG and from random walk. We adapt this methodology to our setting by extracting the diagonal element corresponding to given node from the powers Å, during the process of computing A, in place of (Tan et 2023 Eq. 6).
As shown in Appendix H NODE2VEC yields superior performance to DEG, GDV, and FED* due to its ability to capture global properties of the graph. Note, however, that NODE2 and GDV require access to the adjacency matrix of the global graph which is not generally available for our setting. Moreover, the objective function of NODE2VEC contains multiple hyperparameters and is task agnostic, i.e., its representations do not account for the node classification task hand.
The proposed HOP2VEC leverages the advantages of NODE2 while also alleviating its shortcom- ings within our setting. In HOP2VEC, instead of learning the NSFs before FEDSTRUCT initiates, we start from a random NSF and train generator within FEDSTRUCT. As result, we obtain NSFs that are tailored toward the task, e.g., minimize miss-classification. Notably, in sharp contrast to NODE2 VCC HOP2 ECC does not require knowledge of the complete adjacency matrix. Moreover, compared to NODE2VEC: HCP2VEC is faster and does not need any hyperparameter tuning. Finally, when paired with DECOUPLED GCN, it is able to capture the global properties of the graph. A summary of the different NSF-generating methods given Table 3
The NSFs obtained by HOP2VEC are task-dependent, capture deep structure dependencies, and do not rely on homophily. The first property is inherent to the training-the NSFs are formed to minimize misclassification. The second property results from the fact that the NSFs are optimized based on Aue through Eq. 10 since coefficient Age encompasses the L-hop neighbors of node v, and L can be large, Hop2 V EC is able to capture the global graph's structure information. Furthermore, the parameters 8, the trainable coefficients An, (see Sec, 3 can be adjusted (or learned) to account for heterophilic graphs (we discuss heterophily in App. G.2
14

---

Published as a conference paper at ICLR 2025
B TRAINING PROCESS OF FEDSTRUCT
The training process of FEDSTRUCT with generic NSEs is described in Algorithm The training
process of FEDSTRUCT using HOP2VEC is described in Algorithm
Algorithm 1 FEDSTRUCT
input client with their respective subgraph {Gi) J FEDSTRUCT model parameters (0:
i=r to K do
Collaboratively obtain A based on Algorithm
Locally compute NSFs S {s Vu V.) Share S; with all the clients
end for
for e=1 to Epochs do
for i=1 to K do
Client collects 0 from the server
for V/2 do
Calculate D. based on Eq. 10
end for
Calculate (0) based on Eq.
Calculate (0) based on Proposition
Send (e) to the server
end for
Calculate (() based Eq. 0 - 0 (()
end for
Algorithm 2 FEDSTRUCT using HOP2VEC
input K client with their respective subgraph (G FEDSTRUCT model parameters 0 (0:110,)
Server initialize VsC(0, S)
for to K do Collaboratively obtain Ald based on Algorithm
Create S (su, Yu V.) by randomly initialize 8,. Vu V.
Share S with all the clients
Collect S, jij [K] and create [1( Ve E V)
end for for e=1 Epochs do
for i=1 to K do
Client collects from the server
Client collects sC S) from the server
Client updates
S VL(
for u V. do
Calculate ÿ. based Eq. 15 end for
Calculate C, S) based on Eq.
Calculate (0,, S) based on Proposition 3
Calculate (0, based on Proposition
Send V Ve,, S') and (e, to the server
end for
Calculate VoL(O, S) based on Eq. 0 AVL((A,S)
Calculate sL M
ΣK VsL.(0,S)
end for
15

---

Published as a conference paper at ICLR 2025
C PROOF SECTION
C.I LOCAL GRADIENT
To prove Proposition 1 we need the following Lemma and proposition.
Lemma 1. Let ÿ softmax(q) and L - C ÿ). where CE is the cross-entropy loss function and y is the label corresponding the input vector q, with > yi 1 and being the number of classes. The gradient of L with respect to is equal to
VgL = ÿ y y
(17)
Proof. Using the definition of cross-entropy
CF 9) = Σ
y (olg)(
(18)
2=1
and the definition of softmax,
et
softmax(q) =|1
Vi E
(19)
Σ5 ビ==1
eds
can rewrite C
L Σ Ui (LSE(Q) - -q:)
LSE(q)
y: i=1
V/-
i=1
LSE(g)
y
(20)
where LSE(g) = log( e is the log-sum-exp function. The partial derivative of LSB(q) with respect to is the softmax function
LSE(2) |1( ØLSE(q)
wk E [c])
0qu
e
||(
Vk E [c])
edi
j=1
= ssofmmax(q)
(21)
Therefore, using Eq. 21 and taking the derivative of Eq. 20 with respect to æ leads
V = VgLS(() - V. y) = 9 y.
The local gradient (e), is given by the following proposition.
Proposition 3. Let (,) Eq. 4 use the cross-entropy loss with = (0:ll0s) and let ú. be as in Eq. 10 The local gradient
Vol( = (0)((0)
Vj E |00|]
00,-
given by
(0)
0ga, (8w)
OL,(0)
0fe, (v)
Σ
Ann
(go y,).
Σ
(3, yo).
(22)
00..j
00
00,
0b,,
VEV.
Del.
16

---

Published as a conference paper at ICLR 2025
Proof. By the chain rule and Lemmal
1
we have
OC,(0)
0q.-
Σ
1. ()
00,
00,
Dqu
Σ
(Uv yo)
Vj [[0],
(23)
VEV.
where Qo = Evey A (8.) + (v).
Taking the derivative of with respect to the different
entries of leads
dqu
Ogo, (8.u
Σ
Avn
vj E ||0+]]
(24)
00..j
00s.j
0qu
(o)
Vj E |
(25)
00,.j
00.,j
Substituting Eq. 24 and Eq.
25 into Eq. 23 and separating the summation over V over the different
clients concludes the proof.
C.2 PROOF OF PROPOSITION
1. To obtain {u.. Vu E V/} in Eq. 10 client only needs external inputs A and S.
2. To calculate (O), client only needs external inputs A and S.
By combining
T andd] we prove Proposition T
C.3 PROOF OF PROPOSITION 2
First notice that
VsC((0,S)) II((V,, E
(26)
Using the chain rule and Lemma
we have
Oq V. q: (0,
V (O,
Σ
Dsp
DEVi
aqu
Σ
(g)
yu) Vp VV
(27)
08p
where qu = =uEv Aruou + (v). Taking the derivative of qu with respect to sp leads to
0q.
2su Osp
Σ
A
Osp
Osp
Aup 88p
Aup
Vp E.
(28)
Substituting Eq. 28 into Eq. 27
leads to
V o, (0, =
Σ
Aup - Vo)
Vp E V.
(29)
DEV.
Finally, substituting Eq.
29 into Eq. 26 concludes the proof.
17

---

Published as a conference paper at ICLR 2025
C.4 FEDGCN WITH HOPS NEEDS GLOBAL ADJACENCY MATRIX KNOWLEDGE
In the FedGCN scheme, as detailed in Equation 3 on page 5 of the FedGCN paper, to calculate Ø.. the following information must be sent the server by Client z:
Σ
0g Ai5()
(30)
JEN;
h2j
Σ MEN;
Amm( VIE
(31)
Once the server obtains hay for all clients = E [K]. it calculates the aggregate h2 =E haj and forwards this result to the client where node resides. However, as hj a quantity pertaining to node j. the server must know that i and are connected. Similar arguments hold for all other nodes. Hence, the server needs access to the global adjacency matrix for this scheme to work with 2 hops.
D SCHEME TO OBTAIN THE LOCAL PARTITION OF THE L-HOP COMBINED ADJACENCY MATRIX
D.1 ALGORITHM
As discussed in Section 5 FEDSTRUCT with decoupled GCN only requires the clients have access to their local partition of the global L-hop combined adjacency matrix, i.e., A In this appendix, present an algorithm that enables clients to acquire this matrix in scheme for obtaining the local partitions of the L-hop combined adjacency matrix A is designed specifically to ensure that no client has access to the entire ε-hop (E [l...., L)) adjacency matrix Á
manner. The
We denote by A = I(@a!, Ve E V.) and A = IKa!! Vo V.) the local partition of and À pertaining the nodes of client i, respectively. Further, note that Åli (Di:i) -1 A where
D E R is the diagonal matrix of node degrees, with Bil(v, v) = Enev Teu. Ve E V.
Also, let Al:1 &RIUX denote the submatrix of Ål that connects client to client j for j E [K] and define A!i analogously. Consequently, we have A = (Dit) -1
(Die)-AA A/00
Each client has access to:
-A RIIIIIV for all j e [K] representing the outgoing edges from client to client
AA E E 13 for all j e [K] representing the incoming edges from client client i
We note that client i can compute A! locally as it knows the destination of its outgoing edges, i.e., A for all j E [K]. and can compute Blll
In client i, are interested in acquiring its local partition of Ā, i.c., Ald l| Vo E V.). Let A E R|M denote the submatrix of Al that connects client to client j for j E [K]. Based on
Eq. we can write [ as
1ag Σ
A
B
j [
(32)
where 11 is the submatrix of A' 'hhat connects client i to client for j [K]. Since Á Å we can easily show that
Σ A
(33)
KE(K]
= DD (8)
Σ
1-
(34)
kE|K]
computeed at client A
18

---

Published as a conference paper at ICLR 2025
By induction, we can demonstrate that if each client i has access to | for all j [K] they then collaborate with each other to compute [A [e Here's step-by-step breakdown:
Base case: For é 1, we have [ A This information is available to Client i from the start for all j E [K]
2. Inductive step: Suppose Client i knows [ for all j [K] Then, Client k can compute the intermediate term
Bijk A (A!
(35)
for all j E [K] (since it knows Je-1 and A for all i, J E [K] and share it with Client i. Notice that Client i cannot reconstruct [A from Bish due to the low rank nature of A l: Additionally, Client k also prunes Bijk to remove any concern. Based on Eq. 34
Client can compute 1e by:
[4 = (D
Σ Bijk kE[K]
(36)
To apply pruning, in each iteration, client sends only the top 1 n. values Biyk to Client where p the pruning parameter. Therefore, client receives an estimate of [1 as
| (D
Σ
B
jE [
(37)
KE[K] computed at client &
where Bijk is the pruned version of matrix Bijk with pruning parameter # This summation allows Client to update its local adjacency matrix partition without requiring access to the entire global adjacency matrix. At each step e, Client only accesses [ for all j E [K] and does not learn the full global matrix [Á]e. Moreover, if additional security is required, the summation over Bijk could be performed secure server using homomorphic encryption.
As the final step, Client can compute A! sequentially based on Eq. 32 The resulting algorithm shown Algorithm 3 Finally, we notice that Algorithm 3 requires each client k to evaluate L, X ng x n² matrix products and communicate L, p matrices. This communication complexity is linear with n and is performed only once before the training initiates.
D.2 EXAMPLE
To illustrate our algorithm and its privacy mechanism, we provide an example to compute the 2-hop combined adjacency matrix A, defined Section 3
As stated in Section 2 SFL can be categorized into two groups:
1. SFL with knowledge of cross-subgraph interconnections.
2. SFL with knowledge of cross-subgraph interconnections.
This paper focuses the second scenario, where the interconnections between clients (i.e., between subgraphs) are known to the involved clients. Specifically, client knows its incoming and outgoing edges to every other client j, meaning it knows A and Ali for all j E [K]-
It is important to note that the knowledge of A.!. and [ does not imply that the entire global adjacency matrix is accessible to client i. Each client has access only to the rows and columns corresponding to its nodes. As example, consider graph with nodes, partitioned across
19

---

Published as a conference paper at ICLR 2025
Algorithm/ 3 Private acquisition of A
input {4 A 1 K
DM power L, and list of weights (3e)
j=1
output local matrix {A( for i 1 K do for j to K do
Initialize A," 31
end for end for
for l = 2 to L, do
for = 1 to do
for k=1 to K do
Client & calculate By = 14 Aj [K]
Client & sends the pruned matrix Biyk to client for j E [K]
end for
Client collects B.j from clients [K] [A |1 (D(I)- ">* -= Bija for j E [K]
Client stores
A
A 1
Be 1 for j E [K]
A 1
[
1
A
A R
end for end for
clients, given by the following adjacency matrix:
0
0
0
0
0
0
0
0
0
0
0
0
1
1
A
0
1
0
0
0
1
1
0
0
0
0
1
0
0
0
0
0
0
where Ag- 1 indicates connection between nodes i and j. and Aij 0 indicates no connection.
In this setting, Client comprises nodes (1, 2, 3). Client comprises nodes {4, 5, 6). and Client comprises nodes (7, 9).
Below, we depict the entries of the adjacency matrix known to Client using 0 (there is no connection) and '?' (unknown connection):
(there is connection),
?
?
?
0
0
?
?
?
?
?
0
?
2
?
?
0
1
?
?
0
1
0
0
Known entries of A for Client 2
0
0
0
0
1
0
0
0
(38)
0
0
0
0
0
?
?
0
?
?
?
? ? ?
0
?
?
0
?
?
Client knows all its internal connections (e.g., node is connected to node 5) well as its external
edges (e.g., node 4 is connected to node 2 in Client and node 9 in Client 3. The incoming edges to Client 2 from Client 3 are given by
Ā 1=
0
0
(39)
0
0
20

---

Published as a conference paper at ICLR 2025
That is, there is only connection between Client 2 and Client 3 (between node 4 and node 9). Thus, while Client has access to its own local and inter-client edges, remains unaware of the internal connections of other clients or the interconnections between any other clients {1,3) and E (1,3)-
Hence, Client i knows portion of the global adjacency matrix A, i.e., A corresponding to the connections between its own nodes and to some nodes in other clients. In particular, Client knows
internal connections (including self loops): A
1
0
outgoing connections: A!
0
0
A
0
0
0
0
0
0
0
incoming connections: Al
0
0
A
0
0
1
Similarly, Client 2 knows
internal connections (including self loops): A.
1
1
0
0
outgoing connections: A!
0
0
0
A
0
0
0
0
0 0"
0
0 0
incoming connections: A!"
0
0
A
0
0
1
0
0
and Client knows
internal connections (including self loops): A
0
outgoing connections: A
0
0
A
0 0
0
0
1
0
0
0
0
0
0
incoming connections: A!
0 0
A
0
0
0
0 0
0
0
1
Using AJ1.1 E f1,2,3). Client i can compute both the degree matrix
D. and the normalized
adjacency matrix A!" for all [K] For simplicity, assume that A A
Vi.j
[K] in
this example, as they differ only by normalization constant.
Following Eq. 35
define the intermediate matrix Bija A Ale The following steps outline
remaining computations:
1. Calculating Bisk-
Client calculates Bzn Bra1, B231 as follows,
0
0 0
B211
0
0
1
B2a1
0
0
B231
0 0 0
(40)
1
0
0
0
0
21

---

Published as a conference paper at ICLR 2025
Table 4: Statitics of the dirasets.
DATA
CORA
CITESBER
PUBMED
CHAMELEON
AMAZON PHOTO
AMAZON RATINGS
# CLASSES
3
5
8
5
[
2708
3327
19717
2277
7650
24492
[E]
5278
44327
36101
238162
93050
# FEATURES
1433
3703
500
2325
745
300
EDGE HOMOPHILY RATIO
0.81
0.74
0.80
0.23
0.82
0.38
Client 1 sends these matrices to Client Notice that Client 2, by receiving
B211, B221, B231, cannot reconstruct A A! and A due to the low rank nature of the adjacency matrix. Moreover, Client also prunes Bijk-
Similarly Client 3 calculates B213, B223, B233 as
0 0
0
0
1
B213
1000
B223*
0
B233
0
1
(41)
0
0
0
0
1
which sent Client 2 after pruning. A similar procedure applies for the other combina- tions of Bijk, as outlined in Algorithm 3.
2. Calculating 11.
Upon receiving B211 Br21, B2s1 and B213, B223, B233, [A[2) [ [2 as
Client
can compute
12 = (Dlel)-1 -1 (B211 + B212 + B213)
(42)
[1 (Dlel)-1 (B221 + Brz2 B223)
(43)
[ (D(Pl)-1 (B231 B2s2 B233)
(44)
Note that B212, B222, B232 can be computed locally in Client 2. Using Eqs. 42
Client can update its local 2-hop adjacency matrix without access to the global adjacency matrix. Clients 1 and 3 follow the same procedure to compute [A] 22 and [A] 1212 for each j (1,2,3) respectively.
This procedure be extended to any number of hops l. At hop l, Client only accesses [A for all j E [K] and does not learn the full global matrix [Á]e, Moreover, if additional security required, the summation over Bijk could be performed secure server using homomorphic encryption.
E EXPERIMENTAL SETTING
In this section, we provide more details about the experiments in Section 6 and Appendix F In Table 4 statistics of the different datasets are shown. The edge homophily ratio, measuring the fraction of edges that connect nodes with the same label, provides a measure of the homophily within the dataset. Typically, a value above 0.5 is considered homophilic (Zheng et al. (2022). According to this rule-of-thumb, among the datasets considered in this paper, two would be considered heterophilic, ie., Chameleon and Amazon Ratings.
we provide the step sizes À and Aş for the gradient descent step during the training, the weight decay in the L2 regularization, the number of training iterations (epochs), the number of layers L in the node feature embedding, the number of layers L, in the DECOUPLED GCN, the dimensionality of the NSFs, d,, the pruning parameter p, and the model architecture of the node feature and node structure feature predictors, fo, and ge,, respectively.
Next, provide the hyperparameters for the experiments. In Table 5
All the experiments obtained using Nvidía A30 with 24GB of memory.
22

---

Published as a conference paper at ICLR 2025
Table Hyper-pamneten of the dataeets.
DATA
CORA
CITESEER
PUBMED
CHAMBLEON
AMAZON PHOTO
AMAZON RATINGS
A
0.002
0,002
0.008
0,003
0,005
0,002
0.002
0,002
0.008
0.003
0,005
0,002
WEIGHT DECAY
0.0005
0.0005
0.001
0.0003
0.001
0.0002
EPOCHS
40
60
125
60
150
70
L
2
2
2
2
La
10
20
20
5
256
256
256
256
256
256
P
30
30
30
30
30
O LAYERS
[1433,64.7] ] [256,256,7]
[3703.64.6]
[500.128.3]
[2325.64.5]
[745,256.8]
[300,64.5]
O, LAYERS
1256,128,644
1256,128,3]
[256,256,5]
[256,255,8]
[256,256,5]
F ADDITIONAL RESULTS
In this appendix, we provide additional results that we could not include in the main paper due to space constraints. In particular, provide results for different data partitioning methods: the Louvain algorithm, the K-means algorithm, and random partitioning.
The Louvain algorithm aims at finding communities with high link density, effectively creating subgraphs with limited interconnections. Here, we follow Zhang et al.] (202T) where the global graph first divided into number of subgraphs using the Louvain algorithm. As strive to have even number of nodes among the clients, we inspect the size of the subgraphs and if any exceeds n/ K nodes, it is split in two. This procedure is repeated until no subgraph has more than n nodes. Next, as the number of subgraphs may be larger than K, some subgraphs must be merged. To this end, we sort the subgraphs in descending order with respect to their size and assign the first K subgraphs to the K clients. If there are more than K subgraphs, we assign the (K + 1)-th subgraph by iterating the first client for which the total number of nodes after a merge
the K clients and assigning would not exceed n/ K. This process is repeated until there are only K subgraphs remaining. This procedure results in subgraphs with approximately the same number of nodes and a low number of interconnections.
For the K-means algorithm, we follow Lei et al. (2023) and partition the data into K clusters by proximity in the node feature space. Similarly to the Louvain partitioning, we split any subgraph that exceeds n/ K nodes in two and assign to another subgraph such that the resulting number of nodes is less than K. Compared to the previous partitioning, the K-means approach does not consider the topology, hence, there will be more interconnections between the different subgraphs compared to the Louvain-based partitioning. Further, as highlighted in (Lei et al. 2023), nodes with similar features tend to have the same label, this partitioning method creates highly heterogeneous partitioning as each subgraph tends have an rerreeeprsnntttion of nodes of a given class.
Finally, we consider a random partitioning where each node is allocated to a client uniformly at random. As this partitioning does take into account the topology the features, we end up with large number of interconnections where each subgraph has the same distribution over class labels, i... the data homogeneous across clients. Notably, given the large number of interconnections, this setting arguably constitutes the most challenging scenario in subgraph FL as it is paramount to exploit the interconnections to achieve good performance.
F. PERFORMANCE UNDER DIFFERENT PARTITIONING METHODS
In Table 6 we show the performance of FEDSTRUCT over each of the different partitionings for 10 clients and the train-val-test split according to 10%-10%% 10%-80%. We use this split focus challenging semi- cuni-supervised scenario. Furthermore, each the results is reported using the mean and standard deviation obtained from 10 independent runs.
First, as the central version of the training with GNN does not depend on the partitioning, it is the same as in Table 2 We also report the performance of central training using DECOUPLED GCN and when employing an MLP. By comparing the performance of CENTRAL GNN with CENTRAL MLP, may infer the gains of accounting for the spatial structure within the data. As seen in the table,
23

---

Published as a conference paper at ICLR 2025
Classiicatio accuracies FEDSTBUCT with an underlying decoupled GCN. results are shows 10 clients
split.
COKA
CITESUER
PORSED
CENTRAL GNN
82,9411 1,26
69.37 1.07
85,12:: 1.15
CENTRAL DOCN
83.48 + 1,31
69.05 = 1.20
85.61 0.18
CENTRAL MLP
65 05.47790.0199
63 63.67 0.81
84.31 0.22
LOUVAIN
RANDOM
KMEANS
LOUVAIN
RANDOM
KMEANS
LOUVAIN
RANDOM
KMEANS
FEDAVG
81.05 0.82
65.58
85.79 0.26
FenSGD GNN
21.22.1:00
66
00::
1.51
67.574
69.251
1,19
63.38
0.76
64.64111
84.872
84.661
0.22
FEDAVIG DGCN
77.494 3.06
02.60:1333
3.59
68.18:
1.35
69.88.:
0.90
65
65.04:1:1
1,96
67.10:1
1.02
84.361
0.19
84,421
0.26
85,41
ProSGD DGCN
82. 02.054 0.92
67.15
67.
2,52
69.85
1.06
68.51
1,38
63.23
0.85
65.39
65.39
1.04
84.74
0.17
83.924
0.40
84.68
0.32
FEDAYG MLP
68.59 1.99
65.78:
1.84
64.81
1.83
66.02
0.30
64.41
0.75
64.634
1.09
85.81
0.34
84.714
0.26
84.75
0.43
FenSGD MLP
65.4111 1.33
65
63.6711
1.62
64.42:1
64.87
1.04
63
68
0.74
64.11:
0.80
84.05
0:41
84.291
0.31
84.28
0.41
PRDSAGIS
81.06: 0.89
66
66.33
1.69
67.35
1.18
69.21
1.17
63.93
0.97
64.53#
0.79
84.31
1.62
84.64
0.37
84.91
PEDPUB
78.751 1.33
61.82:1
1.84
64.38:1
1.50
69.20:
1.09
62.911
0.76
62.5611
1.29
85.161
0.29
82.391:
0.41
83.85
0.64
FUDGCN-THOP
82.244 1.13
87.91
81.60:2
0.95
70.244
0.81
70.634
0.87
68
86.731
86.05
0.65
85
0.53
PEOGCN-2H0P
81.884
1.10
82.90:
0.95
82.00
70.45
70.49
1.03
09.29
1.45
86.62
85.734
0.77
85.834
0.48
PROSTROUT (Des)
82.18
0.79
69.89
1.85
71.31
1.42
68.29
1:35
63.54
0.64
65.84 1.36
84.65
0.17
84.01
0.38
84.65 0.45
TEDSTRUCT (FED+)
81.27:1
1.13
69.611
1.87
70.89:
1.21
68.2911
1.47
63.38.1
0.90
65.754 1.15
84.71
0.13
84.02
0.35
84.77 0.40
PEDSTRUCT (H2V)
81.30:4:
0.97
79.27:4
0.90
78.36-
0.82
68.65
1.49
65.43-
0.98
66.44
1.07
82.23-
0.33
85.02-
0.43
84.81 0.42
PEDSTRUCT (112V)F
81.024:
0.60
79.88:1:
0.92
78.79:t
0.96
68.351:
1.45
65.9311
0.81 66
66.8411
0.53
83.031:
85.791:
0.60
85.47:1 0.57
LOCAL GNN
75.36.1 1.43
39.24:1
1.64 47.08:1
2.55
59.151:
1,52
39.88.1
1.62 50.9011 5,66 76.401:
3.49
75.27.1
0.59 75.00.1: 2.83
LOCAL. DGCN
76.78
1,18
41.352
1,33 51.17
1.98 $9.624
1.45
41.991
1.35
$3.041 5.33 81,542
0:47
76.65-2
0.48 80, 10.10: 0.49
LOCAL MLP
67.26
2.05
40.344
1.64
46.44-
2.15 54.62-t 1.64 41.28 0.89
52,024
5.49
81,30+
0.44 75.98-t 0.53 78.81 0.38
CHAMELEON
AMAZON
RATINGS
LOUVAIN
RANDOM
KMEANS
LOUVAIN
RANDOM
KMEANS
LOUVAIN
RANDOM
RMEANS
CENTRAL GNN
$4.3811 1.96
94,1011 0.30
41,42:1 0.80
CENTRAL, DGCN
55.05 # 1.56
92.77 # 0.38
41.05 0.41
CENTRAL MLP
10:1 1.71
87.69:t 1.37
37,74:1 0.39
GNN
45.87
33.062
37.7411
2.96
90.25
PrnSGD GNN
47.95
2.01
36.80
2.04
93.91
91.41
0.88
FEDAYO DGCN
42.01 1.47
31.08
1.24
34.124
3.40
90.87
88.424
0.00
87.364
0.52
40.144
0.00
37.52
0.37
37.96
FEDSGD DGCN
48.012: 1.43
34.78
1.39
35.731
2.02
91.971
0.39
89.85:1
0.39
0.32 90.061:
40.6911
0.49
37.92:1
0.39
38.221 0.33
PEDAvG MLP
32.634 2.31
29.49=
1.37
28.43:
1.69
90.16 1.15
85.39
1.26
85.87
2.50
37.844 0.60
37.23
0.38
37.40 0.19
FEDSGD MLP
31.91 2.14
33.13
1.24
32.46::
1.86
87.66:1
0.86
88.39
1.07
87.99.8
1.35
37.424
0.40
37.65:1
0.38
37.29 0.51
FEDSAGE4
47.70 1.68
36.37
1.59
37.73
1.58
93.8022
0.34
91
33.3322
0.47
91
91.39
0.40
40
40.541 0.71
35.85
0.39 37.552 0.38
PROPLE
47.80sh 1.65
33.31
1.57
34.82:t:
2.07
0.32 91.31
88
18.055
0.68
88.84
0.59
40.37: 0.66
35.72:
0.60
37.00 0.62
FUDGCN-THOP
52.95
3.33
48.23
1.81
48.35
1.68
93.28
60:00:20000
93.62: 0.31
41.132 0.52
40.76:
40.561
2HOP
2.00
1.73
49.14:
1.98
93.54
0.31
PROSTROUT (Dea)
49.66:t 1.61
41,82
1.78
42.16
1.8g
92.05 +
0.44
99.724
0.43
90.17 0.28
40.93:
0.29
38.67
0.66
38.78 0.35
TEDSTRUCT (FED=)
49.36:1
1.89
41.89
1.67
42.5411
1.56
92.02:1
0.41
89.78:1
0.38
90.07.1
0.42
41.03:
0.37
38.65:1
0.44
38.891 0.49
PROSTROCT (HEV)
55.74:2
1.09
52.60=
1:25
$3.401
1.69
91.21
0.42
90.93
0.27
91.42.1
0.72
40.61
0.51
40.972
0.64
41.062 0.42
PEDSTRUCT (H2V)-F
55.75
1.46
53,09
1.85
52.95
1.72
90.404:
0.58
90.744
0.29
91.11:
0.61
40.86: 0.56
41.07=
0.56
41.23 0.43
GNN
46.71 2.42
29.60m
1.25
30.84:::
2.60
91.24:
77.124
1.75
79.48:t 1.59
40.23: 0.71
32.80th
0.43
35.73
LOCAL DGCN
46.23:t 1,70
28.55
1.08
30.12:1:
3.00
90.641:
0:45
81.611
0.95
83.09.1
0.83
41.30:1
0.58
34.16:1
0.25
36.321 0.43
LOCAL ML.
31.44 2,10
21.17=
0.65
22.70::
2.43
89.27
0:75
69
89
1.34
76.05
0.30
37.6742
0.67
33.23
0.39
35.25 0.38
24

---

Published as a conference paper at ICLR 2025
exploiting the graph structure brings the largest benefits for Cora and Chameleon. Moreover, it can be seen for all datasets GNN and DECOUPLED GCN yield similar results for centralized training.
In similar spirit, the performance gap between LOCAL GNN (LOCAL MLP) and CENTRAL GNN (CENTRAL MLP) indicates the potential gains of employing collaborative learning between the clients. Notably, this gap depends the partitioning. From Table 6 the largest for random partitioning followed by the K-means algorithm for all datasets. This is expected, as local training suffers from a large number of interconnections. For example, in Cora, the gap is 42.83%, 35.26%, and 6.54% for random, K-means, and Louvain partitioning, respectively. Furthermore, LOCAL GNN and LOCAL DCGN performs similarly.
be seen that the gap
Considering FEDSGD GNN and FEDSGD DGCN, it can be seen that all scenarios benefit from collaborative learning. For the Louvain partitioning, due its community-bars low number of interconnections, FEDSGD GNN and FEDSGD DGCN performs well for all datasets. For K-means and random partitioning, they performs worse, with the worst performance seen for Cora, Chameleon, and Amazon Ratings. FEDSAGE+ achieves similar performance to FEDSGD GNN whereas FEDPUB is inferior most settings. The FEDSAGE+ IDEAL scheme, incorporating the knowledge of the node IDs of missing neighbors in other clients, is based on a mended graph with flawless in-iantingg of missing one-hop neighbors. Hence, this scheme serves as an upper bound on techniques based on in- ta-patining of one-hop neighbors, such as FEDSAGE+ and FEDNI. Notably, this scheme completely violates privacy as the node features of missing clients cannot be shared between clients. From T we see that this scheme is robust to different partitionings by offering consistent performance close to the CENTRAL GNN.
partitioning with the
We consider FEDSTRUCT with three different methods to generate NSFs: one-hot degree vectors (DEG), FED*, and our task-dependent method HOP2 (H2V), see Appendix A for information. The
are chosen as in Table In Table 6 it can be seen that DEG, only being able to capture the local structure, perform worse than the methods able to capture more global properties of the graph. This is especially true for the K-means and random partitionings. FED* achieves performance close to DEG, likely due to the random walk approach not being informative, hence, capturing essentially the same information as DEG, see Appendix [ Moreover, it can be seen that HOP2VEC performs close to +EDSAGE+ IDEAL for all scenarios and is sometimes superior, e.g., on the Chameleon datasets. This highlights the importance going beyond the one-hop neighbors for some datasets, something that is not possible in FEDSAGE+ IDEAL.
F.2 IMPACT OF PRUNING
To emphasize the strong performance of FEDSTRUCT and its robustness to structural noise, we compare with version of FEDSTRUCT that does not pruning (denoted as -F) in Table 7 As shown in Table 7 FEDSTRUCT'S performance remains very close to the version without pruning across all datasets, demonstrating its ability to handle the removal of structural information effectively.
G DISCUSSION
G.1 PRIVACY
Previous frameworks for subgraph FL (Zhang et al. 2021 Peng et al. 2022 Lei et al. 2023 Zhang
2022 Liu al., 2023; Zhang et al.) 2024; Chen al. 2021 Du and Wu (022) require the sharing of either original or generated node features and/or embeddings among clients. In stark contrast, our proposed framework, FEDSTRUCT, eliminates this need, sharing less sensitive information.
As outlined in Section 5 FEDSTRUCT requires some sharing of structural information between clients. We begin our discussion by mounting potential attack to show that some information may be revealed from other clients. Thereafter, we discuss a strategy to mitigate such attacks by refraining from sharing individual information about nodes. Specifically, present slightly different version of FEDSTRUCT that relies on sharing aggregated quantities between clients without affecting the performance of the original version.
25

---

Published as a conference paper at ICLR 2025
Table 7: Classification accuracy of PEDSSTUUT with pruning (praning parameter (00) and without praninng The results for pruning are presented in bold and the result withou the praning are shownn with -F. The results are shown for 10 clients with a 10-10-50 train-vvll-led splir.
CORA
CIFESEER
PURMER
CENTRAL GNN
52 94.1 1,26
69. 09.37.1 1.07 63.67-4
85.12: 1.15
CENTRAL MLP
65, 47 4-0019
84.31= 0.22
LOUVAIN
RANDOM
KNBANS
LOCIVIN
RANDON
KMEANS
LOUVAIX
RANDOM
KHGANS
EXOSTBUCT
$2.18 0.79
69.89 1885
71.31 H: 1.42
68.29 1.35
63.54
0.64
65.84 1.36
$4.65 I 0.17
$4.01 0.38
84.65 0.45
FEUSTRUCT (FDn))
81.27:1 1.13
69.61 1.87
70.891: 1.21
68.29:2
1.47
63.38:1
0.90
68.751
1.18
84.711 0.13
64,02 0.38
84.77.1 0.40
FEUSTRUCT
$1.30.1
79.27
78.36
0.82
68.65
1.49
65.43.1
66.44
0.33
PSOSTRUCT (D6G)-P
$1.90:1
63.451
0.17
64.112
84.752
PROSTRUCT (FED))
$1.68
0.90
68.00.1
2.85
70.61
1.69
08.39.1
1.48
63.74.1
0.35
65.45.1
1.21
$4.77 0.15
84.10
0.33
84,80.1 0.34
PEDSTRUCT (H2V)-F
81.02+
79.88++
78.79-
0.96
68.35
1.45
65.93+
66.844
63.03
0.41
85.79-
85.47-
LOUNAIN
RANDOM
KHEANS
LOUVAIN
RANDON
KMEANS
LOUVAIN
KANDOM
KMEANS
CENTRAL GNN
$4.38 1.96
94. 10:1 0.30
61,422 0.80
31.10.1
L
37.74:: 0.39
FEDSTRUCT (DEG)
49.66
41.82+
186
89.72++
40.93+ 0.39
38.67-
38.78-
FEDSTRUCCT (FEn.)
49.36
1.89
41.89
1.67
42.54
1,56
92.022
0.41
89.78-2
0.38
90,07 0.42
41.03
0.37
38.65= 0.44
38.89 0.49
FroSTRUCT
58.741: 1.89
$2.601: 1.18
53.42:
1.69
91.21 0.42
90.93:1 0.27
91.423 0.72
48.81 0.51
40.97 0.64
41.063 0.42
PEOSTRUCT (Dnc)-F
49.30:
1.54
41.94 1.55
42:23
1.84
92.07
0.35
90.31
90.68 0.34
40:05 0.37
38.58= 0.53
38.88 0.43
PROSTRUCT (PRDa)-P
92.002
90.1220:48
(USTRUCT(12V) 55.75.1 1.46
53.09.1
1.85
52,95.L
1,72
90,40.1
0,58
90.74.1 0:29
91.11.1 0.61
40 10.56.1.
0,56
41,07 0.56
41.23.1 0.45
In FEDSTRUCT using task-agnostic NSFs, each client is provided with S. i.e. the NSFs of all clients. Consider an honest-but-curious client with NSFs {8 v E V.l. Client may target client by identifying NSFs within client j that closely match some of its own NSFs. By this simple procedure, client may compare the topology of the matched local nodes and infer the topology of some of the nodes within j. Furthermore, as 0, is shared among all clients, client would potentially be able to guess the labels of the identified nodes within client j. Given node's label and topology, may be further possible to infer something about the node features. Using task-dependent NSF, i.c., HOP2VEC, the situation is similar.
Next, we discuss how to alter FEDSTRUCT to prevent reconstruction of the local NSFs, therefore mitigating the aforementioned attack, starting from the task-agnostic NSF generators. From Proposi- tion 3 the summation over V may be split into summation over clients. The prediction and local gradients for client i may then be written as
ÿ softmax
Σ
E
Am Avugo (sw) ff((l)) VE D,
(45)
]E[K] WEV.
(0)
ΣΣ Σ
Aru 0go 20,n
(gv - yo),
Vg E [0.]].
(46)
30.g
JEN] V
Notably, client may evaluate its local gradient provided access to
g
Σ
Amngo,(s.) (su), Ve E V.
(47)
NEV.
Ogo
8(0) Dq
Σ WEV.
Ag E [0,1], Vu e D;
(48)
00..g
for each client j E [K]. For client j * i be able to evaluate these quantities, it needs access to A.u for all E V. and E V. i.e., the weighted sum of the ê-hop paths, E [4], from nodes in client to nodes in client j. Following Appendix D client has access to ovu for V/, and u V. Notably. ava # Agn. due to different degree normalizations. Hence, to obtain the required quantitites in Eq. [7
and Eq. 48 client may share (Āva u E V. u E Vý} with client E [K] after the algorithm in Appendix has finished.
Compared to FEDSTRUCT, the gradients of the above method cannot be calculated locally but bring the benefit of clients only knowing their own local NSFs rather than the individual NSFs of others.
26

---

Published as a conference paper at ICLR 2025
Because of this, the training has to be done in two phases for each iteration where phase accounts for each client i E [K] to collect the quantities in Eq 47 and Eq. 48 from all other clients and where each client computes the local gradients and shares these with the server during phase 2. Note that the communication complexity in each training iteration does not increase as Eq. 47 and Eq. amounts to sharing [c and [0,|c parameters, respectively, where c is the number of class labels. Hence, in total, each client must share (D>) V.J1 + |0,] )e parameters in each iteration with the other clients. Note that this sharing can be made either via the server or via peer-to-peer links.
Although a formal privacy analysis seems formidable, we may follow an approach similar to LLi al. 2023) to argue around the difficulty of perfectly reconstructing the local NSFs. To this end, we take a conservative approach and consider colluding. Hence, we may consider two clients where client 1 the attacker and client 2 is the target.
clients where all but one client is
In each iteration, client receives s.²) E R and 80y E R for v E V1 and E [[02]]. To evaluate s( client 2 utilizes || a d, -i-imensiooall NSFs where the L0-norm counts the number of non-zero elements. Hence, for each received aggregate s!? client 1 obtains observations from ||a, d, unknowns. In total, client will collect [V] such observations, i.e., it observes c <|Vi parameters. Assuming a, for client 2, the worst-case scenario with all a, being non-zero in the same locations with m non-zero elements, client will use the same inputs for each observation in client Hence, if rıd, c. client is unable recover individual NSFs from client 2. Notably, client 2 has full control as it knows m and can count the number of queries from client 1 and refuse to answer if it exceeds mdg/c. Similarly, to evaluate s!?) client utilizes ||a.llo d, ddmiennsional inputs to compute a c-dimensional output. Hence, client will share 00./c parameters, computed from ||a d, parameters |V1 times. Hence, again considering the worst-case view, if md, c 0, Vi client 1 cannot reconstruct the local gradient. Again, client 2 may monitor the number of queries such that the condition is not violated.
When using HOP2VEC as the NSF generator, we no longer optimize over 0, but rather over the NSFs S directly. The problem we face in FEDSTRUCT is that each client has access to S. To alleviate this issue, we use Theorem 2 to split the summation over V to obtain
s( 8 6
SvuSu:
Vu E Dj
(49)
NEV,
Furthermore, the local gradients for the NSFs in client are given as
VsL((O,S) Σ A - y.)) VEV.
(50)
We note that Eq. 49 is required to compute the local predictions on D/, and hence to obtain Eq, 50 In this version of FEDSTRUCT, the training procedure will be divided into three phases. Phase I amounts to each client evaluating Eq. for all other clients and sharing the results. This results in
the sharing of 4 1 |c in total for each client. Phase 2 amounts to each client evaluating its local gradient in Eq. 50 and sharing it with the server, similar to the original FEDSTRUCT. Next, the server aggregates the local gradients over S and partitions the result with respect to the entries residing in each client (the server must know the unique node-IDs in the clients) and returns only the NSF gradients corresponding to the nodes residing in each client. Using this procedure, clients will only have information about the NSFs pertaining to their local nodes.
Next, we again consider Monest-but-ccrionn clients with all but one colluding against a single target. We denote the colluding clients as client and the target as client 2. Client 1 observes Eg. 49 which constitutes c observations from ll c-dimensional inputs. Assuming a worst-case scenario as above with all a, having non-zero entries in the same locations, client 1 observes in total c| </>>, parameters from mc inputs. Hence, to prevent client 1 from perfectly reconstructing individual NSFs, client 2 must ensure that m > [V.l. Again, client 2 has full control over this by counting the number of queries ensuring it is below m.
To summarize, we are able to alter FEDSTRUCT to reveal less information about individual nodes without impacting the performance. Further, each client may prevent perfect reconstruction from being possible by limiting the amount of information that is shared with other clients. To go beyond perfect reconstruction and understand the risk of approximate reconstruction seems formidable.
27

---

Published as a conference paper at ICLR 2025
G.2 HETEROPHILY
Employing decoupled GCN within the FEDSTRUCT framework allows the nodes to access larger receptive fields compared to standard GNNs. This proves advantageous in handling heterophily graphs. This is because in heterophilic graphs, neighboring nodes may not provide substantial information about the node labels. In such scenarios, the mixing of embeddings from higher-order neighbors involves a greater number of nodes with the same class, promoting increased similarity among nodes of the same class. Higher-order neighbor mixing one of the well-known approaches to deal with heterophilic graphs (Zheng al.) 2022). Notably, (Abu-EI-Haija et al. (019) aggregates embeddings from multi-hop neighbors showing superior performance compared to one-hop neighbor aggregation. To show why higher-order neighborhoods help in heterophilic settings, (Zhu et al. (020) theoretically establish that, on average, the labels of 2-hop neighbors exhibit greater similarity to the ego node label when the labels of 1-hop neighbors are conditionally independent from the ego node.
Furthermore, the parameters 1 can be trained adjusted to control the mixing weight of different (-hop neighbors. This allows the network explicitly capture both local and global structural information within the graph. Specifically, different powers of the normalized adjacency matrix
A', E [Ls]. collect information from distinct localities in the graph. Smaller powers capture more local information, while larger powers tend to collect more global information. Consequently, selecting the appropriate parameters {By Iy enables the model to adapt to various structural properties within graphs.
An additional well-established strategy for addressing heterophilic graphs involves the discovery of potential neighbors, proposed by (Zheng et al. 2022). The concept of potential neighbor discovery broadens the definition of neighbors by identifying nodes that may not be directly linked to the ego nodes but share similar neighborhood patterns in different regions of the graph. GEOM-GCN (Pei et al. 2020) introduces a novel approach by defining a geometric Euclidean space and establishing a new neighborhood for nodes that are proximate this latent space. To this aim, FEDSTRUCT employs NSFs to foster long-range similarity between nodes that may not be in close proximity in the graph but exhibit proximity the latent structural space. Specifically, the use of methods such as STRUC2VBC (Ribeiro et al. (017)) for generating NSFs enables the creation of vectors that share similarity, even among nodes that may not be directly connected in the graph. Consequently, the NSEs produced by these NSFs also demonstrate similarity, contributing consistent node label predictions. This approach showcases FEDSTRUCT'S capacity to capture latent structural relationships and enhance the model's 's ability to make accurate predictions in the context of heterophilic graphs.
The robustness of FEDSTRUCT in handling heterophilic graphs is demonstrated in Table 2 and Ta- ble 6 for the Chameleon and Amazon Ratings datasets. Such datasets are heterophilic datasets, with Chameleon having a higher degree of heterophily than Amazon Ratings (see Table 4 For both datasets FEDSTRUCT yields performance close to Central GNN and significantly outperforms FEDSAGE+ and FEDPUB. In Table 2 for the Chameleon dataset and 20 clients, FEDSTRUCT with HOP2VEC achieves an accuracy of 52.76% compared to 34.33% for FEDSAGE+. For the Amazon Ratings dataset and 20 clients, FEDSTRUCT with HOP2VEC achieves an accuracy of 41.16% compared to 36.09% for TEDSAGE+ Note that the improvement is larger for the more het- erophilic dataset. Similar results can be observed for different partitioning methods, see Table For Chameleon, FEDSTRUCT with HOr2VEC outperforms FEDSAGE4 with 6.33% 16.88% and 15.73% for Louvain, random and K-means partitioning, respectively. For Amazon ratings, FEDSTRUCT with HEP2VEC outperforms FEDS AGE+ with 0.07%, 5.05%, and 3.12% for Louvain, random and K-means partitioning, respectively.
We highlight that we have not specifically optimized the parameters of FEDSTRUCT to handle heterophilic graph structures, hence it might be possible to improve the performance of FEDSTRUCT for these heterophilic graphs.
The robustness of FEDSTRUCT to different degrees of homophillyheetropphily (in contrast to frame- works such as BEDSAge# and FEDPUB), underscores the adaptability and effectiveness of our framework diverse graph scenarios, affirming its potential for wide range of applications.
28

---

Published as a conference paper at ICLR 2025
Ulobal
Augresnted loaal
Pelended bvesing
Queic 8% #oNSut
1,4,8
Pal
0
Iobidd mede enkaeind cade
sede Bucaaur cndlchling
Figure 5: PEDSTRUCT framework when the server er has knowledge of the global graph's connections. Global Graph: underlying graph comsisting of intercomeeseed sihgraphs. Local graphe: clients' subgruphs augmensed with exteraal modes (without feutures labels). Stracture encoding: The generales node structure emholdings each node
them the clients. Angiseated local graphe: Genenai node feature embodkings. Federated learning: Federssed learning step explotingg node feature embeddings and node structure embeikings.
H FEDSTRUCT WITH KNOWLEDGE OF THE GLOBAL GRAPH
In this section, discuss FEDSTRUCT for the scenario where the server has complete knowledge of the global graph's connections. This scenario is commonly encountered in applications such as smart grids and pandemic prediction. Importantly, also in this scenario assume that the clients remain unaware of the local graphs of other clients.
If the server has knowledge of the global graph, the NSEs may be computed centrally. Hence, contrary to the case where the central server lacks knowledge of the global graph, any GÑN model may be used, i.e., it is not restricted to decoupled GCN (although, in Sec. H.3 we discuss the advantages of using a decoupled GCN). Furthermore, any conventional NSF methods may be used such as NODE2 and GDV that require knowledge of the L-hop neighborhood.
At each client i E [K]. node prediction is performed based on both the NFEs h. and node structure embeddings (NSEs), Zu. To this aim, we pass the NFEs and NSEs through fully connected layer with parameters c.
G softmax(O! (z. (hh.)) softmax ((e (T) + (O!))
Ve V;
(51)
We denote the vectorized version of O by 0.. From equation 51 we have that 0.
As the server is able to generate the NSEs, at each iteration, NSE updates will be sent to the corresponding clients. For clients to send back gradient updates, they require the NSEs and their derivatives with respect to the generator weight parameters, as seen in Proposition
The FEDSTRUCT framework for this setting is conceptually shown Figure
Using generic GNN, the local gradients are given in the following theorem.
Proposition 4. Let (0), 0 (0:110,|(02) be the local training loss for client i Eq. 4 and go be given in Eq. 57 The gradient
VoLi(0) = (OC,(0) 00;
Vj E [01
(52)
is given by
(C,
Oz.
Σ
( (g. yy)
Vj E [10,]],
00..
30g,
VEV
(C,
Sh
(1 (g. yv)
Vj E [[0l]]
30,,j
NED
OC2(0)
a(O (5) TZ))
(5. - y Vj E [
O c.j
VED
(C,
a a(O Thw)
(go (v) Vj E |0
(0
o c.j
VE
where 0.g denotes the j-th entry of vector 0 g-
29

---

Published as a conference paper at ICLR 2025
Algorithm 4 Algorithm for FEDSTRUCT with knowledge of the global graph
input Global graph 9, sGNN and IGNN models, NSF generator function QUSF, K clients with respective subgraphs { model parameters 0 (z)
S (E) for e=1 to Epochs do
S(L) < (S,
for i=1 to K do
Client collects from the server
Client collects collects { Ve E V&J from the server
Client i collects collects
0x Ve V.} from the server 80
H (4) fGNN,, &,)
for v V; do
y. softmax ! (z. hh.)) end for
Calculate (0) based Eq.
Calculate (0),(0) from Proposition
Send (o) the server
end for
Calculate V (() based on Eq. 0 - 0 (V)
end for
The proof of the theorem given Section H.1
Note that client cannot compute VoL:(0) directly caleulating dz requires knowledge of the global graph connections. Hence, the server must provide dz FEDSTRUCT framework when the server has knowledge of the global graph is described in Alg.
20, along with x, for all E V,, The
H.1
PROOF OF PROPOSITION
Using Eq. 23 we have
(c,
Oz.
Σ
(g. - yv).
00,
00,
VEİ.
(0!")) ! IT h.. Taking the derivative of 2, with respect to different entries of
where qu 0 leads to
0q. Oz (s)
vjj E [|0.]]
(53)
00.
J0..j
0q.
Oh
O
Vj E [|0|]]
(54)
00
a0r.j
0q.
((e
(s)
Zu)
Vj E [
(55)
(0(s)
80(=)
0q.
h
Vj [0 [].
(56)
(f
00(1)
cj
Substituting Eq.
Eq.
Eq.
and Eq. 56 Eq.
23 concludes the proof.
H.2 RESULTS
As aforementioned, knowledge of the adjacency matrix allows FEDSTRUCT to utilize NSF generators such as GDV and N2V, see Appendix A In Table [8] we provide some results for these NSFs and benchmark them against GLOBAL DGCN and FEDSTRUCT (H2V) without knowledge of the
30

---

Published as a conference paper at ICLR 2025
Table Classification accamcies for PEOSTRUCT with and without knowledge of the adjacency matrix. 'The results are shown for 10 clients with 10-10-80 traint-vll-les
COKA +
CITISEER
PUBMED : 0.34
CENTRAL: DGON
68 =
LOUNAIN
RANDOM
KMEANS
LOUYAIN
RANDOM
KMEANS
VAIN
RANDUX
KMBAAN
GLOBAL ADJACENCY MATRIX NOT KNOWN SURVER
PEDSTRUCT (DGCN+H12V) 81.34 1.40 79.62 0.85 30.34 0.62 68.48 I. 0.98 66.34 1.03 66.62 1.59 $3.29 0.34 65.48 0.29 85.93 0.30
GLOBAL ADJACENCY MATRIX KNOWN SERVER
(DGCN+GDV)
81.271 1,56 72.09: 74.552L 1.47 68.8222 64.92:1 1.04 66.22
85
0.26
PIDSTRUET (DGCN-N2V)
22.26 1.21 80.76 0.91 80.97 1.01
66.88 1.19 67.23
24 23 0.31
87.08
PEDSTRUCT (GNN+H2V)
80.87- 0.51 66.84-1
0.71 68.06
1.22 68.89
0.99
63.77:
1.71 64.56 0.96 76.04- 6.77 85 85.27-1 0.45 92.92 4.92
PEDSTRUCT (GNN-GDV)
80. 00.62:1.0 0.79 69. 50.: 1.23 69, 862 1.94 96 1.09 64.78 1.11 64. 4.00 1.17 $1.562 5 46 85. 0.40 85.362
PUOSTRUUT (GNN+ N2V) 81.23
1.02 75.24 75.91 0.90
69.224
64.80
53 1,15 16.11 86.24 0.87 81.04
CHAMELEON
AMAZON PHOTO
AMAZON RATINGS
CENTRAL DOCN
$4.39 + 2.24
92.27 = 0.79
40. + 0.46
LOUVAIN
GLOBAL ARJACENCY MATRIX NOT KNOWN TO SERVER
PEDSTRUCT (DGCN+H2V) 53.15 1.26 52.37 + 0.95 52.85 2.44 90.56 0.58 90.81 0.73 91.07- 0.79 40.93-
4:3--:0000 0.39 41.00- 0.27 40.86 0.50
GLOBAL
PROSTROLT (DVC
48.08 1.64 39.91 1.07 70.7 2.76 91.68 2 0172 90.51 0.55
90.33-t
0.57
41.43
0.51
39
54.54
0.41
39.65 0.43
PEDSTRUCT (DGCN+N2V) 49.23 1.58 43.34
1.43 44,99 2.88 91.86 H. 0.78 91.53 0.46
91.65
+ 0.44
41.74
0.30 41.84 0.38
41.28 0.55
PROSTRUCT (GNN+H2V)
40.424
39.47: 1.53 93.36
91.07
0.57 90.81
35.13
0.44
(GNN-GDV)
46.40.1
2.27
38.91
91.52:1
0.83
PEDSTRUET (GNN-N2V)
48.46 2,21 45.12 2.14 46.02 2.77 91.78 92.00st 0.59 91.59 40.96 0.33 40.29: 0.50 40.12
adjacency matrix. While FEDSTRUCT (GDV) is mostly inferior to FEDSTRUCT (H2V), leveraging NODE2 VCC as the NSF generator boosts the performance even further in several scenarios. For example, on Cora with Louvain partitiong, the performance is improved from 81.23% to 82.78%. Even more, arbitrary GNN architectures are supported when the global adjacency matrix is available at the server and may potentially improve performance even further.
H.3 GNN vs DECOUPLED GRAPH CONVOLUTIONAL NETWORK
As mentioned carlier, the server has knowledge of the global graph, FEDSTRUCT can operate with any underlying GNN model. However, in Figure 6 we demonstrate the advantages of incorporating a decoupled GCN into our framework. To this aim, we provide results for FEDSTRUCT with both an underlying decoupled GCN and standard GNN (GRAPHSAGE) for semi-supervised learning scenario with varying fraction of labeled training nodes Specifically, we show the accuracy for scenarios involving 50%, 10,, and 1% labeled nodes. For 50% and 10% of labeled nodes, FEDSTRUCT with both underlying decoupled GCN and standard GNN yield similar results. However, in heavily semi- suni-supervised scenario (as encountered in applications like anti-money laundering). the accuracy of FEDSTRUCT with standard GNN experiences a significant decline. In contrast, FEDSTRUCT with decoupled GCN achieves performance close to that of central GNN even in such a challenging scenario. This highlights the critical role of employing decoupled GCN to effectively tackle the supervseee learning scenarios. Moreover, knowledge the global graph edges enables the use of NSFs such as NODE2VES which, seen in Figure 6 sometimes enhances the performance compared to HEC2
H.4 COMMUNICATION COMPLEXITY
In this Section, we discuss the communication complexity of FEDSTRUCT when the server has knowledge of the global graph. Note that, in this case, the NSEs can be computed by the server. Hence, no sharing of information between the clients is needed and clients only communicate with the server.
During the training, in each training round, each client collects 0 and returns V VoL, (0, S) to the server, totaling communication of 2F. K - parameters during the training. This is consistent
31

---

Published as a conference paper at ICLR 2025
FEDSGD GNN
FEDSTRUCT (dGON, H2V)
FEDSTRUCT (JGCN, N2V)
FEDSTRUCT (GNN, H2V)
100
PEOSTRUCT N2V)
Central GNN
9595
95
94
949494
93
91
91922.9
91
91
Accuracy (%)
90
87
85
85
83
80
80
75
75
70
10
50
Fraction of training nodes with labels (%)
Figure fraction
lubels for FEOSTRUCT undectying decoupted GCN undectying stundard (GRAPHSAGE)
pariitioning.
Table 9: Communication Complexity of PEDSTRUCT when the Server has Knowledge of the Global Graph.
DATA
BEFORE TRAINING
TRAINING
PEDSTRUCT
O(E K 10 E.n.d (0))) O(E 00 n- 10 E.K
PEDSTRUCT HOr2VEC
d²)
across all versions of FEDSTRUCT. Additionally, the server sends 2,, Ve E V, and (30 Ve E V. each client, adding up E d((0) + parameters. The dominant term of the complexity E n - d (0), which scales with n. The complexity is therefore of the same order as that of FEDSAGE+.
The use of HOP2VEC entails some additional communication complexity, corresponding to the collection of { (zz. Ve V..q E V} by client i, constituting - de parameters, and sending (8,
(,,,(0, S) to the server, constituting E K graphs, E n² is the dominant term out of the two.
d parameters. In practical scenarios with large
With HOP2VEC, the dominant complexity term is the order of n², which is impractical for large networks. It should be noted, however, that real-world graph-structured datasets are sparse. Furthermore, each node only depends on its L--hop neighbors. Hence, many of the values [ Ye
Di q V) are zero and do not need be communicated. Assuming an average node degree d and L, layers, for which each node has access to d' nodes, the complexity of FEDSTRUCT with Hop2 VeC on the order of min d4, , , For small average degree d and Ls, the complexity can therefore be reduced significantly. The communication complexity is reported in Table 9
32


Reviews:
[{"review_id": "SUXnwpzzR7", "reviewer": "Reviewer_TSTT", "summary": "The paper works on subgraph FL for node classification, where inter-connections between different clients is important. \n\nIt first computes a global L-hop neighborhood matrix before training. During training, it uses GNN for node feature embedding and use L-hop matrix multiplying a trainable matrix to calculate node structure embedding. Both embeddings are concatenated to get the final prediction result. Experiments show the performance.", "questions": "As in weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. Subgraph FL with inter-connections is an important topic.\n2. Completing the missing L-hop features by learning a L-hop node structure embedding is an interesting idea.\n3. Experiments show the performance.", "weaknesses": "1. Privacy leakage. Before training, clients communicate to calculate the L-hop neighborhood matrix $\\hat{A}$. In the 2-hop case, since the client knows 1-hop neighbors and the information during the communication, it is still able to reconstruct the 2-hop graph. Pruning cannot guarantee the privacy.\n2. FedSage+ and FedGCN can outperform FedStruct.\n3. In FedGCN, the server does not require a global adjacency matrix for homomorphic encryption. It only needs to know the node ids for encrypted aggregation and identify which nodes belong to each client for sending the aggregation result back.", "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": "", "extra_scores": {}}, {"review_id": "EiBAu2FZWN", "reviewer": "Reviewer_h91B", "summary": "This paper presents a novel framework, FEDSTRUCT, to tackle the challenge of federated learning on graph-structured data distributed across multiple clients, particularly in scenarios involving interconnected subgraphs, it utilizes explicit global graph structure information to capture inter-node dependencies. The effectiveness of FEDSTRUCT is validated through extensive experiments on six datasets for semi-supervised node classification, demonstrating performance that approaches that of centralized methods across various scenarios, including different data partitioning strategies, levels of label availability, and numbers of clients.", "questions": "See the weakness.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1)\tThis paper studies a significant and interesting problem, and the method can be used in a wide range of real-world applications. \n2)\tThe paper is overall well motivated. The proposed model is reasonable and sound. Theoretical analysis is performed.", "weaknesses": "1) The abstract lacks a description of the background. I recommend briefly outlining the context of the issues addressed in this paper before elaborating on the key problems that are solved.\n\n2) Figure 1 has not been cited and its placement is too early in the text; please adjust this detail. Additionally, Figure 2 is unclear; I recommend adjusting the proportions or border thickness of each subfigure.\n\n3) In the Related Work section, you mention that FED-STAR shares structural knowledge, yet in the conclusion, you state, \"No work has leveraged explicit structural information in SFL.\" Are \"structural knowledge\" and \"structural information\" the same concept? Please provide more clarification in the conclusion.\n\n4) The formula following (1) is missing a comma; please check for similar issues throughout the paper.\n\n5) Privacy is one of the directions addressed in this paper, yet most references are to other works. I suggest including some original proofs or experiments related to privacy to enhance the completeness of the article.", "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": "", "extra_scores": {}}, {"review_id": "mTszXuQMta", "reviewer": "Reviewer_mTWE", "summary": "The paper proposes a novel SFL method called FEDSTRUCT, which leverages the augmented explicit structure $\\bar{A}$ to promote the SFL model performance. Moreover, they propose HOP2VEC to learn local structure embedding. FEDSTRUCT precalculates the $\\bar{A}$ with privacy protection and prunes the $\\hat{A}$ matrix to decrease the calculation complexity and communication costs, thus balancing the communication-privacy-accuracy trilemma.", "questions": "see weaknesses.\n\nIf the first questions can be well explained, the rating should be higher.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The proposed method is novel, utilizing augmented explicit structure which can be regarded as global knowledge to promote the performance of the SFL model. \n2. Utilizing pruning skills decrease the calculation complexity and communication costs.\n3. Well written and well formulated problem.", "weaknesses": "1. **Focus on Privacy**. How to  obstain the local L-hop combined adjacency matrix while not share the L-hop global Adjacency Matrix maybe play the core role in FEDSTRUCT. In APP D, the equations [30] [31], [32], what does the $\\hat{A}^{[K]}_j$ mean? Should be $\\hat{A}^{[k]}_j$? If so , the next question, for client $i$, how does it know all $\\hat{A}^{[k]}_j$ for $ k \\in [K]$ without sharing the global adjacency matrix in all clients.  So another question when computing, the $\\tilde{A}^{[i]}_j \\in \\mathbb{R}^{|\\tilde{V}_i| \\times |{V}_j|}$, the same to $\\hat{A}^{[i]}_j$? So $\\hat{A}^{[i]}_k \\times \\hat{A}^{[k]}_j$ should be $\\mathbb{R}^{|\\tilde{V}_k| \\times |{V}_k|}  \\times \\mathbb{R}^{|\\tilde{V}_k| \\times |{V}_j|}$， but according the definition before, the $|\\tilde{V}_k| \\neq |{V}_k| $, how does the computation continue? Maybe I miss something? I really hope you can explain it for me to understand the feasibility of FEDSTRUCT. That's my main concern about this paper.\n\n2. **About the hyperparameters.** **1)** The analysis of $\\beta$ is not enough, an essential parameter in FEDSTRUCT for various homophilic and heterophilic graphs, which directly dominate the performance and affect the  judgment of FEDSTRUCT's contributions. **2)**  It is so strange that the parameter $L_s$ and $L$ is set to1 for heterophilic graph chameleon in table 5. As the author states in lines 297-299, a heterophilic graph should own multi-hop nodes and a high-frequency filter to augment the local graph representation.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)