{"id":"d105edaa-2560-4e27-8b8a-263c23196842","arxiv_id":"2511.01875","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":7,"one_line_summary":"New Gibbs-style samplers with local and global moves make exact Bayesian Gaussian graphical model inference practical at p≈1000, with dimension-free mixing bounds when the true network is sparse.","lead":"This paper presents two MCMC algorithms for exact Bayesian inference in high-dimensional Gaussian graphical models with spike-and-slab priors, and shows they scale to about 1,000 variables. It proves dimension-free mixing bounds under sparsity and matches the runtime of approximate pseudo-Bayesian methods.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Dimension-free mixing bounds are conditional on unproven high-dimensional posterior concentration and on unexamined ideal-Gibbs conductance; abstract's 'provably scale' overstates the proven guarantees.","rationale":"The reader's weakest_assumption is exactly the point I identify: the mixing guarantees are conditioned on the chain being near Ω0 and on posterior concentration, neither of which is established in high dimensions. This is the most load-bearing weakness because it sits between the proved conditional spectral gaps and the advertised 'provably scale to high dimensions.' The paper itself is candid about the gap in Sections 4.2 and 4.4, but the abstract does not carry the caveat, and the ideal-Gibbs ergodicity claim in the abstract has no supporting theorem. The α mismatch (theory α ≈ 54 vs. practice α = 1) is a further disconnect, but it is secondary: even with α satisfying C4, the missing concentration and ideal-Gibbs conductance would remain. I therefore agree with the reader and see no reason to move the verdict. The suggested computational experiment would directly test whether the missing theory has practical teeth.","tokens_in":88961,"tokens_out":8819,"duration_ms":82303,"concrete_test":"Using the authors' code, run the Gibbs/BDMH sampler on a sparse tri-diagonal GGM with known Ω0, n = 2p, for p ∈ {100, 200, 500, 1000}, initialized at the identity (cold start). Record the first iteration t at which Ω^{(t)} enters B_T(Ω0, δ) with δ as in C3, and estimate π(B^c|Y) from a long stationary run. If the hitting time grows gracefully with p and π(B^c|Y) is negligible, the missing concentration is a technical gap; if the hitting time grows super-polynomially or π(B^c|Y) is non-negligible, the dimension-free mixing claim fails for cold starts.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim requires mixing times that do not grow badly with p. The theorems proved (Thm 1, Thm 2) bound the spectral gap of the conditional z-update kernel, not the full chain. The bridge from conditional spectral gaps to full-chain mixing is Proposition 3 / Corollaries 1–2, where the s-conductance of the lazy MH kernel is bounded below by ½ φ_s(P_Gibbs)(1 − e^{−...} − 2π(B^c|Y)/(s φ_s(P_Gibbs))). For this bound to imply a useful mixing time via Eq. (17), three ingredients are needed: (i) φ_s(P_Gibbs) bounded below for the ideal Gibbs sampler; (ii) the conditional spectral gap uniformly large over a set B; (iii) π(B^c|Y)/s small. The paper proves (ii) only on B_T(Ω0, δ) under C3, and never proves (i) or (iii). Section 4.2 states that tight high-dimensional concentration rates for sub-matrices of Ω are not known; Section 4.4 concedes that GIMH is 'only guaranteed to work when the posterior concentrates sufficiently on Ω0, and one has reached stationarity.' Thus the high-dimensional 'proof' is conditional on an unproven concentration hypothesis and an unexamined property of the ideal Gibbs. The abstract additionally claims the ideal Gibbs sampler is 'geometrically ergodic,' yet no theorem in the paper establishes this. Finally, the theory demands α > 1+2(√d+2)² (≈ 54 when d = 10) while all experiments use α = 1, so the proven regime is not the regime recommended and used.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops two MCMC samplers for the posterior distribution of a Gaussian graphical model under a discrete spike-and-slab prior on the precision matrix. The first is a column-wise random-scan Gibbs sampler in which the edge indicators in each column are updated by local moves (Gibbs, BDMH, or LIT); the second is a globally-informed Metropolis-Hastings proposal (GIMH) based on the marginal regression posterior for each column. The paper derives closed-form row-wise conditional updates (Proposition 2), proves conditional spectral-gap bounds for the local and global updates, obtains s-conductance bounds for the full lazy kernels relative to an ideal Gibbs sampler, gives worst-case polynomial per-iteration costs, and reports simulations up to p = 1000 as well as a p = 332 COVID-19 data analysis. Detailed proofs appear in the supplement.","tokens_in":1558,"tokens_out":1586,"duration_ms":72379,"significance":"Exact Bayesian inference for GGMs at p ≈ 1000 would be a substantial advance over current exact samplers and would bring fully Bayesian uncertainty quantification close to the cost of pseudo-Bayesian methods. The construction of tractable row-wise conditionals under a Dirac spike is elegant, Proposition 2 is correct and reusable, and the experiments are thorough: the methods are compared against several state-of-the-art exact and pseudo-Bayesian algorithms on multiple graph structures and sample sizes, with a real-data illustration and a reproducible supplement. The authors also deserve credit for candidly acknowledging several limitations of the theory. If the advertised mixing guarantees were fully established, this would be a high-impact methods paper. In its current form, however, the headline claim that the algorithms 'provably scale to high dimensions when the data-generating precision matrix is sparse' outruns the theorems, which are conditional on unproved high-dimensional concentration and on an unexamined property of the ideal Gibbs sampler.","major_comments":[{"comment":"The full-chain mixing guarantees are conditional on three ingredients that are not all established: (i) a lower bound on the s-conductance of the ideal Gibbs sampler, φ_s(P_Gibbs); (ii) a uniform lower bound on the conditional spectral gaps over a set B; and (iii) smallness of π(B^c|Y)/s. The paper proves (ii) only on sets such as B_T(Ω0,δ) under C3, and it does not prove (i) or (iii) in high dimensions. Section 4.2 states that tight high-dimensional concentration rates for sub-matrices of Ω are not known, and Section 4.4 concedes that GIMH is 'only guaranteed to work when the posterior concentrates sufficiently on Ω0, and one has reached stationarity.' Consequently, Eq. (7) and Corollaries 1–2 provide dimension-free bounds only conditionally on hypotheses that the paper does not establish. The abstract's 'provably scale to high dimensions when the data-generating precision matrix is spa","section":"§4.1–4.4, Proposition 3, Corollaries 1–2"},{"comment":"The abstract states that the paper proves the ideal Gibbs sampler is 'geometrically ergodic.' I could not find any theorem in the main text or the supplement establishing this. The results in Section 4 bound conditional spectral gaps of the z-update kernels and then use Proposition 3 to bound the s-conductance of the full lazy Metropolis-within-Gibbs kernel relative to P_Gibbs. Geometric ergodicity of the ideal Gibbs sampler on the constrained, unbounded space M+(p) is a nontrivial statement and does not follow from the arguments presented. This claim should either be proved explicitly or removed from the abstract and introduction.","section":"Abstract, §1, §4"},{"comment":"There is a substantial mismatch between the theoretical regime and the recommended/implemented regime. Condition C4 requires α > 1 + 2(√d + 2)^2 for the prior inclusion probability θ ∝ p^{-α}, which is roughly 54 when d = 10. The experiments set θ = K/(p−1), i.e., α = 1, and the Discussion states that larger α gave poor inference. The theorems therefore do not cover the settings used in the empirical demonstrations, and the default parameter choice that the paper recommends is outside the proven regime. This should be discussed explicitly and, ideally, the theory should be extended to the practical setting or experiments should also be reported in a regime satisfying C4.","section":"§4.2 (C4), §5.1, §7"}],"minor_comments":[{"comment":"The line 'Ω*_{kj} = 0 if z^{(t-1,r)}_k = 1' appears to invert the intended indicator: non-selected entries should be set to zero, and selected entries should be set to −u*_1. Please check and correct.","section":"Algorithm 4, step 12"},{"comment":"The caption reads 'n∈{p,p,5p}'; this should presumably be 'n∈{p,2p,5p}' to match the main text and the other figures.","section":"Figure 3 caption"},{"comment":"Minor typographical issues: 'Meinhausen & B¨uhlmann' should be 'Meinshausen & Bühlmann', and 'van dem Boom' should be 'van den Boom'. Also check 're-parameterisation' for consistency.","section":"References and spelling"},{"comment":"In the display after Eq. (4), the Gamma density is written as Ga(u2; n/2 + 1, Spp + λ/2), but the parameter second argument is ambiguous (it is later written as (Spp + λ)/2). Please standardize the parametrization to avoid confusion.","section":"Notation in Proposition 2"}],"recommendation":"major_revision","confidential_remarks":"This is a strong computational paper with a clear potential impact, but the advertised 'provable scaling' claim is not supported by the theorems as written. The main missing pieces are identifiable: a proof or explicit assumption about the ideal Gibbs conductance, and high-dimensional posterior concentration for the relevant sets. The theory-practice gap on α also needs to be addressed or at least precisely acknowledged. I would not reject the paper, but it needs substantial revision before the guarantees can be stated as claimed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the row-wise discrete spike-and-slab samplers are a real step forward: they bring exact Bayesian GGM inference to p≈1000 in practice, and the empirical comparisons against ssgraph, bdgraph, and pseudo-likelihood methods are careful and convincing. Second, the theoretical claim in the abstract—'provably scale to high dimensions' and geometric ergodicity of the ideal Gibbs sampler—is not fully backed by the supplied proofs. The paper proves dimension-free spectral gap bounds for the conditional edge-update kernels, but the bridge to the full-chain mixing time depends on posterior concentration in a neighborhood of the true precision matrix (C3, Section 4.2) and on the ideal Gibbs sampler having a bounded s-conductance. Neither is established in high dimensions. The paper itself concedes in Section 4.4 that GIMH is 'only guaranteed to work when the posterior concentrates sufficiently on Ω0, and one has reached stationarity.' So the headline claim is conditional, not unconditional.\n\nWhat's genuinely new: the discrete spike-and-slab prior with Dirac spike, the column-wise update exploiting closed-form conditional marginals (Proposition 2), the GIMH global proposal using a linear-regression inspired proposal with MH correction, and the attempt to port the Yang et al./Zhou et al. mixing theory to GGMs. The derivations in Proposition 2 and the spectral-gap arguments are careful; the supplement includes detailed proofs, and the authors are honest about the gap between theory and practice (e.g., α=1 in experiments versus α>1+2(√d+2)^2 in theory).\n\nSoft spots: (1) The abstract's 'geometrically ergodic' claim for the ideal Gibbs sampler has no corresponding theorem in the body or supplement—it's simply asserted. (2) The dimension-free mixing result is conditional on unproven high-dimensional posterior concentration; the paper notes that tight concentration rates for submatrices of Ω are not known (Section 4.2). (3) The proven regime requires a very large α, which the experiments deliberately avoid—so the theorems don't cover the recommended default settings. These are addressable either by relaxing the claims or by adding a proper concentration theorem. I don't think they sink the paper; the algorithms and experiments stand on their own.\n\nBottom line: this is a serious, thoughtful contribution to Bayesian graphical models. It deserves a real referee, not a desk reject. The referee should ask for a revision that either proves or properly qualifies the 'provably scale' and 'geometrically ergodic' statements. I'd cite it and bring it to a reading group—it's exactly the kind of paper that generates good discussion about when MCMC theory matches practice.","headline":"Solid computational advance for Bayesian GGMs, but the 'provably scale' headline outruns the proven theorems.","tokens_in":89874,"tokens_out":4519,"would_cite":true,"duration_ms":35518,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62F15","62H22","65C40"],"pacs":[],"model":"deepseek-v4-flash","headline":"Exact Bayesian samplers for sparse Gaussian graphs provably scale to p≈1000.","keywords":["Gaussian graphical models","spike-and-slab prior","Markov chain Monte Carlo","spectral gap","birth-death-swap","Metropolis-within-Gibbs","high-dimensional inference","precision matrix"],"falsifier":"Run the local birth-death-swap sampler initialized far from the truth (e.g., at the identity matrix) on an ill-conditioned sparse precision matrix with n=p and modest signal; if the estimated mixing time grows with p or the chain fails to converge, the dimension-free claim is not universal. More directly, estimate the spectral gap of the column-update kernels from simulations under Conditions C0–C4 and check whether it remains bounded below by a constant independent of p.","tokens_in":88850,"feed_emoji":"🧮","tokens_out":3929,"duration_ms":37416,"temperature":0.7,"pith_summary":"The paper claims that fully Bayesian inference for Gaussian graphical models—quantifying uncertainty about which edges exist and about the precision matrix—is computationally feasible for thousands of variables when the true precision matrix is sparse. Two samplers are introduced: a row-wise Metropolis-within-Gibbs algorithm using local birth-death-swap moves, and a global proposal that updates several edges at once based on a linear-regression surrogate. The authors prove that, under sparsity conditions, the mixing times of these samplers do not grow with the number of variables, and that per-iteration costs are polynomial. Empirically, the methods move exact posterior inference from roughly 100 to roughly 1,000 variables (5,000 to 500,000 edges) at speeds comparable to pseudo-Bayesian approximations.","feed_headline":"Exact Bayesian graph inference reaches 1,000 variables","feed_subtitle":"New samplers match pseudo-Bayesian speed while keeping full posterior uncertainty","key_machinery":"The central object is the conditional posterior distribution for a column of the precision matrix, reparameterized as u1=-Ω_zp and u2=Ω_pp-Ω_zp^TΣ_zz|pΩ_zp. Proposition 2 shows the edge-inclusion indicators z have marginal probabilities proportional to exp(m_z^T U_z m_z/2) g1^{|z|}|U_z|^{1/2} θ^{|z|}(1-θ)^{p-1-|z|}, with U_z=(S_pp+λ)Σ_zz|p+g1^{-2}I_z. This form matches the marginal likelihood of a linear regression, allowing local moves via rank-1 Cholesky updates and a global proposal built from a tempered linear-regression posterior. The proof of mixing bounds uses an importance-weight argument: if the maximum importance weight is bounded by W, the spectral gap is at least 1/W, and the pap","core_discovery":"The authors establish that the conditional posterior for one row of the precision matrix, given the rest, has a closed form that depends only on the non-zero entries (Proposition 2). This enables a discrete spike-and-slab prior with exact zeros, so each row update samples only the few non-zero coefficients. For the local birth-death-swap sampler they prove the spectral gap is dimension-free when M=p steps are used (Theorem 1), and for the globally-informed sampler they prove the spectral gap tends to 1 as n grows (Theorem 2). Both results hold under conditions of sparsity and signal strength, and they imply the ideal Gibbs sampler is geometrically ergodic and that the practical samplers inhe","pith_inferences":["If the dimension-free spectral gap holds more generally, scaling beyond p=1000 is limited mainly by per-iteration cost and the ability to maintain the posterior-concentration condition, not by mixing—so the approach could be extended to even larger problems with more efficient sparse algebra.","The paper's theory requires prior inclusion probability θ ∝ 1/p^α with α large, but experiments with α=1 worked well, suggesting the guarantees are sufficient rather than necessary; testing milder priors empirically would clarify the practical gap.","The global proposal's reliance on a linear-regression surrogate suggests a natural extension to non-Gaussian graphical models via latent Gaussian representations or scale mixtures, which could inherit similar mixing guarantees."],"forward_implications":["Exact Bayesian uncertainty quantification for graphical structure becomes practical for p≈1000, eliminating the need to resort to pseudo-Bayesian approximations for computational reasons.","The per-iteration cost of the ideal Gibbs sampler is O(p^3 + T p(d̄^3+p^2)), and sparse linear algebra reduces it further, so the main bottleneck is the maximum node degree d̄ rather than p itself.","The dimension-free mixing bounds mean that, once the chain is in the region where the posterior concentrates, a fixed number of iterations suffices regardless of dimension.","In the COVID-19 application with p=332, the exact sampler outperformed pseudo-Bayesian baselines in out-of-sample predictive log-likelihood and R² while running in comparable time."],"fun_headline_variants":["Bayesian graph inference scales to 1,000 variables","Exact Bayesian inference now reaches 1,000 variables","Full posterior graph inference for 1,000 variables","Spike-and-slab Bayes hits 1,000-variable mark","Bayesian graphs with exact zeros scale to 1,000 variables"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The mixing guarantees assume the current precision submatrix is already within a small neighborhood of the true matrix (Condition C3) and that the posterior concentrates on that set, which the paper does not establish in high dimensions—for the global sampler it explicitly holds only after stationarity.","fun_headline_variants_meta":{"raw":{"variants":["Bayesian graph inference scales to 1,000 variables","Exact Bayesian inference now reaches 1,000 variables","Full posterior graph inference for 1,000 variables","Spike-and-slab Bayes hits 1,000-variable mark","Bayesian graphs with exact zeros scale to 1,000 variables"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000998,"raw_usage":{"total_tokens":4070,"prompt_tokens":761,"completion_tokens":3309,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":505,"completion_tokens_details":{"reasoning_tokens":3224}},"tokens_in":505,"tokens_out":3309,"duration_ms":20542,"temperature":1.0,"reasoning_tokens":3224,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T08:40:21.757779+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the local birth-death-swap sampler initialized far from the truth (e.g., at the identity matrix) on an ill-conditioned sparse precision matrix with n=p and modest signal; if the estimated mixing time grows with p or the chain fails to converge, the dimension-free claim is not universal. More directly, estimate the spectral gap of the column-update kernels from simulations under Conditions C0–C4 and check whether it remains bounded below by a constant independent of p.","supporting_citations":[],"review_version":1}