Abstract
We study maximum likelihood estimation in Gaussian graphical models from a geometric point of view. An algebraic elimination criterion allows us to find exact lower bounds on the number of observations needed to ensure that the maximum likelihood estimator (MLE) exists with probability one. This is applied to bipartite graphs, grids and colored graphs. We also study the ML degree, and we present the first instance of a graph for which the MLE exists with probability one, even when the number of observations equals the treewidth.
Introduction
In modern statistics, particularly in fields like genomics, researchers frequently encounter high-dimensional data where the number of variables $p$ significantly exceeds the number of observations $n$. Gaussian Graphical Models (GGMs) provide a robust framework for representing dependencies between these variables using graphs. A critical question in this context is the existence of the Maximum Likelihood Estimator (MLE). When $p > n$, the sample covariance matrix is singular, yet if the underlying graph is sufficiently sparse, the MLE may still exist. This paper explores the exact lower bounds for $n$ required for MLE existence using the tools of algebraic geometry.
The Geometric Framework of MLE Existence
The problem of MLE existence can be framed as a positive definite matrix completion problem. Geometrically, the MLE exists if and only if the sufficient statistics—the observed entries of the sample covariance matrix—lie within the interior of a specific convex cone.
As shown in Figure 1, the concentration matrices $K$ reside in a cone $\mathcal{K}_G$ defined by the graph $G$. The mapping $\pi_G$ relates the sample covariance $S$ to the sufficient statistics $S_G$ in the cone $\mathcal{C}_G$. The MLE $\hat{\Sigma}$ exists if the data $S$ can be "completed" to a positive definite matrix that satisfies the constraints imposed by the graph.
Breaking the Treewidth Bound
A long-standing heuristic in the field suggested that the MLE exists with probability one if $n$ is at least the size of the largest clique in a chordal cover of the graph (i.e., treewidth + 1). This paper provides a significant counterexample: for a $3 \times 3$ grid, which has a treewidth of 3, the author proves that $n=3$ observations are sufficient for the MLE to exist with probability one, rather than the expected $n=4$.
This discovery was made possible by an Algebraic Elimination Criterion. By examining elimination ideals generated by $(n+1) \times (n+1)$ minors of a symbolic matrix, the author can determine the probability of existence. For small graphs, these computations were performed using Macaulay2. For larger or more complex cases where algebraic methods are memory-intensive, convex optimization simulations using cvx were employed to estimate existence probabilities.
Colored Models and Symmetry
The paper also extends these results to "colored" Gaussian graphical models (RCON models), where symmetries are imposed on the edges or vertices. These symmetries can further reduce the number of observations needed for MLE existence.
In Figure 4, we see how a graph with specific edge symmetries results in a concentration matrix $K$ where multiple entries share the same parameter $\lambda_i$. For some colored 4-cycles, the MLE can exist even with a single observation ($n=1$), a stark contrast to uncolored models. The paper utilizes classic datasets like Frets’s Heads (1921) to demonstrate how such symmetries in head dimensions of siblings affect model estimation.
Key Results and Complexity
The study provides a detailed taxonomy of MLE existence for small non-chordal graphs and bipartite graphs. For bipartite graphs $K_{2,m}$, the MLE exists with probability one if $n \ge 3$. For $n=2$, existence is not guaranteed and depends on the specific geometric orientation of the data vectors.
Furthermore, the paper investigates the ML degree, which represents the algebraic complexity of finding the MLE (the number of critical points of the likelihood function). For $K_{2,m}$, the ML degree grows linearly ($2m+1$) with the number of variables. This stands in contrast to cycles, where the complexity is conjectured to grow exponentially, highlighting how graph structure dictates the computational feasibility of likelihood estimation.
Conclusion and Future Directions
While this work provides sharp bounds for small and structured graphs, several challenges remain. The primary algebraic method—Groebner basis computation—is extremely memory-intensive and does not scale easily to very large graphs. Additionally, the asymptotic behavior of the minimum $n$ as graph size (e.g., in a grid or cycle) tends to infinity remains an open question. Finally, the case of $n=2$ is particularly subtle, as existence often depends on the specific configuration of the data rather than just the graph structure, leaving a general necessary and sufficient condition as a target for future research.
Summary updated