stat.MLNov 17, 2026

Bounded-Order Non-Identifiability in Latent Structure Block Models: The Fiber in Closed Form

Authors: Sie Hendrata Dharmawan, Peter Chin

Organizations: Dartmouth College

Abstract

A graphon is determined by all of its homomorphism densities, but motif-based methods use finitely many. We compute exactly what that truncation costs in a natural family: latent structure block models whose positions lie on KK rays, equivalently degree-corrected block models of rank two. For a given radial law, the configurations that agree on every graph with fewer than 2K−12K-1 vertices form a one-dimensional fiber, which we give in closed form with explicit endpoints; the friendship graph FK−1F_{K-1} is its unique edge-minimal separator, so no fixed motif order serves every KK. The separating signal is suppressed by a factor of at most m12(K−1)m_1^{2(K-1)}, where m1m_1 is the mean squared slope, about 10−410^{-4} at K=4K=4: detecting it from motif counts would take about 101510^{15} nodes in a single graph, at any edge density. The information is nonetheless in the graph; the fiber belongs to the statistic, not the model. Common spectral pipelines, which count no motifs, still slide along the fiber by more than a third of its length at ordinary densities, with confidence regions that almost never contain the truth, while model-based fits of the same embedding do not. We give practitioners four checks: whether a fit is at risk, what to run instead, why a confidence interval will not warn, and how wide the remaining ambiguity is.

Figures & tables

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Oct 6, 2026

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

We study community recovery in the sparse symmetric stochastic block model with qq communities, average degree dd and signal strength λλ through statistical decision theory and Fisher information, and obtain three characterizations of the Kesten-Stigum threshold dλ2=1dλ^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-DD polynomial rules is the trivial risk times 1−CorrD21-\mathrm{Corr}_D^2. Combined with known low-degree and information-theoretic results, this gives the gap as a worst-case statement: for q≥5q\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)1-o(1). Second, the Fisher information about λλ carried by cycle counts is a series with terms of order k(dλ2)kk(dλ^2)^k, convergent exactly when dλ2<1dλ^2<1; below the threshold the relative error of every unbiased cycle-based estimator of λkλ^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 ∣λ∣d|λ|\sqrt{d} per iteration, and one EM step taken there leaves λλ unchanged. A signal-to-noise computation recovers the condition dλ1/χ>1dλ^{1/χ}>1 of Chin et al. for q=nχq=n^χ communities and identifies personalized PageRank as a walk count with suboptimal weights. Experiments on networks with up to 3×1053\times 10^5 vertices confirm the threshold for q=2q=2, the hard window for q=5q=5, and the many-community scaling.
Oct 19, 2026

Robust Latent Variable Graphical Models: Exact Recovery and Fundamental Limits

We study robust estimation of a Gaussian precision matrix that decomposes as a sparse matrix minus a symmetric, possibly indefinite, low-rank matrix, a structure that arises when latent-variable marginalization is combined with conditioning on linear measurements. The proposed convex estimator replaces the sample covariance by the centered Gaussian measure-transformed (MT) covariance, which preserves the signed graph of the sparse component under the nominal model, and penalizes the low-rank component by the nuclear norm of a congruence transform, an atomic norm that encodes structural side information. Our main result is a primal--dual witness theorem: under restricted invertibility and irrepresentability conditions on the Fisher information, the raw convex optimizer is unique, has no false edges, recovers the signs of all sufficiently strong edges, and has exactly the true rank and inertia. These conditions reduce to the graphical-lasso conditions when the low-rank part is absent, and we verify them from primitive incoherence and near-isotropy assumptions. Over a class on which they hold uniformly, we prove information-theoretic limits for Frobenius estimation, signed graph recovery, and inertia recovery. In particular, inertia recovery requires N≳p/νmin⁡2N\gtrsim p/ν_{\min}^2 samples, where νmin⁡ν_{\min} is the smallest nonzero eigenvalue modulus of the low-rank part; the spectral beta-min condition of the witness theorem is necessary up to a log⁡p\sqrt{\log p} factor; and the Frobenius risk attains the minimax rate up to a factor μ(1+min⁡{d,r})log⁡p\sqrt{μ(1+\min\{d,r\})\log p}, where μμ is the incoherence parameter, dd the maximal degree, and rr the rank. We further quantify robustness under Huber contamination, with a bias bound that is sharp for the MT functional and vanishes for remote outliers, and give a globally convergent linearized ADMM with closed-form updates.
Jul 7, 2026

Learning Sparsest Linear Causal DAGs with Latent Confounders via Higher-Order Cumulants

Recovering the exact directed acyclic graph (DAG) in linear non-Gaussian acyclic models with latent confounders (LvLiNGAM) remains a challenging problem. Although LvLiNGAM is identifiable only up to an observational equivalence class, each equivalence class is characterized by a unique sparsest DAG. Recovering the sparsest DAG from finite samples, however, remains difficult. Although existing methods are asymptotically consistent, they do not provide an explicit finite-sample procedure for recovering the unique sparsest DAG, nor do they handle models with an arbitrary number of latent confounders. In this paper, we propose a finite-sample method for recovering the sparsest DAG without imposing any restriction on the number of latent confounders. Simulation studies and real-data analyses demonstrate that the proposed method achieves superior finite-sample performance compared with existing approaches.