Connectivity-Aware Client Selection in Decentralized Federated Learning

Usevalad Milasheuski, Monica Nicoli, Stefano SavazziarXiv 2026 · arXiv

TL;DR

Decentralized Federated Learning (DFL) often suffers from massive communication overhead because every device tries to talk to all its neighbors. This paper introduces a "connectivity-aware" selection strategy that uses spectral graph theory—specifically Laplacian eigenvectors and heat kernels—to help nodes intelligently pick a subset of neighbors to communicate with, cutting message traffic by 50% while maintaining accuracy close to full broadcasting.

What Problem Does This Paper Address?

In standard Federated Learning (FL), a central server orchestrates training across many devices. While effective, this server is a single point of failure and a massive communication bottleneck. Decentralized Federated Learning (DFL) fixes this by letting devices (nodes) talk directly to their neighbors in a peer-to-peer fashion.

However, DFL has its own "chattiness" problem. Most DFL algorithms assume "full-neighborhood broadcasting," where every node sends its model updates to every single neighbor in every round. In energy-constrained environments like drone swarms or IoT networks, this is incredibly wasteful. Existing ways to prune these connections often require nodes to share their local data distributions or gradient information, which adds overhead and potential privacy risks. The authors seek a way to select the most "structurally important" neighbors using only the knowledge of the network's physical layout (topology).

Fig. 1: Standard Broadcasting (Left): A client sends updates to its entire neighborhood. This approach leads to high communication overhead and rapid energy depletion. Topology-Aware Selection (Right): Clients use spectral properties to identify and message only structurally significant neighbors. This strategic subsampling reduces costs while maintaining effective information flow compared to random selection.

Methods

The authors propose two main methods for neighbor selection based on the Graph Laplacian, a matrix representation of the network's connectivity.

  1. Spectral Embedding: This technique maps each node into a low-dimensional space using the eigenvectors of the Laplacian matrix. Nodes that are "close" in this spectral space share similar roles in the network's information flow. Each node calculates the similarity between itself and its neighbors in this space to decide who to talk to.
  2. Heat Kernel Similarity: This models how information (or "heat") would diffuse across the graph over time. Neighbors that have stronger diffusive interactions are prioritized. This captures both immediate neighbors and the broader "mixing" behavior of the network.

The Workflow: * Precomputation: The network topology is analyzed once (a one-time cost) to generate these similarity scores. * Subsampling: In each training round, instead of broadcasting to everyone, a node samples a fraction ($\beta$) of its neighbors based on a probability distribution derived from these similarity scores. * Aggregation: The node then performs standard DFL aggregation (like Decentralized SGD) using only the updates from these selected neighbors.

Datasets

The researchers evaluated their approach using two standard image classification datasets:

  • FMNIST (Fashion MNIST)
  • CIFAR10

To simulate real-world conditions, they used a Dirichlet split to create "non-IID" data, meaning different nodes hold very different types of images (e.g., one node has mostly shoes, another mostly shirts).

They tested these on three distinct graph topologies:

  • Small: A synthetic 8-node Erdős-Rényi graph.
  • Medium: The 32-node Davis Southern women social network.
  • Large: The 77-node Les Misérables co-appearance network.

Key Insights and Ideas

  • Structure Over Content: You don't need to know what a neighbor is learning to know if they are a good communication partner. By focusing purely on the graph's spectral properties, the system remains "data-blind" and "gradient-free," making it highly efficient.
  • Diversity is Key: Interestingly, a baseline method that paired nodes with similar data distributions (Data Sim) performed poorly. The authors found that naively aggregating with similar neighbors restricts diverse gradient exchange, slowing down global convergence. Topology-aware selection avoids this trap by maintaining effective information flow across the whole graph.
  • The "Heterogeneity Sweet Spot": The benefits of spectral selection are most pronounced when data is highly heterogeneous (non-IID) and the graph is large and structurally complex. In these cases, picking the right neighbors is crucial for spreading diverse information quickly.

Key Results

  • Efficiency: The proposed methods reduce the total number of transmitted messages by 50% compared to naive broadcasting.
  • Accuracy: Despite the massive reduction in communication, the accuracy remains very close to the "full broadcast" upper bound.
  • Outperforming Random: On the large Les Misérables graph with high data heterogeneity, spectral embedding and heat kernel methods outperformed random neighbor selection by about 3 percentage points.
Fig. 3: (a) Convergence on the large (Les Mis´erables) graph (FMNIST, Dirich- let, α=0.1); all curves are four-seed means (±std bands). (b,c) Sensitivity of spectral embedding on the small graph (α=0.3) to (b) the ratio β and (c) the dimension k.

As shown in Figure 3(a) above, the spectral methods (blue and green lines) track the "Broadcast" (black line) performance much more closely than random sampling or data-similarity-based methods.

Limitations and Future Work

  • Static Topologies: The current framework assumes the communication graph is fixed. While the authors suggest using iterative solvers (like LOBPCG) to adapt to dynamic graphs (like moving drones), this wasn't the primary focus of the experiments.
  • Hybrid Approaches: The authors acknowledge that their topology-only approach could be even more powerful if combined with data-aware or gradient-aware metrics in a multi-stage selection process.
  • Hyperparameter Sensitivity: While the method is stable across different embedding dimensions ($k$), the choice of the diffusion time ($t$) in the heat kernel and the sampling ratio ($\beta$) still requires some tuning based on the specific application.

Summary updated

Abstract

Decentralized federated learning (DFL) has emerged as a scalable alternative to centralized federated learning, removing the single point of failure and communication bottleneck at the server. However, most existing decentralized approaches rely on full-neighborhood broadcasting, where each client transmits its model update to all of its neighbors in each communication round. While effective, this results in significant communication overhead and high energy consumption. This paper applies spectral graph tools as lightweight client selection methods that leverage the graph topology by analyzing the spectral properties of the graph Laplacian over a fixed communication graph. Specifically, we exploit eigenvector embeddings and heat/diffusion kernel similarities to guide each client in selecting only a subset of structurally relevant neighbors, i.e., those that are most beneficial for the convergence of the federation process. This topology aware randomization matches or outperforms uniform neighborhood subsampling and approaches the accuracy of full broadcasting. The largest gains, about $3$ percentage points, emerge under strong data heterogeneity on larger, structurally rich graphs, while the total number of transmitted messages is reduced by $50\%$ compared to naive broadcasting.
BibTeX
@misc{milasheuski2026connectivity,
  author = {Usevalad Milasheuski and Monica Nicoli and Stefano Savazzi},
  title = {{Connectivity-Aware Client Selection in Decentralized Federated Learning}},
  year = {2026},
  eprint = {2610.41570},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.41570},
}
Figure