Week 7

Problem 1

Complete the notebook Graphs as Data (live). Note, this will not be on the quiz.

Problem 2

In the prior exercise, we saw that spectral clustering can fails when the graph is too connected. For example, too large a bandwidth \(\varepsilon\), or too many neighbours \(m\). Let’s look at the extreme case. Fix distinct points \(\bfx_1,\ldots,\bfx_n\in\Rbb^d\) with \(n\) even. Their Gaussian similarity graph with bandwidth \(\varepsilon>0\) joins every pair \(i\neq j\) by an edge of weight \[ w_{ij}=\exp\Big(-\frac{\|\bfx_i-\bfx_j\|_2^2}{2\varepsilon}\Big), \] with no self-loops (\(w_{ii}=0\)). Let \(\bfL_\varepsilon\) be its Laplacian.

  1. Show that as \(\varepsilon\to\infty\), \(\bfL_\varepsilon\) converges entrywise to \(n\bfI-\mathbf{1}\mathbf{1}^\top\), the Laplacian of the complete graph \(K_n\) (every pair of vertices joined by an edge of weight \(1\)).
  2. Show that \(\mathbf{1}\) is an eigenvector of \(n\bfI-\mathbf{1}\mathbf{1}^\top\) with eigenvalue \(0\), and that every non-zero \(\bfv\perp\mathbf{1}\) is an eigenvector with eigenvalue \(n\). Conclude that \(\lambda_2=\cdots=\lambda_n=n\).
  3. Show that every \(S\) with \(|S|=n/2\) has \(\operatorname{cut}(S)=n^2/4\) in \(K_n\). Conclude why there is no notion of the “best” split.

Problem 3

Let \(G\) be a weighted graph on \(n\) vertices with symmetric weights \(w_{ij}\geq 0\), no self-loops (\(w_{ii}=0\)), and Laplacian \(\bfL=\bfD-\bfW\). Let \(\bfe_1,\ldots,\bfe_n\) be the standard basis vectors of \(\Rbb^n\).

  1. Compute the matrix \((\bfe_i-\bfe_j)(\bfe_i-\bfe_j)^\top\) for \(i\neq j\): which entries are non-zero, and what are they?
  2. Show that \[ \bfL=\sum_{i<j}w_{ij}(\bfe_i-\bfe_j)(\bfe_i-\bfe_j)^\top. \] What goes wrong if the sum is over all ordered pairs \(i\neq j\) instead?
  3. Use part 2 to recover the quadratic form \(\bff^\top\bfL\bff=\sum_{i<j}w_{ij}(f_i-f_j)^2\), and conclude that \(\bfL\) is positive semidefinite.

Problem 4

TipOn the quiz

You may use the previous problem, Problem 3, for this. If this appears on the quiz, you will be given the relevant portion, so you may use it there without proof.

Read the example How Connected Is a Graph? first; it gives the picture behind this problem.

Let \(G\) be a weighted graph with Laplacian \(\bfL\) and eigenvalues \(0=\lambda_1\leq\lambda_2\leq\cdots\leq\lambda_n\). Since \(\bfL\mathbf{1}=\mathbf{0}\), we may take \(\bfu_1=\mathbf{1}/\sqrt n\) in Rayleigh–Ritz, whether or not \(G\) is connected, so \[ \lambda_2=\min\big\{\bfz^\top\bfL\bfz:\ \|\bfz\|_2=1,\ \bfz\perp\mathbf{1}\big\}. \] Let \(G'\) be \(G\) with the weight of one pair \(\{i,j\}\) increased by \(w>0\) (if \(\{i,j\}\) was not an edge, this adds it), with Laplacian \(\bfL'\) and second eigenvalue \(\lambda_2'\).

  1. Show that \(\bfL'=\bfL+w(\bfe_i-\bfe_j)(\bfe_i-\bfe_j)^\top\).
  2. Show that \(\lambda_2'\geq\lambda_2\): adding an edge never makes a graph less connected.
  3. Let \(\bfu_2\) be a unit eigenvector of \(\bfL\) for \(\lambda_2\) with \(\bfu_2\perp\mathbf{1}\). Show that \(\lambda_2'\leq\lambda_2+w\,(u_2(i)-u_2(j))^2\). Use this to explain the figure in Where an edge goes matters.