FedGT: Federated Node Classification with Scalable Graph Transformer

Thanks for your detailed comments and appreciation!
Q1: The authors are suggested to clearly discuss the case studies in the main paper.
R1: Thanks for the suggestion! Due to the limit of the main paper, we provided some case studies such as the t-SNE visualizations of node embeddings and global nodes in Figure 9. We also provided more experimental results in Appendix. E. We will bring the case studies and more experiment results to the main paper in the final version.

Q2: Leveraging local differential privacy mechanisms to protect privacy in FL is not new.
R2: Local differential privacy is not our main contribution in FedGT. Following previous works [1,2], local differential privacy is added to further protect privacy. Compared with previous works on subgraph federated learning (e.g., the baseline methods we compare in our paper), FedGT has comparable or better privacy protection levels.

[1] Chuhan Wu, Fangzhao Wu, Yang Cao, Yongfeng Huang, and Xing Xie. Fedgnn: Federated graph neural network for privacy-preserving recommendation. KDD, 2021
[2] Tao Qi, Fangzhao Wu, Chuhan Wu, Yongfeng Huang, and Xing Xie. Privacy-preserving news recommendation model learning. EMNLP, 2020.

Q3: Please provide more explanations of the assumptions in Theorem 1.
R3: The assumptions in Theorem 1 are mainly two-fold: (1) Firstly, we assume the attention score function is Lipschitz continuous with constant C. We follow this assumption used in previous works e.g., [3]. Moreover, as indicated by [4], the self-attention is Lipschitz if the inputs are bounded and compact. In the data preprocessing, the input node features are normalized. Therefore, the assumption is satisfied in experiments; (2) Secondly, we assume nodes are equally distributed to the global node. In our experiments, we observe that the clustering in FedGT is not sensitive to graph partitioning and the nodes generally distribute evenly to the global nodes. For example, we probed the distribution of nodes to 10 global nodes in a client on the Cora dataset. There are a total 247 nodes in the client and the number of assigned nodes to global nodes is (27, 28, 22, 24, 25, 22, 21, 24, 25, 29), which is quite close to the uniform distribution. To further satisfy the assumption, we can use balanced clustering that ensures nodes are equally distributed to the global nodes. Therefore, these assumptions are reasonable for FedGT.

[3]Kezhi Kong et al., GOAT: A Global Transformer on Large-scale Graphs, ICML 2023
[4]Kim, Hyunjik et al., The lipschitz constant of self-attention. ICML, 2021.

Q4: Can the authors introduce more about the roles of global nodes in FedGT
R4: The global nodes play critical roles in FedGT. Firstly, in the hybrid attention, each node attends to the sampled neighbors in the local subgraph and a set of global nodes representing the global context. As discussed in Sec.4.1 and the experiments, global nodes can supplement the missing information of missing links. Secondly, the personalized aggregation scheme calculates the similarity scores based on global nodes from different clients because global nodes can reflect the corresponding data distribution of local subgraphs. Therefore, global nodes serve as the nexus between hybrid attention and personalized aggregation.

In FedGT, the global nodes are dynamically updated with an online clustering algorithm (Algorithm 1). The global nodes can be regarded as the cluster centroids of node representations and reflect the overall data distribution of the local subgraph.

Q5: Is FedGT applicable to other subgraph settings
R5: Thanks for the questions! In FedGT, we mainly follow the setting of previous works such as [1]. In the future, we may explore other settings such as clients with varying numbers of nodes. Due to the limit time of rebuttal, we will incorporate systematic studies in the future version.

Q6: In the typical federated learning framework, the number of training samples is considered when aggregating the model parameters. However, Equation (8) only uses the normalized similarity for the weighted aggregation. Why can we ignore the number of training samples here? Or do we assume the number of training samples is equivalent across clients?

R6: Thanks for the question! In our work, we follow the setting of previous works such as [1] where the number of nodes of local graphs is roughly the same. Therefore, we only need to consider the normalized similarity for aggregation and ignore the difference in the number of training samples, which is the same as the aggregation scheme in FED-PUB [1]. In future works, we will systematically explore the influence of the number of nodes and consider it in aggregations.

Q7: The Hungarian algorithm only finds a bijective mapping while optimal transport can be generalized to many-to-many cases, could the authors explain the reason for making a one-to-one alignment of the global nodes?

R7: In FedGT, the Hungarian algorithm is used to calculate the pairwise similarity for personalized aggregation. We use the Hungarian algorithm for its easy implementation and stable performance. To the best of our knowledge, we did not find a suitable many-to-many optimal transport applicable to our setting. Therefore, we adopt the Hungarian algorithm in FedGT. We may explore other optimal transport algorithms in our future works.

Q8: Since the global nodes are dynamically updated during the training, and the representations of the nodes are not stable at the beginning of the training, would this impact the effectiveness of similarity calculation based on the global nodes?

R8: The global nodes are dynamically updated during the training and the performance has fluctuations at the beginning. However, based on the observation, FedGT converges very quickly after several iterations (e.g., Figures 5 and 6). Therefore, the update of global nodes will not impact the effectiveness of similarity calculation.

Thanks for your valuable questions and suggestions!
Q1: How to aggregate global nodes is not clearly illustrated. On page 6, the authors state, “the global nodes are first aligned with optimal transport and then averaged similar to Equation 8”. However, it is unclear which optimal transport method is applied and how the similarity between global nodes from different clients is calculated. The authors should clarify whether the normalized similarity α_ij used for model parameters is also employed for global nodes or if a different similarity calculation is used. Besides, in Algorithm 3 lines 11 and 13, the aligning process for the global nodes seems to be performed twice, which needs a clearer explanation.

R1: Thanks for the question. For aggregating the global nodes, the optimal transport algorithm in Equation 7 is used to align the global nodes and calculate similarity. The normalized similarity α_ij used for model parameters is also employed for global nodes. We will state this more clearly in our revised paper.

As for Algorithm 3 lines 11 and 13, the aligning process is only done once in our algorithm. We restate “Obtain $\hat{\mu}_i^{(r)}$ with aligning and weighted averaging.” to emphasize the global nodes are first aligned and then averaged. We will add more explanations along with the algorithm.

Q2: Since the weighted averaging of local models, i.e., Equation (8), is the same in [1], the authors should provide a discussion or experiment to explain why their similarity calculation is superior to that in [1].

[1] Baek J, Jeong W, Jin J, et al. Personalized subgraph federated learning[C] International Conference on Machine Learning. PMLR, 2023: 1396-1415.

R2: Thanks for the question! The main difference between our weighted averaging and [1] is how to calculate the similarity between clients. [1] proposes to use functional similarity to measure the similarity between clients. However, the quality of the calculated similarity is influenced by the randomly generated input graph (stochastic block model used in [1]). The situation becomes worse when the generated input graph has a different distribution from the original data on each client. Moreover, the generation and transmission of the generated input graph induces extra computation and communication costs.

In our paper, we use the global nodes from each client to calculate the similarity between clients. The global nodes are intrinsic to FedGT and can well reflect the data distribution of each client. The calculated similarity is more stable and not influenced by other artifacts. Therefore, our similarity calculation is superior to that in [1].

We will add these explanations to our paper.

Q3: To show the convergence rate, Figure 5 and Figure 6 did not contain FED-PUB, which is the runner-up baseline in most cases.
R3: In Figures 5 and 6, we select several representative baselines to compare with FedGT. For example, FedPer is the representative personalized FL baseline; FedSage+ is the representative subgraph FL baseline; GraphGPS is the representative graph transformer baseline. In the revised version, we added FED-PUB to compare with FedGT. We can observe that FedGT has better convergence performance than the other baselines including FED-PUB.

Q4: In the ablation study, the authors only conduct experiments on w/o global attention and w/o personalized aggregation. Results of w/o the complete Graph Transformer (i.e., without local attention) should also be provided.
R4: Thanks for the suggestion! In the revised paper, we include the results of w/o graph transformer in our ablation studies (Figure 9). We observed that the performance of FedGT w/o graph transformer drops a lot, which further verifies the effectiveness of graph transformer in subgraph federated learning.

Q5: The authors opt for a consistent number of global nodes n_g across all clients. However, how does the methodology account for scenarios in which clients have a varying number of nodes, with some having significantly more and others noticeably fewer? Is there a suggested approach for determining varying n_g values that are customized to each client’s node count?
R5: Thanks for the question! In our paper, we follow the setting of [1] where the number of nodes of each client is roughly the same. In scenarios where clients have varying numbers of nodes, the number of global nodes n_g can be set proportional to the number of nodes. We will systematically explore such settings in our future works.

We thank the reviewer for the response and support! We are happy to know that most of your questions are addressed. As for the default setting that clients possess a similar number of nodes, we follow the same setting with previous works on subgraph federated learning [1, 2]. In our revised version, we further add additional results in the unbalanced setting (Appendix E.11, Figure. 10, Table 11). The number of nodes of clients can vary 10 times. We compared FedGT with the most competitive baseline FED-PUB. The unbalanced setting is more challenging due to fewer nodes and more missing links. However, we can observe that FedGT is robust to the distribution shifts and can consistently achieve better results than baselines.

We hope our further results and explanations can address your concerns. We will be very grateful if you consider increasing to positive scores to support our work!

[1] Ke Zhang, Carl Yang, Xiaoxiao Li, Lichao Sun, and Siu Ming Yiu. Subgraph federated learning with missing neighbor generation. In NeurIPS 21
[2] Jinheon Baek, Wonyong Jeong, Jiongdao Jin, Jaehong Yoon, and Sung Ju Hwang. Personalized subgraph federated learning. In ICML 23

We thank you for the detailed reviews and constructive comments!
Q1：How Graph Transformer deals with the missing links is unclear.
R1：We discussed how Graph Transformer deals with missing links in introduction, Section 4, and Appendix B. FedGT tackles missing link issues with the powerful graph transformer architecture and the global nodes. Most GNNs follow a message-passing paradigm that is likely to make false predictions with altered or missing links. In contrast, Graph Transformer is robust to missing links due to its global attention scheme. Moreover, the global nodes in FedGT capture the global context and get further augmented with personalized aggregation, which can supplement the missing information of cross-subgraph links. Finally, extensive experiments on 6 datasets demonstrate FedGT can overperform state-of-the-art baselines based on GNNs. As pointed by other reviewers, dealing with missing links with graph transformer is well motivated. We will state more clearly in our revised paper.

Q2: The assumption that nodes are equally distributed to the global nodes seems unrealistic due to graph partitioning.
R2: In FedGT, each client curates a set of global nodes to approximate the global context of the corresponding subgraph. As in Algorithm 1, the global nodes are updated with an online clustering algorithm as the cluster centers. In our experiments, we observe that the clustering in FedGT is not sensitive to graph partitioning and the nodes generally distribute evenly to the global nodes. For example, we probed the distribution of nodes to 10 global nodes in a client on the Cora dataset. There are a total 247 nodes in the client and the number of assigned nodes to global nodes is (27, 28, 22, 24, 25, 22, 21, 24, 25, 29), which is quite close to the uniform distribution. To further satisfy the assumption, we can use balanced clustering [1,2] that ensures nodes are equally distributed to the global nodes. Therefore, the assumption is realistic for FedGT.

[1]Weibo Lin et al., Balanced clustering: a uniform model and fast algorithm. IJCAI, 2019.
[2]Bienkowski, Marcin, et al. Improved Analysis of Online Balanced Clustering." International Workshop on Approximation and Online Algorithms. 2021.

Q3: Theorem is not rigorous as it is a known fact that more nodes less error [3]
R3: Thanks for mentioning the related work [3]. Generally, our theorem aligns well with the fact that more nodes less error. In Figure 5(b), we show that the accuracy generally increases with more global nodes. Due to the randomness of training and the redundant noise brought by global nodes, the classification may have fluctuations with a larger number of global nodes.

[3] Kim, Hyunjik, George Papamakarios, and Andriy Mnih. "The Lipschitz constant of self-attention." International Conference on Machine Learning. PMLR, 2021.

Q4: Local LDP does not guarantee privacy for sensitive node features, edges, or neighborhoods on distributed graphs [2,3]. Using LDP does not reflect an actual privacy guarantee for this case.
R4: We thank the reviewer for mentioning the related works [4,5] on the private analysis of graph data. We will cite and discuss them in our paper. In our work, we do not directly upload graph statistics. Instead, we apply LDP to the uploaded model parameters and learned global node representations following previous works [6,7] to protect privacy. Moreover, local differential privacy is not our main contribution to FedGT. Compared with previous works on subgraph federated learning (e.g., the baseline methods we compare in our paper), FedGT has comparable or better privacy protection levels.

[4] Imola, Jacob, Takao Murakami, and Kamalika Chaudhuri. "Locally differentially private analysis of graph statistics." 30th USENIX security symposium (USENIX Security 21). 2021.
[5] Kasiviswanathan, Shiva Prasad, et al. "Analyzing graphs with node differential privacy." Theory of Cryptography: 10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan, March 3-6, 2013. Proceedings. Springer Berlin Heidelberg, 2013.
[6] Chuhan Wu, Fangzhao Wu, Yang Cao, Yongfeng Huang, and Xing Xie. Fedgnn: Federated graph neural network for privacy-preserving recommendation. KDD, 2021
[7] Tao Qi, Fangzhao Wu, Chuhan Wu, Yongfeng Huang, and Xing Xie. Privacy-preserving news recommendation model learning. EMNLP, 2020.