图中的谱聚类详解
source link: https://zhuanlan.zhihu.com/p/266604288
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
在Neural network还未使用在graph里时， 图聚类就有着很大的需求， 比如在社交网络中的群体分类，如何在图中完成相应地工作，本文基于对cs224w 《Spectral Clustering》的学习笔记，尝试描述清楚，这方面经典的工作。
Graph Partitioning
何谓graph partitioning, 如下图，给定无向图
， 将这些节点分为两个组：
逻辑很简单，但是难点在于：
- 如何定义一个尺度，来保证图的切分是合理的：
- 组内成员连接尽可能多；
- 组与组之间连接尽可能少；
- 如何高效地识别这些分区；
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 谱聚类的方法：
- 给定图G和motif M；
-
按M和给定的G，生成新的权重图
;
- 在新的图上应用spectral clustering方法；
- 输出对应的类簇；
大致过程如下图所示：
具体过程如下：
-
给定图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来进行图聚类的方法， 并基于谱聚类的方法来解决来转换原图为带权重的图来解决；
Recommend
-
153
在移动开发过程中，从UI图上获取颜色是日常开发中常有的事。不过从图片获取颜色也有很多种操作方式，很多人在日常中取到的并不是“正确”的值。 上策：避免从图片中取值 最好的情况就是不需要开发者从设计图上获取颜色。常见的方式有以下三种。 设计图上直接标注：sk...
-
108
今天早间，外媒报道在中国谷歌地图已经可以使用。这或将是谷歌重回中国的一个信号。不过事情似乎出现了变化。谷歌总部对此做出回应：“TherehavebeennochangestoGoogleMapsinChina.（Google地图在中国没有任何变化）”。
-
124
最近在做网页版图片处理相关的项目，也算是初入了 canvas 的坑。项目需求中有一个给图片添加水印的功能。我们知道，在浏览器端实现图片添加水印功能，通常的做法就是使用 canvas 的 drawImage 方法。对于普通的合成（比如一张底图和一张 PNG 水印
-
78
本文主要分享整理在unity里实现2D大地图中角色行走的一些知识点1.效果展示...
-
96
在我的布局default.ctp我有 <!--nocache--> <?php echo $this->Html->getCrumbs(' / ', 'Home'); ?> <!--/nocache--> 在我称之为rules.cpt的视图中 <!--n...
-
36
有问题，上知乎。知乎，可信赖的问答社区，以让每个人高效获得可信赖的解答为使命。知乎凭借认真、专业和友善的社区氛围，结构化、易获得的优质内容，基于问答的内容生产方式和独特的社区机制，吸引、聚集了各行各业中大量的亲历者、内行人、领域专家、领域爱好者...
-
5
leetcode 84. 柱状图中最大的矩形 ...
-
10
【Spectral Clustering】谱聚类 2021年03月20日 Author: Guofei 文章归类: 3-3-图模型 ，文章编号: 370 版权声明：本文作者是郭飞。转载随意，但...
-
13
五分钟读懂：ETH 2.0 路线图中的发展重心—RollupDeFi白泽研究院2021-10-24热度: 28551以太坊实际上可以成为解决区块链三难困境的第一个区块...
-
7
← 著名的邓宁-克鲁格效应或许缺少证据支持圣诞节企业给员工开薪水，英国银行执行了两遍转账操作 →majer
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK