【CS224W课程笔记】Spectral Clustering

Overview

Spectral Clustering Algorithoms（谱聚类算法）的三个基本阶段：

Pre-processing（预处理）
构建图的矩阵表示
Decomposition（分解）
- 计算矩阵的特征值和特征向量
- 基于一或多个特征向量将每个点映射到较低维的表示形式
Grouping（分组）
- 基于新的表示将所有点划分为2个或多个集群

Graph Patitioning

问题定义

给定无向图 $G(V, E)$ ，将图中的节点划分到两个不相交的集群 $A,B$ 中。接下来要考虑的问题在于：

如何定义当前划分方式的好坏？
如何高效地识别这样的分区？

Graph Cut Criterion

首先需要明确的是，一个好的分区，其特点在于：

最大化分区内部的连接数量；
最小化分区与分区之间的连接数量。

接下来，将以一个与分区的“edge cut”相关的方程来表达分区目标，其中Cut为那些两个端点位于不同分区的边的集合，即 $cut(A,B)=\sum_{i \in A, j \in B}$ w_{ij}，若图中没有权重表示，则 $w_{ij} \in \{0,1\}$ 。
由此，Graph Cut Criterion可定义为最小化cut的值，即 $arg min_{A,B} cut(A,B)$ ，但考虑如下图所示的情况，红线标注的cut满足最小化的情况，但这并不是我们期望的切分方式，因此还需要添加对集群内的连接尽可能多的考虑。

cut criterion degenerate case

为了产生更加平衡的分区，[Shi-Malik, ’97]提出了新的分区评判标准Conductance，它定义了相对于分区密度的连通情况，即：
$\phi (A,B) = \frac{cut(A,B)}{min(vol(A),vol(B))}$
其中 $vol$ 代表volume， $vol(A)$ 表示分区A中所有节点的加权度数（degree）之和，即 $vol(A)=\sum_{i\in A}k_i$ 。可以看到当分母中两个分区的volume尽可能相等时，该式的值趋向于最大。但此时伴随而来的问题是想要计算得到一个最佳的conductance cut是一个NP-hard问题。而接下来要学习的Spectral Graph Partitioning可以实现优化上述标准的近似保证。

Spectral Graph Partitioning

Basic Knowledge

设 $A$ 为无向图 $G$ 的邻接矩阵， $\mathbf{x}=(x_1,x_2,\dots ,x_n) \in \mathbb{R}^n$ 为 $G$ 中每一个节点的标签/值，则 $\mathbf{y} = A \cdot \mathbf{x}$ 计算的是图 $G$ 中每个节点各自邻居的标签之和，即 $y_i = \sum_{j=1}^n A_{ij} x_j = \sum_{(i,j)\in E} x_j$ 。对于等式 $A \cdot \mathbf{x} = \lambda \cdot \mathbf{x}$ ，其中 $\mathbf{x}$ 称为特征向量（eigenvector），对应的 $\lambda$ 称为特征值（eigenvalue）。
Spectrum：对于图的任一特征向量 $\mathbf{x}^{(i)}$ ，设其对应的特征值为 $\lambda_i$ ，则将谱（spectrum）定义 $\Lambda = \{\lambda_1, \lambda_2, \dots, \lambda_n\}$ ，其中 $\lambda_1 \leq \lambda_2 \leq \dots \leq \lambda_n$ 。
例1：设 $\mathbf{G}$ 为一个所有节点的度数均为 $d$ 的连通图（称 $\mathbf{G}$ 为d-regular graph），当特征向量 $\mathbf{x}=(1,1,\dots , 1)$ 时，求得 $\lambda = d$ ，此时 $d$ 为 $\mathbf{G}$ 的邻接矩阵 $\mathbf{A}$ 的最大特征值，即 $\lambda_n = d$ 。
例2：若 $\mathbf{G}$ 不是连通图，设 $\mathbf{G}$ 有两个互不相连的连通子图 $\mathbf{C}$ 和 $\mathbf{B}$ 组成，每一个子图均是d-regular。若令特征向量 $\mathbf{x}$ 中 $\mathbf{C}$ 的节点的值为1， $\mathbf{B}$ 中所有节点值均为0，对应特征值 $\lambda = d$ ，反之亦然，则此时有 $\lambda_n = \lambda_{n-1} = d$ 。
例3：在例二的基础上，若 $\mathbf{C}$ 和 $\mathbf{B}$ 之间存在部分连接，已知特征向量 $\mathbf{x}^{(n)} = (1,1,\dots , 1)$ ，由于实对称阵属于不同特征值的的特征向量是正交的，所以有 $x_1^{(n-1)}+x_2^{(n-1)}+\dots + x_n^{(n-1)}=0$ 。
Laplacian matrix ：定义，其中为对角矩阵，主对角线元素为各节点的度数。Laplacian矩阵具有以下属性：
1. 对于特征向量 $\mathbf{x}=(1,1,\dots , 1)$ ，特征值 $\lambda = \lambda_1 = 0$ ；
2. 所有特征值均为非负实数；
3. 所有特征向量为实数且彼此正交。
对于对称矩阵 $M$ ，有 $\lambda_2 = min_{x:x^\top \mathbf{w}_1 = 0} \frac{x^\top Mx}{x^\top x}$ ，已知 $\mathbf{w}_1$ 为 $\lambda_1$ 对应的特征向量。其中最小化 $x^\top \mathbf{L} x$ 的意义在于：
$\begin{aligned} x^\top \mathbf{L} x &= \sum_{i,j=1}^n \mathbf{L}_{ij} x_i x_j \\ &= \sum_{i,j=1}^n (\mathbf{D}_{ij} - \mathbf{A}_{ij}) x_i x_j \\ &= \sum_i \mathbf{D}_{ii} x_i^2 - \sum_{(i,j) \in E} 2 x_i x_j \\ &= \sum_{(i,j) \in E} (x_i^2 + x_j^2 - 2 x_i x_j) \\ &= \sum_{(i,j) \in E} {(x_i - x_j)} ^ 2 \\ \end{aligned}$
由此对于Laplacian矩阵，上述公式可写为 $\lambda_2 = min_{x:\sum x_{i} = 0} \frac{\sum_{(i,j)\in E} {(x_i - x_j)}^2}{\sum_i x_i^2}$ ，此时 $\mathbf{x}$ 为单位向量且与 $\mathbf{x}^{(1)}$ 正交。由于 $\mathbf{x}$ 为单位向量，最小化该式意味着最小化分子，又因为 $\sum_i x_i = 0$ ，所以求解的特征向量中有正有负，理想结果将如下图所示（使尽可能少的边经过坐标轴上0的位置）：

Finding x that minimize lambda

Find Optimal Cut

[Fiedler '73]提出了一种寻找最佳切分点的方案，将分区 $(A,B)$ 表示为一个向量 $\mathbf{y}$ ，若某节点 $i \in A$ ，则对应 $y_i=+1$ ，反之， $y_i=-1$ 。分区期望实现 $|A|=|B|$ ，即 $\sum_i y_i = 0$ ，当前向量同样与 $(1, \dots , 1)$ 正交。接下来将通过下式寻找最小化分区cut的分区方案：
$arg min_{\mathbf{y} \in \{-1, +1\}^n} f(y) = \sum_{(i,j)\in E}{(y_i - y_j)} 2$

若将 $\mathbf{y}$ 的取值扩大到实数范围，则有：
$min f(y) = \sum_{(i,j)\in E} {(y_i - y_j)}^2 = \mathbf{y}^\top \mathbf{L} \mathbf{y} \\ \mathbf{y} \in \mathbb{R}^n, \sum_i y_i = 0, \sum_i y_i^2 = 1$
此时Laplacian矩阵 $\mathbf{L}$ 的第二小特征值 $\lambda_2$ 由 $\lambda_2 = min_y f(y)$ 得到； $\lambda_2$ 对应的特征向量 $\mathbf{x}$ 由 $\mathbf{x}=arg min_y f(y)$ 得到，这里的 $\mathbf{x}$ 又称为Fiedler vector。此时就可以利用 $x_i$ 的正负来决定节点 $i$ 属于哪一个分区。上述过程称为spectual clustering。

该过程对应开始的Spectral Clustering Algorithoms（谱聚类算法）的三个基本阶段：

Pre-processing：构建图的Laplacian矩阵 $\mathbf{L}$ ；
Decomposition：寻找矩阵 $\mathbf{L}$ 的特征值 $\lambda$ 和特征向量 $\mathbf{x}$ ；对节点与特征向量 $\mathbf{x}^{(2)}$ 进行映射；
Grouping：对 $\mathbf{x}^{(2)}$ 各元素进行排序，寻找合适的位置进行切分并对相应节点进行分区。