In decentralized training, each worker holds its own data, updates its own copy of the model, and averages it with a few neighbors over a communication graph. Choosing that graph is a real engineering decision for edge clusters, sensor meshes, and drone swarms. The theory practitioners are given to make it is known to mislead. The classical guide is the spectral gap, a single number describing how fast repeated neighbor-averaging mixes information across the whole graph. Several groups have shown it predicts training poorly when every worker sees statistically identical data. Their replacements, however, either assume that identical data or reduce the effect of data skew to a one-hop neighborhood statistic, and they have been tested almost entirely on rings, tori, and other symmetric graphs that real deployments rarely resemble.
This note proposes a specific, falsifiable answer to the open case of skewed data on irregular graphs. The harm a graph does under data skew should depend on how much of the skew lines up with the graph's slow-mixing directions. Skew that varies from node to node gets averaged away quickly. Skew that differs between two weakly connected regions, such as the two sides of a bottleneck link, persists. We turn this into a quantity that can be computed from a single gradient pass before training. We then test it against every existing topology metric in a pre-registered study whose central manipulation is easy to state: we keep the graph and the data fixed and change only which worker gets which shard.
Core Claim
Let $W$ be the $n \times n$ mixing matrix, the table of weights each worker uses to average with its neighbors. Write its eigenvalues as $1=\lambda_1 > \lambda_2 \ge \dots \ge \lambda_n$ with eigenvectors $u_i$. Let $H \in \mathbb{R}^{n \times d}$ stack each node's local full gradient minus the global average gradient, measured at the shared initialization. We define the aligned heterogeneity
$$\Phi(W,H) = \frac{1}{n}\sum_{i=2}^{n} \frac{\lambda_i^2}{(1-\lambda_i)^2}\,\|u_i^\top H\|^2 .$$
The form follows from a one-line calculation on quadratics with fixed heterogeneity. Decentralized stochastic gradient descent (D-SGD) iterates $X_{k+1}=W(X_k-\eta G_k)$. A deterministic drift $-\eta\, u_i^\top H$ in eigenmode $i$ settles at a steady disagreement of size $\eta\lambda_i/(1-\lambda_i)$ times that drift. Squaring and summing over modes gives $\eta^2\Phi$ as the drift part of the steady-state consensus error.
Our claim is that, on irregular graphs with skewed data, $\Phi$ predicts consensus distance, iterations to a target loss, and final test accuracy better than any data-blind graph metric and better than one-hop heterogeneity. We further claim that this advantage largely disappears for gradient tracking, an algorithm whose correction term is designed to cancel exactly this drift. That second prediction is what separates a mechanism from a fitted correlation.
How This Relates to Prior Work
Four papers motivate the proposal by documenting the theory–practice gap under identical data. Decentralized gradient methods: does topology matter? explains why a ring and a clique train almost identically when data is shuffled. Its explanation is a small gradient-variability term, plus a coefficient describing how gradient error spreads across eigenspaces. That eigenspace-energy idea is the direct ancestor of $\Phi$. That paper, however, studies convex subgradient methods on identical data, and its authors note that the effect collapses under skew; we target the skewed case. Beyond spectral gap: the role of the topology in decentralized learning replaces the spectral gap with an "effective number of neighbors" from random-walk variance reduction. It shows this tracks loss across rings, grids, tori, and hypercubes, but it leaves heterogeneous data open. Improved Convergence Analysis of Topology Dependence in Decentralized SGD shows that the stochastic-noise term depends on the full spectrum through $\frac1n\sum_{i\ge2}\lambda_i^2/(1-\lambda_i^2)$. It validates this on graphs with matched spectral gaps. It reports that its heterogeneity term remains tied to the worst-case gap, possibly intrinsically. Our quantity is a direct test of that suspicion: the heterogeneity term should depend on the full spectrum weighted by where the skew lives, and the worst case appears only when skew aligns with $u_2$.
One paper supplies the closest competitor. Yes, Topology Matters in Decentralized Optimization (also Refined Convergence and Topology Learning) defines neighborhood heterogeneity, the gap between a node's one-hop averaged gradient and the global gradient. It then learns sparse graphs with Frank–Wolfe (STL-FW) to reduce it under label skew. Neighborhood heterogeneity is data-aware but blind to multi-hop structure. Two placements can have the same one-hop statistic yet differ in whether the skew is short-range, which washes out, or long-range, which does not. $\Phi$ distinguishes them; neighborhood heterogeneity cannot.
Two papers constrain the design. Topology-aware Generalization of Decentralized SGD shows that topology also affects the test-time generalization gap. We therefore measure test accuracy and train loss separately, rather than assuming optimization speed is the whole story. Row-Stochastic Matrices Can Provably Outperform Doubly Stochastic Matrices shows the choice of averaging weights itself changes outcomes when nodes hold unequal data. We hold weights to Metropolis–Hastings doubly stochastic weights for the main study and treat row-stochastic weights only as a secondary arm. The broader validation-gap literature contributes a methodological warning: synthetic tests tend to embed the assumptions of the proof being tested. Spielman's local clustering (A Local Clustering Algorithm for Massive Graphs) is one example of proof-dictated parameters diverging from practice. This is why our predictors are fixed in advance with no fitted parameters, and why graph families used for evaluation are held out.
Research Program
The work has three parts.
The first is a graph suite that goes beyond symmetric structures. It includes rings, tori, and exponential graphs for continuity with prior work. It adds irregular families that stand in for real deployments: random geometric graphs (the spatial meshes of sensors and drones), barbell and multi-cluster graphs with bottleneck links, preferential-attachment graphs with degree hubs, and time-varying rewired chains in the spirit of D-GADMM from GADMM. The suite uses 32 and 64 nodes, matching the worker counts in the prior experiments.
The second is a set of data placements on each graph. We use Dirichlet label skew at several concentrations. For each concentration we generate shard-to-node assignments that range from scattered, with skew loading fast eigenmodes, to cut-aligned, with skew loading $u_2$. Where possible we hold the one-hop neighborhood heterogeneity fixed across placements by searching over assignments.
The third is a predictor comparison. Every predictor is computed before training. The candidates are the spectral gap, the spectral gap times the scalar heterogeneity bound, the effective number of neighbors, Takezawa et al.'s full-spectrum sum, one-hop neighborhood heterogeneity, and $\Phi$. Each is ranked against measured outcomes.
Baselines
The naive reference point is the spectral gap alone, the quantity existing bounds are written in. It is the default because it is what a practitioner would compute today. It stands in for "do nothing beyond classical theory."
The strongest data-blind competitor is the full-spectrum sum from Improved Convergence Analysis of Topology Dependence in Decentralized SGD. It has the best documented track record on matched-gap graphs. The effective number of neighbors from Beyond spectral gap is reported alongside it.
The strongest data-aware competitor is neighborhood heterogeneity from Yes, Topology Matters, computed from the same initial gradients we use for $\Phi$. This makes the comparison one of equal information. For downstream graph design we also run STL-FW at the same maximum degree. That paper reports that STL-FW at degree 2 converges comparably to a fully connected 100-node network on MNIST, but the file gives no numerical accuracy, so we will reproduce it ourselves.
Fairness is enforced in three ways. Every predictor receives identical inputs, the graph and/or one gradient pass. No predictor has tuned constants beyond a single monotone fit shared across all of them. Training runs use one learning-rate grid per graph–placement pair, chosen on a validation split and identical across arms.
Beating the competitors means a higher Spearman rank correlation between $\Phi$ and iterations-to-target-loss on held-out graph families, with confidence intervals from bootstrapping over seeds and placements that exclude the competitor's value. In the permutation experiment, it means that $\Phi$ correctly orders placements that every data-blind metric, and neighborhood heterogeneity, rate as ties.
The key ablation replaces the weights $\lambda_i^2/(1-\lambda_i)^2$ with uniform weights. This turns $\Phi$ into a plain heterogeneity norm and isolates whether the spectral alignment, rather than the skew magnitude, carries the prediction.
Why not just…?
Why not just use the spectral gap times a heterogeneity constant, as existing bounds do? This predictor is constant across permutations of the same shards on the same graph, so it cannot explain any outcome difference between scattered and cut-aligned placements. If the permutation experiment finds no such differences, our claim fails and this baseline is vindicated. That makes it a real test, not a straw man.
Why not just use one-hop neighborhood heterogeneity, which is already data-aware? On short-range graphs it may match $\Phi$, and we expect it to on dense exponential graphs. The prediction diverges on large rings and bottlenecked geometric graphs, where long-wavelength skew passes every one-hop check yet persists for many averaging rounds. The equal-neighborhood-heterogeneity placements settle this directly.
Why not just run a short pilot of each candidate configuration and extrapolate? This is the most serious threat, because empirical probing sidesteps theory entirely. We include pilot runs at a compute budget matched to computing $\Phi$, and again at ten times that budget. We report where the pilot's rank correlation overtakes $\Phi$. If pilots win at roughly equal cost, the proposal's practical value shrinks to the explanatory one, and we will say so. The theory's added value would then lie in graph design, which pilots cannot do without searching over graphs.
Proposed Experiments
The decisive experiment is the permutation test. On fixed 32-node graphs we train ResNet-18 on CIFAR-10 and a small CNN on MNIST under Dirichlet label skew, using both D-SGD and gradient tracking with five seeds each. The only variable is the shard-to-node assignment. We measure consensus distance over time, iterations to a fixed train loss, and final test accuracy.
The prediction is that, for D-SGD, outcomes order by $\Phi$ while the spectral gap, the full-spectrum sum, and the effective number of neighbors are unchanged by construction. For gradient tracking, the ordering should mostly flatten. If D-SGD outcomes do not vary with placement, the core claim is false. If gradient tracking varies just as much, the drift mechanism is wrong even if the correlation holds.
The second experiment is the held-out family study. Predictors are compared on rings, tori, and exponential graphs, then evaluated without refitting on geometric, hub, barbell, and time-varying graphs. Rank correlation is reported separately per family, so that an aggregate never hides a failure on one family. Takezawa et al.'s ring and torus transient bounds, $O(n^5)$ and $O(n^3\log^2 n)$, give expected scaling we check at 32 versus 64 nodes.
The third experiment is downstream design. Starting from a sparse geometric mesh, we add $k$ edges chosen three ways: greedily reducing $\Phi$, greedily increasing the spectral gap, or by STL-FW at matched degree. We compare test accuracy at equal communication budget, logging wall-clock time under straggler delays to address the cost concern raised in Decentralized gradient methods: does topology matter?.
A final secondary check repeats the permutation test with row-stochastic weights following Row-Stochastic Matrices Can Provably Outperform Doubly Stochastic Matrices. Here $\Phi$ is computed from the eigenvectors in the corresponding weighted geometry. This tests whether the alignment idea carries over when nodes hold unequal amounts of data.
References
- Decentralized gradient methods: does topology matter?
- Beyond spectral gap: the role of the topology in decentralized learning
- Improved Convergence Analysis of Topology Dependence in Decentralized SGD
- Yes, Topology Matters in Decentralized Optimization: Refined Convergence and Topology Learning under Heterogeneous Data
- Refined Convergence and Topology Learning for Decentralized Optimization with Heterogeneous Data
- Topology-aware Generalization of Decentralized SGD
- Row-Stochastic Matrices Can Provably Outperform Doubly Stochastic Matrices in Decentralized Learning
- A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning
- GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning