CS224w图机器学习（四）：Spectral Clustering

内容简介

本文主要介绍CS224W的第五课，图的谱聚类。前一章主要讲图的社区，社区是一组节点的集合，社区内部的节点保持紧密的连接，而与图的其他节点连接很少的节点集合。图的社区是从节点间的连接关系来研究图的性质，本章则是从另一个角度（谱聚类）来介绍图。

CS224W Lecture 5: Spectral Clustering

上图为CS224W第五讲谱聚类的内容框架，如下链接为第五讲的课程讲义

1 Graph Partitioning

首先图的谱聚类包含三步：

1）预处理：构造图的矩阵表征； 2）分解：计算矩阵的特征值和特征向量，并基于特征值和特征向量将每个节点映射到一个低维向量； 3）聚类：根据降维后的向量，对节点进行聚类与分组。

谱聚类的主体思想如上，不涉及聚类的细节，本章就算是讲完了。不过我们当然得尽可能详尽的去理解，那么接下来可先从图的分割（Graph Partitioning）说起。

图的分割问题，可参见下图： 已知无向图

[公式]

，图的分割问题，就是运用合理的手段，将图

[公式]

中的节点，分为两个不相交的集合

[公式]

和

[公式]

。 图的分割问题，有两个核心问题需要解决： 1）怎么定义分割手段的好坏，我们把图分割好后，怎么判断分割后的集合是最优的？ 2）如何快速有效的找到这个最优的分割？

我们先看图分割的评价指标。

还是以上图所示的无向图

[公式]

为例，节点

[公式]

分为一类，节点

[公式]

分为一类，是一种可行的分割方法。那么怎么评价这种分割的好坏呢？ 第一个评价指标为Graph Cut，将图分割为两类需要cut的边条数，一个好的分类应该让不同分割模块的成员之间的连接尽可能地少。

[公式]

，上述例子中的

[公式]

。

而只考虑这一个因素，得到的分割也不一定是最优的，如上图所示。因此我们需要引入新的评价指标：conductance。

[公式]

其中

[公式]

，节点子集A内节点的度之和。

2 Spectral Graph Partitioning

了解了图分割以及评价指标后，我们接下来引入谱的概念。

记

[公式]

为无向图

[公式]

的邻接矩阵，其中

[公式]

。 再假设

[公式]

维向量

[公式]

为图

[公式]

中

[公式]

个节点的标签（特征向量）。

[公式]

再来思考

[公式]

的具体含义，我们知道

[公式]

，而

[公式]

代表的是节点

[公式]

的标签，所以

[公式]

计算的其实是节点

[公式]

的邻接节点的标签之和。 再结合线性代数的知识，我们令

[公式]

，可以得到特征值

[公式]

和对应的特征向量

[公式]

，有了这些知识铺垫，便可引入谱的概念。

图

[公式]

的谱（spectrum）可定义为一组特征向量

[公式]

，这组特征向量满足其对应的特征值

[公式]

，其中

[公式]

。

引入谱的概念后，我们简单举个例子，假设一个无向连通图

[公式]

内所有节点的度都为

[公式]

（d-regular graph），那么图

[公式]

的特征值和特征向量会有什么样的性质呢？ 先假设特征向量

[公式]

，那么有

[公式]

，因为每个节点的度都为

[公式]

，所以

[公式]

。此时

[公式]

为图

[公式]

的邻接矩阵的特征值，且为最大特征值，即

[公式]

。 无向图

[公式]

有且仅有一个特征值和特征向量，详细的证明逻辑如下，先假设图

[公式]

有一个不为

[公式]

的特征向量，再结合无向图

[公式]

的性质证明该向量不可能是特征向量。

再进一步扩展，如果上述无向图

[公式]

并非连通图，而是两个不连通的d-regular graph组成，那么它的特征向量会是什么呢？ 如下所示，它有两个特征向量（分别对应图B和图C），而对应的特征值都为d。 这里已经很接近图的分割了，无向图G有两个不连通的图B和图C组成，而其特征向量已经把图B和图C分割开。

3 Matrix Representation

再回到最开始提到的，谱聚类的三个部分，我们已经了解谱是什么样的概念。接下来便开始介绍图的矩阵表征，先了解下图的三种矩阵。

1）邻接矩阵 Adjacency Matrix A 性质：对称矩阵、有n个实特征值、特征向量均为实向量且不同特征值对应的特征向量正交。 2）度矩阵 Degree Matrix D 性质：对角矩阵（对角元素为节点的度）。 3）拉普拉斯矩阵 Laplacian Matrix

[公式]

性质：最小特征值为0（容易证明）、特征值均为非负实数、特征向量均为实向量且不同特征值对应的特征向量正交、对于任意

[公式]

，有：

[公式]

、L是半正定矩阵，

[公式]

[公式]

有什么具体的含义呢？

[公式]

再介绍一个与对称矩阵相关的引理。

对于对称矩阵

[公式]

，特征值

[公式]

，其中

[公式]

是特征值

[公式]

对应的特征向量。关于该条引理的详细证明如下：

结合上述引理，那么对于拉普拉斯矩阵有

[公式]

因为

[公式]

，所以求得的实数解有正有负，

[公式]

是节点

[公式]

对应的标签，所以如下图所示，只要尽可能地让标签小于0的节点和标签大于0的节点之间的连接最少，我们便可以对图进行有效分割。

有了足够的知识支撑，我们再来看Fiedler提出的寻找图分割的最优cut（find optimal cut）。

将图G分割为子图A和子图B，表示为一个向量，

[公式]

强制令

[公式]

。 通过优化

[公式]

，来寻找最优的分割向量

[公式]

。 再将上述寻找分割向量思想，和前述的拉普拉斯矩阵的第二小特征值和特征向量结合起来 寻找最优的实向量

[公式]

，满足

[公式]

。 其中

[公式]

。 此时拉普拉斯矩阵L的第二小特征值

[公式]

由

[公式]

得出，

[公式]

对应的特征向量由

[公式]

得到（这里的x也成为Fiedler向量）。 此时可以根据特征向量的元素

[公式]

的正负，来决定节点

[公式]

属于哪一个分区，这个过程就是谱聚类（Spectral Clustering）

PS，课程还对上述手段所得到的结果满足conductance评价指标进行了详细的证明，详情可参见课程PPT，此处不再描述。

4 Spectral Clustering Algorithm

最开始我们讲了谱聚类的思想，又把与之相关的概念、引理、证明等都过了一遍，现在终于可以去落地实现谱聚类算法了。

1）预处理（pre-processing）：构建图的拉普拉斯矩阵

[公式]

。 2）分解（Decomposition）：计算拉普拉斯矩阵的特征值和特征向量，选取第二小的特征值及其对应的特征向量。 3）聚类（Grouping）：第二小特征向量中，大于0对应的节点归为一类，小于0的节点归为另一类（也可使用中位数）。 课程提供了一些案例，如下所示

上述是将图聚为两类的方法，那么怎么将图聚为k类呢？

1）基于二分进行递归，Recursive bi-partitioning [Hagen et al., ’92] 该方法效率低，且不稳定 2）Cluster multiple eigenvectors [Shi-Malik, ’00] 选取最小

[公式]

个特征值对应的特征向量构建低维空间（这

[公式]

个特征向量的第

[公式]

个元素，构成了节点

[公式]

的低维空间，对这

[公式]

个

[公式]

维向量进行聚类，就是对图的节点进行聚类），再使用诸如k-means的手段对其进行聚类，该方法目前较为常见。 如何选择类别k的数量呢？先计算拉普拉斯矩阵的特征值和特征向量，再使用相邻特征值的差来选取最优的k，详情如下图。

5 Motifs-Based Spectral Clustering

最后的最后，我们再扩展一下。前述所讲，全都是基于节点之间的关系进行聚类，除了节点关系，我们还知道模块Motifs（如有遗忘，还请回顾第三章的内容，图中反复出现的重要的连接模式），如果我们想基于Motifs对节点进行聚类呢？

整个流程类似于节点的谱聚类，首先定义Motifs的conductance，公式详情可参见下图。紧接着要做的便是找到最合适的分割方式，使得

[公式]

最小。

与节点聚类一样，我们也需要通过Motifs Spectral Clustering算法来得到最优结果，算法也分为三步。关于模块的谱聚类的输入输出如下所示。

1）预处理（pre-processing）：定义矩阵

[公式]

，其中

[公式]

表示图

[公式]

中的边

[公式]

在给定的Motifs结构

[公式]

中参与的次数，详情可参见下图。 2）分解（Decomposition）：定义度矩阵

[公式]

，其中

[公式]

，计算拉普拉斯矩阵：

[公式]

，计算特征向量和特征值

[公式]

。 3）分组（Grouping）：与基于节点关系一样，保证conductance最优。

写在最后

除了基于谱聚类对图进行分割，还有本章没有涉及的如下手段