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 →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
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.
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
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- [Section IV, Lemma 5 and Eqs. (35), (44)]
- [Theorem 3]
- [Lemma 5 proof, remainder term]
minor comments (3)
- [Eq. (35)]
- [Section VI-A]
- [References]
Circularity Check
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
assumptions (6)
- domain assumption The true parameter (S*, w*) is causally minimal.
- domain assumption Noise is i.i.d. Gaussian N(0, σ^2 I) with known variance σ^2.
- domain assumption Edge weights have independent Gaussian N(0, σ_w^2) priors given the graph.
- standard math Law of the iterated logarithm holds for the relevant i.i.d. sums.
- domain assumption The dimension d is fixed and the DAG space Gd is finite.
- standard math Schwartz's Bayesian consistency theorem applies to this model.
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
Reference graph
Works this paper leans on
-
[29]
J. Shaska and U. Mitra. Neyman-Pearson causal inference. In 2024 IEEE International Symposium on Information Theory (ISIT), pages 1269–1274, 2024
work page 2024
-
[1]
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
work page 2023
-
[2]
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
arXiv 2021
-
[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
work page 2019
-
[4]
I. Castillo, J. Schmidt-Hieber, and A. Van der Vaart. Bayesian linear regression with sparse priors. Annals of Statistics , 42(5):1986–2018, 2015
work page 1986
-
[5]
H. Chang, J.J. Cai, and Q. Zhou. Order-based structure learning without score equivalence. Biometrika, 111(2):551–572, 2024
work page 2024
-
[6]
W. Chen, M. Drton, and Y .S. Wang. On causal discovery with an equal-variance assumption. Biometrika, 106(4):973–980, 2019
work page 2019
-
[7]
D.M. Chickering. Optimal structure identification with greedy search. J. Mach. Learn. Res. , 3:507–554, 2002
work page 2002
Show all 39 references
-
[8]
Cundy, A
C. Cundy, A. Grover, and S. Ermon. BCD Nets: Scalable variational approaches for Bayesian causal discovery. NeurIPS, 34:7095–7110, 2021
2021
-
[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
2007
-
[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
1999
-
[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
2003
-
[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
2008
-
[13]
Hastie, R
T. Hastie, R. Tibshirani, and J. Friedman. The elements of statistical learning, 2009
2009
-
[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
2006
-
[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
1995
-
[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
2024
-
[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
2022
-
[18]
Ledoux and M
M. Ledoux and M. Talagrand. Probability in Banach Spaces: Isoperimetry and Processes . Springer-Verlag, Berlin, 1991
1991
-
[19]
Lorch, J
L. Lorch, J. Rothfuss, B. Sch ¨olkopf, and A. Krause. DiBS: Dif- ferentiable Bayesian structure learning. NeurIPS, 34:24111– 24123, 2021
2021
-
[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
2019
-
[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
2024 arXiv
-
[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
2006
-
[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
2024
-
[24]
J. Pearl. Causality. Cambridge University Press, 2009
2009
-
[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
2014
-
[26]
Peters, D
J. Peters, D. Janzing, and B. Schlkopf. Elements of Causal Inference: Foundations and Learning Algorithms . The MIT Press, 2017
2017
-
[27]
Schwartz
L. Schwartz. On Bayes procedures. Z. Wahrsch. Verw. Gebiete, 4(1):10–26, 1965
1965
-
[28]
G. Schwarz. Estimating the dimension of a model. Annals of Statistics, 6(2):461–464, 1978
1978
-
[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
1950
-
[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
2018
-
[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
1991
-
[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
2023
-
[34]
Testi and A
E. Testi and A. Giorgetti. Blind wireless network topology inference. IEEE Trans. Comm. , 69(2):1109–1120, 2020
2020
-
[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
2022 arXiv
-
[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
2010 arXiv
-
[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
2024
-
[38]
Zhang and P
J. Zhang and P. Spirtes. Detection of unfaithfulness and robust causal inference. Minds and Machines , 18:239–271, 2008
2008
-
[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
2018
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.