Less is More: Federated Graph Learning with Alleviating Topology Heterogeneity from A Causal Perspective

Many thanks for your valuable feedback, we carefully reply your concerns as follows.

Response to Weakness(a): The topology of a graph has a significant influence on node embedding. However, inspired by causal learning, we argue that only the critical topological information is a direct determinant for the class of node representations, which is called the causal factor, while the remaining topological information is called the biased factor.

Response to Weakness(b): Admittedly, the general form of the algorithm's generalizability analysis has its roots in domain generalization theory. Indeed, most studies on domain adaptation and domain generalization further analyze the distribution discrepancy $d_{\mathcal{H}\Delta \mathcal{H}}(\tilde{\mathcal{D}}_s,\tilde{\mathcal{D}}_t)$. Similarly, we analyze the term for the upper bound, but for graph data, it is necessary to consider not only differences in feature distributions, but also differences between topological distributions. Therefore, we perform a customized upper bound analysis, which is not available in the existing work on federated graph learning.

Response to Weakness(c): The computational complexity of FedATH mainly comes from the computation process on the clients and consists of three components. Let us take the computation of a client as an example. First, the forward propagation of dual-GCN costs $O(|E|L)$, where $|E|$ denotes the number of edge and $L$ denotes the dimension of embedding. Second, the computation of edge evaluator costs $O(|E|d)$, where $d$ denotes the feature dimension of nodes. Third, the calculation of HSIC criterion takes $O(N^3)$. Overall, the computational complexity of the proposed FedATH is $O(|E|L+|E|d+ N^3)$.

Response to Weakness(d): We use Python and PyTorch to conduct the simulation environment, and perform the experiments of FedATH and compared experiments on a server equipped with an Intel(R) Core(TM) i9-10980XE processor, an RTX 3090 GPU, and 128 GB of RAM. Adam is selected as the optimizer, and the learning rate is set as 0.001. The numbers of communication rounds and local training epochs are fixed as 100 and 3, respectively.

Response to Weakness(e): We will optimize the figures in the following revision for a better presentation.

Response to Essential References Not Discussed: Study [1] proposes to decouple graph data into features of multiple potential subspaces through a new neighborhood routing mechanism, which mainly aims to mine the decoupling factors behind the data and enhance the interpretability and generalization of the model. However, this mechanism may not be suitable for solving topological heterogeneity problems in federated graph learning, since the separation of multiple decoupling factors is computationally and communication-unfriendly, and it is difficult to judge which factor is really needed to be shared by all clients. In contrast, the proposed FedATH decouples the node representations from the topology level and only shares the causal networks, which is computationally and communicatively acceptable. Study [2] proposes a kernel-based optimization method to reduce the discrepancy between the source and target domains and proves it theoretically. However, as described in Response to W(b), for federated graph learning, the effect of topology on the generalization error needs to be taken into account, and thus we tailor an analytical approach that is not found in the exsiting studies.

[1] Ma, J., Cui, P., Kuang, K., Wang, X., Zhu, W. Disentangled Graph Convolutional Networks. ICML, pp. 4212-4221, 2019.

[2] Muandet, K., Balduzzi, D., Schölkopf, B. Domain generalization via invariant feature representation. ICML, pp. 10-18, 2013.

Thank you very much for your valuable comments, the detailed responses are provided as follows.

Response to Weakness1: We have collected two new federated graph learning methods FGGP [1], FedGTA [2], and compared them with the proposed FedATH. The experimental results are reported in the following table, it can be observed that the proposed FedATH is more superior than the new FGL methods.

[1] Wan, G., Huang W., Ye M. Federated graph learning under domain shift with generalizable prototypes. AAAI, pp. 15429-15437, 2024.

[2] Li, X., Wu, Z., Zhang W., etc. FedGTA: topology-aware averaging for federated graph learning. VLDB, pp. 41-50, 2024.

Response to Weakness2: In fact, when we divide the subgraphs to multiple clients, each client has its own training set and test set. Thus, after federated training, the global model is tested on each client and eventually the average performance of all clients is reported.

Response to Weakness3: We summarize the meanings of main symbols in the following table.

Response to Minor Weaknesses: Thanks for the meticulous advice. We will improve the presentation in a revision version.

Thank you for your professional advices, the detailed responses are written as follows.

Response to Weakness1: The difference between causal and biased graphs is whether they contain critical edge information. We use an edge evaluator to assess the importance of each edge. Subgraphs that contain information about important edges are called causal subgraphs, and subgraphs that contain information about the remaining edges are called biased subgraphs.

Response to Weakness2: In traditional federated learning, the samples are isolated from each other and do not affect each other in model training, the model is only affected by differences in data label distribution or feature distribution. In contrast, for federated graph learning, the samples have connecting edges between them, and the sample representations are affected by connecting edges between different nodes. For example, the same class of nodes may connect different classes of nodes in different clients, then the representations minght be heterogeneous even for same classes of nodes in various clients. Therefore, topological heterogeneity is different from traditional label heterogeneity or feature heterogeneity.

Response to Weakness3: First, to verify that sharing only causal networks is sufficient, we tested the algorithm performance when sharing different network components. In most scenarios, sharing only the causal network can achieve optimal results, which indicates that the causal factor is a key component for affecting the performance of the model. It should also be noted that sharing edge evaluators may also be beneficial to improve the performance, due to the fact that the fusion of edge information from different clients facilitates the quality of the evaluators. Second, the experimental results on Photo dataset with large-scale clients in the following table. We can see that the proposed FedATH still takes the leading position in the scenario of large-scale clients.

Thank you very much for your valuable comments, we response your concerns as follows.

Response to Weakness1: We test the performance of several federated learning methods when all the edges are removed on Cora dataset. It can be seen that although topological heterogeneity causes a decline in federated learning, the topology still favors feature learning. Therefore, it is not the case that removing the topology guarantees that optimal performance will be achieved. We give an upper bound on the generalization error in the theorem. However, for practical purposes, a learning system has a lower bound on its generalization error, but the analysis of the lower bound is difficult to infer.

Response to Weakness2: Validating the adaptability of federated learning algorithms in large-scale client scenarios is necessary. We conduct the experiments with 50, 80, and 100 clients on Photo dataset. It can been seen that the proposed FedATH still outperforms other methods in the scenario of large-scale clients, demonstrating that it has good adaptability in face of more clients.

Response to Weakness3: We have noticed that a review of causal learning is necessary, a review about causal learning is written as follows.

Causal learning [1,2] aims to uncover causal factors that affects the data distributions and has gained widespread attention in machine learning. Mining causal factors is often used in invariant representation learning. For example, Lu et al. [3] aimed to discover the independent variables in the data under the nonlinear setting. [4] further disentangled the causal assumptions into invariant factors and nonstable factors. [5] proposed a causal variational autoencoder that captured the causal structures in the data. In recent years, to learn invariant representations in graph learning, some studies have also absorbed the idea of ​​causal learning. For instance, [6] explored a key subgraph from the initial graph to capture the most important information. [7] proposed a graph contrastive invariant learning to enhance the performance of graph representation. [8] introduced the graph autoencoder to learn the invariant graph representations across multiple domains. Inspired by the causal learning, we believe that the local graph consists of causal subgraph and biased subgraph, and sharing the causal information in them help enhance the generalization of the global model.

[1] Pearl, J. Causality. 2009.

[2] Causality for trustworthy artificial intelligence: status, challenges and perspectives. ACM Computing Surveys, 2025.

[3] Invariant causal representation learning for out-of-distribution generalization. ICLR, 2022.

[4] Invariant and transportable representations for anti-causal domain shifts. NIPS, 2022.

[5] Causalvae: Disentangled representation learning via neural structural causal models. CVPR, 2021.

[6] Learning causally invariant representations for out-of-distribution generalization on graphs. NIPS, 2022.

[7] Graph contrastive invariant learning from the causal perspective. AAAI, 2024.

[8] Learning causal representations based on a gae embedded autoencoder. IEEE TKDE, 2025.

Response to Question1: We have released the code at https://anonymous.4open.science/r/FedATH-9517.

Response to Question2: Label heterogeneity emphasizes that the label distribution for independent samples creates a bias. Topological heterogeneity, on the other hand, emphasizes more on the connecting edge relationship between nodes to produce variance. In other words, label heterogeneity can lead to topological heterogeneity, while topological heterogeneity may not be caused by label heterogeneity.

Response to Question3: The purpose of Eq. 9 is to smooth the predictive distribution output by the biased network, not just for labeled nodes, but for all nodes.