BIC And Extended BIC For Graph Selection

Why Graph Selection Needs a Complexity Penalty

A Gaussian graphical model represents conditional independence through the zero pattern of a precision matrix. Choosing a graph is therefore a model-selection problem: a denser graph can fit the observed data at least as well as a sparser graph, but its extra edges can also reflect sampling noise. BIC and extended BIC (EBIC) compare fit with complexity, with EBIC allowing for the fact that high-dimensional graph selection searches a very large collection of possible edge sets.

The scores below apply to Gaussian graph candidates fitted by maximum likelihood. They do not guarantee that a selected graph is correct in every high-dimensional regime. Their use depends on the sampling setting, the candidate models, and the assumptions behind the chosen criterion.

Gaussian Graph Candidates and Their Likelihood

Assume \(X_1,\ldots,X_n\) are independent draws from this model and the mean is known to be zero. Define \(S=n^{-1}\sum_{i=1}^n X_iX_i^\mathsf{T}\). For a positive-definite candidate precision matrix \(\Theta\), the log-likelihood is

For graph \(G\), let \(\hat{\Theta}_G\) maximize this likelihood subject to the zero constraints, assuming a maximizer exists. The maximized log-likelihood is \(\ell_G=\ell(\hat{\Theta}_G)\). Constants common to all candidates do not affect which graph minimizes a score, but keeping them makes the likelihood expression explicit. If the mean is unknown and estimated in every candidate, use the centered sample covariance in place of \(S\) and include the \(p\) mean parameters in \(k_G\); because that addition is the same for every graph, it does not change score differences between these candidates.

Deriving the BIC Penalty

BIC’s parameter-count penalty has a likelihood-based justification in regular, fixed-dimensional model selection. It approximates minus twice the log marginal likelihood, which averages the likelihood over parameter values under a prior. The statement requires regularity; it is not an automatic approximation for every high-dimensional graph problem.

To see the penalty, expand the log-likelihood around its maximum. In a neighborhood of radius of order \(n^{-1/2}\), the quadratic approximation has curvature of order \(n\):

The marginal likelihood integrates this local likelihood against the prior. With \(u=\sqrt{n}\,h\), the \(k\)-dimensional volume element becomes \(dh=n^{-k/2}du\). Continuity of the prior gives \(\pi(\hat{\theta}+h)=\pi(\hat{\theta})+o_p(1)\) locally. The local integral is consequently

The Gaussian integral and the prior density contribute terms of order one to the log marginal likelihood; the shrinking volume contributes \(-\tfrac{k}{2}\log n\). Multiplying the negative log by two yields the stated \(k\log n\) penalty and an \(O_p(1)\) remainder. A Gaussian graph with a fixed edge pattern is a regular model when its constrained maximum is interior and its information is nonsingular. The fixed-dimension condition is important: this derivation alone does not justify BIC when the number of variables or candidate-model complexity grows with \(n\).

Extended BIC and the Number of Candidate Graphs

When there are \(p\) variables, there are \(m=\binom{p}{2}\) possible undirected edges. Even restricting attention to graphs with exactly \(q\) edges leaves \(\binom{m}{q}\) candidate edge sets. BIC’s parameter count charges for the fitted parameters in one candidate; EBIC adds a term reflecting the size of the model collection being searched.

For \(1\leq q\leq m\), the number of edge sets obeys

For the lower bound, write \(\binom{m}{q}=\prod_{j=0}^{q-1}(m-j)/(q-j)\). Each factor is at least \(m/q\), since \(q(m-j)\geq m(q-j)\) is equivalent to \(j(m-q)\geq0\). For the upper bound, use \(\binom{m}{q}\leq m^q/q!\) and \(q!\geq(q/e)^q\), the latter following from \(\log(q!)\geq\int_1^q\log x\,dx=q\log q-q+1\). Thus

Since \(m=p(p-1)/2\) is of order \(p^2\), the added EBIC penalty can be substantial when many candidate edges are considered. For small \(q\) relative to \(p\), its leading dependence on \(p\) is often summarized as approximately \(4\gamma q\log p\), with terms involving \(q\log q\) and constants omitted. The exact combinatorial term should be used when that approximation is not appropriate.

Choosing and Interpreting the Criterion

BIC is motivated by a regular-model approximation to marginal likelihood and is often useful when the candidate collection is modest and the parameter dimension is fixed. In a large graph search, however, the number of edge patterns can grow rapidly. EBIC’s additional term can discourage selecting edges that look favorable only because many possible edges were examined. It makes that search-size adjustment explicit rather than treating every candidate graph as if it had been specified in advance.

The choice of \(\gamma\) controls the extra penalty: increasing \(\gamma\) from zero makes the score more conservative about adding edges. This does not make EBIC universally superior. Its behavior depends on the growth of \(p\), the graph sizes under consideration, signal strength, and the data-generating assumptions. The criterion is a model-selection rule, not a substitute for checking whether the Gaussian graph model is plausible or whether the fitted graph is stable.

Common Pitfall

• Wrong reasoning: “Every graph with \(q\) edges has \(p+q\) parameters, so BIC already accounts for how many different graphs could have been tried.”
• Correction: The term \((p+q)\log n\) counts parameters within a candidate graph. It does not count the \(\binom{\binom{p}{2}}{q}\) distinct edge sets of that size. EBIC adds a term based on this model multiplicity.
• Another caution: Do not treat the approximation \(4\gamma q\log p\) as the exact EBIC term for every \(p\) and \(q\). The exact term is \(2\gamma\log\binom{\binom{p}{2}}{q}\).