PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yin-Kuan Liang, Yan Gao, Yang Long

arXiv:2610.08176v1cs.AIcs.LG

TL;DR

Under non-IID data, decentralized learning depends on communication topology, while local peer selection and global graph optimization each have limits in search scope or information requirements. LFHE uses bounded FoF-based local topology search with a structural score tied to representation disagreement. Across reported baselines it achieves favorable target attainment and competitive final accuracy, with controls identifying the structural term as the principal topology-selection signal.

  • Problem

    Under non-IID data, sparse or poorly mixed graphs can sustain model disagreement, while local partner choices do not ensure efficient graph-wide propagation and direct spectral optimization commonly requires global information or centralized computation.

    Source: §1 · p. 1

  • Method

    LFHE samples FoF-based add-or-swap operations using local ego-topology information and scores them with structural disagreement, exploration, and degree control.

    Source: §1 · p. 2, §3 · p. 3

  • Results

    Across reported baselines, LFHE shows favorable target attainment and competitive final accuracy, while matched diagnostics identify the structural term as the main empirical topology-selection signal.

    Source: §7 · p. 10, §6 · p. 10

  • Takeaways & Limitations

    LFHE is state-aware localized topology search with bounded FoF discovery, rather than an approximation to global spectral optimization.

    Source: §7 · p. 10

    The theoretical result covers the structural component with fixed representations under standard linear consensus, and experiments serialize updates rather than evaluate concurrent or asynchronous commits.

    Source: §3.2 · p. 4, §7 · p. 10

Abstract

from arXiv · show

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.

1 Introduction

In decentralized learning, communication-graph properties shape information propagation, and non-IID data makes topology choice especially consequential. LFHE searches a bounded local candidate set and scores rewiring with a state-dependent structural signal.

1 Introduction

  • Under maximum local degree d̄, the two-hop candidate state is O(d̄^2) per client and O(N d̄^2) system-wide, becoming O(1) and O(N) at fixed sparse degree.Gossip-based discovery can grow toward O(N) state per client and O(N^2) system-wide; this comparison concerns discovery/control state, not total communication volume.Source: §1 · pp. 1–2
  • LFHE’s structural score is a node-local contribution to representation Dirichlet energy, whose sum governs instantaneous disagreement dissipation under standard linear consensus.The framework combines this signal with early exploration and degree control; algebraic connectivity remains an offline diagnostic.Source: §1 · p. 2
  • LFHE samples a friend-of-a-friend candidate and evaluates an edge addition or one-edge swap using structural disagreement, early exploration, and degree control.Its local search uses ego-neighborhood and current FoF frontier information, while spectral quantities remain offline diagnostics.Source: §1 · pp. 1–2
  • The paper evaluates LFHE across image, speech, and text tasks with matched mechanism controls and identifies the structural term as the principal topology-selection signal in the tested regime.It also compares broader peer-discovery strategies to examine the trade-off between localized discovery and broader peer exposure.Source: §1 · p. 2

2 Related Work

Related work spans adaptive peer selection, broader peer discovery, and graph designs that directly target global connectivity. LFHE is positioned as bounded local search between pairwise selection and global optimization.

Adaptive peer discovery and topology evolution

  • Adaptive peer-discovery methods use model similarity or dissimilarity, while Morph progressively broadens discovered-peer state; LFHE restricts candidate exposure to the current FoF frontier.The distinction is primarily search scope: bounded local candidate frontier versus potentially broader network exposure.Source: §2 · p. 2

Connectivity-oriented graph design

  • Sparse graphs can have unfavorable global connectivity, and direct graph or mixing-matrix optimization targets those properties but typically requires graph-wide state or centralized optimization.Consensus and decentralized averaging also depend on global graph and mixing properties.Source: §2 · p. 2

Positioning

  • LFHE combines restricted FoF discovery, post-operation ego-topology scoring, and local add-or-swap updates without online global graph statistics.Its structural score is state-dependent and tied to representation Dirichlet energy; LFHE does not estimate or optimize λ2.Source: §2 · pp. 2–3

3 Method

LFHE performs sampled greedy search over locally observable topology actions, and its structural score has an exact consensus-energy interpretation. The method combines bounded FoF discovery, locally scored rewiring, exploration, and degree control.

3 Method

  • LFHE performs sampled greedy search over ego-neighborhood and FoF actions, committing only operations that improve the initiator-local objective.Source: §3 · p. 3

3.1 Problem Setup

  • Online adaptation needs no global graph statistic, limits discovery to ego/FoF information, and regulates edge acquisition by Dmax; initiator-local gains do not guarantee global connectivity.Source: §3.1 · p. 3

3.2 Overview of the Framework

  • Structural disagreement, early exploration, and degree control shape local fitness; evaluated updates serialize proposals, leaving concurrent conflicts and asynchronous commits outside the protocol.Source: §3.2 · p. 4

3.3 Local Fitness Function Design

  • The structural score is a node-local Dirichlet-energy contribution tied to current disagreement; mismatch supplies early exploration, while degree regularization discourages communication concentration.Source: §3.3 · p. 5

3.4 Topology Evolution Mechanism

  • FoF discovery stays O(d̄^2) per client, becoming O(1) under bounded sparse degree; feasible additions or swaps commit only on strict initiator-local improvement.Source: §3.4 · p. 5

3.5 Consensus-Dissipation Interpretation

  • Under linear consensus, representation Dirichlet energy equals instantaneous centered-disagreement dissipation; unlike λ2, the score evaluates the current representation field, not worst-case directions.Source: §3.5 · p. 6

3.6 Algorithm Description

  • Every K rounds, LFHE adapts topology; Figure 2 reports favorable long-run CIFAR-10 performance versus decentralized baselines, with run-to-run variability bands.Source: §3.6 · p. 6, Figure 2 · p. 7

4 Experimental Setup

The evaluation covers four datasets across image, speech, and text tasks, using a common non-IID partition and a 30-client main system. Comparisons match shared learning components where applicable, while preserving each method’s native topology and communication design.

4 Experimental Setup

  • Experiments cover CIFAR-10, CIFAR-100, Google Speech Commands, and Sentiment140 across image, speech, and text tasks.Unless otherwise stated, data use class-wise Dirichlet α = 0.1, with N = 30 clients and online degree threshold Dmax = 4.Source: §4 · p. 7
  • Comparisons match data partitions, initialization, local optimization budgets, and evaluation schedules where applicable, but retain each method’s native topology and communication semantics.Main results use five seeds; diagnostic studies use three seeds or one controlled seed where specified.Source: §4 · p. 7
  • Dmax is an online edge-acquisition threshold, not a hard maximum degree, because the connected Erdős–Rényi initializer may exceed it.Complete model, optimizer, representation, initialization, and communication details are provided in Appendix F.Source: §4 · p. 7

5 Main Convergence Results and Topology Analysis

Across four datasets, LFHE reaches target accuracy earliest or jointly earliest and has competitive final accuracy, while topology diagnostics and matched controls clarify how its local search behaves. The structural term is the principal empirical topology-selection signal in the tested regime, not evidence of uniform superiority.

5 Main Convergence Results and Topology Analysis

  • 71.6% on CIFAR-10, 45.2% on CIFAR-100, and 78.8% on Speech Commands are LFHE’s highest mean final accuracies among decentralized methods; Sentiment140 is 65.3% versus Epidemic Learning’s 65.5%.LFHE reaches the selected target first at rounds 225, 125, and 170 on CIFAR-10, CIFAR-100, and Sentiment140, respectively, and jointly with Epidemic Learning at round 60 on Speech Commands.Source: §5 · p. 7, Table 1 · p. 8
  • Measured mean FoF candidate sets stay between 9.76 and 11.86 peers per client from N = 30 to N = 500, consistent with bounded per-client discovery state under sparse degree.This diagnostic concerns discovery/control state, not total communication volume or large-system learning speed.Source: §5 · p. 8

5.1 Topology Evolution Behavior

  • Under CIFAR-10 non-IID data (α = 0.1), offline λ2 rises early and stabilizes while clustering falls to a lower stable level, with graphs remaining sparse.By rounds 10–20, new cross-region edges coincide with the sharp λ2 rise; later graphs remain sparse and show no dominant hub.Source: §5.1 · pp. 8–9, Figure 3 · p. 9

5.2 Component and Mechanism Diagnostics

  • In the matched-score diagnostic at α = 0.1, Structural-only reaches final λ2 = 2.306 and accuracy 75.08%, versus 2.247 and 74.82% for full LFHE.The original α = 0.3 removal ablation instead found full LFHE reached the target first and had the highest final mean among reported removal variants.Source: §5.2 · p. 9
  • Exploration-only accepts 3.406 rewires per update versus LFHE’s 1.333, while producing weaker connectivity and accuracy.The findings characterize exploration and degree control as regime-dependent search regulators, not universally necessary components.Source: §5.2 · p. 9
  • Random-FoF reaches 74.62±2.25% accuracy but lower λ2 than LFHE, while graph-only has λ2 = 2.403 but 73.52% accuracy and random swaps yield 66.24%.These controls indicate that neither topology churn nor high algebraic connectivity alone explains LFHE’s behavior.Source: §5.2 · p. 9

6 Discussion

LFHE’s structural score is a state-dependent local contribution to representation Dirichlet energy, rather than an approximation of a global spectral objective. The discussion frames its empirical role and bounded discovery as a trade-off, while noting that execution is serialized.

6 Discussion

  • Each structural score Ci is a node-local contribution to representation Dirichlet energy, whose value gives instantaneous centered-disagreement dissipation under standard linear consensus.The score depends on both graph and current representations, unlike topology-only λ2.Source: §6 · p. 9
  • Matched controls identify structural scoring as the principal topology-selection signal in the tested regime, while exploration and degree control regulate its search.Structural-only slightly exceeds full LFHE in the matched-score diagnostic; Random-FoF, graph-only, and random-swap controls do not explain the observed behavior alone.Source: §6 · p. 10
  • Morph achieves stronger predictive performance, whereas LFHE keeps FoF candidate state O(1) per client and O(N) system-wide under bounded sparse degree.The comparison emphasizes discovery locality rather than predictive superiority or lower total communication.Source: §6 · p. 10
  • Serialized topology proposals can make realized graphs depend on update order; fully concurrent or asynchronous execution was not evaluated.Appendix G.3 quantifies update-order sensitivity.Source: §6 · p. 10

7 Conclusion

The conclusion presents LFHE as bounded local, state-aware topology search with a structural score tied to representation Dirichlet energy. Its reported performance is competitive, with evaluation and implementation boundaries explicitly noted.

7 Conclusion

  • LFHE evaluates local add-or-swap operations using structural disagreement, exploration, and degree control without online global spectral computation.Its structural scores exactly decompose representation Dirichlet energy, which under standard linear consensus determines instantaneous disagreement dissipation.Source: §7 · p. 10
  • Across reported baselines, LFHE has favorable target attainment and competitive final accuracy, while matched diagnostics identify the structural term as its main empirical topology-selection signal.The theoretical result applies to the structural component with fixed representations during each topology decision and standard linear consensus; the full objective depends on representation choice, coefficients, and annealing.Source: §7 · p. 10
  • Evaluation is limited to controlled benchmarks and moderate training populations; Dmax is an online acquisition threshold, acceptance is initiator-local, and updates are serialized.The conclusion lists concurrent updates and large-scale communication-normalized evaluation as future directions.Source: §7 · p. 10

Reproducibility statement

  • The reproducibility statement points to Section 4 for the main protocol and Appendix F for complete experimental settings and architectures.Appendix E contains full algorithmic details; Appendices G.4–G.7 contain sensitivity and diagnostic protocols.Source: Reproducibility statement · p. 10

AI use statement

  • The authors report using generative AI for language editing, manuscript restructuring, experiment planning, and software/code edits, with review and responsibility retained by the authors.Numerical results were taken from executed pipelines and checked against saved outputs.Source: AI use statement · p. 10

A Full Component Ablation

  • Table 2 reports a CIFAR-10 α = 0.3 component ablation using R@Target for reaching 0.65 accuracy and final test accuracy.The caption supplies the comparison scope and metrics, but not the table’s cell values.Source: Table 2 · p. 13

A.1 Original removal ablation and topology diagnostics

The ablation identifies the structural term as the clearest source of topology change, while the appendix explains its consensus-energy meaning and the local, degree-aware procedures used to update topology.

A.1 Original removal ablation and topology diagnostics

  • Without the structural term, topology quality, convergence, and final accuracy degrade most clearly; removing degree regularization raises λ2 but yields denser connectivity without an accuracy gain.In the α = 0.3 ablation, full LFHE reaches the target first and has the highest final mean among removal variants; at α = 0.1, structural-only slightly exceeds full LFHE.Source: §A.1 · p. 13

C Graph Laplacian, Dirichlet Energy, and Algebraic Connectivity

D Structural Signal as Local Consensus Dissipation

  • The local structural score contributes to instantaneous disagreement dissipation, and a positive structural change strictly increases that rate when the representation state is fixed.The consensus identity applies to standard continuous-time linear consensus; experiments instead use discrete degree-aware averaging.Source: D Structural Signal as Local Consensus… · pp. 15–16

E Full Algorithm Description

  • The reference procedure trains and aggregates synchronously, then evaluates and commits topology proposals sequentially on a copied graph.Later proposals observe earlier committed changes within the update call.Source: E Full Algorithm Description · p. 17

E.1 Decentralized Federated Learning Procedure

  • The decentralized procedure alternates local training and aggregation with periodic topology updates.The appendix describes these stages as the reference learning procedure.Source: §E.1 · p. 17

E.2 LFHE Topology Update

  • Each client discovers a FoF candidate and evaluates an edge addition or, when needed, a one-edge swap using ego-network information under a degree constraint.The reference procedure attempts an atomic swap when direct addition is infeasible.Source: §E.2 · pp. 17–18

E.3 Fitness Function

  • Fitness combines an incident-edge representation-energy term, neighborhood mismatch for exploration, and a degree penalty; the mismatch influence decays over time.As β_t decays, the structural term becomes more influential while excessive degree growth remains penalized.Source: §E.3 · p. 20

E.4 Auxiliary Procedures

  • Before a swap removes an edge, a shared neighbor provides a local two-hop alternative-path safeguard without a global path search.This guarantee concerns the serialized reference update; stale or conflicting concurrent removals require additional validation.Source: §E.4 · p. 20

E.5 Implementation Notes

Topology updates use serialized, initiator-local decisions, with order-dependent outcomes and no bilateral approval of affected endpoints.

E.5 Implementation Notes

  • Clients process updates in fixed order on a copied graph, committing each accepted operation immediately; later clients therefore see earlier changes, and the final topology can depend on order.Each initiator evaluates fitness using representations from its ego-neighborhood and current FoF candidate.Source: §E.5 · p. 21
  • Affected peers do not separately approve an operation, so an initiator’s gain need not be a bilateral utility improvement.In the update-order diagnostic, final accuracies stayed within 1.51 percentage points despite substantial topology and λ2 changes; none of 2,280 audited graph states was disconnected, which is not a connectivity guarantee.Source: §E.5 · p. 21
  • Proposal–validate–commit with endpoint-local topology versions is presented as a deployment direction, not a validated asynchronous implementation.The experiments do not implement or validate arbitrary asynchronous transaction semantics.Source: §E.5 · p. 21

F Additional Experimental Details

The appendix specifies datasets, non-IID partitioning, system settings, and training protocols for the experiments.

F Additional Experimental Details

  • Evaluation covers CIFAR-10 and CIFAR-100, a 10-keyword Google Speech Commands subset, and binary Sentiment140 classification.Sentiment140 uses balanced subsampling to 12,000 training tweets and 2,000 test tweets.Source: F Additional Experimental Details · p. 21
  • Class-wise Dirichlet sampling models heterogeneous client data, with α = 0.1 as the default and α = 0.3 for component ablations and the moderate-scale diagnostic.The default system uses 30 clients and online degree threshold Dmax = 4; the expected-degree initializer may initially exceed that threshold.Source: F Additional Experimental Details · p. 21
  • CIFAR and speech use SGD, while Sentiment140 uses Adam; LFHE updates topology every five communication rounds and main results average five seeds.The main training protocol uses one local epoch per round except Sentiment140, which uses two; the appendix also lists architectures and hyperparameters in Tables 4 and 5.Source: F Additional Experimental Details · pp. 21–22, Table 4 · p. 22, Table 5 · p. 23

G.1 Results on Additional Datasets

LFHE is competitive across additional image, speech, and text benchmarks, while diagnostics examine its comparison with Morph, sensitivity, scale, stress behavior, and matched local rewiring controls.

G.1 Results on Additional Datasets

  • LFHE is competitive across CIFAR-100, Speech Commands, and Sentiment140: it finishes at 45.19% and 78.76% on the first two, while Sentiment140 ends slightly below Epidemic Learning.LFHE reaches the Sentiment140 0.65 target 20 rounds earlier, but finishes at 65.29% versus Epidemic Learning’s 65.45%.Source: §G.1 · p. 23, Figure 6 · p. 24

G.2 Direct Comparison with Morph

  • Morph reaches 65% accuracy 16.7 rounds earlier on average, while LFHE’s measured mean FoF candidate set stays 9.76–11.86 peers per client as N increases from 30 to 500.This comparison concerns discovery/control state, not total communication traffic.Source: §G.2 · p. 24

G.3 Update-Order and Endpoint Effects

  • Changing client processing order substantially changes the final graph, while observed final accuracies remain within 1.51 percentage points; accepted operations can also reduce a non-initiator endpoint’s local fitness.The rates of affected non-initiators with negative local-fitness change were 33.3%, 31.5%, and 41.5% for fixed, reverse, and randomized order.Source: §G.3 · pp. 24–25, Table 7 · p. 24

G.4 Sensitivity and Communication Trade-off

  • Varying structural or exploration coefficients around their defaults leaves final accuracy within 78.01–78.32%, while raising the degree threshold from 4 to 6 improves measured learning metrics but increases transmissions by 39%.The coefficient study supports a locally stable region, not cross-dataset hyperparameter invariance; the threshold comparison is a three-seed diagnostic.Source: §G.4 · p. 25

G.5 Moderate-Scale Accuracy Study

  • LFHE has the highest mean final accuracy among plotted methods in a preliminary three-seed CIFAR-10 study at N = 10, 50, and 100.The study stops at N = 100 and does not normalize comparisons by total communication, so it is not a large-system scaling law.Source: §G.5 · p. 25, Figure 7 · p. 25

G.6 Deployment-Stress Diagnostic

  • In a single-seed compounded stress test, the graph remains connected throughout (minimum observed λ2 = 0.670), yet final accuracy drops from 79.53% in the clean diagnostic to 60.18% under stress.This is preliminary evidence only and does not establish robustness to arbitrary asynchrony, long delays, or real distributed failures.Source: §G.6 · p. 26

G.7 Additional Consensus and Client-Variance Diagnostics

  • On CIFAR-10 with α = 0.1, model divergence declines, mean pairwise cosine similarity rises, and client-level accuracy variance declines after the early phase.These are descriptive within-method trajectories, not evidence that a particular topology statistic causes learning improvement.Source: §G.7 · p. 26, Figure 8 · p. 26

H Bridge Evidence Under Matched Rewiring Budget; H.1 Protocol

  • The matched bridge protocol holds candidate access, update frequency, rewiring budget, initialization, training, and aggregation fixed so variants differ only in their local score.The comparison includes Static, Similarity-only, Exploration-only, Structural-only, and LFHE; the supplied passages describe the protocol but not its outcome values.Source: §H.1 · p. 26, Table 8 · p. 27

H.2 Results

Matched score controls identify structural scoring—not rewiring frequency—as the main empirical signal, while cost analyses report local control behavior and simulator-side overhead.

H.2 Results

  • Structural-only and LFHE produced the largest connectivity gains; Structural-only slightly beat LFHE (λ2 2.306 vs 2.247; accuracy 0.7508 vs 0.7482), while Exploration-only rewired most (3.406 vs 1.333) but performed worse.The matched controls identify the structural term as the principal empirical topology-selection signal, not topology churn alone.Source: §H.2 · p. 27

H.3 Additional Simple Controls

  • Random-FoF reached 74.62 ± 2.25% accuracy, near LFHE’s 74.82%, but lower λ2 (1.696 vs 2.247); graph-only reached λ2 2.403 but 73.52% accuracy.The controls caution against attributing all LFHE gains uniquely to its score.Source: §H.3 · p. 27

H.4 Interpretation

  • The matched score study isolates the local scoring rule under shared FoF access; Structural-only can outperform full LFHE, so exploration and degree control regulate search and resources rather than ensure optimal updates.The structural score has an exact state-dependent Dirichlet-energy interpretation, distinct from the empirical finding that it produces the strongest measured topology change in this regime.Source: §H.4 · p. 28

I Cost Analysis / I.1 Measurement Protocol

  • The overhead study records runtime and control counts—including neighbor reads, FoF checks, fitness evaluations, accepted rewires, and edge changes—in a CIFAR-10 run with N = 30 and T = 300.LFHE is called every five communication rounds, for 60 topology updates per seed.Source: I Cost Analysis · p. 28, §I.1 · pp. 28–29

I.2 Asymptotic Cost Discussion

  • When actual maximum degree remains bounded independently of N, control computation is linear in client count; this condition is not guaranteed by an expected-degree initializer.Local candidate fitness avoids repeated global eigendecomposition or full-graph optimization during training.Source: §I.2 · pp. 29–30

I.3 Observed Runtime Overhead

  • 1.886 ± 0.038 seconds was the mean total topology-update time over the 300-round run, or 0.00629 ± 0.00013 seconds per communication round; measurements exclude real network latency and full deployment control traffic.These are implementation-overhead measurements for the synchronous simulator, not end-to-end systems costs.Source: §I.3 · p. 30

I.4 Control Overhead

  • LFHE averaged 353.78 ± 48.55 candidate checks per update but accepted 0.339 ± 0.122 rewires; checks stabilized around 350 per update as accepted rewires became rare later.The candidate-check workload is stable in the reported runs, not an empirical scaling law in N.Source: §I.4 · pp. 30–31, Figure 12 · p. 31

I.5 Acceptance Ratio

  • Only about 10^-3 of inspected candidates are accepted, consistent with initiator-local accept-if-improves selection; acceptance does not establish global or bilateral benefit.LFHE continues checking local candidates while committing only operations that improve node-level fitness under imposed constraints.Source: §I.5 · p. 31

Related papers

Loading 2610.08176v1…