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 K 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−1 vertices form a one-dimensional fiber, which we give in closed form with explicit endpoints; the friendship graph FK−1 is its unique edge-minimal separator, so no fixed motif order serves every K. The separating signal is suppressed by a factor of at most m12(K−1), where m1 is the mean squared slope, about 10−4 at K=4: detecting it from motif counts would take about 1015 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
pair A
pair B
rel. diff.
m1
0.21744283
0.21744283
0 (50 digits)
m2
0.05862892
0.05862892
0 (50 digits)
m3
0.01632560
0.02369236
45.1%
t(F3)
—
—
7.551×10−7
Table 1: Two configurations on one K=4 fiber. The census matches below order 7 exactly; the separator reads a 45% moment gap as 10−6 .
n∗ (extrapolated)
K
ΔmK−1
Δt(FK−1)
200 graphs
1 graph
4
45.1%
7.6×10−7
1012 – 1013
2×1015
5
3.81%
2.3×10−8
2×1015
3×1017
6
1.74%
3.6×10−9
3 – 6×1016
4×1018
Table 2: Census route by K (threshold order 2K−1 ): moment and density separation along the fiber, and the extrapolated n∗ with 200 graphs or one graph per configuration.
Figure 1: P1-cluster at configuration HI ( wmin=0.0375 ), n=32,000 . Top: the fiber and estimates in the fiber’s best-fit plane at two densities. Bottom: the same estimates in intrinsic coordinates (position along the fiber versus signed distance across it). At mean degree 720 every estimate lies close to the curve yet is displaced 31% of the arc along it.
HI
wmin=0.03
LO
w^/w
method
(720)
(500)
(500)
HI
P1-cluster
31.0
49.9
4.5
4.4
row-normalized SC
43.5
58.0
3.3
7.3
spherical + GMM
26.7
37.4
5.5
4.0
SCORE
4.3
7.4
46.4
2.0
SCORE + filter
26.7
52.3
3.7
3.9
Table 3: Median total error ∣θ^−θ0∣ , % of arc, R=200 (mean degree in parentheses), and fitted-to-true minority weight at HI. SCORE at LO is bimodal. † Along-fiber RMSE over all R=20 chains.
Figure 2: Intrinsic along-fiber displacement of P1-cluster over 276 cells ( 9 density levels; up to 21 steep-ray and 10 shallow-ray configurations). Left: minority on the steep ray; right: on the shallow ray, where wmin≥0.19 . The safe region is top right. The hatched row (mean degree 45 ) is estimator breakdown (off-curve error).
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
fit
share
τ1
τ2
α1
objective
atoms collapsed
48.0%
0.218
0.218
0.720
1.197
atoms maximally apart
51.5%
0.0000
0.7777
0.720
1.240
truth
—
0.0115
0.2725
0.2111
1.232
Appendix
Table 4: P2 ′′ fits at LO, C=0.75 , n=32,000 .
Figure 3: Three estimators on identical graphs at LO, C=0.75 , n=32,000 . Unconstrained P2 returns no valid slope law here and is not shown. P2 ′′ fits sit on the boundary of the admissible set; its ±23% replicate spread is the gap between two point masses, not dispersion.
config
wmin
displacement
spread
ratio
LO
0.2111
+2.65
0.232
11
MID
0.3140
−4.96
0.341
15
HI
0.0375
−31.4
4.67
6.7
pair B
0.0361
−33.1
4.42
7.5
Appendix
Table 5: P1-cluster at C=0.3 , n=32,000 : intrinsic signed along-fiber displacement (bias) and spread, % of arc ( + toward the pair-B end).
Figure 4: P1-Prony at LO, n=32,000 : displaced 6.1% at C=0.75 and 38.9% at C=0.3 (intrinsic mean displacement, 200 replicates per cell).
P1-cluster
P1-Prony
tilt
heavy tail of T^ crosses 2-means boundary
third-moment inflation ( +40 – 64% )
error type
classification
estimation of a moment
worst at
small minority weight (steep ray)
wherever the arc has room above
sign
toward α1=0.5 fold (90/90, 162/186)
toward larger m3 (229/276)
Appendix
Table 6: The two tilts.
est.
minority ray
C
n
deg.
largest disp.
Δm3
at wmin
safe from wmin≥
safe from w^min≥
unsafe
of
P1-c
shallow
0.75
2000
281
+9.23
+3.32
0.2732
0.4458
0.4796
8
10
P1-c
shallow
0.75
8000
1125
+1.52
+0.529
0.3154
0.1936
0.1991
0
10
P1-c
shallow
0.75
32000
4500
+0.194
+0.0684
0.3154
0.1936
0.1932
0
10
P1-c
shallow
0.5
2000
125
+29.1
+11.1
0.1936
none
–
10
10
P1-c
shallow
0.5
8000
500
+5.21
+1.95
0.2732
0.3584
0.4009
3
10
P1-c
shallow
0.5
32000
2000
+0.718
+0.252
0.3154
0.1936
0.1952
0
10
Appendix
Table 8: Largest along-fiber displacement and safe region, per estimator, branch and (C,n) . Displacement is intrinsic and signed (% of the reference arc; + toward the pair-B end), with the relative change in m3 at the landing point. Safe means ∣ displacement ∣<5% for this and every larger minority weight on the same branch, stated on the true and on the fitted weight scale; “none means no safe weight on that branch. unsafe of : unsafe points out of points on the branch. Mean degree 45 is estimator breakdown (off-curve error) and is not comparable to the other rows.
est.
C
n
deg.
R
config
wmin
disp.
± SE
spread
RMSE
Δm3
w^/w
dist/ ∣e∣
≤0.02
flags
P1-c
0.75
2000
281
400
LO
0.2111
+8.62
0.069
1.37
8.73
+3.78
1.373
0.3486
0
–
P1-c
0.75
2000
281
400
pair A
0.2552
+9.23
0.073
1.46
9.34
+3.48
1.342
0.3659
0
–
P1-c
0.75
2000
281
400
MID
0.314
-8.26
0.092
1.85
8.47
-2.44
1.305
0.5534
0
–
P1-c
0.75
2000
281
400
HI
0.03754
-48.8
0.3
5.92
49.2
-21.1
9.07
0.09744
2
–
P1-c
0.75
2000
281
400
pair B
0.03613
-50.3
0.29
5.75
50.6
-21.6
9.536
0.0902
2.25
–
P1-c
0.75
8000
1126
200
LO
0.2111
+1.09
0.027
0.38
1.16
+0.533
1.038
0.4616
100
–
Appendix
Table 11: The named configurations at every (C,n) . disp. : intrinsic signed along-fiber bias; spread : replicate SD of the intrinsic position; both in % of the reference arc. R : replicates (pooled runs at n=2000 ). dist/ ∣e∣ : median distance to the fiber over the distance ∣e∣=∣θ^−θ0∣ to the truth. ≤0.02 : share of replicates within 0.02 of the fiber in θ . Flags: bs (sign opposite to the P1-cluster branch pattern), bd (breakdown, mean degree 45), n.s. (not significant at 2 SE), boundary (configuration at the arc end).
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−CorrD2. Combined with known low-degree and information-theoretic results, this gives the gap as a worst-case statement: for q≥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 ∣λ∣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×105 vertices confirm the threshold for q=2, the hard window for q=5, and the many-community scaling.
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/νmin2 samples, where ν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 logp factor; and the Frobenius risk attains the minimax rate up to a factor μ(1+min{d,r})logp, where μ is the incoherence parameter, d the maximal degree, and r 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.
Chuansen Peng, Xiaojing Shen
School of Mathematics, Sichuan University, Chengdu 610064, China
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.
Ming Cai, Hisayuki Hara
Graduate School of Informatics, Kyoto University, Kyoto, Japan · Institute for Liberal Arts and Sciences, Kyoto University, Kyoto, Japan