Source-linked AI summary
Extended Bayesian Information Criteria for Gaussian Graphical Models
Rina Foygel, Mathias Drton
TL;DR
The paper addresses consistent graph selection for sparse Gaussian graphical models when p, n, and the true model size can grow. It develops and analyzes an extended BIC, then evaluates it with graphical lasso preselection; positive γ improves false discovery control over classical BIC and cross-validation while retaining useful positive-selection performance.
Problem
The paper asks how to consistently select sparse Gaussian graphical structures when the number of variables and nonzero parameters grow with sample size.
Method
The paper analyzes an extended BIC over restricted decomposable model spaces and uses graphical lasso to preselect candidate models for simulation-based evaluation.
Results
Positive γ gives strong false discovery rate improvements over classical BIC and cross-validation, with comparable positive selection rate for the chain graph.
Takeaways & Limitations
EBIC with positive γ is practically useful for tuning the graphical lasso in settings where p and q scale with n.
Takeaways & Limitations
The theory assumes i.i.d. Gaussian observations with a positive definite true precision matrix and imposes explicit growth and regularity conditions.
Abstract
from arXiv · showhide
Gaussian graphical models with sparsity in the inverse covariance matrix are of significant interest in many modern applications. For the problem of recovering the graphical structure, information criteria provide useful optimization objectives for algorithms searching through sets of graphs or for selection of tuning parameters of other methods such as the graphical lasso, which is a likelihood penalization technique. In this paper we establish the consistency of an extended Bayesian information criterion for Gaussian graphical models in a scenario where both the number of variables p and the sample size n grow. Compared to earlier work on the regression case, our treatment allows for growth in the number of non-zero parameters in the true model, which is necessary in order to cover connected graphs. We demonstrate the performance of this criterion on simulated data when used in conjunction with the graphical lasso, and verify that the criterion indeed performs better than either cross-validation or the ordinary Bayesian information criterion when p and the number of non-zero parameters q both scale with n.
1 Introduction
The paper studies structure learning in sparse Gaussian graphical models using an extended Bayesian information criterion (EBIC). It establishes consistency when dimensionality and model complexity grow, and evaluates EBIC with graphical lasso preselection.
- 1 Introduction: Gaussian graphical models encode graph structure through zeros in the inverse covariance matrix, making graph recovery a model-selection problem.The graph has an edge between variables whose corresponding inverse-covariance entries may be nonzero.
- 1 Introduction: Information criteria score candidate graphs and can select tuning parameters for methods such as the graphical lasso.The graphical lasso is described as a likelihood-penalization technique.
- 1 Introduction: Positive γ strengthens EBIC penalization of large graphs and supports consistent selection when p grows moderately with n.When γ = 0, EBIC reduces to classical BIC; positive γ provides stronger penalization.
- 1 Introduction: Unlike earlier regression treatments, the analysis allows both the model-size bound q and the true edge count |E0| to grow, covering connected graphs.The paper studies exhaustive search over restricted model spaces containing decomposable models with |E| ≤ q.
- 1 Introduction: Exhaustive search is infeasible for moderate p and q, so the simulations preselect models before scoring them with EBIC.The paper uses graphical lasso to generate a smaller candidate set and reports good results beyond the theoretical assumptions.
2 Consistency of the extended BIC for Gaussian graphical models
The theoretical analysis establishes EBIC consistency for sparse Gaussian graphical models under explicit growth and regularity conditions. Its proof compares true, underfitted, and overfitted decomposable models and shows that EBIC selects the smallest true model with probability tending to one.
- 2.1 Notation and definitions: The model uses a positive definite precision matrix Θ0 supported on diagonal entries and the true edge set E0, with symmetric off-diagonal edge positions.The data are i.i.d. Gaussian with zero mean and precision matrix Θ0.
- 2.1 Notation and definitions: The assumptions allow p, q, and E0 to vary with n while imposing bounds on dimensional growth, conditioning, and signal-related quantities.The conditions include p = O(n^κ), p →∞, and a positive adjusted penalty parameter γ0.
- 2.2 Main result: The main theorem considers all decomposable candidate models with at most q edges and establishes the stated probability limit under the assumptions.The theorem is formulated for model spaces restricted by |E| ≤ q.
- 2.2 Main result: With probability tending to one, EBIC selects the smallest true model E0 when applied to any candidate subset containing E0.This is the paper’s stated consistency conclusion.
- 2.2 Main result: The proof controls underfitted models through likelihood decrease and overfitted decomposable models through likelihood-ratio bounds, then combines both comparisons.The overfitted-model comparison uses the distribution of likelihood ratios for nested decomposable models.
- 2.2 Main result: The resulting comparison shows every candidate model other than E0 has larger EBIC than E0 with probability tending to one.This inequality yields the desired selection result.
3 Simulations
The simulations evaluate EBIC alongside graphical lasso over chain and double-chain graphs as p and n grow. Positive γ generally reduces false discoveries, while finite-sample selection trades positive selection rate against false discovery rate.
- Simulation design: The study applies EBIC with γ ∈ {0, 0.5, 1} to graphical-lasso model paths across chain and double-chain graphs.It varies n from 100 to 800 and uses p ∝ n^κ for κ ∈ {0.5, 0.9, 1, 1.1}.
- Simulation design: The chain and double-chain settings contain graphs with respectively on the order of p and 2p edges.The double chain connects each node to nearby nodes at distances one and two.
- Chain graph: For chain graphs, larger samples recover non-zero coefficients perfectly or nearly perfectly for all γ values, while positive γ yields noticeably lower FDR.The FDR advantage is especially pronounced at higher scaling exponents κ; γ = 0.5 and γ = 1 perform well for moderately large n.
- Double chain graph: For double-chain graphs, PSR declines as γ increases, but positive γ again lowers FDR; with κ ≥ 0.9, BIC0 FDR increases as n and p grow.Cross-validation has higher PSR but extremely high, rapidly increasing FDR, whereas γ = 0.5 has low and decreasing FDR.
- Finite-sample trade-off: Finite samples exhibit a trade-off: lower γ favors higher PSR, whereas higher γ favors lower FDR; γ = 0.5 appears to be a useful compromise.Asymptotically, the stated conditions guarantee consistency, but the best γ in general settings remains open.
4 Discussion
The discussion proposes EBIC for sparse graphical models and reports asymptotic consistency under scaling conditions. Simulations show improved false discovery rates over classical BIC and cross-validation, with signal-strength-dependent effects on positive selection rate.
- The main theorem gives scaling conditions on p, n, the edge bound q, and technical quantities that ensure asymptotic consistency.
- Positive γ substantially improves FDR over classical BIC and cross-validation while producing comparable chain-graph PSR.For double chains with many weaker signals, positive γ yields lower but steadily increasing PSR.
5 Proofs
The proofs establish non-asymptotic and asymptotic consistency of extended BIC under growth of p, n, and the true model size, using concentration bounds and likelihood comparisons.
- Non-asymptotic results: The non-asymptotic proof treats n, p, and q as fixed and derives explicit probability bounds for exact recovery of E0.The approach provides finite-sample guarantees before translating them to the asymptotic setting.
- Proof tools: Chi-square tail bounds and a sample-correlation distributional result control likelihood fluctuations across candidate edges.These lemmas support the uniform probability bounds used in the main theorems.
- Main theorems: Theorem 3 bounds likelihood behavior for models that do not contain the true edge set, while Theorem 4 controls models strictly larger than E0.The two cases are combined through a union bound over admissible models.
- Consistency: Under the stated assumptions, extended BIC selects the smallest true model E0 among decomposable models with at most q edges.The result holds with an explicit high-probability guarantee and extends to the asymptotic regime when the scaling conditions persist.
A Appendix
The appendix supplies concentration-inequality details underlying the theorem proofs and clarifies a lower-sample-size requirement for chi-square left-tail control.
- Proof details: The appendix proves the chi-square tail lemma used in the main arguments, treating even and odd degrees of freedom separately.The derivation uses identities for chi-square densities and bounds involving the gamma function.
- Proof details: The sample-size condition n ≥ 4λ^-2 + 1 is needed for the stated chi-square left-tail bound.When the target interval includes the chi-square mode, an exponentially small tail probability cannot generally be obtained.
- Theorem verification: The appendix fills in the bounds used by Theorems 3 and 4, including uniform control over edges and likelihood differences.These calculations yield the probability bounds required for the non-asymptotic consistency theorem.