Decoupled Subgraph Federated Learning

## Abstract

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 interconnections 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.

## 1 Introduction

Figure: Figure 1: GNN node classification accuracy from exploiting different sources of information over different datasets.

Many real-world data are graph-structured, where nodes represent entities, and edges encapsulate relationships or connections between them.
For example, in demand prediction for the energy grid, nodes represent power stations and edges embody transmission lines.
Similarly, the identification of vulnerabilities in global supply chains
involves nodes as individual companies or production facilities and edges as their interconnections. Another real-world scenario is anti-money laundering, where nodes symbolize accounts and edges correspond to transactions, which are strictly confidential.

Graph neural networks (GNNs) are a class of neural network architectures tailored for graph-structured data with proven success in various domains, such as drug discovery, social networks, or traffic flow modeling Stokes et al. (); Fan et al. (); Jiang and Luo ().
In practical real-world applications, the graph data is often naturally distributed across multiple clients, i.e., the global graph encompasses multiple, non-overlapping subgraphs. For instance, the examples of energy grids, global supply chains, and anti-money laundering involve local graphs delineating regional energy grids, internal supply chains of distinct corporations, and the internal transactional networks of financial institutions, respectively.

For these and many other applications, data sharing among clients is unfeasible due to privacy, regulations, or proprietary restrictions. In this context, federated learning (FL) McMahan et al. (), emerges as a promising approach to exploit (global) graph-structured data while safeguarding data privacy. Various flavors of federated GNNs exist Liu et al. (). In this work, our focus is on one of the most prevalent scenarios: subgraph FL Zhang et al. (),
where clients hold subgraphs of disjoint nodes that integrate into a comprehensive global graph with interconnections between the different local subgraphs.

Training a GNN involves aggregating feature representations of neighboring nodes to generate more expressive embeddings Kipf and Welling (); Hamilton et al. (); Veličković et al. ().
In subgraph FL, a key challenge is facilitating training when some neighboring nodes reside in other clients.
Several approaches have been proposed to address this challenge Zhang et al. (); Peng et al. (); Chen et al. (); Du and Wu (); Lei et al. ().
The prevailing issue with all these approaches lies in their reliance on sharing the original, or generated, node features or node embeddings with other clients. This raises serious privacy concerns in situations when the node features are sensitive.
To remedy this issue, inspired by Cui et al. (), we notice that the global graph structure alone is informative, often less sensitive, and may be used to train strong classifiers beyond what is achievable with vanilla federated learning, see Fig. 1.
In this work, we hinge upon this observation to develop strong subgraph FL algorithms.

Our contribution. We address the problem of subgraph FL for node classification within a global graph containing multiple, non-overlapping, subgraphs belonging to different clients. More precisely, we consider the challenging scenario where the server does not possess knowledge of the global graph connections or node features, i.e., the local subgraphs are confidential. Our contributions include:

- •
We propose a novel subgraph FL framework, named FedStruct,
that exploits deep structural dependencies. To safeguard privacy, FedStruct decouples graph structure and node feature information: Unlike existing approaches, FedStruct eliminates the need for sharing (or generating) node features and/or embeddings. Instead, it leverages global graph structure information to capture inter-node dependencies among clients.
FedStruct incorporates a decoupled graph convolutional network (decoupled GCN) Liu et al. () to limit information exchange between clients.
- •
We introduce a method to generate task-dependent node structure embeddings, coined Hop2Vec, that adapts to the graph and demonstrates competitive performance compared to task-agnostic methods such as Node2Vec Grover and Leskovec (), graphlet counting Pržulj (), or the technique used in FedStar Tan et al. ().
- •
By integrating a decoupled GCN and leveraging deep structural dependencies within the global graph, we address the semi-supervised learning scenario. With these components, FedStruct yields outstanding performance in scenarios with limited number of labeled training nodes. In heavily semi-supervised settings, it significantly outperforms both FedSage+ and FedPub. Further, FedStruct relies on non-local neighbor-extension and inter-layer combination, techniques commonly used to handle heterophilic graphs Zheng et al. ().
To the best of our knowledge, FedStruct is the first subgraph FL framework capable of handling heterophilic graphs.
- •
We validate the effectiveness of FedStruct on six datasets for semi-supervised node classification, showcasing excellent performance close to a centralized approach in multiple scenarios with different data partitioning methods, availability of training labels, and number of clients. The source code is publicly available (https://anonymous.4open.science/r/FedStruct-B70D/).

## 2 Related Work

Subgraph federated learning. The works most closely related to ours are FedSage+ Zhang et al. (), FedNI Peng et al. (), FedPub Baek et al. (), FedCog Lei et al. (), and the works of Zhang et al. (); Liu et al. (); Zhang et al. (); Chen et al. (); Du and Wu ().
FedSage+ Zhang et al. (), the first method to address subgraph FL,
assumes no knowledge of cross-subgraph interconnections. To deal with missing links, it augments the local subgraphs by in-painting cross-subgraph $1$-hop missing neighbors. Specifically, it estimates the number of missing neighbors for each node
and generates features for these neighbors, relying on a strong homophily assumption.
FedNI Peng et al. () proposes a similar in-painting strategy, utilizing a generative adversarial network (GAN) for
generating the missing neighbors and their features, resulting in improved quality of generated node features. This in-painting idea has been extended to accommodate graphs with different node types Zhang et al. () and missing links between subgraphs Liu et al. (). To exploit deeper structural dependencies, building on FedSage+, Zhang et al. () generates node embeddings for missing neighbors, containing information about the node’s $k$-hop neighbors.
FedPub Baek et al. () employs personalized aggregation for each client with weights based on the functional similarity among clients.
The functional similarity is estimated at the server by computing the cosine similarity of the output predictions of the client GNNs when queried with the same random subgraph.
Notably, interconnections are not considered.
FedCog Lei et al. () assumes knowledge of cross-subgraph interconnections and proposes a different approach for subgraph FL, decoupling local subgraphs into an *internal* graph and a *border* graph. Correspondingly, the graph convolution in the underlying GCN is divided into two steps on the two decoupled graphs. FedCog requires sharing intermediate embeddings of local nodes with neighboring clients, in which case it is equivalent to a graph convolution on the global graph.
Other works tackle the problem of subgraph FL through sampling techniques Chen et al. (); Du and Wu ().
Importantly, all these prior methods Zhang et al. (); Peng et al. (); Lei et al. (); Zhang et al. (); Liu et al. (); Zhang et al. (); Chen et al. (); Du and Wu () require the sharing of either original or generated node features or embeddings among clients and operate under a homophily assumption, which does not hold in many practical scenarios.

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. (); Tan et al. ().
To increase GNN’s representation power, Bouritsas et al. () introduces structural information to the aggregation function.
The authors demonstrate that the proposed architecture is strictly more expressive than standard GNNs.
FedStar Tan et al. (), presents an FL scheme to exploit explicit structural information by sharing universal structural knowledge among clients to enhance local performance.
No work has leveraged explicit structural information in subgraph FL.

## 3 Preliminaries

Graph notation. We consider a graph denoted by
$\mathcal{G}=(\mathcal{V},\mathcal{E},\boldsymbol{X},\boldsymbol{Y})$, where
$\mathcal{V}$
is the set of $n$ nodes,
$\mathcal{E}$
the set of edges,
$\boldsymbol{X}\in\mathbb{R}^{n\times d}$
the node feature matrix, and $\boldsymbol{Y}\in\mathbb{R}^{n\times c}$ the label matrix.
For each node $v\in\mathcal{V}$, we denote by $\boldsymbol{x}_{v}\in\mathbb{R}^{d}$ its corresponding feature vector and by $\boldsymbol{y}_{v}\in\mathbb{R}^{c}$ its corresponding one-hot encoded label vector.
We consider a semi-supervised learning scenario and denote by $\tilde{\mathcal{V}}\subseteq\mathcal{V}$ the set of nodes that possess labels. The labels of the remaining nodes are set to $\boldsymbol{0}$.
We also denote by $\mathcal{N}_{\mathcal{G}}(v)=\{u|(u,v)\in\mathcal{E}\}$ the neighbors of node $v$.

For a given matrix $\boldsymbol{M}$, let $m_{uv}$ be its $(u,v)$-th element. The topological information of the whole graph is described by the adjacency matrix $\boldsymbol{A}\in\mathbb{R}^{n\times n}$, where $a_{uv}=1$ if $(u,v)\in\mathcal{E}$.
We define the diagonal matrix of node degrees as $\boldsymbol{D}\in\mathbb{R}^{n\times n}$, where $d_{uu}=\sum_{v}{a_{uv}}$.
Furthermore, we denote by $\boldsymbol{\tilde{A}}=\boldsymbol{A}+\boldsymbol{I}$ the self-loop adjacency matrix, and by $\boldsymbol{\hat{A}}=\boldsymbol{\tilde{D}}^{-1}\boldsymbol{\tilde{A}}$ the normalized self-loop adjacency matrix, where $\tilde{d}_{uu}=\sum_{v\in\mathcal{V}}\tilde{a}_{uv}$.
We also define $[m]=\{1,\dots,m\}$.

GNNs.
Modern GNNs use neighborhood aggregation (propagation step) followed by a learning transformation (update step) to iteratively update node representations at each layer.
Let $\boldsymbol{h}_{v}^{(l)}$ be the feature embedding of node $v$ at layer $l$, with $\boldsymbol{h}_{v}^{(0)}=\boldsymbol{x}_{v}$.
At layer $l\in[L]$ of the GNN we have

$$ $\displaystyle\boldsymbol{h}_{\mathcal{N}_{\mathcal{G}}(v)}^{(l)}$ $\displaystyle=\textsc{Aggregate}^{(l)}\bigg{(}\Big{\{}\boldsymbol{h}_{u}^{(l-1 )},~{}\forall u\in\mathcal{N}_{\mathcal{G}}(v)\Big{\}}\bigg{)}$ (1) $\displaystyle\boldsymbol{h}_{v}^{(l)}$ $\displaystyle=\textsc{Update}^{(l)}\Big{(}\boldsymbol{h}_{v}^{(l-1)}\,,\, \boldsymbol{h}_{\mathcal{N}_{\mathcal{G}}(v)}^{(l)}\,,\boldsymbol{\Theta}^{(l) }\Big{)}\,,$ (2) $$

where $\boldsymbol{\Theta}^{(l)},\textsc{Aggregate}^{(l)}$ and $\textsc{Update}^{(l)}$ denote the learnable weight matrix, aggregation function, and update function associated with layer $l$ of the GNN, respectively.

Decoupled graph convolutional networks.
A significant limitation of GNNs is over-smoothing Li et al. (); Liu et al. (); Dong et al. (), which results in performance degradation when multiple layers are applied.
Over-smoothing is characterized by node embeddings becoming inseparable, making it challenging to distinguish between them.
Recent studies Li et al. (); Liu et al. (); Dong et al. () attribute this phenomenon to the interweaving of the propagation and update steps within each GNN layer.
To address over-smoothing, a well-known solution (hereafter referred to as *decoupled GCN*) is to decouple the propagation and update steps Liu et al. (); Dong et al. ().
Let $\boldsymbol{f}_{\boldsymbol{\theta}}(\boldsymbol{x}_{v})$ be a multi layer perceptron (MLP) network that takes the
node feature $\boldsymbol{x}_{v}$ and learning parameters $\boldsymbol{\theta}$ and returns the label prediction $\hat{\boldsymbol{y}}^{(\text{MLP})}_{v}$,

$$ $\hat{\boldsymbol{y}}^{(\text{MLP})}_{v}=\boldsymbol{f}_{\boldsymbol{\theta}}( \boldsymbol{x}_{v}).$ (3) $$

A decoupled GCN can be described with the model

$$ $\boldsymbol{H}^{(L)}=\boldsymbol{\bar{A}}\boldsymbol{F}_{\boldsymbol{\theta}}( \boldsymbol{X})\,,$ (4) $$

where
$\boldsymbol{\bar{A}}=\sum_{l=1}^{L}{\beta_{l}\boldsymbol{\hat{A}}^{l}}$,
$\boldsymbol{F}_{\boldsymbol{\theta}}(\boldsymbol{X})=||(\boldsymbol{f}_{
\boldsymbol{\theta}}(\boldsymbol{x}_{v})^{\mathsf{T}}\quad\forall v\in\mathcal
{V})$,
with $||$ being the concatenation operation, and ^T denotes the transpose operation. We refer to $\boldsymbol{\bar{A}}$ as the $L$-hop *combined* neighborhood adjacency matrix. Its elements reflect the proximity of two nodes in the graph, with $\beta_{l}$ determining the contribution of each hop. Parameters $\{\beta_{l}\}_{l=1}^{L}$ can be set manually or learned during training.
Eqs. (3) and (4) correspond to the update and propagation step of the decoupled GCN, respectively.

## 4 System Model

We consider a scenario where data is structured according to a *global graph* $\mathcal{G}=(\mathcal{V},\mathcal{E},\boldsymbol{X},\boldsymbol{Y})$.
Graph $\mathcal{G}$
is distributed among $K$ clients such that each client owns a smaller *local* subgraph. We denote by
$\mathcal{G}_{i}=(\mathcal{V}_{i},\mathcal{V}_{i}^{*},\mathcal{E}_{i},\mathcal{
E}_{i}^{*},\boldsymbol{X}_{i},\boldsymbol{Y}_{i})$ the subgraph of client $i$, where $\mathcal{V}_{i}\subseteq\mathcal{V}$
is the set of $n_{i}$ nodes that reside in client $i$, referred to as *internal nodes*, for which client $i$ knows their features.
$\mathcal{V}_{i}^{*}$ is the set of nodes that do not reside in client $i$ but have at least one connection to nodes in $\mathcal{V}_{i}$.
We call these nodes *external nodes*.
Importantly, client $i$ does not have access to the features of nodes in $\mathcal{V}_{i}^{*}$.
Furthermore, $\mathcal{E}_{i}$ represents the set of edges between nodes owned by client $i$ (intra-connections),
$\mathcal{E}_{i}^{*}$ the set of edges between nodes of client $i$ and nodes of other clients (interconnections),
$\boldsymbol{X}_{i}\in\mathbb{R}^{n_{i}\times d}$
the node feature matrix, and
$\boldsymbol{Y}_{i}\in\mathbb{R}^{n_{i}\times c}$
the label matrix for the nodes within subgraph $\mathcal{G}_{i}$, and we denote by $\tilde{\mathcal{V}}_{i}$ the set of nodes that possess labels.
Similar to graph $\mathcal{G}$, $\mathcal{N}_{\mathcal{G}_{i}}(v)$, $\boldsymbol{A}^{(i)}$, and $\boldsymbol{D}^{(i)}$ denote the set of local neighbors, the local adjacency matrix, and the local diagonal matrix
for subgraph $\mathcal{G}_{i}$.

### 4.1 Node
Embeddings

Our focus is on node classification, where the goal is to classify each node based on the underlying graph data. More precisely, we assume that each client employs a GNN model that generates embeddings for each node using the node features and connections in the subgraph. Formally, for client $i$, the feature embedding matrix is obtained as

$$ $\displaystyle\boldsymbol{H}_{i}^{(L)}=\text{fGNN}_{\boldsymbol{\theta}_{ \mathsf{f}}}(\boldsymbol{X}_{i},\mathcal{E}_{i})\,,$ (5) $$

where fGNN is the GNN model to generate node feature embeddings (NFEs), $L$ is the number of propagation layers, and
$\boldsymbol{\theta}_{{\mathsf{f}}}$
is the parameter vector of fGNN.
Also $\boldsymbol{H}_{i}^{(L)}=||\big{(}(\boldsymbol{h}_{v}^{(L)})^{\mathsf{T}}\quad
\forall v\in\mathcal{V}_{i}\big{)}$, where $\boldsymbol{h}_{v}^{(L)}$ is the NFE of node $v$.

### 4.2 Federated Learning

The FL problem can be formalized as learning the model parameters that minimize the aggregated loss across clients,

$$ $\boldsymbol{\theta}^{*}=\operatorname*{arg\,min}_{\boldsymbol{\theta}}\; \mathcal{L}(\boldsymbol{\theta})\,,$ (6) $$

with

$$ $\displaystyle\mathcal{L}(\boldsymbol{\theta})=\frac{1}{|\tilde{\mathcal{V}}|} \sum_{i=1}^{K}{\mathcal{L}_{i}(\boldsymbol{\theta})},\quad\text{and}\quad \mathcal{L}_{i}(\boldsymbol{\theta})=\sum_{v\in\tilde{\mathcal{V}}_{i}}{ \mathrm{CE}(\boldsymbol{y}_{v},\hat{\boldsymbol{y}}_{v})}\,,$ (7) $$

where $\mathrm{CE}$ is the cross-entropy loss function between the true label $\boldsymbol{y}_{v}$ and the predicted label $\hat{\boldsymbol{y}}_{v}$.

The model $\boldsymbol{\theta}$ is trained iteratively over multiple epochs.
At each epoch, the clients compute the local gradients $\nabla_{\boldsymbol{\theta}}\mathcal{L}_{i}(\boldsymbol{\theta})$ and send them to the central server. The server updates the model through gradient descent,

$$ $\boldsymbol{\theta}\leftarrow\boldsymbol{\theta}-\lambda\nabla_{\boldsymbol{ \theta}}\mathcal{L}(\boldsymbol{\theta}),\quad\nabla_{\boldsymbol{\theta}} \mathcal{L}(\boldsymbol{\theta})=\frac{1}{|\tilde{\mathcal{V}}|}\sum_{i=1}^{K} {\nabla_{\boldsymbol{\theta}}\mathcal{L}_{i}(\boldsymbol{\theta})}\,,$ (8) $$

where $\lambda$ is the learning rate.

## 5 FedStruct : Structure-Exploiting Subgraph Federated Learning

In this section, we introduce FedStruct, a novel subgraph FL 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 underlying structure to improve node label prediction while ensuring that neither the server nor the clients have access to the node features. More precisely, at each client $i\in[K]$, node prediction is performed based on both the NFEs $\boldsymbol{h}_{v}^{(L)}$ (which are computed locally at each client, see Sec. 4.1) and
*node structure embeddings* (NSEs), $\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}$, which encode structural information of the nodes.
To this aim, we pass the NFEs and NSEs through a fully connected layer with parameters $\boldsymbol{\Theta}_{\mathsf{c}}$,

$$ $\displaystyle\hat{\boldsymbol{y}}_{v}=\mathrm{softmax}(\boldsymbol{\Theta}_{ \mathsf{c}}^{\mathsf{T}}\big{(}\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}|| \boldsymbol{h}_{v}^{(L)}))=\mathrm{softmax}\big{(}(\boldsymbol{\Theta}_{ \mathsf{c}}^{(\mathsf{s})})^{\mathsf{T}}\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}+ (\boldsymbol{\Theta}_{\mathsf{c}}^{(\mathsf{f})})^{\mathsf{T}}\boldsymbol{h}_{ v}^{(L)})\big{)}\quad\forall v\in\mathcal{V}_{i}\,.$ (9) $$

We denote the vectorized version of $\boldsymbol{\Theta}_{\mathsf{c}}$ by $\boldsymbol{\theta}_{\mathsf{c}}$. From (9), we have that $\boldsymbol{\theta}_{\mathsf{c}}=\boldsymbol{\theta}_{\mathsf{c}}^{(\mathsf{s}
)}\,||\boldsymbol{\theta}_{\mathsf{c}}^{(\mathsf{f})}$.

Since NSEs capture structural information of the global graph, their use is anticipated to enhance node classification compared to the case of a classifier solely relying on NFEs.

Figure: Figure 2: General design of the FedStruct framework. Global Graph: underlying graph consisting of interconnected subgraphs. Local graphs: clients’ subgraphs augmented with external nodes (without features or labels). Structure encoding: Generates node structure features for each node and shares them with other clients. Augmented local graphs: Generate node feature embeddings and node structure embeddings. Federated learning: Federated learning step exploiting node feature embeddings and node structure embeddings.
Refer to caption: extracted/5664685/Figures/fedstruct-b.png

In this work, we consider specifically the challenging scenario where the server lacks knowledge of the global graph connections—a scenario relevant in applications such as anti-money laundering, where the transaction networks within each bank are private. For the learning framework to capitalize on inter-node dependencies among clients, structure embeddings must then be locally generated at each client.
This necessitates clients to selectively share specific local graph structural information with other clients.
To uphold privacy, this sharing of information is done cautiously in FedStruct.

Next, we explain how NSEs are generated while minimizing the information exchanged between clients. We also highlight that FedStruct does not share (nor generate) node features or embeddings among clients. The FedStruct framework is illustrated in Fig. 2 and described in Alg. 1 in App. B.

### 5.1 Node structure features, node structure embeddings, and node prediction

Node structure features. To generate NSEs, our proposed method relies on *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 as distance to other nodes in the graph.
For each node $v\in\mathcal{V}$, the corresponding NSF, $\boldsymbol{s}_{v}\in\mathbb{R}^{d_{\mathsf{s}}}$, is a function of the set of edges $\mathcal{E}$, $\boldsymbol{s}_{v}=\boldsymbol{Q}_{\mathsf{NSF}}(v,\mathcal{E})$.
We define the matrix containing all NSFs as $\boldsymbol{S}=||(\boldsymbol{s}_{v}^{\mathsf{T}},\quad\forall v\in\mathcal{V})$. Function $\boldsymbol{Q}_{\mathsf{NSF}}$ can be defined through various node embedding algorithms, e.g., one-hot degree vector Xu et al. (); Cui et al. (), , graphlet degree vector (GDV) Pržulj (), Node2Vec Grover and Leskovec (), or as in FedStar Tan et al. () (from now, we will simply refer to this NSF technique as FedStar).
We describe these different node embeddings in App. A.
In Sec. 5.3, we introduce a method to generate task-dependent NSEs, which, in contrast to methods such as GDV and Node2Vec, does not require knowledge of the global graph.

Node structure embeddings.
To use NSFs for label prediction, we next outline how to combine NSFs into NSEs amenable to classification.
To this aim, FedStruct employs a GNN, here referred to as sGNN, that generates NSEs by incorporating information from the NSFs and the global graph’s connections.
Let $L_{\mathsf{s}}$ be the number of propagation layers of sGNN and $\boldsymbol{S}^{(L_{\mathsf{s}})}=||\big{(}(\boldsymbol{s}_{v}^{(L_{\mathsf{s}
})}){{}^{\mathsf{T}}}\quad\forall v\in\mathcal{V}\big{)}$ the matrix of NSEs at layer $L_{\mathsf{s}}$, with $\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}$ being the NSE of node $v$.
Formally, $\boldsymbol{S}^{(L_{\mathsf{s}})}$ is obtained as

$$ $\displaystyle\boldsymbol{S}^{(L_{\mathsf{s}})}=\text{sGNN}_{\boldsymbol{\theta }_{\mathsf{s}}}(\boldsymbol{S},\mathcal{E})\,,$ (10) $$

where $\boldsymbol{\theta}_{\mathsf{s}}$ are the parameters of sGNN.

As the server lacks knowledge of the global graph in (10), NSEs need to be generated locally.
Unfortunately, standard GNNs are ill-suited to locally generate NSEs as the intertwining of propagation and update steps within each GNN layer poses challenges.
Specifically, for clients to compute new embeddings for a given layer of the GNN, they require the embeddings of previous layers for neighboring nodes residing in other clients.
Such information access would allow the clients to infer the global graph structure.
To address this concern, FedStruct employs a decoupled GCN.

For client $i\in[K]$ and node $v\in\mathcal{V}_{i}$, let $\boldsymbol{f}_{\boldsymbol{\theta}_{\mathsf{f}}}(\boldsymbol{x}_{v})$ and $\boldsymbol{g}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{s}_{v})$ be the MLP networks used in the update step for the node features and node structure features, respectively.
To employ a decoupled GCN in FedStruct, we use (4) to define the sGNN and fGNN models as

$$ $\displaystyle\boldsymbol{H}_{i}^{(L)}=\text{fGNN}_{\boldsymbol{\theta}_{ \mathsf{f}}}(\boldsymbol{X}_{i},\mathcal{E}_{i})=\boldsymbol{\bar{A}}^{(i)}\; \boldsymbol{F}_{\boldsymbol{\theta}_{\mathsf{f}}}(\boldsymbol{X}_{i})\quad \text{and}\quad\boldsymbol{S}^{(L_{\mathsf{s}})}=\text{sGNN}_{\boldsymbol{ \theta}_{\mathsf{s}}}(\boldsymbol{S},\mathcal{E})=\boldsymbol{\bar{A}}\; \boldsymbol{G}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{S})\,,$ (11) $$

where $\boldsymbol{F}_{\boldsymbol{\theta}_{\mathsf{f}}}(\boldsymbol{X}_{i})=||(
\boldsymbol{f}_{\boldsymbol{\theta}_{\mathsf{f}}}(\boldsymbol{x}_{u})^{\mathsf
{T}}\;\forall u\in\mathcal{V}_{i})$, $\boldsymbol{G}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{S})=||(
\boldsymbol{g}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{s}_{u})^{\mathsf
{T}}\;\forall u\in\mathcal{V})$, and $\boldsymbol{\bar{A}}$ and $\boldsymbol{\bar{A}}^{(i)}$ are the $L$-hop combined adjacency matrices for graph $\mathcal{G}$ and $\mathcal{G}_{i}$, respectively.
Note that clients can compute
$\boldsymbol{H}_{i}^{(L)}$ locally. However,
$\boldsymbol{S}^{(L_{\mathsf{s}})}$ requires the $L$-hop combined adjacency matrix which is not locally available.
We address this issue in Sec. 5.2.

Node prediction. Upon the creation of the NSEs, each client computes the label predictions through (9). For a node $v\in\tilde{\mathcal{V}}_{i}$, expanding (11) leads to

$$ $\displaystyle\boldsymbol{h}_{v}^{(L)}=\sum_{u\in\mathcal{V}_{i}}{\bar{a}_{vu}^ {(i)}\boldsymbol{f}_{\boldsymbol{\theta}_{\mathsf{f}}}(\boldsymbol{x}_{u})} \quad\quad\quad\text{and}\quad\quad\quad\boldsymbol{s}_{v}^{(L_{s})}=\sum_{u \in\mathcal{V}}{\bar{a}_{vu}\boldsymbol{g}_{\boldsymbol{\theta}_{\mathsf{s}}}( \boldsymbol{s}_{u})}\,,$ (12) $$

where $\boldsymbol{h}_{v}^{(L)}$ and $\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}$ represent the NFE and NSE of node $v$, respectively.
Using (12) in (9) leads to

$$ $\displaystyle\hat{\boldsymbol{y}}_{v}$ $\displaystyle=\mathrm{softmax}\Big{(}\sum_{u\in\mathcal{V}}{\bar{a}_{vu} \boldsymbol{g}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{s}_{u})}+\sum_{u \in\mathcal{V}_{i}}{\bar{a}_{vu}^{(i)}\boldsymbol{f}_{\boldsymbol{\theta}_{ \mathsf{f}}}(\boldsymbol{x}_{u})}\Big{)}\,,$ (13) $$

where (13) comes from integrating $\boldsymbol{\Theta}_{\mathsf{c}}^{(\mathsf{f})}$ and $\boldsymbol{\Theta}_{\mathsf{c}}^{(\mathsf{s})}$ into $\boldsymbol{f}_{\boldsymbol{\theta}_{\mathsf{f}}}(\boldsymbol{x}_{u})$ and $\boldsymbol{g}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{s}_{u})$, respectively.

Optimization.
We optimize the learning parameters of FedStruct, $\boldsymbol{\theta}=(\boldsymbol{\theta}_{\mathsf{f}}||\boldsymbol{\theta}_{
\mathsf{s}}||\boldsymbol{\theta}_{\mathsf{c}})$, by solving (6)–(7) with $\hat{\boldsymbol{y}}_{v}$ in (13) using stochastic gradient descent. The local gradients are given in Prop. 2.

### 5.2 Structural information sharing

In the following, we show that for node classification tasks, utilizing the categorical cross-entropy loss function, FedStruct can be trained only with partial knowledge of the global graph structure.(^1^11If the server has access to the global adjacency matrix, FedStruct can be readily used as shown in App. J.)

For a given client $i$, training FedStruct involves computing $\nabla_{\boldsymbol{\theta}}\mathcal{L}_{i}(\boldsymbol{\theta})$
and predicting node labels $\{\hat{\boldsymbol{y}}_{v},\forall v\in\tilde{\mathcal{V}}_{i}\}$.
We denote by $\boldsymbol{\bar{A}}^{[i]}=||(\boldsymbol{\bar{a}}_{v}^{\mathsf{T}},\quad
\forall v\in\tilde{\mathcal{V}}_{i})$ client $i$’s local partition of $\boldsymbol{\bar{A}}$, where $\boldsymbol{\bar{a}}_{v}=||(\bar{a}_{vu},\quad\forall u\in\mathcal{V})$.
Note that $\boldsymbol{\bar{A}}^{[i]}\in\mathbb{R}^{n_{i}\times n}$ contains the rows of matrix $\boldsymbol{\bar{A}}$ corresponding to nodes of graph $\mathcal{G}_{i}$.
In contrast, $\boldsymbol{\bar{A}}^{(i)}\in\mathbb{R}^{n_{i}\times n_{i}}$ is the $L$-hop adjacency matrix of graph $\mathcal{G}_{i}$ and it is solely based on the nodes and internal connections of subgraph $\mathcal{G}_{i}$.
By observing that (13) depends only on $\boldsymbol{\bar{A}}^{[i]}$ and $\boldsymbol{S}$, we have the following proposition.

###### Proposition 1.

To obtain $\{\hat{\boldsymbol{y}}_{v},\forall v\in\tilde{\mathcal{V}}_{i}\}$ in (13), client $i$ only needs external inputs $\boldsymbol{\bar{A}}^{[i]}$ and $\boldsymbol{S}$.

Furthermore, the local gradient $\nabla_{\boldsymbol{\theta}}\mathcal{L}_{i}(\boldsymbol{\theta})$ is given by the following proposition.

###### Proposition 2.

Let $\mathcal{L}_{i}(\boldsymbol{\theta})$ in (7) use the cross-entropy loss
and let $\hat{\boldsymbol{y}}_{v}$ be as in (13). The local gradient

$$ $\displaystyle\nabla_{\boldsymbol{\theta}}\mathcal{L}_{i}(\boldsymbol{\theta})= ||\left(\frac{\partial{\mathcal{L}_{i}(\boldsymbol{\theta})}}{\partial{\theta_ {j}}}\quad\forall j\in[|\boldsymbol{\theta}|]\right)$ $$

is given by

$$ $\displaystyle\frac{\partial{\mathcal{L}_{i}(\boldsymbol{\theta})}}{\partial{ \theta_{\mathsf{s},j}}}=\sum_{v\in\tilde{\mathcal{V}}_{i},u\in\mathcal{V}}{ \bar{a}_{vu}\frac{\partial{\boldsymbol{g}_{\boldsymbol{\theta}_{\mathsf{s}}}( \boldsymbol{s}_{u})}}{\partial{\theta_{\mathsf{s},j}}}(\hat{\boldsymbol{y}}_{v }-\boldsymbol{y}_{v})},\quad\quad\frac{\partial{\mathcal{L}_{i}(\boldsymbol{ \theta})}}{\partial{\theta_{\mathsf{f},j}}}=\sum_{v\in\tilde{\mathcal{V}}_{i}, u\in\mathcal{V}_{i}}{\bar{a}^{(i)}_{vu}\frac{\partial{\boldsymbol{f}_{ \boldsymbol{\theta}_{\mathsf{f}}}(\boldsymbol{x}_{u})}}{\partial{\theta_{ \mathsf{f},j}}}(\hat{\boldsymbol{y}}_{v}-\boldsymbol{y}_{v})}.$ (14) $$

###### Proof.

See App. C.
∎

By combining Prop. 1 and Prop. 2, we have have the following proposition.

###### Proposition 3.

For client $i$, the training of FedStruct, i.e., computing $\{\hat{\boldsymbol{y}}_{v},\forall v\in\tilde{\mathcal{V}}_{i}\}$ and $\nabla_{\boldsymbol{\theta}}\mathcal{L}_{i}(\boldsymbol{\theta})$, requires only
the local partition
$\boldsymbol{\bar{A}}^{[i]}$ and $\boldsymbol{S}$.

Prop. 3 states that clients do not require knowledge of the global adjacency matrix to predict a node’s label or to compute the gradient.
Instead, only the local partition of the global $L$-hop combined adjacency matrix, $\boldsymbol{\bar{A}}^{[i]}$, is necessary to operate FedStruct.
Clients have to collaboratively calculate $\boldsymbol{\bar{A}}^{[i]}$. In App. E, we provide an algorithm to obtain $\boldsymbol{\bar{A}}^{[i]}$ before the training begins without gaining any additional information about the global graph.
Moreover, due to graph isomorphism,
$\boldsymbol{\bar{A}}^{[i]}$
cannot be used to uniquely determine the adjacency matrix of other clients.

###### Proposition 1.

###### Proposition 2.

###### Proof.

###### Proposition 3.

### 5.3 Hop2Vec : Task-Dependent Node Structure Embedding

Well-known NSF methods like Node2Vec and GDV require knowledge of the $L$-hop neighborhood of a node, are task agnostic, and hinge on a homophily assumption (see App. A).
To circumvent these shortcomings, we propose Hop2Vec, a novel method to generate task-dependent NSFs that captures structural information beyond direct neighbors without requiring knowledge of the $L$-hop neighborhood and is applicable to heterophilic graphs.

The idea behind Hop2Vec is to view NSFs as learnable features.
To this end, NSFs are randomly initialized and updated during the training of FedStruct.
More precisely, for fixed $\boldsymbol{\theta}$, the NSFs are optimized by solving

$$ $\boldsymbol{S}^{*}=\operatorname*{arg\,min}_{\boldsymbol{S}}{\mathcal{L}( \boldsymbol{\theta},\boldsymbol{S})}\,.$ (15) $$

In (15) we made explicit that the loss function $\mathcal{L}(\boldsymbol{\theta})$ (introduced in (6) and (7))
is contingent on $\boldsymbol{S}$ through the estimated labels $\hat{\boldsymbol{y}}_{v}$ (see (13)).
The optimization is carried out through gradient descent,

$$ $\boldsymbol{S}\leftarrow\boldsymbol{S}-\lambda_{\mathsf{s}}\nabla_{\boldsymbol {S}}\mathcal{L}(\boldsymbol{\theta},\boldsymbol{S})\,,$ (16) $$

where $\lambda_{\mathsf{s}}$ denotes the learning rate.

The NSFs obtained through (15) 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 $\boldsymbol{\bar{a}}_{uv}$ through (13)—since coefficient $\boldsymbol{\bar{a}}_{uv}$ encompasses the $L$-hop neighbors of node $v$, and $L$ can be large, Hop2Vec is able to capture the global graph’s structure information. Furthermore, the parameters $\beta_{l}$ of the trainable coefficients $\boldsymbol{\bar{a}}_{uv}$ (see Sec. 3) can be adjusted (or learned) to account for heterophilic graphs (we discuss heterophily in App. I.2).

Using Hop2Vec, we note that the learning of $\boldsymbol{g}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{s}_{u})$ (see Sec. 5.1, e.g., (11)) is equivalent to the learning of $\boldsymbol{s}_{u}$, i.e., the purpose of passing the NSFs through the sGNN is to generate task-dependent NSEs.
Since the NSFs $\{\boldsymbol{s}_{u}\}_{u\in\mathcal{V}}$ are subject to optimization, we can integrate the learning parameters of $\boldsymbol{g}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{s}_{u})$ into $\boldsymbol{s}_{u}$ and rewrite (13) as

$$ $\hat{\boldsymbol{y}}_{v}=\mathrm{softmax}\Big{(}\sum_{u\in\mathcal{V}}{\bar{a} _{vu}\boldsymbol{s}_{u}}+\sum_{u\in\mathcal{V}_{i}}{\bar{a}_{vu}^{(i)} \boldsymbol{f}_{\boldsymbol{\theta}_{\mathsf{f}}}(\boldsymbol{x}_{u})}\Big{)}\,.$ (17) $$

To operate FedStruct, as in Sec. 5.2, client $i$ only need access to $\boldsymbol{\bar{A}}^{[i]}$ as shown in 4.

###### Proposition 4.

Let $\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})$ in (7) use the cross-entropy loss and let $\boldsymbol{S}=||(\boldsymbol{s}_{q}^{\mathsf{T}},\quad\forall q\in\mathcal{V})$ represent the matrix containing NSFs generated by Hop2Vec.
Additionally, let $\hat{\boldsymbol{y}}_{v}$ be as in (17).
The gradient $\nabla_{\boldsymbol{S}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})$
is given by

$$ $\displaystyle\nabla_{\boldsymbol{S}}\mathcal{L}_{i}(\boldsymbol{\theta}, \boldsymbol{S})=\sum_{v\in\tilde{\mathcal{V}}_{i}}{\boldsymbol{\bar{a}}_{v}( \hat{\boldsymbol{y}}_{v}-\boldsymbol{y}_{v})^{\mathsf{T}}}\,.$ (18) $$

###### Proof.

See App. D.
∎

The FedStruct framework with Hop2Vec is described in Alg. 2 in App.  B.

###### Proposition 4.

###### Proof.

### 5.4 Communication Complexity

In Table 1, we present the communication complexity of FedStruct alongside that of FedSage+ (for more details see App. H).
We divide the communication complexity into two parts: an offline component, accounting for events taking place before the training is 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, and nodes in the graph, respectively.
Parameter $d$ is the node feature size (all feature dimensions are assumed to be equal to $d$), and $|\boldsymbol{\theta}|$ is the number of model parameters (all model parameters are assumed to be of the same order).

As seen in Table 1, the online complexity of FedStruct is significantly lower than that of FedSage+, which is on the order of $n$.
The online complexity of FedStruct with Hop2Vec, however, is also on the order of $n$.
The offline complexity of FedStruct is on the order of $n^{2}$.
While the offline complexity is less critical than the online complexity, scaling as $n^{2}$ may be impractical for large networks.
To this end, we present a pruning method in App. H.1 to reduce the complexity of FedStruct.
The key idea is to prune the shared $n_{i}\times n$ matrix $\boldsymbol{\bar{A}}^{[i]}$ into size $n_{i}\times p$ where $p\ll n$.
Hence, the $L_{\mathsf{s}}\cdot n^{2}$ term is reduced to $L_{\mathsf{s}}\cdot p\cdot n$.
Overall the complexity of FedStruct with pruning is the same of FedSage+, i.e., on the order of $n$ as can be seen in Table 1.

**Table 1: Communication Complexity of FedStruct.**
| Data | before training | training |
| --- | --- | --- |
| FedStruct | $\mathcal{O}(K\cdot n\cdot d+L_{\mathsf{s}}\cdot n^{2})$ | $\mathcal{O}(E\cdot K\cdot|\boldsymbol{\theta}|)$ |
| FedStruct + Hop2Vec | $\mathcal{O}(K\cdot n\cdot d+L_{\mathsf{s}}\cdot n^{2})$ | $\mathcal{O}(E\cdot K\cdot|\boldsymbol{\theta}|+E\cdot K\cdot n\cdot d)$ |
| FedStruct pruning | $\mathcal{O}(K\cdot n\cdot d+L_{\mathsf{s}}\cdot p\cdot n)$ | $\mathcal{O}(E\cdot K\cdot|\boldsymbol{\theta}|)$ |
| FedSage+ | 0 | $\mathcal{O}(E\cdot K^{2}\cdot|\boldsymbol{\theta}|+E\cdot K\cdot n\cdot d)$ |

## 6 Evaluation

To demonstrate the performance and versatility of FedStruct, we conduct experiments on six datasets pertaining to node classification under scenarios with varying i) amounts of labeled training nodes, ii) number of clients, and iii) data partitioning methods.
The interconnections between clients heavily depend on the latter.
The datasets considered are: Cora Sen et al. (), Citeseer Sen et al. (), Pubmed Namata et al. (), Chameleon Pei et al. (), Amazon Photo Shchur et al. (), and Amazon Ratings Platonov et al. ().
Statistics of the different datasets are given in App. F along with their edge homophily ratio, measuring the proportion of edges connecting nodes of similar labels, ranging between 0 (heterophilic) to 1 (homophilic) Zhu et al. ().

Experimental setting.
We focus on a 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, we consider a random partitioning, which assigns nodes to subgraphs uniformly at random.
This partitioning constitutes a very challenging setting
as the number of interconnections is high and, hence, the learning scheme must exploit such connections, and is relevant in, e.g., transaction networks, where accounts do not necessarily have a preference to interact with nodes in the same subgraph.
In App. G, we also provide details and results for two other partitionings using the Louvain algorithm, as in Zhang et al. (), and the K-means algorithm Lei et al. ().

To provide upper and lower benchmarks, all experiments are also conducted for a centralized setting utilizing the global graph and a localized setting using only the local subgraphs.
In App. G we also give results for an MLP approach to highlight the importance of utilizing the spatial structure within the data.
For the GNN, we rely on GraphSage Hamilton et al. () with two or three layers, depending on the dataset (DCGN performs similarly as shown in Table 6 in App. F).
We further compare FedStruct to vanilla FL (FedSGD GNN) and FedPub, which do not exploit interconnections, and FedSage+ Zhang et al. ().
Note that FedSage+ does not know to what clients the missing neighbors belong to.
Therefore, we provide also an *idealized* version of FedSage+ (and FedNI), denoted fedsage+ ideal, where this information is known and the in-painting of missing one-hop neighbors is replaced by their true features.
This method provides an upper bound on the performance of FedSage+ and FedNI but is not feasible in practice.
For the baseline methods, we use the default hyperparameters but optimize the learning rates.
For
FedStruct, we consider three
methods to create NSFs: one-hot degree vector (Deg), FedStar (Fed$\star$), and the task-dependent approach proposed in Sec. 5.1 Hop2Vec (H2V), see App. A for details.
For H2V, we also provide the performance of the pruned version (FedStruct-p), see Sec. 5.4, with $p=30$.

**Table 2: Node classification accuracy with random partitioning. Nodes are split into train-val-test as 10%-10%-80%. For each result, the mean and standard deviation are shown for $10$ independent runs.**
|  | Cora | Citeseer | Pubmed |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Central GNN | 82.06$\pm$ 1.09 | 69.17$\pm$ 0.90 | 87.71$\pm$ 0.34 |  |  |  |  |  |  |
|  | 5 clients | 10 clients | 20 clients | 5 clients | 10 clients | 20 clients | 5 clients | 10 clients | 20 clients |
| FedSGD GNN | 68.47$\pm$ 1.12 | 65.06$\pm$ 1.92 | 64.59$\pm$ 1.56 | 64.92$\pm$ 1.84 | 63.47$\pm$ 1.29 | 63.78$\pm$ 1.46 | 86.14$\pm$ 0.38 | 85.91$\pm$ 0.42 | 85.31$\pm$ 0.56 |
| FedPub | 65.94 $\pm$ 1.14 | 55.58$\pm$ 2.65 | 43.47 $\pm$ 2.92 | 62.78 $\pm$ 1.28 | 59.80 $\pm$ 1.74 | 57.73 $\pm$ 2.26 | 52.06 $\pm$ 8.83 | 46.25$\pm$ 8.50 | 43.62 $\pm$ 6.78 |
| FedSage+ | 68.42$\pm$ 1.73 | 66.32$\pm$ 1.81 | 64.19$\pm$ 1.54 | 64.65$\pm$ 1.28 | 63.37$\pm$ 1.45 | 62.69$\pm$ 1.35 | 85.89$\pm$ 0.39 | 85.37$\pm$ 0.55 | 85.14$\pm$ 0.28 |
| fedsage+ ideal | 81.74$\pm$ 1.29 | 80.85$\pm$ 1.55 | 79.96$\pm$ 1.27 | 69.52$\pm$ 1.57 | 68.91$\pm$ 1.30 | 69.26$\pm$ 1.49 | 85.40$\pm$ 0.77 | 85.66$\pm$ 0.37 | 85.10$\pm$ 0.80 |
| FedStruct (Deg) | 71.87$\pm$ 2.52 | 68.64$\pm$ 1.51 | 65.06$\pm$ 2.12 | 66.33$\pm$ 1.68 | 63.81$\pm$ 1.31 | 61.50$\pm$ 1.52 | 84.92$\pm$ 0.53 | 85.09$\pm$ 0.48 | 85.40$\pm$ 0.52 |
| FedStruct (Fed$\star$) | 72.40 $\pm$ 1.42 | 68.87 $\pm$ 1.25 | 65.46 $\pm$ 1.82 | 65.96 $\pm$ 0.81 | 64.40 $\pm$ 1.51 | 62.18 $\pm$0.99 | 84.76 $\pm$ 0.23 | 84.84$\pm$ 0.36 | 84.54 $\pm$ 0.27 |
| FedStruct (H2V) | 79.53$\pm$ 1.52 | 80.28$\pm$ 1.44 | 79.39$\pm$ 0.90 | 67.33$\pm$ 1.43 | 66.29$\pm$ 0.87 | 65.24$\pm$ 1.49 | 86.07$\pm$ 0.35 | 86.65$\pm$ 0.53 | 86.24$\pm$ 0.56 |
| FedStruct-p (H2V) | 78.75 $\pm$ 1.47 | 78.75 $\pm$ 1.09 | 78.15 $\pm$ 0.92 | 66.85 $\pm$ 1.23 | 65.65 $\pm$ 1.58 | 65.06 $\pm$ 1.17 | 84.68 $\pm$ 0.45 | 85.01 $\pm$ 0.34 | 85.07$\pm$ 0.42 |
| Local GNN | 49.60$\pm$ 2.13 | 39.23$\pm$ 1.21 | 32.25$\pm$ 1.68 | 50.77$\pm$ 1.78 | 38.99$\pm$ 1.60 | 32.40$\pm$ 1.57 | 82.58$\pm$ 0.28 | 79.10$\pm$ 0.54 | 73.31$\pm$ 0.41 |

Overall performance.
In Table 2, 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\%$ and $9.05\%$, respectively.
For these datasets, FedSGD GNN closes the gap to $16.94\%$ and $5.24\%$, respectively.
FedSage+ yields similar performance as FedSGD GNN for all datasets.
Incorporating the true node features of the mended nodes (FedSage+ Ideal) brings performance close to the centralized approach.
Note, however, that access to the missing neighbors’ node features is unrealistic and completely violates privacy.
FedPub exhibits poor performance, likely due to the low number of labeled nodes and random partitioning.

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 Hop2Vec 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$\star$, and H2V.

Notably, FedStruct with Hop2Vec achieves performance close to a centralized approach. For example, on Cora and Amazon Photo, the gap between central GNN and Hop2Vec is $2.56\%$ and $0.3\%$, respectively.
Similar gaps are observed across all datasets.
Furthermore, compared to, e.g., FedSGD GNN, FedStruct remains robust to an increasing number of clients and, as shown in App. G, across different partitioning methods, highlighting its ability to exploit the interconnections between clients.
Finally, FedStruct-p exhibits only a slight reduction in performance compared to FedStruct but with a significant reduction in communication complexity (see Sec. 5.4).
Additional results including federated averaging and central DGCN are provided in App. G for various partitionings and varying number of labeled training nodes and degrees of heterophily.

## 7 Concluding Remarks

We presented FedStruct, a framework for subgraph FL that decouples node and structure features, explicitly exploiting structural dependencies. The advantages of FedStruct are outlined below.

Privacy.
Unlike existing subgraph FL frameworks, which require sharing original or generated node features and/or embeddings among clients, FedStruct eliminates this need, sharing less sensitive information. In App. I.1, we discuss privacy considerations of FedStruct.

Robustenss. FedStruct shows excellent performance, close to that of a centralized approach, even in heavily semi-supervised learning scenarios with a low fraction of labeled nodes
(see App. G) and significantly outperforms FedSage+ and FedPub in these challenging scenarios.
Furthermore, as seen in App. G, unlike other approaches, FedStruct exhibits robustness accross different partitionings, varying number of clients, and heterophily.

Task-dependent NSF. The proposed Hop2Vec does not require knowledge of the global graph, contrary to well-known methods such as Node2Vec and GDV.

## 8 Acknowledgments and Disclosure of Funding

This work was partially supported by the Swedish Research Council (VR) under grant 2020-03687 and by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation.

## Appendix 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 a vector with a 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 a 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 [].
Although GDV is more expressive than Deg, this approach suffers from high complexity as 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 Leskovec [].
It uses controlled random walks to explore the graph, generating node sequences similar to sentences in a language.
For each node in the graph, multiple random walks are performed creating a large corpus of node sequences.
These sequences are then used to train a skip-gram model to predict the context of a given node, i.e., the neighboring nodes in the random walks.
Once trained, the NSFs are obtained by querying the skip-gram model with a node and extracting its latent representation.

Fed$\star$ is proposed in Tan et al. [] 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 an NSF by concatenating NSFs created from Deg and from a random walk.
We adapt this methodology to our setting by extracting the diagonal element corresponding to a given node from the powers of $\boldsymbol{\hat{A}}$, during the process of computing $\boldsymbol{\bar{A}}$, in place of [Tan et al., , Eq. 6].

As shown in Appendix J, Node2Vec yields superior performance to Deg, GDV, and Fed$\star$ due to its ability to capture global properties of the graph.
Note, however, that Node2Vec 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 at hand.

The proposed Hop2Vec leverages the advantages of Node2Vec while also alleviating its shortcomings within our setting.
In Hop2Vec, instead of learning the NSFs before FedStruct initiates, we start from a random NSF and train a generator within FedStruct.
As a result, we obtain NSFs that are tailored toward the task, e.g., to minimize miss-classification.
Notably, in sharp contrast to Node2Vec, Hop2Vec does not require knowledge of the complete adjacency matrix. Moreover, compared to Node2Vec, Hop2Vec is faster and does not need any hyperparameter tuning.
Finally, when paired with decoupled GCN (DGCN), it is able to capture the global properties of the graph.
A summary of the different NSF-generating methods is given in Table 3.

**Table 3: Comparing NSF generator algorithms**
| Data | Deg | GDV | Node2Vec | Fed$\star$ | Hop2Vec |
| --- | --- | --- | --- | --- | --- |
| task dependent | ✗ | ✗ | ✗ | ✗ | ✓ |
| global properties | ✗ | ✗ | ✓ | ✓ | ✓ |
| fast | ✓ | ✗ | ✗ | ✗ | ✓ |
| no parameter tuning | ✓ | ✓ | ✗ | ✗ | ✓ |
| locally computable | ✓ | ✗ | ✗ | ✓ | ✓ |

## Appendix B Training Process of FedStruct

The training process of
FedStruct with generic NSEs is described in Algorithm 1. The training process of FedStruct using Hop2Vec is described in Algorithm 2.

Figure: Algorithm 1 FedStruct

Figure: Algorithm 2 FedStruct using Hop2Vec

## Appendix C Proof of 2

To prove  2, we need the following lemma.

###### Lemma 1.

Let $\hat{\boldsymbol{y}}=\mathrm{softmax}(\boldsymbol{z})$
and $\mathcal{L}=\mathrm{CE}(\boldsymbol{y},\hat{\boldsymbol{y}})$, where $\mathrm{CE}$ is the cross-entropy loss function and $\boldsymbol{y}$ is the label corresponding to the input vector $\boldsymbol{z}$, with $\sum_{i=1}^{c}{y_{i}}=1$ and $c$ being the number of classes.
The gradient of $\mathcal{L}$ with respect to $\boldsymbol{z}$ is equal to

$$ $\nabla_{\boldsymbol{z}}\mathcal{L}=\hat{\boldsymbol{y}}-\boldsymbol{y}\,.$ (19) $$

###### Proof.

Using the definition of cross-entropy

$$ $\displaystyle\mathrm{CE}(\boldsymbol{y},\hat{\boldsymbol{y}})=-\sum_{i=1}^{c}{ y_{i}\mathrm{log}(\hat{y}_{i})}\,,$ (20) $$

and the definition of softmax,

$$ $\displaystyle\mathrm{softmax}(\boldsymbol{z})=||\left(\frac{e^{z_{i}}}{\sum_{j =1}^{c}{e^{z_{j}}}}\quad\forall i\in[c]\right)\,,$ (21) $$

we can rewrite $\mathcal{L}$ as

$$ $\displaystyle\mathcal{L}$ $\displaystyle=\sum_{i=1}^{c}{y_{i}\big{(}\mathrm{LSE}(\boldsymbol{z})-z_{i} \big{)}}$ $\displaystyle=\mathrm{LSE}(\boldsymbol{z})\sum_{i=1}^{c}{y_{i}}-\sum_{i=1}^{c} {y_{i}z_{i}}$ $\displaystyle=\mathrm{LSE}(\boldsymbol{z})-\boldsymbol{z}^{\mathsf{T}} \boldsymbol{y}\,,$ (22) $$

where $\mathrm{LSE}(\boldsymbol{z})=\mathrm{log}(\sum_{j=1}^{c}{e^{z_{j}}})$ is the log-sum-exp function.
The partial derivative of $\mathrm{LSE}(\boldsymbol{z})$ with respect to $\boldsymbol{z}$ is the $\mathrm{softmax}$ function

$$ $\displaystyle\nabla_{\boldsymbol{z}}\mathrm{LSE}(\boldsymbol{z})$ $\displaystyle=||(\frac{\partial{\mathrm{LSE}(\boldsymbol{z})}}{\partial{z_{k}} }\quad\forall k\in[c])$ $\displaystyle=||(\frac{e^{z_{k}}}{\sum_{j=1}^{c}{e^{z_{j}}}}\quad\forall k\in[ c])$ $\displaystyle=\mathrm{softmax}(\boldsymbol{z})\,.$ (23) $$

Therefore, using  (C) and taking the derivative of  (C) with respect to $\boldsymbol{z}$ leads to

$$ $\displaystyle\nabla_{\boldsymbol{z}}\mathcal{L}$ $\displaystyle=\nabla_{\boldsymbol{z}}\mathrm{LSE}(\boldsymbol{z})-\nabla_{ \boldsymbol{z}}(\boldsymbol{z}^{\mathsf{T}}\boldsymbol{y})=\hat{\boldsymbol{y} }-\boldsymbol{y}\,.$ $$

∎

Using  1, we can now prove  2.
By the chain rule and 1, we have

$$ $\displaystyle\frac{\partial{\mathcal{L}_{i}(\boldsymbol{\theta})}}{\partial{ \theta_{j}}}$ $\displaystyle=\sum_{v\in\tilde{\mathcal{V}}_{i}}{\frac{\partial{\boldsymbol{z} _{v}}}{\partial{\theta_{j}}}\nabla_{\boldsymbol{z}_{v}}\mathcal{L}_{i}( \boldsymbol{\theta})}$ $\displaystyle=\sum_{v\in\tilde{\mathcal{V}}_{i}}{\frac{\partial{\boldsymbol{z} _{v}}}{\partial{\theta_{j}}}(\hat{\boldsymbol{y}}_{v}-\boldsymbol{y}_{v})} \quad\forall j\in[|\boldsymbol{\theta}|]\,,$ (24) $$

where $\boldsymbol{z}_{v}=\sum_{u\in\mathcal{V}}{\bar{a}_{vu}\boldsymbol{g}_{
\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{s}_{u})}+\sum_{u\in\mathcal{V}_{
i}}{\bar{a}_{vu}^{(i)}\boldsymbol{f}_{\boldsymbol{\theta}_{\mathsf{f}}}(
\boldsymbol{x}_{u})}$.
Taking the derivative of $\boldsymbol{z}_{v}$ with respect to the different entries of $\boldsymbol{\theta}$ leads to

$$ $\displaystyle\frac{\partial{\boldsymbol{z}_{v}}}{\partial{\theta_{\mathsf{s},j }}}$ $\displaystyle=\sum_{u\in\mathcal{V}}{\bar{a}_{vu}\frac{\partial{\boldsymbol{g} _{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{s}_{u})}}{\partial{\theta_{ \mathsf{s},j}}}}\quad\forall j\in[|\boldsymbol{\theta}_{\mathsf{s}}|]$ (25) $\displaystyle\frac{\partial{\boldsymbol{z}_{v}}}{\partial{\theta_{\mathsf{f},j }}}$ $\displaystyle=\sum_{u\in\mathcal{V}}{\bar{a}_{vu}\frac{\partial{\boldsymbol{h} _{\boldsymbol{\theta}_{\mathsf{f}}}(\boldsymbol{s}_{u})}}{\partial{\theta_{ \mathsf{f},j}}}}\quad\forall j\in[|\boldsymbol{\theta}_{\mathsf{f}}|]$ (26) $$

Substituting (25) and (26) into (C) and separating the summation over $\mathcal{V}$ over the different clients concludes the proof.

###### Lemma 1.

###### Proof.

## Appendix D Proof of 4

First notice that

$$ $\displaystyle\nabla_{\boldsymbol{S}}\mathcal{L}_{i}(\boldsymbol{\theta}, \boldsymbol{S})=||\big{(}(\nabla_{\boldsymbol{s}_{q}}\mathcal{L}_{i}( \boldsymbol{\theta},\boldsymbol{S}))^{\mathsf{T}}\quad\forall q\in\mathcal{V} \big{)}\,.$ (27) $$

Using the chain rule and  1, we have

$$ $\displaystyle\nabla_{\boldsymbol{s}_{q}}\mathcal{L}_{i}(\boldsymbol{\theta}, \boldsymbol{S})$ $\displaystyle=\sum_{v\in\tilde{\mathcal{V}}_{i}}{\frac{\partial{\boldsymbol{z} _{v}}}{\partial{\boldsymbol{s}_{q}}}\nabla_{\boldsymbol{z}_{v}}\mathcal{L}_{i} (\boldsymbol{\theta},\boldsymbol{S})}$ $\displaystyle=\sum_{v\in\tilde{\mathcal{V}}_{i}}{\frac{\partial{\boldsymbol{z} _{v}}}{\partial{\boldsymbol{s}_{q}}}(\hat{\boldsymbol{y}}_{v}-\boldsymbol{y}_{ v})}\quad\forall q\in\mathcal{V}\,,$ (28) $$

where
$\boldsymbol{z}_{v}=\sum_{u\in\mathcal{V}}{\bar{a}_{vu}\boldsymbol{s}_{u}}+\sum
_{u\in\mathcal{V}_{i}}{\bar{a}_{vu}^{(i)}\boldsymbol{f}_{\boldsymbol{\theta}_{
\mathsf{f}}}(\boldsymbol{x}_{u})}$.
Taking the derivative of $\boldsymbol{z}_{v}$ with respect to $\boldsymbol{s}_{q}$ leads to

$$ $\displaystyle\frac{\partial{\boldsymbol{z}_{v}}}{\partial{\boldsymbol{s}_{q}}}$ $\displaystyle=\sum_{u\in\mathcal{V}}{\bar{a}_{vu}\frac{\partial{\boldsymbol{s} _{u}}}{\partial{\boldsymbol{s}_{q}}}}$ $\displaystyle=\bar{a}_{vq}\frac{\partial{\boldsymbol{s}_{q}}}{\partial{ \boldsymbol{s}_{q}}}$ $\displaystyle=\bar{a}_{vq}\boldsymbol{I}\quad\forall q\in\mathcal{V}$ (29) $$

Substituting  (D) into  (D) leads to

$$ $\displaystyle\nabla_{\boldsymbol{s}_{q}}\mathcal{L}_{i}(\boldsymbol{\theta}, \boldsymbol{S})$ $\displaystyle=\sum_{v\in\tilde{\mathcal{V}}_{i}}{\bar{a}_{vq}(\hat{\boldsymbol {y}}_{v}-\boldsymbol{y}_{v})}\quad\forall q\in\mathcal{V}$ (30) $$

Finally, substituting  (30) into  (27) concludes the proof.

## Appendix E Scheme to Obtain 𝑨 ¯ [ i ] superscript bold-¯ 𝑨 delimited-[] 𝑖 \boldsymbol{\bar{A}}^{[i]} overbold_¯ start_ARG bold_italic_A end_ARG start_POSTSUPERSCRIPT [ italic_i ] end_POSTSUPERSCRIPT

As discussed in Section 5, FedStruct with decoupled GCN only requires the clients to have access to the local partition of the global $L$-hop combined adjacency matrix, i.e., $\boldsymbol{\bar{A}}^{[i]}$.
In this appendix, we present an algorithm to enable clients to privately acquire this matrix.

We denote by $\boldsymbol{\tilde{A}}^{[i]}=||(\boldsymbol{\tilde{a}}_{v}^{\mathsf{T}},\quad
\forall v\in\tilde{\mathcal{V}}_{i})$ and $\boldsymbol{\hat{A}}^{[i]}=||(\boldsymbol{\hat{a}}_{v}^{\mathsf{T}},\quad
\forall v\in\tilde{\mathcal{V}}_{i})$ the local partition of $\boldsymbol{\tilde{A}}$ and $\boldsymbol{\hat{A}}$ pertaining to the labeled nodes of client $i$, respectively.
Further, note that $\boldsymbol{\hat{A}}^{[i]}=\big{(}\boldsymbol{\tilde{D}}^{[i]}\big{)}^{-1}
\boldsymbol{\tilde{A}}^{[i]}$, where $\boldsymbol{\tilde{D}}^{[i]}\in\mathbb{R}^{|\tilde{\mathcal{V}}_{i}|\times|
\tilde{\mathcal{V}}_{i}|}$ is the diagonal matrix of node degrees, with $\boldsymbol{\tilde{D}}^{[i]}(v,v)=\sum_{u\in\mathcal{V}}{\tilde{a}_{vu}}$, $\forall v\in\tilde{\mathcal{V}}_{i}$.
Also, let $\boldsymbol{\tilde{A}}^{[i]}_{j}\in\mathbb{R}^{|\tilde{\mathcal{V}}_{i}|\times
|\mathcal{V}_{j}|}$ denote the entries of $\boldsymbol{\tilde{A}}^{[i]}$ that connects client $i$ to client $j$ for $j\in[K]$ and define $\boldsymbol{\hat{A}}^{[i]}_{j}$ analogously.
Consequently, we have $\boldsymbol{\hat{A}}^{[i]}_{j}=\big{(}\boldsymbol{\tilde{D}}^{[i]}\big{)}^{-1}
\boldsymbol{\tilde{A}}^{[i]}_{j}$.
We note that client $i$ may compute $\boldsymbol{\hat{A}}^{[i]}_{j}$ locally as it knows the destination of its outgoing edges, i.e., $\boldsymbol{\tilde{A}}^{[i]}_{j}$ for all $j\in[K]$, and can compute $\boldsymbol{\tilde{D}}^{[i]}$.

In client $i$, we are interested in acquiring its local partition of $\boldsymbol{\bar{A}}$, i.e., $\boldsymbol{\bar{A}}^{[i]}$.
For $L_{s}=2$, we have

$$ $\displaystyle\boldsymbol{\bar{A}}^{[i]}_{j}$ $\displaystyle=\beta_{1}\boldsymbol{\hat{A}}^{[i]}_{j}+\beta_{2}\sum_{k\in[K]} \boldsymbol{\hat{A}}^{[i]}_{k}\boldsymbol{\hat{A}}^{[K]}_{j},\quad j\in[K]\,.$ (31) $$

We introduce the notation $[\boldsymbol{\hat{A}}^{[i]}_{j}]^{\ell}=\sum_{k\in[K]}\boldsymbol{\hat{A}}^{[i
]}_{k}\big{[}\boldsymbol{\hat{A}}^{[K]}_{j}\big{]}^{\ell-1}$ and write

$$ $\displaystyle[\boldsymbol{\hat{A}}^{[i]}_{j}]^{2}$ $\displaystyle=\sum_{k\in[K]}\boldsymbol{\hat{A}}^{[i]}_{k}\boldsymbol{\hat{A}} ^{[K]}_{j},\quad j\in[K]$ (32) $\displaystyle=(\boldsymbol{\tilde{D}}^{[i]})^{-1}\sum_{k\in[K]}\underbrace{ \boldsymbol{\tilde{A}}^{[i]}_{k}\boldsymbol{\hat{A}}^{[K]}_{j}}_{\text{ computed at client }k},\quad j\in[K]\,.$ (33) $$

From (33), we note that client $i$ will have stored $[\boldsymbol{\hat{A}}^{[i]}_{j}]^{2}$ for all $j\in[K]$ and, therefore, also $[\boldsymbol{\hat{A}}^{[i]}]^{2}$.
For integer $\ell\geq 2$, we can leverage the information that was acquired in the previous rounds as

$$ $\displaystyle[\boldsymbol{\hat{A}}^{[i]}_{j}]^{\ell}=(\boldsymbol{\tilde{D}}_{ i})^{-1}\sum_{k\in[K]}\underbrace{\boldsymbol{B}_{ijk}}_{\text{computed at client }k},\quad j\in[K]\,.$ (34) $$

where $\boldsymbol{B}_{ijk}=\boldsymbol{\tilde{A}}^{[i]}_{k}[\boldsymbol{\hat{A}}^{[K
]}_{j}]^{\ell-1}$ is an $n_{i}\times n_{j}$ matrix that can be calculated in client $k$.
Hence, the clients may compute $\boldsymbol{\bar{A}}^{[i]}_{j}$ sequentially as

$$ $\displaystyle\boldsymbol{\bar{A}}^{[i]}_{j}$ $\displaystyle=\beta_{1}\boldsymbol{\hat{A}}^{[i]}_{j}+\sum_{\ell=2}^{L_{s}} \beta_{\ell}[\boldsymbol{\hat{A}}^{[i]}_{j}]^{\ell},\quad j\in[K]\,.$ (35) $$

The resulting algorithm is shown in Algorithm 3.
Finally, we notice that Algorithm 3 requires each client to evaluate $L_{s}K^{2}$ matrix products and to communicate $L_{s}(K-1)K$ matrices.
Although the complexity is large, we emphasize that this algorithm is performed only once before the training initiates.

Figure: Algorithm 3 Private acquisition of $\boldsymbol{\bar{A}}^{[i]}$

## Appendix F Experimental Setting

In this section, we provide more details about the experiments in Section 6 and Appendix G.
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. [].
According to this rule-of-thumb, among the datasets considered in this paper, two would be considered heterophilic, i.e., Chameleon and Amazon Ratings.

Next, we provide the hyperparameters for the experiments.
In Table 5, we provide the step sizes $\lambda$ and $\lambda_{\mathsf{s}}$ 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_{\mathsf{s}}$ in the DGCN, the dimensionality of the NSFs, $d_{\mathsf{s}}$, and the model architecture of the node feature and node structure feature predictors, $\boldsymbol{f}_{{\boldsymbol{\theta}}_{\mathsf{f}}}$ and $\boldsymbol{g}_{{\boldsymbol{\theta}}_{\mathsf{s}}}$, respectively.

All the experiments are obtained using an Nvidia A30 with 24GB of memory.

**Table 4: Statistics of the datasets.**
| Data | Cora | CiteSeer | PubMed | Chameleon | Amazon Photo | Amazon Ratings |
| --- | --- | --- | --- | --- | --- | --- |
| $\#$ Classes | 7 | 6 | 3 | 5 | 8 | 5 |
| $|\mathcal{V}|$ | 2708 | 3327 | 19717 | 2277 | 7650 | 24492 |
| $|\mathcal{E}|$ | 5278 | 4676 | 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 |

**Table 5: Hyper-parameters of the datasets.**
| Data | Cora | CiteSeer | PubMed | Chameleon | Amazon Photo | Amazon Ratings |
| --- | --- | --- | --- | --- | --- | --- |
| $\lambda$ | 0.002 | 0.002 | 0.008 | 0.003 | 0.005 | 0.002 |
| $\lambda_{\mathsf{s}}$ | 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 | 1 | 1 | 2 |
| $L_{\mathsf{s}}$ | 10 | 20 | 20 | 1 | 3 | 5 |
| $d_{\mathsf{s}}$ | 256 | 256 | 256 | 256 | 256 | 256 |
| $\boldsymbol{\theta}_{\mathsf{f}}$ layers | [ 1433,64,7 ] | [3703,64,6] | [500,128,3] | [2325,64,5] | [745,256,8] | [300,64,5] |
| $\boldsymbol{\theta}_{\mathsf{s}}$ layers | [256,256,7] | [256,128,64,6] | [256,128,3] | [256,256,5] | [256,256,8] | [256,256,5] |

## Appendix G Additional Results

In this appendix, we provide additional results that we could not include in the main paper due to space constraints.

### G.1 Different Partitionings

In this section, we provide results for different types of data partitioning. We consider three different 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. [] where the global graph is first divided into a number of subgraphs using the Louvain algorithm.
As we strive to have an 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/K$ 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 $K$ clients and assigning it to the first client for which the total number of nodes after a merge 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. [] 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 it to another subgraph such that the resulting number of nodes is less than $n/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. [], as nodes with similar features tend to have the same label, this partitioning method creates a highly heterogeneous partitioning as each subgraph tends to have an over-representation of nodes of a given class.

**Table 6: Classification accuracies for FedStruct with an underlying decoupled GCN. The results are shown for 10 clients with a 10–10–80 train-val-test split.**
|  | Cora | Citeseer | Pubmed |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Central GNN | 82.06$\pm$ 1.09 | 69.17$\pm$ 0.90 | 87.71$\pm$ 0.34 |  |  |  |  |  |  |
| Central DGCN | 83.72 $\pm$ 0.64 | 68.69 $\pm$ 1.04 | 86.26 $\pm$ 0.34 |  |  |  |  |  |  |
| Central MLP | 65.31$\pm$ 1.75 | 64.18$\pm$ 0.89 | 85.80$\pm$ 0.33 |  |  |  |  |  |  |
|  | Louvain | random | kmeans | Louvain | random | kmeans | Louvain | random | kmeans |
| FedAvg GNN | 80.38$\pm$ 1.09 | 63.64$\pm$ 1.59 | 65.68$\pm$ 1.88 | 69.71$\pm$ 0.73 | 65.41$\pm$ 1.54 | 65.58$\pm$ 1.09 | 85.67$\pm$ 0.13 | 85.19$\pm$ 0.35 | 85.79$\pm$ 0.26 |
| FedSGD GNN | 80.99$\pm$ 1.33 | 65.06$\pm$ 1.92 | 67.12$\pm$ 2.01 | 68.55$\pm$ 1.25 | 63.47$\pm$ 1.29 | 65.07$\pm$ 1.39 | 85.31$\pm$ 0.44 | 85.91$\pm$ 0.42 | 86.02$\pm$ 0.35 |
| FedAvg DGCN | 77.88$\pm$ 2.86 | 62.21$\pm$ 1.85 | 66.79$\pm$ 1.12 | 69.88$\pm$ 0.90 | 65.04$\pm$ 1.96 | 67.10$\pm$ 1.02 | 84.36$\pm$ 0.19 | 84.42$\pm$ 0.26 | 85.41$\pm$ 0.32 |
| FedSGD DGCN | 82.51 $\pm$ 1.28 | 66.48$\pm$2.27 | 69.29$\pm$2.04 | 68.38$\pm$0.85 | 63.24$\pm$0.89 | 66.21$\pm$1.41 | 84.69$\pm$0.40 | 84.83$\pm$0.35 | 84.99$\pm$0.41 |
| FedAvg MLP | 65.38$\pm$ 2.62 | 58.24$\pm$ 1.87 | 59.15$\pm$ 1.20 | 65.92$\pm$ 1.19 | 64.89$\pm$ 1.64 | 65.50$\pm$ 1.00 | 85.10$\pm$ 0.24 | 84.46$\pm$ 0.34 | 84.29$\pm$ 0.51 |
| FedSGD MLP | 64.42$\pm$ 0.54 | 63.71$\pm$ 1.59 | 64.24$\pm$ 2.02 | 63.39$\pm$ 0.68 | 63.98$\pm$ 1.53 | 64.92$\pm$ 1.39 | 85.39$\pm$ 0.33 | 85.58$\pm$ 0.39 | 85.00$\pm$ 0.32 |
| FedPub | 76.19 $\pm$ 1.14 | 55.58 $\pm$ 2.65 | 58.06 $\pm$ 2.34 | 66.85$\pm$ 1.03 | 59.80 $\pm$ 1.74 | 60.48$\pm$ 1.32 | 36.15 $\pm$ 9.87 | 46.24$\pm$ 8.50 | 40.64$\pm$ 1.93 |
| Fedsage+ | 80.75$\pm$ 0.88 | 66.32$\pm$ 1.81 | 67.08$\pm$ 2.19 | 68.20$\pm$ 1.34 | 63.37$\pm$ 1.45 | 64.32$\pm$ 1.25 | 85.55$\pm$ 0.59 | 85.37$\pm$ 0.55 | 85.83$\pm$ 0.44 |
| fedsage+ ideal | 82.38$\pm$ 1.28 | 80.85$\pm$ 1.55 | 80.58$\pm$ 1.30 | 68.99$\pm$ 1.33 | 68.91$\pm$ 1.30 | 69.53$\pm$ 1.25 | 84.69$\pm$ 1.14 | 85.66$\pm$ 0.37 | 85.81$\pm$ 0.80 |
| FedStruct (Deg) | 81.64$\pm$ 2.33 | 68.64$\pm$ 1.51 | 70.25$\pm$ 2.33 | 68.41$\pm$ 1.20 | 63.81$\pm$ 1.31 | 66.16$\pm$ 1.31 | 84.52$\pm$ 0.47 | 85.09$\pm$ 0.48 | 85.22$\pm$ 0.37 |
| FedStruct (Fed$\star$) | 80.79 $\pm$ 2.55 | 68.87 $\pm$ 1.25 | 70.68 $\pm$ 2.39 | 68.51 $\pm$ 0.92 | 64.40$\pm$ 1.51 | 65.96$\pm$ 1.25 | 84.96 $\pm$ 0.22 | 84.84$\pm$0.36 | 85.45$\pm$0.24 |
| FedStruct (H2V) | 81.23$\pm$ 1.14 | 80.28$\pm$ 1.44 | 79.80$\pm$ 1.53 | 68.50$\pm$ 0.93 | 66.29$\pm$ 0.87 | 67.20$\pm$ 1.52 | 83.74$\pm$ 0.39 | 86.65$\pm$ 0.53 | 86.01$\pm$ 0.38 |
| FedStruct-p (H2V) | 80.92$\pm$ 1.11 | 78.75 $\pm$ 1.09 | 79.72$\pm$ 1.02 | 68.80$\pm$ 0.80 | 65.65 $\pm$ 1.58 | 66.70 $\pm$ 1.28 | 82.86 $\pm$ 0.37 | 85.01 $\pm$ 0.34 | 85.30$\pm$0.42 |
| Local GNN | 75.52$\pm$ 1.45 | 39.23$\pm$ 1.21 | 46.80$\pm$ 4.59 | 58.75$\pm$ 1.37 | 38.99$\pm$ 1.60 | 49.15$\pm$ 5.21 | 81.17$\pm$ 0.37 | 79.10$\pm$ 0.54 | 81.34$\pm$ 0.63 |
| Local DGCN | 76.29$\pm$1.74 | 41.85$\pm$1.23 | 50.85$\pm$4.15 | 58.66$\pm$1.14 | 41.22$\pm$1.43 | 51.44$\pm$5.67 | 81.72$\pm$0.46 | 78.61$\pm$0.50 | 81.28$\pm$0.64 |
| Local MLP | 66.33$\pm$ 1.12 | 38.57$\pm$ 1.55 | 45.81$\pm$ 3.90 | 53.27$\pm$ 1.02 | 39.50$\pm$ 1.19 | 50.12$\pm$ 5.80 | 82.78$\pm$ 0.67 | 78.51$\pm$ 0.57 | 80.81$\pm$ 0.56 |

Finally, we consider a random partitioning where each node is allocated to a client uniformly at random.
As this partitioning does not take into account the topology or the features, we end up with a large number of interconnections where each subgraph has the same distribution over class labels, i.e., the data is 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.

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%-80%.
We use this split to focus on a challenging semi-supervised scenario.
Furthermore, each of 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 DGCN and when employing an MLP. By comparing the performance of Central GNN with Central MLP, one may infer the gains of accounting for the spatial structure within the data.
As seen in the table, exploiting the graph structure brings the largest benefits for Cora and Chameleon.
Moreover, it can be seen for all datasets GNN and DGCN 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 on the partitioning.
From Table 6, it can be seen that the gap is 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.

Considering FedSGD GNN and FedSGD DGCN, it can be seen that all scenarios benefit from collaborative learning.
For the Louvain partitioning, due to its community-based partitioning with the 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 in 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-painting of missing one-hop neighbors.
Hence, this scheme serves as an upper bound on techniques based on in-painting 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 Table 6, we see that this scheme is robust to different partitionings by offering consistent performance close to the Central GNN.

We consider FedStruct with three different methods to generate NSFs: one-hot degree vectors (Deg), Fed$\star$, and our task-dependent method Hop2Vec (H2V), see Appendix A for information. The hyper-parameters are chosen as in Table 5.
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$\star$ 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 A.
Moreover, it can be seen that Hop2Vec performs close to fedsage+ ideal for all scenarios and is sometimes superior, e.g., on the Chameleon datasets.
This highlights the importance of going beyond the one-hop neighbors for some datasets, something that is not possible in fedsage+ ideal.

### G.2 Impact of the Number of Labeled Training Nodes

Figure: Figure 3: Accuracy vs training-ratio for Cora with random partitioning and $10$ clients.
Refer to caption: extracted/5664685/Figures/train_ratio.png

As highlighted in Liu et al. [], the decoupled GCN is suitable in situations where over-smoothing is a bottleneck.
In Dong et al. [], it was further shown that decoupled GCN is especially suited for semi-supervised learning due to its ability to leverage pseudo-labels from all the unlabeled nodes during training.
In Fig. 3, we show the performance of FedStruct on the Cora dataset using different NSF generators for different amounts of labeled nodes in the training set.
In particular, we use a $x$%-10%-$(0.9-x)$% train-val-test split where $x$ denotes the ratio of labeled training nodes.

From Fig 3, it can be seen that FedStruct with H2V achieves a performance very close to the Central GNN for all fractions of labeled nodes in the training set. Notably, FedStruct performs very well even for a heavily semi-supervised scenario: it is performant already at 5% of labeled training nodes, achieving close to 80% top-1 accuracy.
Federated approaches not utilizing global graph structure, like FedSage+, exhibit a sharper decline in performance for a low fraction of labeled nodes. For example,
the top-$1$ accuracy of FedSage+ declines from about 75%
for 50% labeled nodes in the training set to below 60% for 5% labeled nodes. The performance of FedStruct is superior for all fractions of level nodes and experiences a much shallower decline, from about 84% for 50% labeled nodes in the training set to about 76% for 5% labeled nodes for FedStruct with H2V.
Finally, the performance of local GNN deteriorates significantly from scarce labels.

### G.3 Impact of the number of Layers in the Decoupled GCN

In this section, we provide results on the impact of the number of layers used in the decoupled GCN, $L_{s}$, in FedStruct on the Cora dataset.
We consider K-means partitioning and 10 clients.
In Fig. 4, we show the top-1 accuracy after training FedStruct using both NFEs and NSEs but at inference, we use only NSEs (s) or both NFEs and NSEs (s+f).
The Central GNN and FedSGD GNN rely on GraphSage with $3$ layers and is, therefore, independent of the layers used in the decoupled GCN.

First, we observe that the top-1 accuracy for Deg s+f does not vary significantly with respect to $L_{s}$.
For Hop2Vec (H2V), the situation is different.
The performance of H2V is low for $L_{s}$ below 10 and above 30, achieving the best performance between $10$ and $20$ layers.
This is because the NSE is unable to learn an extended neighborhood for small $L_{s}$ whereas, for large $L_{s}$, over-smoothing becomes the bottleneck.
We also visualize H2V s to highlight the impact of NSFs alone.
H2V s achieves $75\%$ whereas H2V s+f achieves $80\%$ top1-accuracy.
From here, we conclude that the NSEs alone convey useful information to predict labels but that NFEs are required to achieve performance close to Central GNN.

Figure: Figure 4: Accuracy vs number of decoupled GCN propagation layers $L_{s}$ on Cora with K-means partitioning.
Refer to caption: extracted/5664685/Figures/layers.png

## Appendix H Communication Complexity

**Table 7: Communication Complexity of FedStruct.**
| Data | before training | training |
| --- | --- | --- |
| FedStruct | $\mathcal{O}(K\cdot n\cdot d+L_{\mathsf{s}}\cdot n^{2})$ | $\mathcal{O}(E\cdot K\cdot|\boldsymbol{\theta}|)$ |
| FedStruct + Hop2Vec | $\mathcal{O}(K\cdot n\cdot d+L_{\mathsf{s}}\cdot n^{2})$ | $\mathcal{O}(E\cdot K\cdot|\boldsymbol{\theta}|+E\cdot K\cdot n\cdot d)$ |
| FedStruct-p | $\mathcal{O}(K\cdot n\cdot d+L_{\mathsf{s}}\cdot p\cdot n)$ | $\mathcal{O}(E\cdot K\cdot|\boldsymbol{\theta}|)$ |
| FedSage+ | 0 | $\mathcal{O}(E\cdot K^{2}\cdot|\boldsymbol{\theta}|+E\cdot K\cdot n\cdot d)$ |

In Table 7, we present the communication complexity of FedStruct alongside that of FedSage+.
We divide the communication complexity into two parts: an offline component, accounting for events taking place before the training is 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, and nodes in the graph, respectively.
Parameter $d$ is the node feature size (all feature dimensions are assumed to be equal to $d$), and $|\boldsymbol{\theta}|$ is the number of model parameters (all model parameters are assumed to be of the same order). In the following, we discuss the complexity of the different variants of FedStruct.

The results in Table 7 are based on the following observations:

- •
FedStruct requires an offline phase where clients acquire $\boldsymbol{\bar{A}}^{[i]}$ and $\mathcal{S}_{i}=\{\boldsymbol{s}_{u},\forall u\in\mathcal{V}_{i}\}$ from other clients. The communication requirement of this phase is $L_{\mathsf{s}}\cdot n^{2}$ and $K\cdot n\cdot d$ parameters, respectively.
Beyond the offline phase, similar to the previous methods, $\boldsymbol{\theta}$ is federated during the training phase.
- •
FedStruct with Hop2Vec shares the same offline phase as without Hop2Vec.
However, during the training phase, clients exchange gradients $\nabla_{\boldsymbol{S}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})$, which entails an additional complexity of $E\cdot K\cdot n\cdot d$.
- •
In FedSage, feature generator parameters and node embedding vectors are shared between all clients, amounting to a communication overhead of $E\cdot K^{2}\cdot|\boldsymbol{\theta}|$ and $E\cdot K\cdot n\cdot d$ parameters, respectively.

As described in Section 5, FedStruct includes an offline phase before the training.
The online complexity of FedStruct is significantly lower than that of FedSage, which is on the order of $n$.
On the other hand, the online complexity of FedStruct with Hop2Vec, is also on the order of $n$.
The offline complexity of FedStruct is on the order of $n^{2}$.
While the offline complexity is less critical than the online complexity, scaling as $n^{2}$ may be impractical for large networks. In Appendix H.1, we provide a pruning method to reduce this complexity without hampering the performance significantly.
The communication of the pruned version (FedStruct-p) is shown in Table 7 and the performance is shown in Table 8.

**Table 8: Classification accuracy of FedStruct with pruning (pruning parameter $p=30$) and without pruning. The results for pruning are presented in bold. The results are shown for 10 clients with a 10–10–80 train-val-test split.**
|  | Cora | Citeseer | Pubmed |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Central GNN | 82.06$\pm$ 1.09 | 69.17$\pm$ 0.90 | 87.71$\pm$ 0.34 |  |  |  |  |  |  |
| Central MLP | 65.31$\pm$ 1.75 | 64.18$\pm$ 0.89 | 85.80$\pm$ 0.33 |  |  |  |  |  |  |
|  | Louvain | random | kmeans | Louvain | random | kmeans | Louvain | random | kmeans |
| FedStruct (Deg) | 82.14$\pm$ 0.76 | 67.83$\pm$ 2.73 | 70.82$\pm$ 0.88 | 67.98$\pm$ 1.58 | 64.13$\pm$ 1.24 | 65.46$\pm$ 2.11 | 84.65$\pm$ 0.41 | 84.87$\pm$ 0.38 | 85.31$\pm$ 0.60 |
| FedStruct (Fed$\star$) | 80.79 $\pm$ 2.55 | 68.87 $\pm$ 1.25 | 70.68 $\pm$ 2.39 | 68.51 $\pm$ 0.92 | 64.40$\pm$ 1.51 | 65.96$\pm$ 1.25 | 84.96 $\pm$ 0.22 | 84.84$\pm$0.36 | 85.45$\pm$0.24 |
| FedStruct (H2V) | 80.81$\pm$ 1.32 | 80.00$\pm$ 1.21 | 80.01$\pm$ 1.51 | 67.99$\pm$ 1.85 | 66.73$\pm$ 1.45 | 66.93$\pm$ 1.29 | 83.97$\pm$ 0.49 | 86.05$\pm$ 0.48 | 86.25$\pm$ 0.50 |
| FedStruct-p (Deg) | 81.82$\pm$ 0.89 | 69.23$\pm$ 2.21 | 71.48$\pm$ 1.16 | 68.01$\pm$ 1.93 | 63.97$\pm$ 1.31 | 65.83$\pm$ 1.79 | 84.68$\pm$ 0.43 | 84.74$\pm$ 0.41 | 85.46$\pm$ 0.60 |
| FedStruct-p (Fed$\star$) | 80.03$\pm$1.10 | 67.69$\pm$0.84 | 68.72$\pm$1.95 | 68.91$\pm$ 1.14 | 64.43$\pm$1.47 | 65.17$\pm$1.42 | 85.00$\pm$0.32 | 84.73$\pm$0.28 | 85.39$\pm$0.20 |
| FedStruct-p (H2V) | 80.19$\pm$ 1.28 | 79.36$\pm$ 1.59 | 79.92$\pm$ 1.40 | 67.85$\pm$ 2.01 | 66.12$\pm$ 1.36 | 66.96$\pm$ 1.54 | 82.39$\pm$ 0.76 | 84.18$\pm$ 0.38 | 84.25$\pm$ 0.70 |

### H.1 Complexity Reduction via Pruning

The offline complexity component of FedStruct scales with $n^{2}$, making it impractical for very large networks.
In this section, we introduce a modified version of FedStruct that significantly reduces the $n^{2}$ complexity while achieving similar performance.
This modified version of FedStruct builds on the fact that real-world graph-structured datasets are often sparse.

The key idea is to apply a pruning technique when obtaining the shared matrix $\boldsymbol{\bar{A}}^{[i]}$ using Algorithm 3 in Appendix E.
More specifically, we choose an integer $p\ll n$ and, in each offline communication round, retain only the top $p\cdot n_{i}$ values of matrix $\boldsymbol{B}_{ijk}$ (originally of dimension $n_{i}\times n_{j}$).
Hence, the complexity is reduced from $L_{\mathsf{s}}\cdot n^{2}$ to $L_{\mathsf{s}}\cdot p\cdot n$. Overall the complexity of FedStruct with pruning is the same of FedSage, i.e., on the order of $n$.
The communication complexity of FedStruct with pruning is provided in Table 7.

The performance of FedStruct with pruning (FedStruct-p) is illustrated in  Table 8 for pruning parameter $p=30$. It can be observed that the performance of FedStruct with pruning is similar to that of FedStruct with no pruning across all datasets, partitionings, and NSFs.
Table 8 also highlights the robustness of FedStruct against the presence of structural noise.
That is, in the presence of unreliable or noisy connections, pruning can be used to limit to reliable connections whilst achieving comparable performance to the case where all connections are reliable Fox and Rajamanickam [].

## Appendix I Discussion

### I.1 Privacy

Previous frameworks for subgraph FL Zhang et al. [], Peng et al. [], Lei et al. [], Zhang et al. [], Liu et al. [], Zhang et al. [], Chen et al. [], Du and Wu [] 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 a 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, we present a slightly different version of FedStruct that relies on sharing aggregated quantities between clients without affecting the performance of the original version.

In FedStruct using task-agnostic NSFs, each client is provided with $\boldsymbol{S}$, i.e., the NSFs of all clients.
Consider an honest-but-curious client $i$ with NSFs $\{\boldsymbol{s}_{u}:u\in\mathcal{V}_{i}\}$.
Client $i$ may target client $j$ by identifying NSFs within client $j$ that closely match some of its own NSFs.
By this simple procedure, client $i$ may compare the topology of the matched local nodes and infer the topology of some of the nodes within $j$.
Furthermore, as $\boldsymbol{\theta}_{s}$ is shared among all clients, client $i$ would potentially be able to guess the labels of the identified nodes within client $j$.
Given a node’s label and topology, it may be further possible to infer something about the node features.
Using task-dependent NSF, i.e., 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 1 and 2, the summation over $\mathcal{V}$ may be split into a summation over clients.
The prediction and local gradients for client $i$ may then be written as

$$ $\displaystyle\hat{\boldsymbol{y}}_{v}$ $\displaystyle=\mathrm{softmax}\Big{(}\sum_{j\in[K]}\sum_{u\in\mathcal{V}_{j}}{ \bar{a}_{vu}\boldsymbol{g}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{s}_{ u})}+\sum_{u\in\mathcal{V}_{i}}{\bar{a}_{vu}^{(i)}\boldsymbol{f}_{\boldsymbol{ \theta}_{\mathsf{f}}}(\boldsymbol{x}_{u})}\Big{)}\,,\quad v\in\tilde{\mathcal{ V}}_{i},$ (36) $\displaystyle\frac{\partial{\mathcal{L}_{i}(\boldsymbol{\theta})}}{\partial{ \theta_{\mathsf{s},q}}}$ $\displaystyle=\sum_{v\in\tilde{\mathcal{V}}_{i}}\sum_{j\in[K]}{\sum_{u\in \mathcal{V}_{j}}\bar{a}_{vu}\frac{\partial{\boldsymbol{g}_{\boldsymbol{\theta} _{\mathsf{s}}}(\boldsymbol{s}_{u})}}{\partial{\theta_{\mathsf{s},q}}}(\hat{ \boldsymbol{y}}_{v}-\boldsymbol{y}_{v})},\quad\forall q\in[|\boldsymbol{\theta }_{s}|].$ (37) $$

Notably, client $i$ may evaluate its local gradient provided access to

$$ $\displaystyle\bar{\boldsymbol{s}}^{(j)}_{v}$ $\displaystyle=\sum_{u\in\mathcal{V}_{j}}{\bar{a}_{vu}\boldsymbol{g}_{ \boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{s}_{u})},\quad\forall v\in\tilde {\mathcal{V}}_{i}$ (38) $\displaystyle\tilde{\boldsymbol{s}}^{(j)}_{vq}$ $\displaystyle=\sum_{u\in\mathcal{V}_{j}}\bar{a}_{vu}\frac{\partial{\boldsymbol {g}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{s}_{u})}}{\partial{\theta_{ \mathsf{s},q}}},\quad\forall q\in[|\boldsymbol{\theta}_{s}|],\forall v\in \tilde{\mathcal{V}}_{i}$ (39) $$

for each client $j\in[K]$.
For client $j\neq i$ to be able to evaluate these quantities, it needs access to $\bar{a}_{vu}$ for all $v\in\tilde{\mathcal{V}}_{i}$ and $u\in\tilde{\mathcal{V}}$, i.e., the weighted sum of the $\ell$-hop paths, $\ell\in[L]$, from nodes in client $i$ to nodes in client $j$.
Following Appendix E, client $j$ has access to $a_{vu}$ for $v\in\tilde{\mathcal{V}}_{j}$ and $u\in\mathcal{V}$.
Notably, $a_{vu}\neq a_{uv}$ due to different degree normalizations.
Hence, to obtain the required quantitites in (38) and (39), client $i$ may share $\{\bar{a}_{vu}:v\in\tilde{\mathcal{V}}_{i},u\in\mathcal{V}_{j}\}$ with client $j\in[K]$ after the algorithm in Appendix E 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.
Because of this, the training has to be done in two phases for each iteration where phase 1 accounts for each client $i\in[K]$ to collect the quantities in (38) and (39) 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 (38) and (39) amounts to sharing $|\tilde{\mathcal{V}}_{i}|c$ and $|\boldsymbol{\theta}_{s}|c$ parameters, respectively, where $c$ is the number of class labels.
Hence, in total, each client $i$ must share $(|\tilde{\mathcal{V}}\setminus\tilde{\mathcal{V}}_{i}|+|\boldsymbol{\theta}_{s
}|)c$ 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 Lei et al. [] to argue around the difficulty of perfectly reconstructing the local NSFs.
To this end, we take a conservative approach and consider honest-but-curious clients where all but one client is colluding.
Hence, we may consider two clients where client 1 is the attacker and client 2 is the target.
In each iteration, client 1 receives $\tilde{\boldsymbol{s}}_{v}^{(2)}\in\mathbb{R}^{c}$ and $\tilde{\boldsymbol{s}}^{(2)}_{vq}\in\mathbb{R}^{c}$ for $v\in\tilde{\mathcal{V}}_{1}$ and $q\in[|\boldsymbol{\theta}_{2}|]$.
To evaluate $\tilde{\boldsymbol{s}}_{v}^{(2)}$, client 2 utilizes $\norm{\boldsymbol{a}_{v}}_{0}$ $d_{s}$-dimensional NSFs where the L0-norm counts the number of non-zero elements.
Hence, for each received aggregate $\tilde{\boldsymbol{s}}_{v}^{(2)}$, client $1$ obtains $c$ observations from $\norm{\boldsymbol{a}_{v}}_{0}d_{s}$ unknowns.
In total, client $1$ will collect $|\tilde{\mathcal{V}}_{1}|$ such observations, i.e., it observes $c|\tilde{\mathcal{V}}_{1}|$ parameters.
Assuming a, for client $2$, the worst-case scenario with all $\boldsymbol{a}_{v}$ being non-zero in the same locations with $m$ non-zero elements, client $2$ will use the same inputs for each observation in client $1$.
Hence, if $nd_{s}>c|\tilde{\mathcal{V}}_{1}|$, client $1$ is unable to 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 $md_{s}/c$.
Similarly, to evaluate $\tilde{\boldsymbol{s}}^{(2)}_{vq}$, client 2 utilizes $\norm{\boldsymbol{a}_{v}}_{0}$ $d_{s}$-dimensional inputs to compute a $c$-dimensional output.
Hence, client $2$ will share $|\boldsymbol{\theta}_{s}|c$ parameters, computed from $\norm{\boldsymbol{a}_{v}}_{0}d_{s}$ parameters $|\tilde{\mathcal{V}}_{1}|$ times.
Hence, again considering the worst-case view, if $md_{s}>c|\boldsymbol{\theta}_{s}||\tilde{\mathcal{V}}_{1}|$, 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 $\boldsymbol{\theta}_{s}$ but rather over the NSFs $\boldsymbol{S}$ directly.
The problem we face in FedStruct is that each client has access to $\boldsymbol{S}$.
To alleviate this issue, we use Theorem 4 to split the summation over $\mathcal{V}$ to obtain

$$ $\displaystyle\bar{\boldsymbol{s}}^{(j)}_{v}$ $\displaystyle=\sum_{u\in\mathcal{V}_{j}}\bar{a}_{vu}\boldsymbol{s}_{u},\quad \forall v\in\tilde{\mathcal{V}}_{i}.$ (40) $$

Furthermore, the local gradients for the NSFs in client $i$ are given as

$$ $\nabla_{\boldsymbol{S}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})= \sum_{v\in\tilde{\mathcal{V}}_{i}}{\boldsymbol{\bar{a}}_{v}(\hat{\boldsymbol{y }}_{v}-\boldsymbol{y}_{v})^{\mathsf{T}}}.\,$ (41) $$

We note that (40) is required to compute the local predictions on $\tilde{\mathcal{V}}_{i}$, and hence to obtain (41).
In this version of FedStruct, the training procedure will be divided into three phases.
Phase 1 amounts to each client evaluating (40) for all other clients and sharing the results.
This results in the sharing of $|\tilde{\mathcal{V}}\setminus\tilde{\mathcal{V}}_{i}|c$ in total for each client.
Phase 2 amounts to each client evaluating its local gradient in (41) and sharing it with the server, similar to the original FedStruct.
Next, the server aggregates the local gradients over $\boldsymbol{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 honest-but-curious clients with all but one colluding against a single target.
We denote the colluding clients as client $1$ and the target as client $2$.
Client $1$ observes (40) which constitutes $c$ observations from $\norm{\boldsymbol{a}_{v}}_{0}$ $c$-dimensional inputs.
Assuming a worst-case scenario as above with all $\boldsymbol{a}_{v}$ having $m$ non-zero entries in the same locations, client $1$ observes in total $c|\tilde{\mathcal{V}}_{1}|$ parameters from $mc$ inputs.
Hence, to prevent client $1$ from perfectly reconstructing individual NSFs, client $2$ must ensure that $m>|\tilde{\mathcal{V}}_{1}|$.
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.

### I.2 Heterophily

Employing a 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 is one of the well-known approaches to deal with heterophilic graphs Zheng et al. [].
Notably, Abu-El-Haija et al. [] 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. [] 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 $\{\beta_{j}\}_{j=1}^{L_{\mathsf{s}}}$ can be trained or adjusted to control the mixing weight of different $l$-hop neighbors.
This allows the network to explicitly capture both local and global structural information within the graph.
Specifically, different powers of the normalized adjacency matrix
$\boldsymbol{\hat{A}}^{l},\ l\in[L_{\mathsf{s}}]$,
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 $\{\beta_{j}\}_{j=1}{L_{\mathsf{s}}}$ 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, as proposed by Zheng et al. [].
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. [] introduces a novel approach by defining a geometric Euclidean space and establishing a new neighborhood for nodes that are proximate in 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 in the latent structural space. Specifically, the use of methods such as Struc2Vec Ribeiro et al. [] 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 to consistent node label predictions.
This approach showcases FedStruct’s capacity to capture latent structural relationships and enhance the model’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 Table 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 FedSage+. Note that the improvement is larger for the more heterophilic dataset. Similar results can be observed for
different partitioning methods, see Table 6. For Chameleon, FedStruct with Hop2Vec outperforms FedSage+ with 6.33%, 16.88% and 15.73% for Louvain, random and K-means partitioning, respectively.
For Amazon ratings, FedStruct with Hop2Vec outperforms FedSage+ 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 homophily/heterophily (in contrast to frameworks such as FedSage+ and FedPub), underscores the adaptability and effectiveness of our framework to diverse graph scenarios, affirming its potential for a wide range of applications.

## Appendix J FedStruct with Knowledge of the Global Graph

In this section, we 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 we 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 GNN model may be used, i.e., it is not restricted to decoupled GCN (although, in Sec. J.3, we discuss the advantages of using a decoupled GCN).
Furthermore, any conventional NSF methods may be used such as Node2Vec and GDV that require knowledge of the $L$-hop neighborhood.

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 5.
The FedStruct framework for this setting is conceptually shown in Fig. 5.

Figure: Figure 5: FedStruct framework when the server has knowledge of the global graph’s connections. Global Graph: underlying graph consisting of interconnected subgraphs. Local graphs: clients’ subgraphs augmented with external nodes (without features or labels). Structure encoding: The server generates node structure features and node structure embeddings for each node and shares them with the clients. Augmented local graphs: Generate node feature embeddings. Federated learning: Federated learning step exploiting node feature embeddings and node structure embeddings.
Refer to caption: extracted/5664685/Figures/fedstruct-a.png

Using a generic GNN, the local gradients are given in the following theorem.

###### Proposition 5.

Let $\mathcal{L}_{i}(\boldsymbol{\theta})$, $\boldsymbol{\theta}=(\boldsymbol{\theta}_{\mathsf{f}}||\boldsymbol{\theta}_{
\mathsf{s}}||\boldsymbol{\theta}_{\mathsf{c}})$, be the local training loss for client $i$ in (7) and $\hat{\boldsymbol{y}}_{v}$ be given in (9).
The gradient

$$ $\nabla_{\boldsymbol{\theta}}\mathcal{L}_{i}(\boldsymbol{\theta})=||\left(\frac {\partial{\mathcal{L}_{i}(\boldsymbol{\theta})}}{\partial{\theta_{j}}}\quad \forall j\in[|\boldsymbol{\theta}|]\right)\,$ (42) $$

is given by

$$ $\displaystyle\frac{\partial{\mathcal{L}_{i}(\boldsymbol{\theta})}}{\partial{ \theta_{\mathsf{s},j}}}$ $\displaystyle=\sum_{v\in\tilde{\mathcal{V}}}{\frac{\partial{\boldsymbol{s}_{v} ^{(L_{\mathsf{s}})}}}{\partial{\theta_{\mathsf{s},j}}}\boldsymbol{\Theta}_{ \mathsf{c}}^{(\mathsf{s})}(\hat{\boldsymbol{y}}_{v}-\boldsymbol{y}_{v})}\quad \forall j\in[|\boldsymbol{\theta}_{\mathsf{s}}|],$ $\displaystyle\frac{\partial{\mathcal{L}_{i}(\boldsymbol{\theta})}}{\partial{ \theta_{\mathsf{f},j}}}$ $\displaystyle=\sum_{v\in\tilde{\mathcal{V}}}{\frac{\partial{\boldsymbol{h}_{v} ^{(L)}}}{\partial{\theta_{\mathsf{f},j}}}\boldsymbol{\Theta}_{\mathsf{c}}^{( \mathsf{f})}(\hat{\boldsymbol{y}}_{v}-\boldsymbol{y}_{v})}\quad\forall j\in[| \boldsymbol{\theta}_{\mathsf{f}}|],$ $\displaystyle\frac{\partial{\mathcal{L}_{i}(\boldsymbol{\theta})}}{\partial{ \theta_{\mathsf{c},j}^{(\mathsf{s})}}}$ $\displaystyle=\sum_{v\in\tilde{\mathcal{V}}}{\frac{\partial{\big{(}( \boldsymbol{\Theta}_{\mathsf{c}}^{(\mathsf{s})})^{\mathsf{T}}\boldsymbol{s}_{v }^{(L_{\mathsf{s}})}\big{)}}}{\partial{\theta_{\mathsf{c},j}^{(\mathsf{s})}}}( \hat{\boldsymbol{y}}_{v}-\boldsymbol{y}_{v})}\quad\forall j\in[|\boldsymbol{ \theta}_{\mathsf{c}}^{(\mathsf{s})}|],$ $\displaystyle\frac{\partial{\mathcal{L}_{i}(\boldsymbol{\theta})}}{\partial{ \theta_{\mathsf{c},j}^{(\mathsf{f})}}}$ $\displaystyle=\sum_{v\in\tilde{\mathcal{V}}}{\frac{\partial{\big{(}( \boldsymbol{\Theta}_{\mathsf{c}}^{(\mathsf{f})})^{\mathsf{T}}\boldsymbol{h}_{v }^{(L)}\big{)}}}{\partial{\theta_{\mathsf{c},j}^{(\mathsf{f})}}}(\hat{ \boldsymbol{y}}_{v}-\boldsymbol{y}_{v})}\quad\forall j\in[|\boldsymbol{\theta} _{\mathsf{c}}^{(\mathsf{f})}|]\,,$ $$

where $\theta_{\cdot,j}$ denotes the $j$-th entry of vector $\boldsymbol{\theta}_{\cdot,j}$.

The proof of the theorem is given in Section J.1.

Note that client $i$ cannot compute $\nabla_{\boldsymbol{\theta}}\mathcal{L}_{i}(\boldsymbol{\theta})$ directly as calculating $\frac{\partial{\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}}}{\partial{\theta_{
\mathsf{s},j}}}$ requires knowledge of the global graph connections. Hence, the server must provide $\frac{\partial{\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}}}{\partial{\theta_{
\mathsf{s},j}}}$ along with $\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}$ for all $v\in\tilde{\mathcal{V}}_{i}$. The FedStruct framework when the server has knowledge of the global graph is described in Alg. 4.

Figure: Algorithm 4 Algorithm for FedStruct with knowledge of the global graph

###### Proposition 5.

### J.1 Proof of 5

Using  (C) we have

$$ $\displaystyle\frac{\partial{\mathcal{L}_{i}(\boldsymbol{\theta})}}{\partial{ \theta_{j}}}=\sum_{v\in\tilde{\mathcal{V}}_{i}}{\frac{\partial{\boldsymbol{z}_ {v}}}{\partial{\theta_{j}}}(\hat{\boldsymbol{y}}_{v}-\boldsymbol{y}_{v})}\,,$ $$

where $\boldsymbol{z}_{v}=(\boldsymbol{\Theta}_{\mathsf{c}}^{(\mathsf{s})})^{\mathsf{
T}}\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}+(\boldsymbol{\Theta}_{\mathsf{c}}^{(
\mathsf{f})})^{\mathsf{T}}\boldsymbol{h}_{v}^{(L)}$.
Taking the derivative of $\boldsymbol{z}_{v}$ with respect to different entries of $\boldsymbol{\theta}$ leads to

$$ $\displaystyle\frac{\partial{\boldsymbol{z}_{v}}}{\partial{\theta_{\mathsf{s},j }}}$ $\displaystyle=\frac{\partial{\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}}}{\partial{ \theta_{\mathsf{s},j}}}\boldsymbol{\Theta}_{\mathsf{c}}^{(\mathsf{s})}\quad \forall j\in[|\boldsymbol{\theta}_{\mathsf{s}}|]$ (43) $\displaystyle\frac{\partial{\boldsymbol{z}_{v}}}{\partial{\theta_{\mathsf{f},j }}}$ $\displaystyle=\frac{\partial{\boldsymbol{h}_{v}^{(L)}}}{\partial{\theta_{ \mathsf{f},j}}}\boldsymbol{\Theta}_{\mathsf{c}}^{(\mathsf{f})}\quad\forall j \in[|\boldsymbol{\theta}_{\mathsf{f}}|]$ (44) $\displaystyle\frac{\partial{\boldsymbol{z}_{v}}}{\partial{\theta_{\mathsf{c},j }^{(\mathsf{s})}}}$ $\displaystyle=\frac{\partial{\big{(}(\boldsymbol{\Theta}_{\mathsf{c}}^{( \mathsf{s})})^{\mathsf{T}}\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}\big{)}}}{ \partial{\theta_{\mathsf{c},j}^{(\mathsf{s})}}}\quad\forall j\in[|\boldsymbol{ \theta}_{\mathsf{c}}^{(\mathsf{s})}|]$ (45) $\displaystyle\frac{\partial{\boldsymbol{z}_{v}}}{\partial{\theta_{\mathsf{c},j }^{(\mathsf{f})}}}$ $\displaystyle=\frac{\partial{\big{(}(\boldsymbol{\Theta}_{\mathsf{c}}^{( \mathsf{f})})^{\mathsf{T}}\boldsymbol{h}_{v}^{(L)}\big{)}}}{\partial{\theta_{ \mathsf{c},j}^{(\mathsf{f})}}}\quad\forall j\in[|\boldsymbol{\theta}_{\mathsf{ c}}^{(\mathsf{f})}|]\,.$ (46) $$

Substituting (43), (44), (45), and (46) into (C) concludes the proof.

### J.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 9, we provide some results for these NSFs and benchmark them against Global DGCN and FedStruct (H2V) without knowledge of the adjacency matrix.
While FedStruct (GDV) is mostly inferior to FedStruct (H2V), leveraging Node2Vec 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.

**Table 9: Classification accuracies for FedStruct with and without knowledge of the adjacency matrix. The results are shown for 10 clients with a 10–10–80 train-val-test split.**
|  | Cora | Citeseer | Pubmed |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Central DGCN | 83.72 $\pm$ 0.64 | 68.69 $\pm$ 1.04 | 86.26 $\pm$ 0.34 |  |  |  |  |  |  |
|  | Louvain | random | kmeans | Louvain | random | kmeans | Louvain | random | kmeans |
| Global adjacency matrix not known to server |  |  |  |  |  |  |  |  |  |
| FedStruct (DGCN+H2V) | 81.34$\pm$ 1.40 | 79.62$\pm$ 0.85 | 80.34$\pm$ 0.62 | 68.48$\pm$ 0.98 | 66.34$\pm$ 1.03 | 66.62$\pm$ 1.59 | 83.39$\pm$ 0.34 | 85.48$\pm$ 0.29 | 85.93$\pm$ 0.30 |
| Global adjacency matrix known to server |  |  |  |  |  |  |  |  |  |
| FedStruct (DGCN+GDV) | 81.27$\pm$ 1.56 | 72.09$\pm$ 1.70 | 74.55$\pm$ 1.47 | 68.82$\pm$ 0.91 | 64.92$\pm$ 1.04 | 66.22$\pm$ 1.37 | 84.98$\pm$ 0.21 | 85.59$\pm$ 0.26 | 85.88$\pm$ 0.21 |
| FedStruct (DGCN+N2V) | 82.26$\pm$ 1.21 | 80.76$\pm$ 0.91 | 80.97$\pm$ 1.01 | 68.46$\pm$ 1.17 | 66.88$\pm$ 1.19 | 67.23$\pm$ 0.92 | 84.84$\pm$ 0.23 | 86.87$\pm$ 0.31 | 87.08$\pm$ 0.24 |
| FedStruct (GNN+H2V) | 80.87$\pm$ 0.51 | 66.84$\pm$ 0.71 | 68.06$\pm$ 1.22 | 68.89$\pm$ 0.99 | 63.77$\pm$ 1.71 | 64.66$\pm$ 0.96 | 76.04$\pm$ 6.77 | 85.27$\pm$ 0.45 | 82.92$\pm$ 4.92 |
| FedStruct (GNN+GDV) | 80.62$\pm$ 0.79 | 69.50$\pm$ 1.23 | 69.86$\pm$ 1.94 | 68.96$\pm$ 1.09 | 64.78$\pm$ 1.11 | 64.90$\pm$ 1.17 | 81.56$\pm$ 5.46 | 85.12$\pm$ 0.40 | 85.36$\pm$ 0.30 |
| FedStruct (GNN+ N2V) | 81.23$\pm$ 1.02 | 75.24$\pm$ 1.00 | 75.91$\pm$ 0.90 | 69.22$\pm$ 1.26 | 64.80$\pm$ 1.71 | 65.53$\pm$ 1.15 | 76.11$\pm$ 6.80 | 86.24$\pm$ 0.87 | 81.04$\pm$ 6.28 |

### J.3 GNN vs DGCN

As mentioned earlier, if the server has knowledge of the global graph, FedStruct can operate with any underlying GNN model. However, in Fig. 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 a standard GNN (GraphSage) for a 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 a heavily semi-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 a decoupled GCN to effectively tackle the semi-supervised learning scenarios.
Moreover, knowledge of the global graph edges enables the use of NSFs such as Node2Vec which, as seen in Fig. 6, sometimes enhances the performance compared to Hop2Vec.

Figure: Figure 6: Accuracy vs fraction of training nodes with labels for FedStruct with underlying decoupled GCN and underlying standard GNN (GraphSage) on the Amazon Photo dataset with K-means partitioning.

### J.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 (there is offline phase as in Appendix H) and clients only communicate with the server.

**Table 10: Communication Complexity of FedStruct when the Server has Knowledge of the Global Graph.**
| Data | before training | training |
| --- | --- | --- |
| FedStruct | 0 | $\mathcal{O}(E\cdot K\cdot|\boldsymbol{\theta}|+E\cdot n\cdot d\cdot|<br>\boldsymbol{\theta}|)$ |
| FedStruct + Hop2Vec | 0 | $\mathcal{O}(E\cdot K\cdot|\boldsymbol{\theta}|+E\cdot n\cdot d\cdot|<br>\boldsymbol{\theta}|+E\cdot K\cdot n\cdot d+E\cdot n^{2}\cdot d^{2})$ |

During the training, in each training round, each client collects $\boldsymbol{\theta}$ and returns $\nabla_{\boldsymbol{\theta}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})$ to the server, totaling a communication of $2E\cdot K\cdot|\boldsymbol{\theta}|$ parameters during the training.
This is consistent across all versions of FedStruct.
Additionally, the server sends $\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}$, $\forall v\in\tilde{\mathcal{V}}_{i}$, and $\{\frac{\partial{\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}}}{\partial{\boldsymbol{
\theta}_{\mathsf{s}}}},\forall v\in\tilde{\mathcal{V}}_{i}\}$ to each client, adding up to $E\cdot n\cdot d(|\boldsymbol{\theta}|+1)$ parameters.
The dominant term of the complexity is $E\cdot n\cdot d\cdot|\boldsymbol{\theta}|$, 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 $\{\frac{\partial{\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}}}{\partial{\boldsymbol{
s}_{q}}},\forall v\in\tilde{\mathcal{V}}_{i},q\in\mathcal{V}\}$ by client $i$, constituting $E\cdot n^{2}\cdot d^{2}$ parameters, and sending $\nabla_{\boldsymbol{S}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})$ to the server, constituting $E\cdot K\cdot n\cdot d$ parameters.
In practical scenarios with large graphs, $E\cdot n^{2}\cdot d^{2}$ is the dominant term out of the two.

With Hop2Vec, the dominant complexity term is on the order of $n^{2}$, 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_{\mathsf{s}}$-hop neighbors.
Hence, many of the values $\{\frac{\partial{\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}}}{\partial{\boldsymbol{
s}_{q}}},\forall v\in\tilde{\mathcal{V}}_{i},q\in\mathcal{V}\}$ are zero and do not need to be communicated.
Assuming an average node degree $\bar{d}$ and $L_{\mathsf{s}}$ layers, for which each node has access to $\bar{d}^{L_{\mathsf{s}}}$ nodes, the complexity of FedStruct with Hop2Vec is on the order of $\min\{n\cdot\bar{d}^{L_{\mathsf{s}}},n^{2}\}$.
For small average degree $\bar{d}$ and $L_{\mathsf{s}}$, the complexity can therefore be reduced significantly.
The communication complexity is reported in Table 10.

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: As in weaknesses.
soundness: 2
strengths: 1. Subgraph FL with inter-connections is an important topic.
2. Completing the missing L-hop features by learning a L-hop node structure embedding is an interesting idea.
3. Experiments show the performance.
summary: The paper works on subgraph FL for node classification, where inter-connections between different clients is important. 

It 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.
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.
2. FedSage+ and FedGCN can outperform FedStruct.
3. 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.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 2
questions: See the weakness.
soundness: 3
strengths: 1)	This paper studies a significant and interesting problem, and the method can be used in a wide range of real-world applications. 
2)	The paper is overall well motivated. The proposed model is reasonable and sound. Theoretical analysis is performed.
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.
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.

2) 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.

3) 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.

4) The formula following (1) is missing a comma; please check for similar issues throughout the paper.

5) 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.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 4
questions: see weaknesses.

If the first questions can be well explained, the rating should be higher.
soundness: 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. 
2. Utilizing pruning skills decrease the calculation complexity and communication costs.
3. Well written and well formulated problem.
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.
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.

2. **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.

Meta-review: This paper introduces FedStruct, a novel framework for federated learning (FL) on graph-structured data distributed across multiple clients. It focuses on the subgraph FL setting, where interconnections between clients play a significant role. The primary innovation lies in leveraging explicit global graph structure information to capture inter-node dependencies without sharing sensitive node features or embeddings, thereby addressing critical privacy concerns.

The problem setting—FL on interconnected subgraphs—is significant, with numerous real-world applications, such as transaction networks and social graphs. The proposed method enhances privacy preservation by eliminating the need to share sensitive node features or embeddings, distinguishing itself from existing approaches. FedStruct was evaluated on six diverse datasets, demonstrating its effectiveness.

However, gaps remain between theory and practice. The proposed privacy guarantees rely on theoretical assumptions and mechanisms like homomorphic encryption, which are not fully implemented or demonstrated. Additionally, the experimental evaluation could be strengthened by incorporating a more comprehensive hyperparameter analysis and testing on more realistic FL scenarios to better assess its applicability.

Overall, the paper has notable strengths, particularly in addressing an important problem and demonstrating promising results, the unresolved privacy concerns and limited experimental rigor slightly outweigh the merits. Therefore, I recommend acceptance, with a note to the authors to address these concerns in the final version.

Decision: Accept (Poster)