30 Spectral Graph Theory and PageRank
Graph algorithms become numerical linear algebra after choosing matrix conventions. Undirected graphs lead to symmetric Laplacians. Directed ranking problems lead to stochastic matrices and eigenvectors.
30.1 Graph Matrices
(Convention) For undirected graphs, \(\bA\) is symmetric. For directed random walks in this section, probability vectors are columns and \(P_{ij}\) is the probability of moving from node \(j\) to node \(i\).
For a graph \(G = (V, E)\) with \(n\) vertices:
Adjacency \(\bA\): \(A_{ij} = w_{ij}\) if \((i,j) \in E\), else \(0\).
Degree \(\bD\): Diagonal matrix with \(D_{ii} = d_i = \sum_{j} w_{ij}\).
Defined as \(\bL = \bD - \bA\).
Discrete Derivative: \((\bL \boldsymbol{f})_i = \sum_{j \sim i} w_{ij} (f_i - f_j)\).
Quadratic Form: \(\bx^T \bL \bx = \sum_{(i,j) \in E} w_{ij} (x_i - x_j)^2\), with each undirected edge counted once.
For an undirected weighted graph with nonnegative weights, \(\bL\) is symmetric positive semidefinite and \(\bL\mathbf{1}=\bzero\).
Symmetry follows from \(w_{ij}=w_{ji}\). Using the quadratic form in the result above, \[ \begin{align} \bx^T\bL\bx = \sum_{(i,j)\in E} w_{ij}(x_i-x_j)^2 \geq 0. \end{align} \] Thus \(\bL\) is positive semidefinite. If \(\bx=\mathbf{1}\), every difference \(x_i-x_j\) is zero, and direct substitution gives \(\bL\mathbf{1}=\bzero\).
(Three-node path) For \(1-2-3\), \[ \begin{align} \bA= \begin{pmatrix} 0&1&0\\ 1&0&1\\ 0&1&0 \end{pmatrix}, \qquad \bL= \begin{pmatrix} 1&-1&0\\ -1&2&-1\\ 0&-1&1 \end{pmatrix}. \end{align} \] The zero eigenvector is \(\mathbf{1}\) because constant signals have no graph variation.
For a connected graph with \(0 = \lambda_1 \leq \lambda_2 \leq ... \leq \lambda_n\):
\(\lambda_1 = 0\) with eigenvector \(\mathbf{1}\).
Multiplicity of 0: Equals the number of connected components.
Fiedler Value (\(\lambda_2\)): Measures algebraic connectivity. \(\lambda_2 > 0\) iff graph is connected.
Use the result above to show \(\bL\mathbf{1}=\bzero\).
Derive \(\bx^T\bL\bx=\sum_{(i,j)\in E}w_{ij}(x_i-x_j)^2\) for edges counted once.
Conclude that \(\bL\) is positive semidefinite for an undirected graph.
Show that if a graph has two connected components, then there are two independent vectors in \(\mathcal{N}(\bL)\).
Symmetric: \(\bL_{\text{sym}} = \bD^{-1/2} \bL \bD^{-1/2}\). (Eigenvalues in \([0, 2]\)).
Random Walk: \(\bL_{\text{rw}} = \bI-\bA\bD^{-1}\) under the column-stochastic convention.
(Degree normalization) The unnormalized Laplacian can let high-degree vertices dominate cuts. Normalized Laplacians measure variation relative to vertex degree.
30.2 Spectral Clustering
Minimizing a graph cut (RatioCut) is NP-hard. Spectral methods relax this to an eigenvector problem:
Compute \(k\) smallest eigenvectors of \(\bL\) (starting from \(\bv_2\)).
Embed vertices in \(\fR^k\) using these eigenvectors.
Cluster embedding via \(k\)-means.
30.3 Random Walks and PageRank
Transition matrix \(\bP = \bA\bD^{-1}\) under the column-stochastic convention.
\(P_{ij} = w_{ij}/d_j\) is the probability of moving from \(j\) to \(i\).
Stationary Distribution: \(\boldsymbol{\pi}\) such that \(\bP\boldsymbol{\pi} = \boldsymbol{\pi}\). For undirected graphs, \(\pi_i = d_i / \sum d_j\).
Show that the columns of \(\bP=\bA\bD^{-1}\) sum to one.
For the path graph \(1-2-3\), compute \(\bP\).
Verify that \(\pi_i=d_i/\sum_j d_j\) satisfies \(\bP\boldsymbol{\pi}=\boldsymbol{\pi}\).
Models a random surfer on a directed web graph with teleportation: \[ \begin{align} \mathbf{G} = d \bS + \frac{1-d}{N} \mathbf{J}, \end{align} \]
\(d\) is the damping factor (standard: 0.85).
\(\bS\) is column-stochastic and handles dangling nodes.
\(\mathbf{J}\) is the all-ones matrix (teleportation).
Computation: PageRank vector \(\mathbf{r}\) is the dominant eigenvector of \(\mathbf{G}\), computed via power iteration.
(Dangling nodes) A page with no outgoing links gives a zero column before normalization. The standard fix replaces that column by the uniform probability vector before forming \(\bS\).
30.4 Exercises
Construct \(\bL\) for a 3-vertex path graph. Find its eigenvalues by hand.
Show that \(\bL \mathbf{1} = \bzero\) for any graph.
Prove \(\bL\) is positive semidefinite using the quadratic form.
Implement PageRank power iteration for a 10-node random graph.