Gaussian Graphical Model

1. Multivariate Gaussian Distribution

Definition 1.1    $X_V$ has a multivariate Gaussian distribution with parameters $\mu$ and $\mathrm{\Sigma }$ if the joint density is $$f(x_V;\mu ,\mathrm{\Sigma })=\frac{1}{(2\pi {)}^{p/2}|\mathrm{\Sigma }{|}^{1/2}}\exp [-\frac{1}{2}(x_V-\mu {)}^{\mathrm{\top }}{\mathrm{\Sigma }}^{-1}(x_V-\mu )],$$ where $x_V\in {\mathbb{R}}^p$. Note that we usually consider $$\ln f(x_V;\mu ,\mathrm{\Sigma })=C-\frac{1}{2}(x_V-\mu {)}^{\mathrm{\top }}{\mathrm{\Sigma }}^{-1}(x_V-\mu ).$$ or $$\ln f(x_V;\mu ,K)=C-\frac{1}{2}(x_V-\mu {)}^{\mathrm{\top }}K(x_V-\mu ).$$

Theorem 1.1    Let $X_V$ has a multivariate Gaussian distribution with concentration matrix $K={\mathrm{\Sigma }}^{-1}$. Then $X_i\perp \perp X_j\mid X_{V-\{i,j\}}$ iff $k_{ij}=0$, where $k_{ij}$ is the corresponding entry in the concentration matrix.

2. Gaussian Graphical Model (GGM)

If $M$ is a matrix whose rows and columns are indexed by $A\subseteq V$, we write $\{M{\}}_{A,A}$ to indicate the matrix indexed by $V$ (i.e., it has $|V|$ rows and columns) whose $A,A$-entries are $M$ and with zeroes elsewhere. For example, if $|V|=3$ then $$M=\left[\begin{array}{cc}a& b\\ b& c\end{array}\right]\text{and}\{M{\}}_{12,12}=\left[\begin{array}{ccc}a& b& 0\\ b& c& 0\\ 0& 0& 0\end{array}\right],$$ where $12$ is used as an abbreviation for $\{1,2\}$ in the subscript.

Lemma 2.1    Let $\mathcal{G}$ be a graph with decomposition $(A,S,B)$, and $X_V\sim {\mathcal{N}}_p(0,\mathrm{\Sigma })$. Then $p(x_V)$ is Markov w.r.t. $\mathcal{G}$ iff $${\mathrm{\Sigma }}^{-1}=\{({\mathrm{\Sigma }}_{AS,AS}{)}^{-1}{\}}_{AS,AS}+\{({\mathrm{\Sigma }}_{BS,BS}{)}^{-1}{\}}_{BS,BS}-\{({\mathrm{\Sigma }}_{S,S}{)}^{-1}{\}}_{S,S},$$ and ${\mathrm{\Sigma }}_{AS,AS}$ and ${\mathrm{\Sigma }}_{BS,BS}$ are Markov w.r.t. ${\mathcal{G}}_{A\cup S}$ and ${\mathcal{G}}_{B\cup S}$ respectively.

Proof. Since $(A,S,B)$ is a decomposition and $p(x_V)$ is Markov, then $X_A\perp \perp X_B\mid X_S$, which implies for all $x_V\in {\mathbb{R}}^{|V|}$, $$p(x_V)p(x_S)=p(x_A,x_S)p(x_B,x_S).$$ Then $$x_V^{\mathrm{\top }}{\mathrm{\Sigma }}^{-1}{x}_V+x_S^{\mathrm{\top }}({\mathrm{\Sigma }}_{S,S}{)}^{-1}{x}_S=x_{AS}^{\mathrm{\top }}({\mathrm{\Sigma }}_{AS,AS}{)}^{-1}{x}_{AS}+x_{BS}^{\mathrm{\top }}({\mathrm{\Sigma }}_{BS,BS}{)}^{-1}{x}_{BS},$$ i.e., $$x_V^{\mathrm{\top }}{\mathrm{\Sigma }}^{-1}{x}_V+x_V^{\mathrm{\top }}\{({\mathrm{\Sigma }}_{S,S}{)}^{-1}{\}}_{S,S}{x}_V=x_V^{\mathrm{\top }}\{({\mathrm{\Sigma }}_{AS,AS}{)}^{-1}{\}}_{AS,AS}{x}_V+x_V^{\mathrm{\top }}\{({\mathrm{\Sigma }}_{BS,BS}{)}^{-1}{\}}_{BS,BS}{x}_V.$$ Therefore, $${\mathrm{\Sigma }}^{-1}=\{({\mathrm{\Sigma }}_{AS,AS}{)}^{-1}{\}}_{AS,AS}+\{({\mathrm{\Sigma }}_{BS,BS}{)}^{-1}{\}}_{BS,BS}-\{({\mathrm{\Sigma }}_{S,S}{)}^{-1}{\}}_{S,S}.$$

The converse holds similarly.

$◻$

3. Maximum Likelihood Estimation

Let $X_V^{(1)},\dots ,X_V^{(n)}\stackrel{\text{i.i.d.}}{\sim }{\mathcal{N}}_p(0,\mathrm{\Sigma })$. The sufficient statistic for $\mathrm{\Sigma }$ is the sample covariance matrix $$W=\frac{1}{n}\sum _{i=1}^n{X}_V^{(i)}(X_V^{(i)}{)}^{\mathrm{\top }}.$$ In addition, $\hat{\mathrm{\Sigma }}=W$ is the MLE for $\mathrm{\Sigma }$ under the unrestricted model (i.e., when all edges are present in the graph). Let ${\hat{\mathrm{\Sigma }}}^{\mathcal{G}}$ denote the MLE for $\mathrm{\Sigma }$ under the restriction that the distribution satisfies the Markov property for $\mathcal{G}$, and ${\hat{K}}^{\mathcal{G}}$ denote the inverse of ${\hat{\mathrm{\Sigma }}}^{\mathcal{G}}$.

For a decomposable graph $\mathcal{G}$ with cliques $C_1,\dots ,C_k$, the MLE can be written in the form $$({\hat{\mathrm{\Sigma }}}^{\mathcal{G}}{)}^{-1}=\sum _{i=1}^k\{(W_{C_i,C_i}{)}^{-1}{\}}_{C_i,C_i}-\sum _{i=2}^k\{(W_{S_i,S_i}{)}^{-1}{\}}_{S_i,S_i}.$$

Example 3.1    Whittaker (1990) analyzed data on five maths test results administered to 88 students, in analysis, algebra, vectors, mechanics and statistics. Some of the entries in the concentration matrix are quite small, suggesting that conditional independence holds. We want to fit a graphical model and check if it gives an excellent fit.

Figure 1: A graph for the maths test data.

By computation, ${\hat{\mathrm{\Sigma }}}^{\mathcal{G}}$ is:

	Mechanics	Vectors	Algebra	Analysis	Statistics
Mechanics	$0.00524$	$-0.00244$	$-0.00287$	$0$	$0$
Vectors	$-0.00244$	$0.01035$	$-0.00561$	$0$	$0$
Algebra	$-0.00287$	$-0.00561$	$0.02849$	$-0.00755$	$-0.00493$
Analysis	$0$	$0$	$-0.00755$	$0.00982$	$-0.00204$
Statistics	$0$	$0$	$-0.00493$	$-0.00204$	$0.00644$

We carry out a likelihood ratio test to see whether this model is a good fit to the data. We want to test $$H_0:\text{Restricted model}\text{against}{H}_1:\text{Unrestricted model}.$$ The test statistic is $$2(l(\hat{\mathrm{\Sigma }})-l({\hat{\mathrm{\Sigma }}}^{\mathcal{G}}))=0.8958244\to {\chi }_{(4)}^2$$ and the $p$-value is $0.925>0.05$, i.e., the model is a good fit.

Here is the relevant code in R:

library(ggm)
data(marks)

# MLE of the covariance matrix under the unrestricted model.
S = cov(marks) 

# Concentration matrix under the restriction.
K = matrix(0, 5, 5)
K[1:3, 1:3] = solve(S[1:3, 1:3])
K[3:5, 3:5] = K[3:5, 3:5] + solve(S[3:5, 3:5])
K[3, 3] = K[3, 3] - 1 / S[3, 3]

# MLE of the covariance matrix under the restriction.
Simga_hat = solve(K)

# Test statistic.
tr = function(x) sum(diag(x))
n = nrow(marks)
test_sta = - n * ((log(det(S)) - log(det(Simga_hat))) 
	   - tr(S %*% (solve(S) - solve(Simga_hat))))
p = pchisq(q=test_sta, df=4, lower.tail=FALSE)