TOPIC 2

Spectral and singular value decompositions

4 Introduction to spectral graph theory


Course: Math 535 - Mathematical Methods in Data Science (MMiDS)
Author: Sebastien Roch, Department of Mathematics, University of Wisconsin-Madison
Updated: Sep 21, 2020
Copyright: © 2020 Sebastien Roch


4.1 Matrices associated to graphs

A convenient way of specifying a graph is the following matrix representation.

Definition (Adjacency Matrix): Assume the undirected graph $G = (V,E)$ has $n = |V|$ vertices. The adjacency matrix $A$ of $G$ is the $n\times n$ symmetric matrix defined as

$$ \begin{align} A_{xy} = \begin{cases} 1 & \text{if $\{x,y\} \in E$}\\ 0 & \text{o.w.} \end{cases} \end{align} $$

$\lhd$

Triangle graph

(Source)

$$ A= \begin{pmatrix} 0 & 1 & 1\\ 1 & 0 & 1\\ 1 & 1 & 0 \end{pmatrix}. $$

$\lhd$

Definition (Incidence Matrix): The incidence matrix of an undirected graph $G = (V, E)$ is the $n \times m$ matrix $B$, where $n = |V|$ and $m =|E|$ are the numbers of vertices and edges respectively, such that $B_{ij} = 1$ if the vertex $i$ and edge $e_j$ are incident and 0 otherwise. $\lhd$

Incidence matrix

(Source)

$$ B = \begin{pmatrix} 1 & 1 & 1 & 0\\ 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 1 \end{pmatrix}. $$

$\lhd$

Definition (Oriented Incidence Matrix): An oriented incidence matrix of an (undirected) graph $G = (V, E)$ is the incidence matrix of an orientation of $G$. $\lhd$

(Source)

$\lhd$

In [2]:
g = complete_graph(3)
Out[2]:
{3, 3} undirected simple Int64 graph
In [3]:
A = adjacency_matrix(g)
Out[3]:
3×3 SparseArrays.SparseMatrixCSC{Int64,Int64} with 6 stored entries:
  [2, 1]  =  1
  [3, 1]  =  1
  [1, 2]  =  1
  [3, 2]  =  1
  [1, 3]  =  1
  [2, 3]  =  1
In [4]:
Array(A)
Out[4]:
3×3 Array{Int64,2}:
 0  1  1
 1  0  1
 1  1  0
In [5]:
g = smallgraph(:petersen)
A = Array(adjacency_matrix(g))
Out[5]:
10×10 Array{Int64,2}:
 0  1  0  0  1  1  0  0  0  0
 1  0  1  0  0  0  1  0  0  0
 0  1  0  1  0  0  0  1  0  0
 0  0  1  0  1  0  0  0  1  0
 1  0  0  1  0  0  0  0  0  1
 1  0  0  0  0  0  0  1  1  0
 0  1  0  0  0  0  0  0  1  1
 0  0  1  0  0  1  0  0  0  1
 0  0  0  1  0  1  1  0  0  0
 0  0  0  0  1  0  1  1  0  0
In [6]:
Array(incidence_matrix(g))
Out[6]:
10×15 Array{Int64,2}:
 1  1  1  0  0  0  0  0  0  0  0  0  0  0  0
 1  0  0  1  1  0  0  0  0  0  0  0  0  0  0
 0  0  0  1  0  1  1  0  0  0  0  0  0  0  0
 0  0  0  0  0  1  0  1  1  0  0  0  0  0  0
 0  1  0  0  0  0  0  1  0  1  0  0  0  0  0
 0  0  1  0  0  0  0  0  0  0  1  1  0  0  0
 0  0  0  0  1  0  0  0  0  0  0  0  1  1  0
 0  0  0  0  0  0  1  0  0  0  1  0  0  0  1
 0  0  0  0  0  0  0  0  1  0  0  1  1  0  0
 0  0  0  0  0  0  0  0  0  1  0  0  0  1  1

4.2 Laplacian matrix

Our main matrix of interest is the Laplacian matrix.

Definition (Laplacian Matrix): Let $G = (V,E)$ be a graph with vertices $V = \{1, \ldots, n\}$ and adjacency matrix $A \in \mathbb{R}^{n \times n}$. Let $D = \mathrm{diag}(\delta(1), \ldots, \delta(n))$ be the degree matrix. The Laplacian matrix associated to $G$ is defined as $L = D - A$. Its entries are

$$ l_{ij} = \begin{cases} \delta(i) & \text{if $i = j$}\\ -1 & \text{if $\{i,j\} \in E$}\\ 0 & \text{o.w.} \end{cases} $$

$\lhd$

Observe that the Laplacian matrix $L$ of a graph $G$ is symmetric:

$$ L^T = (D- A)^T = D^T - A^T = D - A $$

where we used that both $D$ and $A$ are themselves symmetric. The associated quadratic form is particularly simple and will play an important role.


Lemma (Laplacian Quadratic Form): Let $G = (V, E)$ be a graph with $n = |V|$ vertices. Its Laplacian matrix $L$ is PSD and furthermore we have the following formula for the Laplacian quadratic form

$$ \mathbf{x}^T L \mathbf{x} = \sum_{e = \{i,j\} \in E} (x_i - x_j)^2 $$

for any $\mathbf{x} = (x_1, \ldots, x_n)^T \in \mathbb{R}^n$.


Proof: Let $B$ be an oriented incidence matrix of $G$. We claim that $L = B B^T$. Indeed, for $i \neq j$, entry $(i,j)$ of $B B^T$ is a sum over all edges containing $i$ and $j$ as endvertices, of which there is at most one. When $\{i,j\} \in E$, that entry is $-1$, since one of $i$ or $j$ has a $1$ in the column of $B$ corresponding to $e$ and the other one has a $-1$. For $i = j$, letting $b_{xy}$ be entry $(x,y)$ of $B$,

$$ (B B^T)_{ii} = \sum_{e = \{x, y\} \in E: i \in e} b_{xy}^2 = \delta(i). $$

Thus, for any $\mathbf{x}$, we have $(B^T \mathbf{x})_k = x_v - x_u$ if the edge $e_k = \{u, v\}$ is oriented as $(u,v)$ under $B$. That implies

$$ \mathbf{x}^T L \mathbf{x} = \mathbf{x}^T B B^T \mathbf{x} = \|B^T \mathbf{x}\|^2 = \sum_{e = \{i,j\} \in E} (x_i - x_j)^2. $$

Since the latter is always nonnegative, it also implies that $L$ is PSD. $\square$

As a convention, we denote the eigenvalues of a Laplacian matrix $L$ by

$$ 0 \leq \mu_1 \leq \mu_2 \leq \cdots \leq \mu_n. $$

Another important observation:


Lemma ($\mu_1 = 0$): Let $G = (V, E)$ be a graph with $n = |V|$ vertices and Laplacian matrix $L$. The constant unit vector

$$ \mathbf{y}_1 = \frac{1}{\sqrt{n}} (1, \ldots, 1)^T $$

is an eigenvector of $L$ with eigenvalue $0$.


Proof: Let $B$ be an oriented incidence matrix of $G$ recall that $L = B B^T$. By construction $B^T \mathbf{y}_1 = \mathbf{0}$ since each column of $B$ has exactly one $1$ and one $-1$. So $L \mathbf{y}_1 = B B^T \mathbf{y}_1 = \mathbf{0}$ as claimed. $\square$

Grid graph

(Source)

In [5]:
g = grid([4,7])
Out[5]:
{28, 45} undirected simple Int64 graph
In [6]:
function rand_locs(g)
    return rand(nv(g)), rand(nv(g)) # random x and y coord for each vertex
end
Out[6]:
rand_locs (generic function with 1 method)
In [7]:
(x, y) = rand_locs(g)
hcat(x,y)
Out[7]:
28×2 Array{Float64,2}:
 0.191692   0.606737
 0.989004   0.352409
 0.189396   0.51508
 0.816165   0.587919
 0.436631   0.0819465
 0.50328    0.586298
 0.3384     0.835183
 0.740025   0.818151
 0.754872   0.119381
 0.699313   0.38022
 0.437357   0.593008
 0.771573   0.61867
 0.0918346  0.227644
 ⋮          
 0.2729     0.787315
 0.0667081  0.801595
 0.391096   0.387632
 0.14777    0.355164
 0.247434   0.194785
 0.328025   0.0842352
 0.406501   0.271673
 0.452194   0.910649
 0.699653   0.304761
 0.736827   0.244049
 0.791831   0.205615
 0.854796   0.181293
In [9]:
gplot(g, layout=rand_locs)
Out[9]:
In [12]:
function spec_locs(g)
    L = Array(laplacian_matrix(g)) # laplacian L of g
    F = eigen(L) # spectral decomposition
    v = F.vectors # eigenvectors
    return v[:,2], v[:,3] # returns 2nd and 3rd eigenvectors
end
Out[12]:
spec_locs (generic function with 1 method)
In [13]:
gplot(g, layout=spec_locs)
Out[13]:

Lemma (Laplacian and Connectedness): If $G$ is connected, then the Laplacian eigenvalue $\mu_2 > 0$.


Proof: Let $G = (V, E)$ with $n = |V|$ and let $L = \sum_{i=1}^n \mu_i \mathbf{y}_i \mathbf{y}_i^T$ be a spectral decomposition of its Laplacian $L$ with $0 = \mu_1 \leq \cdots \leq \mu_n$. Suppose by way of contradiction that $\mu_2 = 0$. Any eigenvector $\mathbf{y} = (y_{1}, \ldots, y_{n})^T$ with $0$ eigenvalue satisfies $L \mathbf{y} = \mathbf{0}$ by definition. By the Laplacian Quadratic Form Lemma then

$$ 0 = \mathbf{y}^T L \mathbf{y} = \sum_{e = \{i, j\} \in E} (y_{i} - y_{j})^2. $$

In order for this to hold, it must be that any two adjacent vertices $i$ and $j$ have $y_{i} = y_{j}$. Furthermore, because $G$ is connected, between any two of its vertices $u$ and $v$ - adjacent or not - there is a path $u = w_0 \sim \cdots \sim w_k = v$ along which the $y_{w}$'s must be the same. Thus $\mathbf{y}$ is a constant vector. But that is a contradiction since the eigenvectors $\mathbf{y}_1, \ldots, \mathbf{y}_n$ are in fact linearly independent, so that $\mathbf{y}_1$ and $\mathbf{y}_2$ cannot both be a constant vector. $\square$


Lemma (Number of Connected Components): If $\mu_{k+1}$ is the smallest nonzero Laplacian eigenvalue of $G$, then $G$ has $k$ connected components.


We will be interested in more quantitative results of this type. Before proceeding, we start with a simple observation. By our proof of the Spectral Theorem, the largest eigenvalue $\mu_n$ of the matrix Laplacian $L$ is the solution to the optimization problem

$$ \mu_n = \max\{\langle \mathbf{x}, L \mathbf{x}\rangle:\|\mathbf{x}\| = 1\}. $$

Such extremal characterization is useful in order to bound the eigenvalue $\mu_n$, since any choice of $\mathbf{x}$ with $\|\mathbf{x}\| =1$ gives a lower bound through the quantity $\langle \mathbf{x}, L \mathbf{x}\rangle$. That perspective will be key to our application to graph partitioning.


Lemma (Laplacian and Degree): Let $G = (V, E)$ be a graph with maximum degree $\bar{\delta}$. Let $\mu_n$ be the largest eigenvalue of its matrix Laplacian $L$. Then

$$ \mu_n \geq \bar{\delta}+1. $$

Proof idea: As explained before the statement of the lemma, it suffices to find a good test unit vector $\mathbf{x}$ to plug into $\langle \mathbf{x}, L \mathbf{x}\rangle$. A clever choice does the trick.

In [14]:
A = [0 1 1 0 0; 1 0 1 0 0; 1 1 0 0 0; 0 0 0 0 1; 0 0 0 1 0]
Out[14]:
5×5 Array{Int64,2}:
 0  1  1  0  0
 1  0  1  0  0
 1  1  0  0  0
 0  0  0  0  1
 0  0  0  1  0
In [15]:
degrees = reshape(sum(A,dims=1),:)
Out[15]:
5-element Array{Int64,1}:
 2
 2
 2
 1
 1
In [16]:
D = Diagonal(degrees)
Out[16]:
5×5 Diagonal{Int64,Array{Int64,1}}:
 2  ⋅  ⋅  ⋅  ⋅
 ⋅  2  ⋅  ⋅  ⋅
 ⋅  ⋅  2  ⋅  ⋅
 ⋅  ⋅  ⋅  1  ⋅
 ⋅  ⋅  ⋅  ⋅  1
In [17]:
L = D - A
Out[17]:
5×5 Array{Int64,2}:
  2  -1  -1   0   0
 -1   2  -1   0   0
 -1  -1   2   0   0
  0   0   0   1  -1
  0   0   0  -1   1
In [18]:
F = eigen(L)
F.values
Out[18]:
5-element Array{Float64,1}:
 1.1102230246251565e-15
 1.3322676295501878e-15
 2.0
 3.0
 3.0

Observe that (up to numerical error) there are two $0$ eigenvalues and that the largest eigenvalue is greater or equal than the maximum degree plus one.

In [19]:
g = smallgraph(:petersen)
L = Array(laplacian_matrix(g))
Out[19]:
10×10 Array{Int64,2}:
  3  -1   0   0  -1  -1   0   0   0   0
 -1   3  -1   0   0   0  -1   0   0   0
  0  -1   3  -1   0   0   0  -1   0   0
  0   0  -1   3  -1   0   0   0  -1   0
 -1   0   0  -1   3   0   0   0   0  -1
 -1   0   0   0   0   3   0  -1  -1   0
  0  -1   0   0   0   0   3   0  -1  -1
  0   0  -1   0   0  -1   0   3   0  -1
  0   0   0  -1   0  -1  -1   0   3   0
  0   0   0   0  -1   0  -1  -1   0   3
In [20]:
F = eigen(L)
F.values
Out[20]:
10-element Array{Float64,1}:
 2.6645352591003757e-15
 1.9999999999999982
 1.9999999999999982
 1.9999999999999984
 2.0
 2.0000000000000027
 4.999999999999998
 5.000000000000001
 5.000000000000002
 5.0000000000000036