Pith. sign in

REVIEW 3 major objections 3 minor 39 references

Bayesian causal discovery: Posterior concentration and optimal detection

T0 review · 3 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash

Pith's one-line read Posterior probability of the true causal DAG converges to 1 exponentially fast when the DAG is maximal, and at best polynomially fast otherwise.

desk verdict A genuine and interesting dichotomy, but Theorem 3's constant-1 lower bound is wrong due to a determinant sign error; the correct rate is c/√n with a prior-dependent c. read the letter →

arxiv 2507.16529 v1 pith:ZQX5IF3X submitted 2025-07-22 math.ST stat.TH

classification math.STstat.TH MSC 62F1562C1062F12
keywords BayesiancausaldiscoveryposteriorconcentrationlinearstructuralequationmodelGaussianDAGmaximaledgedetectionNeyman-Pearsonhypothesistestinglawoftheiteratedlogarithm
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

Bayesian causal discovery with linear Gaussian structural equations and standard spike-and-slab priors has two very different sample-size regimes. The paper proves that if the true directed acyclic graph is maximal, meaning that adding any single edge would create a cycle, then the posterior probability of the true graph approaches 1 exponentially fast in the number of observations, almost surely. If the true graph is not maximal, the same posterior probability cannot approach 1 faster than $1/\sqrt{n}$, almost surely, no matter how many observations are collected. The bottleneck is the possibility of one spurious extra edge carrying an arbitrarily small but nonzero coefficient, so the hard part of causal discovery is avoiding overfitting rather than finding the existing structure. The paper also proves that the Bayesian posterior yields an optimal edge-detection rule in the Neyman-Pearson sense.

What carries the argument

The engine of the proof is the posterior log-odds ratio $\log[\pi(S|X_n)/\pi(S^*|X_n)]$ between a candidate DAG $S$ and the true DAG $S^*$. Lemma 4 shows that whenever $S^*$ is not a subgraph of $S$, this log-odds equals $-nD(P_{A^*}\|P_{m(S,\mu_\infty(S))}) + O(\sqrt{n\log\log n})$ almost surely, so every such competitor is killed at an exponential rate. Lemma 5 shows that when $S^*$ is non-maximal, there is a one-edge extension $S^+$ of $S^*$ whose log-odds is only $-\frac12\log n + \delta_n$ with $\delta_n$ eventually nonnegative, which produces the $1/\sqrt{n}$ floor. The asymptotic limits $\mu_\infty(S)$ come from least-squares projections, the fluctuation bounds come from the law of the iterated logarithm, and the one-edge analysis uses the Sherman-Morrison inversion formula.

What would settle it

Take a known non-maximal three-node DAG, such as $X_3 = aX_1 + \epsilon_3$ with $a\neq0$ and no other edges, generate $n$ samples, and compute the exact posterior over all 25 DAGs for $n = 10^4, 10^5, 10^6$. Plot $\log(1-\pi(S^*|X_n))$ against $\log n$; Theorem 3 predicts a slope approaching $-1/2$, while an exponential decay or a slope much steeper than $-1/2$ would contradict it. Repeating the same comparison with a maximal three-node DAG should show the linear-in-$n$ decay of Theorem 2 after subtracting the $O(\sqrt{n\log\log n})$ fluctuation term.

Watch

Extended reading notes

Core claim

The central result is a pair of almost-sure asymptotic statements for the posterior on DAG space under the model $X = AX + \epsilon$, with Gaussian noise, a uniform prior over DAGs, and independent Gaussian priors on nonzero edge weights. Under causal minimality of the true pair $(S^*,w^*)$, Theorem 2 gives $\pi(S^*|X_n) = 1 - \exp\{-nD(A^*) + O(\sqrt{n\log\log n})\}$ when $S^*$ is maximal, where $D(A^*) > 0$ is the minimum Kullback-Leibler divergence between the true distribution and the distribution obtained from any other DAG with its limiting least-squares weights. Theorem 3 gives $1 - \pi(S^*|X_n) \geq (1+o(1))/\sqrt{n}$ when $S^*$ is non-maximal, so consistency holds but at a strictly slower rate. In the binary version of the model with all nonzero weights fixed to 1, the error is $1 - \exp\{-n/2 + O(\sqrt{n\log\log n})\}$ for every true DAG. The paper further shows that the optimal Neyman-Pearson edge detector is exactly the posterior rule that declares an edge absent when $\pi(\chi_{ij}(S)=0|X_n)$ exceeds a threshold.

Load-bearing premise

The load-bearing assumption is that the true DAG and its edge weights are causally minimal, meaning no subgraph of the true DAG generates the same distribution; if this fails, the posterior need not concentrate on the true graph, and the exponential-versus-$1/\sqrt{n}$ dichotomy can break down.

Editorial extensions

If this is right

  • For a maximal true DAG, sample size only needs to grow logarithmically in the desired posterior error, because the error is $\exp\{-nD(A^*)+O(\sqrt{n\log\log n})\}$.
  • For a non-maximal true DAG, the posterior assigns probability at least roughly $1/\sqrt{n}$ to a one-edge-larger DAG for every $n$, so exact structure recovery is qualitatively harder.
  • The slow regime is caused by the prior's ability to place arbitrarily small nonzero weights on a spurious edge; fixing all nonzero weights to 1 removes the problem and restores exponential convergence with exponent $1/2$.
  • The optimal edge-detection rule from hypothesis testing can be evaluated by thresholding the posterior probability of each edge's absence, so MCMC approximations to the posterior are directly useful for constrained error detection.
  • Posterior consistency holds for both maximal and non-maximal true DAGs, so the issue is only the rate at which uncertainty disappears, not whether it disappears.

Reading between the lines

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

  • The $1/\sqrt{n}$ floor is what one expects when testing a zero edge against a local alternative with coefficient of order $n^{-1/2}$; the authors do not state this connection explicitly, but it suggests the same rate should appear whenever an edge weight is allowed to shrink with $n$.
  • The exponent $D(A^*)$ is a population quantity, so a practical extension would be to estimate it from data and use it as a sequential stopping rule for MCMC-based causal discovery; the paper does not develop this.
  • Because the optimal detector is a posterior threshold, any approximate posterior sampler that converges to $\pi(S|X_n)$ should inherit near-optimal edge-detection performance; this is testable on larger graphs even though the theoretical rates are proved for fixed dimension.
  • In high-dimensional settings with $d$ growing in $n$, the factorial-size factor $|G_d|$ in the lower-bound argument may change the dichotomy, so the paper's fixed-$d$ rates should not be extrapolated without further analysis.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 3 minor

Summary. The paper studies posterior concentration on DAG model space for linear structural equation models with Gaussian noise. With a uniform prior on DAGs and independent Gaussian priors on edge weights, it claims a sharp dichotomy: if the true DAG is maximal, the posterior probability of the true model tends to 1 exponentially fast with exponent n D(A*), while if the true DAG is non-maximal, the posterior probability converges no faster than 1/sqrt(n), specifically 1 - pi(S*|X^n) >= (1+o(1))/sqrt(n) almost surely. A binary-weight version gives exponential convergence with exponent 1/2 for every true DAG. The paper also reformulates an optimal Neyman-Pearson edge detector in terms of posterior probabilities and reports simulation experiments supporting the rates.

Significance. If correct, the maximal/non-maximal dichotomy would be a valuable qualitative contribution, linking Bayesian causal discovery to the phenomenon that avoiding overfitting is harder than identifying existing structure. The proof strategy via a BIC-type expansion and the law of the iterated logarithm is natural, and the exact small-d simulations are a useful check. The reformulation of the optimal detector in Proposition 3 is clean and potentially useful. However, the sharp constant in Theorem 3 is false as stated, and the error originates in the sign of the determinant contribution in Lemma 5; the qualitative dichotomy may survive with a prior-dependent constant, but the main theorem in its present form needs substantial correction.

major comments (3)
  1. [Section IV, Lemma 5 and Eqs. (35), (44)]
  2. [Theorem 3]
  3. [Lemma 5 proof, remainder term]
minor comments (3)
  1. [Eq. (35)]
  2. [Section VI-A]
  3. [References]

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the posterior-concentration and edge-detection results are derived from the stated prior, likelihood, and standard asymptotic estimates, with self-citations only for side connections.

full rationale

The paper's main results are derived from explicit Bayes-factor computations rather than from fitted parameters or from the conclusions they are said to establish. The posterior odds in Sections III and IV start from the exact expressions for π(S|Xn) in (8), (10), and (15), and the proofs of Theorems 1–3 use only these expressions, standard LIL estimates, and the algebraic estimates in Lemmas 4 and 5. No parameter appearing in the theorems is fitted to the data: the rate exponent D(A*) in Theorem 2 is defined from the true distribution via (17), and the 1/√n lower bound in Theorem 3 follows from the claimed Lemma 5 remainder. Causal minimality is an assumption about the data-generating process, not an output of the posterior, so it does not import the target result. The self-citations are not load-bearing: the analogy to Bayesian Context Trees in [23] is illustrative, and the optimal edge-detector in Section V is imported from the authors' prior work [29] as an established result rather than used to prove the main concentration theorems. Proposition 3 is an algebraic rewriting of the likelihood-ratio threshold in terms of the posterior, and its proof is self-contained. Consequently, the central claims do not reduce to their inputs by construction, and any concern about the sign of the determinant expansion in Lemma 5 is a mathematical correctness issue, not a circularity issue.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No free parameters are fitted to data; the rate constants D(A*) and 1/2 are derived from the true distribution. Model inputs σ^2 and σ_w^2 are stated assumptions, not fitted values. No new particles, forces, or entities are introduced.

assumptions (6)
  • domain assumption The true parameter (S*, w*) is causally minimal.
    Stated in Section II; needed for identifiability, for D(PA*||PA(S)) > 0 in Lemma 4, and for μ∞(S*) = w* in Proposition 2.
  • domain assumption Noise is i.i.d. Gaussian N(0, σ^2 I) with known variance σ^2.
    Section II, equation (1); used for the Gaussian likelihood and KL divergence computations.
  • domain assumption Edge weights have independent Gaussian N(0, σ_w^2) priors given the graph.
    Section II; the Gaussian form yields the tractable posterior expression (8) and the LIL-based remainder estimates.
  • standard math Law of the iterated logarithm holds for the relevant i.i.d. sums.
    Used in the proofs of Theorem 1 and Propositions 1 and 2 to control O(sqrt(n log log n)) remainders; see Section III and Appendix B.
  • domain assumption The dimension d is fixed and the DAG space Gd is finite.
    Theorems 2 and 3 are stated for this setting; the finite model class is used in the union bounds over S not equal to S*.
  • standard math Schwartz's Bayesian consistency theorem applies to this model.
    Invoked in the proof of Theorem 3 to assert π(S*|Xn) converges to 1; conditions are not proved in the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Bayesian causal discovery: Posterior concentration and optimal detection." pith.science (2026). https://pith.science/paper/ZQX5IF3X

@misc{pith2026250716529,
  author       = {Pith},
  title        = {Pith review of: Bayesian causal discovery: Posterior concentration and optimal detection},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZQX5IF3X}},
  note         = {Machine review of arXiv:2507.16529}
}
abstract

We consider the problem of Bayesian causal discovery for the standard model of linear structural equations with equivariant Gaussian noise. A uniform prior is placed on the space of directed acyclic graphs (DAGs) over a fixed set of variables and, given the graph, independent Gaussian priors are placed on the associated linear coefficients of pairwise interactions. We show that the rate at which the posterior on model space concentrates on the true underlying DAG depends critically on its nature: If it is maximal, in the sense that adding any one new edge would violate acyclicity, then its posterior probability converges to 1 exponentially fast (almost surely) in the sample size $n$. Otherwise, it converges at a rate no faster than $1/\sqrt{n}$. This sharp dichotomy is an instance of the important general phenomenon that avoiding overfitting is significantly harder than identifying all of the structure that is present in the model. We also draw a new connection between the posterior distribution on model space and recent results on optimal hypothesis testing in the related problem of edge detection. Our theoretical findings are illustrated empirically through simulation experiments.

Figures

Figures reproduced from arXiv: 2507.16529 by the authors.

Figure 1
Figure 1. Binary structure learning for three-node graphs. Left: The posterior probability [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. General structure learning for a maximal three-node graph. The true matrix is [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. General structure learning for a non-maximal three-node graph. The true matrix [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Performance comparison between the optimal MCMC [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

39 extracted references · 37 canonical work pages

  1. [29]

    Shaska and U

    J. Shaska and U. Mitra. Neyman-Pearson causal inference. In 2024 IEEE International Symposium on Information Theory (ISIT), pages 1269–1274, 2024

  2. [1]

    Annadani, N

    Y . Annadani, N. Pawlowski, J. Jennings, S. Bauer, C. Zhang, and W. Gong. BayesDAG: Gradient-based posterior inference for causal discovery. NeurIPS, 36:1738–1763, 2023

  3. [2]

    Annadani, J

    Y . Annadani, J. Rothfuss, A. Lacoste, N. Scherrer, A. Goyal, Y . Bengio, and S. Bauer. Variational causal networks: Approxi- mate Bayesian inference over causal structures. arXiv e-prints, 2106.07635 [cs.LG], June 2021

  4. [3]

    X. Cao, K. Khare, and M. Ghosh. Posterior graph selection and estimation consistency for high-dimensional Bayesian DAG models. Annals of Statistics , 47(1):319–348, 2019

  5. [4]

    Castillo, J

    I. Castillo, J. Schmidt-Hieber, and A. Van der Vaart. Bayesian linear regression with sparse priors. Annals of Statistics , 42(5):1986–2018, 2015

  6. [5]

    Chang, J.J

    H. Chang, J.J. Cai, and Q. Zhou. Order-based structure learning without score equivalence. Biometrika, 111(2):551–572, 2024

  7. [6]

    W. Chen, M. Drton, and Y .S. Wang. On causal discovery with an equal-variance assumption. Biometrika, 106(4):973–980, 2019

  8. [7]

    Chickering

    D.M. Chickering. Optimal structure identification with greedy search. J. Mach. Learn. Res. , 3:507–554, 2002

Show all 39 references
  1. [8]

    Cundy, A

    C. Cundy, A. Grover, and S. Ermon. BCD Nets: Scalable variational approaches for Bayesian causal discovery. NeurIPS, 34:7095–7110, 2021

  2. [9]

    Eaton and K

    D. Eaton and K. Murphy. Bayesian structure learning using dynamic programming and MCMC. In Proceedings of the Twenty-Third Conference on Uncertainty in Artificial Intelli- gence, pages 101–108, 2007

  3. [10]

    Friedman, M

    N. Friedman, M. Goldszmidt, and A. Wyner. Data analysis with Bayesian networks: A bootstrap approach. Proceedings of Fifteenth Conference on Uncertainty in Artificial Intelligence , pages 196–205, 1999

  4. [11]

    Friedman and D

    N. Friedman and D. Koller. Being Bayesian about net- work structure. A Bayesian approach to structure discovery in Bayesian networks. Machine Learning, 50:95–125, 2003

  5. [12]

    Grzegorczyk and D

    M. Grzegorczyk and D. Husmeier. Improving the structure MCMC sampler for Bayesian networks by introducing a new edge reversal move. Machine Learning, 71(2):265–305, 2008

  6. [13]

    Hastie, R

    T. Hastie, R. Tibshirani, and J. Friedman. The elements of statistical learning, 2009

  7. [14]

    Heckerman, C

    D. Heckerman, C. Meek, and G. Cooper. A Bayesian approach to causal discovery. In Computation, Causation, and Discov- ery, pages 141–166. AAAI Press, 2006

  8. [15]

    Kass and A.E

    R.E. Kass and A.E. Raftery. Bayes factors. Journal of the American Statistical Association , 90(430):773–795, 1995

  9. [16]

    Kontoyiannis

    I. Kontoyiannis. Context-tree weighting and Bayesian Context Trees: Asymptotic and non-asymptotic justifications. IEEE Trans. Inform. Theory , 70(2):1204–1219, 2024

  10. [17]

    Kontoyiannis, L

    I. Kontoyiannis, L. Mertzanis, A. Panotonoulou, I. Papageor- giou, and M. Skoularidou. Bayesian Context Trees: Modelling and exact inference for discrete time series. Jouranl of the Royal Statistical Society Series B , 84(4):1287–1323, 2022

  11. [18]

    Ledoux and M

    M. Ledoux and M. Talagrand. Probability in Banach Spaces: Isoperimetry and Processes . Springer-Verlag, Berlin, 1991

  12. [19]

    Lorch, J

    L. Lorch, J. Rothfuss, B. Sch ¨olkopf, and A. Krause. DiBS: Dif- ferentiable Bayesian structure learning. NeurIPS, 34:24111– 24123, 2021

  13. [20]

    Lozano, J.I

    G.L. Lozano, J.I. Bravo, M.F. Garavito Diago, H.B. Park, A. Hurley, S.N. Peterson, E.V . Stabb, J.M. Crawford, N.A. Broderick, and J. Handelsman. Introducing THOR, a model microbiome for genetic dissection of community behavior. mBio, 10(2):e02846–18, 2019

  14. [21]

    Mamaghan, P

    A.M.K. Mamaghan, P. Tigas, K.H. Johansson, Y . Gal, Y . An- nadani, and S. Bauer. Challenges and considerations in the evaluation of Bayesian causal discovery. arXiv e-prints , 2406.03209 [cs.LG], 2024

  15. [22]

    Meinshausen and P

    N. Meinshausen and P. B ¨uhlmann. High-dimensional graphs and variable selection with the Lasso. Annals of Statistics , 34(3):1436–1462, 2006

  16. [23]

    Papageorgiou and I

    I. Papageorgiou and I. Kontoyiannis. Posterior representations for Bayesian Context Trees: Sampling, estimation and conver- gence. Bayesian Analysis, 19(2):501–529, 2024

  17. [24]

    J. Pearl. Causality. Cambridge University Press, 2009

  18. [25]

    Peters and P

    J. Peters and P. B ¨uhlmann. Identifiability of Gaussian structural equation models with equal error variances. Biometrika, 101(1):219–228, 2014

  19. [26]

    Peters, D

    J. Peters, D. Janzing, and B. Schlkopf. Elements of Causal Inference: Foundations and Learning Algorithms . The MIT Press, 2017

  20. [27]

    Schwartz

    L. Schwartz. On Bayes procedures. Z. Wahrsch. Verw. Gebiete, 4(1):10–26, 1965

  21. [28]

    G. Schwarz. Estimating the dimension of a model. Annals of Statistics, 6(2):461–464, 1978

  22. [30]

    Sherman and W.J

    J. Sherman and W.J. Morrison. Adjustment of an inverse matrix corresponding to a change in one element of a given matrix. Annals of Mathematical Statistics , 21(1):124–127, 1950

  23. [31]

    M. Shin, A. Bhattacharya, and V .E. Johnson. Scalable Bayesian variable selection using nonlocal prior densities in ultrahigh- dimensional settings. Statistica Sinica, 28(2):1053–1078, 2018

  24. [32]

    Spirtes and C.N

    P. Spirtes and C.N. Glymour. An algorithm for fast recovery of sparse causal graphs. Social Science Computer Review , 9(1):62–72, 1991

  25. [33]

    Strieder and M

    D. Strieder and M. Drton. Confidence in causal inference under structure uncertainty in linear causal models with equal variances. Journal of Causal Inference, 11(1):20230030, 2023

  26. [34]

    Testi and A

    E. Testi and A. Giorgetti. Blind wireless network topology inference. IEEE Trans. Comm. , 69(2):1109–1120, 2020

  27. [35]

    C. Toth, L. Lorch, C. Knoll, A. Krause, F. Pernkopf, R. Peharz, and J. von K ¨ugelgen. Active Bayesian causal inference. arXiv e-prints, 2206.02063 [cs.LG], 2022

  28. [36]

    Viinikka, A

    J. Viinikka, A. Hyttinen, J. Pensar, and M. Koivisto. Towards scalable Bayesian learning of causal DAGs. arXiv e-prints , 2010.00684 [cs.LG], 2020

  29. [37]

    X. Wu, S. Peng, J. Li, J. Zhang, Q. Sun, W. Li, Q. Qian, Y . Liu, and Y . Guo. Causal inference in the medical domain: A survey. Applied Intelligence, 54(6):4911–4934, 2024

  30. [38]

    Zhang and P

    J. Zhang and P. Spirtes. Detection of unfaithfulness and robust causal inference. Minds and Machines , 18:239–271, 2008

  31. [39]

    Zheng, B

    X. Zheng, B. Aragam, P.K. Ravikumar, and E.P. Xing. DAGs with NO TEARS: Continuous optimization for structure learn- ing. NeurIPS, 31:9492–9503, 2018. 13

Pith tools

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