Detector-Output Instability near the Kesten–Stigum Boundary: Separating Hard Readout, Relaxation, and Fixed-Point Dispersion

Faruk Alpay, Barış Başaran · 2026

Read Detector-Output Instability near the Kesten–Stigum Boundary: Separating Hard Readout, Relaxation, and Fixed-Point Dispersion by Faruk Alpay, Barış Başaran (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-30346.txt.

Introduction

Faruk Alpay and Barış Başaran study why community detection algorithms disagree with themselves near a famous threshold. The Kesten–Stigum boundary marks where communities become detectable in random networks. Algorithms return one partition, hiding how unstable that answer is. The authors track the whole spread of outputs instead. Three paired measures separate readout effects from real spread.

Their testbed is the symmetric sparse stochastic block model. Linearized belief propagation recovers the standard onset condition. The hard partition instability peaks slightly past the boundary. That peak moves when the polarization cutoff changes, a readout artifact. A clean cutoff law governs the activation offset's median. Residual gating then separates readout effects from critical slowing down. Near threshold, gated runs show zero disagreement among themselves. Deeper inside, genuine fixed-point dispersion survives the gating. Large network audits confirm a small plateau above the boundary.

Catalog record

CREATORFaruk Alpay, Barış Başaran
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.30346

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Detector-Output Instability near the Kesten–Stigum Boundary: Separating Hard Readout, Relaxation, and Fixed-Point Dispersion Faruk Alpay, Barış Başaran Abstract Community-detection algorithms usually return a single partition, even when the same network supports several plausible outputs under independent initializations or small data perturbations. We study this output distribution through three paired observables: hard-partition variation of information (VI), a residual-gated fixed-point VI, and a cutoff-free Jensen–Shannon distance between BP marginal fields. For the symmetric sparse stochastic block model, linearizing belief propagation around the uninformative fixed point gives the standard Kesten–Stigum onset condition ( c in − c out ) 2 / ( q 2 ​ c ) = snr 2 = 1 (c_{\mathrm{in}}-c_{\mathrm{out}})^{2}/(q^{2}c)=\mathrm{snr}^{2}=1 , with snr = ( c in − c out ) / ( q ​ c ) \mathrm{snr}=(c_{\mathrm{in}}-c_{\mathrm{out}})/(q\sqrt{c}) . This calculation locates the linear onset. The maximum of the hard VI readout is a finite-size detector curve: in the synthetic sweeps it lies on the detectable side, typically snr ⋆ ≃ 1.05 \mathrm{snr}^{\star}\simeq 1.05 – 1.10 1.10 . The hard-readout peak is readout-dependent. On the same BP outputs, changing the polarization cutoff from 0.001 0.001 to 0.1 0.1 moves snr ⋆ \mathrm{snr}^{\star} across 1.047 1.047 – 1.128 1.128 and lowers the peak VI from about 1.83 1.83 to 1.49 1.49 bits at the largest cutoff. The nontrivial-readout activation point has a clean cutoff law: the median activation offset satisfies snr 50 ​ ( τ ) − 1 = 0.0086 + 0.522 ​ τ \mathrm{snr}_{50}(\tau)-1=0.0086+0.522\tau with R 2 = 0.996 R^{2}=0.996 over the same sweep. Long-budget residual gating separates this readout effect from critical slowing. At snr = 1.05 \mathrm{snr}=1.05 and 1.10 1.10 , the 2500-iteration hard VI is 1.49 1.49 and 1.58 1.58 bits, but the residual-gated subsets have zero VI and zero marginal dispersion. From snr = 1.15 \mathrm{snr}=1.15 through 1.30 1.30 , all or nearly all runs pass the gate and retain VI 1.31 1.31 down to 1.24 1.24 bits, with marginal dispersion 0.056 0.056 – 0.085 0.085 bits per node. A high-replication large- N N audit uses thirty graph draws at each sampled point through N = 100000 N=100000 . The large- N N peak locations are 1.024 1.024 , 1.022 1.022 , 1.025 1.025 , and 1.024 1.024 for N = 16000 , 32000 , 64000 , 100000 N=16000,32000,64000,100000 . A zero-asymptote power law is disfavored; the measured high- N N behavior is a small plateau snr ⋆ − 1 ≃ 0.024 \mathrm{snr}^{\star}-1\simeq 0.024 with graph-bootstrap 90% interval [ 0.0227 , 0.0316 ] [0.0227,0.0316] . On real networks, a label-free Bethe-Hessian modularity margin and a Chung–Lu null gate are evaluated on political blogs and six SNAP graphs. The real-network benchmark confirms that the measurement can be run label-free, while heterogeneous networks can retain null-significant structure even after strong edge subsampling. The final claim is a detector-output decomposition near the Kesten–Stigum boundary, with hard readout, relaxation dynamics, and fixed-point-field dispersion reported separately. 1 Introduction Community detection asks for a partition of a network into groups that are densely connected internally and sparsely connected externally [ 1 , 2 ] . Standard algorithms return one partition, but the inferential object is often a distribution. Independent optimizer initializations, bootstrap edge perturbations, and changes of objective can yield partitions that have similar scores but different node assignments. The issue goes beyond implementation: modularity maximization has an extensively degenerate landscape of high-scoring partitions [ 3 ] , and recent work on solution-landscape exploration and overlap-gap geometry treats the distribution of near-optimal partitions as a structural feature of the problem [ 4 , 5 ] . Related ensemble perspectives appear in consensus clustering and Bayesian blockmodel uncertainty [ 22 , 24 ] . We call the dispersion of plausible algorithmic outputs partition degeneracy . The stochastic block model (SBM) supplies a controlled setting in which this dispersion can be related to a known transition. In the sparse symmetric SBM, community recovery undergoes the Kesten–Stigum transition [ 9 , 10 , 11 , 12 , 13 , 14 ] : above the threshold the planted partition has nonzero overlap with efficient estimators, whereas below it no estimator improves over chance. Belief propagation attains this threshold [ 11 ] ; spectral algorithms based on the non-backtracking operator and the Bethe Hessian attain the same boundary [ 16 , 17 ] . Finite networks round the transition but preserve its scaling structure [ 15 ] . The statistical-physics description is a changing landscape of fixed points and metastable states. Kawamoto and Kabashima counted metastable modularity states and located an algorithmic limit through the complexity of that landscape [ 18 ] . This paper turns that landscape picture into a detector-output decomposition. We measure the hard partition readout used by a practical pipeline, the cutoff-free dispersion of BP marginal fields, and the residual-gated part of the BP ensemble that has reached a fixed point. The hard VI curve has an offset peak above \mathrm{snr}=1 in finite sparse SBMs. The new controls show how much of that peak comes from hard readout and critical slowing, and where a budget-stable fixed-point ensemble remains. Contributions and scope. The paper makes the following claims and limitations explicit. • We define hard-readout partition degeneracy as the mean variation of information among an algorithmic ensemble of detected partitions and express it as a function of the partition-overlap matrix. The definition is label-permutation invariant and requires no ground truth, but it is a joint property of the detector ensemble and the graph (Sections 2 – 3 ). • We recall the Kesten–Stigum scaling coordinate from the linearization of belief propagation around the uninformative fixed point. This calculation gives the onset reference \mathrm{snr}=1 . We use cutoff-free marginal-field dispersion and residual-gated VI to separate hard readout from BP fixed-point convergence (Section 3 ). • We measure the finite-size offset of the hard-readout ridge. In the phase diagram it lies in 1.05\leq\mathrm{snr}^{\star}\leq 1.15 , and in the size sweep it moves from \mathrm{snr}^{\star}\approx 1.09 at N=500 to \mathrm{snr}^{\star}\approx 1.05 at N=8000 . We add a high-replication large- N audit through N=100000 . The large- N offset is a small plateau near 0.024 , so the earlier zero-asymptote exponent fit is replaced by a plateau scaling statement (Sections 5 and 7 ). • We report a peak-normalized alignment across twelve block-count and mean-degree combinations and compare its spread to a permutation null. This supports a nonrandom alignment of the finite-size detector curves while staying below an exact universality claim (Section 6 ). • We use a partition-space embedding to show that the detected-partition cloud broadens in the weakly detectable band, and we add controls that separate fixed-graph initialization noise from pooled graph sampling, expose the polarization-cutoff readout artifact, record BP iteration counts, residuals, matched-budget partition drift, a cutoff-free marginal-dispersion observable, and a Bethe free-entropy proxy (Sections 8 – 9 ). • We add a q=5 hard-phase probe comparing random BP initialization with a weak planted warm start. The probe finds no well-converged sub-Kesten–Stigum coexistence band for the tested detector, so the main claims remain restricted to the continuous q\leq 4 regime (Section 10 ). • We repeat the measurement on political blogs and on six public SNAP networks. The real-network coordinate is label-free: a Bethe-Hessian modularity

Read the complete text