Stanford图机器学习公开课CS224W(五)笔记

Lecture 5 -Spectral Clustering

Posted by Yunlongs on November 30, 2020

Spectral Clustering

这一部分来讲述谱聚类算法的产生缘由。

一.Graph Partitioning

首先给出问题:如何做出下图所示的一个分割?

  • 最大化组内的连接数
  • 最小化组间的连接数

下面我们将这种partition表达为组间”edge cut”的目标函数:

\[cut(A,B)=\sum_{i\in A,j\in B}w_{ij}\]

如果是加权图的话$w_{ij}$为权值。

所以我们就最小化上面的目标函数得到组间的最小割,但是这样做存在一个问题:仅考虑了组间的连接,没考虑组内的连接性,因此会出现下图的bad case。

为了考虑组内的连接性,引出了一个概念:Conductance 来平衡组内和组间的重要性,形式化定义如下所示。

\[\phi(A,B) = \frac{cut(A,B)}{min(vol(A),vol(B))}\]

其中$vol(A)$为组A内所有节点的度。

二.Spectral Clustering Intuition

这里给定一个邻接矩阵$A$,和每个节点的值向量$\vec x$,我们可以得到

\[A\vec x = \lambda \vec x\]

这里我们来分析下$A\vec x$中$j^{th}$坐标上的元素,当为无权图时,$j^{th}$上的值为节点$j$所有邻居值的累加,这就相当于赋予了节点$j$具有邻居属性的新值。

2.1 Spectral Graph Theory

Spectrum: 一个图的特征值$\lambda _i$对应的特征向量$\vec x^{(i)}$,并且特征值是从小到大排序的。

\[\lambda _1 \leq \lambda _2 \leq ... \leq \lambda _n\]

如果我们假设图$G$是d-正则且连通的,那么我们可以很容易的得到一个特征值和特征向量:

当$\vec x = (1,1,…,1)$时,有$A\vec x = (d,d,…,d) = \lambda \vec x$,所以特征向量为$\vec x_n=(1,1,…,1)$,特征值$\lambda _n= d$且为最大的特征值。

所以当给定一个连通的d-正则图时,根据上面的发现,我们可以得出额外的结论:$\vec x_{n-1}$的的元素之和必为0。

这是因为,$\vec x_n ^T\vec x_{n-1} = 0$,又因为$\vec x_n=(1,1,…,1)$,所以$\sum_i \vec x_{n-1}[i] = 0$。

这样的话,我们将可以将$\vec x_{n-1}$划分为两类节点:$\vec x_{n-1}[i] >0 $ vs. $\vec x_{n-1}[i]<0$。因此就可以得到两个不同的节点群组。

2.2 Optimization Problem

设节点的邻接矩阵为$A$,度矩阵为$D$,可以得到拉普拉斯矩阵:$L=D-A$。

需要注意的是,生成的拉普拉斯矩阵是半正定矩阵,因此特征值为非负实数,特征向量实数且相互正交。

这里给出一个拉普拉斯矩阵的例子,如下图所示:

明显可以得出,特征向量$\vec x_1 = (1,1,…,1)$,对应的特征值为$\lambda _1=0$为最小特征值。

这时回顾2.1所讲的Intuition,现在若我们能找到第二小的特征值$\lambda _2$和对应的特征向量,那么我们就可以对将图划分为具有正负标签的两类群组。

根据瑞丽商定理,$\lambda _2$可以这样求得:

当特征向量为单位向量后,$x^Tx=1$。

那么现在就要探讨下,对于图$G$的$x^T Lx$意味着什么?

最优化问题的解$x$就为$\lambda _2$的特征向量。

并且我们可以根据$x_2$中值的正负,来将节点分到不同的群组中去。

最后值的注意的是:此优化问题和Conductance的最小化问题是等价的。证明

https://www.cnblogs.com/pinard/p/6221564.html

2.3 谱聚类算法

三个基本阶段:

  1. 预处理: 构建图的拉普拉斯矩阵表示
  2. 矩阵分解:求一个或多个最小的特征值和特征向量
  3. 节点分组:基于节点新的表征,分配节点到多个聚类之中

比如下图,就是根据特征向量$x_2$的正负来进行节点聚类的例子。

但是为什么只使用$\lambda _2$对应的特征向量呢?难道其他的特征向量都没意义?

当然不是,只是因为$\lambda _2$为第二小的特征值,对于拉普拉斯矩阵来说,特征值越小,特征向量中含有的信息量越大,而第一小的特征值为0,特征向量是没有意义的。所以在实际中,我们可以选择k个最小的特征向量,这样就形成了$n\times k$的特征矩阵,根据每个节点的特征值进行聚类就行了。

那么应当选什么样的k值比较好呢?

选择具有最大特征值差距的k是最好的:$\Delta k = ||\lambda _k - \lambda{k-1}||$

三. Motif-Based Spectral Clustering

在之前我们是根据边的紧密程度来进行聚类的,那么如果我们想要基于一些其他的模式来进行聚类呢?

研究证明一些小的子图(Motifs)来构成网络中的块。

Motifs概念见https://yunlongs.cn/2020/11/27/cs224w-3/

为了方便理解,给个例子:

3.1 Defining Motif Conductance

这里我们需要将针对边的目标函数迁移到针对motifs上。

思想:

  • 输入:图$G$和motif$M$
  • 使用$G$形成一个新的加权图$W^{(M)}$
  • 对$W^{(M)}$应用谱聚类
  • 输出聚类结果

3.2 Optimizing Motif Conductance

预处理: $W_{ij}^{(M)}= 边(i,j)$出现在motif $M$中的次数

矩阵分解: 基于$W^{(M)}$的标准谱聚类

这样做的Insight在于,对$W^{(M)}$的谱聚类可以帮助找到很低的motif conductance: