图聚类是无监督学习中的一个基本问题,在计算机科学和分析现实世界数据中有着广泛的应用。在许多实际应用中,我们发现聚类具有重要的高层结构。这在图聚类算法的设计和分析中经常被忽视,因为这些算法对图的结构做了强烈的简化假设。本文讨论了聚类结构是否可以有效学习的自然问题,并描述了四个用于学习图和超图中聚类结构的新算法结果。论文的第一部分对经典的谱聚类算法进行了研究,并对其性能进行了更严格的分析。这一结果解释了为什么它在更弱、更自然的条件下工作,并有助于缩小谱聚类算法的理论保证与其优秀的经验性能之间的差距。

论文的第二部分在前一部分的理论保证的基础上,表明当底层图的簇具有一定的结构时,少于k个特征向量的谱聚类能够比使用k个特征向量的经典谱聚类产生更好的输出,其中k是聚类的个数。本文首次讨论和分析了少于k个特征向量的谱聚类的性能,并表明一般的聚类结构可以用谱方法学习。第三部分考虑使用局部算法高效地学习簇结构,其运行时间仅依赖于目标簇的大小,且与底层输入图无关。经典的局部聚类算法的目标是找到一个与图其他部分稀疏连接的簇,本文的这一部分提出了一种局部聚类算法,它可以找到一对彼此紧密连接的簇。这一结果表明,即使在现实世界中普遍存在的大图中,某些聚类结构也可以在局部环境中有效地学习。

论文的最后研究了超图中密集连接聚类的学习问题。该算法基于一种新的热扩散过程,扩展了最近在超图谱理论方面的一系列工作。它允许在建模对象的高阶关系的数据集中学习簇的结构,可以应用于有效分析在实践中发生的许多复杂数据集。在不同领域的合成数据集和真实数据集上进行了广泛的评估,包括图像分类和分割、迁移网络、合著网络和自然语言处理。实验结果表明,新提出的算法是实用、有效的,可以立即应用于实际数据的聚类结构学习。

成为VIP会员查看完整内容
37

相关内容

爱丁堡大学,简称爱大,全球20强顶尖名校。位于英国苏格兰首府爱丁堡市,创建于1583年,是英语国家中第六古老的大学。爱丁堡大学产生过23名诺贝尔奖获得者。达尔文、大卫?休谟、亚当?斯密、麦克斯韦、亚当?弗格森等诸多名家均曾在爱丁堡学习或从事研究。由于其悠久的历史、庞大的规模、卓越的教学质量与科研水平,爱丁堡大学在2016/17年QS世界大学排名中位居全球第19位,其实力与美国著名的常青藤盟校相当。

【伯克利博士论文】可信赖机器学习,227页pdf
专知会员服务
87+阅读 · 2022年12月12日
【牛津大学博士论文】多模态自监督学习,172页pdf
专知会员服务
134+阅读 · 2022年10月4日
【伯克利博士论文】学习跨领域的可迁移表示
专知会员服务
45+阅读 · 2022年8月17日
【博士论文】多任务学习视觉场景理解,140页pdf
专知会员服务
89+阅读 · 2022年4月5日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
4+阅读 · 2014年12月31日
国家自然科学基金
7+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
4+阅读 · 2008年12月31日
Disentangled Information Bottleneck
Arxiv
12+阅读 · 2020年12月22日
Arxiv
26+阅读 · 2018年2月27日
VIP会员
相关基金
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
4+阅读 · 2014年12月31日
国家自然科学基金
7+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
4+阅读 · 2008年12月31日
微信扫码咨询专知VIP会员