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
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.
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.
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.
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.
# 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.
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.
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.
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.
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.
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.
# 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 path graph joins nodes 1–2 and 2–3, each with weight 1. Which signal has the smallest value of \(x^\top Lx\)?
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.
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\).
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.
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\)
# 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.
A precision matrix has \(\Theta_{11}=\Theta_{22}=2\) and \(\Theta_{12}=-1\). What is the partial correlation of \(X_1\) and \(X_2\)?
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).
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.
# 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.
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.
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.
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.
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.
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.)
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\).
\(\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.
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.
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.
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).
Each project uses this lecture's methods and public data, and has a clear result.
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)