{"id":"31ef0991-cadc-40b8-9726-9f3fa3aa4fa5","arxiv_id":"1909.01062","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A method to generate graph-constrained correlation matrices, uniform for chordal graphs and via a hybrid scheme for general graphs, with experiments showing that validation rankings depend heavily on the simulation method.","lead":"This paper proposes new ways to generate random correlation matrices that respect the zero-pattern constraints of an undirected graph, for use in testing graphical model learning algorithms. For chordal graphs the authors sample near-uniformly from this set, and they show that the choice of sampling method changes how structure learning algorithms are ranked.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Uniform-sampling claim for chordal graphs rests on an untested Metropolis sampler: no mixing analysis, tuning values, or diagnostics are given for Algorithm 4.","rationale":"The paper's central novelty is the chordal uniform sampler. The mathematics leading to the row densities appears sound: the Jacobian factorization in Eq. 9 is consistent with the known full elliptope case, and the sequential orthogonalization in Algorithm 5 is algorithmically valid for producing matrices in E_p(G). The non-chordal hybrid's lack of a distributional characterization is real, but the paper explicitly states that uniform sampling for non-chordal graphs is future work, so that gap is less load-bearing than the unverified MCMC step. The reader's conditional verdict is appropriate: the claim holds asymptotically if the MH chain is exact, but the implemented finite-run sampler is not demonstrated to deliver the claimed uniform distribution. The proposed concrete test, comparing Algorithm 3 against an exact sampler for the actual graph sizes and gamma values used in the experiments, would settle whether the concern lands.","tokens_in":39156,"tokens_out":19170,"duration_ms":215441,"concrete_test":"Reproduce Algorithm 3 for the chordal triangulation G' used in Section 4.2 (p = 50, edge probability 0.05) with exact row sampling: for each row i, sample v on S_+^alpha exactly, e.g. by rejection sampling from the uniform hemisphere with acceptance probability (v_1)^gamma, or by an equivalent exact method. Draw 5,000 exact U matrices and 5,000 U matrices from the paper's gmat implementation using its default sigma_epsilon and t_b. Compare the marginal distribution of u_ii, or of a fixed off-diagonal entry of M, for each row using a two-sample KS test, and report the smallest p-value and the effective sample size of the MH draws. A significant deviation for any row would show that the implemented Algorithm 3 is not actually sampling uniformly from E_p(G).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is Algorithm 3 + Algorithm 4: for each row i, a single draw from a finite-run Metropolis chain is treated as a sample from f(v) proportional to v_1^gamma on S_+^alpha, with gamma = |pa(i)| + 1 and alpha = |ch(i)|. The area-formula argument in Section 3.3 and Eq. 9, combined with the row factorization, correctly shows that if each row were exactly distributed as f, then M = UU^t would be uniform on E_p(G). It does not show that the finite chain in Algorithm 4, with unspecified sigma_epsilon and t_b, has reached that target. In Section 4.2, gamma reaches values around 50, where the target density is sharply concentrated near v_1 = 1; a poorly scaled Gaussian proposal can mix slowly, and no acceptance rates, autocorrelation times, or Gelman-Rubin diagnostics are reported. The chordal uniformity claim and the validation results in Figures 3-8 therefore depend on an unverified practical assumption, even though the asymptotic stationary distribution of the MH chain is correct.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":39361,"tokens_out":15855,"duration_ms":169976,"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":[{"comment":"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":"Section 3.3, Algorithms 3-4, Eq. (9)"},{"comment":"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.","section":"Section 3.4, Algorithm 5 and Figures 3-6"}],"minor_comments":[{"comment":"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.","section":"Section 2.3"},{"comment":"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":"Algorithm 3"},{"comment":"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.","section":"Section 4.3"},{"comment":"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.","section":"Algorithm 4 and Section 3.3"},{"comment":"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.","section":"Figures 3, 4, and 6"},{"comment":"The two entries by Córdoba et al. from 2018 are not distinguished in citations; please label them 2018a and 2018b to avoid ambiguity.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The theoretical derivation for chordal graphs is sound and the code is a real asset. My main concern is that the uniformity claim is presented as a property of Algorithm 3 although it depends on an MCMC convergence assumption that is not documented. I believe this is fixable with added tuning values, diagnostics, and careful wording about the non-chordal hybrid; I would not reject the manuscript."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know about this paper if you care about how synthetic Gaussian graphical models are generated for benchmarking structure learning. It makes a concrete point: diagonal dominance, the default trick for ensuring positive definiteness, produces matrices whose off-diagonal entries are squeezed toward zero, and that distorts which structure learning algorithms look good. The authors test this by replicating Krämer et al.'s validation with their own sampler and show rankings change. That part is solid and well motivated.\n\nWhat is actually new is modest but real. They assemble existing pieces — the row-wise Metropolis sampler and partial orthogonalization from their own 2018 papers, the Jacobian from Roverato — into a scheme for chordal graphs where the rows factor, so exact uniform sampling from the elliptope is possible in principle. For non-chordal graphs they triangulate, sample uniformly on the triangulation, then orthogonalize to kill the fill-in edges. They are upfront that the non-chordal hybrid has no characterized distribution.\n\nThe soft spot is exactly where the stress-test lands. Algorithm 4 is the load-bearing part for chordal uniformity, and the paper gives no tuning values for the proposal variance or burn-in, no acceptance rates, no mixing diagnostics. For high-degree nodes the target density is sharply concentrated near v1=1, and a poorly scaled Gaussian proposal could easily mix slowly. The area formula argument is correct conditional on the chain being at its stationary distribution, but the finite-run chain is treated as if it were there. This is a standard MCMC caveat, but for a paper whose headline is 'sample uniformly', it needs to be quantified. The authors could easily add a short diagnostic section. The validation plots also lack error bars, which is minor but annoying when the claim is that rankings change.\n\nI don't think the reader's skepticism should be pushed further. The paper is honest, the building blocks are published, and the three-variable simulation matches the expected uniform disk. The chordal result is genuinely useful, and the non-chordal method, while heuristic, is still a clear improvement over diagonal dominance in exploring the off-diagonal range.\n\nI'd send this to referees. A serious referee can ask for the missing diagnostics and a more careful statement of what is proven versus approximated. I'd cite it if I were writing about simulation of graphical models.","headline":"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.","tokens_in":39913,"tokens_out":2170,"would_cite":true,"duration_ms":21872,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["random correlation matrix","chordal graph","Cholesky parametrization","Metropolis-Hastings sampling","partial orthogonalization","Gaussian graphical model","structure learning validation","positive definite matrix simulation"],"falsifier":"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.","tokens_in":38927,"feed_emoji":"🎲","tokens_out":10552,"duration_ms":94689,"temperature":0.7,"pith_summary":"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.","feed_headline":"Uniform sampling of chordal-graph correlation matrices is possible","feed_subtitle":"The generator changes which structure-learning algorithms look good, so validation results depend on it.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Provides the partial orthogonalization method (Algorithm 2) that the paper adapts and whose i.i.d.-entry behaviour it analyses.","marker":"Córdoba et al. (2018)"},{"why":"Supplies the Metropolis-Hastings sampler (Algorithm 4) used to draw rows from hemisphere densities proportional to the first coordinate raised to a power.","marker":"Córdoba et al. (2018)"},{"why":"Gives the Jacobian of the Cholesky parametrization that factorizes across rows and underlies the uniform sampler.","marker":"Roverato (2000)"},{"why":"Provides the area-formula theorem (their Theorem 1) that justifies sampling from a density proportional to the Jacobian to obtain uniform draws on the elliptope slice.","marker":"Diaconis et al. (2013)"},{"why":"Establishes the equality between positive definite matrices with chordal zero pattern and the Bayesian-network Cholesky parametrization used here.","marker":"Wermuth (1980)"},{"why":"Supplies the chordal-graph machinery (perfect sequences of cliques, perfect orderings) that lets a chordal graph be oriented without v-structures.","marker":"Lauritzen (1996)"},{"why":"Provides the structure-learning validation benchmark and the diagonal-dominance generator whose conclusions the paper replicates and contrasts.","marker":"Krämer et al. (2009)"}],"fun_headline_variants":["Chordal graphs enable uniform correlation matrix sampling","Uniform draws from chordal-graph elliptope slices","Cholesky trick samples chordal correlation matrices uniformly","Uniform chordal-graph correlation sampling via Cholesky"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Chordal graphs enable uniform correlation matrix sampling","Uniform draws from chordal-graph elliptope slices","Cholesky trick samples chordal correlation matrices uniformly","Uniform chordal-graph correlation sampling via Cholesky"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000698,"raw_usage":{"total_tokens":3113,"prompt_tokens":865,"completion_tokens":2248,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":481,"completion_tokens_details":{"reasoning_tokens":2186}},"tokens_in":481,"tokens_out":2248,"duration_ms":18181,"temperature":1.0,"reasoning_tokens":2186,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T05:27:27.922223+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":", year 2000","cited_arxiv_id":null,"evidence_quote":"Gives the Jacobian of the Cholesky parametrization that factorizes across rows and underlies the uniform sampler."},{"cited_title":", author Holmes, S","cited_arxiv_id":null,"evidence_quote":"Provides the area-formula theorem (their Theorem 1) that justifies sampling from a density proportional to the Jacobian to obtain uniform draws on the elliptope slice."},{"cited_title":", year 1980","cited_arxiv_id":null,"evidence_quote":"Establishes the equality between positive definite matrices with chordal zero pattern and the Bayesian-network Cholesky parametrization used here."},{"cited_title":", year 1996","cited_arxiv_id":null,"evidence_quote":"Supplies the chordal-graph machinery (perfect sequences of cliques, perfect orderings) that lets a chordal graph be oriented without v-structures."}],"review_version":1}