FedTAD: Topology-aware Data-free Knowledge Distillation for Subgraph Federated Learning

1 Introduction

Graph neural networks (GNNs) have emerged as a promising machine learning paradigm on structured data, exhibiting remarkable performance across diverse AI applications, such as social recommendation [Guo and Wang, 2020] and financial analysis [Yang et al., 2021]. However, most existing GNNs presuppose centralized data storage, which grants a single user or institution access to the entire graph for training. This vulnerable assumption does not apply to many realworld scenarios, as a domain-specific graph may consist of multiple subgraphs, each constrained to be locally accessed due to competition and privacy concerns. For instance, each financial institution constructs its transaction network without sharing privacy-sensitive data with others [Fu et al., 2022]. Consequently, training powerful GNNs using collective intelligence becomes challenging in such distributed scenarios.

† Corresponding author.

To this end, federated graph learning (FGL), the concept of integrating federated learning (FL) with graphs is proposed. Especially, the instance of FGL on a semi-supervised node classification paradigm is known as subgraph-FL. In each training round of this federated setting, each client utilizes its privately stored subgraph to train the local model independently. Then, these local models are uploaded to a trusted central server and aggregated into a global model, which will be broadcast to local clients for the next training round. In the aforementioned multi-client collaborative training process, FedAvg [McMahan et al., 2017] serves as a simple yet effective method, accomplishing global model aggregation by quantifying the sizes of data samples across multiple clients.

Despite extensive study of subgraph-FL, inherent differences in data collection methods often lead to multi-client data variation [Xie et al., 2021], leading to a decline in the model performance, referred to as the subgraph heterogeneity [Baek et al., 2023]. Unlike data heterogeneity in conventional FL, subgraph heterogeneity arises from both nodes and topology, as shown in Fig. 1(a). As a result, the conventional federated optimization strategies fail at addressing subgraph heterogeneity (e.g., FedProx [Li et al., 2020] for Non-iid label distributions) due to the emission of topology. To this end, Fed-PUB [Baek et al., 2023] measures subgraph similarity for personalized aggregation. FedGTA [Li et al., 2023] introduce graph mixed moments for topology-aware aggregation. FedSage+[Zhang et al., 2021] and FedGNN[Wu et al., 2021] aspire to reconstruct potential missing edges among clients, representing an implicit resolution to subgraph heterogeneity by aligning local optimization objectives at the data level. Despite the considerable efforts of subgraph heterogeneity, they still have the following limitations.

L1: Lack of in-depth exploration. The impact mechanisms of subgraph heterogeneity from the independent roles of node and topology variation are ambiguous. Solution: we empirically investigate and decouple node and topology variation among clients, revealing that they correspond to the difference in label distributions and class-wise homophily (i.e., for a specific class of nodes, the preference of them and their neighbors with similar attributes). These variations lead to different class-wise knowledge reliability. Specifically, for a specific label, the local model trained with a local subgraph that has numerous nodes with this label and exhibits strong class-wise homophily has a reliable prediction.

L2: Sub-optimal model aggregation in subgraph-FL.

Due to the local training process encoding patterns of local subgraph into parameters of the local model, class-wise knowledge with different reliability is implicitly contained in these parameters. As a result, the server-side model aggregation is inevitably misled by unreliable class-wise knowledge. Solution: we propose FedTAD, as a topology-aware data-free knowledge distillation strategy, which fully considers the differences in the reliability of class-wise knowledge among local GNNs to improve subgraph-FL. Specifically, on the Client side, FedTAD first utilizes topology-aware node embeddings to measure the reliability of class-wise knowledge. Then, on the Server side, FedTAD employs a generator to model the input space and generates a pseudo graph for transferring reliable knowledge from the multi-client local model to the global model. Remarkably, FedTAD can be viewed as a hot-plugging strategy for any FL optimization strategy, aiming to correct the global model misled by unreliable knowledge during multi-client model aggregation.

Our contributions. (1) New Observation. To the best of our knowledge, this paper is the first to investigate the subgraph heterogeneity by decoupling multi-client node and topology variation, providing valuable empirical analysis. (2) New Method. We propose FedTAD, which can serve as a hotplugging post-processor for existing federated optimization strategies, achieving reliable knowledge transfer and alleviating the negative impact of unreliable class-wise knowledge caused by subgraph heterogeneity. (3) SOTA Performance. Extensive experiments on six datasets demonstrate that FedTAD outperforms existing baselines (up to 5.3% higher), and improves various state-of-the-art FGL optimization strategies (up to 4.9% performance boost).

2 Preliminaries

Graph Neural Networks. Consider an undirected graph G = (V, E) with V as the node-set and E as the edge-set. Each node vi ∈ V has a F-dimensional attribute vector xi and a label yi. The adjacency matrix (including self-loops) is ˆA ∈ RN×N . N (vi) represents the neighbor nodes set of node vi. Building upon this, most GNNs can be subsumed into the deep message-passing framework [Gilmer et al., 2017], which obtains a representation of the current node by recursively aggregating and transforming the representations of its neighbors. Specifically, the representation of node vi at the l-th layer is denoted as hl+1 i and is computed as follows:

where h0i = xi, hli is the representation of node vi in the l-th (previous) layer, AGG(·) aggregates the neighbor representations, and UPD(·, ·) updates the representation of the current node using its representation and the aggregated neighbor representation at the previous layer.

Subgraph Federated Learning. In subgraph-FL, the k-th client has an undirected subgraph Gk = (Vk, Ek) of an implicit global graph Gg = (Vg, Eg) (i.e., Vk ⊆ Vg, Ek ⊆ Eg). Each node vi ∈ Vk has an attribute vector xik and a label yik . Typically, the training process of the t-th communication round in subgraph-FL with FedAvg aggregation strategy can be described as follows: (i) Client Selection: Randomly select a set of clients St based on a certain probability for this round of subgraph-FL. (ii) Local Update: Each selected client (e.g., the k-th) downloads the parameters of the global GNN ˜wt and performs local training on its private subgraph Gk to minimize L(Gk), where L(Gk) is the task loss for semi-supervised node classification on subgraph Gk. (iii) Global Aggregation: The server collects the parameters of the local GNNs {wk}k∈St to perform parameter aggregation concerning the number of training instances, i.e., ˜wt = ∑k∈St |Vk | N wtk , where N denotes the total number of nodes for all selected clients.

Class-wise Homophily. Various GNN research [Zhu et al., 2020; Sun et al., 2023] has discussed the graph homophily (i.e., for an entire graph, the preference of connected nodes with similar attributes). However, this paper focuses on a more fine-grained issue: class-wise graph homophily (i.e., for a specific class of nodes, the preference of them and their neighbors with similar attributes). We contend that local GNNs offer more reliable predictions for classes with higher class-level homophily, providing effective guidance for subgraph-FL. Details are presented in Section 3.

3 Empirical Investigation

In this section, we delve into subgraph heterogeneity by separating node and topology entanglement. We first apply the average assignment-based Louvain algorithm [Blondel et al., 2008] to split the Cora dataset [Yang et al., 2016] into three subgraphs, aligning with the strategy in FedSage+ [Zhang et al., 2021]. Before being distributed to clients, these subgraphs are modified to decouple the node and topology variation, which are detailed in Fig. 1(b). (i) Node variation. Removing edges to mitigate topology variation effects. (ii) Topology variation. Clients share the nodes of subgraph 1, eliminating node variation, while the topology is perturbed by randomly adding edges. Then, we conduct subgraph-FL using GCN and FedAvg, comparing global GNN performance with/without Client 1 participation.

Node Variation. Essentially, node variation can be regarded as the data heterogeneity in conventional FL, manifested as label Non-independent identical distribution (Noniid). Node heterogeneity and the performance of two global models (with/without Client 1 participation) are depicted in Fig. 1(c) and (d). Notably, client 1 predominantly collects nodes of classes 2 and 3, while other class nodes are scarce on Client 1. Consequently, global model performance is notably improved for classes 2 and 3 with Client 1 participation, but it declines to some extent for other classes. Thus, we argue that the node variation leads to differences in the reliability of class-wise knowledge. Observation 1. For a specific class, local GNN trained with a larger number of nodes corresponds to more reliable knowledge.

Topology Variation. Building on the previous exploration, where node variation influences class-level knowledge reliability within local GNNs, we assume that topology variation may yield similar effects. Yet, a critical challenge is properly mapping the intricate topology into class-level distribution. Referring to a previous study [Zhu et al., 2020], GNNs generally exhibit improved performance when dealing with graphs characterized by higher homophily. Intuitively, we assume that GNNs offer more reliable class-wise knowledge when the majority of nodes within that class exhibit stronger local homophily. Consequently, we adapt the edge homophily ratio [Zhu et al., 2020] to quantify class-wise homophily. Specifically, consider a graph G = (V, E) with node label yi for each node vi ∈ V, we use φ(c) to denotes the class-wise homophily on class c, which is computed as:

Fig. 1(c) and (d) display the class-wise homophily distribution of three clients and the performance of two global models (with/without Client 1 participation). Notably, Client 1 exhibits weak class-wise homophily in class 3 but strong homophily in other classes. Global model performance for class 3 declines with Client 1 participation but improves for other classes. We assert that topology variation corresponds to differences in class-wise homophily and also leads to variations in the reliability of class-wise knowledge. Observation 2. For a specific class, local GNN trained with stronger classwise homophily corresponds to more reliable knowledge.

4 Methodology

4.1 Overview

The overview of our proposed FedTAD is depicted in Fig.2. On the Client side, each client computes topology-aware node embeddings to measure class-wise knowledge reliability, which is then uploaded to the server. On the Server side, guided by the class-wise knowledge reliability, FedTAD generates a pseudo graph for transferring reliable knowledge from multi-client local models to the global model.

4.2 Class-wise Knowledge ReliabilityMeasuring

To obtain reliable knowledge from clients, our key insight is that the reliability of local models for specific label predictions depends on their local subgraph (i) a large number of corresponding labeled nodes and (ii) strong class-wise graph homophily. However, the existence of unlabeled nodes hinders access to class-wise graph homophily. To this end, we introduce a topology-aware node embedding, which characterizes a node with its original feature and local topological structure. Afterward, we assess the class-wise knowledge reliability by quantifying the similarity in topology-aware node embeddings between labeled nodes and their neighbors.

Topology-aware Node Embedding. We obtain the topology embedding of each labeled node i based on the graph diffusion [Tong et al., 2006], which is defined as:

where T = AD-1 represents the random walk transition matrix, D represents the degree matrix (i.e., di = ∑nj=1 aij ). By combining different walking distances {1, ..., p}, the topology embedding captures rich structural information. Then, the topology-aware node embedding of vi can be obtained by concatenating the node features xi and hTOPO i :

Class-wise Knowledge Reliability. Building upon the above conceptions, for a specific class c, the class-wise knowledge reliability is formally defined as:

where s(·, ·) represents the cosine similarity. Intuitively, Eq. (5) considers both the label and structure distribution, as the V labeled term performs the summation of labeled nodes of the same class, and the ∑vj∈N(vi) s(hHYB i , hHYB j )/|N(vi)| term measures the class-wise graph homophily within the 1hop ego-graph of each labeled node.

4.3 Topology-aware Knowledge Distillation

The proposed FedTAD servers as a post-processor following the vanilla model aggregators (e.g., FedAvg). Its objective is to transfer reliable knowledge from multi-client local models to further improve the aggregated model ˜w. Specifically, in each round t, the server receives the local model weights {wk}k∈St and the class-wise knowledge reliability {ϕk}k∈St uploaded from the selected clients St.

Server-side Knowledge Generation. The server first uses a generator to generate pseudo node attributes ˆX ∈ RB×F ,

where P denotes the generator, θ is the parameter of generator, z is the standard Gaussian noise, i.e. z ∼ N(0, 1), y denotes the label of ˆx sampled from uniform distribution, and B denotes the number of generated nodes.

Subsequently, we construct the topology structure based on ˆX with the K-Nearest Neighbors strategy. Specifically, the pseudo adjacency matrix ˆ A is computed as follows:

where σ(·) represents the sigmoid function. The obtained pseudo graph is denoted as ˆG = (ˆ V, ˆ E) with the pseudo features ˆX and pseudo labels ˆ Y .

To ensure that generated samples closely resemble real ones, it is crucial to confine them within the same semantic space. In many data-free knowledge distillation studies in the vision domain, a strategy involves training the generator to be accurately predicted by teacher models [Chen et al., 2019]. Building upon this approach, we further encourage the generator to learn reliable class-wise semantics from each local model by minimizing the following loss:

where ϕc = ∑k∈St ϕck , ˆ Vc denotes the pseudo node with label c, σ(·) is the softmax function, f is the GNN classifier, and LCE represents the cross-entropy loss. Eq. (8) dynamically adjusts the weights based on the global proportion of class-wise knowledge reliability, ensuring that the generated nodes can be precisely predicted by reliable clients.

Furthermore, to mitigate the risk of mode collapse, the generator is encouraged to minimize diversity loss, facilitating the generation of diverse nodes, which is widely applied in generative models [Ding et al., 2018; Mao et al., 2019].

Eq. (9) can reduce the similarity of features across pairs of pseudo nodes, aiming to mitigate redundant features to prevent inefficiencies in subsequent knowledge distillation.

Server-side Knowledge Distillation. The pseudo graph is subsequently employed for knowledge distillation. Owing to the global model being misled by unreliable knowledge, predictions of the global and local models exhibit notable differences in specific nodes. Consequently, for a specific local model, we incentivize the global model to minimize divergence on pseudo-nodes in reliable classes,

where KL(·||·) denotes the Kullback-Leibler divergence function. Conversely, the generator aims to generate pseudo nodes that induce divergence between the global and local model in reliable classes as much as possible. Therefore, the generation stage and the distillation stage compose an adversarial training process, which is formulated as follows:

where λ1 and λ2 are trade-off parameters to control the contribution of different loss functions. The overall process is topology-aware since it is guided by class-wise knowledge reliability, considering class-wise graph homophily. The complete algorithm of FedTAD is presented in Algorithm 1.

5 Experiments

In this section, we conduct experiments to verify the effectiveness of FedTAD. Specifically, we aim to answer the following questions: Q1: Compared with other state-of-the-art

Algorithm 1 FedTAD Execution on Client and Server

Input:

Rounds, T; Local subgraphs, {Gk}k∈St ; Knowledge reliabilities, {ϕk}k∈St ; Server-side training iteration, I; generation iteration, Ig; distillation iteration, Id;

Output:

Global GNNweight, ˜w;

• 1: Client-side Initialize:
• 2: Obtain topology-aware node embeddings via Eqs. (3, 4);
• 3: Obtain the class-wise knowledge reliability via Eq. (5).
• 4: for each communication round t = 1, ..., T do
• 5: Client-side Execute:
• 6: Update local GNN {wk}k∈St with ˜w;
• 7: Train local GNN {wk}k∈St with {Gk}k∈St ;
• 8: Server-side Execute:
• 9: Aggregate local GNN {wk}k∈St into global GNN ˜w;
• 10: for each iteration i = 1, ..., I do
• 11: Generate pseudo node attributes ˆX via Eq. (6);
• 12: Obtain the pseudo adjacency ˆ A via Eq. (7);
• 13: for each inner iteration g = 1, ..., Ig do

14:

Update the generator θ via Eq. (11);

• 15: end for
• 16: for each inner iteration d = 1, ..., Id do
• 17: Update the global model ˜w via Eq. (11);

18:

end for

• 19: end for
• 20: end for

federated optimization strategies, can FedTAD achieve better performance? Q2: Where does the performance gain of FedTAD come from? Q3: Is FedTAD sensitive to the hyperparameters? Q4: Can FedTAD maintain robustness when partial clients participate? Q5: As a hot-plug method, how much performance improvement can FedTAD bring? Q6: What is the time complexity of FedTAD?

5.1 Datasets and SimulationMethod

We perform experiments on six widely used public benchmark datasets in graph learning: three small-scale citation network datasets (Cora, CiteSeer, PubMed [Yang et al., 2016]), two medium-scale co-author datasets (CS, Physics [Shchur et al., 2018]), and one large-scale OGB dataset (ogbn-arxiv [Hu et al., 2020]). More details can be found in Table 1. To simulate the distributed subgraphs in the subgraph-FL, we employ the Louvain algorithm [Blondel et al., 2008] to achieve graph partitioning, which is based on the optimization of modularity and widely used in subgraph-FL fields [Zhang et al., 2021; He et al., 2021].

5.2 Baselines and Experimental Settings

Baselines. We compare the proposed FedTAD with five conventional FL optimization strategies (FedAvg [McMahan et al., 2017], FedProx [Li et al., 2020], SCAFFOLD [Karimireddy et al., 2020], MOON [Li et al., 2021], FedDC [Gao et al., 2022]), two personalized subgraph-FL optimization strategies (Fed-PUB [Baek et al., 2023], FedGTA [Li et al., 2023]), one personalized graph-FL optimization strategy

(GCFL+ [Xie et al., 2021]), and one subgraph-FL framework (FedSage+ [Zhang et al., 2021]).

Hyperparameters. For each client and the central server, we employ a two-layer GCN as our backbone. The dimension of the hidden layer is set to 64 or 128. The local training epoch and round are set to 3 and 100, respectively. The learning rate of GNN is set to 1e-2, the weight decay is set to 5e-4, and the dropout is set to 0.5. Based on this, we perform the hyperparameter search for FedTAD using the Optuna framework [Akiba et al., 2019] on λ1 and λ2 within {10-1 , 10-2 , 10-3 }, and I, Ig, Id within {1, 3, 5, 10}. For each experiment, we report the mean and variance results of 3 standardized training.

5.3 Experimental Analysis

Result 1: the answer to Q1. The comparison results are presented in Table 2. As observed, the proposed FedTAD consistently outperforms baselines. Specifically, compared with FedAvg, FedTAD brings at most 5.3% performance improvement; Compared with FedGTA, which is the optimal baseline in most cases, FedTAD can achieve at most 4.9% performance improvement. The convergence curves of FedTAD and baselines are shown in Fig. 3. As observed, FedTAD consistently converges within fewer communication rounds, demonstrating that FedTAD is suitable for subgraph-FL scenarios with limited communication overhead.

Moreover, to reduce privacy leaks, we also evaluated the performance of FedTAD when 10% Gaussian noise is introduced into the uploaded class-level knowledge reliability. As observed, FedTAD exhibits a performance decline of less than 0.4% and remains superior to the baseline.

Result 2: the answer to Q2. To answer Q2, we focus on the composition of FedTAD, including the class-wise knowledge reliability module on the client side, and the topologyaware knowledge distillation module on the server side.

First, we conducted an ablation study on the Cora datasets with 5/10/20 participating clients to demonstrate the effectiveness of class-level knowledge reliability (Eq. 5). Specifically, we performed two replacements for its calculation. (i) ϕc = 1 (each class is equally reliable, FedTAD-eq for short); (ii) ϕc = |V labeled | (only considering node variation while ignoring topology variation, FedTAD-nv for short). Moreover, we additionally replace the pseudo graph in FedTADeq with the real global graph (FedTAD-r-eq for short). The comparative results are presented in Fig. 4 (a). As observed, the performance achieved by FedTAD-eq, FedTAD-r-eq, and FedAvg are nearly identical, demonstrating that blindly conducting knowledge distillation without considering the classwise knowledge reliability cannot improve the global model, even when relying on real graph data. Moreover, The performance of FedTAD-nv is consistently lower than FedTAD, suggesting that ignoring topology will lead to suboptimal class-wise knowledge reliability.

Afterward, we conducted an ablation study on the Cora dataset with 5 participating clients to investigate the contribution of each loss in the knowledge distillation module. Specifically, we remove three loss functions (Lsem, Ldiv and Ldiverg) for the generator. The experimental results are shown in Fig. 4 (b). As observed, removing any of the losses results in performance degradation for FedTAD, indicating that each loss function plays a crucial role in FedTAD.

Result 3: the answer to Q3. To answer Q3, we assess the performance of FedTAD with 20 participating clients under diverse combinations of trade-off parameters. Specifically, we tune the trade-off parameters λ1 and λ2 within {10-3 , 10-2 , 10-1 , 1}. The sensitive analysis results are presented in Fig. 5. As observed, the performance fluctuation of FedTAD remains consistently below 1%, demonstrating that FedTAD is insensitive to the value of trade-off parameters.

Result 4: the answer to Q4. To answer Q4, we compare FedTAD with four baseline methods, including FedAvg, Fed-PUB, FedSage+, and FedGTA on Cora and ogbn-arxiv datasets with 20 participating clients. The activate fraction varies in {0.2, 0.4, 0.6, 0.8, 1.0}. The experimental results are presented in Table. 4. As observed, FedTAD consistently outperforms the baseline, indicating that FedTAD can maintain robustness with partial client participation.

Result 5: the answer to Q5. To answer Q5, we incorporate FedTAD as a plugin into several FGL (i.e., graph-level FL and subgraph-FL) baseline methods, including GCFL+, Fed-PUB, FedSage+, and FedGTA, and evaluate their performance boost on the ogbn-arxiv dataset with 20 participating clients. The experimental results are presented in Table. 3. As observed, FedTAD consistently improves baselines and achieves at most a 5.1% performance boost.

Result 6: the answer to Q6. To answer Q6, we provide the complexity analysis of FedTAD. On the Client side, calculating the topology-aware node embedding (Eq. 3) costs O(pB) with sparse computation, where p denotes the walk distance, and B denotes the number of generated nodes; class-wise knowledge reliability (Eq. 5) costs O(m), where m denotes the number of edges; On the Server side, the time complexity of model aggregation depends on the chosen optimization strategy; the topology-aware data-free knowledge distillation process costs O(I(IgBf(z + B + Nc) + IdBfNc)), where N denotes the number of participating clients, and z, f, c denote the dimension of sampled noise, node feature, and number of classes, respectively.

6 RelatedWork

Graph Neural Networks. Earlier research on deep graph learning extends convolution to handle graphs [Bruna et al., 2013] but comes with notable parameter counts. To this end, GCN [Kipf and Welling, 2016] simplifies graph convolution by utilizing a 1-order Chebyshev filter to capture local neighborhood information. Moreover, GAT [Veliˇckovi´c et al., 2017] adopts graph attention, allowing weighted aggregation. GraphSAGE [Hamilton et al., 2017] introduces a variety of learnable aggregation functions for performing message aggregation. Further details on GNN research can be found in surveys [Wu et al., 2020; Zhou et al., 2020].

Federated Graph Learning. Mainstream FGL studies can be divided into two settings: (i) Graph-FL: GCFL+ [Xie et al., 2021] and FedStar [Tan et al., 2023]. Each client collects multiple independent graphs, aiming to collaboratively solve graph-level downstream tasks (e.g., graph classification). (ii) Subgraph-FL: each client holds a subgraph of an implicit global graph, aiming to solve node-level downstream tasks (e.g., node classification). Notably, there are currently two main challenges: (a) The global GNN performance degradation caused by subgraph heterogeneity (node and topology variation in multi-client subgraphs). Fed-PUB [Baek et al., 2023] points out this heterogeneity stems from the various label distributions and addresses it through personalized technologies. (b) The information loss caused by missing edges (connections implicitly exist between subgraphs across clients are lost due to distributed storage). Approaches for handling missing edges include FedSage+ [Zhang et al., 2021] and FedGNN [Wu et al., 2021].

7 Conclusion

In this paper, we provide an in-depth investigation of the subgraph heterogeneity problem by individually analyzing the impact of node and topology variation. We demonstrate that subgraph heterogeneity results in variation in the class-wise knowledge reliability. Building on this insight, we propose FedTAD, utilizing topology-aware data-free knowledge distillation to enable the local models to transfer their most reliable knowledge to correct the global model misled by unreliable knowledge. The experimental results demonstrate that FedTAD significantly outperforms state-of-the-art baselines.

Acknowledgments

This work was supported by the Shenzhen Science and Technology Program (Grant No. KJZD20230923113901004), the Science and Technology Planning Project of Guangdong Province under Grant 2023A0505020006, and the National Natural Science Foundation of China under Grants U2001209, 62072486.