Nodewise Lasso For Neighborhood Selection

Why Regress Each Variable on the Others?

A Gaussian graphical model represents conditional relationships among variables using the zeros of its precision matrix. Yet directly estimating a large precision matrix can be difficult when the number of variables is substantial relative to the sample size. Neighborhood selection offers a different route: for each variable in turn, regress it on all the remaining variables and use an L1 penalty to encourage a sparse set of predictors. The selected predictors are candidate neighbors in the graph.

The key connection is exact at the population level: in a multivariate Gaussian distribution, the regression coefficient for one variable on another is a scaled precision-matrix entry. This tutorial derives that connection, specifies the nodewise Lasso criterion, and shows how to interpret its support. A fitted support is a data-based candidate, not by itself a guarantee of correct graph recovery.

Definition: Let $X=(X_1,\ldots,X_p)^T\sim N_p(\mu,\Sigma)$, where $\Sigma$ is positive definite, and let $\Omega=\Sigma^{-1}$ be its precision matrix. The Gaussian graph has an undirected edge between distinct nodes $j$ and $k$ when $\Omega_{jk}\ne 0$. The neighborhood of node $j$ is $N(j)=\{k\ne j:\Omega_{jk}\ne 0\}$.

From a Gaussian Conditional Distribution to Regression

Write $Z=X-\mu$. The Gaussian density, up to a factor that does not depend on $z$, is proportional to $\exp(-z^T\Omega z/2)$. To find the conditional distribution of $X_j$ given the other coordinates, collect the terms in the exponent that involve $z_j$. Since $\Omega$ is symmetric, those terms are

-\frac12\Omega_{jj}z_j^2-z_j\sum_{k\ne j}\Omega_{jk}z_k = -\frac12\Omega_{jj}\left(z_j+\frac{1}{\Omega_{jj}}\sum_{k\ne j}\Omega_{jk}z_k\right)^2 +\frac{1}{2\Omega_{jj}}\left(\sum_{k\ne j}\Omega_{jk}z_k\right)^2.

The last term on the right does not depend on $z_j$. The remaining expression is a univariate normal kernel in $z_j$, so its conditional variance is $1/\Omega_{jj}$, and its conditional mean is $-\sum_{k\ne j}(\Omega_{jk}/\Omega_{jj})z_k$. Returning to the original variables gives the regression form below.

Theorem: For $X\sim N_p(\mu,\Sigma)$ with positive-definite $\Sigma$ and $\Omega=\Sigma^{-1}$, the conditional distribution of $X_j$ given $X_{-j}=(X_k:k\ne j)$ is $$ X_j\mid X_{-j}\sim N\left(\mu_j-\sum_{k\ne j}\frac{\Omega_{jk}}{\Omega_{jj}}(X_k-\mu_k),\ \frac{1}{\Omega_{jj}}\right). $$ Consequently, the population regression coefficient of $X_k$ in the regression of $X_j$ on all other variables is $\beta_{jk}=-\Omega_{jk}/\Omega_{jj}$.

To make the regression form explicit, write its conditional mean as $\alpha_j+\sum_{k\ne j}\beta_{jk}X_k$. Then $\beta_{jk}=-\Omega_{jk}/\Omega_{jj}$, and $\alpha_j=\mu_j-\sum_{k\ne j}\beta_{jk}\mu_k$. Because $\Omega_{jj}>0$, multiplying an entry in row $j$ by $-1/\Omega_{jj}$ cannot change whether it is zero. Thus the population regression’s nonzero slopes identify exactly the nonzero off-diagonal entries in row $j$ of $\Omega$.

Corollary: Under the stated Gaussian and positive-definiteness assumptions, the population regression support for node $j$ is $N(j)$: $$ \{k\ne j:\beta_{jk}\ne0\}=\{k\ne j:\Omega_{jk}\ne0\}. $$

This is a statement about population quantities. With a finite sample, regression coefficients must be estimated; when $p$ is large, ordinary least squares may be unstable or undefined. Nodewise Lasso replaces that unpenalized fit with a sparse penalized fit.

The Nodewise Lasso Criterion

Suppose $n$ independent observations of the $p$-vector have been collected. For a particular node $j$, let $y_j\in\mathbb{R}^n$ contain the observed values of variable $j$, and let $X_{-j}$ be the $n$ by $p-1$ matrix whose columns contain the observations of the other variables. For centered data, the nodewise Lasso estimate is any minimizer of

\hat\beta^{(j)} \in \underset{b\in\mathbb{R}^{p-1}}{\operatorname{argmin}} \left\{ \frac{1}{2n}\lVert y_j-X_{-j}b\rVert_2^2 +\lambda_j\lVert b\rVert_1 \right\}, \qquad \lambda_j\ge 0.

Here $\lVert b\rVert_1=\sum_{k\ne j}|b_k|$. An intercept can instead be included and left unpenalized; centering the response and predictors gives the displayed form. The tuning parameter $\lambda_j$ controls the trade-off between squared-error fit and sparsity. If the variables are rescaled, the numerical coefficients and the appropriate penalty scale change, so the chosen scaling convention matters.

For any fitted minimizer, define its regression support by $\hat S_j=\{k\ne j:\hat\beta_{jk}\ne0\}$. The population identity motivates interpreting members of $\hat S_j$ as candidate neighbors of $j$. The L1 term encourages coefficients to be exactly zero, but it does not ensure that every selected coefficient corresponds to a true edge or that every true edge is selected.

Result: For the nodewise objective with $\lambda_j>0$, a coefficient vector $b$ minimizes the criterion if and only if, for every predictor column $x_k$, $$ \frac{x_k^T(y_j-X_{-j}b)}{n}=\lambda_j s_k, \qquad s_k= \begin{cases} \operatorname{sign}(b_k),&b_k\ne0,\\ \text{a number in }[-1,1],&b_k=0. \end{cases} $$

To verify this characterization, the squared-error term is differentiable and has derivative with respect to $b_k$ equal to $-x_k^T(y_j-X_{-j}b)/n$. The subgradient of $|b_k|$ is $\operatorname{sign}(b_k)$ when $b_k\ne0$, and the interval $[-1,1]$ when $b_k=0$. The objective is convex, so a point minimizes it exactly when zero belongs to its subgradient. Combining these coordinate conditions gives the displayed equations. In particular, a zero fitted coefficient requires $\left|x_k^T(y_j-X_{-j}b)/n\right|\le\lambda_j$: the residual’s correlation with that predictor must not exceed the penalty threshold. $\square$

Worked Examples

Worked Example: Reading Neighborhoods from a Precision Matrix

Suppose $X\sim N_3(0,\Sigma)$ has precision matrix $$ \Omega= \begin{pmatrix} 2&-0.8&0\\ -0.8&2&-0.6\\ 0&-0.6&1.5 \end{pmatrix}. $$ First check that this is a valid positive-definite precision matrix. Its leading principal minors are $2$, $2(2)-0.8^2=3.36$, and $2(2\cdot1.5-0.6^2)-0.8(0.8\cdot1.5)=5.28-0.96=4.32$. All are positive, so the matrix is positive definite.

For node 1, the conditional regression coefficients are $\beta_{12}=-(-0.8)/2=0.4$ and $\beta_{13}=-0/2=0$. Its population neighborhood is therefore $\{2\}$.

For node 2, the coefficients are $\beta_{21}=0.8/2=0.4$ and $\beta_{23}=0.6/2=0.3$, so its neighborhood is $\{1,3\}$. For node 3, they are $\beta_{31}=0/1.5=0$ and $\beta_{32}=0.6/1.5=0.4$, giving neighborhood $\{2\}$. The nonzero population slopes correspond to the two nonzero off-diagonal pairs, $(1,2)$ and $(2,3)$.

Worked Example: Conditional Independence Is Not Zero Marginal Covariance

Use the same precision matrix. Since $\Omega_{13}=0$, the Gaussian graph has no edge between nodes 1 and 3, and their conditional regression coefficient is $\beta_{13}=0$. For a Gaussian vector, this means $X_1$ and $X_3$ are conditionally independent given $X_2$.

That zero does not imply zero marginal covariance. To check, the $(1,3)$ entry of $\Sigma=\Omega^{-1}$ is the $(3,1)$ cofactor of $\Omega$, divided by its determinant. The minor obtained by deleting row 3 and column 1 is $\begin{pmatrix}-0.8&0\\2&-0.6\end{pmatrix}$, whose determinant is $0.48$; the cofactor sign is positive. The determinant of $\Omega$ is $4.32$, as calculated above. Hence $\operatorname{Cov}(X_1,X_3)=0.48/4.32=1/9\ne0$.

Thus a regression of $X_1$ on $X_3$ alone can show an association even though the full conditional regression coefficient for $X_3$ in the regression of $X_1$ on both $X_2$ and $X_3$ is zero. Neighborhood selection concerns the latter, conditional relationship.

Worked Example: A Nodewise Lasso Fit with an Orthogonal Design

Consider $n=5$ centered observations on four variables, and fit variable 4 using variables 1, 2, and 3. Define four centered, orthonormal vectors in $\mathbb{R}^5$: $u_1=(1,-1,0,0,0)^T/\sqrt2$, $u_2=(1,1,-2,0,0)^T/\sqrt6$, $u_3=(1,1,1,-3,0)^T/\sqrt{12}$, and $u_4=(1,1,1,1,-4)^T/\sqrt{20}$. Their entries each sum to zero, and direct inner products give $u_r^Tu_s=1$ if $r=s$ and $0$ otherwise.

Set $x_k=\sqrt5u_k$ for $k=1,2,3$, and $y_4=\sqrt5(0.8u_1+0.35u_2+0.1u_3+0.5u_4)$. Then $x_k^Tx_l/5$ equals 1 when $k=l$ and 0 otherwise. Also, $x_k^Ty_4/5$ is respectively $0.8$, $0.35$, and $0.1$. The component $0.5\sqrt5u_4$ of $y_4$ is orthogonal to all three predictors, so it contributes only a constant to the objective.

Take $\lambda_4=0.2$. Because the predictors are orthogonal with squared norms $5$, the objective’s terms depending on $b$ separate: $$ \frac{1}{10}\lVert y_4-X_{-4}b\rVert_2^2+0.2\sum_{k=1}^3|b_k| =\text{constant}+\sum_{k=1}^3\left\{\frac12(b_k-c_k)^2+0.2|b_k|\right\}, $$ where $(c_1,c_2,c_3)=(0.8,0.35,0.1)$. For a positive $c_k$, the minimizing coefficient is $c_k-0.2$ if $c_k>0.2$, and zero if $c_k\le0.2$, as follows by setting the derivative to zero on $b_k>0$ and checking the subgradient condition at zero. Therefore $\hat\beta_{41}=0.6$, $\hat\beta_{42}=0.15$, and $\hat\beta_{43}=0$. This fit selects variables 1 and 2 as candidate neighbors of variable 4. It illustrates how the penalty can set a small association to zero; it does not establish whether that candidate support equals the true population neighborhood.

Interpretation and Common Pitfalls

Nodewise Lasso is useful because it turns a multivariate graph question into a collection of regression problems. Each regression uses one variable as the response and the remaining variables as predictors. This can make sparse estimation feasible in settings where an unpenalized regression with many predictors is unstable. The population regression identity explains why these separate fits can provide information about precision-matrix neighborhoods.

Using marginal association as the edge criterion. A nonzero marginal covariance need not imply a graph edge. The relevant population coefficient comes from conditioning on all the other variables.
Dropping the minus sign or the denominator. The coefficient is $-\Omega_{jk}/\Omega_{jj}$, not $\Omega_{jk}$. Its sign and magnitude depend on the diagonal entry, although its zero pattern does not.
Treating a fitted support as a proven graph. The exact support identity is a population result. A finite-sample Lasso support is an estimate and can include false selections or omit true neighbors.
Ignoring scale. Rescaling predictors changes regression coefficient magnitudes and can affect penalized selection. Use a consistent scaling convention and penalty calibration.

Each nodewise regression gives a directed list of selected predictors because it has a designated response. The underlying Gaussian graph, however, is undirected. The precise issue of combining lists from different nodewise fits is a separate question; here the central point is that each fit supplies candidates through its own conditional regression.

Check Your Understanding

Use the definitions and derivations above to answer these questions.

For a Gaussian vector with precision matrix $\Omega$, write the conditional regression coefficient of $X_k$ in the regression for $X_j$.
Why does multiplying $\Omega_{jk}$ by $-1/\Omega_{jj}$ preserve whether the coefficient is zero?
What condition does the nodewise Lasso subgradient impose on the residual correlation for a predictor whose fitted coefficient is zero?
Can $X_j$ and $X_k$ have nonzero marginal covariance when $\Omega_{jk}=0$? Explain the role of conditioning.
Why should a nonzero coefficient in a finite-sample nodewise Lasso fit be called a candidate edge rather than a guaranteed edge?