$S^2$FGL: Spatial Spectral Federated Graph Learning

Dear Reviewer uVfb:

Thank you for your encouraging comments on our work. We hope that our responses below will address your concerns and reinforce your positive evaluation.

Weakness

W1: A more detailed analysis of existing methods and their limitations is required, particularly for the FGL baselines.

A1: In response to your concerns, we further elaborate on the deficiencies of the FGL baseline methods evaluated in our study. Specifically, FedSage+ seeks to reconstruct subgraphs by locally training a neighborhood generator. FedGTA determines aggregation weights using mixed moments of neighbor features and local smoothing confidence. FGSSL aligns similarity matrices between local and global GNNs while employing node-level contrastive learning. Similarly, FGGP applies contrastive learning, integrating clustering prototypes to enhance prediction accuracy. FedPub utilizes similarity-based clustering on random graphs at the client side and employs local masks to incorporate the global model. FedStar introduces a specialized channel for processing graph structure, sharing only this channel’s parameters. In summary, existing approaches fail to address two critical issues: spatial label signal disruptions and spectral client drifts. Label signal disruptions weaken the semantic recognition ability of GNNs in FGL, thereby reducing its overall effectiveness. Additionally, spectral client drifts hinder collaboration among clients, making it difficult to establish an efficient spectral signal propagation paradigm. Our work aims to address this gap by focusing on these two underexplored aspects.

W2: Why does the second method align only the high-frequency and low-frequency spectral features, rather than other components?

A2: Both low-frequency and high-frequency areas of the graph spectrum are critical and highly representative. Low-frequency components typically capture the global structural properties of the graph, for instance, the second smallest eigenvalue indicates graph connectivity. Conversely, high-frequency eigenvectors contain detailed local information. Directly matching all eigenvectors is computationally prohibitive. Instead, selecting those associated with the smallest and largest eigenvalues reduces computational complexity while preserving the graph's essential structural characteristics.

We are grateful for your encouraging feedback and hope that our response has effectively addressed your concerns!

Dear Reviewer yo13:

Thank you for your thoughtful review and for acknowledging the value of our work. We hope the responses provided below will clarify your concerns and contribute to a more favorable evaluation.

Weakness

W1: The authors should conduct a hyperparameter study for the NLIR and include the performance comparison with FedTAD.

A1: Thank you for your thoughtful suggestions. We have added experiments regarding the prototype count hyperparameters in NLIR to Table 1 and included comparison experiments with FedTAD in Table 2. The results in Table 1 demonstrate the stability of the NLIR method under variations in prototype counts. The results in Table 2 show that our method consistently outperforms FedTAD, validating its efficiency. We will include these results in the final version.

Table 1: Hyper-parameter study of prototype count in NLIR

Table 2: Performance comparison with FedTAD

W2: The authors should clarify the key advantages of the spectral solutions over spatial solutions in mitigating spectral client drifts.

A2: Methods that rely on the spatial domain fail to capture signal propagation patterns across different frequencies in the graph spectra. As a result, client drifts caused by GNNs overfitting to local frequency signal propagation paradigms are challenging to resolve for them. Instead, our method performs spectral reconstruction based on the adjacency awareness of different GNNs and promotes the alignment of local spectral signal propagation patterns with the globe. This approach enables the formation of a generalizable and strong spectral signal propagation paradigm, effectively mitigating spectral client drifts.

Thank you again for your efforts in reviewing our work. We hope our rebuttal has clarified and addressed your concerns!

Dear Reviewer svqb:

We sincerely appreciate your time and effort and hope that our responses will address your concerns and lead to an updated score.

Experimental Designs Or Analyses

There are only experiments with ACM-GCN.

A1: $S^2FGL$ is a backbone-agnostic framework designed to address label signal disruption and spectral client drifts. In light of your thoughtful comment, we have incorporated results using GCN in Table 1, showing that $S^2FGL$ consistently outperforms current methods. The results will be included in the final version.

Table 1: Performance comparison using GCN.

Weakness

W1: Why NLIR is novel.

A2: For the target problem, we innovatively focus on label signal disruption (LSD), which brings significant semantic degradation. Though existing methods mitigate edge loss structurally, they ignore the semantic degradation under LSD and fail to offer targeted solutions. Therefore, current FGL methods inevitably suffer from limited GNN semantic recognition ability.

Methodologically, existing prototype-based approaches exhibit two critical limitations under LSD: insufficient semantic richness and semantic deviation under structural biases. Correspondingly, we propose a novel metric $\Lambda^\text{SALC}$ (Eq. 3 and 4, Page 4), which jointly accounts for label influence and structural representativeness to effectively mitigate LSD.

W2: The similarity matrix requires second-order complexity. The projection requires doing EVD on a dense Laplacian.

A3: First, the computation of the feature similarity matrix is widely accepted in FGL. Specifically, FGSSL leverages it to align structural consensus, FGGP utilizes it for contrastive learning, and FedGL employs it for structure updates. Distinctively, we align the reconstructed spectrum to enable a highly expressive signal propagation scheme against spectral drifts, achieving the best performance.

Second, our method does not require an EVD on a dense Laplacian. Since only partial eigenvectors are needed, we leverage SciPy's sparse solver eigsh with $O(r\cdot nnz\cdot I)$. $r$ denotes the number of eigenvectors needed, $nnz$ is the non-zero element, and $I$ is required iterations.

W3: The authors need to verify the existence of the spectral challenge and prove the method can mitigate it.

A4: We kindly note that we have demonstrated the spectral challenge in Fig. 1(b). For further validation, we compute the Pearson correlation between spectral shift (KL divergence of a client's eigenvalue distribution from the global) and local accuracy of the global GNN under FedAvg. After runs under five random seeds, they are -0.39 (Cora), -0.27 (Citeseer), and -0.34 (Pubmed), indicating that greater spectral shift leads to higher inconsistency with global optimization and confirming spectral drifts.

FGMA facilitates a generic signal propagation paradigm across clients to mitigate spectral drifts. For validation, Table 2 shows that FGMA is more effective under higher spectral heterogeneity, providing strong evidence for its specificity and effectiveness. Spectral heterogeneity here is the average KL divergence among clients' eigenvalue distributions.

Table 2: Correlation between Spectal Heterogeneity and FGMA Improvement on FedAvg.

W4: Lack of complexity analysis.

A5: For a $k$-layer GNN with batch size $b$ and feature dimension $f$, the propagated features $X^{(k)}$ have a space complexity of $O((b+k)f)$, while linear regression has $O(f²)$. Key parameters include $n$, $m$, $c$ (nodes, edges, classes), $s$ (augmented nodes), $g$ (complemented neighbors), $p$ (trainable prototype matrix dimension), $Q$ (query set size for contrastive learning), and $N$ (selected clients per round). Analysis in Table 3 shows that $S^2FGL$ achieves top performance with reasonable overhead.

Table 3: Complexity analysis. Best in bold and second with underline.

Thank you for your valuable feedback and hope that our rebuttal adequately addresses your concerns!

Dear Reviewer yM48:

We sincerely appreciate the time and effort you have invested in reviewing our paper, as well as your favorable assessment of the motivation and design of our method. We hope that our rebuttal has effectively addressed your concerns.

Weakness

W1: The authors should consider conducting experiments with a larger number of clients to ensure that NLIR remains effective in configurations with more clients

A1: We kindly emphasize that our experimental setup adheres to standards in existing FGL research, incorporating suitably configured numbers of clients. Nonetheless, to address your concerns, we conducted additional experiments with a substantially larger number of clients on the large-scale graph dataset arxiv-year. The results in Table 1 confirm the robustness and effectiveness of our method in large-scale client settings.

Table 1: NLIR performance under large client scale.

W2: The ablation study should incorporate error bars.

A2: In response to your concern, we incorporate error bars in Table 2 as follows. We will incorporate your suggestions in the final version.

Table 2: Ablation study of $S^2FGL$ with error bars

Other Comments Or Suggestions

A3: We are grateful for your feedback regarding the typo. We will implement the revision in the final version.

We sincerely appreciate your thoughtful review comments and hope that our rebuttal has addressed the concerns you raised!