Spectral Embeddings
Week 8, Problem 1 (live)
This page belongs to Problem 1 of Week 8. Like the earlier live pages, it runs Python in your browser, so there is nothing to install. The first visit downloads Python, numpy, and matplotlib, which can take a minute; wait until the loading message disappears.
Every box is pre-written. Your job is to read what comes out, explain it, and then amend it! Lines marked Experiment suggest a change to make, and you should try to predict what will happen before you press Run Code. The numbered Rhetorical Questions are things to think about; each has an answer you can expand once you have tried. Your edits should be saved in this browser, and Start Over restores the original code.
Every box can use the helpers in spectral_tools.py, which build the datasets, graphs, and pictures. You don’t need this, but feel free to look at it.
Every box on this page starts with numpy as np and matplotlib.pyplot as plt already imported, along with these helpers:
knn_graph(X, m)andgaussian_graph(X, eps): the weight matrix \(\bfW\) of the \(m\)-nearest-neighbour graph, or of the Gaussian similarity graph with bandwidth \(\varepsilon\), of the rows ofX.laplacian(W): the Laplacian \(\bfL=\bfD-\bfW\).normalized_embedding(W, k): the \(k\) smallest eigenvalues of \(\bfL_{\mathrm{sym}}\) and the matrix \(\bfPhi=[\bfphi_1,\ldots,\bfphi_k]\) of Lecture 16, exactly as in the lecture’s NumPy box.eigenmap(W, m): the \(m\)-dimensional Laplacian eigenmap \(\bfY=[\bfphi_2,\ldots,\bfphi_{m+1}]\), with the eigenvalues.energy(Y, W): the energy \(E(\bfY)=\frac12\sum_{i,j}w_{ij}\|\bfy_i-\bfy_j\|_2^2\), computed from the definition, not from a trace.scatter(Y, colors, title, ax=...)andpanels(count), for pictures.
Outliers
In Lecture 16 we switched from the Laplacian \(\bfL\) to the normalized Laplacian \(\bfL_{\mathrm{sym}}\) because “in a similarity graph, vertices are patently not all the same”. Here, we try to investigate why. The data are two blobs of \(100\) points each, plus a single outlier, the last row of X. We build the Gaussian similarity graph and split it in two twice: by the sign of the Fiedler vector of \(\bfL\), as in Lecture 14, and by the sign of \(\bfphi_2\) from \(\bfL_{\mathrm{sym}}\), as in Lecture 16.
Rhetorical Question 1. What does each split do?
The Fiedler vector of \(\bfL\) puts the outlier on one side and all \(200\) blob points on the other. The normalized split separates the two blobs exactly (the outlier joins one of them).
To see why, the box below compares the cut, which the Fiedler vector of \(\bfL\) tries to make small, with the normalized cut, \[ \operatorname{Ncut}(S)=\operatorname{cut}(S)\Big(\frac1{\operatorname{vol}(S)}+\frac1{\operatorname{vol}(S^c)}\Big), \] for the split that cuts off the outlier and for the split between the blobs.
Rhetorical Question 2. Which split has the smaller cut, and which has the smaller normalized cut? Using the vol(S) column, explain why the normalized cut prefers the split between the blobs.
Cutting off the outlier costs about \(0.0017\), against about \(5.5\) for the blob split. The normalized cut ranks the splits the other way, about \(1\) against \(0.003\).
The outlier is cheap to cut off only because it is barely connected to anything. But then its volume is small too: every edge at \(v\) leaves \(\{v\}\), so \(\operatorname{vol}(\{v\})=\operatorname{cut}(\{v\})=\deg(v)\) and \(\operatorname{Ncut}(\{v\})>1\), however far away \(v\) is. Each blob, on the other hand, has volume about \(4\times10^3\), and the cut of about \(5.5\) between them is roughly \(0.1\%\) of it. So the normalized cut asks what fraction of each side’s similarity leaves it, and a point that is attached to nothing is not a good cluster by that measure.
Experiment. Move the outlier closer, to outlier=(2.0, 3.0) and then (2.0, 2.0). Separately, keep it at (2.0, 4.0) and increase eps to 1, 2, and 4. Run both boxes after each change.
Rhetorical Question 3. When does the Fiedler vector of \(\bfL\) stop isolating the outlier? Does increasing eps, which makes every weight larger, help it? Does the normalized split ever fail?
At (2.0, 3.0) the outlier’s degree is about \(0.1\), and the Fiedler vector switches to the blob split. That cut is still much smaller than the \(5.5\) between the blobs, but the relaxation also prefers balanced splits, and here the balanced split wins. Increasing eps alone does not help: the outlier’s degree grows, but so do the weights between the blobs, and at (2.0, 4.0) the Fiedler vector still cuts off the outlier (with one other stray point at eps = 4) for every eps above. In all of these runs the normalized cut of the outlier split stays above \(1\), the blob split stays well below it, and the normalized split separates the blobs.
The eigenmap is only defined up to rotation
Problem 2 says that rotating or reflecting a Laplacian eigenmap does not change its energy or its constraints. Here we look at a case where this freedom is actually used. The data are \(500\) points uniform in the unit square, which we embed in \(\Rbb^2\) with a \(10\)-nearest-neighbour graph.
The box below repeats this for four different samples of the square, and then for four samples of a \(1.5\times1\) rectangle, using the same four seeds. The first panel of each row shows the sample with seed \(0\), colored by \(x\). The title of each eigenmap panel gives the gap \(\lambda_3-\lambda_2\).
Rhetorical Question 4. For the square, how do the four pictures differ? For the \(1.5\times1\) rectangle, how do they differ? Explain the difference using the gap \(\lambda_3-\lambda_2\) and Problem 2.
For the square, the pictures are the same shape turned by different angles: the direction in which the color (\(x\)) increases changes from panel to panel. For the rectangle, \(x\) always increases along the horizontal axis, so the pictures agree up to flips.
By Problem 2, every rotation of \([\bfphi_2,\bfphi_3]\) is an equally good embedding, but the eigensolver only returns eigenvectors. On the rectangle, varying along the long side is smoother than along the short side: stretching a function by \(1.5\) divides the differences between neighbours by \(1.5\), so \(\lambda_2\approx\lambda_3/1.5^2\). With this gap, each eigenvector is unique up to sign, and only flips remain. On the square, turning by \(90^\circ\) swaps \(x\) and \(y\), so \(\lambda_2\approx\lambda_3\); any rotation of the pair is then (nearly) a pair of eigenvectors again, and which one comes out depends on the small irregularities of each sample.
Now we check Problem 2 numerically. The box computes the energy in two ways, and how far each matrix is from satisfying the constraints, for \(\bfY\) and for \(\bfY\bfQ\) with a random orthogonal \(\bfQ\). The last column measures how far each column \(\bfz\) is from satisfying \(\bfL\bfz=\mu\bfD\bfz\) for some \(\mu\), as a fraction of \(\|\bfL\bfz\|_2\).
Rhetorical Question 5. Which entries of the output does Problem 2 predict, and which part predicts each? Now set a = 1.5: \(\bfY\bfQ\) still has the same energy as \(\bfY\) and still satisfies the constraints, but its residuals grow a lot. Why?
The first two columns agree for every row (part 1), and \(E(\bfY)=\lambda_2+\lambda_3\) (the smoothest embedding). \(E(\bfY\bfQ)=E(\bfY)\) (parts 2 and 3), and \(\bfY\bfQ\) satisfies both constraints, up to rounding errors (part 4).
The columns of \(\bfY\bfQ\) are mixtures \(\bfpsi=\alpha\bfphi_2+\beta\bfphi_3\), and \(\bfL\bfpsi=\bfD(\alpha\lambda_2\bfphi_2+\beta\lambda_3\bfphi_3)\), which is a multiple of \(\bfD\bfpsi\) only if \(\lambda_2=\lambda_3\) or one of \(\alpha,\beta\) is zero. On the square \(\lambda_2\approx\lambda_3\), so a mixture is nearly an eigenvector. On the rectangle the eigenvalues are well separated, and the mixture is far from an eigenvector, even though it is still a minimizer.
Experiment. With a = 1.5, replace Q by np.array([[1.0, 0.0], [0.0, -1.0]]), then by np.array([[0.0, 1.0], [1.0, 0.0]]). Both are orthogonal; predict the residuals of \(\bfY\bfQ\) before you run it.