8  Network Learning

Chapter Aim

Chapter 08 is about learning a network from high-dimensional biological data. In Chapter 09, networks are treated as given objects for downstream analysis. Here the graph itself is estimated from a data matrix, and every edge is therefore a statistical claim.

The rows of the network-learning input are observations and the columns are features. In a gene network, the \(p\) nodes are genes. In a metabolite network, the nodes are metabolites. In a microbiome association network, the nodes may be taxa or sequence variants. We write the graph as

\[\begin{equation} G=(V,E), \qquad V=\{1,\ldots,p\}. \label{eq:ch08-feature-graph} \end{equation}\]

The adjacency matrix is

\[\begin{equation} A\in\{0,1\}^{p\times p}, \qquad A_{j\ell}=1 \quad \Longleftrightarrow \quad (j,\ell)\in E. \label{eq:ch08-adjacency-matrix} \end{equation}\]

For the undirected graphs considered in this chapter,

\[\begin{equation} A=A^\top, \qquad A_{jj}=0. \label{eq:ch08-undirected-adjacency} \end{equation}\]

The main question is how to estimate \(A\) from \(X\). The key message is that simple pairwise correlations do not separate direct from indirect associations. Sparse regression and sparse inverse covariance estimation try to estimate conditional dependence structure instead. Node-wise lasso estimates each node from all other nodes. Graphical lasso estimates the whole precision matrix at once. StARS then gives a stability-based way to choose the regularization level. Methods such as SPIEC-EASI combine compositional preprocessing with sparse graphical-model estimation for microbiome data (Kurtz et al. 2015).

TipNotation convention

Notation follows the shared convention in the notation chapter. Vectors are columns by default, row vectors are written with transposes, and dimensions should be checked whenever matrices are multiplied, transformed, modeled, or decomposed.

NoteMain external references

For graph language and graph encodings, see MSMB Networks and Trees, especially the graph foundations (MSMB Networks Graphs). The statistical network-learning methods in this chapter are based mainly on node-wise lasso for high-dimensional graphs (Meinshausen and Bühlmann 2006), sparse inverse covariance estimation with graphical lasso (Friedman et al. 2008; Yuan and Lin 2007), stability selection for graphical models via StARS (Liu et al. 2010), and compositional microbial network inference via SPIEC-EASI (Kurtz et al. 2015). Practical computation of SPIEC-EASI with MB and graphical-lasso variants, StARS-style stability selection through pulsar, and SparCC comparison is included in Exercise Sheet 6, Task 1 (Exercise Sheet 06 2026). NetCoMi network construction and analysis is then treated as a separate follow-up task in Exercise Sheet 6, Task 2. The sparse-regression and stability-selection machinery behind node-wise lasso is prepared by the high-dimensional regression exercises in Exercise Sheet 05 (Exercise Sheet 05 2026).

Learning Goals

After this chapter, students should be able to distinguish a known biological network from an inferred statistical network, define an adjacency matrix for a feature graph, explain why correlation networks can contain indirect edges, write down the Gaussian graphical model, connect zeros in the precision matrix to conditional independence, compute partial correlations from the precision matrix, formulate node-wise lasso regression, symmetrize node-wise edge estimates, formulate the graphical lasso objective, explain how StARS selects a regularization parameter using subsampling stability, and explain why microbiome network inference needs normalization or log-ratio preprocessing before sparse graphical modeling.

8.1 What Does An Edge Mean?

A learned network is not automatically a mechanistic interaction map. An edge may mean correlation, conditional dependence, predictive association, co-occurrence after preprocessing, or agreement with a chosen model. These meanings are different.

For feature vectors \(x_{\cdot j}\) and \(x_{\cdot \ell}\), a pairwise association network might define an edge by thresholding a sample correlation:

\[\begin{equation} A_{j\ell}^{\mathrm{cor}} = \mathbf{1} \left\{ |\hat{\rho}_{j\ell}|\geq \tau \right\}, \qquad j\neq \ell. \label{eq:ch08-correlation-threshold-network} \end{equation}\]

This is easy to compute, but a correlation edge can be indirect. If gene \(1\) regulates gene \(2\) and gene \(2\) regulates gene \(3\), then genes \(1\) and \(3\) may be correlated even if there is no direct statistical dependence after conditioning on gene \(2\). The purpose of graphical models is to move from marginal association toward conditional association.

The preprocessing step matters before any network is learned. Raw count data

\[\begin{equation} C\in\mathbb{N}_0^{n\times p} \label{eq:ch08-raw-count-matrix} \end{equation}\]

are usually not appropriate inputs for Gaussian graphical modeling. One typically first constructs a transformed matrix \(X\), for example using variance-stabilized values, residuals, or log-ratio coordinates:

\[\begin{equation} C \longmapsto X. \label{eq:ch08-counts-to-network-input} \end{equation}\]

The network is only interpretable relative to this map. A graph learned from CLR-transformed compositions is a graph in log-ratio geometry. A graph learned from residuals is a graph after removing the fitted mean structure. A graph learned from raw proportions is usually hard to interpret because sequencing depth and compositional constraints can induce artificial associations.

The distinction between an embedding and the underlying graph is important computationally as well. In graph-based single-cell clustering, the KNN or SNN adjacency matrix is the object being clustered; the two-dimensional layout is only a display of that object. The construction and inspection of such an SNN graph is worked through in Exercise Sheet 04 (Exercise Sheet 04 2026). The microbial-network counterpart, where the graph is an inferred association network rather than a clustering graph, is computed with SPIEC-EASI in Exercise Sheet 6, Task 1 (Exercise Sheet 06 2026).

8.2 Gaussian Graphical Models

The cleanest mathematical foundation for this chapter is the Gaussian graphical model. Assume that each row of \(X\) is an independent draw from a multivariate normal distribution:

\[\begin{equation} x_i \sim \mathcal{N}_p(\mu,\Sigma), \qquad i=1,\ldots,n. \label{eq:ch08-gaussian-row-model} \end{equation}\]

Here \(x_i\in\mathbb{R}^{p}\) is the column-vector version of row \(i\), \(\mu\in\mathbb{R}^{p}\) is the mean vector, and \(\Sigma\in\mathbb{R}^{p\times p}\) is the covariance matrix. The precision matrix is

\[\begin{equation} \Omega = \Sigma^{-1}. \label{eq:ch08-precision-matrix} \end{equation}\]

In a Gaussian graphical model, missing edges correspond to zeros in the precision matrix:

\[\begin{equation} A_{j\ell}=0 \quad \Longleftrightarrow \quad \Omega_{j\ell}=0, \qquad j\neq \ell. \label{eq:ch08-edge-precision-zero} \end{equation}\]

The statistical meaning is conditional independence:

\[\begin{equation} \Omega_{j\ell}=0 \quad \Longleftrightarrow \quad X_j\perp X_\ell \mid X_{-(j,\ell)}. \label{eq:ch08-gaussian-conditional-independence} \end{equation}\]

Here \(X_j\) and \(X_\ell\) are random feature coordinates, and \(X_{-(j,\ell)}\) denotes all remaining coordinates. This is why precision-based graphs are often more useful than correlation graphs: the edge asks whether two features remain associated after adjusting for the rest of the measured system.

The partial correlation between features \(j\) and \(\ell\) is computed from the precision matrix as

\[\begin{equation} \rho_{j\ell\mid -(j,\ell)} = - \frac{\Omega_{j\ell}} {\sqrt{\Omega_{jj}\Omega_{\ell\ell}}}. \label{eq:ch08-partial-correlation} \end{equation}\]

Thus estimating a Gaussian graphical model can be seen either as estimating a sparse precision matrix or as estimating a sparse partial-correlation network.

8.3 Why Sparsity Is Needed

The sample covariance matrix is

\[\begin{equation} \hat{\Sigma} = \frac{1}{n} \sum_{i=1}^{n} (x_i-\bar{x})(x_i-\bar{x})^\top, \qquad \bar{x} = \frac{1}{n} \sum_{i=1}^{n} x_i. \label{eq:ch08-sample-covariance} \end{equation}\]

If \(p>n\), then \(\hat{\Sigma}\) is singular:

\[\begin{equation} \operatorname{rank}(\hat{\Sigma}) \leq n-1 < p. \label{eq:ch08-sample-covariance-singular} \end{equation}\]

The inverse covariance \(\hat{\Sigma}^{-1}\) does not exist. Even when \(p<n\), the inverse can be unstable if \(p\) is close to \(n\) or if features are strongly correlated. Network learning therefore needs regularization. The biological assumption is often that the conditional-dependence graph is sparse: each feature is directly connected to only a small subset of all possible features.

The number of possible undirected edges is

\[\begin{equation} \binom{p}{2} = \frac{p(p-1)}{2}. \label{eq:ch08-number-possible-edges} \end{equation}\]

Without sparsity, a high-dimensional network can quickly become uninterpretable. With too much sparsity, real dependencies are missed. Network learning is therefore a model-selection problem over the regularization level.

8.4 Node-Wise Lasso Regression

The first sparse route is neighborhood selection by node-wise lasso regression, following the high-dimensional graph-estimation approach of Meinshausen and Bühlmann (Meinshausen and Bühlmann 2006). For node \(j\), use feature \(j\) as a response and all remaining features as predictors:

\[\begin{equation} x_{\cdot j} = X_{-j}\beta^{(j)} + \varepsilon^{(j)}. \label{eq:ch08-nodewise-linear-model} \end{equation}\]

Here \(X_{-j}\in\mathbb{R}^{n\times(p-1)}\) is the analysis matrix with column \(j\) removed, and \(\beta^{(j)}\in\mathbb{R}^{p-1}\) contains the regression coefficients for predicting node \(j\). Node-wise lasso estimates

\[\begin{equation} \hat{\beta}^{(j)}_{\lambda} = \arg\min_{\beta\in\mathbb{R}^{p-1}} \left\{ \frac{1}{2n} \left\| x_{\cdot j} - X_{-j}\beta \right\|_2^2 + \lambda \|\beta\|_1 \right\}. \label{eq:ch08-nodewise-lasso-objective} \end{equation}\]

This is the lasso from Chapter 07, now used locally at each node. The estimated neighborhood of node \(j\) is

\[\begin{equation} \hat{N}_{\lambda}(j) = \left\{ \ell\neq j: \hat{\beta}^{(j)}_{\lambda,\ell}\neq 0 \right\}. \label{eq:ch08-nodewise-neighborhood} \end{equation}\]

Because the regression of \(j\) on \(\ell\) and the regression of \(\ell\) on \(j\) are fit separately, the two directions can disagree. An undirected graph requires symmetrization. The OR rule defines an edge if either regression selects it:

\[\begin{equation} \hat{A}_{j\ell}^{\mathrm{OR}}(\lambda) = \mathbf{1} \left\{ \ell\in\hat{N}_{\lambda}(j) \ \text{or}\ j\in\hat{N}_{\lambda}(\ell) \right\}. \label{eq:ch08-nodewise-or-rule} \end{equation}\]-nodewise-or-rule} \end{equation}

The AND rule defines an edge only if both regressions select it:

\[\begin{equation} \hat{A}_{j\ell}^{\mathrm{AND}}(\lambda) = \mathbf{1} \left\{ \ell\in\hat{N}_{\lambda}(j) \ \text{and}\ j\in\hat{N}_{\lambda}(\ell) \right\}. \label{eq:ch08-nodewise-and-rule} \end{equation}\]-nodewise-and-rule} \end{equation}

The OR rule is more sensitive and usually gives denser graphs. The AND rule is more conservative. The node-wise lasso approach is attractive because it decomposes a large graph-learning problem into \(p\) familiar regression problems (Meinshausen and Bühlmann 2006). Its limitation is that the global object is assembled from local fits; it does not directly estimate one positive-definite precision matrix.

Computationally, each node-wise fit is an ordinary high-dimensional lasso problem with a different response column. The regularization-path and cross-validation mechanics are therefore the same as in sparse regression, while the stability question is now asked for edges rather than for a phenotype-prediction model; the relevant sparse-regression and stability-selection computations are practiced in Exercise Sheet 05, and their network-learning version is applied directly through SPIEC-EASI MB and graphical-lasso fits in Exercise Sheet 6, Task 1 (Exercise Sheet 05 2026; Exercise Sheet 06 2026).

8.5 From Node-Wise Regression To Precision Matrices

The connection between node-wise regression and precision matrices is exact under a Gaussian model. Partition the random vector into coordinate \(j\) and all other coordinates. The conditional mean of \(X_j\) given \(X_{-j}\) is linear:

\[\begin{equation} \mathbb{E}(X_j\mid X_{-j}) = \mu_j + \Sigma_{j,-j} \Sigma_{-j,-j}^{-1} (X_{-j}-\mu_{-j}). \label{eq:ch08-gaussian-conditional-mean} \end{equation}\]

Equivalently, in terms of the precision matrix,

\[\begin{equation} \mathbb{E}(X_j\mid X_{-j}) = \mu_j - \frac{1}{\Omega_{jj}} \sum_{\ell\neq j} \Omega_{j\ell} (X_\ell-\mu_\ell). \label{eq:ch08-conditional-mean-precision} \end{equation}\]

Thus the population regression coefficient of \(X_\ell\) in the regression of \(X_j\) on all other features is

\[\begin{equation} \beta_{\ell}^{(j)} = - \frac{\Omega_{j\ell}}{\Omega_{jj}}, \qquad \ell\neq j. \label{eq:ch08-nodewise-coefficient-precision} \end{equation}\]

Therefore

\[\begin{equation} \beta_{\ell}^{(j)}=0 \quad \Longleftrightarrow \quad \Omega_{j\ell}=0. \label{eq:ch08-nodewise-zero-equivalence} \end{equation}\]

This is why node-wise variable selection can recover a conditional-dependence graph. The lasso is being used not because the response is a phenotype, but because selecting predictors in each node-wise regression selects candidate neighbors.

8.6 Graphical Lasso

The second sparse route estimates the precision matrix directly. If the data are centered, the Gaussian negative log-likelihood for a precision matrix \(\Omega\) is, up to constants,

\[\begin{equation} \operatorname{tr}(\hat{\Sigma}\Omega) - \log\det(\Omega), \qquad \Omega\succ 0. \label{eq:ch08-gaussian-negative-log-likelihood} \end{equation}\]

The graphical lasso adds an \(\ell_1\) penalty to encourage off-diagonal sparsity:

\[\begin{equation} \hat{\Omega}_{\lambda} = \arg\min_{\Omega\succ 0} \left\{ \operatorname{tr}(\hat{\Sigma}\Omega) - \log\det(\Omega) + \lambda \sum_{j\neq \ell} |\Omega_{j\ell}| \right\}. \label{eq:ch08-graphical-lasso-objective} \end{equation}\]

Some implementations penalize all entries, and some penalize only off-diagonal entries. The statistical target for graph structure is the off-diagonal pattern. Once \(\hat{\Omega}_{\lambda}\) has been estimated, the graph is

\[\begin{equation} \hat{A}_{j\ell}(\lambda) = \mathbf{1} \left\{ \hat{\Omega}_{\lambda,j\ell}\neq 0 \right\}, \qquad j\neq \ell. \label{eq:ch08-glasso-adjacency} \end{equation}\]

The fitted partial correlations are

\[\begin{equation} \hat{\rho}_{j\ell\mid -(j,\ell)} = - \frac{\hat{\Omega}_{\lambda,j\ell}} {\sqrt{\hat{\Omega}_{\lambda,jj}\hat{\Omega}_{\lambda,\ell\ell}}}. \label{eq:ch08-glasso-partial-correlation} \end{equation}\]

Graphical lasso estimates one coherent precision matrix and therefore one coherent Gaussian graphical model (Friedman et al. 2008; Yuan and Lin 2007). The regularization parameter \(\lambda\) controls sparsity. Large \(\lambda\) gives a sparse graph; small \(\lambda\) gives a dense graph. The difficult part is choosing \(\lambda\) in a way that does not merely produce a visually pleasing network.

8.7 Model Selection With StARS

StARS, the Stability Approach to Regularization Selection, chooses the regularization level by asking whether the selected edges are stable under subsampling (Liu et al. 2010). Let \(\lambda\in\Lambda\) be a candidate regularization value. For subsample \(b=1,\ldots,B\), fit the graph-learning method on a subset of the observations and obtain an adjacency matrix

\[\begin{equation} \hat{A}^{(b)}(\lambda) \in \{0,1\}^{p\times p}. \label{eq:ch08-stars-subsample-adjacency} \end{equation}\]

For edge \((j,\ell)\), the estimated selection probability is

\[\begin{equation} \hat{\pi}_{j\ell}(\lambda) = \frac{1}{B} \sum_{b=1}^{B} \hat{A}^{(b)}_{j\ell}(\lambda). \label{eq:ch08-stars-selection-probability} \end{equation}\]

An edge is unstable if it is selected in some subsamples but not others. The Bernoulli variability of edge \((j,\ell)\) is

\[\begin{equation} \hat{\xi}_{j\ell}(\lambda) = 2\hat{\pi}_{j\ell}(\lambda) \left[ 1-\hat{\pi}_{j\ell}(\lambda) \right]. \label{eq:ch08-stars-edge-instability} \end{equation}\]

This quantity is near zero if the edge is almost always absent or almost always present, and it is largest when \(\hat{\pi}_{j\ell}(\lambda)\) is near \(1/2\). The average instability over all possible undirected edges is

\[\begin{equation} \hat{D}(\lambda) = \frac{2}{p(p-1)} \sum_{1\leq j<\ell\leq p} \hat{\xi}_{j\ell}(\lambda). \label{eq:ch08-stars-average-instability} \end{equation}\]

Given a threshold \(\tau_{\mathrm{StARS}}\), often chosen as a small value such as \(0.05\), StARS selects a regularization level whose estimated graph instability is controlled:

\[\begin{equation} \hat{D}(\hat{\lambda}) \leq \tau_{\mathrm{StARS}}. \label{eq:ch08-stars-threshold-rule} \end{equation}\]

In practice, one evaluates a regularization path and chooses a graph that is as rich as possible while keeping instability below the threshold. StARS is not a proof that the selected edges are true biological interactions. It is a model-selection criterion: it asks whether the graph is reproducible under perturbations of the sample.

8.8 Compositional Data And SPIEC-EASI

Microbiome network learning is harder because sequencing counts are sparse, overdispersed, and compositional. If \(c_i\) is the count vector for observation \(i\) and

\[\begin{equation} N_i = \sum_{j=1}^{p} c_{ij}, \label{eq:ch08-library-size} \end{equation}\]

then the observed proportions

\[\begin{equation} \hat{\pi}_{ij} = \frac{c_{ij}}{N_i} \label{eq:ch08-observed-proportion} \end{equation}\]

live on the simplex. Increasing the observed proportion of one taxon forces at least one other proportion to decrease. This can induce negative correlations even when the underlying absolute abundances are independent. A naive correlation network on proportions is therefore not a reliable ecological interaction network (Friedman and Alm 2012).

Log-ratio transformations address the compositional scale. For positive compositions, the centered log-ratio transform is

\[\begin{equation} \operatorname{clr}(\pi_i)_j = \log \pi_{ij} - \frac{1}{p} \sum_{\ell=1}^{p} \log \pi_{i\ell}. \label{eq:ch08-clr-transform} \end{equation}\]

Zeros must be handled before this transformation is applied. SPIEC-EASI combines compositional preprocessing ideas with sparse inverse covariance estimation. At a high level, its workflow is

\[\begin{equation} C \longmapsto \tilde{X} \longmapsto \hat{A}_{\lambda}, \label{eq:ch08-spiec-easi-workflow} \end{equation}\]

where \(\tilde{X}\) is a transformed representation suitable for sparse graphical modeling, and \(\hat{A}_{\lambda}\) is learned using either neighborhood selection or graphical lasso-type estimation. The regularization parameter is selected using stability ideas such as StARS. SPIEC-EASI combines normalization or compositional transformation with sparse graph estimation because the graph is only meaningful on the scale on which conditional associations are modeled (Kurtz et al. 2015).

The complete SPIEC-EASI workflow with American Gut data, MB and GLASSO options, StARS-style tuning through pulsar, SparCC comparison, graph plotting, and degree distributions is worked through in Exercise Sheet 6, Task 1 (Exercise Sheet 06 2026).

8.9 What To Report

A learned network should be reported as a statistical estimate, not as a discovered wiring diagram. At minimum, one should state the input data object, filtering rules, normalization or transformation, node definition, graph-learning method, regularization path, model-selection criterion, final number of nodes and edges, and any stability diagnostics.

A compact learned-network result can be written as

\[\begin{equation} \left( \hat{A}_{\hat{\lambda}}, \hat{\lambda}, \hat{D}(\hat{\lambda}), |V|, |E| \right). \label{eq:ch08-network-result-object} \end{equation}\]

For Gaussian graphical models, it is also useful to report the estimated precision matrix or partial correlations:

\[\begin{equation} \left( \hat{\Omega}_{\hat{\lambda}}, \hat{P}_{\hat{\lambda}}, \hat{A}_{\hat{\lambda}} \right), \label{eq:ch08-precision-result-object} \end{equation}\]

where \(\hat{P}_{\hat{\lambda}}\) contains partial correlations derived from Equation \(\ref{eq:ch08-glasso-partial-correlation}\). Biological interpretation should be cautious: an edge is a conditional association under the chosen model and preprocessing, not automatically a direct physical interaction or causal effect.

Summary

Network learning turns a feature matrix into an estimated graph. Correlation networks are simple but often confound direct and indirect associations. Gaussian graphical models define edges through conditional dependence, represented by nonzero off-diagonal entries of the precision matrix. Node-wise lasso estimates each node’s neighborhood by sparse regression. Graphical lasso estimates the whole sparse precision matrix directly. StARS chooses the regularization level by measuring graph instability under subsampling. For microbiome data and other compositional measurements, methods such as SPIEC-EASI combine normalization or log-ratio preprocessing with sparse graphical-model estimation.

The chapter’s central message is that a learned network is a model-dependent statistical object. The edge set depends on preprocessing, node definition, distributional assumptions, regularization, and model selection. This is precisely why network learning must be separated from network analysis: before computing centralities or modules, we need to know what the edges mean and how they were estimated.

References

Exercise Sheet 04. 2026. Exercise Sheet 04 Solutions: Hierarchical Clustering and Graph-Based Clustering of High-Dimensional Biological Data. https://bio-datascience.github.io/ahbd/assets/exercises/AHDBD_SS26_Exercise04_Solution.html.
Exercise Sheet 05. 2026. Exercise Sheet 05 Solutions: Hypothesis Testing, Differential Abundance, PERMANOVA, and High-Dimensional Inference. https://bio-datascience.github.io/ahbd/assets/exercises/AHDBD_SS26_Exercise05_Solution.html.
Exercise Sheet 06. 2026. Exercise Sheet 06 Solutions: Task 1 Sparse Microbial Network Inference with SPIEC-EASI, Task 2 Network Analysis with NetCoMi, and Deep Count Autoencoders. https://bio-datascience.github.io/ahbd/assets/exercises/AHDBD_SS26_Exercise06_Solution.html.
Friedman, Jerome, Trevor Hastie, and Robert Tibshirani. 2008. “Sparse Inverse Covariance Estimation with the Graphical Lasso.” Biostatistics 9 (3): 432–41. https://doi.org/10.1093/biostatistics/kxm045.
Friedman, Jonathan, and Eric J. Alm. 2012. “Inferring Correlation Networks from Genomic Survey Data.” PLoS Computational Biology 8 (9): e1002687. https://doi.org/10.1371/journal.pcbi.1002687.
Kurtz, Zachary D., Christian L. Müller, Emily R. Miraldi, Dan R. Littman, Martin J. Blaser, and Richard A. Bonneau. 2015. “Sparse and Compositionally Robust Inference of Microbial Ecological Networks.” PLOS Computational Biology 11 (5): e1004226. https://doi.org/10.1371/journal.pcbi.1004226.
Liu, Han, Kathryn Roeder, and Larry Wasserman. 2010. “Stability Approach to Regularization Selection (StARS) for High Dimensional Graphical Models.” Advances in Neural Information Processing Systems 23: 1432–40.
Meinshausen, Nicolai, and Peter Bühlmann. 2006. “High-Dimensional Graphs and Variable Selection with the Lasso.” The Annals of Statistics 34 (3): 1436–62. https://doi.org/10.1214/009053606000000281.
Yuan, M., and Y. Lin. 2007. “Model Selection and Estimation in the Gaussian Graphical Model.” Biometrika 94 (1): 19–35. https://doi.org/10.1093/biomet/asm018.