Press "Enter" to skip to content

图中的谱聚类详解

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

在Neural network还未使用在graph里时, 图聚类就有着很大的需求, 比如在社交网络中的群体分类,如何在图中完成相应地工作,本文基于对cs224w 《Spectral Clustering》的学习笔记,尝试描述清楚,这方面经典的工作。

 

Graph Partitioning

 

何谓graph partitioning, 如下图,给定无向图
, 将这些节点分为两个组:

逻辑很简单,但是难点在于:

 

 

    1. 如何定义一个尺度,来保证图的切分是合理的:

 

      1. 组内成员连接尽可能多;

 

      1. 组与组之间连接尽可能少;

 

 

 

 

    1. 如何高效地识别这些分区;

 

 

Criterion

 

Cut(A,B):
如下图,图当中,两个点分别在两个分组的边的数量;

Minimum-cut

 

最小化图分组间的连接(如果有权重,则考虑权重):
这样会存问题:

仅仅考虑图当中分组的外部连接;
未考虑图中分组的内部连接;

因此,在下面图中,会出现,假如是minimum cut不是optimal cut :

Conductance

 

与Minimum-cut逻辑不一样, Conductance不仅仅考虑分组间的连接, 也考虑了分割组内的“体积块”, 保证分割后得到的块更均衡,Conductance指标如下:

 

 

其中
指分组块A内节点所有的权重度之和; 但是,得到最好的Conductance是一个np难题。

 

Spectral Graph Partitioning

 

假定A为无连接图G的链接矩阵表示,如(i,j)中存在边,则
,否则为0; 假定x是维度为n的向量
,我们认为他是图当中每个节点的一种标签; 那幺
的意义是, 如下图,
表示i的邻居节点与对应标签和:


,可以得到特征值:
, 和对应的特征向量
。对于图G, spectral(谱)定义为对应特征值
,其
对应的特征向量组

 

d-Regular Graph 举例

 

假定图当中每个节点的度均为
,且G是连通的,即称为 d-Regular Graph
。 假定
,那幺
, 故会有对应的特征对:

 


且d是A最大的特征值(证明课程未讲)

 

d-Regular Graph on 2 Components

 

假定G有两个部分, 每个部分均为d-Regular Graph, 那幺必然存在:

 



 

所以必然存在两个特征值
, 推广起来,如果图G中两个部分互相连通,如下图, 则最大的特征值很近似:

推广, 这里有点没有太理解:

Matrix Representations

 

邻接矩阵A

对称矩阵;
n个实数特征值;
特征向量均为实数向量且正交:

度矩阵

对角矩阵;


,
表示节点i的度;

Laplacian matrix

Laplacian matrix 有以下特点:

令x=(1,…,1)则
, 故

L的特征值均为非负实数;
L的特征向量均为实数向量,且正交;

对于所有x,

L能够表示为

Find Optimal Cut

 

分组表示(A,B)为一个向量,其中

问题转换为寻找最小化各部分间连接:

相关证明间slide,这里老师没有做过多解读;

 

Spectral Clustering Algorithm

 

基础方法

 

如下图:主要包括三个步骤: – 预处理:构造图的表示, 包括Laplacian Matrix; – 矩阵分解:

计算Laplacian Matrix的所有的特征值与特征向量;

将节点使用特征向量表示(对应
的特征向量
);

– 聚类, 将节点的特征表示,排序, 按大于0与小于来进行拆分:

以下是多个实例, 看起来使用
对应的特征向量
来切分是比较合适的:

k-Way Spectral Clustering

 

如何将图切分为k个聚类呢?

递归利用二分算法,将图进行划分。但是递归方法效率比较低,且比较不稳定;
使用降维方法,将节点表示为低维度的向量表示,然后利用k-mean类似的方法对节点进行聚类;

那幺如何选择合适的k呢,如下图,计算连续的特征值之间的差值,选择差异最大的即为应该选择的k?

Motif-Based SPectral Clustering

 

是否能够通过专有的pattern 来进行聚类呢?上一篇文章有提到motif, 如下图:

给定motif,是否能够得到相应地聚类结果:

答案当然是可以的, 而且也是复用前面的逻辑

 

Motif Conductance

 

和上文中, 按边来切分逻辑不通, conductance指标,应该表征为motif的相关指标,如下:

这里给出一个计算的例子, 如下图, 该出模式分子为切分经过的该模式数量, 分母为该模式覆盖的所有节点数量:

所以motif的谱聚类就变成了给定图G与Motif结构来找到
最小的, 很不幸, 找到最小化motif conductance也是一个np问题; 同样地,也专门提出了解决motif 谱聚类的方法:

 

 

    1. 给定图G和motif M;

 

    1. 按M和给定的G,生成新的权重图

    1. ;

 

    1. 在新的图上应用spectral clustering方法;

 

    1. 输出对应的类簇;

 

 

大致过程如下图所示:

具体过程如下:

 

 

    1. 给定图G与motif M, 计算权重图

 

2. 应用谱聚类, 计算其Laplacian Matrix的特征值与特征向量,得到第二小的特征向量,:

3. 按升序对第二小特征值的对应的特征向量进行排序(对应的节点ID需要保存以计算motif conductance), 以
计算motif conductance值,选择最小地的值即为划分点, 如下图,1,2,3,4,5为一个类:

Summary

 

本章我们学习了谱聚类相关的工作, 首先,讲了关于表征切分图的指标cut(A,B)以及conductance,如何切分图以及为什幺切分图是一个np难题,然后提出了利用谱聚类的方法来解决该问题,从而学习到了degree matrix, Laplacian matrix等概念; 而后提出是否有按motif来进行图聚类的方法, 并基于谱聚类的方法来解决来转换原图为带权重的图来解决;

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注