A Tutorial on Spectral Clustering

关于谱聚类的文章，主要包含了谱聚类和拉普拉斯矩阵的内容。最近研究 GCN 的原理的时候发现了这篇论文。
Von Luxburg U. A tutorial on spectral clustering[J]. Statistics and Computing, 2007, 17(4): 395-416.
原文链接：A Tutorial on Spectral Clustering

2 Similarity graphs

给定一组数据点 $x_1, …, x_n$ 还有数据点 $x_i$ 和 $x_j$ 之间的相似性 $s_{ij} \geq 0$，聚类的目标是将样本点分到几个组中，组的样本相似，不同组的样本不相似。如果没有更多的信息，使用 similarity graph 表示数据是一个好的方法，$G = (V, E)$。每个顶点 $v_i$ 表示一个数据点 $x_i$。如果相似度 $s_{ij}$ 是正的，且大于一个确定的阈值，那么两个顶点相连，边的权重为 $s_{ij}$。聚类的问题可以使用相似度图重新定义为：我们想找到一个划分方案，使得不同组之间的边有很小的权重（意味着不同类簇间的样本不相似），同组内的权重较高（意味着同一类簇的样本相似）。我们首先引入一些符号和性质。

2.1 Graph notation

$G = (V, E)$ 是无向图，顶点集 $V = \lbrace v_1, …, v_n \rbrace $。我们假设图 $G$ 是带权的，边有非负权重 $w_{ij} \geq 0$。带权的邻接矩阵是 $W = (w_{ij})_{i,j=1,…,n}$。如果 $w_{ij} = 0$，表示顶点 $v_i$ 和 $v_j$之间没有边。因为 $G$ 是无向的，所以 $w_{ij} = w_{ji}$。顶点 $v_i \in V$ 的度定义为：

$$d_i = \sum^n_{j = 1} w_{ij}.$$

事实上，这个加和只会在所有和 $v_i$ 邻接的顶点上做， 因为和其他的顶点之间的边权重为0。度矩阵 $D$ 定义为对角矩阵，对角线上是度 $d_1, …, d_n$。给定顶点的子集 $A \subset V$，它的补集 $V \ \backslash \ A$ 表示为 $\bar{A}$。定义一个指示向量 $1_A = (f_1, \dots f_n)’ \in \mathbb{R}^n$，如果 $v_i \in A$，$f_i = 1$，否则 $f_i = 0$。我们在做求和的时候，比如 $\sum_{i \in A} w_{ij}$， 把 $\lbrace i \mid v_i \in A \rbrace $ 简记为 $i \in A$。对于两个不相交的集合 $A, B \subset V$，定义：

$$W(A, B) := \sum_{i \in A, j \in B} w_{ij}.$$

我们考虑两个不同的方式来描述子集 $A \subset V$ 的“大小”：

$$\vert A \vert := A 的顶点数\\ \text{vol}(A) := \sum_{i \in A} d_i.$$

直观上来讲，$\vert A \vert$ 通过顶点数描述了 $A$ 的大小，但是 $\text{vol}(A)$ 通过对 $A$ 中所有的边进行加和得到。如果 $A$ 中的两个结点可以通过一条路径连接，而且中间的点都在 $A$ 中，那么称子集 $A \subset V$ 是连通的。如果子集是连通的，且顶点集 $A$ 和 $\bar{A}$ 之间没有结点相连，那么称 $A$ 是一个连通分量。如果 $A_i \cap A_j = \emptyset$ 且 $A_1 \cup \dots \cup A_k = V$，那么非空集合 $A_1, \dots, A_k$ 是图的一个划分。

2.2 Different similarity graphs

有一些流行的方法对顶点间的相似度或距离构建图。构建相似度图的目标是对样本之间的局部邻居关系建模。

The $\varepsilon$-neighborhood graph: 我们把距离小于 $\varepsilon$ 的样本连起来。因为连接起来的样本点基本是一个尺度的，考虑边的权重不会增加更多的信息。所以，$\varepsilon$-邻居图通常是无权图。

$k$-nearest neighbor graphs: 如果 $v_j$ 是 $v_i$ 的 $k$-近邻邻居，那目标是连接 $v_i$ 和 $v_j$。但是，这个定义会得到一个有向图，因为邻居间的关系是非对称的。有两种方法变成有向。第一种是忽略边的方向，也就是用无向边连接。结果通常称为 $k$-近邻邻居图。第二种方法是如果两个顶点互为对方的 $k$-近邻邻居，那么相连。得到的图称为 mutual $k$-nearest neighbor graph。这两种图的边都是顶点的相似度。

The fully connected graph: 我们简单的连接有着正的相似度的顶点，边的权重就是相似度 $s_{ij}$。因为图应该表示局部邻居关系，这个构建方法只在相似度能体现局部邻居关系时才有效。举个相似度函数的例子，高斯相似度函数 $s(x_i, x_j) = \exp(- \Vert x_i - x_j \Vert ^ 2 / (2 \sigma^2))$，参数 $\sigma$ 控制了邻居的宽度。这个参数和 $\varepsilon$-邻居图中的 $\varepsilon$ 的角色差不多。

上面提到的图是谱聚类中常用的。据我们所知，相似度图如何影响谱聚类的结果还不为所知。不同的图的表现形式我们会在第八节讨论。

3 Graph Laplacians and their basic properties

谱聚类的主要工具是图拉普拉斯矩阵。有一个领域致力研究这些矩阵，称为谱图理论(e.g., see Chung, 1997)。我们这节定义不同的拉普拉斯矩阵，指出他们的重要性质。我们会仔细的对比不同的拉普拉斯矩阵。注意，事实上没有一个统一的说法说哪个矩阵就是 “graph Laplacian”。通常，每个作者都称他们使用的矩阵是拉普拉斯矩阵。因此，在读关于拉普拉斯矩阵的论文的时候需要注意。

假设 $G$ 是无向带权图，权重矩阵 $W$，$w_{ij} = w_{ji} \geq 0$。使用一个矩阵的特征向量时，我们没有必要假设他们是归一化的。举个例子，常向量 $1$ 和他的倍数 $a1$ 在 $a = \not 0$ 的时候被认为是相同的特征向量。特征值总时升序排列，而且会有多重性。前 $k$ 个特征值，我们指的是前 $k$ 个最小的特征值。

3.1 The unnormalized graph Laplacian

非归一化的图拉普拉斯矩阵定义为：

$$L = D - W.$$

关于它的性质的论文在 Mohar(1991, 1997)。下面性质是谱聚类需要的性质：

Proposition 1 (Properties of $L$) 拉普拉斯矩阵满足以下性质：

1. 对于每个向量 $f \in \mathbb{R}^n$，我们有：

$$f'Lf = \frac{1}{2} \sum^n_{i,j=1} w_{ij}(f_i - f_j)^2.$$

1. $L$ 是对称且半正定的。
2. $L$ 最小的特征值是 $0$，对应的特征向量是常向量 $1$。
3. $L$ 有 $n$ 个非负实数特征值 $0 = \lambda_1 \leq \lambda_2 \leq \dots \lambda_n$。

Proof.
Part (1)：由 $d_i$ 的定义得：

$$\begin{aligned} f'Lf &= f'Df - f'Wf = \sum^n_{i=1}d_i f^2_i - \sum^n_{i,j=1} f_i f_j w_{ij}\\ &=\frac{1}{2} \Bigg( \sum^n_{i=1} d_i f^2_i - 2 \sum^n_{i,j=1} f_i f_j w_{ij} + \sum^n_{j=1} d_j f^2_j \Bigg) = \frac{1}{2} \sum^n_{i,j=1} w_{ij} (f_i - f_j)^2. \end{aligned}$$

Part (2)：$L$ 的对称性是因为 $W$ 和 $D$ 是对称的。半正定是 Part (1) 的结果，对于任意的 $f \in \mathbb{R}^n$，$f’Lf \geq 0$。

Part (3)：显而易见。

Part (4)：由(1) 和 (3) 推出。

注意：非归一化的拉普拉斯矩阵不依赖于邻接矩阵 $W$ 的对角线上的元素。邻接矩阵非对角线上的元素得到非归一化的拉普拉斯矩阵。图中的自连接不会改变对应的拉普拉斯矩阵。
（这里说白了就是，拉普拉斯矩阵非对角线位置上的元素是邻接矩阵对应位置的元素的相反数，如果顶点加自连接，那么度矩阵就会对应地增加，D-W在对角线上还是一样的数，不会变）

非归一化的拉普拉斯矩阵的特征值和特征向量可以用于描述图的很多性质，参见 Mohar(1991, 1997)。对于谱聚类来说一个重要的性质是：

Proposition 2 (Number of connected components and the spectrum of $L$) 图 $G$ 是无向非负权重的图。拉普拉斯矩阵的特征值 $0$ 的多重性 $k$ 等于图中的连通分量 $A_1, \dots, A_k$ 的数量。特征值 $0$ 的特征空间通过指示向量 $1_{A_1}, \dots, 1_{A_k}$ 生成。

Proof. 我们先以 $k = 1$ 为例，也就是说只有一个连通图。假设 $f$ 是特征值 $0$ 对应的特征向量。我们知道：

$$0 = f'Lf = \sum^n_{i,j=1} w_{ij} (f_i - f_j)^2.$$

因为权重 $w_{ij}$ 是非负的，如果所有的项 $w_{ij} (f_i - f_j)^2$ 都消失了，这个和就会很小。因此，如果两个顶点相连（权重大于0），那么 $f_i$ 需要等于 $f_j$。我们可以发现，对于所有顶点 $f$ 需要是一个相同的常数，且这些点可以通过一条路径相连。此外，因为无向图内连通分量所有的顶点可以通过一条路径相连，$f$ 对于整个连通分量来说需要是一个常数。在只有一个连通分量的图中，我们因此只有一个常向量 $1$ 作为特征向量，对应的特征值为 $0$，显然这个向量就是这个连通分量的指示向量。

现在考虑 $k$ 个连通分量。为了不失一般性，我们假设顶点是根据连通分量排序的。这样，邻接矩阵 $W$ 有一个块对角形式，对于矩阵 $L$ 也是如此：

$$L = \begin{pmatrix} L_1 & & & \\ & L_2 & & \\ & & \ddots & \\ & & & L_k \end{pmatrix}$$

注意：块 $L_i$ 是一个关于它自己的拉普拉斯矩阵，也就是对应第 $i$ 个子图的拉普拉斯矩阵。在这个对角都是块矩阵的例子中，我们知道 $L$ 的谱是所有的 $L_i$ 的谱的并集，对应的 $L$ 的特征向量是 $L_i$ 的特征向量，其他方块的位置都是0.因为每个 $L_i$ 是一个连通图的拉普拉斯矩阵，我们知道每个 $L_i$ 在第 $i$ 个连通分量上，有特征值 $0$，且多重性为 $1$，对应的特征向量常向量。因此，矩阵 $L$ 的特征值 $0$ 的个数就等于连通分量数，而且对应的特征向量是连通分量的指示向量。

3.2 The normalized graph Laplacians

在文献中有两个归一化的拉普拉斯矩阵。两个矩阵紧密相连，定义如下：

$$\begin{aligned} & L_{sym} := D^{-1/2} L D^{-1/2} = I - D^{-1/2} W D^{-1/2}\\ & L_{rw} := D^{-1} L = I - D^{-1} W. \end{aligned}$$

我们将第一个矩阵表示为 $L_{sym}$，因为它是一个对称阵，第二个矩阵表示为 $L_{rw}$，因为它和随机游走有关。接下来我们总结一下这两个矩阵的性质。关于归一化的拉普拉斯矩阵的引用在 Chung (1997)。

Proposition 3 (Properties of $L_{sym}$ and $L_{rw}$) 归一化的拉普拉斯矩阵满足以下性质：

1. 对于每个 $f \in \mathbb{R}^n$，我们有：

$$f' L_{sym} f = \frac{1}{2} \sum^n_{i,j=1} w_{ij} \Bigg( \frac{f_i}{\sqrt{d_i}} - \frac{f_j}{\sqrt{d_j}} \Bigg)^2.$$

1. $\lambda$ 是 $L_{rw}$ 的一个特征值，对应的特征向量 $u$，当且仅当 $\lambda$ 是 $L_{sym}$ 的一个特征值且对应的特征向量 $w = D^{1/2}u$。
2. $\lambda$ 是 $L_{rw}$ 的一个特征值，对应的特征向量 $u$，当且仅当 $\lambda$ 和 $u$ 是 generalized eigenproblem $Lu = \lambda Du$ 的解。
3. $0$ 是 $L_{rw}$ 的特征值，常向量 $1$ 是特征向量。$0$ 是 $L_{sym}$ 的特征值且特征向量是 $D^{1/2}1$。
4. $L_{sym}$ 和 $L_{rw}$ 是半正定的，有 $n$ 个非负的实数特征值 $0 = \lambda_1 \leq \dots \leq \lambda_n$。