最近在看GNN/GCN的时候遇到谱聚类，学了下，做了些笔记。

本文主要参考了：[1] https://www.cnblogs.com/pinard/p/6221564.html#!comments

Introduction

谱聚类是图论中的算法，主要思想是空间中距离较远的两个点之间边的权重值较低， 距离较近的两个点之间边的权重值较高， 通过对所有数据点组成的图（Graph）进行切图， 使不同子图之间边的权重和尽可能低， 子图内边的权重值的和尽可能高，从而达到聚类的目的。

基础1： 无向权重图

对于边$(v_i,v_j)$, 它的权重$w_{ij} > 0$。对于没有边的节点$v_i$和$v_j$, 他们之间的权重$w_{ij}=0$。图中的节点$v_i$, 它的度$d_i$定义为和它连接的所有边的权重之和，即： $$ d_i = \sum_{j=1}^n w_{ij} $$ 根据所有节点的度值，我们可以得到一个度矩阵$D$: $$ D=\displaystyle \left(\begin{array}{ccc}{d_{1}} & {\ldots} & {\ldots} \\\ {\ldots} & {d_{2}} & {\ldots} \\\ {\vdots} & {\vdots} & {\ddots} \\\ {\ldots} & {\ldots} & {d_{n}}\end{array}\right) ^{n\times n} $$ 是一个$n \times n$的对角阵，对角元素是每个节点的度和。

定义图的邻接矩阵为$W \in \mathbb{R}^{n \times n}$， 每个元素$W_{ij}$表示节点对$(v_i,v_j)$之间的权重。 对于$V$中的一个子节点集$A \subset V$， 定义： $$|A|=A 中的节点个数 $$

$$vol(A) = \sum_{i \in A} d_i \quad 表示A中所有节点的权重之和$$

基础2：相似矩阵

再提下谱聚类的基本思想： 距离较远的两个点之间权重值较低，距离较近的两个点之间权重值较高

但是在谱聚类中，我们只能获得数据点的定义，无法给出邻接矩阵，因为是离散的分布在空间中，无法得知其中的连接关系。

一般来说，通过样本点距离度量的相似矩阵$S$来获得邻接矩阵$W$.

构建邻接矩阵$W$有两种方法: $\epsilon$-邻近法， K邻近法和全连接法。

$\epsilon$-邻近法

$\epsilon$为距离的阈值，欧式距离$S_{ij}$表示两点$v_i$,$v_j$的坐标$x_i$,$x_j$之间的距离。 即 $S_{ij} =||x_i-x_j||^2_2$为相似矩阵$S \in \mathbb{R}^{n \times n}$的第$i$行第$j$个元素，则邻接矩阵$W$可以表示为：

$$ w_{ij}=\left\{\begin{array}{ll}{0} & {s_{i j}>\epsilon} \\ {\epsilon} & {s_{i j} \leq \epsilon}\end{array}\right. $$

意思是如果两点之间的距离大于$\epsilon$，那么他们之间的权重为0， 如果他们之间的距离小于$\epsilon$，他们之间的权重为$\epsilon$。 这种方法的弊端在于点之间的距离只有两种情况，不够精确，故很少采用。

K邻近法

利用KNN算法遍历所有样本点，取每个样本点最近的$k$个点作为近邻，只有和样本点距离最近的$k$个点的$w_{ij} >0$，但会出现一种情况， $v_i$的k个近邻中有$v_j$，但$v_j$的k个近邻中没有$v_i$，这样会造成邻接矩阵$W$的不对称， 因此提供两种解决办法

第一种： 只要$v_j$在$v_i$的K邻域中，那么不管$v_i$在不在$v_j$的K邻域中，都把$v_i$加入$v_j$的邻域中，即：

$$ w_{i j}=w_{j i}=\left\{\begin{array}{ll}{0} & {x_{i} \notin K N N\left(x_{j}\right) \text { and } x_{j} \notin K N N\left(x_{i}\right)} \\ {\exp \left(-\frac{\left||x_{i}-x_{j}\right||^2_2}{2 \sigma^{2}}\right)} & {x_{i} \in K N N\left(x_{j}\right) \text { or } x_{j} \in K N N\left(x_{i}\right)}\end{array}\right. $$ 第二种，必须$v_i$在$v_j$的K邻域中，且$v_j$在$v_i$的K邻域中，那么才保留两者间的权重，否则都为0，即：

$$ w_{i j}=w_{j i}=\left\{\begin{array}{ll}{0} & {x_{i} \notin K N N\left(x_{j}\right) \text { or } x_{j} \notin K N N\left(x_{i}\right)} \\ {\exp \left(-\frac{||x_{i}-x_{j}||^2_2}{2 \sigma^{2}}\right)} & {x_{i} \in K N N\left(x_{j}\right) \text { and } x_{j} \in K N N\left(x_{i}\right)}\end{array}\right. $$

全连接法

设所有点之间的权重都大于0，可以选择不同的核函数来定义边的权重，常用的如多项式核函数，高斯核函数， Sigmod核函数。 最常用的为高斯核函数RBF，将两点之间的距离带入高斯核函数RBF中，即： $$ w_{i j}=w_{ji}=s_{i j}=s_{ji}=\exp \left(-\frac{\left|x_{i}-x_{j}\right|_{2}^{2}}{2 \sigma^{2}}\right) $$ 其中，$sigma$为为函数的宽度参数 , 控制了函数的径向作用范围。

基础3：拉普拉斯矩阵

拉普拉斯矩阵定义为$L = D-W$ 如上文所示，$D$为度矩阵，$W$为邻接矩阵。

拉普拉斯矩阵具有如下性质：

1. $L$是对称阵 （因为$D$和$W$都是对称阵）

2. $L$的所有特征值都是实数 （因为$L$是对称阵）

3. 对于任意向量$f$， 有$f^TLf = \displaystyle \frac{1}{2} \sum_{i = 1}^n \sum_{j = 1}^n w_{ij} (f_i-f_j)^2$

   推导： $$ \begin{aligned} f^TLf &= f^TDf-f^TWf\\ &= \sum^n_{i = 1}d_if_i^2 - \sum_{i = 1}^n\sum_{j =1}^n f_if_j w_{ij}\\ &= \frac{1}{2}\left(\sum^n_{i=1}d_if_i^2 -2\sum_{i = 1}^n\sum_{j =1}^n f_if_j w_{ij} + \sum^n_{i=1}d_if_i^2\right)\\ &由于d_i = \sum_{j = 1}^nw_{ij}, 将d_i带入上式得\\ f^TLf &= \frac{1}{2} \left(\sum_{i = 1}^n\sum_{j =1}^n w_{ij}f_i^2-2\sum_{i = 1}^n\sum_{j =1}^n f_if_j w_{ij} + \sum_{i = 1}^n\sum_{j =1}^n w_{ij}f_i^2\right)\\ & = \frac{1}{2} \left(\sum_{i = 1}^n\sum_{j =1}^n w_{ij}f_i^2-2\sum_{i = 1}^n\sum_{j =1}^n f_if_j w_{ij} + \sum_{j = 1}^n\sum_{i =1}^n w_{ji}f_j^2\right)\\ &= \frac{1}{2}\left(\sum_{i=1}^n\sum_{j = 1}^n w_{ij} (f_i-f_j)^2\right) \end{aligned} $$

4. 拉普帕斯矩阵是半正定的，且$n$个实数特征值都$\geq$，即 $0=\lambda_1 \leq \lambda_2 \cdots \leq \lambda_n$，且最小的特征值为0。

   证明，因为$f^TLf \geq 0$ 所以$L$半正定。

基础4：无向图切图

对于无向图$G$，目的是将图$G = (v,E)$切成相互没有连接的k个子图，每个子图是一个节点集合：$A_1,A_2,\cdots, A_k$，满足$A_i \cap A_j = \phi$ 且$A_1 \cup A_2 \cup \cdots \cup A_k = V$，对于两个节点集合$A ,B \subset V$, $A \cap B = \phi$，定义$A$,$B$之间的切图权重为： $$ W(A,B) = \sum_{v_i\in A, v_j \in B} w_{ij} \quad 表示A中节点到B中节点的权重和 $$ 对于$k$个子图节点集合$A_1,A_2,\cdots, A_k$，定义切图$Cut$为： $$ Cut(A_1,A_2, \cdots, A_k) = \frac{1}{2}\sum^k_{i = 1} W(A_i,\overline{A_i}) $$ 其中$\overline{A_i}$是$A_i$的补集，也就是除$A_i$外其他所有节点的集合，$Cut$计算的是$A_i$中每个节点到$\overline{A_i}$中每个节点的权重总和，如果最小化$Cut$，就相当于最小化每个子集中节点到自己外节点的权重，但是会存在一个问题，如下图所示：

如果按左边那条线分割，可以保证有边子图到左边子图的权重最小，但不是最佳分割。

谱聚类：切图聚类

为了避免上述效果不佳的情况，提供两种切图方式，1.RatioCut, 2.Ncut.

RatioCut 切图

最小化$Cut(A_1,A_2, \cdots, A_k)$的同时，最大化每个子图中接待你的个数，即：A_{i}, \overline{A}_{i}

$$RatioCut\left(A_{1}, A_{2}, \ldots A_{k}\right)=\frac{1}{2} \sum_{i=1}^{k} \frac{W\left(A_{i}, \overline{A_i}\right)}{\left|A_{i}\right|}$$

目标是最小化$RatioCut\left(A_{1}, A_{2}, \ldots A_{k}\right)$。

为此，我们引入一个指示向量（indicator vector）$h_j \in {h_1,h_2,\cdots, h_k}$，其中$j = 1,2,\cdots,k$，对于其中任意一个向量$h_j$，它是一个$n$维向量，即： $$ h_j = (h_{1j},h_{2j}, \cdots, h_{nj})^T \\ h_{i j}=\left\{\begin{array}{ll}{0} & {v_{i} \notin A_{j}} \\ {\frac{1}{\sqrt{\left|A_{j}\right|}}} & {v_{i} \in A_{j}}\end{array}\right. $$ $h_ij$表示节点$v_i$ 是否属于子图$A_j$, 如果属于，那么$h_{ij} = \frac{1}{\sqrt{\left|A_{j}\right|}}$，如果不属于，那么$h_{ij} = 0$。

那么对于$h_i^TLh_i$有： $$ \begin{aligned} h_i^T L h_i &= \frac{1}{2}\sum_{m=1}\sum_{n=1}w_{mn}(h_{im}-h_{in})^2\\ &= \frac{1}{2}\left(\sum_{m\in A_i}\sum_{n \in A_i}w_{mn}(h_{im}-h_{in})^2+\sum_{m\in A_i}\sum_{n \notin A_i}w_{mn}(h_{im}-h_{in})^2 + \\ \sum_{m\notin A_i}\sum_{n \in A_i}w_{mn}(h_{im}-h_{in})^2 + \sum_{m\notin A_i}\sum_{n \notin A_i}w_{mn}(h_{im}-h_{in})^2\right)\\ & 上式中的mn是图中任意选取的两个不同的节点， 针对子图A_i及其对应的指示向量h_i,\\ &任意选取的节点对有四种情况。其中 根据h_{ij}的定义，第一项和第四项为0，所以\\ &=\frac{1}{2} \left(\sum_{m\in A_i}\sum_{n \notin A_i}w_{mn}(h_{im}-h_{in})^2 + \sum_{m\notin A_i}\sum_{n \in A_i}w_{mn}(h_{im}-h_{in})^2\right) \\ &=\frac{1}{2} \left(\sum_{m\in A_i}\sum_{n \notin A_i}w_{mn}(\frac{1}{\sqrt{\left|A_{i}\right|}})^2 + \sum_{m\notin A_i}\sum_{n \in A_i}w_{mn}(-\frac{1}{\sqrt{\left|A_{i}\right|}})^2\right) \\ &=\frac{1}{2}\left(\frac{1}{|A_i|}Cut(A_i,\overline{A_i}) + \frac{1}{|A_i|}Cut(A_i,\overline{A_i})\right)\\ &=\frac{Cut(A_i,\overline{A_i})}{|A_i|} = RatioCut(A_i) \end{aligned} $$ 上式$h_i^TLh_i$可以看做是子图$A_i$的RatioCut，那么： $$ \begin{aligned} RatioCut(A_1,A_2,\cdots,A_k) &=\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{Cut(A_i,\overline{A_i})}{|A_i|} \\ &= \sum_{i=1}^k h_i^TLh^i = \sum_{i=1}^k (H^TLH)_{ii} = tr(H^TLH) \end{aligned} $$ 每个$h_i^TLh^j$的值对应于矩阵$H^TLH$在位置$ij$处的值： $$ H=(h_1,h_2,\cdots,h_k) \in \mathbb{R}^{n\times k} $$ $$ h_i^TLh_j = (H^TLH)_{ij} \to h^T_iLh_i = (H^TLH)_{ii} $$

由于$h_i\cdot h_j = 0, h_i \cdot h_i = 1$, 所以$H^TH = I$是一个单位矩阵

所以切图优化函数为： $$ \underbrace{\arg \min }_{H} RatioCut\left(A_1,A_2,\cdots A_k\right) = \underbrace{\arg \min }_{H} \operatorname{tr}\left(H^{T} L H\right) \quad \text { s.t. } \quad H^{T} H=I $$ $H$中的每个指示向量$h$是$n$维的，每个向量中的元素有两种取值，分别是0和$\frac{1}{\sqrt{\left|A_{j}\right|}}$， 所以每个$h$有$2^n$种可能性，所以整个$H$有$k2^n$中，因此上述目标函数是个NP-hard问题。

注意到$tr(H^TLH)$中每个优化子目标$h_i^TLh_i$，其中，$h$是单位正交基，基每个元素的平方和等于1，$L$为对称矩阵，此时$h^T_iLh_i$的最大值为$L$的最大特征值， $h^T_iLh_i$的最小值是$L$的最小特征值。在谱聚类中，我们的目标是找到目标函数的最小特征值，从而使目标函数最小，得到对应的特征向量。

对于$h^T_iLh_i$，目标是找到$L$最小的特征值，这个值就是$h^T_iLh_i$的最小值，对于$tr(H^TLH) = \sum^k_{i=1} h^T_iLh_i$，目标是找到$k$个最小的特征值，从而使$tr(H^TLH)$最小。

通过找到$L$最小的$k$个特征值，可以对应得到$k$个特征向量，这$k$个特征向量可以组成一个$n \times k$的矩阵，这个矩阵就是我们需要的指示向量矩阵$H$，里面包含了每个节点所属子图的信息。一般来说 我们需要对$H$按行做标准化： $$ h_{ij}^* = \frac{h_{ij}}{\sqrt{\sum_{t=1}^kh^2_{it}}} $$ 注意到，$H$的每行是一个$k$维行向量，即$H_i = (H_{i1},H_{i2},\cdots, H_{ik})$， 表示节点$i$属于每个子图的指标值， 我们可以把$H_i$当做节点$v_i$的表示向量， 由于归一化后的$H$还不能明确指示各个样本的归属， 我们还需要对$H$代表的所有节点做一次传统聚类，如K-Means。

NCut切图

把$RatioCut$的分母从$|A_i|$换成$vol(A_i) = \sum_{j \in A_i}d_j$， 为$A_i$中所有节点的权重之和，一般来说$NCut$效果好于$RatioCut$: $$ NCut(A_1,A_2,\cdots,A_k) = \frac{1}{2}\sum_{i=1}^k\frac{W(A_i,\overline{A_i})}{vol(A_i)} = \sum^k_{i = 1}\frac{Cut(A_i)}{vol(A_i)} $$ $NCut$指示向量$h$做了改进，$RatioCut$切图在指示向量中使用$\frac{1}{\sqrt{|A_i|}}$表示某节点归属于子图$A_i$，而$NCut$切图使用子图权重$\frac{1}{\sqrt{vol{A_i}}}$来表示某节点归属子图$A_i$如下： $$ h_{i j}=\left\{\begin{array}{ll}{0} & {v_{i} \notin A_{j}} \\ {\frac{1}{\sqrt{v o l\left(A_{j}\right)}}} & {v_{i} \in A_{j}}\end{array}\right. $$ 上式表示如果节点$v_i$在子图$A_j$中，那么指示向量$h_j$的第$i$个元素为$\frac{1}{\sqrt{vol{A_j}}}$。

那么对于$h_i^TLh_i$有： $$ h^T_iLh_i = \frac{1}{2}\sum_{m=1}\sum_{n=1}w_{mn}(h_{im}-h_{in})^2 = \frac{Cut(A_i)}{vol(A_i)} =NCut(A_i) $$ 目标函数： $$ NCut(A_i,A_2,\cdots,A_k) = \sum^k_{i = 1} NCut(A_i) = \sum^k_{i=1}h^T_iLh_i =\sum^k_{i=1}(H^TLH)_{ii} = tr(H^TLH) $$ 此时，$h_i \cdot h_j = 0$，$h_i\cdot h_i = \frac{|A_i|}{vol(A_i)} \neq 1$， 所以$H^TH \neq I$。

但是， 由于：$h^T_iDh_i = \sum^n_{j = 1} h_{ij}^2d_j$, $d_j$为节点$v_j$的权重和，$h_{ij}$的值表示节点j是否在子图$A_i$中，如果在子图$A_i$中，那么$h_{ij}^2 = \frac{1}{vol(A_i)}$，否则为0。

$$h^T_iDh_i = \frac{1}{vol(A_i)} \sum_{v_j \in A_i} d_j = \frac{1}{vol(A_i)} \cdot vol(A_i) = 1$$

最终目标函数为： $$ \underbrace{\arg \min } _{H}\operatorname{tr}\left(H^{T} L H\right) \quad \text { s.t. }\quad H^{T} D H=I $$ 由于$H$中的指示向量$h$不是标准正交基，所以RatioCut中加粗的定理不能直接使用，所以，令$H = D^{-\frac{1}{2}}F$, $D^{-\frac{1}{2}}$表示对$D$对角线上元素开方后求逆，那么： $$ H^TLH = F^TD^{-\frac{1}{2}}LD^{-\frac{1}{2}}F $$

$$ H^TDH = F^TD^{-\frac{1}{2}}DD^{-\frac{1}{2}}F = F^TF=I $$ 所以目标函数转化为： $$ \underbrace{\arg \min }_{F} \operatorname{tr}\left(F^{T} D^{-1 / 2} L D^{-1 / 2} F\right) \quad \text { s.t. } \quad F^{T} F=I $$ 同$RatioCut$，$D^{-1 / 2} L D^{-1 / 2}$是对称矩阵，$F$中的每个向量为标准正交基，只需要求出$D^{-1 / 2} L D^{-1 / 2}$的最小的前$k$个特征值，然后求出对应的特征向量，并标准化，最后得到特征矩阵$F$，然后对$F$的行向量做一次传统聚类，如K-means.

一般来说， $D^{-1 / 2} L D^{-1 / 2}$相当于对拉普拉斯矩阵$L$做了一次标准化，即$\frac{L_{i j}}{\sqrt{d_{i} * d_{j}}}$.

我把本文整理成了PDF