Worked Example: Recovering A Sparse Chain And Hub Graph

From a Precision Estimate to a Graph

A sparse Gaussian graphical model represents conditional relationships among variables as edges in an undirected graph. A chain and a hub can have similar numbers of edges but very different structures: a chain spreads its connections along a path, while a hub concentrates many connections at one vertex. Recovering the correct edge set therefore matters not only for counting errors but also for understanding the resulting topology.

For a $p$-dimensional Gaussian random vector $X$ with mean $\mu$ and positive-definite covariance matrix $\Sigma$, write $\Theta=\Sigma^{-1}$ for its precision matrix. A zero in an off-diagonal position of $\Theta$ represents conditional independence, not necessarily marginal independence. In a fitted model, the nonzero off-diagonal entries of the estimated precision matrix determine the estimated graph.

Definition: The Gaussian graphical model associated with a positive-definite precision matrix $\Theta$ has vertices $1,\ldots,p$ and edge set $$ E(\Theta)=\{\{i,j\}:1\leq i<j\leq p,\ \Theta_{ij}\neq 0\}. $$ For an estimated precision matrix $\hat{\Theta}$, the estimated edge set is $\hat{E}=E(\hat{\Theta})$. The restriction $i<j$ counts each undirected edge once.

In the examples, the fitted matrices are illustrative outputs from regularized Gaussian graphical-model fits to simulated Gaussian data. Their diagonal entries and nonzero patterns are displayed so that the graph recovery calculations can be checked directly. They are not claims that every simulated sample, or every tuning choice, produces the same fit. Positive definiteness is checked explicitly; edge recovery is evaluated by comparing supports, not by comparing matrix entries alone.

Why Precision Zeros Encode Conditional Independence

The link between precision matrices and graph edges is specific to the multivariate Gaussian distribution. Here is the conditional-independence statement that justifies the graph definition.

Theorem: Suppose $X\sim N_p(\mu,\Sigma)$, where $\Sigma$ is positive definite, and let $\Theta=\Sigma^{-1}$. For distinct indices $i$ and $j$, $$ X_i\perp X_j\mid X_{\{1,\ldots,p\}\setminus\{i,j\}} \quad\Longleftrightarrow\quad \Theta_{ij}=0. $$

Proof. Fix the values of all coordinates except $i$ and $j$. In the Gaussian density, collect the terms involving $x_i$ and $x_j$. Up to a factor that does not depend on these two coordinates, their conditional density has the form $$ \exp\left\{-\frac{1}{2} \begin{pmatrix}x_i&x_j\end{pmatrix} \begin{pmatrix}\Theta_{ii}&\Theta_{ij}\\\Theta_{ij}&\Theta_{jj}\end{pmatrix} \begin{pmatrix}x_i\\x_j\end{pmatrix} +\text{terms linear in }x_i,x_j\right\}. $$ The $2\times2$ matrix displayed here is positive definite: it is a principal submatrix of the positive-definite matrix $\Theta$. If $\Theta_{ij}=0$, the quadratic term has no product $x_i x_j$, so the conditional density factors into a function of $x_i$ times a function of $x_j$; the two coordinates are conditionally independent. Conversely, if they are conditionally independent, their positive conditional density factors into separate functions of $x_i$ and $x_j$. The mixed derivative of its log density with respect to $x_i$ and $x_j$ must then be zero. From the displayed Gaussian kernel, that derivative is $-\Theta_{ij}$, so $\Theta_{ij}=0$. This proves both directions. $\square$

Worked Example: A Five-Vertex Chain

Worked Example: Recovering a Chain

Let $X\sim N_5(0,\Sigma)$, with true precision matrix $$ \Theta= \begin{pmatrix} 2&-0.4&0&0&0\\ -0.4&2&-0.4&0&0\\ 0&-0.4&2&-0.4&0\\ 0&0&-0.4&2&-0.4\\ 0&0&0&-0.4&2 \end{pmatrix}. $$ The true edge set is $E=\{12,23,34,45\}$, where $12$ denotes the undirected edge $\{1,2\}$, and similarly for the other pairs. This is the chain $1-2-3-4-5$.

The matrix is positive definite. It is symmetric, and in every row the diagonal entry is greater than the sum of the absolute off-diagonal entries: the row sums are $0.4,0.8,0.8,0.8,0.4$, each less than $2$. A proof of the diagonal-dominance check appears below.

Suppose a regularized fit to one simulated data set returns $$ \hat{\Theta}= \begin{pmatrix} 2&-0.30&0&0&-0.20\\ -0.30&2&-0.25&0&0\\ 0&-0.25&2&0&0\\ 0&0&0&2&-0.30\\ -0.20&0&0&-0.30&2 \end{pmatrix}. $$ Reading the nonzero off-diagonal entries once each gives $$ \hat{E}=\{12,15,23,45\}. $$ This fit is also positive definite: its largest absolute off-diagonal row sum is $0.55$, which is less than its diagonal entry $2$.

The true and fitted edge sets have three edges in common, $12,23,45$. Thus $12,23,45$ are true positives; $34$ is a false negative; and $15$ is a false positive. There are no true negatives among absent pairs needed for the edge-level precision and recall calculation. The graph has four true edges and four estimated edges, so $$ \text{precision}=\frac{3}{3+1}=\frac{3}{4},\qquad \text{recall}=\frac{3}{3+1}=\frac{3}{4},\qquad F_1=\frac{2(3/4)(3/4)}{3/4+3/4}=\frac{3}{4}. $$ The missed link and added edge change the chain into a differently ordered chain, with path $3-2-1-5-4$. It is still a chain: every vertex has degree at most two. The example shows why the topology must be checked from the actual edge list rather than inferred from a verbal summary of the errors.

Checking Positive Definiteness Before Interpreting a Fit

A precision estimate must be positive definite to serve as the precision matrix of a nonsingular Gaussian model. In the examples, strict diagonal dominance provides a simple sufficient check.

Result: If a real symmetric matrix $A$ satisfies $$ A_{ii}>\sum_{j\neq i}|A_{ij}|\quad\text{for every }i, $$ then $A$ is positive definite.

Proof. For any nonzero vector $x$, symmetry gives $$ x^\mathsf{T}Ax =\sum_i A_{ii}x_i^2+2\sum_{i<j}A_{ij}x_ix_j. $$ Using $2|x_i x_j|\leq x_i^2+x_j^2$, we obtain $$ x^\mathsf{T}Ax \geq \sum_i A_{ii}x_i^2 -\sum_{i<j}|A_{ij}|(x_i^2+x_j^2) =\sum_i\left(A_{ii}-\sum_{j\neq i}|A_{ij}|\right)x_i^2. $$ Every coefficient in the final sum is strictly positive. Since $x\neq0$, at least one $x_i^2>0$, and therefore $x^\mathsf{T}Ax>0$. This is the definition of positive definiteness. $\square$

Worked Example: A Seven-Vertex Hub

Worked Example: Recovering a Hub

Consider a seven-variable Gaussian model with true precision matrix having diagonal entries $3$, entries $\Theta_{1j}=\Theta_{j1}=-0.35$ for $j=2,\ldots,7$, and all other off-diagonal entries zero. Its true edge set is $$ E=\{12,13,14,15,16,17\}. $$ Vertex 1 is the hub, with degree 6; each other vertex has degree 1. The sum of the absolute off-diagonal entries in row 1 is $6(0.35)=2.1<3$. In each other row it is $0.35<3$. The matrix is positive definite by the result above.

Suppose the fitted precision matrix has diagonal entries $3$, hub entries $\hat{\Theta}_{1j}=\hat{\Theta}_{j1}=-0.35$ for $j=2,\ldots,6$, an additional pair $\hat{\Theta}_{23}=\hat{\Theta}_{32}=-0.18$, and all other off-diagonal entries zero. Its estimated edge set is $$ \hat{E}=\{12,13,14,15,16,23\}. $$ Row 1 has absolute off-diagonal sum $5(0.35)=1.75<3$; rows 2 and 3 each have sum $0.35+0.18=0.53<3$; and rows 4 through 7 have sums no greater than $0.35$. The fitted matrix is therefore positive definite.

The five recovered hub edges are true positives. The edge $17$ is a false negative, and $23$ is a false positive. There are six true edges and six estimated edges, so $$ \text{precision}=\frac{5}{6},\qquad \text{recall}=\frac{5}{6},\qquad F_1=\frac{2(5/6)(5/6)}{5/6+5/6}=\frac{5}{6}. $$ Unlike the chain example, the error has changed the degree of the hub: its degree falls from 6 to 5, while vertices 2 and 3 acquire an extra connection. The counts alone do not describe that structural change.

Worked Example: Comparing the Two Recovery Patterns

Worked Example: Edge Scores and Topology

The chain fit has 3 true positives, 1 false positive, and 1 false negative. The hub fit has 5 true positives, 1 false positive, and 1 false negative. For each fit, the number of estimated edges equals the number of true edges, so precision and recall are equal: $3/4$ for the chain and $5/6$ for the hub. The corresponding F1 scores are also $3/4$ and $5/6$.

Both fits make two edge errors in total, one omission and one addition. Yet their graph-level consequences differ. In the chain, the errors reroute the path to $3-2-1-5-4$, preserving the chain topology but changing the vertex order along it. In the hub, omitting $17$ reduces the center's degree, while adding $23$ creates a connection between two peripheral vertices. Thus, even when the number and types of edge errors match, the role of the affected vertices determines how the graph changes.

For a simulation study, report both edge-level scores and a concise description of the recovered structure. For example, the hub fit's recall of $5/6$ says that one of six true links was missed; the degree comparison identifies that the missed link was incident to the central vertex. Those are complementary summaries, not competing ones.

What the Recovery Results Do—and Do Not—Show

The examples separate three questions that are easy to conflate. First, is the fitted matrix a valid positive-definite precision matrix? Second, which off-diagonal entries are selected as nonzero, and what edge set follows? Third, how well does that edge set recover the true graph? A positive-definite estimate answers the first question, not the third. Likewise, a good edge score does not establish that a particular edge has been estimated precisely or that an edge is causally meaningful.

The graph is conditional on the modeled variables. If relevant variables are omitted, the interpretation of the remaining graph can change; an edge in the observed-variable graph should not automatically be read as a direct causal link. Interpret the fitted topology as a conditional-dependence summary under the stated Gaussian model.

Common Mistakes

Counting symmetric matrix entries twice. An undirected edge $\{i,j\}$ is one edge, even though both $\Theta_{ij}$ and $\Theta_{ji}$ appear in the matrix. List only pairs with $i<j$.
Calling a nonzero precision entry a marginal association. The zero pattern encodes conditional independence given the other modeled variables; it does not by itself describe marginal independence.
Assuming an added edge necessarily creates a branch. Check vertex degrees and trace paths. In the chain example, the fitted path is $3-2-1-5-4$, so the result is a differently ordered chain, not a branched tree.
Reporting only one recovery score. Precision and recall distinguish false additions from missed true edges. Counts and a topology description help explain what those errors did to the graph.
Ignoring matrix validity. A sparse pattern alone does not ensure a valid Gaussian precision matrix. Check symmetry and positive definiteness before interpreting it as a fitted Gaussian model.

Key takeaway: Recovering a sparse graph requires translating the fitted precision matrix into an undirected edge set, checking the matrix is valid, and comparing the estimated and true supports. Edge scores quantify errors; the chain or hub topology explains their structural consequences.

Check Your Understanding

Use the definitions and calculations in this tutorial to answer the following questions.

Why is the edge $\{2,5\}$ counted once rather than twice when reading a symmetric precision matrix?
In the chain example, identify the false positive and false negative. What is the fitted path when its vertices are read in order?
For the hub example, how does the false negative affect the degree of vertex 1, and what does the false positive do to vertices 2 and 3?
Explain why positive definiteness of a fitted precision matrix does not imply correct graph recovery.
If a fit has 8 true positives, 2 false positives, and 4 false negatives, calculate its precision and recall.