【爱丁堡大学博士论文】图聚类结构的学习，164页pdf

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

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

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