本文提出了一种利用角度信息和奇异值分解的子线性时间图聚类算法，并在其基础上给出了测试聚类可行性的查询复杂度下界，并且通过这些技术，也实现了新的子线性时间下界近似最大割价值的问题。

Aug, 2018

研究了具有度数限制的图形，证明了其局部邻域统计与 “平面图” 不同，并由此推断出很多图形的特性和性质可以通过少量的查询进行测试。

Jan, 2008

我们设计了一个次线性时间的谱聚类预处理方法来解决在具有强聚类性的图中的问题。我们的算法通过在次线性时间内进行预处理和查询回答，得到与实际聚类接近的 $k$-partition。我们的实验证明了我们的理论性能。

Oct, 2023

本研究的主要贡献是提出了一种使用子线性时间的谱聚类算法，该算法可以将图按照展开器分簇，并可以提高聚类的准确性，同时通过估计图中节点的随机游走的分布，实现对谱嵌入的点积访问，并使用谱嵌入进行超平面划分，从而实现聚类。

Jan, 2021

论文提出了信息论阈值的上下界，并进一步证明了当组数较大且特定参数取值时，物理条件下的凝聚阈值是具有严格界限的，若邻居间与组间边缘概率不同，则分配问题可以解决，否则无算法可优于随机。

Jan, 2016

研究了如何检测随机图中的高维几何结构问题，提出了一种基于新量的近乎最优和高效的测试方法，并针对稠密和稀疏情况提出了检测界和估计维度的猜想。

Nov, 2014

本文介绍了一种使用谱算法的简单多项式时间用于进行图分割的方法，旨在寻找具有网络传导性和诱导子图的低导纳集合，并且提出了一种找到最佳 k 聚类的方法，其中 k 是一个整数，而且这种方法与 Cheeger's inequality 有所不同。

Sep, 2013

本文提出了一种基于随机游走的局部聚类算法，通过将内部连接性参数考虑入内，改进了先前结果，得到更优秀的聚类精度和 conductance，并探讨了其与全局谱算法之间的联系。

Apr, 2013

针对具有清晰社区结构的有符号图，我们提供了本地聚类算法，可以在只读取图形的一小部分的情况下，在亚线性时间中回答会员查询并正确分类节点。

Jun, 2022

本文提出了能够在接近于线性的时间内找到稀疏切割的近似算法，解决了设计拥有近似保证的局部图聚类算法的开放性问题，并且其近似保证与 Cheeger 不等式相当。

Apr, 2012