How many graphs?

Topic: Graphical models · more questions on this topic
‹ Conditional independence from a partitioned covariance A tempting wrong turn ›

How many undirected graphs are there on p=5 vertices, and on p=20? Why does this make search impractical without regularisation?

Worked answer (click to show)

Each of the \binom{p}{2} possible edges is present or absent: there are 2^{\binom{p}{2}} undirected graphs. For p=5, 2^{10}=1024. For p=20, 2^{190}\approx 1.6\times 10^{57}. Even allowing for relabelling of the vertices, exhaustive search is impractical. A criterion can still compare a manageable candidate set. With a singular sample covariance the unrestricted positive-definite Gaussian maximum-likelihood estimate fails to exist, although the likelihood at a candidate positive-definite matrix remains defined. An L^1 penalty turns the discrete search into a convex optimisation with a path of solutions indexed by one parameter \lambda.