这里主要对谱聚类做一个简单介绍。谱聚类方法本身和图神经网络的关系不大，但是它作为一个图拉普拉斯矩阵的重要应用，能够帮助我们更好的理解拉普拉斯矩阵。

谱聚类

要了解谱聚类, 首先要对谱图论的一些基本概念有所了解, 主要的就是图Laplacian矩阵相关的基本知识, 具体可以参考这里的入门介绍. 这里我们只对必要的概念做一个回顾.

Laplacian矩阵

对于一个图来说, 它的非标准化Laplacian矩阵定义为:

$L=D-W$

其中$D$为主对角线矩阵, 其对角线元素等于该节点在图中的度. $W$则为邻接矩阵.

这样一个矩阵有以下性质:

对于任意$f\in\mathbb{R}^n$, 有$f^{T} L f=\frac{1}{2}\sum_{i}^{n}$.
$L$是对称半正定矩阵.
$L$最小的特征值为0, 其对应的特征向量为一个元素全为1的向量.
$L$有非负的实值特征值$0=\lambda1 = \lambda{2} = \cdots = \lambda_{n}$.

具体的证明就不详细展开了.

下面给出一个定理:

定理令$G$为一个无向图, 且图中边的权值都是非负的. 那么该图对应的Laplacian矩阵的值为0的特征值重数$k$就等于该图的联通分部$A_1, …, A_k$数量.

Graph cut视角

从graph cut的视角来看待聚类问题，其实就是找一个图的分割，使得不同组之间的边的权重很小而组内的边的权重很大。
形式化的来说，对于两个组$A, B$，令$W(A, B) :=\sum{i \in A, j \in B} w{i j}$ ，$\bar{A}$为$A$的补集. 对于$k$分割而言, 简单的最小割方法可以通过最小化以下式子来实现:

$\operatorname{cut}\left(A_{1}, \ldots, A_{k}\right) :=\frac{1}{2} \sum_{i=1}^{k} W\left(A_{i}, \overline{A}_{i}\right)$

对$k=2$的情况,这种方法可以有一定效果, 但是这个方法在实际使用中通常无法令人满意. 在很多情况下, 该方法的结果会将一个个单独的节点和图的其余部分分开来, 虽然这可以达到最小化上式的目的, 但是显然这不是我们想要的效果. 因此, 有两种常见的对上述目标函数的改进,分别是RatioCut和Ncut:

$\begin{array}{l}{\text { RatioCut }\left(A_{1}, \ldots, A_{k}\right) :=\frac{1}{2} \sum_{i=1}^{k} \frac{W\left(A_{i}, \overline{A}_{i}\right)}{\left|A_{i}\right|}=\sum_{i=1}^{k} \frac{\operatorname{cut}\left(A_{i}, \overline{A}_{i}\right)}{\left|A_{i}\right|}} \\ {\operatorname{Ncut}\left(A_{1}, \ldots, A_{k}\right) :=\frac{1}{2} \sum_{i=1}^{k} \frac{W\left(A_{i}, \overline{A}_{i}\right)}{\operatorname{vol}\left(A_{i}\right)}=\sum_{i=1}^{k} \frac{\operatorname{cut}\left(A_{i}, \overline{A}_{i}\right)}{\operatorname{vol}\left(A_{i}\right)}}\end{array}$

二者都是通过cluster的规模来对Cut做约束, RatioCut使用了每个簇的节点数量, 而Ncut则使用了每个簇边权重和. 这样就可以克服上面节点划分时对小规模cluster的倾向, 实际上这两种方法都倾向于更平衡的分割.

可惜的是, 这种目标函数定义下的问题变成了一个NP-hard的问题. 因此我们需要将条件放宽, 接下来说明如何通过放宽条件, 将graph-cut问题转化为spectral clustering.

Ratio Cut for k=2

我们从Ratio Cut入手, 先来讨论最简单的$k=2$的情况, 假设我们的划分一个簇为$A$, 由于只有两簇, 另一个簇就是它的补集$\bar{A}$, 令$f$为指示向量, 其中的第$i$元素代表了节点$i$所属的簇. 并令:

$f_{i}=\left\{\begin{array}{ll}{\sqrt{|\overline{A}| /|A|}} & {\text { if } v_{i} \in A} \\ {-\sqrt{|A| /|\overline{A}|}} & {\text { if } v_{i} \in \overline{A}}\end{array}\right.$

接着引入Laplacian矩阵, 可以得到其和RatioCut的关系.

$\begin{aligned} f^{T} L f &=\frac{1}{2} \sum_{i, j=1}^{n} w_{i j}\left(f_{i}-f_{j}\right)^{2} \\ &=\frac{1}{2} \sum_{i \in A, j \in \overline{A}} w_{i j}\left(\sqrt{\frac{|A|}{|A|}}+\sqrt{\frac{|A|}{|\overline{A}|}}\right\}^{2}+\frac{1}{2} \sum_{i \in \overline{A}, j \in A} w_{i j}\left(-\sqrt{\frac{|A|}{|A|}}-\sqrt{\frac{|A|}{|\overline{A}|}}\right)^{2} \\ &=\operatorname{cut}(A, \overline{A})\left(\frac{|A|+|\overline{A}|}{|A|}+2\right) \\ &=\operatorname{cut}(A, \overline{A})\left(\frac{|A|+|\overline{A}|}{|A|}+\frac{|A|+|\overline{A}|}{|\overline{A}|}\right) \\ &=|V| \cdot \operatorname{Ratio} \operatorname{Cut}(A, \overline{A}) \end{aligned}$

那么, 由上式可以得出,优化RatioCut就是优化$f^TLf$.

接着, 不难观察到$f$的两个性质:

$\sum_{i=1}^nf_i = 0$
$|f|^2=n$

那我们的问题就转化为一个带约束离散优化问题:　　

$\min_{A \subset V} f^Ｔ L f \text { subject to } f \perp \mathbb{1}, \|f\|=\sqrt{n}$

这个问题仍然是一个NP-hard问题．　发现此处$f_i$的取值只能为离散值（其实只有两个取值），我们可以进一步放松条件，允许其取任意值．这种情况下，　由Rayleigh-Ritz定理(有兴趣的可以参考后面第二篇参考文献的Section 5.5.2.)可以得到$f$可以是$L$第二小的特征值对应的特征向量.

有了$f$后聚类就比较方便了,最简单的做法就是将其按$f_i$的正负性来分类. 但是当$k>2$后, 一种更普遍的做法是将$f$作为特征值, 然后对其施行k-means聚类方法. 这也正是非标准化的谱聚类 unnormalized spectral clustering.

任意k的Ratio Cut

类似上面的步骤, 我们也可以推导任意k取值下的Raio Cut. 同样的, 我们定义$k$个指示向量为$h_j$:

$h_{i, j}=\left\{\begin{array}{ll}{1 / \sqrt{\left|A_{j}\right|}} & {\text { if } v_{i} \in A_{j}} \\ {0} & {\text { otherwise }}\end{array}\right.$

令指示向量组成的矩阵为$H\in \mathbb{R}^{n\times k}$ , 那么由

$h_{i}^{T} L h_{i}=\frac{\operatorname{cut}\left(A_{i}, \overline{A}_{i}\right)}{\left|A_{i}\right|}$$ 可以得到 $$h_{i}^{T} L h_{i}=\left(H^{T} L H\right)_{i i}$

接着容易推出RationCut和矩阵$H$的关系:

$\operatorname{RatioCut}\left(A_{1}, \ldots, A_{k}\right)=\sum_{i=1}^{k} h_{i}^{T} L h_{i}=\sum_{i=1}^{k}\left(H^{T} L H\right)_{i i}=\operatorname{Tr}\left(H^{T} L H\right)$

其中$\operatorname{Tr}$为矩阵的迹, 那么也容易得出目标函数, 结合上一节类似的放松技巧, 我们的问题转为:

$\min _{H \in \mathbb{R}^{n} \times k} \operatorname{Tr}\left(H^{T} L H\right) \text { subject to } H^{T} H=I$

类似的, 上述问题的求解, 也可令$H$为Laplacian矩阵$L$的前$k$个特征向量来解决.

Ncut

有了前面的铺垫, Ncut的推导也顺理成章, 这里就不赘述了. 但是, 和之前不同的是, 这里推导出来的使用的是标准化后Laplacian矩阵,即$D^{-1 / 2} L D^{-1 / 2}$

Relaxiation 方法

上述这种放宽条件的方法, 虽然使得问题难度降低可以顺利解决,但是其最大的不足在于得出的解的效果没有理论保证．

Random Walks视角

这里我们从随机游走的视角来看一下谱聚类. 图上的随机游走就是从途中某个节点跳到其他节点的随机过程. 那么谱聚类就可以看做找到一个图的分割, 使得随机游总尽量在同一个簇内待的长而很少从一个簇跳到另一个簇.

对于随机游走, 首先需要构建转移矩阵, 令$p{ij}$表示从节点$i$跳到节点$j$的概率为二者边的权重除以节点$i$的度$p{i j} :=w{i j} / d{i}$, 那么整个转移矩阵可以写成:

$P=D^{-1} W$

对于非二分连通图,随机游走的过程总是会产生一个唯一的稳定分布$\pi=\left(\pi{1}, \dots, \pi{n}\right)^{T}$, 其中 $\pi_{i}=d_{i} / \operatorname{vol}(V)$ .
观察$P$的形式, 容易发现它和之前定义的一种标准化的Laplacian$L{rw}$很相似, 实际上$L{\mathrm{rw}}=I-P$. 那么假设$L{rw}$的某个特征值/向量为$\lambda, u$, 那么对应的$P$的特征值/向量就是$1-\lambda, u$. 那么$P$最大的特征值也就是$L{rw}$最小的特征值.

Random Walks和谱聚类

事实上, 可以从两个方面来考虑RandomWalks和谱聚类的关系.

Random walks和Ncut

首先将Random walks和Ncut联系起来. 一个容易证明的定理是:　

定理　令$G$为一个非二分联通图．假设我们在其上从$X0$开始进行随机游走并到达稳定分布$\pi$，　对于节点集的两个不相交子集$A,B \subset V$, 令$P(B | A) :=P\left(X{1} \in B | X_{0} \in A\right)$, 那么有:

$\operatorname{Ncut}(A, \overline{A})=P(\overline{A} | A)+P(A | \overline{A})$

将Random walks和Ncut等价转换后,那么随机游走的收敛就等同于了谱聚类的收敛.

通勤距离

图上从节点$v_i$到$v_j$的通勤距离通常定义为从$v_i$出发,随机游走到$v_j$再回到$v_i$的期望时间.

下面我们借助通勤距离的概念来理解谱聚类能够work的原因.

通勤距离有许多好的性质, 例如:

通勤距离往往不只依赖两点间最短的路径, 而是和最短的那一批路径都相关.
同样是由较短的路径连接的两个点, 这两个点周围的密度相近时的通勤距离会比两点周围密度较为不同时的的通勤距离短.

可以看出这些性质都挺适合聚类的应用场景.

更棒的是, 图上通勤距离的计算通过图Laplacian的伪逆$L^\dagger$来获得.

为了计算伪逆, 我们先将Laplacian矩阵分解$L=U \Lambda U^{T}$, 其中$U$为特征向量矩阵, $\Lambda$为主对角线为特征值的矩阵. 由于Laplacian矩阵一定有特征值0, 所以$L$是不可逆的, 所以只能计算其伪逆$L^{\dagger} :=U \Lambda^{\dagger} U^{T}$, 其中$L^\dagger$的各个元素为$1/\lambdai$（如果$\lambda_i=0$则设为$0$). 那么伪逆就是: $l{i j}^{\dagger}=\sum{k=2}^{n} \frac{1}{\lambda{k}} u{i k} u{j k}$. 这个矩阵也是对称且半正定的.

关于通勤距离, 有如下定理:
定理令$G=(V,E)$为无向联通图, 那么它的通勤距离和伪逆之间有:

$c_{i j}=\operatorname{vol}(V)\left(l_{i i}^{\dagger}-2 l_{i j}^{\dagger}+l_{j j}^{\dagger}\right)=\operatorname{vol}(V)\left(e_{i}-e_{j}\right)^{T} L^{\dagger}\left(e_{i}-e_{j}\right)$

其中$e_i$为$i-th$为1,其余位为0的unit vector(节点的onehot表示).

通过通勤距离的形式可以看出, $\sqrt{c_{ij}}$可以被看做图上点之间的某种欧氏距离. 那么不禁会想, 我们是否可以将图上的第$i$点做一个embedding到$z_i\in\mathbb{R}^n$, 并使两点新的表征下的之间的欧氏距离就是它们的通勤距离呢?

实际上可以令$zi$为矩阵$U(\Lambda^{\dagger})^{1/2}$的第$i$行, 那么就有$\left\langle z{i}, z{j}\right\rangle= e{i}^{T} L^{\dagger} e{j}$ 以及 $c{i j}=\operatorname{vol}(V)\left|z{i}-z{j}\right|^{2}$.

做了这种embedding之后, 图中每个节点也就可以用一个向量来表征,如果我们要做聚类的话, 就可以接一个kmeans算法.

那么这种通勤距离嵌入(commute time embedding)和谱聚类有什么关系呢. 在谱聚类中, 节点的表征$y_i$为矩阵$U$的行, 而这里$z_i$是$U(\Lambda^{\dagger})^{1/2}$的行, 它们差别有两点:

后者的表征是随图Laplacian的逆特征值缩放.
前者是取前$k$列作为特征, 后者则是取所有列.

但是总体来看, 尽管存在着不同, 但是二者还较为相似, 因此通过研究通勤距离, 也可以帮助我们理解谱聚类. 然而二者更深层次的关联, 还有待研究.

扰动理论视角

扰动理论(perturbation theory)研究的是我们给某个矩阵加上一个轻微的扰动$H$后它的特征值和特征向量的变化, 扰动后的矩阵就是$\tilde{A} :=A+H$.

如何将扰动理论应用到谱聚类中呢?　
不妨考虑这样一个理想情况，　即各个簇之间的相似度均为0, 此时, 如果我们选Laplacian矩阵的前k列作为指示向量, 那么对于每个节点, 它的表征$y_{i} \in \mathbb{R}^{k}$的形式应该是$(0, \dots, 0,1,0, \ldots 0)^{T} \in \mathbb{R}^{k}$, 其中1的位置就指示了该节点所属的簇. 在这种理想情况下, Kmeans算法可以将其很好的分类出来.

当然, 理想情况现实中基本无法实现, 那么接着考虑一种近乎理想情况, 这时不同簇之间点的相似度不完全为0(但是仍然较小). 扰动理论告诉我们这种情况下, 特征向量的值和理想情况下的特征向量的值应该非常接近. 因此, 如果扰动不是很大的话, kmeans算法依然可以将其很好的聚类.

扰动理论

扰动理论中, 常用canonical angles来衡量两个子空间的距离. 令 $\mathcal{V}1$, $\mathcal{V}_2$为两个子空间, 而$V_1, V_2$为这两个空间的正交基, 那么两个子空间的canonical angles的余弦值就是矩阵$V_1^TV_2$的奇异值, 记作$\Theta\left(V{1}, V_{2}\right)$.

接着介绍在扰动理论中一个很重要的定理是Davis-Hahan定理:　

Davis-Kahan定理 令$A, H \in \mathbb{R}^{n \times n}$均为对称矩阵, $|\cdot|$为Frobenus Norm. 令扰动后的矩阵为$\tilde{A} :=A+H$. 令$S{1} \subset \mathbb{R}$表示区间 , 而$\sigma{S{1}}(A)$就是该区间内包含的$A$的特征值集合, 这些特征值对应的特征空间. $\sigma{S{1}}(\tilde{A})$ 和 $\tilde{V}{1}$也是类似的定义.
令$S_1$和$A$不包含在$S_1$内的谱的距离为:

$\delta=\min \left\{|\lambda-s| ; \lambda\quad \text{eigenvalue of }A, \lambda \notin S_{1}, s \in S_{1}\right\}$

那么对于子空间,他们的的距离$d\left(V{1}, \tilde{V}{1}\right) :=\left|\sin \Theta\left(V{1}, \tilde{V}{1}\right)\right|$有上界:

$d\left(V_{1}, \tilde{V}_{1}\right) \leq \frac{\|H\|}{\delta}$

应用在谱聚类中, 令扰动Laplacian及其特征值为$\tilde{L} \quad \tilde{\lambda}{1}, \ldots, \tilde{\lambda}{n}$. 接着最重要的一步就是选择$S1$使得矩阵$L$和$\tilde{L}$的前k个特征值都被包含在内. 显然, 如果扰动越小或者$|\lambda_k-\lambda{k+1}|$越大, 就越容易选取$S1$. 假设成功选到了这样一个集合, 那么Davis-Kahan定理告诉我们, 矩阵$L$和$\tilde{L}$特征值非常接近, 它们的差值上界为$\frac{|H|}{\delta}$. 扰动后的矩阵和原矩阵的相似程度取决于$H$的范数以及$S_1$和$L$第$k+1$个特征值$\lambda{k+1}$的距离$\delta$.
如果我们取集合$S1$为区间$[0, \lambda_k]$, 那么$\delta$的取值就和谱间隔(spectral gap)$|\lambda{k+1}-\lambda_k|$相关. 这种eigengap越大, Laplacian的特征向量和理想情况越接近, 谱聚类效果也越好.

当然, 当$H$过大或者eigengap过小时, 我们可能找不到一个满足条件的$S_1$, 这是不得不做一些拖鞋, 允许$S_1$多包含或者少包含一些$\tilde{L}$的特征值.

　谱聚类的实践技巧　　

相似度矩阵　　

如何选取合适的相似度矩阵呢．前面提过常用的相似度矩阵有KNN,$\varepsilon$-邻居图, 以及全连接.

$\varepsilon$-邻居图指对于每个节点, 将离他距离为$\varepsilon$以内的节点相连(相似度设为1). 那么这里参数$\varepsilon$的选取就很重要, 而且它没有办法处理不同尺度下的情况. 因此, 这种相似度矩阵比较适合于对数据较为了解, 有一定先验知识且尺度较为一致的情况.

KNN 指的是对于每个节点, 将离它最近的K个节点相连. 这种方法就可以处理尺度不一致的数据点. 它还有一个变种Mutual KNN, 即只有两个节点互为最近的k个节点之一它们才连接. 这种MKNN倾向于连接同一个密度的区域中的节点, 可以看作是KNN和$\varepsilon$-邻居的一种折中.

下图给出了他们之间的一个直观的比较:

使用高斯相似函数$s(x{i}, x{j})=\exp (-|x{i}-x{j}|^{2} /(2 \sigma^{2}))$的全连接图也是一种非常常用的连接方式, 这里的$\sigma$的作用和上述的$\varepsilon$类似. 但是它的缺点在于这样产生的相似矩阵不是稀疏的.

总的来说, 一开始不妨选择KNN作为连接的方式, 一般来说它的鲁棒性较强一些.

相似度矩阵的参数选取

上面提到的相似度矩阵都涉及到(超)参数的选取, 遗憾的是, 并没有理论证明如何选取能够保证更好的性能. 不过实践中, 这些参数的选取还是有一些指导意见.

KNN. 这里k的选取通常要保证建完图之后, 图的联通分量的数量小于我们要聚类的簇数. 对于较小的数据我们可以挨个尝试, 对于很大的图, 一个建议的选择是$k\approx \log(n)$的量级.

$\varepsilon$-邻居. 这里通常会选择图的最小生成树上的最长边.

全连接. 当使用高斯相似函数时, 一个建议是令$\sigma$为每个节点离第$k$近节点距离的均值, k的取值可以为$\log(n)+1$. 另一种建议是和上面一样, 选择最小生成树上的最长边.

图Laplacian的选取

上面介绍了三种Graph Laplacian, 那么实践中应该如何选取呢?　

当图中节点的度较为相近时，　三者其实差不多，　但是当度的分布较为广时，不同Laplacian的表现就有差别了. 一般来说, 标准化后的Laplacian会优于未标准化的Laplacian. 而标准化后的Laplacian中$L{rw}$会优于$L{sym}$.

总结

最早的Spectral Clustering思想可以追溯到1973年Donath和Hoffman的研究, 同一年, Fiedler发现了对于二分图, 它的Laplacian矩阵的第二个特征向量可以很好的用作分类. 之后Spectral Clustering的理论和实践都不断完善. 总的来说, 它有着以下有优点:　