Topology-Aware Knowledge Propagation in Decentralized Learning

Mansi Sakarvadia, Nathaniel Hudson, Tian Li, Ian Foster, Kyle ChardSubmission to ICLR 2026 · Rejected

TL;DR

Decentralized learning removes the central server by having devices only communicate with direct network neighbors, but rare or out-of-distribution (OOD) knowledge struggles to propagate across the graph. This paper shows that OOD knowledge dissemination heavily depends on network structure and the origin node's position, and introduces topology-aware aggregation—weighting neighbor updates by graph centrality metrics (degree and betweenness). This simple modification accelerates OOD knowledge propagation, improving OOD accuracy by an average of 123% across models without hurting in-distribution performance or increasing communication overhead.

What Problem Does This Paper Address?

In fully decentralized machine learning, devices train local models on local data and periodically average parameters with immediate network neighbors—avoiding the single point of failure and bottleneck of a central parameter server. However, real-world data is non-IID and geographically heterogeneous.

When valuable, out-of-distribution (OOD) knowledge is concentrated on only a few devices (or a single node), standard decentralized training algorithms struggle to spread that knowledge across the network. If models only generalize to their immediate neighborhood's data distribution, they will fail when encountering OOD inference requests in production. This paper investigates how topology and node location govern the "hopping" of OOD information across networks and how to fix the resulting knowledge bottlenecks.

Methods

Standard decentralized algorithms weigh neighbors uniformly (Unweighted) or by sample size (Weighted). In contrast, the authors introduce topology-aware aggregation:

  • Centrality Weighting: Each device weights neighbor $j$ based on its structural importance in the network using graph centrality metrics:
  • Degree (Local): Measures the neighbor's number of connections. High-degree hubs excel at absorbing and broadcasting updates.
  • Betweenness (Global): Measures how frequently a node falls on the shortest path between all node pairs, quantifying its role as a cross-network bridge.
  • Softmax Scaling: Aggregation coefficients $C_{i,j}$ are normalized over the neighborhood $\mathcal{N}_i$ using a temperature-scaled softmax: $$C_{i,j} = \frac{\exp(R_j / \tau)}{\sum_{k \in \mathcal{N}_i} \exp(R_k / \tau)}$$ where $R$ is the centrality vector and $\tau = 0.1$ provides an optimal empirical trade-off.

  • Computational Cost: Centrality metrics are computed once before training, incurring zero runtime memory or per-round communication overhead compared to baseline gossip algorithms.

Datasets

The authors evaluate across five datasets and multiple data modalities:

  • Computer Vision: MNIST, Fashion-MNIST (FMNIST), CIFAR-10, and CIFAR-100.
  • Language / Reasoning: TinyMem, a configurable synthetic language dataset producing multi-task multiplicative math sequences (context length 150) evaluated on a 1-layer GPT-2 model.

OOD / Heterogeneity Setup: Background data is distributed mostly IID across nodes ($\alpha_l = \alpha_s = 1000$ via Dirichlet partitioning). A worst-case knowledge propagation scenario is simulated by placing OOD data on a single node via a 10% backdoor trigger (a red square image patch or a specific trigger token sequence 100), evaluated against held-out global IID and OOD test sets. Additional experiments validate label-skew non-IID distributions without backdoors.

Topologies tested include Barabási–Albert (BA) (scale-free), Stochastic Block (SB) (modular community structures), and Watts–Strogatz (WS) (small-world) graphs across network sizes ranging from 8 to 64 nodes.

Key Insights and Ideas

  • OOD Knowledge Faces High Resistance: In standard decentralized setups, IID data spreads smoothly, but OOD data remains trapped near its origin node, resulting in stark performance disparities across devices.
  • Node Location Matters Immensely: Placing OOD data on well-connected hubs yields vastly superior propagation compared to placing it on peripheral, low-degree nodes. FL and centralized training do not exhibit this vulnerability.
  • Modularity Traps Information: In modular networks (Stochastic Block models), tightly bound communities act as firewalls, severely inhibiting OOD knowledge spread across community boundaries.
  • Theoretical Backing via Spectral Gap: The authors demonstrate that topology-aware mixing matrices increase the network's spectral gap compared to uniform or random averaging. Decentralized optimization theory shows that a larger spectral gap accelerates consensus and forces worker models closer together faster.

Key Results

  • Large Accuracy Gains: Topology-aware aggregation (Degree and Betweenness) outperforms uniform, data-weighted, random, and even fully connected federated baselines, improving average OOD test accuracy AUC by 123% across models in a topology.
  • No Degradation of IID Performance: Topology-aware weighting boosts OOD diffusion while maintaining or slightly improving IID accuracy (e.g., maintaining ~54% IID accuracy on CIFAR-10 while jumping from 20% to 42% OOD accuracy).
  • Scale-Free Robustness: In Barabási-Albert networks, topology-aware methods maintain high OOD dissemination even as graph size scales up (up to 64 nodes), whereas baseline performance degrades sharply.

Limitations and Future Work

  • Uniform Degree Graphs: In networks where node centralities are largely uniform (such as ring-like Watts-Strogatz graphs), topology-aware methods provide minimal advantage over uniform averaging.
  • Security Implications: Because these strategies efficiently propagate localized data across an entire network, they also accelerate the spread of malicious data or backdoor attacks; robust filtering and anomaly detection will be essential.
  • Future Directions: Exploring dynamic/time-varying topologies, alternative centralities (e.g., PageRank, eigenvector centrality), and online or streaming decentralized environments.

Summary updated

Abstract

Decentralized learning enables collaborative training of models across naturally distributed data without centralized coordination or maintenance of a global model. Instead, devices are organized in arbitrary communication topologies, in which they can only communicate with neighboring devices. Each device maintains its own local model by training on its local data and integrating new knowledge via model aggregation with neighbors. Therefore, knowledge is propagated across the topology via successive aggregation rounds. We study, in particular, the propagation of out-of-distribution (OOD) knowledge. We find that popular decentralized learning algorithms struggle to propagate OOD knowledge effectively to all devices. Further, we find that both the location of OOD data within a topology, and the topology itself, significantly impact OOD knowledge propagation. We then propose topology-aware aggregation strategies to accelerate (OOD) knowledge propagation across devices. These strategies improve OOD data accuracy, compared to topology-unaware baselines, by 123% on average across models in a topology.
BibTeX
@misc{sakarvadia2025topology,
  author = {Mansi Sakarvadia and Nathaniel Hudson and Tian Li and Ian Foster and Kyle Chard},
  title = {{Topology-Aware Knowledge Propagation in Decentralized Learning}},
  year = {2025},
  eprint = {2505.11760},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.11760},
}
Figure