CS Paper Radar

Slow Beats Fast at the Kesten-Stigum Threshold: Minimax, Fisher-Information and Belief-Propagation Characterizations of the Information-Computation Gap in Sparse Stochastic Block Models

Soroor Ghandali

cs.IT cs.LGmath.PRmath.STstat.ML ·submitted 2026-10-06 05:43 UTC · v1

Abstract

We study community recovery in the sparse symmetric stochastic block model with $q$ communities, average degree $d$ and signal strength $λ$ through statistical decision theory and Fisher information, and obtain three characterizations of the Kesten-Stigum threshold $dλ^2=1$ and of the information-computation gap below it. First, on each community-size profile the minimax risk of any class of rules closed under averaging and vertex relabeling equals its Bayes risk under the uniform prior; the posterior mean is the unique Bayes rule and is admissible, and the Bayes risk of degree-$D$ polynomial rules is the trivial risk times $1-\mathrm{Corr}_D^2$. Combined with known low-degree and information-theoretic results, this gives the gap as a worst-case statement: for $q\ge 5$ there is a window below the threshold in which no low-degree rule beats the trivial risk asymptotically, while an exponential-time rule does on a set of labelings of probability $1-o(1)$. Second, the Fisher information about $λ$ carried by cycle counts is a series with terms of order $k(dλ^2)^k$, convergent exactly when $dλ^2<1$; below the threshold the relative error of every unbiased cycle-based estimator of $λ^k$ stays above an explicit constant, and every cycle-count test has success probability bounded below one. Third, the derivative of belief propagation at its uninformative fixed point multiplies a random perturbation by $|λ|\sqrt{d}$ per iteration, and one EM step taken there leaves $λ$ unchanged. A signal-to-noise computation recovers the condition $dλ^{1/χ}>1$ of Chin et al. for $q=n^χ$ communities and identifies personalized PageRank as a walk count with suboptimal weights. Experiments on networks with up to $3\times 10^5$ vertices confirm the threshold for $q=2$, the hard window for $q=5$, and the many-community scaling.

Comment
36 pages, 4 figures, 6 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Tightness and Error Exponents of SDP with Logarithmically Many Communities

cs.IT math.ST ·2026-10-07 ·Shengtao Guo, Ethan X. Fang, Junwei Lu
theory similarity 0.58
Abstract · 36 pages, 8 figures

We study a semidefinite programming (SDP) relaxation for community recovery when the number of communities grows logarithmically. In the balanced stochastic block model with $n=km$ vertices, we consider the regime $k/\log m\toγ>0$, with edge probabilities $α\log m/m$ within communities and $β\log m/m$ across them, for fixed $α>β>0$. We derive the sharp asymptotic tightness boundary away from critical cases. When rare vertices cause tightness to fail while the bulk remains spectrally stable, the normalized matrix error of every near-optimal solution still vanishes. We prove matching high-probability exponents for this error and the normalized optimal objective gain, governed by the same local correction that determines tightness. Throughout this spectrally stable region, a single SDP solve followed by explicit rounding and refinement achieves exact community recovery above the information-theoretic threshold. This guarantee holds even when the planted community matrix is not an optimal solution to the SDP.

0.31

Minimax Quantile Bounds via Information Measures

cs.IT math.ST ·2026-08-21 ·Amedeo Roberto Esposito
similarity 0.55
Abstract

We develop a unified information-theoretic framework for lower bounding minimax quantiles. The starting point is a loss-adapted Neyman--Pearson metaconverse that bounds the minimax success probability at every loss threshold and confidence level. The bound separates the small-ball behaviour of the prior under the loss from the statistical distinguishability of the observation model, and is optimised over an auxiliary output distribution. Different relaxations of this Neyman--Pearson bound yield converses based on \(f\)-informativity, Sibson mutual information \(I_α\), Maximal Leakage, and Amemiya norms. Classical Fano and Le Cam lower bounds are recovered as special cases. The framework also clarifies why different information measures are suited to different recovery criteria. Maximal Leakage is exact for a class of symmetric exact-recovery problems. We use this identity to derive finite-sample bounds on the full minimax exact-recovery risk in the balanced Gaussian weighted stochastic block model, as well as two-sided finite-sample minimax-quantile bounds for low-rank matrix estimation under isotropic bounded-energy noise. For approximate Hamming recovery, we exhibit a heterogeneous binary model in which an optimised finite Sibson order yields a strong converse while the Maximal Leakage specialisation is trivial. Finally, for one-coordinate Poisson localisation, a Bennett-type Young function used through its Amemiya norm recovers the exact success-probability scale, whereas classical Fano and fixed-power relaxations are strictly weaker. These results show that sharp converses for minimax quantiles require adapting the information measure to the recovery resolution, whether exact or approximate, and to the tail behaviour of the likelihood ratio.

0.45

Percolation in the Stochastic Block Model

cs.SI physics.soc-phcond-mat.stat-mechmath.PR ·2026-09-22 ·Luca Pieleanu, Moritz Laber, Narayan G. Sabhahit, Dmitri Krioukov
similarity 0.53
Abstract · 23 pages, 10 figures

The stochastic block model is a paradigmatic model of networks with community structure. Yet percolation in the model has been studied primarily in cases with a fixed block structure, even though in real networks, the community structure may evolve as the network grows. Here we study percolation in sequences of stochastic block models in which the numbers and sizes of communities, as well as the intra- and intercommunity connection probabilities may all change with the network size. We analyze five such sequences using two methods: linearized self-consistent equations for the locally tree-like models and a branching process at the community scale for the models with nonvanishing clustering. We find that the critical average degree is not generally equal to $1$, even in locally tree-like sequences, because the transition depends on how connections are distributed across the evolving community structure. We also show that the community-scale branching process accurately predicts the transition when intercommunity connections are sufficiently sparse, even in the presence of nonvanishing clustering, while a geometric stochastic block model sequence demonstrates the limitations of this method when correlations between intercommunity connections cannot be neglected. These results extend percolation studies in the stochastic block model to more realistic scenarios with evolving community structure, and may provide new methods to derive the upper and lower bounds for the percolation threshold in geometric long-range percolation.

0.19

BaCon: Band-Concentrated Exponential Random Graph Models

cs.SI ·2026-11-03 ·Enrico Schiazzano, Giulia Preti, Aristides Gionis, Matteo Riondato, Gianmarco De Francisci Morales
similarity 0.52
Abstract

Exponential-family random graph models ERGMs provide a parametric interpretable framework for modeling real graphs including the Web and social networks Fitted ERGMs may suffer from degeneracy matching observed graph statistics in expectation does not guarantee that the observed graph and similar ones are highly probable under the fitted distribution We introduce Band-Concentrated ERGMs BaCon a framework that avoids degeneracy by imposing a probabilistic constraint requiring at least $1-δ$ of the distribution probability mass to lie on the set of graphs with statistics within an $\varepsilon$-tolerance band around the observed statistics BaCons maximumentropy distribution still belongs to the exponential family while including a factor checking for inclusion in the tolerance band We derive the exact Metropolis-Hastings acceptance rule for this target and use a practical stochastic approximation procedure with a smoothed band membership during fitting Experiments on social networks across increasingly challenging model specifications show that BaCon substantially increases the probability mass assigned to graphs whose statistics are close to the observed ones while remaining estimable for specifications where standard ERGM estimation fails These results demonstrate that probability mass constraints are a principled way to mitigate degeneracy while retaining the benefits of exponential-family graph models

0.28

An Accuracy-Information Tradeoff for Loss-Difference Conditional Mutual Information

cs.LG cs.ITstat.ML ·2026-10-06 ·Hazar Yueksel
similarity 0.52
Abstract · v2: title metadata corrected (no change to the paper). 61 pages, of which 8 pages main text. Code, data and the Lean 4 formalization are in …

Loss-difference conditional mutual information (ld-CMI) uses the smallest of the standard observations in the supersample hierarchy of generalization bounds: it measures what a learner's loss differences reveal about which candidate of each pair it was trained on. Accuracy is known to force information into the model; data processing does not carry such lower bounds to losses. We show, by bounding three moments of the loss differences, that accuracy also forces ld-CMI. For linear predictors with a smooth convex loss of nonzero slope at zero, such as the logistic loss, plus a regularizer whose curvature and growth are both of power $r\ge2$, on product distributions over a scaled sign cube in dimension at least linear in $n$, every proper learner with expected excess risk at most $\varepsilon$ on these distributions at the optimal sample size $n\asymp\varepsilon^{-2+2/r}$ has worst-case ld-CMI of order $n$ bits, and $Θ(n/(1+(τ/\varepsilon)^2))$ bits under Gaussian noise of standard deviation $τ$ on the loss differences. The same holds without a regularizer, at $n\asymp\varepsilon^{-2}$. Consequently, range-scaled ld-CMI bounds cannot vanish on these distributions, although every proper learner's generalization gap is $O(n^{-1/2})$. We also show that model-level information does not determine noisy loss-difference information, and that the growth, slope and dimension conditions are needed, the last up to a logarithm.

0.35

Sharper bounds on the thresholds for sensitive and Blackwell optimality

cs.GT ·2026-10-07 ·Xavier Allamigeon, Stéphane Gaubert, Julien Grand-Clément, Ricardo Katz
similarity 0.51
Abstract

In perfect-information two-player stochastic games, the notions of Blackwell and sensitive optimality provide generalizations of the classical mean-payoff optimality and discount optimality criteria to account for more farsighted preferences. We provide bounds on the Blackwell threshold $α_{\sf bw}$ and the $d$-sensitive thresholds $α_{\sf d}$, defined as the smallest discount factors above which discount optimal policies coincide with Blackwell optimal policies and $d$-sensitive optimal policies respectively. Our refined bounds improve upon prior work by focusing on ``reduced'' families of polynomials and, crucially, our bounds are tight in terms of controlling the degrees and heights of the minimal polynomials of the Blackwell thresholds. We apply classical root separation based on Mahler's and Cauchy's bounds to our reduced families to derive the strongest upper and lower bounds on $α_{\sf bw}$ in the literature, and we are the first to obtain bounds on $α_{\sf d}$ in the multichain stochastic setting.

0.30

Smoothed Analysis for Distributed MIS

cs.DC ·2026-11-12 ·Dipan Dey, Fabien Dufoulon, William K. Moses, Gopal Pandurangan
theory similarity 0.51
Abstract

We study smoothed analysis of the distributed Maximal Independent Set (MIS) problem. Luby's algorithm computes an MIS in $O(\log n)$ rounds, while the recent $Ω(\log n/\log\log n)$ lower bound of Khoury and Schild (2026) shows that it is nearly optimal even in the LOCAL model. We ask whether small random perturbations can overcome this worst-case barrier. Given an arbitrary base graph $G$ on $n$ nodes, we consider the smoothed graph $\mathcal{G}_s=G\triangle G(n,p)$, where $G(n,p)$ is an independent random graph and $\triangle$ denotes symmetric difference. Thus, each possible edge is independently toggled with probability $p$. We establish nearly tight bounds on the smoothing needed for faster distributed MIS. For every base graph $G$, when $p=β\ln n/n$ for a sufficiently large constant $β$, a randomized LOCAL algorithm, given only $\mathcal{G}_s$, computes an MIS of $\mathcal{G}_s$ in $O(\sqrt{\log n})$ rounds with high probability. This is almost quadratically faster than the worst-case lower bound. Conversely, if $p\le(1/2-δ)\ln n/n$ for a fixed constant $δ>0$, there exists a base graph on which every randomized LOCAL MIS algorithm requires $Ω(\log n/\log\log n)$ rounds on the smoothed graph. Hence, the smoothing parameter required for this speedup is optimal up to a constant factor. These results show that smoothed analysis can overcome worst-case lower-bound barriers for distributed local graph problems.

0.10

Local Fisher Information Enables Sparse Causal Discovery

cs.LG stat.ML ·2026-10-03 ·Byeongguk Kang, Donghyeon Lee, Euijong Song, Gunwoong Park
theory similarity 0.51
Abstract

Sparse causal discovery calls for methods that exploit graph structure without estimating high-dimensional densities. We introduce Fisher Information Completion Search (FiCS), a source-first algorithm for additive noise models that uses one local Fisher score for both ordering and parent selection. Under regularity and nonconstant-parent conditions, we prove that a node's local Fisher information equals the noise Fisher information exactly when the conditioning set contains all parents, provided that it contains no descendants. This Fisher parent completion identifies the parent set as the unique minimal Fisher completion. With a maximum conditioning set size $q$ at least the maximum indegree $d$, population FiCS queries marginals of at most $q+1$ variables and recovers the true directed acyclic graph under a positive ordering margin. Bounded conditioning also has a population advantage: reducing $q$ toward $d$ cannot decrease, and can strictly increase, the ordering margin. A growing non-Gaussian family separates local Fisher selection from conditional-variance and leaf-first Fisher ordering. For the regularized kernel Stein estimator, we establish high-dimensional DAG consistency under $q\{1+\log(p/q)\}+\log p=o(n)$, uniform Fisher separation, local approximation, and compatible ridge and parent penalty parameters. Experiments show the strongest gains when $n$ is small relative to $p$, quantify the effect of the conditioning size, and demonstrate competitive reference-graph recovery on three real-data benchmarks.

0.31