原文作者: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]
聚类是机器学习中的常见问题,传统的图聚类方法是寻找低连通度(conductance)的簇。这种方法只适用于无向图,也无法衡量簇之间的关系。这篇文章中,基于Hermitian矩阵对有向图的表达,提出了一种亚线性时间的算法对有向图进行聚类;除此之外,可以提取处簇之间的关联。(数学证明过于复杂,笔记中跳过了很多证明)
对于传统的无向图,可以采用谱聚类的方法来对节点进行聚类。谱聚类主要分为以下几个步骤
由于使用了拉普拉斯矩阵的特征值,需要所有特征值为实数,而只有对称矩阵可以保证所有特征值为实数
主要从三个方面对该聚类方法进行介绍
首先我们假设图G的k个划分分别为S0,S1到S(k-1),我们定义它的流度(flow ratio)为以下公式
其中Vol(S)代表了划分S中所有节点度数的总和,而w(S,T)是它的S-T cut cost(可以参考这个页面)。有了流度的定义之后,文中给出的优化目标是要最大化这个流度,正如以下公式所示
公式一的定义有些像无向图聚类中的标准化割值(Normalized Cut Value),但无向图中的正则化割值是为了寻找低连通度的簇,但这篇文章的方法是要寻找一个能够最大化Flow Ratio的分隔方法。
这篇文章采用了Hermitian adjacency matrix来作为相似矩阵,当节点u到v可达时,值为否则值为0。因此,标准化拉普拉斯矩阵可以定义为
有了标准化拉普拉斯矩阵之后就可以采用和无向图聚类相似的方法了,这篇文章将自己的方法命名为SimpleHerm,主要分为三步
作者采用了木材交易的情景对算法进行测试,结果表明,在2006年到2009年间,几个簇都较为稳定,符合现实情况。对比了DD-SYM的方法,相对来说更加不稳定(有更多噪音),因此这篇文章中提出的方法相对于DD-SYM是一种提升。
安全学术圈招募队友-ing, 有兴趣加入学术圈的请联系secdr#qq.com