REVIEW 2 major objections 6 minor 34 references
On generating random Gaussian graphical models
T0 review · 2 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read For chordal graphs, correlation matrices respecting the graph's zero pattern can be drawn uniformly, and a hybrid of uniform sampling and orthogonalization extends the construction to general graphs.
desk verdict A useful, honest methods paper that gives chordal uniform sampling a real try; the main practical claim is only as good as the unexamined Metropolis chain underneath it. 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 load-bearing object is the Cholesky parametrization $\Phi: U \mapsto UU^t$ restricted to $U^p_1(G)$, the set of unit-row upper-triangular matrices whose zero pattern matches the missing edges of $G$; for chordal $G$ this map is a bijection onto $E_p(G)$ and its Jacobian factorizes across rows, reducing uniform sampling on the elliptope to independent one-dimensional-hemisphere Metropolis draws. The second mechanism is modified Gram-Schmidt orthogonalization of each row against the rows it must be orthogonal to, which enforces the zero pattern of $E_p(G)$ and serves both as a standalone generator and as the cleanup step that removes fill-in edges after triangulation.
What would settle it
Run Algorithm 3 on a chordal graph with a high-degree node, collect many draws, and compare the empirical distribution of off-diagonal entries with the exact uniform marginals on $E_p(G)$ (available in closed form for small graphs such as the three-node chain, where $E_3(G)$ is the unit disk); a systematic discrepancy that grows with dimension or degree would falsify the uniformity claim.
Extended reading notes
Core claim
For a chordal undirected graph $G$ with a perfect elimination ordering, the paper establishes a one-to-one parametrization of the elliptope slice $E_p(G)$ by unit-row upper-triangular Cholesky factors: $\Phi(U)=UU^t$ with $U \in U^p_1(G)$. The Jacobian of this map, $\det(J_\Phi(U))=2^p \prod_{i=1}^p u_{ii}^{|\operatorname{pa}(i)|+1}$, factorizes row by row, so the uniform measure on $E_p(G)$ pulls back to independent distributions on hemispheres $S_+^{|\mathrm{ch}(i)|}$, each with density proportional to the first coordinate raised to $|\operatorname{pa}(i)|+1$. The paper then samples those rows with a Metropolis-Hastings step and maps back through $\Phi$, giving a uniform draw from $E_p(G)$. For a general undirected graph, the paper's Algorithm 5 samples a Cholesky factor uniformly on a triangulation and then orthogonalizes rows against non-neighbours, returning a matrix in $E_p(G)$ without a stated target distribution.
Load-bearing premise
The uniformity guarantee depends on the random-walk sampling step having converged to its target distribution by the time the algorithm stops, for every graph size and node degree used; no mixing analysis, tuning values, or diagnostics are supplied, and for the non-chordal hybrid the output distribution is not described at all.
Editorial extensions
If this is right
- For chordal graphs, Algorithm 3 gives a uniform sampler over $E_p(G)$ (up to Markov-chain error), so validation studies can benchmark against the full set of compatible correlation matrices instead of a biased subset.
- Structure-learning comparisons built on diagonally dominant matrices can mis-rank methods: the paper's replication of an earlier benchmark study shows rankings change when the proposed generator is used, especially at higher graph density.
- The row-wise factorization means the computational cost of the uniform sampler is governed by parent and child counts in a perfect elimination ordering, not by the full $p \times p$ matrix, so the method remains usable for moderately large chordal graphs.
- For non-chordal graphs, the hybrid method guarantees a matrix in $E_p(G)$ and spreads off-diagonal entries more than diagonal dominance, though it does not carry a uniformity guarantee.
Reading between the lines
- The paper leaves the Metropolis step uncharacterized; a natural calibration exercise would be to compare Algorithm 3's output with exact uniform marginals on small chordal graphs (e.g., the three-node chain, where $E_3(G)$ is the unit disk) to pick burn-in and noise variance.
- Because Algorithm 5's output depends on the chosen triangulation and vertex ordering, one could randomize over triangulations or average over orderings to obtain a better-defined reference distribution for non-chordal graphs.
- The same Cholesky-row sampling scheme transfers directly to concentration graphs, since $\Omega = UU^t$ with zeros in the upper triangle is exactly the decomposition the paper uses; the validation comparisons shown are for correlation/covariance matrices, but the generator applies to the precision-matrix case as well.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proposes methods for generating symmetric positive definite correlation matrices whose zero pattern is prescribed by an undirected graph, with the aim of improving synthetic-model generation for validating structure learning algorithms. For chordal graphs, it develops a uniform sampler over the set E_p(G) of compatible correlation matrices. The method uses the Cholesky parametrization U ↦ UU^t, whose Jacobian factorizes across rows, and samples each row independently on a hemisphere S_+^α from a density proportional to v_1^γ with γ = |pa(i)| + 1, using the Metropolis-Hastings algorithm mh_u. For non-chordal graphs, the paper proposes a hybrid method: sample uniformly from a triangulation of G and then apply partial orthogonalization to remove the edges added by the triangulation. The experiments examine marginal distributions of matrix entries for the different generators and compare rankings of structure learning algorithms under diagonal dominance versus the proposed hybrid method.
Significance. Conditional on the Metropolis step converging, the row-factorization argument in Section 3.3 is clean and gives a principled way to sample uniformly from E_p(G) for chordal graphs, which is a useful alternative to the prevailing diagonal-dominance constructions. The paper also ships an R package and reproduction code, which is a concrete asset. The three-variable example (Figure 2) is a convincing sanity check of the uniform target. The empirical finding that the matrix generator changes the ranking of structure learning algorithms is practically relevant. The principal weakness is that the uniformity claim relies on a finite-run Metropolis sampler whose tuning parameters and convergence behavior are not documented; this is fixable but currently load-bearing.
major comments (2)
- [Section 3.3, Algorithms 3-4, Eq. (9)] The claim that Algorithm 3 samples uniformly from E_p(G) for chordal G holds only if mh_u returns a draw from f(v) ∝ v_1^γ on S_+^α. Algorithm 4 is a finite-run Metropolis chain whose two free parameters, the proposal variance σ_epsilon and the burn-in t_b, are never assigned numerical values anywhere in the manuscript, and no acceptance rates, autocorrelation times, or other convergence diagnostics are reported. In Section 4.2, γ can be around 50, where the target density is sharply concentrated near v_1 = 1 and a poorly scaled Gaussian proposal can mix very slowly. Because the uniform-sampling claim is the central contribution, this is a load-bearing gap. Please report the values of σ_epsilon and t_b used in all experiments and provide convergence diagnostics, or alternatively present the result explicitly as an asymptotic statement with a practical verification protocol.
- [Section 3.4, Algorithm 5 and Figures 3-6] For non-chordal graphs, the output of Algorithm 5 depends on the choice of triangulation and of the permutation σ, but the paper does not discuss this dependence or characterize the induced distribution on E_p(G). The figure labels such as "Uniform (+ partial orthogonalization)" can therefore be misleading, because the final output is not uniform over E_p(G). The paper should state explicitly that this hybrid is a heuristic whose distribution is unknown and that different triangulations or permutations may lead to different generators.
minor comments (6)
- [Section 2.3] The sentence "In the Gaussian case, this implies that if 1≺···≺ p is a perfect ordering for G." is incomplete; please finish it, for example by stating that S^p_{>0}(G) = B(G_D) under a perfect ordering.
- [Algorithm 3] The notation in Algorithm 3 for assigning the non-first entries of v to the children columns is garbled in the text; it should read u_{i,ch(i)} = v_{-1}, where v_{-1} is the vector v without its first entry.
- [Section 4.3] The text says "there is a significant improvement in the densest (d = 0.5)", but Figure 7 is labeled d = 0.25; please correct the value or the figure caption to be consistent.
- [Algorithm 4 and Section 3.3] The comment "with default noise variance σ_epsilon and burn-in time t_b" implies that defaults exist, but no values are given; if the defaults come from Córdoba et al. (2018), please provide the values or an explicit pointer.
- [Figures 3, 4, and 6] The captions say "marginal densities of the non-zero entries", but the plots only appear to show the first and last non-zero entries; please state explicitly which entries are displayed.
- [References] The two entries by Córdoba et al. from 2018 are not distinguished in citations; please label them 2018a and 2018b to avoid ambiguity.
Circularity Check
No significant circularity: the chordal uniform-sampling claim follows from a standard area-formula argument, and the Metropolis sampler is fully specified with the correct stationary distribution.
full rationale
The central claim that Algorithm 3 samples uniformly from Ep(G) for chordal G is derived, not assumed. The paper parametrizes Ep(G) by unit-row Cholesky factors with the graph zero pattern, uses the known Jacobian det(JPhi(U)) = 2^p times the product of u_ii^{pa(i)+1} (Eq. 9), and then applies the area formula of Diaconis et al. (2013) to reduce uniform sampling on Ep(G) to independent row sampling from a density proportional to v_1^gamma on S_+^alpha. Each row of U is sampled by the Metropolis-Hastings algorithm in Algorithm 4, whose acceptance ratio (v'_1/v_t1)^gamma has the stated target f(v) proportional to v_1^gamma as its stationary distribution. No fitted parameter is renamed as a prediction, and no data subset is used to calibrate the result. The citations to Cordoba et al. (2018) provide the earlier Metropolis procedure and an alternative statement of the Jacobian, but the algorithm is reproduced in full in the paper and the Jacobian is also attributed to Roverato (2000); these are normal prior-work references rather than load-bearing self-citations. The non-chordal case is explicitly not claimed to be uniform: Algorithm 5 combines uniform sampling on a triangulation with partial orthogonalization, and the conclusions state that sampling uniformly from Ep(G) for non-chordal G remains future work. The absence of mixing diagnostics or explicit tuning values for sigma_epsilon and t_b is a practical convergence concern, not a circularity, because the target distribution of the Metropolis chain is correctly specified by construction.
Assumptions & free parameters
free parameters (2)
- MH noise variance sigma_epsilon
- MH burn-in t_b
assumptions (4)
- standard math The Cholesky factorization parametrization Phi: U_p^1(G) -> E_p(G) is one-to-one for chordal graphs with a perfect ordering (Section 2.3, Eq. 8).
- standard math The Jacobian determinant det(J_Phi(U)) = 2^p * prod_i u_ii^{|pa(i)|+1} (Eq. 9) holds for the Cholesky parametrization.
- ad hoc to paper The Metropolis-Hastings sampler mh_u (Algorithm 4) samples from f(v) proportional to v_1^gamma on the positive hemisphere S_+^alpha.
- domain assumption For non-chordal graphs, applying uniform sampling to a triangulation and then partial orthogonalizing to remove triangulation edges yields matrices whose distribution is a useful proxy for uniform over E_p(G).
Cite this review
Pith. "Pith review of On generating random Gaussian graphical models." pith.science (2026). https://pith.science/paper/2P4CMY7T
@misc{pith2026190901062,
author = {Pith},
title = {Pith review of: On generating random Gaussian graphical models},
year = {2026},
howpublished = {\url{https://pith.science/paper/2P4CMY7T}},
note = {Machine review of arXiv:1909.01062}
}
read the original abstract
Structure learning methods for covariance and concentration graphs are often validated on synthetic models, usually obtained by randomly generating: (i) an undirected graph, and (ii) a compatible symmetric positive definite (SPD) matrix. In order to ensure positive definiteness in (ii), a dominant diagonal is usually imposed. In this work we investigate different methods to generate random symmetric positive definite matrices with undirected graphical constraints. We show that if the graph is chordal it is possible to sample uniformly from the set of correlation matrices compatible with the graph, while for general undirected graphs we rely on a partial orthogonalization method.
Figures
Figures from the paper (5 more)
Reference graph
Works this paper leans on
-
[1]
author Arvaniti, E. , author Claassen, M. , year 2014 . title Markov network structure learning via ensemble-of-forests models , in: booktitle Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence , publisher AUAI Press . pp. pages 42--51
work page 2014
-
[2]
author Cai, T. , author Liu, W. , author Luo, X. , year 2011 . title A constrained l_1 minimization approach to sparse precision matrix estimation . journal Journal of the American Statistical Association volume 106 , pages 594--607
work page 2011
-
[3]
author Carvalho, C.M. , author Massam, H. , author West, M. , year 2007 . title Simulation of hyper-inverse W ishart distributions in graphical models . journal Biometrika volume 94 , pages 647--659
work page 2007
-
[4]
author C\' o rdoba, I. , author Varando, G. , author Bielza, C. , author Larra\ n aga, P. , year 2018 . title A partial orthogonalization method for simulating covariance and concentration graph matrices , in: editor Kratochv\' i l, V. , editor Studen\' y , M. (Eds.), booktitle Proceedings of the Ninth International Conference on Probabilistic Graphical M...
work page 2018
-
[5]
author C \'o rdoba, I. , author Varando, G. , author Bielza, C. , author Larra \ n aga, P. , year 2018 . title A fast M etropolis- H astings method for generating random correlation matrices , in: editor Yin, H. , editor Camacho, D. , editor Novais, P. , editor Tall \'o n-Ballesteros, A.J. (Eds.), booktitle Intelligent Data Engineering and Automated Learn...
work page 2018
-
[6]
author Cox, D.R. , author Wermuth, N. , year 1993 . title Linear dependencies represented by chain graphs . journal Statistical Science volume 8 , pages 204--218
work page 1993
-
[7]
author Dawid, A.P. , year 1980 . title Conditional independence for statistical operations . journal The Annals of Statistics volume 8 , pages 598--617
work page 1980
-
[8]
author Dawid, A.P. , author Lauritzen, S.L. , year 1993 . title Hyper M arkov laws in the statistical analysis of decomposable graphical models . journal The Annals of Statistics volume 21 , pages 1272--1317
work page 1993
Show all 34 references
-
[9]
, year 1972
author Dempster, A.P. , year 1972 . title Covariance selection . journal Biometrics volume 28 , pages 157--175
1972
-
[10]
, author Holmes, S
author Diaconis, P. , author Holmes, S. , author Shahshahani, M. , year 2013 . title Sampling from a Manifold . publisher Institute of Mathematical Statistics . volume volume 10 of series Collections . pp. pages 102--125
2013
-
[11]
, author Samaras, D
author Honorio, J. , author Samaras, D. , author Rish, I. , author Cecchi, G. , year 2012 . title Variable selection for G aussian graphical models , in: booktitle Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics , publisher PMLR ...
2012
-
[12]
, year 2006
author Joe, H. , year 2006 . title Generating random correlation matrices based on partial correlations . journal Journal of Multivariate Analysis volume 97 , pages 2177 -- 2189
2006
-
[13]
, author Johan, L
author Joong-Ho, W. , author Johan, L. , author Seung-Jean, K. , author Bala, R. , year 2013 . title Condition-number-regularized covariance estimation . journal Journal of the Royal Statistical Society: Series B (Statistical Methodology) volume 75 , pages 427--450
2013
-
[14]
, year 1996
author Kauermann, G. , year 1996 . title On a dualization of graphical G aussian models . journal Scandinavian Journal of Statistics volume 23 , pages 105--116
1996
-
[15]
, author Rajaratnam, B
author Khare, K. , author Rajaratnam, B. , year 2011 . title Wishart distributions for decomposable covariance graph models . journal The Annals of Statistics volume 39 , pages 514--555
2011
-
[16]
a mer, N. , author Sch \
author Kr \"a mer, N. , author Sch \"a fer, J. , author Boulesteix, A.L. , year 2009 . title Regularized estimation of large-scale gene association networks using graphical G aussian models . journal BMC Bioinformatics volume 10 , pages 384
2009
-
[17]
, year 1996
author Lauritzen, S.L. , year 1996 . title Graphical Models . publisher Oxford University Press
1996
-
[18]
, author Wolf, M
author Ledoit, O. , author Wolf, M. , year 2012 . title Nonlinear shrinkage estimation of large-dimensional covariance matrices . journal Annals of Statistics volume 40 , pages 1024--1060
2012
-
[19]
, year 2013
author Lenkoski, A. , year 2013 . title A direct sampler for G-Wishart variates . journal Stat volume 2 , pages 119--128
2013
-
[20]
, author Massam, H
author Letac, G. , author Massam, H. , year 2007 . title Wishart distributions for decomposable graphs . journal The Annals of Statistics volume 35 , pages 1278--1323
2007
-
[21]
, author Kurowicka, D
author Lewandowski, D. , author Kurowicka, D. , author Joe, H. , year 2009 . title Generating random correlation matrices based on vines and extended onion method . journal Journal of Multivariate Analysis volume 100 , pages 1989 -- 2001
2009
-
[22]
, author Zhu, S
author Lin, Y. , author Zhu, S. , author Lee, D. , author Taskar, B. , year 2009 . title Learning sparse M arkov network structure via ensemble-of-trees models , in: booktitle Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics , publi...
2009
-
[23]
, author Power, S.C
author Paulsen, V.I. , author Power, S.C. , author Smith, R.R. , year 1989 . title Schur products and matrix completions . journal Journal of Functional Analysis volume 85 , pages 151--178
1989
-
[24]
, year 1999
author Pourahmadi, M. , year 1999 . title Joint mean-covariance models with applications to longitudinal data: Unconstrained parameterisation . journal Biometrika volume 86 , pages 677--690
1999
-
[25]
, year 2000
author Roverato, A. , year 2000 . title Cholesky decomposition of a hyper inverse W ishart matrix . journal Biometrika volume 87 , pages 99--112
2000
-
[26]
, author Strimmer, K
author Sch \"a fer, J. , author Strimmer, K. , year 2005 a. title An empirical B ayes approach to inferring large-scale gene association networks . journal Bioinformatics volume 21 , pages 754--764
2005
-
[27]
, author Strimmer, K
author Sch \"a fer, J. , author Strimmer, K. , year 2005 b. title A shrinkage approach to large-scale covariance matrix estimation and implications for functional genomics . journal Statistical Applications in Genetics and Molecular Biology volume 4
2005
-
[28]
, author Jelisavcic, V
author Stojkovic, I. , author Jelisavcic, V. , author Milutinovic, V. , author Obradovic, Z. , year 2017 . title Fast sparse G aussian M arkov random fields learning based on C holesky factorization , in: booktitle Proceedings of the Twenty-Sixth International Joint Conference...
2017
-
[29]
, year 2018
author Tropp, J.A. , year 2018 . title Simplicial faces of the set of correlation matrices . journal Discrete & Computational Geometry volume 60 , pages 512 -- 529
2018
-
[30]
, year 1980
author Wermuth, N. , year 1980 . title Linear recursive equations, covariance selection, and path analysis . journal Journal of the American Statistical Association volume 75 , pages 963--972
1980
-
[31]
, author Cox, D
author Wermuth, N. , author Cox, D. , author Marchetti, G.M. , year 2006 . title Covariance chains . journal Bernoulli volume 12 , pages 841--862 . :10.3150/bj/1161614949
2006
-
[32]
, author Piironen, J
author Williams, D.R. , author Piironen, J. , author Vehtari, A. , author Rast, P. , year 2018 . title Bayesian estimation of G aussian graphical models with predictive covariance selection . http://arxiv.org/abs/1801.05725 arXiv:1801.05725
2018 arXiv
-
[33]
, author Zou, H
author Xue, L. , author Zou, H. , year 2012 . title Regularized rank-based estimation of high-dimensional nonparanormal graphical models . journal Annals of Statistics volume 40 , pages 2541--2571
2012
-
[34]
, author Lin, Y
author Yuan, M. , author Lin, Y. , year 2007 . title Model selection and estimation in the G aussian graphical model . journal Biometrika volume 94 , pages 19--35
2007
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.