Pith. sign in

REVIEW 4 major objections 6 minor 51 references

Bayesian Inference with Structured Signal: Static Replica Symmetry Breaking on the Nishimori Line in the Planted Spin Glass

T0 review · 4 major / 6 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A correlated, non-separable prior can push a Bayes-optimal posterior into a static replica-symmetry-breaking phase on the Nishimori line, with threshold β_rsb(κ) separating the glassy low-β phase from an easy replica-symmetric phase.

desk verdict A solid cavity-method paper with a provocative claim—static RSB on the Nishimori line for a correlated prior—that is honestly caveated but not fully nailed down because the key phase is only analyzed at x=1. read the letter →

arxiv 2608.02373 v1 pith:IMZRMXUG submitted 2026-08-03 cond-mat.dis-nn cond-mat.stat-mechcs.ITmath.IT

Andrea Vincenzo Dell'Abate , Louise Budzynski This is my paper · ORCID
classification cond-mat.dis-nncond-mat.stat-mechcs.ITmath.IT MSC 82B4482B2662F15
keywords plantedspinglasscensoredblockmodelNishimorilinereplicasymmetrybreakingstructuredpriorcavitymethodbeliefpropagationrandomregulargraphs
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper asks whether correlations in the signal's prior can break the usual replica-symmetric behaviour of Bayes-optimal inference. Using a minimal planted spin glass on random regular graphs whose planted configuration is sampled from an Ising model with coupling κ, it maps three regimes. In the paramagnetic regime, correlations lower the reconstruction threshold β_c(κ). In the ferromagnetic regime, the prior alone gives partial recovery and observations only help above β_p=κ. In the static RSB regime of the prior, the paper finds a posterior transition at β_rsb(κ) from an easy replica-symmetric phase at large β to a static RSB phase at small β, on the Nishimori line — a glassy phase in Bayes-optimal inference driven by the non-separable correlated prior.

What carries the argument

The central object is the planted spin glass (the Censored Block Model) on random d-regular graphs, with signal drawn from the Ising prior P_κ(s) ∝ ∏_{(ij)∈E} e^{κ s_i s_j} and noisy edge observations J_ij with likelihood e^{β J_ij s_i s_j}/(2 cosh β). The analysis runs through distributional cavity equations: replica-symmetric equations for the paramagnetic and ferromagnetic prior regimes, and, for the glassy prior regime, the simplified 1RSB equations at Parisi parameter x=1, where condensation is signalled by negative complexity Σ and q_0=0<q_1. The threshold β_rsb(κ) is located by the free-energy crossing between this static-RSB branch and the RS branch.

What would settle it

Solve the full 1RSB cavity equations at the correct Parisi parameter x<1 inside the β<β_rsb region: if the dominant solution is not a condensed phase with zero complexity and q_0<q_1, or if the free-energy crossing shifts or disappears, the reported transition is an artifact of the x=1 simplification. Alternatively, on finite instances under Nishimori conditions, measure the posterior overlap distribution P(q) for β<β_rsb: static RSB predicts a non-trivial, multi-peaked P(q), whereas replica symmetry predicts a concentrated one.

Watch

Extended reading notes

Core claim

When the signal is sampled from an Ising prior that is itself in a static RSB phase (κ<κ_rsb), the posterior on the Nishimori line is not always replica symmetric: for β below a threshold β_rsb(κ) the thermodynamically dominant solution is a static RSB (condensed) phase, detected through a negative complexity and q_0=0<q_1 at x=1, while for β above the threshold the RS solution dominates and inference is easy. This provides an example where a non-separable, correlated prior leads to static RSB in a Bayes-optimal inference problem, overturning the standard expectation that Bayes-optimality implies replica symmetry.

Load-bearing premise

The paper's headline transition is detected with a simplified version of the replica calculation that the authors themselves say does not give correct thermodynamic observables inside the glassy phase; if that simplified negative-complexity criterion does not mark the true onset of the static RSB phase, the central claim shifts or disappears.

Editorial extensions

If this is right

  • In the paramagnetic prior regime, the reconstruction threshold β_c(κ) is lower than the unstructured β_c(0), reaching β_c=0 at κ=κ_rsb, so correlations in the signal make inference information-theoretically easier.
  • In the ferromagnetic prior regime, the prior-based trivial estimator already achieves non-zero overlap; observations improve over it only for β>β_p(κ)=κ.
  • When the prior is static RSB, the posterior is replica symmetric and easy for β>β_rsb(κ), but becomes a static RSB (condensed) phase for β<β_rsb(κ) even under Nishimori conditions.
  • The glassy posterior phase is associated with algorithmic hardness: Belief Propagation convergence deteriorates at small β, and the posterior-based estimator can do worse than the prior-based one.
  • The Nishimori identities still hold on the thermodynamically dominant branch, so the static RSB phase is not a violation of Bayes optimality but a breakdown of the usual replica-symmetric picture for correlated priors.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the x=1 negative-complexity criterion is confirmed by a full x<1 solution, the mechanism suggests that any non-separable prior with a glassy component can seed a glassy posterior even when the channel is Bayes-optimal; one could look for the same phenomenon in stochastic-block-model variants with correlated priors.
  • The finite-size finding that a mismatched unstructured prior converges but reconstructs worse suggests a practical consequence: using an overly simple prior can make algorithms look well-behaved while silently degrading recovery; a testable extension is to compare matched versus mismatched priors across the β<β_rsb region.
  • One sharp quantitative consequence worth testing is that β_c(κ) vanishes as κ approaches κ_rsb from the paramagnetic side, meaning arbitrarily weak observations suffice near the prior condensation transition; this could be probed with spectral or message-passing algorithms on large instances.
  • The unusual scenario where the dominant x=1 solution has zero overlap with the signal while subdominant informative states exist suggests that recovery inside the glassy phase may hinge on metastable states; this is an editorial inference, not a claim the paper establishes.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 6 minor

Summary. This paper studies the planted spin glass (censored block model) on random d-regular graphs when the planted signal is drawn from an Ising prior with coupling κ, rather than an i.i.d. prior. The posterior is an Ising model with edge couplings κ + β J_ij; the Bayes-optimal setting places the model on the Nishimori line. Using distributional cavity equations, the authors derive a phase diagram in (κ, β). For a paramagnetic prior they obtain a stability threshold β_c(κ) (Eq. 11) that decreases with |κ|; for a ferromagnetic prior they show β_p = κ separates the regime where the posterior improves over the prior estimator; for an s-RSB prior (κ < κ_rsb) they report a transition at β_rsb(κ) from a replica-symmetric easy phase to a static RSB phase, detected from negative complexity in the x=1 1RSB equations (Eq. C27). Finite-size BP simulations support the RS-regime predictions and suggest degraded performance in the low-β s-RSB regime.

Significance. If the posterior s-RSB transition were established, it would be a notable counterexample to the usual expectation that Bayes-optimal inference on the Nishimori line is replica symmetric, and it would provide a minimal analytically tractable model of correlated priors. The paper's RS results for paramagnetic and ferromagnetic priors are clean: Eq. (11) is a concrete closed-form stability condition, and the β_p = κ argument is elegant and non-circular. The manuscript also provides code and notebooks. However, the headline claim is currently supported only by the x=1 simplification, which the authors themselves state is not the correct thermodynamic description; the numerical evidence is also weakened by sampling caveats. The significance is high if the x<1 program can be completed or the claims are appropriately downgraded.

major comments (4)
  1. [IIIB3 / Eq. (C27)] The posterior s-RSB transition is the central claim, but it is derived entirely from the x=1 1RSB equations. The manuscript explicitly states in Secs. IIIA and IIIB3 that a correct static-RSB description requires x<1 and that x=1 gives incorrect thermodynamic observables inside the condensed phase. Negative complexity at x=1 may indicate condensation, but it does not by itself establish that the physical x*<1 branch exists, that its free energy crosses the RS branch at the reported β_rsb(κ), or that the transition is a true thermodynamic transition. Without solving the x<1 equations, or at least giving an independent controlled argument for the onset, the headline claim is not established.
  2. [Eq. (C34) / Fig. 4] The free-energy comparison used to locate β_rsb compares the RS free entropy with the x=1 replicated potential of a branch with negative complexity. When Σ<0 the x=1 branch is not a physical state of the Gibbs measure; the quantity Φ_RSB(x=1) includes a negative complexity contribution and is not the physical free entropy of a condensed phase. A crossing between these two objects is therefore not automatically a thermodynamic transition. The authors should compare the RS free entropy with the physical free entropy of the x*<1 solution.
  3. [Fig. 5 / Appendix A2] The finite-size BP results in the s-RSB prior regime use BP-guided decimation to sample planted configurations from the prior. The authors concede that this method gives accurate marginals only in the RS phase and is not guaranteed accurate in the RSB regime. The energy consistency check is necessary but weak. Thus the numerical simulations are suggestive but cannot independently confirm the existence or location of the posterior s-RSB phase.
  4. [Appendix C1c] The prior Parisi parameter x0 is estimated by locating the zero of Σ0(x0), where the complexity values are of order 10^-6 near κ_rsb. The authors note this is numerically unreliable close to κ_rsb and consequently omit cavity predictions from Fig. 5. This means the quantitative value of β_rsb(κ) is uncontrolled precisely in the regime used to illustrate the transition.
minor comments (6)
  1. [Abstract / Sec. I vs. IIIB3] The abstract and introduction state the detection of a static RSB transition as a definite result, while Sec. IIIB3 says the nature of the phase 'remains unresolved' and the x=1 solution 'does not give correct thermodynamic observables.' Please align the claims with the caveats throughout.
  2. [Eq. (11)] The sum over J is not defined; please specify that J ∈ {±1} and define the bracket notation ⟨·⟩ if used.
  3. [Fig. 1 caption] The caption says 'κ ∈ [κ_rsb, κ_c]' with κ_rsb negative; the sign convention is confusing. Please state explicitly that κ_rsb = -atanh(1/√(d-1)).
  4. [Appendix C2b] The opening sentence 'Obtaining the 1-RSB cavity equation for the prior probability is analogous...' appears to be a copy-paste from C2a and should read 'posterior probability'.
  5. [Eq. (C25)] The definition of ̅Q_σ and the removal of the reweighting factor are quite terse; a few explanatory sentences would improve readability.
  6. [Code availability] The GitHub repository [34] is cited but the paper does not state which figures/notebooks correspond to which numerics; please add reproducibility notes.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the main thresholds are derived from cavity equations; the x=1 static-RSB criterion is a stated approximation, not a circular input.

full rationale

The paper's derivation chain is not self-referential. The posterior (Eq. 5) is constructed from the structured prior (Eq. 1) and the channel (Eq. 4). The paramagnetic-regime threshold β_c(κ) follows from a linear stability analysis of the paramagnetic fixed point (Appendix B.3, Eq. 11), and the ferromagnetic-regime threshold β_p(κ)=κ follows from the sign of the effective couplings in Eq. (5) — both are derived quantities, not fitted inputs renamed as predictions. In the RSB region, the posterior s-RSB branch is a genuine fixed-point solution of the simplified x=1 1RSB cavity equations (Appendix C, Eq. C27), and the negative-complexity criterion is a standard condensation diagnostic. The paper explicitly disclaims that x=1 gives the correct thermodynamic observables inside the condensed phase: 'once a static RSB phase is detected, using x=1 no longer gives the correct thermodynamic observables' (Section III.B.3). This is an approximation/correctness caveat about the quantitative location of β_rsb, not an equivalence between input and output. The prior phase boundary κ_rsb is imported from independent external results [21,22], and the self-citations [5,17] are contextual background rather than load-bearing evidence. No fitted parameter is passed off as a prediction and no uniqueness claim is imported from the authors' prior work. Therefore the central derivation is self-contained; the x=1 caveat lowers confidence in the exact value of β_rsb but does not make the argument circular.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

No new particles, forces, conserved quantities, or other invented entities. The model parameters κ and β are problem inputs, not fitted constants. Numerical hyperparameters and x0 are algorithmic or derived quantities. The main load-bearing input is the standard cavity/1RSB framework plus the x=1 simplification, which the paper itself flags as incomplete.

free parameters (2)
  • x0 (prior Parisi parameter) = 0 < x0 < 1, value where prior complexity Σ0(x0)=0; not tabulated
    Selected by solving the prior 1RSB equation and fitting Σ0(x0) to zero. It is not fitted to posterior data, but it enters the posterior s-RSB calculation and is numerically delicate near κ_rsb (complexity ~1e-6).
  • ε (initial-condition bias) = 1e-3 or 0
    Ad-hoc choice for informed/uninformed BP and population dynamics initializations; standard symmetry-breaking seed, not fitted.
assumptions (5)
  • domain assumption Random d-regular graphs are locally tree-like and BP fixed points accurately approximate marginals so the distributional cavity equations close.
    Used throughout Appendix B to derive Eqs. (B21)/(B22) and all phase boundaries; standard but not proven for this correlated-prior model.
  • ad hoc to paper In the 1RSB formalism, negative complexity at Parisi parameter x=1 detects the onset of a static (condensed) RSB phase, and the free-energy crossing between RS and x=1 branches locates β_rsb.
    Specific to the simplified treatment in Appendix C2c; the paper notes x<1 is required for correct observables inside the phase.
  • domain assumption The prior phase boundaries κ_c = atanh(1/(d-1)) and κ_rsb = -atanh(1/sqrt(d-1)) are taken from the cited literature [21,22].
    Inputs to the phase diagram; not re-derived in this paper.
  • domain assumption P(R)=δ[R-R*] holds for the prior 1RSB messages because the graph is random regular and the prior coupling is homogeneous.
    Used to reduce the posterior 1RSB equations to Eqs. (C18)/(C27).
  • ad hoc to paper BP-guided decimation produces representative planted configurations from the s-RSB prior.
    Appendix A2 and Section III.B3 admit this is uncontrolled in the RSB regime; used to generate finite-size instances for Figure 5.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Bayesian Inference with Structured Signal: Static Replica Symmetry Breaking on the Nishimori Line in the Planted Spin Glass." pith.science (2026). https://pith.science/paper/IMZRMXUG

@misc{pith2026260802373,
  author       = {Pith},
  title        = {Pith review of: Bayesian Inference with Structured Signal: Static Replica Symmetry Breaking on the Nishimori Line in the Planted Spin Glass},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IMZRMXUG}},
  note         = {Machine review of arXiv:2608.02373}
}
abstract

A common assumption in theoretical models of Bayesian inference is that the signal has i.i.d. components. To study the effect of correlations in the signal prior, we consider a minimal model: the planted spin glass on random regular graphs, where the signal is sampled from an Ising model with coupling $\kappa$. Depending on the phase of the prior, we find that adding structure in the signal can either help or hinder inference. In the paramagnetic regime, correlations in the signal lower the reconstruction threshold, so that weaker signal strength is sufficient for recovery. In the ferromagnetic regime, the prior alone already enables partial recovery, and we identify the threshold above which the observations provide additional information. When the prior itself is in a replica symmetry breaking (RSB) phase, we detect a static RSB transition in the posterior under Nishimori conditions. This provides an example where a non-separable, correlated prior leads to static RSB in a Bayes-optimal inference problem. We discuss the consequences of this glassy phase for algorithmic performance, in particular for Belief Propagation.

Figures

Figures reproduced from arXiv: 2608.02373 by the authors.

Figure 1
Figure 1. FIG. 1. Phase diagram of the inference problem obtained [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. FIG. 2. Transition for [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. FIG. 3. Transition for [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: FIG. 4. Transition for [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]
Figure 5
Figure 5. Figure 5: FIG. 5. Performance of BP at [PITH_FULL_IMAGE:figures/full_fig_p009_5.png]
Figure 6
Figure 6. Figure 6: FIG. 6. Complexity Σ of the static RSB solution of (C27) [PITH_FULL_IMAGE:figures/full_fig_p010_6.png]
Figure 7
Figure 7. Figure 7: FIG. 7. Top: Plot of the complexity of the prior Σ [PITH_FULL_IMAGE:figures/full_fig_p022_7.png]
Figure 8
Figure 8. Figure 8: FIG. 8. Results with paramagnetic prior. Left: [PITH_FULL_IMAGE:figures/full_fig_p029_8.png]
Figure 9
Figure 9. Figure 9: FIG. 9. Results with ferromagnetic prior. Left: [PITH_FULL_IMAGE:figures/full_fig_p029_9.png]
Figure 10
Figure 10. Figure 10: FIG. 10. Results with sRSB prior [PITH_FULL_IMAGE:figures/full_fig_p030_10.png]
Figure 11
Figure 11. Figure 11: FIG. 11. Results with sRSB prior [PITH_FULL_IMAGE:figures/full_fig_p030_11.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

51 extracted references · 1 linked inside Pith

  1. [1]

    The overlap between the MMO estimator and the planted configuration provides a quantitative estima- tion of the accuracy of the estimator

    Bayesian estimators As a measure of inference performance, we study in Section III the overlap between the planted configura- tions and an estimator ˆσ: O(s,ˆσ) = 1 N X i=1 si ˆσi .(6) The best Bayesian estimate, the Mean Overlap, is obtained by averaging over the posterior distribution MO(ˆσ) = X σ Pβ,κ(σ|J) 1 N NX i=1 σi ˆσi .(7) TheMaximum Mean Overlap...

  2. [2]

    Relation with previous works Bayesian inference problems with non-trivial priors have previously been studied in several contexts. In spiked matrix models, signal sparsity has been incor- porated through separable sparse priors, leading to efficient algorithms that achieve Bayes-optimal per- formance in some regimes [25], while statistical-to- computation...

  3. [3]

    not better than prior

    Bayesian optimality on the Nishimori line In the Bayes-optimal setting, the parameters used for inference match those of the generative model. In our case, this means that the prior parameterκand the channel parameterβare known and used in the pos- terior distribution (5). This setting corresponds to the Nishimori line, where the Nishimori identities hold...

  4. [4]

    not better than prior

    Paramagnetic prior Forκ∈[κ rsb, κc] the prior is in the paramagnetic phase, the planted configuration has vanishing magne- tization and the trivial estimator (9) has zero overlap with the signal. The phase transition undergone by the posterior from the impossible phase to the easy phase is shown in Figure 2 forκ= 0.4. The top panel dis- plays the overlap ...

  5. [5]

    not better than the prior

    Ferromagnetic prior Whenκ > κc, the prior is in the ferromagnetic phase and the trivial estimator (9) achieves non-zero overlap with the signal. The phase transition is shown in Fig- ure 3 forκ= 0.6. It separates a “not better than the prior” phase, where the MMO estimator (8) achieves the same overlap as the trivial estimator, to an easy phase, where the...

  6. [6]

    We identify a critical thresholdβ rsb(κ): forβ < β rsb, 8 FIG

    Prior in a static RSB phase Whenκ < κrsb, the prior lies in a static RSB phase. We identify a critical thresholdβ rsb(κ): forβ < β rsb, 8 FIG. 4. Transition forκ=−1.2 from a static RSB phase to a easy RS phase, occurring atβ rsb = 0.398 (vertical dashed line). Top left: Complexity Σ of the two solutions of (C27). Top right: inter-state and intra-state ove...

    2025

  7. [7]

    D. L. Donoho, A. Maleki, and A. Montanari. Message- passing algorithms for compressed sensing.Proceed- ings of the National Academy of Sciences,106(45), 18914–18919 (2009)

    2009

  8. [8]

    H. Cui, F. Krzakala, and L. Zdeborova. Bayes-optimal Learning of Deep Random Networks of Extensive- width. InProceedings of the 40th International Con- ference on Machine Learning, volume 202 ofProceed- ings of Machine Learning Research, pages 6468–6521. PMLR, 23–29 Jul 2023

    2023

Show all 51 references
  1. [9]

    Goldt, F

    S. Goldt, F. Krzakala, L. Zdeborov´ a, and N. Brunel. Bayesian reconstruction of memories stored in neural networks from their connectivity.PLOS Computational Biology,19(1), e1010813 (2023)

    2023

  2. [10]

    Altarelli, A

    F. Altarelli, A. Braunstein, L. Dall’Asta, A. Lage- Castellanos, and R. Zecchina. Bayesian Inference of Epidemics on Networks via Belief Propagation.Phys. Rev. Lett.,112, 118701 (2014). 12

    2014

  3. [11]

    Braunstein, L

    A. Braunstein, L. Budzynski, and M. Mariani. Sta- tistical mechanics of inference in epidemic spreading. Physical Review E,108(6) (2023)

    2023

  4. [12]

    Parisi.Spin Glass Theory, pages 317–329

    G. Parisi.Spin Glass Theory, pages 317–329. Springer US, Boston, MA, 1987

    1987

  5. [13]

    Nishimori.Statistical Physics of Spin Glasses and Information Processing: an Introduction

    H. Nishimori.Statistical Physics of Spin Glasses and Information Processing: an Introduction. Oxford Uni- versity Press, Oxford; New York, 2001

    2001

  6. [14]

    Decelle, F

    A. Decelle, F. Krzakala, C. Moore, and L. Zdeborov´ a. Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Physical Review E,84(6) (2011)

    2011

  7. [15]

    Lesieur, F

    T. Lesieur, F. Krzakala, and L. Zdeborova. Phase tran- sitions in sparse PCA. In2015 IEEE International Sym- posium on Information Theory (ISIT), page 1635–1639. IEEE, June 2015

    2015

  8. [16]

    Coja-Oghlan, F

    A. Coja-Oghlan, F. Krzakala, W. Perkins, and L. Zde- borov´ a. Information-theoretic thresholds from the cav- ity method.Advances in Mathematics,333, 694–795 (2018)

    2018

  9. [17]

    Lelarge and L

    M. Lelarge and L. Miolane. Fundamental limits of sym- metric low-rank matrix estimation. InProceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 1297–

    2017

  10. [18]

    Zdeborov´ a and F

    L. Zdeborov´ a and F. Krzakala. Statistical physics of inference: thresholds and algorithms.Advances in Physics,65(5), 453–552 (2016)

    2016

  11. [19]

    Aubin, B

    B. Aubin, B. Loureiro, A. Maillard, F. Krzakala, and L. Zdeborov´ a. The spiked matrix model with generative priors. InAdvances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019

    2019

  12. [20]

    Goldt, M

    S. Goldt, M. M´ ezard, F. Krzakala, and L. Zdeborov´ a. Modeling the Influence of Data Structure on Learning in Neural Networks: The Hidden Manifold Model.Physi- cal Review X,10(4) (2020)

    2020

  13. [21]

    Loureiro, C

    B. Loureiro, C. Gerbelot, H. Cui, S. Goldt, F. Krza- kala, M. M´ ezard, and L. Zdeborov´ a. Learning curves of generic features maps for realistic datasets with a teacher-student model*.Journal of Statistical Mechan- ics: Theory and Experiment,2022(11), 114001 (2022)

    2022

  14. [22]

    Duranthon and L

    O. Duranthon and L. Zdeborov´ a. Neural-prior stochas- tic block model.Machine Learning: Science and Tech- nology,4(3), 035017 (2023)

    2023

  15. [23]

    D. Ghio, F. Boncoraglio, and L. Zdeborov´ a. Inference in spreading processes with neural-network priors.Phys. Rev. E,113, 015301 (2026)

    2026

  16. [24]

    Braunstein, L

    A. Braunstein, L. Budzynski, M. Mariani, and F. Ricci- Tersenghi. Evidence of replica symmetry breaking un- der the Nishimori conditions in epidemic inference on graphs.Physical Review E,111(6) (2025)

    2025

  17. [25]

    Deshpande and A

    Y. Deshpande and A. Montanari. Information- theoretically optimal sparse PCA. In2014 IEEE In- ternational Symposium on Information Theory, pages 2197–2201, 2014

    2014

  18. [26]

    E. Abbe, A. S. Bandeira, A. Bracher, and A. Singer. Decoding Binary Node Labels from Censored Edge Measurements: Phase Transition and Efficient Recov- ery .IEEE Transactions on Network Science and En- gineering,1(01), 10–22 (2014)

    2014

  19. [27]

    Saade, F

    A. Saade, F. Krzakala, M. Lelarge, and L. Zdeborov´ a. Spectral detection in the censored block model. In ISIT 2015 - IEEE International Symposium on Infor- mation Theory, volume 2015 of2015 IEEE Interna- tional Symposium on Information Theory (ISIT), pages 1184–1188, Hong-Kon...

    2015

  20. [28]

    Zdeborov´ a and S

    L. Zdeborov´ a and S. Boettcher. A conjecture on the maximum cut and bisection width in random regular graphs.Journal of Statistical Mechanics: Theory and Experiment,2010, P02020 (2010)

    2010

  21. [29]

    Coja-Oghlan, P

    A. Coja-Oghlan, P. Loick, B. F. Mezei, and G. B. Sorkin. The Ising Antiferromagnet and Max Cut on Random Regular Graphs.SIAM Journal on Discrete Mathematics,36(2), 1306–1342 (2022)

    2022

  22. [30]

    V. H. Can. Annealed limit theorems for the Ising model on random regular graphs.The Annals of Applied Prob- ability,29(3), pp. 1398–1445 (2019)

    2019

  23. [31]

    P. W. Holland, K. B. Laskey, and S. Leinhardt. Stochas- tic blockmodels: First steps.Social Networks,5(2), 109–137 (1983)

    1983

  24. [32]

    Nishimori, M

    H. Nishimori, M. Ohzeki, and M. Okuyama. Temper- ature chaos as a logical consequence of the reentrant transition in spin glasses.Phys. Rev. E,112, 044140 (2025)

    2025

  25. [33]

    Jenatton, G

    R. Jenatton, G. Obozinski, and F. Bach. Structured Sparse Principal Component Analysis. InProceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9 ofProceedings of Machine Learning Research, pages 366–373, Chia La- guna Resort,...

    2010

  26. [34]

    Semerjian

    G. Semerjian. Some observations on the ambivalent role of symmetries in Bayesian inference problems.Comptes Rendus. Physique,26(G1), 199–216 (2025)

    2025

  27. [35]

    M. Andrea. Estimating random variables from ran- dom sparse observations.European Transactions on Telecommunications,19(4), 385–403 (2008)

    2008

  28. [36]

    Barbier and D

    J. Barbier and D. Panchenko. Strong Replica Symme- try in High-Dimensional Optimal Bayesian Inference. Communications in Mathematical Physics,393, 1199– 1239 (2022)

    2022

  29. [37]

    Nishimori

    H. Nishimori. Anomalous distribution of magnetization in an Ising spin glass with correlated disorder.Phys. Rev. E,110, 064108 (2024)

    2024

  30. [38]

    Nishimori

    H. Nishimori. Instability of the ferromagnetic phase un- der random fields in an Ising spin glass with correlated disorder.Phys. Rev. E,111, 044109 (2025)

    2025

  31. [40]

    Ricci-Tersenghi, G

    F. Ricci-Tersenghi, G. Semerjian, and L. Zdeborov´ a. Typology of phase transitions in Bayesian inference problems.Physical Review E,99(4) (2019). [34]https://github.com/andreadellabate/planted_ spin_glass_Ising_prior

    2019

  32. [41]

    Montanari, F

    A. Montanari, F. Ricci-Tersenghi, and G. Semerjian. Solving Constraint Satisfaction Problems through Be- lief Propagation-guided decimation.ArXiv,preprint arXiv:0709.1667(2007)

    2007 arXiv

  33. [42]

    Semerjian

    G. Semerjian. On the Freezing of Variables in Random Constraint Satisfaction Problems.Journal of Statistical Physics,130, 251–293 (2008)

    2008

  34. [43]

    M´ ezard and A

    M. M´ ezard and A. Montanari.Information, Physics, and Computation. Oxford University Press, 01 2009. 13 Appendix A: Belief Propagation

    2009

  35. [44]

    Belief-Propagation equations For each edge (i, j)∈Ewe introduce the BP mes- sagesν i→j, νj→i as the marginal probability distribu- tions ofσ i andσ j in the amputated graphG= (V, E\ {(i, j)}). The BP messages obey the following set of equations defined on each directed edgei→j...

  36. [45]

    This could be done using Monte Carlo sampling or Belief Propagation algorithms

    Sampling the planted configuration In the finite-size experiments, the planted configura- tions is sampled from the prior distribution (1). This could be done using Monte Carlo sampling or Belief Propagation algorithms. In practice, we use a BP- guided decimation procedure [35...

  37. [46]

    Letm (t) i0→j0 be the message sent by the BP algorithm at iterationtalong the edge (i 0, j0)

    Cavity equations for the prior probability In this section we start by illustrating how to obtain the distributional cavity equation for the prior proba- bility (1) (for which the standard derivation applies) by retracing the steps shown in [37]. Letm (t) i0→j0 be the message ...

  38. [47]

    Cavity equations for the posterior probability a. Sampling the disordered variables Applying the replica-symmetric cavity method di- rectly to our posterior distribution (5) is not as straight- forward since the BP equation (A1) depends on the couplings variablesJ . In particu...

  39. [48]

    Stability analysis In the regionκ∈[κ rsb, κc] the cavity equation (B22) admits the trivial paramagnetic fixed point P(ν|s) =δ[ν−¯ν] with ¯ν(σ) = 1 2 .(B36) This fixed point is the one found by the BP algorithm when the all the messages in the initial condition are set to 1/2. ...

  40. [49]

    Cavity equations Obtaining the 1-RSB cavity equation for the prior probability is analogous to what done in Appendix B 1

    Cavity equations for the prior probability a. Cavity equations Obtaining the 1-RSB cavity equation for the prior probability is analogous to what done in Appendix B 1. The messageR (t) i0→j0 passing through the directed edge i0 →j 0 at iterationtwill depend on the initial mess...

  41. [50]

    Sampling the disordered variables Once again, the couplingsJ are not independent

    Cavity equations for the posterior probability a. Sampling the disordered variables Once again, the couplingsJ are not independent. To account for this we must condition on the planted configuration, which must be sampled by in turn in- troducing the planted messages. Differen...

  42. [51]

    One can neverthe- less obtain tractable equations by settingx 0 = 1 and applying simplifications analogous to those used for the posterior in Appendix C 2 c

    Simplifications for Erd˝ os-R´ enyi random graphs When the prior is not defined on a random regular graph, for instance on an Erd˝ os-R´ enyi graph, or when its couplings are not homogeneous, the simplification P(R) =δ[R−R ∗] no longer applies. One can neverthe- less obtain tr...

  43. [1301]

    PMLR, 07–10 Jul 2017

    2017

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.