Dear Reviewer h7Za

We sincerely thank you for your insightful feedback and have provided detailed responses to your questions.

W1: Without quantitative analysis of heterogeneity reduction.

We provide a quantitative analysis of heterogeneity reduction at this link.

W2: Lack an analysis of computational complexity & S1: How its sparsification techniques scale with increasing data size or client count.

We analyzed the computational complexity from three aspects:

1. Parameter Sparsification Module:

   • Forward/Backward FLOPs are $O(s_p \cdot d)$, where $s_p$ is the parameter sparsity rate and $d$ is the parameter dimension.
   • Communication costs are reduced to $O(s_p \cdot d)$ via bit-wise mask compression (Section 4.2).
   • Mask alignment requires $O(K \cdot L)$ operations per round, but with small constants for $K$ (clients) and $L$ (layers), its impact is negligible.

2. Graph Sparsification Module:

   • With $T$ GSEs, the local computation is $O(T \cdot |E|)$, where $|E|$ is the number of edges.
   • The message passing process has a complexity of $O(s_g \cdot |E| \cdot d)$, with $s_g$ as the graph sparsification rate.
   • The gating mechanism adds $O(N \cdot D)$ operations, but since $D$ is typically small, its overhead is minimal.

3. OT-based Similarity Computation:

   • Standard OT complexity is $O(n^3)$ for $n$-node graphs, but we reduce this to $O(n \log n)$ using the sliced Wasserstein distance.

Overall, the computational complexity of EAGLES is given by:

Ignoring smaller constants, this simplifies to:

In summary, EAGLES scales linearly with the data size, and the number of clients has minimal impact on the computational complexity.

W3: However, the impact of expert count (Figure 7b) is under-discussed.

As shown in Figure 7b (Appendix D.3), performance improves consistently as the number of experts increases, reaching its peak around 4 experts due to the benefit of richer structural perspectives. Beyond this point, the marginal gains diminish. While Section 5.4 briefly touches on this point, we agree that a more in-depth analysis would further strengthen the discussion.

Q 1.1: Could the authors clarify how the OT method adapts to the federated setting when client graphs have significant structural variations?

In FL settings with significant structural variations, our OT adaptation relies on two key mechanisms. First, the graph synergy expert encodes node contextual features in the $W_{\text{gate}}$ matrix, forming a structure-aware semantic space via hard concrete distribution sampling. This enables OT to assess similarity based on learned semantics instead of raw topology. Second, by treating each client’s structural distribution as a probability measure over this space, we derive client-specific transport plans and similarity weights (Eqs. 20 and 22), which automatically assign lower weights to structurally dissimilar clients. Importantly, only the compact $W_{\text{gate}}$ parameters are transmitted, preserving privacy while allowing the server to compute OT plans with $O(n \log n)$ complexity through entropic regularization.

Q 1.2: Would this method still function efficiently if the number of clients increased substantially?

EAGLES remains efficient even as the number of clients grows significantly. Our framework reduces communication and computation through parameter sparsification (dynamic mask consensus) and OT-based similarity aggregation, minimizing redundant interactions. Experiments (Appendix Fig. 6a & 6b) show that scaling to 100 clients on Ogbn-Proteins and Cora results in only a minor performance drop, while achieving an 18% reduction in Training FLOPS and a 20% reduction in Communication Bytes compared to baselines.

Q 2.1: How does $W_{gate}$ impact parameter sparsification when the number of GSEs increases?

$W_{\text{gate}}$ is a learnable gating parameter. Additional GSEs introduce richer structural diversity, and by integrating sparsified subgraphs obtained from multiple criteria through $W_{\text{gate}}$, the robustness of graph sparsification is enhanced. This reduction in structural redundancy allows for the allocation of different gradient update weights to model parameters during backpropagation, thereby influencing parameter sparsification.

Q 2.2: Would $W_{gate}$ lead to an excessive amount of additional parameters?

The gating parameter matrix $W_{\text{gate}}$ (Eq. (12)) is designed as a lightweight mapping layer with low dimensionality. Specifically, its parameter size is $D \times T$, where $D$ is the input feature dimension and $T$ denotes the number of experts. Since the number of experts is typically a small constant, $W_{\text{gate}}$ scales linearly with $D$, thereby not introducing an excessive number of parameters.

Dear Reviewer Fguv

We sincerely thank you for taking the time to evaluate our work and have adressed your concerns as follows:

W1: Additional empirical studies addressing the significant computational challenges faced by FGL will further strengthen this analysis.

In the theoretical model, the message passing mechanism in GNNs causes the neighborhood size to expand exponentially with the number of layers. For a graph with an average degree of $d$, 1-hop neighborhood covers $d$ neighbors, a 2-hop neighborhood covers $d^2$ neighbors, and an $L$-hop neighborhood covers $d^L$ neighbors [1].

We measured the k-hop receptive fields (k=1,2,3,4) for the amz-photo and Ogbn-arxiv datasets. The results are as follows:

The results show that the receptive fields exhibit a clearly super-linear growth trend, confirming that GNNs indeed face significant computational challenges.

[1]: Xu, K.; Hu, W.; Leskovec, J.; and Jegelka, S. (2019). How Powerful are Graph Neural Networks? arXiv preprint arXiv:1810.00826.

W2: Supplementary experiments addressing the omitted DropEdge.

We conducted experiments on DropEdge on the PubMed, with some of the results presented below (we adopted the original 0.8 retention rate for GCN).

Pubmed

W3: A typo on page seven in Section 5 where "comprehensively" is misspelled as "omprehensively."

Thank you for your careful reading. We have corrected the typo and carefully proofread the manuscript to fix similar issues.

W4: Validate the proposed method on social network graph datasets.

We conducted experiments on the Flickr dataset to validate the effectiveness of the proposed method on social network graph datasets:

Flickr

S1: The manuscript specifies the split ratios for each dataset but does not describe the splitting strategy.

Thank you for pointing that out. We will include additional details on the splitting strategy in the revised manuscript.

Q1: How does the proposed method perform in scenarios where clients have vastly different computational capabilities (e.g., edge devices versus more powerful systems)?

Clients with limited resources can opt for higher sparsity to reduce memory and computation, while more capable machines may choose lower sparsity for better accuracy. Additionally, consensus-based parameter masks and a multi-expert graph sparsification framework ensure that all clients benefit from an efficient, robust model.

Q2: Can the proposed approach still be effective under other non-iid partitioning methods, such as Metis?

We conducted experiments on Cora and ogbn-arxiv, and the results are shown below:

Cora

Ogbn-arxiv

The results show that under Metis partitioning, EAGLES still exhibits superior performance.

Dear Reviewer jagF

We sincerely appreciate your detailed review and invaluable feedback. In the response below, we provide a thorough reply to address your concerns and offer a clearer explanation of our method.

W1: what $W_{gate}$ refers to in eq (12) lacks the necessary explanation in the text.

$W\_{\text{gate}}$ is a learnable weight matrix in the Graph Synergy Expert (GSyE) module that performs gating. It projects the node feature matrix $X$ into a latent space for Hard Concrete sampling, determining which graph sparsification experts to activate. In essence, $W\_{\text{gate}}$ generates gating vectors $z$ that, after thresholding, indicate the significance of each edge in the final sparsified subgraph. We will introduce $W_{\text{gate}}$ in the revised manuscript.

W2: Performance on heterophilic graphs (e.g., arXiv) remains unvalidated.

We conducted experiments on heterophilic graphs using ogbn-arxiv-TA [1] from the HeTGB (Heterophilic Text-attributed Graph Benchmark):

The results show that on heterophilic graphs using ogbn-arxiv-TA, EAGLES also demonstrates superiority.

[1]: Li, S.; Wu, Y.; Shi, C.; and Fang, Y. (2025). HeTGB: A Comprehensive Benchmark for Heterophilic Text-Attributed Graphs. arXiv preprint arXiv:2503.04822.

W3 & S1: Whether the proposed method can speed up the experiments was not explored, and supplement experiments on training time to further verify the efficiency of the method.

We measured the time required for clients to reach the target accuracy on the ogbn-arxiv dataset across different methods, and the accuracy achieved by different methods at the same number of epochs on the ogbn-proteins dataset. The results are presented below:

TIME TO REACH TARGET ACCURACY

ROC-AUC UNDER THE SAME EPOCH

The results show that EAGLES can train the model to a target accuracy in a shorter amount of time, and also achieve higher performance at the same number of epochs. This further verifies that our proposed method can accelerate model training.

Q1: Can the authors provide additional ablation experiments regarding $λ_2$ and $λ_3$ in Eq(19)

We conducted ablation experiments on $λ_2$ and $λ_3$ on the ogbn-arxiv dataset, and the results are presented below:

Ogbn-arxiv (fix $λ_3$ = 1e-6)

Ogbn-arxiv (fix $λ_2$ = 0.1)

Increasing $λ_2$ enforces stricter GSyE constraints, balancing expert contributions and enhancing subgraph homogeneity. In heterogeneous scenarios, raising $λ_2$ from 0.05 to 0.2 leads to a clear accuracy boost. Conversely, while a larger $λ_3$ speeds up sparse parameter identification, it may cause significant accuracy loss; a smaller $λ_3$ permits finer-grained sparsification.

We sincerely appreciate for taking the time to review our manuscript and hope our response will address your concerns and contribute to an improved score.

W1: How the GSyE processes and combines the outputs of various sparsification experts.

In our method, GSyE (Graph Synergy Expert) is used to fuse and refine different subgraphs generated by multiple GSE (Graph Sparsification Expert, aiming to alleviate structure information overfitting during the graph sparsification process. The specific steps are as follows:

1. Multiple GSE generate various versions of subgraphs based on different criteria (Eq. (11)).
2. For the target node v, its node features $\mathbf{X}$ are projected using a learnable matrix $\mathbf{W}_{gate}$ to obtain gating scores $\boldsymbol{z}$, which are then used to generate continuous approximations $\psi(\boldsymbol{z})$ of binary gates, thereby enabling gradient-based optimization (Eq. (13)).
3. The HardStep function (Eq. (14)) is applied to hard-threshold $\psi(\boldsymbol{z})$ to either 0 or 1, determining whether to activate the corresponding expert's recommendation for the edge $e_{ij}$.
4. For each edge $e_{ij}$, if at least one expert recommends retaining it, the edge is marked as a candidate edge; otherwise, it is pruned directly.

Q1: How the hard concrete distribution is optimized?

The hard concrete distribution is applied to the raw gating scores $\boldsymbol{z}$ (Eq. (12)) to produce continuous probabilities $\psi(\boldsymbol{z})$. The HardStep function further binarizes $\psi(\boldsymbol{z})$ into discrete gates—0 and 1. During backpropagation, we employ the Straight-Through estimator [1] to approximate gradients and address the optimization problem.

[1]: Bengio, Y.; Léonard, N.; and Courville, A. (2013). Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprint arXiv:1308.3432.

Q2: How dynamic masking thresholds are computed? + Q3: How client-specific masks are aligned?

In consensus-informed parameter sparsification, dynamic masking thresholds are computed through a layer-wise adaptive process. For the $l$-th layer’s parameter matrix $W^{(l)}$, a threshold vector $\kappa\_{0}^{(l)}$ is dynamically optimized using straight-through estimators (STE) to bypass non-differentiability during backpropagation. Specifically, parameters $W^{(l)}$ are pruned if their absolute values fall below $\kappa\_{0}^{(l)}$, where thresholds are updated via a loss function (Eq. (6)) to maximize sparsity while maintaining performance. Client-specific masks are aligned through a consensus mechanism where overlapping “1”s in binary masks across clients form a unified sparse subnetwork, enabling parameter sharing and communication efficiency.

Q4: How the rollback pruning strategy ensures pruning stability?

The rollback pruning strategy ensures pruning stability by designating, at each predefined pruning checkpoint (for example, every 10% increment in pruning rate), the highest-performing subnetwork within an acceptable accuracy range (±3%). Before moving on to a deeper level of pruning, the method reverts (rolls back) to this optimal subnetwork. This rollback step prevents the accumulation of errors from continuous pruning and mitigates sudden drops in performance, thereby maintaining overall model stability and ensuring effective deep pruning.

Q5: How the framework balances trade-offs between structural similarity, computational efficiency, and model performance in the optimization process (Equation 3)?

Our weighted loss function combines a structural similarity term (enforcing alignment of sparse subnetworks via mask consensus), a computational cost penalty (promoting parameter sparsity to reduce FLOPs), and a task-specific performance loss (e.g., cross-entropy for accuracy). Hyperparameters $λ\_1$ and $λ\_2$ dynamically adjust the trade-offs: higher $λ\_1$ prioritizes mask consistency across clients, while $λ\_2$ controls sparsity-intensity.