Federated Graph Learning with Graphless Clients
Authors: Xingbo Fu
Song Wang
Yushun Dong
Binchi Zhang
Chen Chen
Jundong Li
Venue: Accepted by TMLR ()

Abstract: Federated graph learning is tasked with training machine learning models, such as Graph Neural Networks (GNNs), for multiple clients, each with its own graph data. Existing methods usually assume that each client has both node features and graph structure of its graph data. In real-world scenarios, however, there exist federated learning systems where only a part of the clients have such data while other clients graphless clients may only have features. This naturally leads to a novel problem in federated graph learning: how to jointly train a model over distributed graph data with graphless clients? To tackle this problem, we propose a novel Federated Graph Structure Learning (FedGSL) framework in this paper. In FedGSL, we devise a local graph learner on each graphless client which learns the local graph structure with the structure knowledge transferred from other clients. To enable structure knowledge transfer, we design a GNN model and a feature encoder on each client. During local training, the feature encoder retains the local graph structure knowledge together with the GNN model via knowledge distillation, and the structure knowledge is transferred among clients in global update. Our extensive experiments on five real-world graph datasets demonstrate the superiority of FedGSL over other five federated learning approaches.

Published in Transactions on Machine Learning Research (10/2024)
Federated Graph Learning with Graphless Clients
Xingbo Fu
af3ao edu
Deportment of Electrical and Computer Engineering University of Virginia
Song Wang
swSue@virginia.com edu
Department Electrical and Computer Engineering University of Virginia
Yushun Dong
yd6eb edu
Department of Electricnl and Computer Engineering University of Virginia
Binchi Zhang
epb6gus@virginia.. edu
Depariment of Electrical and Computer Engineering University of Virginia
Chen Chen
zriufiduvirgiinie edu
Department of Computer Science University of Virginia
Jundong Li
Department of Electrical and Computer Engineering Universily of Virginia
Reviewed on OpenReview:
https: http:///ppeeeeeeeee//m net/ forun? id= mVApDeDfyR
Abstract
Federated Graph Learning (FGL) is tasked with training machine learning models, such as Graph Neural Networks (GNNs), for multiple clients, each with its own graph data. Existing methods usually assume that each client has both node features and graph structure of its graph data. In real-world scenarios, however, there exist federated systems where only a part of the clients have such data while other clients (i.c. graphless clients) may only have node features. This naturally leads to a novel problem in FGL: how to jointly Iruin model over distributed graph data with graphless clients? In this paper, we propose a novel framework FedGLS to tackle the problem FGL with graphless clients. In FedGLS, we devise local graph learner each graphless client which learns the local graph structure with the structure knowledge transferred from other clients. To enable structure knowledge transfer, design GNN model and feature encoder each client. During local training, the feature encoder retains the local graph structure knowledge together with the GNN model via knowledge distillation, and the structure knowledge is transferred among clients in global update. Our extensive experiments demonstrate the superiority of the proposed FedGLS over five baselines.
1 Introduction
Recent years have witnessed a growing development of graph-based applications a wide range of high- impact domains. As powerful deep learning tool for graph-based applications, Graph Neural Networks (GNNs) exploit abundant information inherent in graphs (Wu et al. 2020] and show superior performance
in different domains, such node classification (Fu et al. 2023 He et al. 2022 and link prediction (Tan

---

Published in Transactions on Machine Learning Research (10/2024)
C Company
C
B
Hospital Hospital
Hospital
Hospital
An example of a healthcare system including four hospitals. In this example, Hospital A and Hospital D have their local datasets of patients (node features) and co-staying information (links) among them. In the meantime, Hospital B and Hospital C only have their local datasets of patients (node features). The four hospitals aim to jointly train model for predicting whether a patient is at high risk of contracting contagious disease, orchestrated by a third-party company over their local datasets while the company cannot directly access their private datasets.
Figure 1:
ct al. 2023a Zhang& & Chen 2018 Traditionally, GNNs are trained over graph data stored on a single machine. In the real world, however, multiple data owners (i.e., clients) may have their own graph data and hope to jointly train GNNs over their graph data. The challenge in this scenario is that the graph data is often not allowed to be collected from different places to single server for training due to the emphasis on data security and user privacy (Voigt & Von dem Bussche 2017 Wang et al.) 2024b). Considering a group of hospitals, for instance, each of them has its local dataset of patients. These hospitals hope to collaboratively train GNNs for patient classification tasks (e.g., predicting whether a patient at high risk of contracting a contagious discase) while keeping their private patient data locally due to strict privacy policies and commercial competition.
To tackle the above challenge, Federated Learning (FL) MMMMaan et al.) 2017 enables collaborative training among clients over their private graph data orchestrated by central server. Typically, FL can be categorized into horizontal and vertical FL based on how data is distributed among clients (Yang et al., 2019). This study focuses on horizontal FL where distributed datasets share the same feature space. During cach training round, the selected clients receive the global model from the central server and perform local updates over their local graph data. The central server aggregates the updated local models from the clients and computes the new global model for the next training round. Numerous studies have been proposed to improve FL performance over graph data by reconstructing cross-client information (Zhang et al. 2021b aligning overlapping instances (Peng et al. 2021 Zhou et al. 2022 and mitigaling data heterogeneity (Xie et al.
2021
Tan et al. 2023b Fu et al. 2024).
The above methods rely on a fundamental assumption that each client has graph structure information its local graph data. In the real world, however, this assumption may not be feasible for all the clients. Instead, there may be a part of clients only having local node features, whereas other clients have both node features and edge information. To illustrate this scenario in practice, we provide a real-world example as follows. More practical examples can be found in Appendix A
Motivating example. Considering the aforementioned example of a healthcare system as shown in Figure we may construct local graphs in each hospital by laking patient demographics as node features and co-staying in a ward as edges. In the real world, however, some hospitals may not record the co-staying information and cannot construct patient graphs. As a result, these hospitals are unable to dircctly train GNNs to predict whether a patient at high risk of contracting contagious discase in a federated manner. If we instead train a machine learning model only based on patient. features, the classification performance will
2

---

Published in Transactions on Machine Learning Research (10/2024)
be unsatisfactory because we disregard the important co-staying information between patients, which significantly determine the risk of contracting a contagious disease for a patient.
The above scenario brings us a novel problem in the federated setting: how to jointly train a GNN model for the classification task from isolated graphs distributed in multiple clients while some clients only have node features? In this paper, we name such clients as graphless clients. Since directly training GNNs is obviously infeasible in this setting, collaboratively training Non-GNN-based models such as multi-layer perceptrons (MLPs) and Support Vector Machines (SVMs) is plausible solution to the above problem. However, number of experiments in prior works have demonstrated that the Non-GNN-basse models are typically less accurate than GNNs for the classification task (Franceschi et al., 2019 Zhang et al. 2022). Another intuitive method is to let a graphless client construct graph structure based on the similarity of the features (e.g., using kNN (Gidaris & Komodakis 2019)) and jointly train GNNs together with other clients. A disadvantage of this method is that the generated graphs are only dependent on node features and are not suitable for node classification (Franceschi et al., 2019 Liu et al. 2022). To overcome the disadvantage, is natural let the graphless clients produce graph structures with the structure knowledge of other clients. However, structure knowledge transfer and utilization in federated manner are still challenging and unexplored.
In this study, we propose a novel framework FedGLS to handle FGL with graphless clients. FedGLS aims to solve two key challenges of utilizing structure knowledge in this scenario: 1) how to transfer structure knowledge among clients; and 2) how to utilize the transferred knowledge on graphless clients? In FedGLS, we first design two modules- a GNN model and a feature encoder on each client. particular, we deploy a third module a local graph learner on each graphless client. The GNN model learns node embeddings over the local graph and the feature encoder approximates the output of the GNN model via knowledge distillation (Hinton et al. 2015). Therefore, the GNN model and the feature encoder together retain structure knowledge on each client. The central server collects the local parameters of the two modules from the clients and gets the global parameters. In this way, FedGLS transfers structure knowledge among clients. The local graph learner utilizes the structure knowledge by maximizing the consistency between the output of the global GNN model and leature encoder on each graphless client with a contrastive loss. We conduct exlensive experiments over five datasets, and the results show that FedGLS outperforms other baselines.
Our contributions can be summarized follows.
Problem Formulation. We propose novel research problem of FGL with graphless clients and provide the formal definition of the proposed problem.
Algorithm Design. We propose FedGLS to tackle the proposed problem. We devise scheme for transferring structure knowledge among clients in FedGLS by letting feature encoder imitate the node embeddings from a GNN model. The scheme enables a graph learner on each graphless client to learn its local graph structure with the structure knowledge transferred from other clients.
Experimental Evaluations. We conduct extensive experiments on real-world dalasets, and the results validate the superiority of our proposed FedGLS against five baselines. Our implementation of FedGLS is available in the supplementary materials.
2 Related Work
2.1 Federated Learning
FL [McMahan al. 2017] enables participants (i.e., clients) to jointly train model under the coordination of central server without sharing their private data. One key problem that FL concerns is statistical heterogeneity: the data across clients are likely to be non-III (Li et al. 2020a Wu et al., 2024a). When each client updates its local model based on its local dataset, its local objective may be far from the global objective. Thus, the averaged global model is away from the global optima (Wang et al.) 2024a Wu et al. 2024b, Wang et al. 2023) and influences the convergence of FL. To overcome the performance degradation of FedAvg when data at each client are statistically heterogeneous (non-IID), number of recent studies have been proposed from different aspects. Typically, these studies can be categorized into single global
3

---

Published in Transactions on Machine Learning Research (10/2024)
model-based methods and personalized model-based methods. Single global model-based methods aim to train global model for all clients. For instance, FedProx (Li et al. 2020bb adds a proximal term to the local training loss to keep updated parameters close to the global model. SCAFFOLD (Karimireddy et al. 2020) customizes the gradient updates of personalized models to mitigate client drifts between local models and the global model. Moon (Li et al. 2021) uses a contrast ive loss to increase the distance between the current and previous local models. Personalized model-based mothods instead enable each client to train a personalized model to mitigate the impact of data heterogeneity. For example, pFedHNN (Shamsian et al. trains central hypernetwork to output unique personal model for each client. FedProto (Tan et al. utilize the prototypes to regularize the local model training.
2021
2022
and FedProc Muu et al. 2023)
2.2
Federated Graph Learning
Following many well-designed FL methods for Euclidean data (e.g., images). number of recent studies have begun tackling challenges in FL on graph data (Fu et al. 2022) to achieve better performance downstream tasks. One specific problem in FL, on graph data is missing neighboring information when each client only owns a part of the original graph. The recent proposed methods recover missing neighboring information by transmitting intermediate result (Zhang et al. 2021a] and generating missing noighbors (Zhang et al.) 2021b). Another interesting issue in FL on graphs is aligning overlapping instances across clients. This issue happens FI. with heterogeneous graphs (Peng et al., (022)) and vertical FL on graphs (Zhou et a 2022). In the meantime, some recent studies focus on the unique challenges caused by data heterogeneity in FGL. For example, GCFL (Xie et al.) 2021 enables clients with similar graph structure properties to share model parameters. FedStar (Tan et al. 2023b) designs structure encoder to share structure knowledge among clients for graph classification. FedLit (Xie et al. 2023 mitigates the impact of link-type heterogeneily underlying homogeneous graphs in FGL via an EM-based clustering algorithm. Different from the aforementioned problems where the clients own structured data (i.e., graphs), our work aims to deal with the setting where a part of the clients do not have structure information.
3 Problem Statement
In this section, we first present basic concepts in GNNs and FL. Then we propose a novel problem sctting of FGL with graphless clients.
3.1 Preliminaries
Before formally presenting the formulation of the novel problem, we first introduce the concepts of GNNs and FGL.
Notations. We use bold uppercase letters (e.g., A) to represent matrices. For any matrix, e.g., Z, we use the corresponding bold lowercase letters z, to denote its i-th row vector. We use letters in calligraphy font (o.g., V) to denote scts. |V] denotes the cardinality of set V.
u2, Graph Neural Networks. We use G (V,E, X) to denote an attributed graph, where V = [2,,,2 vp is the set of n |V] nodes, E is the edge set, and X E gaxd is the node feature matrix. d is the number of node features. The edges describe the relations between nodes and can also be represented by an adjacency matrix A E Raxa_ A GNN model ʃ parameterized by = (0z, 0z) learns the node embeddings Raxd based on X and A
(1) Here d' is the embedding dimension, and 02 represents parameters of the encoder part in f to obtain the node embedding Z. For the node classification task, we use Z to obtain the prediction fZ; E Rexp where p is the number of classes, and 0g represents parameters of the predictor in f. Given the label set Vr = (vI, 32.- ... , where yi denotes the label of node v; E Vr. = {Ul, U., ... v.), u.,), the objective is to minimize the difference between Y and Vr.
Z fX, A;0.).
min L(0)
Σ 1()..)))
(2)
[VLl
4

---

Published in Transactions on Machine Learning Research (10/2024)
where -(.,)) is the cross-cntropy loss.
Federated Graph Learning. In federated system with K clients C = {elt), .. c( C owns private graph g(k) ( x and n | The goal of the clients is to collaboratively train a GNN model f parameterized by 0 orchestrated by central server while keeping the private datascts locally. Specifically, the objective is to solve
,.kk.,,,k,,,,, each client
K
arg F(0)
Σ (0),
n
where (0) = p Enevy e Mi). and N Ex= (*)) is the total number of nodes around all the
clients. FedAvg (McMahan et al. 2017 is one of generic federated optimization methods, which can be directly applied to FL on graph data. Typically, during each training round, client c(*) updates its local GNN parameters g(*) over its private graph G(k) via SGD for number of epochs with initialization of the parameters set to the global GNN parameters 0. At the end of the round, the server collects (0(*) k=1 from clients and computes the new global GNN paramoters by
K (k)
8(K)
(4)
N
The new global GNN parameters are used for local training in the next round.
3.2 Problem Definition
The clients jointly training a GNN model require structure information (e.g., A (k)) of a private graph g(l)) known by each client c(&), However, this requirement may not be feasible for the clients and some of the clients only have its local node feature matrix (*)) As a result, we cannot obtain GNN model trained directly the distributed graph data all the clients.
Based on the aforementioned challenges, we propose a novel problem setting in FGL. We provide a formal definition of the problem as follows.
PROBLEM 1. Federated graph lcarning with graphless clients: Given a set of K clients C = [K and 1 < M < K, each cliend c(k) E c {c(k)) 1k=1 owns the node fentures x(k) in ils privale graph G(k) with the complete structure information (e.g., A (1)) while each graphless client ((k) E E = | only owns its local node features x(k), The goal of the whole clients C is to collaboratively train model for the node classification task without sharing their graph data.
4 Methodology
In this section, we present the proposed framework FedGLS. The goal of FedGLS is to let graphless clients learn local graph structures with the structure knowledge transferred from other clients. To achieve this goal, FedGLS solves the following two challenges: 1) how to transfer structure knowledge among clients; and 2) how to utilize the transferred structure knowledge on graphless clients. To handle the first challenge, we design GNN model and feature encoder each client. The feature encoder aims to retain structure knowledge together with the GNN model via knowledge distillation. To utilize the transferred structure knowledge, we design a graph learner on each graphless client. This module generates local graph structure and learns the structure knowledge in the GNN model and the feature encoder via a contrastive loss.
4.1 Framework Overview
Figure 2 illustrates an overview of FedGLS. Tt consists of two training stages: local training on the clients and global update on the central server.
Local Training. On each client, GNN model generates node embeddings with respect to node features and local graph structure. The goal of the feature encoder is to retain structure knowledge together with the
5

---

Published in Transactions on Machine Learning Research (10/2024)
Local Training
nx
n
Central Server
Global Update
h-1
@( (b(4)
0,
0.4
Feature Encoder (g)))
Feature Encoder h h(
Node embeddings H
Labels y/2
Node embeddings H(K)
Labels y
Node features (())
Node features ((R)
1 K
Graph learner ((ss(k))
[k CL
CE
KD
GNN model (
GNN model ((
Original graph G( ((())
Node embeddings
Predictions Pich
Generated graph g(t) (x())
Node embeddings 2
Predictions g(8)
Z(R)
Client c(0 C1
Client (k0 C2
Figure 2: An overview of the proposed FedGLS.
GNN model. It approximates the output (i.e., node embeddings) of the GNN model using the knowledge learned by the GNN model. On each graphless client, graph learner generates local graph structure and learns the structure knowledge via a contrastive loss. Finally, the well-trained graph learner produces local graph structure and the GNN model learns more expressive node embeddings.
Global Update. After local training, the central server gathers the local parameters of the GNN model and the feature encoder from the clients. Then it computes the new global parameters following FodAvg and broadcasts them to the clients for local training in the next round.
4.2 Local Training
As introduced above, we deploy GNN model and feature encoder on each client. For each graphless client, an extra graph learner is deployed to generate the graph structure. In this subsection, we will introduce the local update the three modules during local training on the clients.
For each graphless client ((k) E C2 a graph learner g produces an adjacency matrix S(A) E R2 (x)) respect to the node feature matrix (k) Formally, we formulate the graph learner as
with
s = (w) (w))
(5)
where (k) denotes the parameters g. Gen(.) denotes a graph generalor which produces a matrix ((k) B (1) based on the node features. Typically, we instantiate the graph generator as an MLP encoder an atlentive encoder followed by a cosine similarity function. Ω(-) is non-parametric adjacency processor
E
which conducts post-processing on ((k) and outputs ((a) Generally, it includes four main operations: sparsification, activation, symmetrization, and normalization (Liu et al. (022). The adjacency processor 2(-) ensures that ((k) is normalized symmetric sparse adjacency matrix with non-negative values. For detailed descriptions about designing graph generators and adjacency processors in the graph learner, readers can refer to Appendix
Then the GNN model on each graphless client c(k) E C2 produces node embeddings with the generated adjacency matrix (() and the node feature matrix x (k) the input. For each client (()) C1, the client

---

Published in Transactions on Machine Learning Research (10/2024)
instead uses the original adjacency matrix A (k), Specifically, the GNN model produces the node embeddings (d)) by
(h) = f(x(1) (())))))))))
(6)
for each client el E C2; otherwise, ((k) will be replaced by the original adjacency matrix A (R) 000) is the parameters in f. In this paper, we instantiate the GNN model f as a GCN.
In the meantime, the feature encoder h similarly generates the node representations H() but it is only basod the node feature matrix X (R)
H (k) = h(X (H)).
(7)
where @lh) denotes the parameters in h. In this paper, we instantiate the feature encoder as an MLP.
Optimizing w(+), For a graphless client clk) E C2, its well-trained graph learner 9 with its parameters (1) is supposed to learn structure knowledge transferred from other clients. Typically, produces the adjacency matrix ((A) so that the node embeddings (*) produced by the GNN model based on ( and x are consistent with (*) produced by the feature encoder. To achieve this, we optimize the local graph learner by maximizing the agreement with a contrastive loss (e.g., NT-Xent (Chen et al., 2020ab). Specifically, we consider the embedding pair z! 2(() and In!")) of node 12 E V(k) as positive pair. In contrast, the embedding 2 (k) and the embedding of any other node e/j E ((A) (either in (k) or (()) compose negative pair. Our goal is to decrease the distance between positive pairs and increase the distance between negative pairs. Concretely, we formalize it as the contrastive loss as follows:
ssmma (6) h 1/T
R H (b)
= log
(8)
sim
+ sim(z (6) 22 2//)//]
where sim(..) is the cosine similarity function, and t is a temperature parameter. The contrastive loss (k) encourages 2; not to be too close to other node embeddings and therefore alleviate the over-smoothing issue in GNNs.
In the end, the local graph learner is optimized by minimizing the total contrastive loss:
min w(
CL
& (Z (()).
(9)
(F)
Optimizing ((k), The GNN model f aims to learn expressive node emboddings and therefore predicts the labels of unlabeled nodes. To optimize the parameters (bk) in I on each client ((k) E C, we minimize the classification loss over all labeled nodes in (k) by
min C(k) 6(4)
Σ CE()..))
(10)
D
where CE(:,) denotes the cross-entropy loss.
Optimizing (4)), The goal of the feature encoder to produce (K) without structure information which is consistent with (k) and therefore enables the training of the graph learner. The key challenge for training graph learners is to enforce closeness between H and (K), To tackle this issue, we resort to knowledge distillation (Hinoon et al., 2015). The intuition of knowledge distillation is to let a student model learn with the knowledge (c.g., predictions) from teacher model. Typically, the student model is ablc to produce comparable oulputs with the teacher model. In FedGLS, we choose to disuill knowledge from the GNN model to the feature encoder. Then the feature encoder (e.g., an MLP) achieves comparable performance with a GNN via learning the knowledge transferred from the GNN only based on the features (Zhang et al., 2022). In FedGLS, the parameters (()) of a feature encoder on each client c(k) E C are updated by approximating the knowledge (i.e., the node embeddings (*)) from its GNN model. Specifically, the feature encoder

---

Published in Transactions on Machine Learning Research (10/2024)
client c(k) C is optimized by minimizing the discrepancy between h. (8) and (k) 2; distillation (Hinton et al. 2015) as follows:
for us V(k) via knowledge
Σ KL(f(Z min
LDD
(11)
a(f)
where (L(-II-) is to compute the Kullback-Leiblee divergence (KL-divergence).
4.3 Global Update
During global update, the central server gathers the local ((k) and σf from the clients. Then it computes the new global 9 and ø with FedAvg. More specifically, the new global and ø for the next round are calculated by
(k) B(R)
(k)
(0, - Σ N
N ((N))
(12)
El
4.4 Overall Algorithm
The overall federated training algorithm of FedGLS is shown in Algorithm
I During each round, the central server sends global 0 and ø to the selected clients, For each client ((k) E C2, the graph learner first produces the adjacency matrix ((k) The GNN model f takes node features (k) and the generated adjacency matrix ((k) (Tor clients in Ci, they use their original adjacency matrices A (R) instead) to get node representations (A)), Then the feature encoder h computes corresponding node embeddings (()) only with node features (() as input. The parameters (k) in g are updated by minimizing the discrepancy between ( and (k)
using Eq. 9 Afterward, each client ((k) E updates the parameters ((k) of f via supervised learning using Eq. and updates the parameters ((k) of with the knowledge distilled from the GNN model supervision information using Eq. 11 Finally, the central server collects the updated g(k) and (i(k) from the clients to get the new global 0 and ó using Eq. 12 for local training in the next round. We provide complexity analysis Appendix
5 Experiments
We conduct extensive experiments over five real-world datasets to verify the superiority of the proposed FedGLS. In particular, aim to answer the following questions.
RQI: How does FedGLS perform compared with other state-of-the-arl baselines?
RQ2: How well can FedGLS stable under different local epochs and various graphless client ratios?
5.1
Experiment Setup
5.1.1
Datasets
We synthesize the distributed graph data based on five common real-world datasets, i.e., Cora (een et al. 2008), CiteSocr (Sen et al., 2008), PubMed (Sen al. 2008), Flickr (Zeng et al. 2020). and ogbn-arxiv (Hu)
et al. 2020). Following the data partition strategy in previous studies (Huang al. 2023 Zhang et al. 2021b), synthesize the distributed graph data. by splitting each dataset into multiple communities via the Louvain algorithm (Blondel et al. 2008); each community is regarded as entire graph in client. We summarize the statistics and basic information about the datasets in Appendix D
In our experiments, we randomly select half clients as graphless clients. Following the setting in (Zhang ct al. 2021b), we randomly select nodes on cach client and let 60% for training, 20% for validation, and the remaining for testing. We report the average accuracy for node classification over the clients for five random repetitions.

---

Published in Transactions on Machine Learning Research (10/2024)
Algorithm The detailed algorithm of FedGLS.
Input: global parameters learning rate a, 9,7, local epoch E
Output:
1:
repeat
Server selects subset clients C, from C, then broadcasts and & to 3: for client (()) E C. do
g(k) &- 0, ((())
Ø if c()) E C2 then
5:
6:
// Update graph learner
n(1)
Compute ((K) (oll))
Σ (1((")
7:
w(th (h) - wis Cod (w!tt)
9:
end if
for 1,2.... E do
11:
// Update GNN classifier Compute (B(N))
12:
Σ CB(F,.))
( t g aV o(N (
13:
14:
// Update feature encoder
Compute ((k) (
E KL(S(2))) 0! "0
15:
MEV((
1 - t - vV elk) (D(())
(k)
16:
end for Client (!)) sends O(A), (A)) back to server
18:
end for Server updates 0 and via 0 +-
20:
Σ
(4))
N
p(a)
p(h)
+-
Σ
(k)
N pb(A))
cliige
c(F)ee
21:
until training stop
5.1.2
Basclines
Since FedGLS is proposed to deal with a novel problem setting in FGL with graphless clients, most of the existing frameworks cannot be directly adopted without any preprocessing. Considering this, we first design the following two baselines.
Fed-MLP: the clients in C jointly train an MLP model;
Fed-GNNMLP: the clients in C1 collaboratively train GNN model while the clients in C2 collab- oralively train an MLP model;
In the meantime, include the following bascline which can be adopted to handle the heterogencous model architecture setting.
FedProto Taa et al. 2022): the local models on the clients in C are GNNs and those the clients in C2 are MLPs, then FedProto performs collaborative training by aggregating prototypes. A prototype is the mean value of the embeddings of instances in a class.
Furthermore, also consider the following two baselines with preprocessing.
Local-GNNK: first performs the kNN operation on the graphless clients in C2, then each client in C individually trains GNN model over its local data without any communication among the clients;
Fed-GNNk: first performs the kNN operation on the graphless clients in C2, then jointly trains GNN model over the clients in C.
9

---

Published in Transactions on Machine Learning Research (10/2024)
Table Node classification performance (Accuracy: Std) over different datasets. Bold and underlined values indicate best and second-best mean performances, respectively.
Datasets
Fed-MLP
Fed-GNNMLP
FedProto
Local-GNNk
Fed-GNNk
FedGLS
Fed-GNNN
0.6141
0.7448
0.8089
0.8002
0.7891
0.8180
0.8238
Cora
(+000599)
(+000104)
(40.0078)
(+000267)
(+0.0269)
(=0.0281)
(+-0.0109)
0.7253
0.7521
0.7876
0.7834
0.7884
0.8058
0.7951
CiteSeer
(+0.0169)
(#0.0279)
(+0.0184)
(=0.0262)
(+0.0131)
(=0.0171)
(+0.0273)
0.8398
0.8413
0.8341
0.8328
0.8426
0.8491
0.8629
PubMed
(=0.0044)
(+0.0088)
(#0.0097)
(=0.0098)
(=0.0128)
(=0.0070)
(+0.0017)
0.4649
0.4868
0.4720
0.4844
0.4796
0.4937
0.5014
Flickr
(+0.0031)
(+0.0029)
(+0.0044)
(+0.0058)
(+0.0032)
(+0.0048)
(+0.0024)
0.4495
0.4652
0.4685
0.4573
0.4761
0.4872
0.5386
ogbn-arxiv
(+0.0065)
(+0.0049)
(+0.0037)
(+0.0051)
(+0.0014)
(+000052)
(+000000)
the meantime, we include Fed-GNN which uses the real graph structures on the graphless clients in C2. Thooretically, Fed-GNN should perform better than FedGLS and the aforementioned basclines since Fed-GNN utilizes more information (i.e., graph structures on the clients in C2).
5.1.3 Parameter Settings
We implement a two-layer GCN and a two-layer MLP as the GNN model and the feature encoder FedGLS, respectively. We apply the same model archilectures to the models used in the baselines. In FedGLS, we choose a two-layer attentive encoder as the graph generator in the graph learner. The hidden size of each layer in the two models is 16. For all the aforementioned models, optimizer. The learning rates and 8 are set to 0.01 in the GNN model and the feature encoder and 7 is set to 0.001 in the graph learner. The temperature in the contrastive loss is set to 0.2. The number of local epoch E' is set to 5. The number of rounds is set to 100 for Cora and CiteSeer, 200 for PubMed, 300 for Flickr, and 2,000 for ogbn-arxiv. All the clients are sampled during each round.
the Adam (Kingmaa & Ba 2015)
5.2 Effectiveness Evaluation
In this subsection, we evaluate the performance of FedGLS over the five datasets against the baselines to answer RQL. Specifically, we compare FedGLS with the five baselines on the node classification accuracy and convergence speed.
5.2.1 Classification Performance
We first evaluate the node classification accuracy of different approaches over the five datasets. We conduct all the experiments five times and report the average accuracy with standard deviation in Table [ As for the baselines without preprocessing, Fed-GNNMLP outperforms Fed-MLP over all the datasets. It is because Fed-GNNMLP utilizes structure information on the clients in C1. However, there is still a huge performance gap between Fed-GNNMI.P and FedGLS since training MLPs based solely on node features on graphless clients by Fed-GNNMLP cannot achieve comparable performance with FedGLS using structure information. Although FedProto is personalized approach which enables each client train a local model with global prototypes a constraint, it does not always perform better than Fed-MLP and Fed-GNNMLP (e.g., PubMed and Flickr). Since graphless clients in FedProto use MIPs as the backbonc model and other clients use GNNs, they may learn distinct protolypes with their different backbone models. As for the baselines with preprocessing, Fed-GNNk fails to perform better than Be on Cora and Flickr. In the meantime, we can observe significant performance degradation of Fod-GNNk compared with Fed-GNN. It indicates that constructing graph structures via kNN is not suitable for generating graphs in the real world. In the end, we observe that FedGTS consistently achieves the highest classification accuracy. Compared with Ped-GNNK,
10

---

Published in Transactions on Machine Learning Research (10/2024)
Fed-GNNK FedGLS
1.75
0.475
FedGLS
1.50
1.65
0.450
1.25
0.6
Training loss
1.60
Test accuracy
0.425
Training
1.00
0.5
1.55
0.400
0.75
1.50-
0.375
0.50
0.3
0.25
0.2
Fed-GNNK
1.45
0.350
Fed-GNNk FedGLS
FedGLS
0.00
0.1
1.40
0.325
20
40
60
100
20
40
60
100
100 150 200 250 360 Rounds
100 150 200 250 300 Rounds
Rounds
Rounds
(a) Training loss of Cora
(b) Test accuracy of Cora
(c) Training loss of Flickr
(d) Test accuracy of Flickr
Figure 3: Result for convergence speeds of FedGLS and Fod-GNNk: (a) training loss curve and (b) test accuracy curve Cora; (c) training loss curve and (d) test accuracy curve Flickr.
FedGLS is able to deliver better prediction performance, much closer to Fed-GNN (even a little bit higher on CiteSeer). is because the graph learner produces well-learned graph structures on graphless clients which benefit training of the GNN model.
5.2.2 Convergence Speed
We then compare convergence speeds of FodGLS with the best bascline Fed-GNNk. We present the curves of training loss and lest accuracy during the training process on Cora and Flickr in Figure 3 From the results, we observe that the training loss of FedGLS decreases significantly faster than that of Fed-GNNk and the test accuracy of FedGLS reaches relatively high values with fewer rounds than Fed-GNNk on both datasets. According to the observation, we can conclude that FedGLS converges faster than Fed-GNNk. This because the GNN model in FedGLS trained over adaptive graphs whose adjacency matrices are generated by graph learners instead of simply produced by kNN in Fed-GNNk. The graph learners on graphless clients learn more suitable graph structures for the node classification task by learning structure knowledge transferred from other clients.
Table 2: Node classification performance (Accuracy) under different local epochs on Citescer and PubMed dataset. Bold and underlined values indicate best and second-best mean performances, respectively.
Datasets
Epochs
Fed-MLP
Fed-GNNk
FedGLS
0.7203
0.7876
0.8017
CiteSeer
0.7253
0.7884
0.8058
10
0.7311
0.7859
0.8015
0.8406
0.8467
0.8477
PubMed
0.8398
0.8426
0.8491
10
0.8354
0.8455
0.8493
5.3
Sensitivity Study
In this subsection, we conduct sensitivity studies to answer RQ2. Specifically, we evaluate the performance of FedGLS under different local epochs and graphless client ratios.
5.3.1 Local Epochs
The main experiments are conducted with the local epoch E 5. In this part, we set the local epoch and 10 and report. the average accuracy of Fed-MLP, Fed-GNNK, and FedGLS. Table 2 shows the results
11

---

Published in Transactions on Machine Learning Research (10/2024)
Table 3: Node classification performance (Accuracy) under different graphless client ratios on PubMed and Flickr datasct. Bold and underlined values indicate best and sccond-best mean performances, respectively.
Datasets
C1I: |C2l
Fed-MLPP
Fod-GNNk
FedGI.
12:4
0.8398
0.8465
0.8527
PubMed
8:8
0.8398
0.8426
0.8491
4:12
0.8398
0.8351
0.8422
12:8
0.4649
0.4831
0.4982
Flickr
10:10
0.4649
0.4796
0.4937
8:12
0.4649
0.4687
0.4790
on CiteSeer and PubMed. From the results, we observe that FedGLS performs stably under different local epochs and has the best utility under all the settings on CiteSeer and PubMed.
5.3.2 Graphless Client Ratios
We also consider varying ratios of graphless clients in C. In this part, we conduct experiments on PubMed and Flickr with different graphless clients. Table shows the results of Fed-MLP, Fed-GNNK, and FedGLS PubMed and Flickr. Note that the performance of Fed-MLP keeps consistent since it does not require structure information for training. From the table, we can observe that FedGLS consistently achieves better utility compared with Fed-GNNk and Fed-MLP. In the meantime, FedGLS and Fed-GNNk show performance degradation when there are more graphless clients because of less structure information in the system. For instance, Fed-GNNK performs worse than Fed-MLP on PubMed when [C]: |C2l = 4: 12.
6 Conclusion
In this paper, study novel problem of FGL with graphless clients. To tackle this problem, propose principled framework FedGTSS which deploys a local graph learner each graphless client to learn graph structures with the structure knowledge transferred from other clients. To enable structure knowledge transfer, we design a GNN model and a feature encoder in FedGLS. They retain structure knowledge together via knowledge distillation and the structure knowledge transferred among clients during global update. Extensive experiments are conducted on five real-world datasets to show the effectiveness of the proposod algorithm FedGLS.
Although this study proposes novel research problem in FGL, there some limitations in the proposed FedGLS. For example, one potential limitation of FedGLS is that it may not recover the underlying graph structures on graphless clients since it produces fixed k neighbors for each node on graphless clients. There- fore, the generated graph structures may not match the unknown real-world structure information. We will work on designing frameworks to obtain graph structures with consistent real-world structure information. In addition, graphless clients with heterogencous graphs may introduce more challenges and are worthy of exploration in the future.
Acknowledgments
This work is supported in part by the National Science Foundation under grants (IIS-2006844, IIS-2144209 IIS 22232297 IIS-2331315 CNS-2154962, BCS-2228534, and CMMI-2411248) and the Commonwealth Cyber Initiative Awards under grants (VV-1Q24-011, VV-1Q25-004).
References
Vincent Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008
12

---

Published in Transactions on Machine Learning Research (10/2024)
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International Conference on Machine Learning, 2020a.
Yu Chen, Lingfei Wu, and Mohammed Zaki. Iterative deep graph learning for graph neural networks: Better and robust node embeddings. In Advances in nearal information processing systems, 2020b.
Luca Franceschi, Mathias Nieport, Massimiliano Pontil, and Xiao Hc. Learning discrete structures for graph neural networks. In ICML, 2019.
Xingbo Fu, Binchi Zhang, Yushun Dong, Chen Chen, and Jundong Li. Federated graph machine learning: A survey of concepts, techniques, and applications. ACM SIGKDD Explortiion Newsletter, 2022.
Xingbo Fu, Chen Chen, Yushun Dong, Anil Vullikanti, Eili Klein, Gregory Madden, and Jundong Li. Spatial- temporal networks for anlibiogram pattern prediction. In 2023 IEEE 11th International Conference Healthcare Informatics, 2023.
Xingbo Fu, Zihan Chen, Binchi Zhang, Chen Chen, and Jundong Li. Federated graph learning with structure proxy alignment. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2024.
Spyros Gidaris and Nikos Komodakis. Generating classification weights with gun denoising autoencoders for few-shot learning. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, 2019.
Yilin He, Chaojie Wang, Hao Zhang, Bo Chen, and Mingyuan Zhou. A variational edge partition model for supervised graph representation learning. Advances in Newral Information Processing Systems, 2022.
Geoffrey Hinton, Oriol Vinyals, Jeff Dean, et al. Distilling the knowledge in a neural network. arXiv preprint arXiv:1503.02533 2015.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. 2020.
Wenke Huang, Guancheng Wan, Mang Ye, and Bo Du. Federated graph semantic and structural learning. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence, 2023.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 2020.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, 2020.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In International Conference on Learning Representations, 2015.
Qinbin Li, Bingsheng He, and Dawn Song. Model-contrastive federated learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2021.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEFE signal processing magazine, 2020a.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogencous networks. In Proceedings of Machine learning and systems, 2020b.
Yixin Liu, Yu Zheng, Daokun Zhang, Hongxu Chen, Hao Peng, and Shirui Pan. Towards unsupervised deep graph structure learning. In Proceedings of the ACM Web Conference, 2022.
13

---

Published in Transactions on Machine Learning Research (10/2024)
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effiien learning of deep networks from decentralized data. In Artificial intelligence and statistics, 2017.
Xutong Mu, Yulong Shen, Ke Cheng, Xucli Geng, Jiaxuan Fu, Tao Zhang, and Zhiwei Zhang. Fedproc: Prototypical contrastive federated learning on non-iid data. Future Generation Computer Systems, 2023.
Hao Peng, Haoran Li, Yangqiu Song, Vincent Zheng, and Jianxin Li. Differentially private federated knowl- edge graphs embedding. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, 2021.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collec- tive classification in network data. Al magazine, 2008.
Aviv Shamsian, Aviv Navon, Ethan Fetaya, and Gal Chechik. Personalized federated learning using hyper- networks. In International Conference on Machine Learning, 2021.
Qiaoyu Tan, Xin Zhang, Ninghao Liu, Daochen Zha, Li Li, Rui Chen, Soo-Hyun Choi, and Xia Hu. Bring your own view: Graph neural networks for link prediction with personalized subgraph selection. In Proceedings of the Sirteenth ACM International Conference on Web Search and Data Mining, 2023a.
Yue Tan, Guodong Long, Lu Liu, Tianyi Zhou, Qinghua Lu, Jing Jiang, and Chengqi Zhang. Fedproto: Federated prototype learning across heterogeneous clients. In Proceedings of the AAAI conference on artificial intelligence, 2022.
Yue Tan, Yixin Liu, Guodong Long, Jing Jiang, Qinghua Lu, and Chengqi Zhang, Federated learning on non-iid graphs via structural knowledge sharing. In Proceedings of the AAAT conference on artificial intelligence, 2023b.
Paul Voigt and Axel Von dem Bussche. The general data protection regulation (gdpr). A Practical Guide, 1st Ed., Cham: Springer International Publishing, 2017.
Jiaqi Wang, Yuzhong Chen, Yuhang Wu, Mahashweta Das, Hao Yang, and Fenglong Ma. Rethinking per- sonalized federated learning with clustering- based dynamic graph propagation. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, 2024a.
Song Wang, Xingbo Fu, Kaize Ding, Chen Chen, Huiyuan Chen, and Jundong Li. Federated few-shot learning. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2023.
Song Wang, Yushun Dong, Binchi Zhang, Zihan Chen, Xingbo Fu, Yinhan He, Cong Shen, Chuxu Zhang, Nitesh V Chawla, and Jundong Li. Safety in graph machine learning: Threats and safeguards. arXiv preprint ar Xiv: 1 11034, 2024b.
Yebo Wu, Li Li, Chunlin Tian, Tao Chang, Chi Lin, Cong Wang, and Shlen--Zhong Xu. Heterogeneity-awarr memory efficient federated learning via progressive layer freezing. In 2024 IEEE/ACM 32nd International Symposium on Quality of Service (IWQoS), 2024a.
Yebo Wu, Li Li, Chunlin Tian, and Chengzhong Xu. Breaking the memory wall for heterogeneous federated learning with progressive training. arXie preprint 13.:2444113349 2024b.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2020.
Han Xic, Jing Ma, Li Xiong, and Carl Yang. Federated graph classification over non-iid graphs. In Advances in neural information processing systems, 2021.
Han Xie, Li Xiong, and Carl Yang. Federated node classification over graphs with latent link-type hetero- geneity. In Proceedings of the ACM Web Conference, 2023.
14

---

Published in Transactions on Machine Learning Research (10/2024)
Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology (TIST), 2019.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graphsaint: Graph sampling based inductive learning method. In International Conference on Learning Representa- tions, 2020.
Binchi Zhang, Minnan Luo, Shangbin Feng, Ziqi Liu, Jun Zhou, and Qinghua Zheng. Ppsgen: A privacy- preserving subgraph sampling based distributed gen training method. arXiv preprint arXiv:2110. 10.020000, 2021a.
Ke Zhang, Carl Yang, Xiaoxiao Li, Lichao Sun, and Siu Ming Yiu. Subgraph federated learning with missing neighbor generation. In Advances in neural information processing systems, 2021b.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in neural information processing systems, 2018.
Shichang Zhang, Yozen Liu, Yizhou Sun, and Neil Shah. Graph-less neural networks: Teaching old mlps new tricks via distillation. In International Conference on Learning Representations, 2022.
Jun Zhou, Chaochao Chen, Longfei Zheng, Huiwen Wu, Jia Wu, Xiaolin Zheng, Bingzhe Wu, Ziqi Liu, and Li Wang. Vertically federated graph neural network for privacy-preserving node classification. Proceedings of the 31st International Joint Conference on Artificial Intelligence, 2022.
Yanqiao Zhu, Weizhi Xu, Jinghao Zhang, Qiang Liu, Shu Wu, and Liang Wang. Deep graph structure learning for robust representations: A survey. orXiv preprint arXiv:2003.0000 2021.
A Practical Scenarios with Graphless Clients
In this section, we provide more real-world scenarios where the proposed problem will arise.
Graphless clients do not record edge information. In practice, some clients in an FGL system may downplay the importance of edge information and therefore choose not to record it. Considering a healthcare system with multiple hospitals, we may construct local graphs in each hospital by taking patient demographics as node features and co-staying in a ward as edges. In the early stage of a pandemic, however, some hospitals (i.e,, graphless clients) may not take account co-staying information and fail record it. Since the co-staying information crucial for predicting a patient's 's risk of contracting a contagious disease, these hospitals camnot make accurate predictions based solely on patient demographics. Instead, our proposed FedGLS can help them to generate proper graph structures with structure knowledge transferred from other hospitals, enhancing the contagious risk prediction on these hospitals.
Graphless clients have not yet generated edge information. In the real world, some clients in an FGL system may initially have only node features, with edge information generated later. This scenario is common in dynamic graphs. Considering a financial system with multiple banks, each bank has its local dataset of customers in a city such as their demographics. For a bank operated for years in a city, it also stores transaction records among its customers and the customers naturally form a customer graph where edges represent the transaction records. Nevertheless, a new bank (i.e., a graphless client) in another city may only have few or even no transaction records and fail to form a customer graph. Considering the abundant information in transaction records, the new bank will benefit from training model for financial lending with proper graph structures.
Graphless clients have contaminated edge information. The edge information on some clients in an FGL system may be contaminated by malicious attackers. Considering multiple c-commerce companies that aim to jointly train model for product rating prediction, nodes are products and edges connect products that are frequently bought together. For some companies (i.e., graphless
15

---

Published in Transactions on Machine Learning Research (10/2024)
clients), their edge information may be destroyed manipulated by hackers and cannot be used for model training. Without the informative edge information, it is difficult to predict the rating given to a product by its node features (e.g., word embeddings).
B Module Designing of Graph Learner
Graph learners FedGLS aim to learn graph structures (i.e., adjacency matrices) on the clients in C2 help GCN training for node classification. Typically, graph learner on each graphless client consists of graph generator Gen(-) and non-parametric adjacency processor !(-)). For simplicity, we omit the client index of the notations in this section.
B.1 Graph Generator
Most existing graph generators produce a matrix S either by direct approaches (treating the elements in S
as independent parameters) (Franceschi ct al. 2019; Jin et al. 2020) or neural approaches (computing S
through an encoder) (Chen el al. 2020b Liu et al. 2022). Since direct approaches are difficult to train (Zhu) et al. 2021p, we consider neural approaches in this paper. Neural approaches take node features as input and produce matrix S. Specifically, we formulate neural network-basod graph generator Gen(-) on cach graphless client in C2 as
$= (e) ((Fnc(X;w)),
(13)
where w denotes parameters in the encoder Ene(.) and +()) is a non-parametric metric function (e.g., cosine similarity, Euclidean distance, and inner product). Here mainly consider two specific instances of neural network-based graph generators, i... MLP Encoders and Attentive Encoders.
An I-th layer ML. Encoder employs an MLP to produce node representations by R ( Enc (-1) = ( (R()))
(14)
for 1 1,2, ... L. (1) denote the node representations after the I-th layer of Enc(-) and R()) is the node feature mairix X. w()) is the weight matrix of I-th layer in a(.) is an activation function.
In an Attentive Encoder, each layer computes the Hadamard product of the input vector and parameters. Specifically, an L layer Attentive Encoder on each client in C2 can be written as
R (1) Enc (R (R)))) = ([r[[-1))) C (()),
r (1-1)
@ (((]T)
(15)
for 1,2,..., r r(-")) the transpose of the i-th row vector R (1-1) and (11) is the weight vector of the 1-th layer in w.
o the Hadamard operation
B.2 Adjacency Processor
The generated matrix Š measures the similarities between the node features. With Š, the nodes V form a fully connected graph which is not only computationally expensive but also might introduce noise. Furthermore, S may have both positive and negative values while an adjacency matrix should typically be non-negative. Therefore, we deploy an adjacency processor ?(-) to refine the generated matrix Š before taking it as the input of GNNs. The goal of the adjacency processor 2(-) to obtain a sparse symmetric normalized adjacency matrix with non-negate non-negative elements. Typically, the adjacency processor includes three main operations: sparsification, symmetrization, and normalization.
B.2.1 Sparsification
To obtain a sparse adjacency matrix, we consider a kNN-based sparsification applied on S. Specifically, the sparsification operation Sp(S,; k) produces sparse adjacency matrix (sF) by masking off (i.e., set zero) those elements in S; which are not in the set of top & values in s;
S.y, S E TopK(s,, 0,
s (sp) = kp(Sk:) =
(16)
otherwise
16

---

Published in Transactions on Machine Learning Research (10/2024)
Table 4: The statistics and basic information about the five datasets adopted for our experiments.
Dataset
Clients
Node Features
Average Nodes
Average Edges
Classes
Cora
8
1,433
192
695
CiteSeer
8
3,703
149
535
6
PubMed
16
500
1,079
4,367
3
Flickr
20
500
4,441
28,663
7
ogbn-arxiv
16
128
8,948
50,397
40
where (bpK(5,,)) k) selects the highest & values in S,.
B.2.2 Symmetrization
In practice, undirected graphs typically own symmetric adjacency matrix with non-negative values. Consid- ering this, we conduct symmetrization operation
((s9m) = Sym(S()))) ((((p)) + + (S(PP))
(17)
where a is nonlinear activation function.
B.2.3 Normalization
Once we get ((8))) we normalize it by computing its degree matrix D (sym)) and multiplying it from left and right to (D (esmm))y)
S Norm ((ym)) = (D (aym)) ) g (*ym) (sym)) --2
(18)
C Complexity Analysis
In the federated setting, clients may not be equipped with powerful machines for model training. Therefore, the training cost becomes a major concern during collaborative training. Since FedGLS is agnostic on graph Iearners and graph learners are updated only once per round, we mainly focus on analyzing the computational complexity training the GNN model and the feautre encoder (e.g,, an MLP) in FedGLS. As we analyze the computational complexity during local training within a client, we omit the client index of the notations for simplicity in this subsection.
We (ake the training of 2-layer GCN and 2-layer MLP as the GNN model and the leature encoder example. Their parameters are trained over a graph G E, X) with = [V] nodes on client. Here we assume that both the GCN and the MLP have the same hidden size m. Typically, the GCN produces Z E mm by
Z = \
(19)
where 0 = (Wo, wa), and o--) is nonlinear activation function. The feature encoder produces H E guxm by
H = H=o(XW))W;
(20)
where o= (WY. W The time complexity of the 2-layer GCN O22mm² + 2n²m) for both forward and backward pass. Hence, the overall time complexity of the GCN is 0(um² n²²m). Similarly, we can get the time complexity of the MLP as O(nm²). Typically, is significantly larger than m (e.g., 1,079 vs 16 in PubMed). Then the time complexity of the MIP will be consequently much smaller than the GCN. As a result, the feature encoder in FedGLS does not introduce siguificant extra computational costs compared with other baselines such as Fed-GNNk.
To reduce the training cost of the feature encoder, we may choose to use smaller MLPs or model com- pression. It can not only reduce the computational complexity of the feature encoder, but also uses fewer communication resources during aggregation. We leave this exploration for future work.
17

---

Published in Transactions on Machine Learning Research (10/2024)
D Datasets
In this study, we synthosize the distributed graph data on five real-world datascts, i.c., Cora Sen et al. 2008 CiteSeer (Sen et al. 2008), PubMed (Sen et al. 2008), Flickr (Zeng et al. 2020), and ogbn-arxiv (Hu et al. 2020) by splitting each of them into multiple communities. community is regarded as an entire graph on a client. Table summarizes the statistics and basic information about the five datasets.
18


Reviews:
[{"review_id": "bGSPyoQq1c", "reviewer": "Reviewer_iWP3", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n+ The paper introduces a novel approach for learning GNNs in federated learning settings assuming an interesting and more practical scenario where some of the clients do not have the structure of the graph. This can be of relevance for some applications, as it is the case of the financial system described in the paper as a motivating example. \n\n+ The proposed approach to tackle the problem seems sound, including the local graph learner, the GNN model, and the feature encoder. The motivation and the steps to formulate Algorithm 1 are reasonable. The use of knowledge distillation to infer the graph structure for graphless clients is an interesting way to solve the problem. \n\n+ Following the previous point, the paper is nicely written, the problem is well motivated, the different components of the algorithm are well presented, and the paper is easy to read. \n\n+ The authors strived to provide a comprehensive empirical analysis using 5 different real datasets to validate their approach. The baselines used for the experiments are reasonable. \n\n\nWeaknesses:\n+ While the experimental results provide a nice view on the performance of the model, a deeper analysis discussing why FedGLS outperforms the other baselines would be beneficial. On the other hand, it would be interesting to analyze the performance of some of the components, like the graph learner to measure how accurate is this model in estimating the underlying (unknown) graph structure. \n\n+ The discussion of the benefits, limitations and future work is relatively brief. It would be interesting to discuss the specific challenges encountered, the limitations of the proposed method, and further research avenues to explore in the future.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces FedGLS, a novel framework to address the challenge of applying Graph Neural Networks (GNNs) in federated learning settings in cases where some of the clients lack of a complete graph structure. Traditional federated learning for GNNs assumes local data availability, including the graph structure for all the clients. However, in some practical scenarios this assumption can be restrictive. FedGLS overcomes this limitation by constructing local graph representations from available features and partial neighbor information, using a GNN model to capture structural dependencies and node features, and employing a feature encoder to format these features for federated aggregation. During local training, the feature encoder retains both the local graph structure knowledge and the GNN model via knowledge distillation. This way, the structure knowledge is transferred among clients during the global model update in the central node. The experimental results demonstrate that FedGLS outperforms different baselines, making it a more practical solution for federated learning with GNNs.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "+ In the Introduction/motivation of the work, I think it would be nice to position the paper better with respect the horizontal vs vertical federated learning paradigms. At first, when reading these first sections it was a bit unclear to me if the method was more oriented to solve a problem for vertical or horizontal federated learning. It is a minor comment, but I think it could help to position better the paper and to make it easier for the average reader. \n\n+ Analyze the ability of the graph learner to estimate the underlying graph structure for graphless clients. \n\n+ Extend the discussion on the benefits, challenges, limitations, and future research in this direction.", "broader_impact_concerns": "N/A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "w09xcwunDi", "reviewer": "Reviewer_WwGe", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The proposed problem is natural.\n2. The proposed algorithm is natural and interesting.\n3. The experiments indicate that the algorithm works in practice.\n4. The paper is well-written.\n\nI didn't find a major weakness.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a new framework for federated graph learning, in which some workers (or clients, as phrased in the paper) have access to a graph and other workers don't have access to a graph—although an underlying graph exists—but have access to the graph nodes. The paper proposes an algorithm for all the workers to learn a common model to predict values for each node in such a way that the workers don't explicitly share their data.\n\nThe paper clearly explains the algorithm and also provides experiments showing the algorithm works in practice and is better than trivial extensions of previous algorithms.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Some experiments are executed on only some of the datasets (for example, Table 2 considers only CiteSeer and PubMed datasets). Why is that so? Doesn't the method work well for other datasets? Some explanation is needed here (not critical for accepting the paper).\n\nFor easier readability, please add parentheses when citing papers, e.g., \n\"One key problem that FL concerns is statistical heterogeneity: the data across clients are likely to be non-IID (see Li et al. 2020a)\"\n(not critical for accepting the paper).", "broader_impact_concerns": "I have no concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "HSj1XkE1wg", "reviewer": "Reviewer_K8TF", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is well written and easy to read (except for some small concerns).\n- The authors propose a novel problem formulation and an algorithm to solve it.\n- The authors provide extensive empirical results showing the superiority against naive baselines obtained by adjusting existing algorithms to new problems.\n\nWeaknesses:\n- Not enough examples supporting that new problem formulation should be explored. In my opinion, when one proposes a new problem/field/etc. that should be explored, he/she should give many examples of where this problem appears, so that the community has a clear understanding of why this new area/field should be explored.\n- In the current version, graphless clients perform more work than the clients who own graph structures. Therefore, clients who have local graph structures will stay without any jobs for some time. In my opinion, this is a waste of resources. I would suggest performing graph learning on the clients with local graph structures and forcing the output to be close to ground truth local graph structure. This knowledge can also be used by graphless clients to further improve their graph learners. \n\nQuestions:\n- In the example of Figure 1, it seems new banks who don’t have transaction history are also not able to construct proper node features as well, i.e. $X^{(k)}$ seems to be unreliable as well. For example, node features should contain features like average money transferred/spent which cannot be known without transaction history. In other words, it feels like if a client doesn’t have $A^{(k)}$, then it also doesn’t have good $X^{(k)}$, and one should use node feature learner as well.\n- Why is there only one step to update graph learners’ parameters while for other parts there are several local steps?\n- In the introduction you mention “This scenario brings us a novel problem in the federated setting”. However, in the experiments, you mention “How does FedGLS perform compared with other state-of-the-art baselines?”. These two sentences contradict each other. Maybe it’s better to link to a section with baselines to not confuse readers. \n- Why does the related work section come in the end?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a new problem formulation where some clients do not have local graph structure, and thus have to learn some approximation of it during the training. Next, the authors propose FedGLS algorithm to tackle this problem. They provide experiments comparing the proposed method with some baselines which are obtained by modifying well-known algorithms to new problem formulation.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please check the strengths and weaknesses section.", "broader_impact_concerns": "I do not see any ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: I believe that the motivation behind the work needs to be stronger and would like to get more feedback from the authors.
Decision: Accept (poster)