The non-tightness of the reconstruction threshold of a 4 states symmetric model with different in-block and out-block mutations

Ning Ning; Wenjian Liu

arxiv: 1906.09479 · v1 · pith:NRAPWWNHnew · submitted 2019-06-22 · 📊 stat.ML · cs.LG· math.PR

The non-tightness of the reconstruction threshold of a 4 states symmetric model with different in-block and out-block mutations

Wenjian Liu , Ning Ning This is my paper

Pith reviewed 2026-05-25 17:56 UTC · model grok-4.3

classification 📊 stat.ML cs.LGmath.PR

keywords tree reconstructionstochastic block modelreconstruction thresholdnon-tightness4-state modelhybrid-hard phasebroadcasting on trees

0 comments

The pith

Conditions exist under which the reconstruction threshold of a 4-state symmetric model is not tight.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The tree reconstruction problem checks whether root information survives at arbitrarily deep levels of a tree. Its link to stochastic block model clustering creates hybrid-hard phases whenever the reconstruction threshold fails to be tight. This paper examines a 4-state symmetric model in which in-block and out-block transition probabilities differ. It derives explicit conditions on those probabilities under which the threshold is provably non-tight. The result identifies parameter regimes where 4-community clustering is information-theoretically possible yet computationally hard.

Core claim

In the 4-state symmetric model with distinct in-block and out-block transition probabilities, the reconstruction threshold on regular trees is not tight whenever the parameters satisfy the inequalities established in the paper.

What carries the argument

The 4-state symmetric model with different in-block and out-block transition probabilities, which produces distinct decay rates for information inside versus outside blocks.

If this is right

The corresponding 4-community stochastic block model possesses a hybrid-hard phase under the identified conditions.
Root information can be recovered from the leaves in some parameter regimes but not others.
The non-tightness result extends earlier tightness proofs from symmetric two-state models to this four-state asymmetric case.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Similar non-tightness may appear in other multi-state models once in-block and out-block rates are allowed to differ.
Clustering algorithms for four-community graphs may need separate procedures for the hybrid-hard region identified here.

Load-bearing premise

The established connection between tree reconstruction and stochastic block model clustering continues to hold for this 4-state model.

What would settle it

An explicit computation of the root-to-leaf mutual information that decays exactly at the usual Kesten-Stigum threshold rather than strictly inside the claimed non-tight region would falsify the result.

read the original abstract

The tree reconstruction problem is to collect and analyze massive data at the $n$th level of the tree, to identify whether there is non-vanishing information of the root, as $n$ goes to infinity. Its connection to the clustering problem in the setting of the stochastic block model, which has wide applications in machine learning and data mining, has been well established. For the stochastic block model, an "information-theoretically-solvable-but-computationally-hard" region, or say "hybrid-hard phase", appears whenever the reconstruction bound is not tight of the corresponding reconstruction on the tree problem. Although it has been studied in numerous contexts, the existing literature with rigorous reconstruction thresholds established are very limited, and it becomes extremely challenging when the model under investigation has $4$ states (the stochastic block model with $4$ communities). In this paper, inspired by the newly proposed $q_1+q_2$ stochastic block model, we study a $4$ states symmetric model with different in-block and out-block transition probabilities, and rigorously give the conditions for the non-tightness of the reconstruction threshold.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper claims to give rigorous conditions for non-tightness in a 4-state tree model with asymmetric in/out mutations, but the abstract leaves the key mapping and derivations uncheckable.

read the letter

This paper targets the reconstruction threshold for a 4-state symmetric channel where in-block and out-block transition probabilities are allowed to differ. It uses the q1+q2 SBM construction to produce explicit conditions under which the threshold is not tight, which would mark the hybrid-hard region for four communities. That is the central claim and the part that is new relative to the limited existing rigorous results for q=4 models. The work stays inside the standard broadcasting-on-trees framework and does not introduce new proof techniques, but it does apply the framework to a variant that had not been handled before. The abstract is clear that the conditions are derived rigorously rather than fitted. The soft spot is exactly the one the stress-test flags: the tree-SBM equivalence and the second-moment or fixed-point arguments were originally worked out for symmetric channels. When the mutation matrix becomes asymmetric in the in/out sense, those calculations can shift, and nothing in the abstract shows that the stability analysis was redone for the new transition probabilities. Without the derivations it is impossible to tell whether the non-tightness conditions rest on a fresh verification or on an unadjusted carry-over. The paper is therefore for readers who already follow the reconstruction-threshold literature and want to see the q=4 case pushed one step further. A specialist would get value from the explicit conditions if they survive checking; a general reader would not. It deserves a serious referee to inspect the mapping and the algebra, even though the current evidence is only the abstract.

Referee Report

2 major / 1 minor

Summary. The manuscript examines the tree reconstruction problem on a 4-state symmetric channel whose transition probabilities differ between in-block and out-block pairs. It claims to derive rigorous conditions under which the reconstruction threshold is not tight, thereby identifying an information-theoretically solvable but computationally hard regime in the associated 4-community stochastic block model.

Significance. A correct derivation would enlarge the small collection of models for which non-tightness of the reconstruction threshold has been proved, thereby clarifying the location of the hybrid-hard phase for community detection with four groups. The extension from symmetric q-ary channels to the asymmetric in/out mutation structure is a non-trivial technical step whose validity determines the result's reach.

major comments (2)

[Introduction / Model definition] The equivalence between root reconstruction on the tree and community detection in the corresponding SBM must be re-established for the new transition matrix. Standard second-moment or fixed-point arguments were derived for symmetric channels; the differing in-block and out-block probabilities alter the relevant stability analysis and the paper must show explicitly that the non-tightness criterion still follows from the same mutual-information or reconstruction threshold expressions.
[Main result / Theorem statement] The main theorem stating the conditions for non-tightness (presumably in §4 or §5) relies on the claim that the 4-state model inherits the known tree-SBM connection. If the proof invokes prior results for q-ary symmetric channels without re-deriving the Kesten-Stigum threshold or the second-moment bound for the asymmetric case, the rigor of the stated conditions is not secured.

minor comments (1)

[Abstract] The abstract asserts that 'rigorous conditions are given' but does not state what those conditions are; a one-sentence summary of the main theorem would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on the equivalence between tree reconstruction and the SBM for our 4-state model with differing in-block and out-block transitions. We address each major comment below and will revise the manuscript accordingly.

read point-by-point responses

Referee: [Introduction / Model definition] The equivalence between root reconstruction on the tree and community detection in the corresponding SBM must be re-established for the new transition matrix. Standard second-moment or fixed-point arguments were derived for symmetric channels; the differing in-block and out-block probabilities alter the relevant stability analysis and the paper must show explicitly that the non-tightness criterion still follows from the same mutual-information or reconstruction threshold expressions.

Authors: We agree that the equivalence must be re-established explicitly for the new transition matrix. In the revised manuscript we will insert a dedicated subsection (in the model definition or introduction) that adapts the second-moment method and fixed-point analysis to the case of distinct in-block and out-block probabilities, confirming that the non-tightness criterion continues to follow from the corresponding mutual-information and reconstruction-threshold expressions. revision: yes
Referee: [Main result / Theorem statement] The main theorem stating the conditions for non-tightness (presumably in §4 or §5) relies on the claim that the 4-state model inherits the known tree-SBM connection. If the proof invokes prior results for q-ary symmetric channels without re-deriving the Kesten-Stigum threshold or the second-moment bound for the asymmetric case, the rigor of the stated conditions is not secured.

Authors: We acknowledge the concern. The current proof sketch may rely too heavily on prior symmetric-channel results. In the revision we will expand the proof of the main theorem to contain a self-contained derivation of the Kesten-Stigum threshold and the second-moment bound that accounts for the asymmetric in/out-block transition structure, thereby securing the rigor of the stated non-tightness conditions. revision: yes

Circularity Check

0 steps flagged

No circularity; tree-SBM connection cited as externally established

full rationale

The abstract states the tree reconstruction to SBM clustering connection 'has been well established' and claims to 'rigorously give the conditions for the non-tightness' for the new 4-state model. No self-citations, fitted parameters renamed as predictions, or definitional reductions are visible. The derivation is presented as building on prior external results with new analysis for the asymmetric transition probabilities, satisfying the criteria for a self-contained result.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only abstract available; no explicit free parameters, axioms, or invented entities can be extracted.

pith-pipeline@v0.9.0 · 5733 in / 936 out tokens · 22427 ms · 2026-05-25T17:56:05.391554+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Main Theorem. If |λ1|≠|λ3| and 0<|λ2|<max{|λ1|,|λ3|}, the Kesten-Stigum bound is not tight for every d...
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

the connection between the reconstruction on the tree problem and the clustering problem in the setting of the stochastic block model

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages · 2 internal anchors

[1]

Banks, C

J. Banks, C. Moore, J. Neeman, and P. Netrapalli , Information-theoretic thresholds for community detection in sparse networks , in Conference on Learning Theory, 2016, pp. 383– 416

work page 2016
[2]

Bernussou and J.-L

J. Bernussou and J.-L. Abatut , Point mapping stability , Pergamon, 1977. 20 W. LIU AND N. NING

work page 1977
[3]

Bhamidi, R

S. Bhamidi, R. Rajagopal, and S. Roch , Network delay inference from additive metrics , Random Structures & Algorithms, 37 (2010), pp. 176–203

work page 2010
[4]

P. M. Bleher, J. Ruiz, and V. A. Zagrebnov , On the purity of the limiting Gibbs state for the Ising model on the bethe lattice , Journal of Statistical Physics, 79 (1995), pp. 473–482

work page 1995
[5]

Borgs, J

C. Borgs, J. Chayes, E. Mossel, and S. Roch , The Kesten-Stigum reconstruction bound is tight for roughly symmetric binary channels , in Foundations of Computer Science, 2006. FOCS’06. 47th Annual IEEE Symposium on, IEEE, 2006, pp. 518– 530

work page 2006
[6]

Brito, I

G. Brito, I. Dumitriu, S. Ganguly, C. Hoffman, and L. V. Tran , Recovery and rigidity in a regular stochastic block model , in Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial a nd Applied Mathematics, 2016, pp. 1589–1601

work page 2016
[7]

Chayes, L

J. Chayes, L. Chayes, J. P. Sethna, and D. Thouless , A mean ﬁeld spin glass with short- range interactions, Communications in Mathematical Physics, 106 (1986), pp. 4 1–89

work page 1986
[8]

Daskalakis, E

C. Daskalakis, E. Mossel, and S. Roch , Optimal phylogenetic reconstruction, in Proceedings of the thirty-eighth annual ACM symposium on Theory of compu ting, ACM, 2006, pp. 159– 168

work page 2006
[9]

Evans, C

W. Evans, C. Kenyon, Y. Peres, and L. J. Schulman , Broadcasting on trees and the Ising model, Annals of Applied Probability, (2000), pp. 410–433

work page 2000
[10]

Kesten and B

H. Kesten and B. P. Stigum , Additional limit theorems for indecomposable multidimens ional galton-watson processes, The Annals of Mathematical Statistics, 37 (1966), pp. 1463 –1481

work page 1966
[11]

Kesten and B

H. Kesten and B. P. Stigum , Limit theorems for decomposable multi-dimensional galton - watson processes, Journal of Mathematical Analysis and Applications, 17 (19 67), pp. 309– 338

work page
[12]

M. Kimura , A simple method for estimating evolutionary rates of base su bstitutions through comparative studies of nucleotide sequences , Journal of molecular evolution, 16 (1980), pp. 111–120

work page 1980
[13]

W. Liu, S. R. Jammalamadaka, and N. Ning , The tightness of the Kesten-Stigum reconstruc- tion bound of symmetric model with multiple mutations , Journal of Statistical Physics, 170 (2018), pp. 617–641

work page 2018
[14]

Liu and N

W. Liu and N. Ning , Big data information reconstruction on an inﬁnite tree for a 4 × 4-state asymmetric model with community eﬀects , arXiv preprint arXiv:1812.10475, (2018)

work page arXiv 2018
[15]

Liu and N

W. Liu and N. Ning , Large degree asymptotics and the reconstruction threshold of the asym- metric binary channels , Journal of Statistical Physics, (2018), pp. 1–28

work page 2018
[16]

M ´ezard and A

M. M ´ezard and A. Montanari , Reconstruction on trees and spin glass transition , Journal of statistical physics, 124 (2006), pp. 1317–1350

work page 2006
[17]

Mossel , Reconstruction on trees: beating the second eigenvalue , Annals of Applied Proba- bility, (2001), pp

E. Mossel , Reconstruction on trees: beating the second eigenvalue , Annals of Applied Proba- bility, (2001), pp. 285–300

work page 2001
[18]

Mossel , Phase transitions in phylogeny , Transactions of the American Mathematical Soci- ety, 356 (2004), pp

E. Mossel , Phase transitions in phylogeny , Transactions of the American Mathematical Soci- ety, 356 (2004), pp. 2379–2404

work page 2004
[19]

Mossel , Survey: information ﬂow on trees , DIMACS series in discrete mathematics and theoretical computer science, 63 (2004), pp

E. Mossel , Survey: information ﬂow on trees , DIMACS series in discrete mathematics and theoretical computer science, 63 (2004), pp. 155–170

work page 2004
[20]

Deep Learning and Hierarchal Generative Models

E. Mossel , Deep learning and hierarchal generative models , arXiv preprint arXiv:1612.09057, (2016)

work page internal anchor Pith review Pith/arXiv arXiv 2016
[21]

Mossel, J

E. Mossel, J. Neeman, and A. Sly , A proof of the block model threshold conjecture , Combi- natorica, (2013), pp. 1–44

work page 2013
[22]

Mossel, J

E. Mossel, J. Neeman, and A. Sly , Belief propagation, robust reconstruction and optimal recovery of block models , in Conference on Learning Theory, 2014, pp. 356–370

work page 2014
[23]

Non-Reconstructability in the Stochastic Block Model

J. Neeman and P. Netrapalli , Non-reconstructability in the stochastic block model , arXiv preprint arXiv:1404.6304, (2014)

work page internal anchor Pith review Pith/arXiv arXiv 2014
[24]

Ricci-Tersenghi, G

F. Ricci-Tersenghi, G. Semerjian, and L. Zdeborov ´a, Typology of phase transitions in bayesian inference problems , Physical Review E, 99 (2019), p. 042109

work page 2019
[25]

Sly , Reconstruction for the Potts model , The Annals of Probability, 39 (2011), pp

A. Sly , Reconstruction for the Potts model , The Annals of Probability, 39 (2011), pp. 1365– 1406

work page 2011

[1] [1]

Banks, C

J. Banks, C. Moore, J. Neeman, and P. Netrapalli , Information-theoretic thresholds for community detection in sparse networks , in Conference on Learning Theory, 2016, pp. 383– 416

work page 2016

[2] [2]

Bernussou and J.-L

J. Bernussou and J.-L. Abatut , Point mapping stability , Pergamon, 1977. 20 W. LIU AND N. NING

work page 1977

[3] [3]

Bhamidi, R

S. Bhamidi, R. Rajagopal, and S. Roch , Network delay inference from additive metrics , Random Structures & Algorithms, 37 (2010), pp. 176–203

work page 2010

[4] [4]

P. M. Bleher, J. Ruiz, and V. A. Zagrebnov , On the purity of the limiting Gibbs state for the Ising model on the bethe lattice , Journal of Statistical Physics, 79 (1995), pp. 473–482

work page 1995

[5] [5]

Borgs, J

C. Borgs, J. Chayes, E. Mossel, and S. Roch , The Kesten-Stigum reconstruction bound is tight for roughly symmetric binary channels , in Foundations of Computer Science, 2006. FOCS’06. 47th Annual IEEE Symposium on, IEEE, 2006, pp. 518– 530

work page 2006

[6] [6]

Brito, I

G. Brito, I. Dumitriu, S. Ganguly, C. Hoffman, and L. V. Tran , Recovery and rigidity in a regular stochastic block model , in Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial a nd Applied Mathematics, 2016, pp. 1589–1601

work page 2016

[7] [7]

Chayes, L

J. Chayes, L. Chayes, J. P. Sethna, and D. Thouless , A mean ﬁeld spin glass with short- range interactions, Communications in Mathematical Physics, 106 (1986), pp. 4 1–89

work page 1986

[8] [8]

Daskalakis, E

C. Daskalakis, E. Mossel, and S. Roch , Optimal phylogenetic reconstruction, in Proceedings of the thirty-eighth annual ACM symposium on Theory of compu ting, ACM, 2006, pp. 159– 168

work page 2006

[9] [9]

Evans, C

W. Evans, C. Kenyon, Y. Peres, and L. J. Schulman , Broadcasting on trees and the Ising model, Annals of Applied Probability, (2000), pp. 410–433

work page 2000

[10] [10]

Kesten and B

H. Kesten and B. P. Stigum , Additional limit theorems for indecomposable multidimens ional galton-watson processes, The Annals of Mathematical Statistics, 37 (1966), pp. 1463 –1481

work page 1966

[11] [11]

Kesten and B

H. Kesten and B. P. Stigum , Limit theorems for decomposable multi-dimensional galton - watson processes, Journal of Mathematical Analysis and Applications, 17 (19 67), pp. 309– 338

work page

[12] [12]

M. Kimura , A simple method for estimating evolutionary rates of base su bstitutions through comparative studies of nucleotide sequences , Journal of molecular evolution, 16 (1980), pp. 111–120

work page 1980

[13] [13]

W. Liu, S. R. Jammalamadaka, and N. Ning , The tightness of the Kesten-Stigum reconstruc- tion bound of symmetric model with multiple mutations , Journal of Statistical Physics, 170 (2018), pp. 617–641

work page 2018

[14] [14]

Liu and N

W. Liu and N. Ning , Big data information reconstruction on an inﬁnite tree for a 4 × 4-state asymmetric model with community eﬀects , arXiv preprint arXiv:1812.10475, (2018)

work page arXiv 2018

[15] [15]

Liu and N

W. Liu and N. Ning , Large degree asymptotics and the reconstruction threshold of the asym- metric binary channels , Journal of Statistical Physics, (2018), pp. 1–28

work page 2018

[16] [16]

M ´ezard and A

M. M ´ezard and A. Montanari , Reconstruction on trees and spin glass transition , Journal of statistical physics, 124 (2006), pp. 1317–1350

work page 2006

[17] [17]

Mossel , Reconstruction on trees: beating the second eigenvalue , Annals of Applied Proba- bility, (2001), pp

E. Mossel , Reconstruction on trees: beating the second eigenvalue , Annals of Applied Proba- bility, (2001), pp. 285–300

work page 2001

[18] [18]

Mossel , Phase transitions in phylogeny , Transactions of the American Mathematical Soci- ety, 356 (2004), pp

E. Mossel , Phase transitions in phylogeny , Transactions of the American Mathematical Soci- ety, 356 (2004), pp. 2379–2404

work page 2004

[19] [19]

Mossel , Survey: information ﬂow on trees , DIMACS series in discrete mathematics and theoretical computer science, 63 (2004), pp

E. Mossel , Survey: information ﬂow on trees , DIMACS series in discrete mathematics and theoretical computer science, 63 (2004), pp. 155–170

work page 2004

[20] [20]

Deep Learning and Hierarchal Generative Models

E. Mossel , Deep learning and hierarchal generative models , arXiv preprint arXiv:1612.09057, (2016)

work page internal anchor Pith review Pith/arXiv arXiv 2016

[21] [21]

Mossel, J

E. Mossel, J. Neeman, and A. Sly , A proof of the block model threshold conjecture , Combi- natorica, (2013), pp. 1–44

work page 2013

[22] [22]

Mossel, J

E. Mossel, J. Neeman, and A. Sly , Belief propagation, robust reconstruction and optimal recovery of block models , in Conference on Learning Theory, 2014, pp. 356–370

work page 2014

[23] [23]

Non-Reconstructability in the Stochastic Block Model

J. Neeman and P. Netrapalli , Non-reconstructability in the stochastic block model , arXiv preprint arXiv:1404.6304, (2014)

work page internal anchor Pith review Pith/arXiv arXiv 2014

[24] [24]

Ricci-Tersenghi, G

F. Ricci-Tersenghi, G. Semerjian, and L. Zdeborov ´a, Typology of phase transitions in bayesian inference problems , Physical Review E, 99 (2019), p. 042109

work page 2019

[25] [25]

Sly , Reconstruction for the Potts model , The Annals of Probability, 39 (2011), pp

A. Sly , Reconstruction for the Potts model , The Annals of Probability, 39 (2011), pp. 1365– 1406

work page 2011