LFHE: Local-First Heuristic Evolution for Bounded Local Topology Search in Decentralized Learning with Non-IID Data

Yin-Kuan Liang; Yan Gao; Yang Long

cs.AIOct 6, 2026

LFHE: Local-First Heuristic Evolution for Bounded Local Topology Search in Decentralized Learning with Non-IID Data

Authors: Yin-Kuan Liang, Yan Gao, Yang Long

Organizations: Durham University · University of Cambridge

Abstract

Decentralized learning is highly sensitive to communication topology under non-IID data. Adaptive peer-selection methods can exploit local model information, but broader peer discovery may require increasingly large control state, whereas direct spectral optimization typically relies on graph-wide information. We study the intermediate setting of bounded local topology search and propose Local-First Heuristic Evolution (LFHE), a representation-driven rewiring framework whose candidate discovery and scoring use only ego-neighborhood and friend-of-a-friend (FoF) information. The structural score admits an exact interpretation through graph Dirichlet energy: its sum across clients equals twice the representation Dirichlet energy, which under standard linear consensus dynamics governs the instantaneous dissipation of representation disagreement. LFHE combines this state-dependent structural signal with early exploration and degree control, while algebraic connectivity remains an offline graph diagnostic. Under bounded sparse degree, its FoF candidate state remains local rather than expanding toward population-wide peer tracking. Across four image, speech, and text benchmarks, LFHE achieves competitive decentralized learning performance. Matched-protocol controls identify the structural term as the principal empirical topology-selection signal, while comparison with broader peer discovery exposes a trade-off between predictive performance and discovery-state locality. Together, these results motivate state-aware bounded local topology search between pairwise peer selection and globally informed topology optimization.

Figures & tables

Figure 1 : Overview of LFHE. Each client $i$ observes only its ego-graph, samples a two-hop FoF candidate, and evaluates it using a local objective with structural, exploration, and degree-control terms. If the candidate improves the objective, LFHE adds the edge when direct addition is feasible or performs a feasible one-edge swap otherwise; if no improving feasible operation exists, the candidate is rejected.

Panel of Figure 2 — Figure 2 : Main convergence results on CIFAR-10 under non-IID data. LFHE shows favorable long-run performance relative to the reported decentralized baselines; shaded bands summarize run-to-run variability.

Method	CIFAR-10 ( $\geq$ 70%)		CIFAR-100 ( $\geq$ 35%)		Speech Commands ( $\geq$ 70%)		Sentiment140 ( $\geq$ 65%)
Method	R@T	Final Acc. (%)	R@T	Final Acc. (%)	R@T	Final Acc. (%)	R@T	Final Acc. (%)
FedAvg	115	78.40 $\pm$ 0.80	85	51.90 $\pm$ 0.30	35	86.80 $\pm$ 0.50	40	70.60 $\pm$ 2.70
Fully Connected	105	78.40 $\pm$ 0.70	85	51.80 $\pm$ 0.50	35	86.40 $\pm$ 1.40	40	70.60 $\pm$ 2.60
Ring	–	52.60 $\pm$ 1.20	–	27.00 $\pm$ 0.80	–	53.00 $\pm$ 3.10	–	58.00 $\pm$ 2.70
Static Random	–	67.40 $\pm$ 1.70	160	41.70 $\pm$ 1.20	75	74.20 $\pm$ 3.50	–	63.50 $\pm$ 2.30
Epidemic Learning	–	70.00 $\pm$ 1.60	130	44.10 $\pm$ 0.70	60	78.10 $\pm$ 3.30	190	65.50 $\pm$ 2.30

Table 1 : Convergence speed and final accuracy across datasets over five random seeds. R@T denotes the communication round at which the mean accuracy across seeds first reaches the target specified in each dataset column, and “–” indicates that the target was not reached within the training budget. Final accuracy is reported as mean

\pm

std. FedAvg and Fully Connected are included as reference points. Among decentralized methods, the best result is shown in bold and the second-best in underline.

Panel of Figure 3 — Figure 3 : Topology evolution of LFHE on CIFAR-10 under non-IID data ( $\alpha=0.1$ ). Left: algebraic connectivity $\lambda_{2}$ and clustering coefficient. Right: representative graph snapshots at different training rounds.

Appendix figures & tables15 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 5 — Figure 5 : Topology evolution under ablation. Left: algebraic connectivity ( $\lambda_{2}$ ). Right: clustering coefficient.

Method	Connectivity-aware	Similarity-aware	Ego-graph local	No global graph statistics
Spectral methods	✓	$\times$	$\times$	$\times$
D-PSGD / Gossip	$\times$	$\times$	$\times$	✓
D-Cliques / STL-FW	✓	✓	$\times$	$\times$
Epidemic Learning	$\times$	$\times$	✓	✓
DissDL (legacy impl.)	$\times$	✓	✓	✓
Morph	$\times$	✓	$\times$	✓

Appendix

Table 3 : Comparison of representative communication-structure approaches. The last column refers to online information requirements rather than concurrent execution semantics.

\checkmark^{*}

denotes a state-dependent Dirichlet structural signal rather than direct optimization of

\lambda_{2}

Item	Setting
Number of clients	$N=30$ for the main experiments; $N\in\{10,50,100\}$ for scalability experiments.
Online degree threshold	$D_{\max}=4$ ; the expected-degree initializer is not guaranteed to satisfy a hard cap.
Topology update interval	$K=5$ communication rounds.
Evaluation interval	Every 5 communication rounds.
Random seeds	$\{42,43,44,45,46\}$ .
Non-IID partitioning	Class-wise Dirichlet partitioning with $\alpha=0.1$ by default; the component ablation and moderate-scale diagnostic use $\alpha=0.3$ .

Appendix

Table 4: Implementation details and hyperparameters used in the main experiments.

Dataset	Model architecture	Representation $r_{i}$
CIFAR-10	CNN with two convolutional blocks: Conv(3,32)-BN-ReLU, Conv(32,32)-BN-ReLU, MaxPool; Conv(32,64)-BN-ReLU, Conv(64,64)-BN-ReLU, MaxPool; adaptive average pooling to $4\times 4$ ; MLP classifier $1024\rightarrow 256\rightarrow 10$ with dropout 0.3.	Flattened final classifier-layer weights.
CIFAR-100	Same CNN backbone as CIFAR-10, with the final classifier dimension changed to 100 classes: $1024\rightarrow 256\rightarrow 100$ .	Mean-reduced final classifier-layer weights, producing a 100-dimensional representation.
Speech Commands	CNN over log-Mel spectrograms: Conv(1,32)-BN-ReLU, Conv(32,32)-BN-ReLU, MaxPool; Conv(32,64)-BN-ReLU, Conv(64,64)-BN-ReLU, MaxPool; adaptive average pooling to $4\times 4$ ; MLP classifier $1024\rightarrow 256\rightarrow 10$ with dropout 0.3.	Flattened final classifier-layer weights.
Sentiment140	Embedding-based text classifier with 128-dimensional token embeddings, attention-mask mean pooling, and MLP classifier $128\rightarrow 128\rightarrow 2$ with dropout 0.2.	Flattened final classifier-layer weights.

Appendix

Table 5: Model architectures and representation extraction rules.

Panel of Figure 6 — Figure 6 : Test accuracy (mean $\pm$ std) on additional datasets under non-IID data. LFHE is competitive across image, speech, and text tasks; Sentiment140 illustrates that faster target attainment need not imply the best final accuracy.

Method	Final accuracy (%)	nAUC (%)
LFHE	71.37 $\pm$ 2.19	60.57 $\pm$ 1.52
Morph	72.25 $\pm$ 1.92	63.17 $\pm$ 1.23

Appendix

Table 6: Three-seed LFHE–Morph comparison under the shared diagnostic protocol. nAUC denotes normalized accuracy area under the learning curve.

Order	Final acc. (%)	nAUC (%)	R@65	Final $\lambda_{2}$	Edge Jaccard
Fixed	69.03	58.82	160	0.936	1.000
Reverse	70.54	60.29	145	0.685	0.291
Random/update	69.61	59.24	155	0.807	0.271

Appendix

Table 7: Single-seed update-order diagnostic. Edge Jaccard is measured against the final graph from fixed order.

Figure 7 : Moderate-scale CIFAR-10 diagnostic under $\alpha=0.3$ with $N\in\{10,50,100\}$ . Bars report final test accuracy averaged over three seeds.

Panel of Figure 8 — Figure 8 : Additional LFHE diagnostics on CIFAR-10 with $\alpha=0.1$ . Left: model-consensus quantities. Right: client-level test-accuracy variance.

Method	Final $\lambda_{2}$	$\Delta\lambda_{2}$	Final Acc.	Mean Div.	Mean Rewires
Static	0.592	0.000	0.6675	0.766	0.000
Similarity-only	0.578	-0.014	0.6704	0.727	0.183
Exploration-only	1.038	0.447	0.7356	0.221	3.406
Structural-only	2.306	1.715	0.7508	0.136	1.111
LFHE	2.247	1.655	0.7482	0.133	1.333

Appendix

Table 8: Summary of matched-budget bridge evidence on CIFAR-10 with

\alpha=0.1

. Final

\lambda_{2}

reports the final algebraic connectivity.

\Delta\lambda_{2}

is computed relative to the shared initial graph used by all matched-budget variants. Mean divergence is computed over the last 20% of evaluation rounds.

Figure 9 : Bridge evidence under matched FoF candidate generation and rewiring budget on CIFAR-10 with $\alpha=0.1$ . Methods containing the structural term ( Structural-only and LFHE ) produce substantially larger and more stable gains in algebraic connectivity than Similarity-only or Exploration-only . The same methods also achieve lower model divergence and stronger test accuracy under the same local update protocol.

Figure 10 : Accepted rewires per topology update under the same maximum rewiring budget. Exploration-only performs more rewiring than LFHE or Structural-only during much of training, but does not achieve the strongest connectivity or accuracy. This shows that the advantage of structural-term methods is not explained by rewiring frequency alone.

Figure 11 : Per-update LFHE topology overhead across communication rounds. Thin lines show individual seeds and the bold line shows the mean across seeds. The runtime remains stable throughout training, indicating that LFHE does not incur increasing topology-update cost in later rounds.

Panel of Figure 12 — Figure 12 : Control overhead of LFHE during topology evolution. Left: Candidate checks increase in the early stage and then stabilize, showing a stable candidate-check workload over later training rounds. Right: Accepted rewiring operations are concentrated in early rounds and become rare as the topology stabilizes.

Explore similar work

Oct 4, 2026cs.LG

Population Scaling or Data Dilution? Dynamics of Local Topology Evolution in Decentralized Learning

Scaling decentralized learning changes not only the number of clients

N

, but also the dynamics of information propagation and consensus. We argue that the effect of increasing

N

cannot be understood in isolation, because data allocation, topology-dependent mixing, and communication capacity may change simultaneously. We study these coupled effects on CIFAR-10 with

N\in\{10,50,100,200\}

, comparing a degree-two Ring, a Static Random graph, and Local-First Heuristic Evolution (LFHE), a locally adaptive topology process based on friend-of-friend discovery. The Ring provides an analytically transparent failure mode: its Metropolis spectral gap decays as

Θ(N^{-2})

, implying progressively slower contraction of model disagreement as the population grows. Experiments show that holding the nominal local dataset size fixed substantially reduces the apparent population penalty observed when a fixed total dataset is divided among more clients. The remaining degradation depends strongly on communication structure: Ring enters a high-disagreement regime, whereas Static Random and LFHE remain close to consensus. Increasing LFHE's degree threshold further improves accuracy and consensus, but at a substantially higher model-transmission cost. These results show that decentralized scaling is governed by coupled learning and communication dynamics, rather than by the number of clients alone.

Yin-Kuan Liang, Yan Gao, Yang Long

Durham University · University of Cambridge

Decentralized Learning Singular Learning Theory

Ask PDF

Sep 24, 2026cs.LG

SPADE-DFL: Communication-Efficient Decentralized Federated Learning via Derivative-Free Linearized ADMM

Reducing communication in derivative-free decentralized learning requires controlling the disagreement accumulated over multiple local updates. This paper develops SPADE-DFL, a primal--dual method that allows the number of local function-value updates between neighbor exchanges to grow with the computation budget while preserving the nonprivate convergence order. For smooth nonconvex objectives under uniform query-moment bounds, the prescribed nonprivate schedule achieves a time-averaged stationarity and consensus bound of

\mathcal{O}(T^{-1/3})

using only

Θ(T^{2/3})

communication rounds, where

T

is the number of local updates per client. For private training, the accumulated data-dependent increment is isolated from the graph correction, allowing one protected state per client and round to generate all outgoing messages. We prove client-level differential privacy for the full interactive transcript and quantify the resulting optimization error over a finite horizon. Experiments on four classification tasks show that SPADE-DFL achieves higher mean test accuracy than existing decentralized learning methods.

Mengli Wei, Mengkai Zhu, Jiawen Chen +2

School of Mathematics, Southeast University, Nanjing 210096, China

Decentralized Learning Federated Learning Δ)$-Differential Privacy Primal-Dual Methods Alternating Direction Method Of Multiplier Convergence+1

Ask PDF

May 26, 2026cs.LG

HEAL: Resilient and Self-* Hub-based Learning

Decentralized learning enhances privacy, scalability, and fault tolerance by distributing data and computation across nodes. A popular approach is Federated learning, which relies on a central aggregator, yet faces challenges such as server vulnerabilities, scalability issues, privacy risks and most importantly, the single point of failure. Alternatively Gossip Learning and Epidemic Learning offer fully decentralization through peer-to-peer exchanges of model updates, ensuring robustness and privacy, at the price of slower model convergence. In this work, we introduce a novel decentralized learning framework called HEAL. HEAL is the first cross-layer decentralized learning framework that exploits an optimized self-organizing and self-healing underlying P2P overlay combining the strengths of Federated Learning, Gossip and Epidemic Learning. Leveraging the recently proposed Elevator algorithm, HEAL promotes dynamically chosen nodes to act as aggregators. Through simulations, we demonstrate that HEAL has similar performances to that of Federated Learning in crash-free settings, while being fully decentralized and fault-tolerant. In crash and churn prone environments HEAL outperforms Gossip and Epidemic Learning.

Mohamed Amine Legheraba, Stefan Galkiewicz, Maria Gradinariu Potop-Butucaru +1

NPA · Sorbonne University, CNRS, LIP6, F-75005 Paris, France · NPA, IUF, LINCS +1

Decentralized Learning Federated Learning Gossip Resilience Epidemiological Models Self

Ask PDF