PaperlayerView exact revision on arXiv

Source-linked AI summary

Rethinking One-Shot Federated Graph Learning: Training-Free Statistical Estimation

Shutong Zheng, Sijia Chen

arXiv:2609.06154v1cs.LG

TL;DR

Under extreme non-IID conditions, local GNN training in one-shot federated graph learning can cause cross-client representation misalignment. SPEAR replaces local optimization with training-free prototype estimation and reliability-adaptive aggregation; across seven benchmarks it achieves state-of-the-art performance while reducing computational overhead by orders of magnitude.

  • Problem

    Under extreme non-IID conditions, local GNN training can overfit to client-specific patterns and misalign representations that cannot be corrected through one-shot aggregation.

    Source: §1 · pp. 1–2

  • Method

    SPEAR estimates topology-smoothed local prototypes and aggregates them with sample-size-adaptive shrinkage, without local gradient optimization or iterative communication.

    Source: §1 · p. 2, §4.1 · p. 3, §4.2 · p. 5

  • Results

    Across seven benchmarks, SPEAR achieves state-of-the-art performance and orders-of-magnitude lower computational overhead than existing training-based, distillation-based, and generative methods.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The results support training-free statistical estimation as an effective approach to robust one-shot federated graph learning under extreme heterogeneity.

    Source: §6 · p. 7

    The setting assumes clients hold private local subgraphs with unavailable cross-client edges and label distributions modeled by a Dirichlet parameter.

    Source: §3.1 · p. 2

Abstract

from arXiv · show

One-shot federated graph learning generally aims to train Graph Neural Networks (GNNs) across clients with disconnected subgraphs in a single communication round. Existing methods predominantly design advanced optimization strategies under the premise that local GNN training is indispensable. However, empirical observations reveal that under extreme non-IID conditions, local GNN training suffers from severe cross-client representation misalignment, becoming a major source of error rather than a remedy. Motivated by this, we reformulate one-shot FGL as a statistical estimation problem. We propose SPEAR (Statistical Prototype Estimation with Adaptive Reliability), a completely training-free framework that directly computes topology-smoothed class prototypes from local graphs in the original feature space. The server then aggregates these prototypes using a sample-size-adaptive shrinkage estimator that down-weights unreliable local estimates, producing robust global class prototypes. Extensive experiments across seven benchmarks demonstrate that SPEAR consistently achieves state-of-the-art accuracy under extreme heterogeneity. Moreover, SPEAR delivers at least an order-of-magnitude speedup over all baselines, reaching several orders of magnitude against generative and distillation-based methods. Our findings suggest that training-free statistical estimation, rather than local GNN optimization, provides the key to robust and efficient one-shot federated graph learning. The code is available at https://github.com/Yodeesy/SPEAR .

1 Introduction

SPEAR reframes one-shot federated graph learning as training-free statistical estimation after local GNN training is found to misalign representations under extreme non-IID conditions. Across seven benchmarks, it achieves state-of-the-art performance while reducing computational overhead by orders of magnitude.

1 Introduction

  • Federated graph learning addresses graph-structured data split across clients, where partitioning severs global topology and creates structural heterogeneity.Federated learning provides a privacy-preserving mechanism for distributed training without exposing raw local data.Source: §1 · p. 1
  • Across seven benchmarks, SPEAR achieves state-of-the-art performance and reduces computational overhead by orders of magnitude compared with existing one-shot FGL methods.On Coauthor-CS at β = 0.05, the time-performance frontier reports superior performance and multi-magnitude speedups across client scales.Source: §1 · pp. 1–2
  • One-shot FGL limits collaboration to a single communication round, avoiding the repeated synchronization that can impose prohibitive bandwidth and latency overheads.Source: §1 · p. 1
  • Under extreme non-IID conditions, local GNN training overfits to client-specific labels and structure, producing representation misalignment that one-shot aggregation cannot effectively correct.This motivates asking whether local parameter optimization is necessary for extreme one-shot FGL.Source: §1 · pp. 1–2
  • SPEAR replaces local GNN optimization with topology-smoothed prototype estimation and reliability-adaptive shrinkage to construct global prototypes without gradients or iterative communication.Local prototypes are estimated in the original feature space, and the server adapts shrinkage to estimate reliability.Source: §1 · p. 2

2 Related Work

Prior federated graph learning methods address graph heterogeneity through repeated communication or one-shot pipelines that still train local GNNs. Training-free statistical learning has reached federated non-graph settings, leaving graph relational structure unaddressed.

2.1 Multi-Round Federated Graph Learning

  • Multi-round FGL methods mitigate partition-induced graph heterogeneity through repeated client-server exchanges, but retraining and retransmission scale poorly under bandwidth or latency constraints.Source: §2.1 · p. 2

2.2 One-shot Federated Graph Learning

  • One-shot FGL methods use distinct graph synthesis, proxy-model, or codebook strategies, yet each still optimizes a local GNN before client information is shared.Source: §2.2 · p. 2

2.3 Training-Free Statistical Learning

  • Training-free federated statistical methods for images and text use independent feature vectors, while discarding the relational structure central to graphs.This gap motivates SPEAR’s training-free statistical formulation of federated graph learning.Source: §2.3 · p. 2

3 Preliminaries and Motivation

The setup assigns each client a private subgraph with unavailable cross-client edges and label distributions controlled by a Dirichlet parameter. The motivation reports that local neural optimization disrupts raw-feature alignment under extreme non-IID conditions, supporting a training-free alternative.

3.1 Background

  • Smaller Dirichlet β induces increasingly severe structural and label heterogeneity across clients, whose cross-client edges are unavailable.Each client holds a private local subgraph with node features and labels.Source: §3.1 · p. 2
  • Standard FGL represents local subgraphs with parameterized GNNs, whose layers combine structural propagation, trainable weights, and nonlinear activation.Source: §3.1 · p. 2
  • In one-shot FGL, clients transmit local graph summaries once, and the server constructs a global solution without subsequent refinement.Source: §3.1 · pp. 2–3

3.2 Motivation

  • Raw features form shared semantic regions across clients, while local neural training disrupts that alignment; FedProto and FedGTA show more cluster distortion than FedAvg.The cited UMAP visualization concerns Cora at β = 0.05.Source: §3.2 · p. 3, Figure 2 · p. 3
  • Raw features yield a positive cosine Silhouette Score on Cora, whereas gradient-based methods fall below −0.29 for FedProto and FedGTA.The reported degradation also appears across broader benchmarks and baselines, motivating abandonment of local optimization.Source: §3.2 · p. 3

4 Methodology

SPEAR replaces trainable local GNNs with topology-smoothed class prototypes, then calibrates and aggregates them using sample-size-adaptive shrinkage. Its server produces global prototypes for cosine-similarity inference without iterative communication or gradient optimization.

4.1 Topology-Smoothed Prototype Estimation

  • Clients apply truncated PPR to L2-normalized features using a self-looped, row-normalized transition matrix, propagating features for a small number of steps without trainable transformations.The propagation weight α controls neighborhood contribution; smaller α retains more of the original features, and T = 2 is given as an efficient example.Source: §4.1 · p. 3
  • Each client averages the smoothed representations of its labeled nodes by class and sends those prototypes with class sample counts in one communication round.This replaces transmission of a bulky GNN model with compact prototypes and counts.Source: §4.1 · p. 3

4.2 Reliability-Adaptive Prototype Shrinkage

  • Under the stated statistical assumptions, the optimal shrinkage estimator has lower expected MSE than the uncalibrated local estimate whenever τ^2 > 0.The analysis models local prototype noise as independent, zero-mean, isotropic, and inversely proportional in variance to sample size.Source: §4.2 · p. 4
  • Smaller class sample sizes increase shrinkage toward the peer mean, while the server sample-weights calibrated prototypes to form each global prototype.When only one client observes a class, the peer mean is set to that client's prototype, disabling shrinkage for that observation.Source: §4.2 · pp. 4–5
  • For inference, the server classifies nodes by cosine similarity between their topology-smoothed features and the global prototypes, bypassing parameterized layers.The test graph is smoothed using the same PPR scheme described for local features.Source: §4.2 · p. 5
  • SPEAR is gradient-free; client computation is O(T|E_k|F + N_kF), one-shot communication is O(CF) per client, and server shrinkage is O(KCF).The paper links this lightweight design to efficiency gains evaluated in Section 5.2.Source: §4.2 · p. 5

5 Experiments

Across seven node-classification benchmarks under a shared transductive evaluation protocol, SPEAR outperforms baselines while reducing communication and runtime. Robustness, ablation, and representation analyses examine its behavior across perturbations and heterogeneity levels, the interaction of its components, and the calibration of global prototypes.

5.2 Performance Comparison

  • Under extreme non-IID settings (β = 0.05), SPEAR consistently outperforms all multi-round and one-shot baselines by a significant margin.The evaluation uses seven graph datasets and a shared transductive protocol in which the server evaluates centrally on the complete test graph.Source: §5.1 · pp. 5–6, §5.2 · p. 6
  • Communication falls from 7246 MB to 18.8 KB on CiteSeer, and wall-clock time is up to 111× lower than multi-round FedAvg.SPEAR transmits topology-smoothed prototypes rather than model parameters or gradients and also outpaces the fastest one-shot baseline, GHOST.Source: §5.2 · p. 6

5.3 Robustness Analysis

  • With edge noise (ρ = 0.5) and feature noise (η = 0.5), degradation stays within 0.6% and 1.0%, respectively, across four datasets.The robustness table compares performance under each perturbation with the clean setting.Source: §5.3 · p. 6, Table 2 · p. 6
  • Across β = 0.05 to 0.25, SPEAR maintains an advantage over baselines, largest under extreme heterogeneity; accuracy is also stable across an order of magnitude of γ.Increasing α can help on homophilous graphs but hurt on heterophilous graphs, so the experiments use a conservative, dataset-agnostic α.Source: §5.3 · pp. 6–7, Figure 4 · p. 6

5.4 Ablation Study

  • PPR without shrinkage reduced Amazon-Computers accuracy from 74.33% to 62.84%, while shrinkage alone yielded negligible gains; together, the modules are complementary.The ablation compares component-removed variants with the complete SPEAR estimator across seven datasets.Source: §5.4 · p. 7, Table 4 · p. 7

5.5 Representation Analysis

  • On Cora, average cosine distance to true class centroids drops from 0.3217 for local prototypes to 0.1997 for global prototypes calibrated by shrinkage.The UMAP depicts PPR-smoothed features, uncalibrated local prototypes, and calibrated global prototypes.Source: §5.5 · p. 7, Figure 5 · p. 7

6 Conclusion

SPEAR reframes one-shot federated graph learning as training-free statistical estimation, with prototype shrinkage replacing local GNN optimization. The paper reports robust accuracy and lower overhead under extreme heterogeneity, while noting simplifying assumptions in its shrinkage analysis.

6 Conclusion

  • Across seven benchmarks, SPEAR achieves superior classification accuracy under extreme heterogeneity while reducing computational and communication overhead by orders of magnitude.The conclusion associates local optimization under extreme non-IID conditions with cross-client representation misalignment.Source: §6 · p. 7

A Broader Impact

  • Under extreme non-IID conditions, statistical estimation is presented as a complementary alternative to gradient-based optimization for one-shot FGL.The broader-impact discussion says local optimization often collapses under high variance, small samples, and severe graph truncation.Source: A Broader Impact · p. 11
  • SPEAR uses one communication round and zero local training overhead, reducing costs relevant to resource-constrained edge deployment.Source: A Broader Impact · p. 11
  • Experiments suggest SPEAR's statistics-driven aggregation is resilient to representative data-poisoning attacks without defense-specific modules.It communicates one round of class-level prototypes, reducing the attack surface relative to repeated model-update exchange.Source: A Broader Impact · p. 11

B.1 SPEAR Algorithm

  • The SPEAR pipeline is training-free and follows a strict one-shot communication paradigm.Clients upload local prototypes and sample counts, and the algorithm applies reliability-adaptive shrinkage.Source: §B.1 · pp. 11–12

B.2 Complexity Analysis

  • Client computation scales as O(T|E_k|F + N_kF), per-client communication as O(CF), and server computation as O(KCF).The client computation uses sparse PPR propagation and local prototype construction, without dense O(N_kF^2) transformations or epoch-wise iteration.Source: §B.2 · p. 12

C.1 Proof of Proposition 1

  • The proof states that shrinkage strictly reduces expected error relative to the uncalibrated local estimate under the stated assumptions.Source: §C.1 · p. 13

C.2 Discussion on Theoretical Simplifications

  • The theory treats smoothed node samples as approximately independent and peer-mean variance as constant; the authors identify both as simplifying approximations.Topological overlap may make effective sample size smaller than the raw node count, while the shrinkage scale γ is tunable to absorb peer-variance approximation error.Source: §C.2 · pp. 13–14

C.3 Empirical Characterization of Prototype Estimation Errors

The section tests whether prototype errors fall across SPEAR's stages, comparing local estimates, naive averaging, and reliability-adaptive shrinkage. The final prototypes have the smallest reported errors, consistent with the shrinkage risk prediction.

C.3 Empirical Characterization of Prototype Estimation Errors

  • The comparison tracks average cosine distance to true full-graph class centroids across local prototypes, naive averages, and SPEAR's final global prototypes.The experiment evaluates the predicted error reduction rather than verifying Assumption 1 itself.Source: §C.3 · p. 14
  • SPEAR reduces residual prototype error nearly an order of magnitude on examples including Coauthor-CS (0.199 → 0.024) and ogbn-arxiv (0.105 → 0.000).It has the smallest estimation errors across all datasets in the reported comparison.Source: §C.3 · p. 14, Table 1 · p. 14
  • Naive averaging partially reduces local-prototype errors, while SPEAR's reliability-adaptive shrinkage consistently yields the smallest errors.These empirical results are described as consistent with Proposition 1's prediction that shrinkage reduces estimation risk.Source: §C.3 · p. 14

D Datasets and Experimental Setup

The experiments use seven graph benchmarks with dataset-specific splitting protocols and fixed SPEAR hyperparameters. Visual comparisons report weaker class separation for some one-shot baselines and show calibrated prototypes near class centers across the benchmarks.

D. Datasets and Experimental Setup

E.1 Visual Comparison of Baselines

  • With β = 0.05, FedCVAE and FedSD2C show weaker class separation than even multi-round FedAvg; GHOST and OASIS retain more structure but remain less separated than raw features.The passage characterizes the latter methods' computational and communication burdens as impractical for resource-constrained edge deployment.Source: §E.1 · p. 15

E.2 Global Prototype Calibration Across Datasets

  • Across all seven benchmarks, global prototypes are reported near their respective true geometric class centers under extreme non-IID conditions.The section presents this as visual evidence of calibration robustness.Source: §E.2 · p. 15

E.3 Quantitative Representation Analysis

The representation analysis finds that SPEAR largely preserves raw-feature alignment, while gradient-based local optimization degrades it under extreme non-IID conditions. As client counts rise, SPEAR's reported accuracy remains stable while training-based baselines degrade.

E.3 Quantitative Representation Analysis

  • SPEAR tracks or slightly exceeds raw-feature Silhouette Scores on six of seven datasets; on Amazon-Computers, its score is −0.0856 versus −0.0772 for raw features.Gradient-based methods drive scores heavily negative across almost all datasets; Table 3 reports scores under β = 0.05.Source: §E.3 · pp. 15, 17, Table 3 · p. 17
  • Silhouette Score alone does not guarantee semantic-label alignment, so representation cohesion should be interpreted jointly with downstream classification accuracy.FedAvg's Coauthor-CS Silhouette Score is 0.3149 despite downstream accuracy of 25.33%, versus SPEAR's 90.81%.Source: §E.3 · p. 17

F.1 Scalability Across Varying Numbers of Clients

  • As client count increases, training-based GHOST and OASIS show high variance and performance degradation, while SPEAR outperforms the strongest one-shot baselines across client scales.Source: §F.1 · p. 17
  • On ogbn-arxiv, SPEAR accuracy varies only 0.18% across K = 5 to K = 100, from 37.19% to 37.37%.The passage attributes this stability to stronger shrinkage penalties for local prototypes as per-class sample sizes decrease.Source: §F.1 · p. 17

F.2 Complete Hyperparameter Sensitivity Analysis

SPEAR is broadly stable to shrinkage intensity and propagation depth, while the best teleport probability depends on graph homophily. The authors also examined semantic peer selection and degree-augmented reliability before adopting a simpler design.

F.2 Complete Hyperparameter Sensitivity Analysis

  • SPEAR remains stable across an order of magnitude of γ and across propagation depths T, with γ degrading only when disabled or excessively large.Unlike deep GNNs, its training-free forward diffusion maintains stable accuracy at larger T without catastrophic over-smoothing.Source: §F.2 · p. 18
  • Teleport probability α trades off local initial features against structural information from truncated neighborhoods, making its useful setting graph-dependent.Increasing α benefits strongly homophilous datasets but can hurt heterophilous graphs.Source: §F.2 · p. 18

G Design Philosophy and Ablation on Heuristic Strategies

  • The design exploration considered semantic-similarity peer selection and reliability weighting by both sample size N and average degree d.These were investigated as alternatives to straightforward average fusion and sample-size-based reliability.Source: G Design Philosophy and Ablation on… · pp. 18–19

F.2 Complete Hyperparameter Sensitivity Analysis

  • On homophilous graphs, raising α to 0.80 increased Cora accuracy from 63.35% to 73.93%; on Texas, α ≥0.30 lowered accuracy from 75.68% to 64.19%.The analysis attributes the contrast to stronger smoothing aligning same-label neighbors in homophilous graphs but introducing cross-class noise in heterophilous graphs; α = 0.15 is the conservative default.Source: §F.2 · p. 18, Figure 3 · p. 19

G.1 Ablation on Heuristic Peer-Selection

Complex peer-selection heuristics do not consistently improve SPEAR, while sample-size weighting with average fusion retains robust performance under the tested targeted poisoning attack. The discussion also identifies a boundary: low-pass smoothing can be detrimental on heterophilic graphs, which SPEAR cannot exploit constructively.

G.1 Ablation on Heuristic Peer-Selection

  • Semantic selection and degree-augmented reliability provide no consistent gains over streamlined SPEAR across the evaluated graph types.The authors attribute the lack of gains to distorted local embedding spaces and structural fragmentation; semantic matching can overfit local noise, while local degree adds unpredictable topological variance.Source: §G.1 · pp. 19–20, Table 5 · p. 19

G.2 Robustness Evaluation under Byzantine Attacks

  • Under attack from three malicious clients, semantic selection provides no robust defense, while baseline SPEAR maintains 62.73% accuracy on Cora at β = 0.05.The reported accuracy is nearly identical to clean-data performance; the authors attribute robustness to valid class samples concentrated in benign clients and their resulting sample weights.Source: §G.2 · p. 20, Table 6 · p. 20

H Limitations

  • The authors identify limitations in the framework, including the restricted usefulness of topological smoothing on heterophilic graphs.Their conservative α = 0.15 limits cross-class contamination but does not resolve the lack of constructive heterophily-aware propagation.Source: H Limitations · p. 20, §H.1 · pp. 20–21

H.1 Topological Utilization on Heterophilic Graphs

  • On heterophilic graphs, removing PPR sometimes improves results, and SPEAR lacks a mechanism to constructively use heterophilic edges.Removing PPR improves Chameleon from 38.89% to 42.11% and Roman-Empire from 42.56% to 44.28%; adaptive high-pass or band-pass filters are proposed as future work.Source: §H.1 · pp. 20–21, Table 7 · p. 21

H.2 The Capacity Boundary of Training-Free Paradigms

SPEAR’s advantage depends on the data regime: training-based methods can catch up as heterogeneity relaxes, though the crossover varies with dataset and hyperparameters. The paper also notes that prototype sharing lacks formal privacy guarantees and that differential-privacy noise can conflict with small-sample variance reduction.

H.2 The Capacity Boundary of Training-Free Paradigms

  • On Cora, training-based methods can narrow and sometimes surpass SPEAR as β rises toward 1.0, while on Coauthor-CS SPEAR reaches 91.01% versus FedAvg’s 80.32% after 200 rounds at β = 1.0.The capacity boundary varies with dataset properties and SPEAR’s hyperparameter configuration; the paper leaves its precise theoretical characterization open.Source: §H.2 · p. 21, Figure 4 · p. 22
  • SPEAR is presented as a safeguard for extreme data scarcity and skew, not a universal replacement for deep training-based approaches.The paper identifies characterizing the crossover across architectures, graph topologies, feature densities, and hyperparameter regimes as an open question.Source: §H.2 · p. 21

H.3 Privacy and the Tension with Small-Sample Variance

  • Prototype-only communication exposes less information than gradient-based FGL but has no formal privacy guarantee, and prototypes may remain vulnerable to reconstruction or membership inference.Differential-privacy perturbations increase small-sample prototype variance, counteracting the estimator’s variance-reduction objective.Source: §H.3 · p. 22
Loading 2609.06154v1…