Pith. sign in

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 →

arxiv 1909.01062 v2 pith:2P4CMY7T submitted 2019-09-03 stat.ME

classification stat.ME
keywords randomcorrelationmatrixchordalgraphCholeskyparametrizationMetropolis-HastingssamplingpartialorthogonalizationGaussiangraphicalmodelstructurelearningvalidationpositivedefinitesimulation
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

This paper addresses how synthetic Gaussian graphical models are built for validating structure-learning algorithms. It argues that the usual trick of enforcing a dominant diagonal biases the generated matrices toward tiny off-diagonal entries, and shows experimentally that this bias changes which algorithms appear to work. The main positive result is that when the underlying undirected graph is chordal (every cycle of length four or more has a chord), one can sample uniformly from the set of correlation matrices compatible with that graph, using a row-wise Cholesky parametrization and a Metropolis step on hemispheres. For non-chordal graphs, the authors triangulate the graph, sample uniformly on the triangulation, and then apply partial orthogonalization to delete the added edges, producing a matrix in the desired set whose entries explore the off-diagonal range more fully.

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.

Watch

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

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

  • 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.
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

2 major / 6 minor

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)
  1. [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.
  2. [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)
  1. [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.
  2. [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.
  3. [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.
  4. [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.
  5. [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.
  6. [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

0 steps flagged · score 0.0 of 10

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 2 free parameters · 4 assumptions · 0 invented entities

The paper's central contribution rests on a published Jacobian, the authors' own MH sampler, and an uncharacterized hybrid scheme for non-chordal graphs. No new physical or mathematical entities are introduced.

free parameters (2)
  • MH noise variance sigma_epsilon
    Used in Algorithm 4's proposal step; convergence and acceptance probability depend on it, but no value or tuning guidance is given in the paper.
  • MH burn-in t_b
    Number of iterations discarded before returning the sample; no value is provided, and there is no convergence diagnostic to justify the choice.
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).
    This equivalence between decomposable models and DAGs with no v-structures is established in the cited literature (Wermuth 1980; Paulsen et al. 1989) and assumed without proof here.
  • 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.
    Attributed to Roverato (2000) and Córdoba et al. (2018); used to define the row densities for the MH sampler. The paper relies on this result rather than deriving it.
  • 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.
    The sampler was introduced in the authors' own Córdoba et al. (2018) IDEAL paper and is not proven to converge here; the paper provides no mixing or error analysis and leaves tuning parameters unspecified.
  • 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).
    The paper does not characterize this distribution; it only demonstrates empirically in Section 4 that marginal densities look reasonable and that validation rankings change. Whether this distribution is adequate for validation is assumed rather than proven.

how reviews work

0 comments
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 reproduced from arXiv: 1909.01062 by the authors.

Figure 1
Figure 1. Chordal undirected graph with three variables. [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 2
Figure 2. Scatter plot of the two non-zero entries for correlation matrices sampled from [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Marginal densities of the non-zero entries of matrices sampled from [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: Marginal densities of the non-zero entries of matrices sampled from [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]
Figure 5
Figure 5. Figure 5: Chordal undirected graph Gchain with 50 variables and 49 edges 11 [PITH_FULL_IMAGE:figures/full_fig_p011_5.png]
Figure 6
Figure 6. Figure 6: Marginal densities of the non-zero entries of matrices sampled from [PITH_FULL_IMAGE:figures/full_fig_p012_6.png]
Figure 7
Figure 7. Figure 7: True positive rate (TPR) and true discovery rate (PPV) of the structure learning algorithms [PITH_FULL_IMAGE:figures/full_fig_p013_7.png]
Figure 8
Figure 8. Figure 8: True positive rate (TPR) and true discovery rate (PPV) of the structure learning algorithms [PITH_FULL_IMAGE:figures/full_fig_p014_8.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 33 canonical work pages

  1. [1]

    , author Claassen, M

    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

  2. [2]

    , author Liu, W

    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

  3. [3]

    , author Massam, H

    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

  4. [4]

    , author Varando, G

    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...

  5. [5]

    , author Varando, G

    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...

  6. [6]

    , author Wermuth, N

    author Cox, D.R. , author Wermuth, N. , year 1993 . title Linear dependencies represented by chain graphs . journal Statistical Science volume 8 , pages 204--218

  7. [7]

    , year 1980

    author Dawid, A.P. , year 1980 . title Conditional independence for statistical operations . journal The Annals of Statistics volume 8 , pages 598--617

  8. [8]

    , author Lauritzen, S.L

    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

Show all 34 references
  1. [9]

    , year 1972

    author Dempster, A.P. , year 1972 . title Covariance selection . journal Biometrics volume 28 , pages 157--175

  2. [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

  3. [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 ...

  4. [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

  5. [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

  6. [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

  7. [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

  8. [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

  9. [17]

    , year 1996

    author Lauritzen, S.L. , year 1996 . title Graphical Models . publisher Oxford University Press

  10. [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

  11. [19]

    , year 2013

    author Lenkoski, A. , year 2013 . title A direct sampler for G-Wishart variates . journal Stat volume 2 , pages 119--128

  12. [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

  13. [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

  14. [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...

  15. [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

  16. [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

  17. [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

  18. [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

  19. [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

  20. [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...

  21. [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

  22. [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

  23. [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

  24. [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

  25. [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

  26. [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

Pith tools

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