Rethinking Federated Graph Learning: A Data Condensation Perspective

1 Introduction

Graph Neural Networks (GNNs) have emerged as a robust machine learning paradigm to learn expressive representations of graph-structured data through message passing, exhibiting remarkable performance across various AI applications, such as molecular interactions[Huang et al., 2020]. However, most existing GNNs adopt a centralized training strategy where graph data need to be collected together before training. In practical industrial scenarios, large-scale graphs are collected and stored on edge devices. Meanwhile, regulations such as GDPR [Voigt and Von dem Bussche, 2017] highlight the importance of data privacy and impose restrictions on the transmission of local data, which often contains sensitive information. This has led to the exploration of leveraging collective intelligence through distributed data silos to enable collaboration in graph learning [Li et al., 2022a].

To this end, Federated Graph Learning (FGL) has been proposed, extending Federated Learning (FL) to graphstructured data. Its core idea is to harness collective intelligence for the collaborative training of powerful GNNs, thereby advancing AI-driven insights in federated systems. Given the diversity of graph-based downstream tasks, this paper focuses on subgraph-FL, the instance of FGL on a semisupervised node classification paradigm. To enhance understanding, we present case study within healthcare systems.

Case Study. In different regions, residents visit various hospitals (e.g., independent clients), all of which are centrally managed by government organizations (e.g., the trusted server). Each hospital maintains a subgraph in its database, containing demographics, living conditions, and patient interactions. These subgraphs form a global patient network. Notably, due to privacy regulations, geographic isolation, and competitive concerns, centralized data storage is not feasible. Fortunately, subgraph-FL enables federated training through multi-client collaboration without direct data sharing. For tasks such as predicting the spread of infections during a pandemic [Bertozzi et al., 2020], developing a federated collaborative paradigm based on distributed scenarios is essential.

Specifically, as illustrated in Fig.1(a), the iterative training process of conventional subgraph-FL consists of four steps: (1) all clients download the latest global model from the server; (2) each client trains the model on its privately stored subgraph; (3) after local training, the clients upload the model parameters or gradients to the central server; (4) the server aggregates the model parameters or gradients to update the global model, which is then broadcast back to clients.

Based on this, most subgraph-FL approaches [Fu et al., 2022] rely on model parameters or gradients as the optimization carriers for federated training. These carriers are primarily derived from Computer Vision (CV)-based FL collaborative paradigm [Lim et al., 2020], which struggles to capture the client-specific local convergence tendencies due to the complex topology in FGL, thus failing to adequately address the unique challenges of subgraph heterogeneity [Baek et al., 2023]. Notably, current FGL methods [Li et al., 2024b; Li et al., 2024a] typically face a trade-off between optimization and privacy, as they seek to enhance model gradientbased federated convergence by sharing more messages. Further analysis and empirical studies will be provided in Sec. 3. Despite the significant contributions of existing methods, the inherent trade-off dilemma in CV-based federated optimization carriers limits the upper bound of FGL convergence, motivating us to propose a new collaborative paradigm.

Inspired by Graph Condensation (GC) [Zhao et al., 2020; Jin et al., 2021], a comprehensive and explicit approach based on condensed graphs holds promise in addressing the aforementioned limitations. Specifically, condensed graphs can effectively capture the complex relationships between nodes and topology, providing a more suitable means of information transmission. This implies that we can use the condensed graph as the optimization carrier for FGL, replacing traditional model parameters or gradients. Furthermore, a recent study [Dong et al., 2022] suggests that data condensation via gradient matching can safeguard privacy. This makes condensed graph-based approaches highly promising as a robust framework for FGL data heterogeneity. The core idea of our method is to integrate generalized condensation subgraph consensus to acquire comprehensive and reliable knowledge.

In this paper, we propose a new FGL paradigm based on condensed subgraphs, as illustrated in Fig.1(b): (1) Each client performs local subgraph condensation using gradient matching and then uploads the condensed subgraph to the server; (2) The central server optimizes the condensed knowledge from a global perspective, resulting in a global-level condensed graph; (3) The server then trains a robust global model on the condensed graph and returns it to the clients.

Based on our proposed FGL paradigm, we introduce FedGM, a specialized dual-stage framework, as follows: Stage 1: Each client independently performs local subgraph condensation through gradient matching between the real subgraph and the condensed subgraph, without any communication, and then uploads the condensed knowledge to the server. Notably, multiple clients execute data condensation locally and in parallel. The central server then integrates these condensed subgraphs into a global-level condensed graph. It implies that Stage 1 is completed. And clients and the server only need to perform a single communication round to upload the locally condensed subgraphs, making this a one-shot FGL

process. Stage 2: To achieve performance comparable to directly training on the implicit global real graph, FedGM employs federated gradient matching to optimize the condensed features. This approach leverages global class-wise knowledge to reinforce and consolidate the condensation consensus through multiple rounds of federated optimization. Subsequently, the central server trains a global robust GNN using the global condensed graph and distributes it to all clients.

Our contributions are as follows: (1) New Framework. To the best of our knowledge, we are the first to introduce condensed graphs as a novel optimization carrier to address the challenge of subgraph heterogeneity. (2) New Paradigm. We propose FedGM, a dual-stage paradigm that integrates generalized condensed subgraph consensus to obtain comprehensive knowledge while minimizing communication costs and reducing the risk of privacy breaches through a single transmission of condensed data between clients and the server. (3) SOTA Performance. Extensive experiments on six datasets demonstrate the consistent superiority of FedGM over stateof-the-art baselines, with improvements of up to 4.3%.

2 Notations and ProblemFormalization

2.1 Notations

Graph Neural Networks. Consider a graph G = {A, X, Y} consisting of N nodes, where X ∈ RN×d is the ddimensional node feature matrix and Y ∈ {1, ...,C}N denotes the node labels over C classes. A ∈ RN×N is the adjacency matrix, with entry Ai,j > 0 denoting an observed edge from node i to j, and Ai,j = 0 otherwise. Building upon this, most GNNs can be subsumed into the deep message-passing framework [Wu et al., 2020a].

Graph Condensation. Graph condensation is proposed to learn a synthetic graph with N ′ ≪ N nodes from the real graph G, denoted by Sk = {A′ , X′ , Y′ } with A′ ∈ RN ′×N ′ , X′ ∈ RN ′×d , Y′ ∈ {1, ...,C}N ′ , such that a GNN f(·) solely trained on S can achieve comparable performance to the one trained on the original graph. In other words, graph condensation can be considered as a process of minimizing the loss defined on the models trained on the real graph G and the synthetic graph S:

where GNNθS and GNNθG denote the GNN models trained on S and G, respectively; L represents the loss function used to measure the difference of these two models.

Subgraph Federated Learning. In subgraph-FL, the kth client has a subgraph Gk = {Ak,Xk,Yk} of an implicit global graph Gglo = {Aglo,Xglo,Yglo} (i.e., Ak ⊆ Aglo,Xk ⊆ Xglo,Yk ⊆ Yglo). Each subgraph consists of Nk nodes, where Xk ∈ RNk×d is the d-dimensional node feature matrix and Yk ∈ {1, ...,C}Nk denotes the node labels over C classes. Typically, the training process for the t - th communication round in subgraph-FL with the FedAvg aggregation can be described as follows: (i) Initialization: This step occurs only at the first communication round (t = 1). The server sets the local GNN parameters of k clients to the global GNN parameters ¯ θ, using θk ← ¯ θ ∀k. (ii) Local Updates: Each local GNN performs training on the local data Gk to minimize the task loss L(Gk; θk), and then updating the parameters: θk ← θk - η∇L. (iii) Global Aggregation: After local training, the server aggregates local knowledge with respect to the number of training instances, i.e., ¯ θ ∑Kk=1 ← Nk N θk with N = ∑k Nk, and distributes the updated global parameters ¯ θ to clients selected at the next round.

2.2 ProblemFormalization

The proposed condensation-based Subgraph-FL framework is as follows: Firstly, each client performs local subgraph condensation, then uploads condensed knowledge to the server. Specifically, suppose that a client k is tasked with learning a local condensed subgraph with N ′ < N nodes from the real subgraph Gk, denoted as Sk = {A′k ,X′k ,Y′k } with A′k ∈ RN ′×N ′ , X′k ∈ RN ′×d , Y′k ∈ {1, ..., C}N ′ . The central server leverages the global perspective to optimize the condensed subgraphs, resulting in a global-level condensed graph Sglo = {A′glo ,X′glo ,Y′glo }. Subsequently, the server trains a robust global model on the condensed graph and returns it to the clients. The motivation for this design is to obtain a powerful model trained on the condensed graph Sglo, achieving performance comparable to one directly trained on the implicit global graph Gglo:

where GNNθ denotes the GNN model parameterized with θ, θS denotes the parameters of the model trained on Sglo, and L is the loss function used to measure the difference between model predictions and ground truth (i.e. cross-entropy loss).

3 Empirical Analysis

In this section, we empirically explore subgraph heterogeneity to investigate the FGL optimization dilemma. According to our observations, existing methods have the following limitations: (i) Using model parameters or gradients as primary information carriers overlooks the complex interplay between features and topology within local heterogeneous subgraphs, resulting in sub-optimal performance; (ii) many existing methods require the upload of additional information (e.g., subgraph embeddings, or mixed moments), raising privacy concerns. The in-depth analysis is provided as follows.

In CV-based FL, data heterogeneity refers to variations among clients in terms of features, labels, data quality, and data quantity [Qu et al., 2022; Li et al., 2022b]. This variability presents substantial challenges for effective federated training and optimization. In this work, we focus on the heterogeneity of features and labels, considering their strong correlation, widely highlighted by practical applications. Unlike data heterogeneity in conventional FL, subgraph heterogeneity is influenced by diverse topologies across clients [Li et al., 2024a]. According to the homophily assumption [Wu et al., 2020b], connected nodes tend to share similar feature distributions and labels. However, with the increasing deployment of GNNs in real-world applications, topology heterophily has emerged [Zhu et al., 2021; Luan et al., 2022], where the connected nodes exhibit contrasting attributes. Due to community-based subgraph data collection methods (i.e., the community can be viewed as the client), subgraphs from different communities often exhibit diverse topological structures, leading to Non-independent and identically distributed labels, as shown in Fig.2(a). Specifically, we observe strong homophily at Client 1 in Cora and CiteSeer, as the majority of nodes belong to the same label class. In contrast, at Cora-Client 3 and CiteSeer-Client 10, we observe the presence of heterophily, as label distributions approach uniformity. In summary, clients often exhibit diverse label distributions and topologies, a characteristic of distributed graphs that demands attention. Conventional federated training, which neglects subgraph heterogeneity, leads to underperformance.

To address these issues, FED-PUB [Baek et al., 2023] measures subgraph similarity by transmitting subgraph embeddings for personalized aggregation. FedGTA [Li et al., 2024b] shares mixed moments and local smoothing confidence for topology-aware aggregation. FedSage+[Zhang et al., 2021] and FedGNN[Wu et al., 2021] aim to reconstruct potentially missing edges among clients, thereby aligning local objectives at the data level. FedTAD [Zhu et al., 2024] introduces topology-aware, data-free knowledge distillation. Despite the considerable efforts of subgraph heterogeneity, these methods rely on uploading additional information, leading to privacy concerns and higher communication overhead.

Considering the capability of condensed graphs to capture complex node-to-topology relationships while preserving privacy, we propose the condensation-based subgraphFL framework. To validate the effectiveness of condensed knowledge as an optimization carrier, we conduct experiments using GCN in a federated learning setting with 10 clients across two common datasets, Cora [Kipf and Welling,

2016a] and CiteSeer [Kipf and Welling, 2016a], as shown in Fig.2(b). The results demonstrate improved model performance and faster convergence of the condensation-based subgraph-FL method. Superior performance indicates a better capability to tackle subgraph heterogeneity, while faster convergence translates into reduced communication costs.

4 Method

The overview of our proposed FedGM is depicted in Fig.3. In Stage 1, each client involves a local process of standard graph condensation by one-step gradient matching and uploads condensed subgraphs to the central server. The server subsequently integrates these into a global-level graph. In Stage 2, we introduce federated optimization and perform multiple rounds of communication to leverage the class-wise knowledge, enhancing the quality of the condensed features.

4.1 Stage 1: Condensed Graph Generation

In the first stage, our task is to integrate the condensation consensus from clients to generate a global condensed graph. Since the real graph is distributed among multiple participants, direct access to the real graph to obtain the condensed graph, as in Eq.(2), is prohibited. Therefore, we perform subgraph condensation on each client to achieve local optimization and then integrate these subgraphs on the server via a single round of federated communication. Considering privacy protection requirements and condensation quality, we adopt the gradient alignment advocated by [Jin et al., 2021; Jin et al., 2022] as the local learning task. Unlike GraphGAN [Wang et al., 2018] and GraphVAE [Simonovsky and Komodakis, 2018], which synthesize high-fidelity graphs by capturing data distribution, its goal is to generate informative graphs for training GNNs rather than "real-looking" graphs.

Client-Side Subgraph Condensation. The FedGM aims to provide a flexible graph learning paradigm by enabling each client to perform local subgraph condensation under local conditions without requiring real-time synchronization. The client generate the condensed subgraph through one-step gradient matching[Jin et al., 2021; Jin et al., 2022], where a GNN is updated using real subgraph and condensed subgraph, respectively, and their resultant gradients are encouraged to be consistent, as show on the left side of Fig.4. The local optimization objective can be formulated as:

where D(·, ·) represents a distance function, and the subgraph condensation model parameters θk for client k are initialized from the distribution of random initialization Pθk . In each condensation round, each client initializes its subgraph condensation model to calculate the gradients for the real subgraph and the condensed subgraph. By taking different parameter initializations drawn from the distribution Pθk , the learned Sk can avoid over fitting a specific initialization.

To facilitate efficient learning of Sk, a common practice is to reduce the trainable pieces in the condensed subgraph Sk = {A′k ,X′k ,Y′k } to only the node features X′k . Concretely, the labels Y′k can be predefined to match the distribution of different classes in the real subgraph, while each client condenses the graph structure by leveraging a function to parameterize the adjacency matrix A′k to prevent overlooking the implicit correlations between condensed node features and condensed structure [Jin et al., 2021]:

where MLPΦ is a multi-layer perceptron (MLP) parameterized with Φ, [·; ·] indicates concatenation and σ is the sigmoid function. The client condenses the subgraph by optimizing alternately X′k and Φk. After condensation, the client transfers Sk to the server via one-shot federated communication.

Server-Side Condensed Subgraphs Integration. To construct a global condensed graph, the server concatenates the features and labels from each client's condensed subgraph:

where X′k and Y′k represent the condened features and labels from client k, respectively. Unlike real-world graph structures, the condensed topology lacks tangible meaning, which is only relevant to the passage of condensed knowledge within the GNNs. To avoid disrupting the knowledge representing each client's subgraph within condensed data, we retain the topology of each condensed subgraph. Specifically, the global condensed adjacency matrix A′glo is represented as:

where Vk denotes the set of nodes from client k. Consequently, we obtain an initial global condensed graph, consisting of multiple connected components. However, there remains a significant gap between the quality of the condensed graph and our desired target due to the limitations of the narrow local scope. Therefore, it is crucial to effectively optimize the condensed graph by leveraging a global perspective.

4.2 Stage 2: Condensed Graph Optimization

There is a common phenomenon of class imbalance at the client level in scenarios with subgraph heterogeneity, which obviously leads to poorer feature quality for condensed nodes, especially for the minority classes. We observe that majority classes on one client often correspond to minority classes on other clients in scenarios with subgraph heterogeneity, as shown in Fig. 1(b). Therefore, we aim to collect the class-wise gradients generated by each subgraph and perform federated gradient matching to optimize the condensed features. Our intuition is that the shared intra-class knowledge between clients provides a basis based on the global perspective, which iteratively reduces the gap between the condensed graph and the real graph via class-wise gradient matching, as illustrated on the right side of Fig. 4.

In the second stage, FedGM introduces condensed graph optimization, which is performed over multi-round federated communication. In the t-th iteration, the server samples the gradient generation model parameters θt from random initialization distribution Pθt and sends it to each client.

Clinet-Side Gradient Generation. On each client, the real subgraphs generate class-wise gradients through the gradient generation model. For class c, and the generated gradient is:

where Ak,c denotes the adjacency matrix composed of the cclass nodes and their neighbors and Xk,c denote the features corresponding to the c-class nodes. To ease the presentation, we adopt the following nations for every client k:

Upon having the class-wise gradients obtained, clients share the generated gradients ▽θt LGk with the server.

Sever-Side Gradient Matching. For class c, the server calculates the gradient generated by the implicit global graph based on the number of c-class condensed nodes from clients:

The gradients generated by the condensed graph is as follows:

Then we empower the server to match the gradients of the implicit global graph and the condensed graph for each category using the distance function. And we simplify our objective as

▽θt LG and ▽θt LSglo in the above equation are defined as

In the multi-round communication process, the central server optimizes the features using the class-specific gradients, ultimately obtaining the desired condensed graph. The secondstage method of FedGM is presented in Algorithm 1.

Algorithm 1 FedGM-Condensed Graph Optimization Input: Rounds, T ; Local real subgraphs, {Gk}Kk=1 ; Initial condensed graph, Sglo Output: Optimized condensed graph, S ′glo /* Client Execution */ 1 for each communication round t = 1, ..., T do 2 Update the gradient generation model θt; for each class c = 1, ..., C do 3 Sample on the real subgraph according to the class c (Ak,c, Xk,c, Yk,c) ∼ Gk; 4 Calculate loss and get the gradient via Eq.9 5 Upload the number of samples of each category and the corresponding gradient to the central server /* Server Execution */ 6 for each communication round t = 1, ..., T do 7 initialize θt ∼ Pθt ; 8 for each client k = 1, ..., K do 9 Send the gradient generation model θt to client k; Receive the number of class samples and the corresponding gradient for each class c = 1, ..., C do Calculate the condensed graph gradient via Eq.12; Calculate the real graph gradient via Eq.11;

10 11 12 13 14 Update the condensed features X′glo via Eq.13;

5 Experiments

In this section, we conduct experiments to verify the effectiveness of FedGM. We introduce 6 benchmark graph datasets across 5 domains and the simulation strategy for the subgraph-FL scenario. And we present 8 evaluated state-ofthe-art baselines. Specifically, we aim to answer the following questions: Q1: Compared with other state-of-the-art federated optimization strategies, can FedGM achieve better performance? Q2: Where does the performance gain of FedGM come from? Q3: Is FedGM sensitive to the hyperparameters? Q4: What is the time complexity of FedGM?

5.1 Datasets and SimulationMethod

We evaluate FedGM on six public benchmark graph datasets across five domains, including two citation networks (Cora, Citeseer) [Kipf and Welling, 2016a], one co-authorship network (CS) [Shchur et al., 2018], one co-purchase network (Amazon Photo), one task interaction network (Tolokers) [Platonov et al., 2023], and one social network (Actor) [Tang et al., 2009]. More details can be found in Table 1. To simulate the distributed subgraphs in subgraph-FL, we employ the Louvain algorithm [Blondel et al., 2008] to achieve graph partitioning across 10 clients, which is based on modularity optimization and widely used in the subgraph-FL fields.

5.2 Baselines and Experimental Settings

Baselines. We compare the proposed FedGM with four conventional FL optimization strategies (FedAvg [McMahan et al., 2017], FedProx [Li et al., 2020], SCAFFOLD [Karimireddy et al., 2020], MOON [Li et al., 2021]), two personalized subgraph-FL optimization strategies (Fed-PUB[Baek et al., 2023], FedGTA[Li et al., 2024b]), one subgraph-FL optimization strategy (FedTAD [Zhu et al., 2024]), and one subgraph-FL framework (FedSage+ [Zhang et al., 2021]).

Hyperparameters. For conventional framework, we employ a 2-layer GCN [Kipf and Welling, 2016b] with 256 hidden units as the backbone for both the clients and the central server. The local training epoch is set to 3. Notably, modelspecific baselines such as FedSage+ [Zhang et al., 2021] adhere to the custom architectures specified in their original papers. In the FedGM framework, the local subgraph condensation model, gradient generation model, and the model employed for evaluation are all implemented as 2-layer GCNs with 256 hidden units, and the condensed graph structure generation model is implemented as a 3-layer MLP with 128 hidden units. In the first stage, the number of local condensation epochs is 1000. Based on this, we perform the hyperparameter search for FedGM using the Optuna framework [Akiba et al., 2019] on the ratio r of condensed nodes to real nodes within the ranges of 0 to 1. For all methods, the learning rate for the GNN is set to 1e-2, the weight decay is set to 5e-4, and the dropout rate is set to 0.0. The federated training is conducted over 100 rounds. For each experiment, we report the mean and variance results of 3 standardized training runs.

5.3 Results and Analysis

Result 1: the answer to Q1. The comparison results are presented in Table 2. According to observations, the proposed FedGM overall outperforms the baseline. Specifically, compared with FedAvg, FedGM brings at most 4.3% performance improvement; Compared with Fed-PUB, FedGM can achieve a performance improvement of at most 4.1%. Moreover, FedGM consistently outperforms existing SOTA methods in varying numbers of clients. Notably, as the number of clients increases, the performance advantage of FedGM becomes more pronounced. Specifically, with 20 clients, FedGM achieves a 13.4% performance improvement over FedAvg, as shown in Fig.5. The convergence curves of FedGM and baselines are shown in Fig.2(b). It is observed that FedGM has a good effect at the beginning of federated communication, which shows that FedGM is suitable for subgraph-FL scenarios with limited communication overhead. In addition, FedGM demonstrates robust performance stability across various client settings, with accuracy fluctuations remaining within a margin of 2% as shown in Fig.5.

Result 2: the answer to Q2. Stage 2 builds upon the foundation established in Stage 1. To answer Q2, we conducted an ablation study to investigate the effectiveness of both Stage

1 and Stage 2, as shown in Table 2. After Stage 1, our method achieves an average accuracy of 72.92%, surpassing other state-of-the-art methods on two datasets, demonstrating the feasibility of the condensation-based FGL paradigm. In addition, our method consistently achieves superior performance compared to its single-stage variant across all datasets (e.g., increasing from 84.91% to 90.85% and from 72.92% to 74.56%), highlighting the pivotal role of the second stage in enhancing the model's representational capacity and robustness. This further validates that leveraging global intra-class knowledge contributes to improving the quality of the condensed graphs, reinforcing the efficacy of FedGM.

Result 3: the answer to Q3. To answer Q3, we assess the performance of FedGM under diverse condensation ratios. The sensitivity analysis on the Cora and CiteSeer datasets is presented in Fig.6. Overall, most values cluster near the maximum, reflecting consistently high accuracy under the majority of conditions. FedGM is insensitive to the condensation ratio, and there is no significant dependence.

Result 4: the answer to Q4. To answer Q4, we provide the complexity analysis of FedGM. In Stage 1, condensation graph generation costs O(rM), where r denotes the condensation ratio, and M denotes the size of the labeled dataset. A single transmission of condensed data implies a lower risk of privacy leakage. In Stage 2, condensation graph optimization costs O(KTNΘGNN ), where K denotes the number of participating clients, T denotes the number of the federal communication rounds, and ΘGNN denotes the size of GNN gradients or parameters associated with gradient matching. Notably, FedAvg represents the lowest communication cost among federated learning processes, and its time complexity is also O(KTNΘGNN ). Unlike FedAvg, where the shared model parameters represent a trained GNN model, FedGM leverages the shared parameters primarily for generating gradients rather than direct model deployment. This distinction implies a reduced privacy risk during the federated process.

6 Conclusion

In this paper, we conduct an in-depth analysis of the tradeoff dilemma caused by the poor performance of conventional federated carriers in handling subgraph heterogeneity. Considering the capability of condensed graphs to capture complex node-to-topology relationships while preserving privacy, we are the first to propose a new condensation-based FGL paradigm. Specifically, we propose FedGM, a dual-stage paradigm that integrates generalized condensation consensus to capture comprehensive knowledge. Experimental results demonstrate FedGM outperforms state-of-the-art baselines.