谱聚类的更紧密分析，以及更多

ICMLAug, 2022

A Tighter Analysis of Spectral Clustering, and Beyond

Peter Macgregor, He Sun

TL;DR本研究针对典型的谱聚类算法，探讨在一些较弱条件下其性能为何，还研究了利用少于 k 个特征向量进行嵌入的谱聚类，实验表明在合成和真实数据上，使用少于 k 个特征向量时，谱聚类也能够产生相当或更好的结果。

Abstract

This work studies the classical spectral clustering algorithm which embeds the vertices of some graph $G=(V_G, E_G)$ into $\mathbb{R}^k$ using $k$ eigenvectors of some matrix of $G$, and applies $k$-means to part

spectral clustering graph embedding eigenvectors k-means performance analysis

发现论文，激发创造

理论与实践中的快速简单谱聚类

本研究提出了一种基于顶点嵌入的简单谱聚类算法，通过幂法计算的向量，在接近线性时间内计算顶点嵌入，并在输入图形的自然假设下，算法能够可靠地恢复出真实聚类结果。通过在多个合成和现实世界数据集上的评估发现，该算法与其他聚类算法相比，具有显著更快的速度，并且产生的聚类准确度基本相同。

Oct, 2023

改进的谱聚类算法分析

本文探讨了基于谱算法的图分割技术，阐述了相关算法在数据分析中的应用，通过对图的一定假设条件，通过优化谱嵌入图算法的表现提供更好性能保证。

Dec, 2019

压缩谱聚类

本文提出了一种基于图信号处理的方法，采用图滤波和随机采样技术加速生成 Laplacian 矩阵特征向量和 k-means 聚类算法步骤，该方法在控制误差的同时计算时间效率可达到数个数量级的提升，并在人工合成数据和真实网络数据集上进行测试。

Feb, 2016

通过幂法的谱聚类 —— 可证明性

本文通过理论分析证明，在光谱聚类时，使用小量的幂迭代即可通过近似特征向量来达到接近最优的 K-means 聚类结果。

Nov, 2013

特征向量选择和自适应 $k$ 的近似谱聚类

该论文提出了一种利用两个相关指标来估算子空间嵌入中的聚类数，使用增长型神经气 (GNG) 逼近的算法，有效地解决了聚类问题，并在效率上与手动设置 k 的相似方法竞争。

Feb, 2023

可解释的图谱谱聚类文本文档

通过提出基于组合 Laplacian 的图谱聚类结果的解释方法，实现了将聚类结果与文本内容之间的桥梁构建，找到了与文档内容相关的谱聚类的解释方法。

Aug, 2023

利用光谱嵌入技术对随机游走特征值的锐利界限

本文介绍了利用图的随机行走矩阵的前 k 个非平凡特征向量对图进行谱嵌入的方法，并使用此框架限制了所有图的所有特征值，并提出了一种新的工具 —— 谱嵌入，在分析可逆马尔可夫链中使用。

Nov, 2012

谱聚类教程

该论文介绍了谱聚类算法和图拉普拉斯的基本性质，推导了不同的谱聚类算法，比较了它们之间的优缺点。

Nov, 2007

大维数据的核谱聚类

本文通过对核谱聚类方法进行首次分析，发现在维度和数量同时增长的情况下，核矩阵的归一化拉普拉斯矩阵与所谓的尖峰随机矩阵呈类似的渐近行为。通过一种如尖峰矩阵模型的可分离条件，证明该模型中的一些孤立特征值 - 特征向量对携带聚类信息。我们精确评估了这些特征值的位置和特征向量内容，在理论和实践角度揭示了核谱聚类中非常重要（有时相当破坏性）的方面。最后将结果与 MNIST 数据库中图像实际聚类的性能进行比较，证明了理论和实践之间的重要匹配。

Oct, 2015

分布式草图缩放图聚类

该研究使用基于矩阵草图的方法来解决在大规模图分析中传统方法遇到的挑战，尤其是无监督学习的社区结构划分问题，实验表明该方法在分配内存中可以获得出色的聚类效果，同时提高了聚类速度。

Jul, 2020