Machine Learning · Lecture 20a

Lecture 20a
Learning Graphs from Data I: Correlation, Smoothness and Precision

Part V · Signals, senses, structure  |  correlation networks and their pitfalls, graph Laplacians and smooth signals, learning a graph from weather data, Gaussian graphical models and the precision matrix, partial correlation, the graphical lasso, neighbourhood selection  |  reading: Dempster (1972); Meinshausen & Bühlmann (2006); Friedman, Hastie & Tibshirani (2008); Kalofolias (2016); Dong et al. (2019)  |  causal discovery follows in Lecture 20b

Cartoon: the ice cream and the swimmersTwo stick figures stand by a chart in which ice-cream sales and swimming accidents rise and fall together. One says the two are connected. The other points to a sun above the chart and says both follow the weather. Ice cream and swimmingaccidents are connected! Both follow the sun.Condition on it.
Two variables can move together without either one affecting the other; a graph should join only what is still related once everything else is known
In this lecture
  1. Correlation networks and their pitfalls
  2. Learning a graph from smooth signals
  3. Gaussian graphical models: zeros in the precision matrix
  4. The graphical lasso and neighbourhood selection
  5. Summary, exercises, projects, reading

Lecture 9 took a graph as given (a road map, a friendship network) and learned on top of it. Often there is no graph, only measurements: daily returns of many stocks, temperatures at many weather stations, levels of many proteins in a cell. This lecture infers the graph from the data. Here the question is which variables are directly related; Lecture 20b asks which variables cause which.

By the end you should be able to explain why thresholding correlations gives misleading networks; state the Laplacian smoothness identity and use it to learn a graph from signals; prove that zeros in a Gaussian precision matrix are exactly conditional independences; and fit and tune the graphical lasso and neighbourhood selection.

1 — Correlation networks and their pitfalls

The simplest way to build a graph from data is to join every pair of variables whose correlation is large. Such correlation networks are common in finance, genomics and neuroscience. They are easy to compute and often wrong, for three reasons that this section measures on real data.

definition 20.1 — correlation network and partial correlation

For variables \(X_1,\dots,X_p\) with sample correlations \(r_{ij}\), the correlation network at threshold \(\tau\) has an edge \(i\)–\(j\) whenever

$$|r_{ij}|>\tau.$$

The partial correlation \(\rho_{ij\cdot\text{rest}}\) is the correlation between the residuals of \(X_i\) and \(X_j\) after each has been regressed on all the other variables. It measures what \(X_i\) and \(X_j\) still share once everything else is accounted for.

data — 56 large companies, 2003–2007

Daily opening and closing prices of 56 large US-listed companies (Exxon, Apple, Goldman Sachs, Coca-Cola, Toyota and others) from January 2003 to December 2007, as used in scikit-learn's "visualising the stock market structure" example, from the GitHub repository scikit-learn/examples-data. The prices are not adjusted for stock splits, so the code detects the splits (overnight jumps of more than 30%) and removes them. The lecture plan named the Fama–French 30 industry portfolios, but Kenneth French's Data Library could not be reached from the build environment.

code — a correlation network of stocks, and three pitfalls
# Correlation networks: daily returns of 56 large companies, 2003-2007, and three ways correlation misleads
import numpy as np, pandas as pd, re, warnings; warnings.filterwarnings('ignore')
from sklearn.covariance import GraphicalLassoCV, graphical_lasso
from sklearn.linear_model import LassoCV, Lasso
rng = np.random.default_rng(0)
names = dict(re.findall(r'"([A-Z]+)": "([^"]+)"', open('data/stocks/symbols.txt').read())); names['GE'] = 'General Electric'
raw = {s: pd.read_csv(f'data/stocks/{s}.csv', index_col='date') for s in names}
lo, lc = pd.DataFrame({s: np.log(d['open']) for s, d in raw.items()}), pd.DataFrame({s: np.log(d['close']) for s, d in raw.items()})
gap = lo - lc.shift(1); split = gap.abs() > 0.3                # prices are not split-adjusted: a 2-for-1 split is a -0.69 overnight gap
R = (lc - lc.shift(1)).where(~split, lc - lo).dropna()          # daily log returns, intraday only on split days
logprice = R.cumsum()                                           # split-adjusted log price
print(f"split days detected and corrected: {int(split.values.sum())}")
X = ((R - R.mean()) / R.std()).values; n, p = X.shape
C = np.corrcoef(X.T); off = C[np.triu_indices(p, 1)]
print(f"{p} companies, {n} trading days ({R.index[0]} to {R.index[-1]})")
print(f"correlations between daily returns: median {np.median(off):.2f}; {np.mean(off > 0.3):.0%} of the {len(off):,} pairs above 0.3")
ev = np.linalg.eigvalsh(C)[::-1]
print(f"largest eigenvalue of the correlation matrix: {ev[0]:.1f} of {p} ({ev[0] / p:.0%} of total variance, the 'market')")
# pitfall 1: a common driver. Remove the market (first principal component) and look again
u = np.linalg.eigh(C)[1][:, -1]; m = X @ u
Xr = X - np.outer(m, u); Cr = np.corrcoef(Xr.T); offr = Cr[np.triu_indices(p, 1)]
print(f"after removing the market factor: median correlation {np.median(offr):.2f}; {np.mean(offr > 0.3):.0%} of pairs above 0.3")
# pitfall 2: trends. Correlate price levels instead of returns, and two independent random walks
Cp = np.corrcoef(logprice.values.T)[np.triu_indices(p, 1)]
print(f"correlations between price levels: {np.mean(np.abs(Cp) > 0.5):.0%} of pairs above 0.5 in absolute value")
rw = [abs(np.corrcoef(rng.standard_normal((2, n)).cumsum(1))[0, 1]) for _ in range(2000)]
print(f"two independent random walks of {n} steps: median |correlation| {np.median(rw):.2f}; above 0.5 in {np.mean(np.array(rw) > 0.5):.0%} of 2,000 trials")
# pitfall 3: indirect paths. A chain X1 -> X2 -> X3
z = rng.standard_normal((3, 10000)); x1 = z[0]; x2 = 0.8 * x1 + 0.6 * z[1]; x3 = 0.8 * x2 + 0.6 * z[2]
r13 = np.corrcoef(x1, x3)[0, 1]
res = lambda a, b: a - np.polyfit(b, a, 1)[0] * b
print(f"chain X1 -> X2 -> X3: corr(X1, X3) = {r13:.2f}, but after removing X2 from both: {np.corrcoef(res(x1, x2), res(x3, x2))[0, 1]:+.3f}")
split days detected and corrected: 25
56 companies, 1257 trading days (2003-01-03 to 2007-12-31)
correlations between daily returns: median 0.29; 43% of the 1,540 pairs above 0.3
largest eigenvalue of the correlation matrix: 17.8 of 56 (32% of total variance, the 'market')
after removing the market factor: median correlation -0.03; 1% of pairs above 0.3
correlations between price levels: 73% of pairs above 0.5 in absolute value
two independent random walks of 1257 steps: median |correlation| 0.43; above 0.5 in 41% of 2,000 trials
chain X1 -> X2 -> X3: corr(X1, X3) = 0.64, but after removing X2 from both: +0.018

Daily returns of these companies are strongly correlated: the median correlation is 0.29, and 43% of all pairs exceed 0.3, so a threshold at 0.3 joins an oil company to a bank and a software maker to a retailer (Section 3 prints two such pairs). The reason is a common driver. The largest eigenvalue of the correlation matrix carries 32% of the total variance: on most days the whole market rises or falls together. Remove that one factor and the median correlation drops to -0.03, with 1% of pairs above 0.3. The second pitfall is trends. Correlating price levels instead of returns puts 73% of pairs above 0.5, and two random walks that share nothing have a median absolute correlation of 0.43: anything that drifts looks correlated with anything else that drifts. The third is indirect paths: in the chain, \(X_1\) and \(X_3\) have correlation 0.64, but once \(X_2\) is removed from both, what remains has correlation +0.018.

The three pitfalls have one cause: correlation counts every route by which two variables are linked, including routes through other variables. What we usually want is the direct link, the one that remains after the other variables are held fixed. Partial correlation measures exactly that, and Section 3 shows how to compute it for all pairs at once.

causal — correlation is not an edge

In the chain \(X_1\to X_2\to X_3\), the variables \(X_1\) and \(X_3\) are strongly correlated, yet neither acts on the other directly: every effect passes through \(X_2\). A common driver, like the market for stocks or the sun for ice cream and swimming, produces the same pattern without any chain at all. Partial correlations remove both kinds of indirect link, but they still cannot say which way an arrow points. That needs the causal ideas of Lecture 20b.

2 — Learning a graph from smooth signals

Graph signal processing (Lecture 9 and Lecture 18) treats a set of values, one per node, as a signal on a graph. A signal is smooth on a graph if neighbouring nodes have similar values: temperatures at nearby weather stations, for example. That suggests a way to learn a graph: find the graph on which the observed signals are smoothest, while keeping it sparse.

definition 20.2 — graph Laplacian and smoothness

Let \(W\) be a symmetric matrix of non-negative edge weights \(w_{ij}\), with degrees \(d_i=\sum_jw_{ij}\) and \(D=\operatorname{diag}(d_1,\dots,d_p)\). The graph Laplacian is

$$L=D-W.$$

For a signal \(x\in\mathbb R^p\) with one value per node, the Laplacian quadratic form \(x^\top Lx\) measures how much \(x\) varies across edges. Small values mean a smooth signal.

proposition 20.1 — the Laplacian sums squared differences across edges

For every signal \(x\),

$$x^\top Lx=\frac12\sum_{i,j}w_{ij}\,(x_i-x_j)^2\;\ge\;0.$$

For many signals, stored as the rows \(s_i\in\mathbb R^T\) of a matrix \(S\) (one row per node, one column per time), summing over the columns gives

$$\operatorname{tr}\big(S^\top LS\big)=\sum_{i\lt j}w_{ij}\,\lVert s_i-s_j\rVert^2.$$

Expand the right-hand side of the first identity, using the symmetry of \(W\):

$$\frac12\sum_{i,j}w_{ij}\big(x_i^2-2x_ix_j+x_j^2\big)=\sum_id_ix_i^2-\sum_{i,j}w_{ij}x_ix_j=x^\top Dx-x^\top Wx.$$

That is \(x^\top Lx\), and it is a sum of non-negative terms. The second identity applies the first to each column of \(S\) and adds; each unordered pair appears twice in \(\sum_{i,j}\), which cancels the \(\tfrac12\). \(\square\)

So the smoothness of the signals on a candidate graph is a weighted sum of the distances \(Z_{ij}=\lVert s_i-s_j\rVert^2\) between the nodes' signals. Minimising it alone would put all weight on the single closest pair, or give the empty graph. Kalofolias (2016) adds two terms that prevent this:

$$\min_{w\ge0}\;\sum_{i\lt j}w_{ij}Z_{ij}\;-\;\alpha\sum_i\log d_i\;+\;\beta\sum_{i\lt j}w_{ij}^2 .$$

The logarithm of each degree goes to minus infinity if a node loses all its edges, so every node stays connected. The squared penalty spreads weight over several edges; a larger \(\beta\) gives a denser graph. The problem is convex, and for 26 nodes a standard bounded optimiser solves it in a fraction of a second.

data — daily maximum temperatures at 26 US weather stations, 2022

Daily maximum temperatures in 2022 at 26 stations of NOAA's Global Historical Climatology Network (GHCN-Daily) across the continental United States, from Ajo, Arizona, to Apalachicola, Florida, with each station's latitude, longitude and elevation. The extract is the us_temperature data set of the openintro R package, via the Rdatasets copy on GitHub; it contains the first 26 stations in alphabetical order, so the stations are spread across the country with no particular pattern. Missing days (about 3%) are filled by linear interpolation.

code — learning a graph of weather stations from their temperatures alone
# Learning a graph from smooth signals: daily maximum temperatures at 26 US weather stations in 2022
from scipy.optimize import minimize
T = pd.read_csv('data/us_temperature.csv'); T = T[T.year == 2022]
st = T.groupby('station')[['location', 'latitude', 'longitude']].first()
Y = T.pivot(index='date', columns='station', values='tmax').interpolate(limit_direction='both')
Y = (Y.values - 32) * 5 / 9                                   # degrees Fahrenheit -> Celsius, (365, 26)
d = np.arange(len(Y)); H = np.column_stack([np.ones(len(Y))] + [f(2 * np.pi * k * d / 365) for k in (1, 2, 3) for f in (np.cos, np.sin)])
A = Y - H @ np.linalg.lstsq(H, Y, rcond=None)[0]               # anomalies: remove each station's seasonal cycle (3 harmonics)
S = A.T; q = S.shape[0]                                       # one row per station: a "signal" of 365 days
print(f"{q} stations, {S.shape[1]} days; anomaly sd {A.std():.1f} C")
iu = np.triu_indices(q, 1); E = len(iu[0])
Z = ((S[:, None, :] - S[None, :, :]) ** 2).sum(-1)[iu]; Z = Z / Z.mean()   # squared distance between station signals
B = np.zeros((q, E)); B[iu[0], np.arange(E)] = 1; B[iu[1], np.arange(E)] = 1  # degree of each node = B @ w
def learn_graph(alpha, beta):
    """Kalofolias (2016): minimise sum w_ij Z_ij - alpha sum_i log(degree_i) + beta ||w||^2 over w >= 0."""
    f = lambda w: (w @ Z - alpha * np.log(B @ w).sum() + beta * w @ w, Z - alpha * B.T @ (1 / (B @ w)) + 2 * beta * w)
    w = minimize(f, np.full(E, 0.1), jac=True, method='L-BFGS-B', bounds=[(0, None)] * E).x
    return np.where(w > 1e-3 * w.max(), w, 0)
lat, lon = np.radians(st.latitude.values), np.radians(st.longitude.values)
km = 6371 * np.arccos(np.clip(np.sin(lat)[:, None] * np.sin(lat) + np.cos(lat)[:, None] * np.cos(lat) * np.cos(lon[:, None] - lon), -1, 1))
nn3 = np.argsort(km, 1)[:, 1:4]                                  # each station's 3 nearest stations on the map
near = lambda i, j: (j in nn3[i]) or (i in nn3[j])
def describe(w, label):
    e = np.flatnonzero(w); dist = km[iu][e]
    print(f"{label}: {len(e)} edges, median length {np.median(dist):,.0f} km (all pairs: {np.median(km[iu]):,.0f} km); "
          f"{np.mean([near(iu[0][k], iu[1][k]) for k in e]):.0%} join map neighbours; {np.sum(B @ (w > 0) == 0)} stations left without an edge")
W = learn_graph(1.0, 0.03); describe(W, 'learned from smoothness   ')
Cs = np.corrcoef(S)[iu]; top = np.zeros(E); top[np.argsort(-Cs)[:np.count_nonzero(W)]] = 1
describe(top, 'top correlations, same count')
Lap = lambda w: np.diag(B @ w) - (lambda M: M + M.T)(np.zeros((q, q)) + np.bincount(iu[0] * q + iu[1], w, q * q).reshape(q, q))
L = Lap(W); sh = rng.permutation(W)
print(f"smoothness tr(S' L S) / ||w||_1 on the learned graph {np.trace(S.T @ L @ S) / W.sum():.0f}; same weights on random pairs {np.trace(S.T @ Lap(sh) @ S) / sh.sum():.0f}")
26 stations, 365 days; anomaly sd 4.8 C
learned from smoothness   : 43 edges, median length 555 km (all pairs: 1,525 km); 81% join map neighbours; 0 stations left without an edge
top correlations, same count: 43 edges, median length 554 km (all pairs: 1,525 km); 77% join map neighbours; 1 stations left without an edge
smoothness tr(S' L S) / ||w||_1 on the learned graph 5148; same weights on random pairs 13182

The learned graph has 43 edges, and they are short: the median edge joins stations 555 km apart, against 1,525 km for a random pair, and 81% of edges join a station to one of its three nearest neighbours on the map. The optimiser never saw a coordinate; it found the geography because weather systems span hundreds of kilometres, so nearby stations have similar daily anomalies. On this small problem the same number of largest correlations does almost as well (77% join map neighbours), but it leaves one station with no edge at all, which the logarithmic term rules out. Moving the learned weights to random pairs makes the signals 2.6 times rougher, by the measure of Proposition 20.1.

A graph learned from temperatures, drawn on the map

The optimiser saw only the 365 daily temperature anomalies at each station, never the coordinates. Change \(\beta\) to make the learned graph denser or sparser, and compare it with a graph made from the same number of largest correlations. Hover over a station to see its name.

spot check 20.1

A path graph joins nodes 1–2 and 2–3, each with weight 1. Which signal has the smallest value of \(x^\top Lx\)?

By Proposition 20.1, add up \((x_i-x_j)^2\) over the two edges.
\((1-1.5)^2+(1.5-2)^2=0.5\), against 2 and 18 for the others. Only the size of the jumps across edges counts: the signal may rise steadily along the path and still be smooth.

3 — Gaussian graphical models: zeros in the precision matrix

For Gaussian data there is an exact answer to "which pairs are directly related". It lives not in the covariance matrix but in its inverse.

definition 20.3 — Gaussian graphical model

Let \(X=(X_1,\dots,X_p)\sim\mathcal N(\mu,\Sigma)\) with \(\Sigma\) invertible. The precision matrix is

$$\Theta=\Sigma^{-1}.$$

The Gaussian graphical model of \(X\) is the undirected graph with an edge \(i\)–\(j\) exactly when \(\Theta_{ij}\neq0\).

theorem 20.1 — zeros of the precision matrix are conditional independences

Let \(X\sim\mathcal N(\mu,\Sigma)\) and \(\Theta=\Sigma^{-1}\). For \(i\neq j\), write \(X_{\text{rest}}\) for all the other variables. Then

$$X_i\perp X_j\mid X_{\text{rest}}\quad\Longleftrightarrow\quad\Theta_{ij}=0,$$

and the partial correlation of Definition 20.1 is

$$\rho_{ij\cdot\text{rest}}=-\frac{\Theta_{ij}}{\sqrt{\Theta_{ii}\,\Theta_{jj}}}.$$

Split the variables into \(A=\{i,j\}\) and \(B=\text{rest}\). Given \(X_B\), the pair \(X_A\) is Gaussian with covariance equal to the Schur complement

$$\Sigma_{AA}-\Sigma_{AB}\Sigma_{BB}^{-1}\Sigma_{BA}=\big(\Theta_{AA}\big)^{-1},$$

by the formula for the inverse of a block matrix. Here \(\Theta_{AA}\) is the \(2\times2\) block of \(\Theta\), and its inverse is

$$\big(\Theta_{AA}\big)^{-1}=\frac1{\Theta_{ii}\Theta_{jj}-\Theta_{ij}^2}\begin{pmatrix}\Theta_{jj}&-\Theta_{ij}\\-\Theta_{ij}&\Theta_{ii}\end{pmatrix}.$$

Two jointly Gaussian variables are independent exactly when their covariance is zero, so \(X_i\perp X_j\mid X_B\) exactly when \(\Theta_{ij}=0\). Dividing the off-diagonal entry by the square root of the product of the diagonal entries gives the conditional correlation, \(-\Theta_{ij}/\sqrt{\Theta_{ii}\Theta_{jj}}\). For Gaussian data the conditional covariance does not depend on the value of \(X_B\), so this is also the correlation of the regression residuals in Definition 20.1. \(\square\)

The covariance matrix records every route between two variables; the precision matrix keeps only the direct ones. A second view of the same matrix explains why, and leads to a practical algorithm.

theorem 20.2 — each row of the precision matrix is a regression

Under the assumptions of Theorem 20.1, the best prediction of \(X_j\) from all the other variables is linear,

$$\mathbb E[X_j\mid X_{-j}]=\mu_j+\sum_{k\neq j}\beta_{jk}\,(X_k-\mu_k),\qquad \beta_{jk}=-\frac{\Theta_{jk}}{\Theta_{jj}},$$

and its error variance is \(1/\Theta_{jj}\). So \(X_k\) is needed to predict \(X_j\) exactly when \(\Theta_{jk}\neq0\).

For Gaussian variables, the conditional mean of \(X_j\) given \(X_{-j}\) has coefficients \(\Sigma_{j,-j}\Sigma_{-j,-j}^{-1}\), and the conditional variance is \(\Sigma_{jj}-\Sigma_{j,-j}\Sigma_{-j,-j}^{-1}\Sigma_{-j,j}\).

The block-inverse formula for \(\Theta=\Sigma^{-1}\) gives

$$\Theta_{jj}=\big(\Sigma_{jj}-\Sigma_{j,-j}\Sigma_{-j,-j}^{-1}\Sigma_{-j,j}\big)^{-1},\qquad \Theta_{j,-j}=-\Theta_{jj}\,\Sigma_{j,-j}\Sigma_{-j,-j}^{-1}.$$

The first identity says the error variance is \(1/\Theta_{jj}\); the second says the coefficients are \(-\Theta_{j,-j}/\Theta_{jj}\). \(\square\)

code — dense covariance, sparse precision; partial correlations of stocks
# Gaussian graphical models: the covariance is dense, the precision matrix is sparse
np.set_printoptions(precision=2, suppress=True)
Bc = np.eye(5) - np.diag([0.8] * 4, -1)                        # chain X1 -> X2 -> X3 -> X4 -> X5, X_k = 0.8 X_(k-1) + noise
Sig = np.linalg.inv(Bc) @ np.linalg.inv(Bc).T; Theta = np.linalg.inv(Sig)
clean = lambda M: np.where(np.abs(M) < 1e-9, 0.0, M)
print("covariance of the chain (every pair correlated):\n", Sig)
print("precision matrix (zero exactly where two variables are not neighbours in the chain):\n", clean(Theta))
pc = lambda Th: -Th / np.sqrt(np.outer(np.diag(Th), np.diag(Th)))          # partial correlations
P = pc(np.linalg.inv(C))                                       # stocks: inverse of the sample correlation matrix
sym = list(names)
for a, b in [('XOM', 'CVX'), ('KO', 'PEP'), ('TM', 'HMC'), ('XOM', 'JPM'), ('MSFT', 'WMT')]:
    i, j = sym.index(a), sym.index(b)
    print(f"{names[a]:>14s} - {names[b]:<14s} correlation {C[i, j]:.2f}   partial correlation {P[i, j]:+.2f}")
offP = np.abs(P[np.triu_indices(p, 1)])
print(f"all {len(offP):,} stock pairs: {np.mean(offP < 0.05):.0%} have |partial correlation| below 0.05 (|correlation| below 0.05: {np.mean(np.abs(off) < 0.05):.0%})")
covariance of the chain (every pair correlated):
 [[1.   0.8  0.64 0.51 0.41]
 [0.8  1.64 1.31 1.05 0.84]
 [0.64 1.31 2.05 1.64 1.31]
 [0.51 1.05 1.64 2.31 1.85]
 [0.41 0.84 1.31 1.85 2.48]]
precision matrix (zero exactly where two variables are not neighbours in the chain):
 [[ 1.64 -0.8   0.    0.    0.  ]
 [-0.8   1.64 -0.8   0.    0.  ]
 [ 0.   -0.8   1.64 -0.8   0.  ]
 [ 0.    0.   -0.8   1.64 -0.8 ]
 [ 0.    0.    0.   -0.8   1.  ]]
         Exxon - Chevron        correlation 0.83   partial correlation +0.46
     Coca Cola - Pepsi          correlation 0.48   partial correlation +0.24
        Toyota - Honda          correlation 0.73   partial correlation +0.55
         Exxon - JPMorgan Chase correlation 0.41   partial correlation -0.02
     Microsoft - Wal-Mart       correlation 0.39   partial correlation +0.07
all 1,540 stock pairs: 81% have |partial correlation| below 0.05 (|correlation| below 0.05: 0%)

The chain shows Theorem 20.1 at work. Every pair in the covariance matrix is correlated, but the precision matrix is zero except next to the diagonal: each variable is directly linked only to its two neighbours. For the stocks, partial correlations separate direct from shared links. Exxon and Chevron keep a large partial correlation (+0.46), as do Toyota and Honda (+0.55): they share something beyond the market. Exxon and JPMorgan Chase, correlated at 0.41, have partial correlation -0.02; Microsoft and Wal-Mart drop from 0.39 to +0.07. Their correlation came from the rest of the market. Overall, 81% of pairs have a partial correlation below 0.05 in absolute value, against 0% of pairs for ordinary correlation.

spot check 20.2

A precision matrix has \(\Theta_{11}=\Theta_{22}=2\) and \(\Theta_{12}=-1\). What is the partial correlation of \(X_1\) and \(X_2\)?

Use \(\rho_{12\cdot\text{rest}}=-\Theta_{12}/\sqrt{\Theta_{11}\Theta_{22}}\); mind the sign.
\(-(-1)/\sqrt{2\cdot2}=0.5\). A negative precision entry means a positive partial correlation.

4 — The graphical lasso and neighbourhood selection

With many variables and limited data, the inverse of the sample covariance is noisy: none of its entries is exactly zero, and with more variables than observations it does not exist. Both methods below estimate a sparse precision matrix by adding the \(\ell_1\) penalty of the lasso (Lecture 3), which sets small entries exactly to zero. Both assume, at least approximately, that the data are multivariate normal. When the variables are skewed or heavy-tailed, the same methods can be run on a correlation matrix computed from ranks, which is valid for any monotone transformation of each variable: the nonparanormal of Lecture 17b (Definition 17.13).

definition 20.4 — graphical lasso and neighbourhood selection

Let \(S\) be the sample covariance (or correlation) matrix. The graphical lasso (Friedman, Hastie and Tibshirani, 2008) estimates

$$\hat\Theta=\arg\max_{\Theta\succ0}\;\Big\{\log\det\Theta-\operatorname{tr}(S\Theta)-\lambda\sum_{i\neq j}|\Theta_{ij}|\Big\}.$$

The first two terms are the Gaussian log-likelihood (up to a factor and a constant); the penalty \(\lambda\) controls how many edges survive.

Neighbourhood selection (Meinshausen and Bühlmann, 2006) uses Theorem 20.2 instead. Run a lasso regression of each \(X_j\) on all the others, and join \(j\) and \(k\) if the coefficient of \(X_k\) in the regression for \(X_j\), or of \(X_j\) in the regression for \(X_k\), is non-zero (the "or" rule).

Neighbourhood selection is simpler and parallel: \(p\) separate lasso fits. The graphical lasso fits all rows together and returns a proper, positive-definite precision matrix, which a sampler or a classifier can use. Both need the penalty to be chosen, and that choice matters more than the choice of method.

code — the graphical lasso on the stocks; recovering a known graph
# The graphical lasso on the stocks, and edge recovery when the true graph is known
sector = {**dict.fromkeys(['TOT', 'XOM', 'CVX', 'COP', 'VLO'], 'energy'), **dict.fromkeys(['WFC', 'JPM', 'AIG', 'AXP', 'BAC', 'GS'], 'finance'),
          **dict.fromkeys(['MSFT', 'IBM', 'YHOO', 'DELL', 'HPQ', 'AMZN', 'AAPL', 'SAP', 'CSCO', 'TXN', 'XRX', 'CAJ', 'SNE'], 'technology'),
          **dict.fromkeys(['TWX', 'CMCSA', 'CVC'], 'media'), **dict.fromkeys(['TM', 'F', 'HMC', 'NAV'], 'vehicles'),
          **dict.fromkeys(['NOC', 'BA', 'GD', 'RTN'], 'defence'), **dict.fromkeys(['KO', 'PEP', 'K', 'UN', 'PG', 'CL', 'KMB'], 'household goods'),
          **dict.fromkeys(['MCD', 'MAR', 'WMT', 'HD', 'CVS'], 'retail'), **dict.fromkeys(['MMM', 'GE', 'CAT', 'DD', 'R'], 'industrial'),
          **dict.fromkeys(['GSK', 'PFE', 'SNY', 'NVS'], 'pharmaceutical')}
sec = np.array([sector[s] for s in sym]); same = (sec[:, None] == sec[None, :])[np.triu_indices(p, 1)]
gl = GraphicalLassoCV(cv=5).fit(X); cvk = int((np.abs(gl.precision_[np.triu_indices(p, 1)]) > 1e-4).sum())
print(f"lambda chosen by 5-fold cross-validation: {gl.alpha_:.3f}, giving {cvk} edges of {len(same):,} ({cvk / len(same):.0%})")
def glasso_edges(Xm, lam):
    Th = graphical_lasso(np.corrcoef(Xm.T), lam, max_iter=500)[1]; return Th, np.abs(Th[np.triu_indices(p, 1)]) > 1e-4
for label, Xm, lam in [('returns', X, 0.4), ('returns minus the market factor', Xr, 0.2)]:
    Th, e = glasso_edges(Xm, lam); k = int(e.sum()); Cm = np.corrcoef(Xm.T)[np.triu_indices(p, 1)]
    deg = (np.abs(Th) > 1e-4).sum(1) - 1
    print(f"{label}, lambda = {lam}: {k} edges; same-sector share {same[e].mean():.0%} "
          f"(the {k} largest correlations: {same[np.argsort(-Cm)[:k]].mean():.0%}; random pairs {same.mean():.0%}); "
          f"most connected: " + ", ".join(f"{names[sym[i]]} ({deg[i]})" for i in np.argsort(-deg)[:3]))
    cross = [f"{names[sym[a]]}-{names[sym[b]]}" for a, b, ek, sk in zip(*np.triu_indices(p, 1), e, same) if ek and not sk]
    if len(cross) <= 6: print("  edges between sectors: " + ", ".join(cross))
# simulation: a random sparse graph on 30 variables, 200 samples; can each method find its edges?
def sparse_precision(d, prob, seed):
    g = np.random.default_rng(seed); A = np.triu(g.random((d, d)) < prob, 1) * g.choice([-1, 1], (d, d)) * g.uniform(0.3, 0.6, (d, d))
    A = A + A.T; return A + np.eye(d) * (np.abs(np.linalg.eigvalsh(A)).max() + 0.2)
d = 30; Th0 = sparse_precision(d, 0.08, 1); iu30 = np.triu_indices(d, 1); truth = Th0[iu30] != 0
Xs = rng.multivariate_normal(np.zeros(d), np.linalg.inv(Th0), 200); Xs = (Xs - Xs.mean(0)) / Xs.std(0); Cs30 = np.corrcoef(Xs.T)
def f1(est):
    tp = np.sum(est & truth); return 0 if tp == 0 else 2 * tp / (est.sum() + truth.sum())
grid = np.linspace(0.02, 0.6, 30); curve = {}
curve['correlation threshold'] = [f1(np.abs(Cs30[iu30]) > t) for t in grid]
curve['graphical lasso'] = [f1(np.abs(graphical_lasso(Cs30, a, max_iter=500)[1][iu30]) > 1e-4) for a in grid]
def neighbourhood(a):
    Bm = np.zeros((d, d))
    for j in range(d): Bm[j, np.arange(d) != j] = Lasso(alpha=a).fit(np.delete(Xs, j, 1), Xs[:, j]).coef_
    return ((Bm != 0) | (Bm.T != 0))[iu30]                    # "or" rule: keep an edge if either regression selects it
curve['neighbourhood selection'] = [f1(neighbourhood(a)) for a in grid]
print(f"\nsimulated graph: {d} variables, {truth.sum()} true edges, 200 samples. Best F1 score over each method's tuning parameter:")
for m_, v in curve.items(): print(f"  {m_:24s} {max(v):.2f} (at parameter {grid[int(np.argmax(v))]:.2f})")
lambda chosen by 5-fold cross-validation: 0.181, giving 623 edges of 1,540 (40%)
returns, lambda = 0.4: 145 edges; same-sector share 44% (the 145 largest correlations: 43%; random pairs 11%); most connected: General Electric (23), JPMorgan Chase (22), Goldman Sachs (22)
returns minus the market factor, lambda = 0.2: 41 edges; same-sector share 90% (the 41 largest correlations: 88%; random pairs 11%); most connected: Total (4), Exxon (4), Chevron (4)
  edges between sectors: Toyota-Canon, Toyota-Sony, Canon-Honda, Navistar-Caterpillar

simulated graph: 30 variables, 37 true edges, 200 samples. Best F1 score over each method's tuning parameter:
  correlation threshold    0.69 (at parameter 0.24)
  graphical lasso          0.79 (at parameter 0.20)
  neighbourhood selection  0.82 (at parameter 0.20)

Three lessons. First, cross-validation picks \(\lambda=0.181\) and keeps 623 edges, 40% of all pairs. Cross-validation chooses the penalty that predicts held-out data best, and for prediction many small edges help; it is not designed to find the graph. Second, at \(\lambda=0.4\) the graph has 145 edges, but only 44% join companies in the same sector (random pairs: 11%), and the hubs are General Electric, JPMorgan Chase and Goldman Sachs, which behave like the market itself. Exercise 3 explains why: an unobserved common cause makes the precision matrix dense. Remove the market factor first and the picture changes: at \(\lambda=0.2\), 90% of the 41 edges are within a sector (oil companies, banks, defence firms, drug makers). The few exceptions make sense too: Toyota–Canon, Toyota–Sony, Canon–Honda and Navistar–Caterpillar, which link Japanese companies and two makers of heavy vehicles and machinery. On these data the graphical lasso and the same number of largest correlations agree closely (90% against 88%), so the gain from the precision matrix is mainly the factor lesson, not the sector count. On simulated data with a known graph, the gain is clearer: the best F1 score is 0.69 for thresholded correlations, 0.79 for the graphical lasso and 0.82 for neighbourhood selection.

00.10.20.30.40.50.600.250.50.751tuning parameter (penalty λ, or correlation threshold)F1 score for the true edgescorrelation thresholdgraphical lassoneighbourhood selection
Recovering a known graph: F1 score (the harmonic mean of the share of true edges found and the share of reported edges that are true) for a simulated 30-variable Gaussian graphical model with 200 samples, against each method's tuning parameter. Dots mark each method's best value.

Correlation against partial correlation

Left: correlations between the 56 stocks, grouped by sector (red positive, blue negative). Right: partial correlations from the graphical lasso, with zeros left blank. Increase \(\lambda\) to remove edges; tick the box to remove the market factor first. The circle shows the graph, with edges inside a sector in that sector's colour.

bayes — the graphical lasso as a posterior mode

The \(\ell_1\) penalty is the logarithm of a Laplace prior on each off-diagonal entry of \(\Theta\), \(p(\Theta_{ij})\propto e^{-\lambda|\Theta_{ij}|}\). The graphical lasso estimate is therefore the posterior mode (MAP estimate, Lecture 5) under that prior. A full Bayesian treatment keeps the whole posterior: the Bayesian graphical lasso (Wang, 2012) samples \(\Theta\) by Gibbs sampling, and G-Wishart priors put probability on graphs themselves, so that each edge gets a posterior probability rather than a yes or no. The cost is computation; the gain is an honest statement of which edges the data actually support.

history — covariance selection

Arthur Dempster's "Covariance selection" (Biometrics, 1972) proposed simplifying a covariance matrix by setting entries of its inverse to zero, and fitting the rest by maximum likelihood. For three decades the zeros were chosen by stepwise testing, which was slow and unstable beyond a few dozen variables. Nicolai Meinshausen and Peter Bühlmann (Annals of Statistics, 2006) showed that lasso regressions recover the graph consistently even when the number of variables grows faster than the sample size. Jerome Friedman, Trevor Hastie and Robert Tibshirani's graphical lasso (Biostatistics, 2008) solved the penalised likelihood with a fast coordinate-descent algorithm, and made sparse precision matrices a standard tool in genomics and finance.

quantum — learning about a quantum state from few measurements

A quantum state of \(n\) qubits is described by \(4^n\) real numbers, so learning all of it (quantum state tomography) needs exponentially many measurements. Huang, Kueng and Preskill (Nature Physics, 2020) showed that many properties can be learned from far fewer. Their classical shadows apply a random rotation to each copy of the state, measure it, and store the outcome. From these records one can estimate, for example, all correlations between pairs of qubits, with a number of copies that grows only logarithmically in the number of properties. Learning which qubits are correlated, and how strongly, is the quantum analogue of estimating a covariance graph from samples.

big picture — networks learned from data

Brain "connectivity" maps are often graphs learned from fMRI signals: partial correlations between brain regions, estimated with the graphical lasso, separate direct functional links from shared input. In finance, networks of banks and countries learned from returns or credit spreads are used to monitor contagion, the way distress spreads through the system; the market factor seen here is the reason such analyses usually remove common factors first. In genomics, sparse precision matrices of gene expression suggest which genes regulate which, a first step towards the causal questions of Lecture 20b. Sensor networks for weather, air quality or traffic use graphs learned from smooth signals to interpolate missing readings and detect faulty sensors.

5 — Summary, exercises, projects, reading

summary
exercises
  1. Show that the Laplacian of Definition 20.2 has eigenvalue 0 with eigenvector \(\mathbf 1=(1,\dots,1)\). Use Proposition 20.1 to show that if the graph is connected, every vector with \(x^\top Lx=0\) is constant.

    Each row of \(L\) sums to \(d_i-\sum_jw_{ij}=0\), so \(L\mathbf 1=0\).

    If \(x^\top Lx=0\), every term \(w_{ij}(x_i-x_j)^2\) is zero, so \(x_i=x_j\) across every edge. Along any path the value cannot change, and in a connected graph every pair of nodes is joined by a path, so \(x\) is constant. (With several components, \(x\) may take a different constant on each, so the multiplicity of the eigenvalue 0 counts the components, as used by spectral clustering in Lecture 15.)

  2. A linear chain \(X_1=\varepsilon_1\), \(X_2=aX_1+\varepsilon_2\), \(X_3=bX_2+\varepsilon_3\) has independent standard normal noise. Writing \(X=AX+\varepsilon\), the precision matrix is \((I-A)^\top(I-A)\). Compute it and check that \(\Theta_{13}=0\).

    Here \(I-A\) has rows \((1,0,0)\), \((-a,1,0)\) and \((0,-b,1)\). Multiplying out,

    $$\Theta=\begin{pmatrix}1+a^2&-a&0\\-a&1+b^2&-b\\0&-b&1\end{pmatrix}.$$

    The (1,3) entry is the inner product of the first and third columns of \(I-A\), \((1,-a,0)\cdot(0,0,1)=0\). The graph is the chain 1–2–3, as in the code with \(a=b=0.8\), whose precision diagonal entries are \(1.64\) and \(1\).

  3. In a one-factor market model, \(X=b\,m+\varepsilon\) with \(m\sim\mathcal N(0,1)\) and independent \(\varepsilon\sim\mathcal N(0,D)\), \(D\) diagonal. Use the Woodbury identity to find \(\Theta=\Sigma^{-1}\). Which entries are zero? What does this say about the graph of stock returns, and why does removing the market factor help?

    \(\Sigma=D+bb^\top\), so by Woodbury

    $$\Theta=D^{-1}-\frac{D^{-1}bb^\top D^{-1}}{1+b^\top D^{-1}b}.$$

    The off-diagonal entry \((i,j)\) is \(-b_ib_j/(d_id_j(1+b^\top D^{-1}b))\), which is non-zero whenever both stocks load on the market. The graph is complete, although the stocks are independent given \(m\). An unobserved common cause makes the precision matrix dense. Removing the factor (or modelling the precision as sparse plus low rank, as in Chandrasekaran, Parrilo and Willsky, 2012) restores the sparse structure, which is why the sector edges appear so clearly in the second fit of the code.

  4. Show that with \(\lambda=0\) and an invertible \(S\), the graphical lasso returns \(\hat\Theta=S^{-1}\). What goes wrong when there are fewer observations than variables, and how does \(\lambda>0\) fix it?

    The gradient of \(\log\det\Theta-\operatorname{tr}(S\Theta)\) is \(\Theta^{-1}-S\). Setting it to zero gives \(\Theta=S^{-1}\), and the objective is concave, so this is the maximum.

    With \(n\lt p\), \(S\) is singular. Take a vector \(v\) with \(Sv=0\) and \(\Theta=I+tvv^\top\): the trace term stays fixed while \(\log\det\Theta\) grows without bound as \(t\to\infty\), so there is no maximiser. With \(\lambda>0\), the penalty grows linearly in the entries of \(\Theta\), faster than the logarithm, so a maximiser exists and is unique.

  5. In neighbourhood selection, the "and" rule keeps an edge only if both regressions select it. Which rule gives more edges? If the lasso selects each true neighbour with probability 0.9 and each non-neighbour with probability 0.05, independently, what are the probabilities that a true edge and a false edge are kept under each rule?

    The "or" rule keeps every edge the "and" rule keeps, and more.

    True edge: "or" \(1-0.1^2=0.99\); "and" \(0.9^2=0.81\). False edge: "or" \(1-0.95^2\approx0.098\); "and" \(0.05^2=0.0025\). The "and" rule trades some missed edges for many fewer false ones. Meinshausen and Bühlmann showed that both are consistent under suitable conditions; in practice the difference shrinks as \(n\) grows.

  6. (Code.) Refit the graphical lasso at \(\lambda=0.4\) on 50 bootstrap samples of the trading days (resampling days with replacement). Keep only the edges that appear in at least 80% of the fits. How many edges survive, and which sectors do they join?

    Resample rows of X with rng.integers(0, n, n), refit with graphical_lasso(np.corrcoef(Xb.T), 0.4), and count how often each edge is non-zero. Expect the within-sector edges (oil companies, banks, Japanese firms, household goods) to be very stable and many cross-sector edges to appear in only some fits. Selecting edges by their stability under resampling, rather than by a single fit, is the idea behind stability selection (Meinshausen and Bühlmann, 2010) and the StARS method for choosing \(\lambda\) (Liu, Roeder and Wasserman, 2010).

student projects

Each project uses this lecture's methods and public data, and has a clear result.

1. How stable is a network of New York neighbourhoods?

question
Which neighbourhood indicators (income, rent burden, asthma rates, air quality, crime, commuting time) are directly related once the others are accounted for, and do the edges survive from year to year and across bootstrap samples?
data
NYC Open Data and the NYU Furman Center's neighbourhood indicators by community district; the NYC Environment and Health Data Portal for health and air-quality measures; several years of each.
method
Standardised indicators; graphical lasso with \(\lambda\) chosen by cross-validation and by stability selection; bootstrap edge frequencies; comparison of the graphs from different years.
outcome
A short list of stable direct links, a list of edges that come and go, and a discussion of which links might be causal and which are confounded by borough or income.

2. A graph of the city's air-quality sensors

question
Does a graph learned from smooth signals of air pollution recover the city's geography, and does it reveal pollution corridors (highways, the waterfront) that distance alone does not?
data
Hourly PM2.5 readings from New York State Department of Environmental Conservation monitors and the NYC Community Air Survey, or from low-cost sensor networks with public data.
method
The smoothness objective of Section 2 for several \(\beta\); comparison with correlation networks and with \(k\)-nearest-neighbour graphs on the map; interpolation of a held-out sensor by graph smoothing.
outcome
Maps of the learned graphs, an interpolation error for each graph, and an assessment of whether learned edges follow roads or wind directions.

Reading and sources

Data. Stock prices: scikit-learn's example data for "visualizing the stock market structure", github.com/scikit-learn/examples-data (folder financial-data). Temperatures: NOAA Global Historical Climatology Network Daily (M. J. Menne et al., Journal of Atmospheric and Oceanic Technology 29, 897–910, 2012), extract in the openintro R package (us_temperature), via github.com/vincentarelbundock/Rdatasets. The Fama–French 30 industry portfolios named in the lecture plan could not be downloaded from the build environment and are not used.

numbers in the text not printed by a code box are computed in verify_L20a.py, figures and widget data in figs_L20a.py; code-box outputs are pasted from actual runs (numpy, pandas, SciPy and scikit-learn on two CPU cores)