原文作者：Steinar Laenen, He Sun
文章来源：NIPS2020
原文标题：Higher-Order Spectral Clustering of Directed Graphs
原文链接：https://proceedings.neurips.cc/paper/2020/file/0a5052334511e344f15ae0bfafd47a67-Paper.pdf
笔记作者：[email protected]
文章小编：[email protected]

1、摘要

聚类是机器学习中的常见问题，传统的图聚类方法是寻找低连通度（conductance）的簇。这种方法只适用于无向图，也无法衡量簇之间的关系。这篇文章中，基于Hermitian矩阵对有向图的表达，提出了一种亚线性时间的算法对有向图进行聚类；除此之外，可以提取处簇之间的关联。（数学证明过于复杂，笔记中跳过了很多证明）

2、传统的无向图的聚类方法

对于传统的无向图，可以采用谱聚类的方法来对节点进行聚类。谱聚类主要分为以下几个步骤

1. 计算邻接矩阵，对于无向图来说，邻接矩阵一定是一个对称阵，其两节点之间的权重，代表了两个节点关系的远近。值越大，代表关系越紧密。（因此在谱聚类中如果一些节点关系比较紧密，会出现很大的簇）
2. 计算拉普拉斯矩阵
3. 计算拉普拉斯矩阵的特征值和特征向量（选取最小的k个特征值和对应的特征向量）
4. 对特征矩阵进行聚类，得到簇划分 在步骤4中，因为图中可能有悬挂节点甚至孤立节点，可以使用RatioCut或者NCut等方法来切图，得到一定条件下的最优解。

2.1 谱聚类的优点

• 这种方法因为考虑到了两节点之间的相关性，当数据较为稀疏时，传统算法如KMeans很难做到这点
• 这个算法采用k个特征值聚类，相当于进行了降维，在处理高维数据时有优势

2.2 传统谱聚类为何无法用于有向图

由于使用了拉普拉斯矩阵的特征值，需要所有特征值为实数，而只有对称矩阵可以保证所有特征值为实数

3、本文提出的方法

主要从三个方面对该聚类方法进行介绍

3.1 优化目标

首先我们假设图G的k个划分分别为S0,S1到S(k-1)，我们定义它的流度(flow ratio)为以下公式

其中Vol(S)代表了划分S中所有节点度数的总和，而w(S,T)是它的S-T cut cost（可以参考这个页面）。有了流度的定义之后，文中给出的优化目标是要最大化这个流度，正如以下公式所示

公式一的定义有些像无向图聚类中的标准化割值(Normalized Cut Value)，但无向图中的正则化割值是为了寻找低连通度的簇，但这篇文章的方法是要寻找一个能够最大化Flow Ratio的分隔方法。

3.2 相似矩阵

这篇文章采用了Hermitian adjacency matrix来作为相似矩阵，当节点u到v可达时，值为否则值为0。因此，标准化拉普拉斯矩阵可以定义为

3.3 聚类

有了标准化拉普拉斯矩阵之后就可以采用和无向图聚类相似的方法了，这篇文章将自己的方法命名为SimpleHerm，主要分为三步

1. 计算拉普拉斯矩阵的特征值对应的特征向量
2. 计算一个嵌入{F(v)}，![Equation5.png] (Equation5.png)，其中v为所有节点
3. 对{F(v)}进行KMeans聚类

3.4 效果

作者采用了木材交易的情景对算法进行测试，结果表明，在2006年到2009年间，几个簇都较为稳定，符合现实情况。对比了DD-SYM的方法，相对来说更加不稳定（有更多噪音），因此这篇文章中提出的方法相对于DD-SYM是一种提升。

安全学术圈招募队友-ing, 有兴趣加入学术圈的请联系secdr#qq.com