子线性时间下的谱聚类预测器

Jan, 2021

Spectral Clustering Oracles in Sublinear Time

Grzegorz Gluch, Michael Kapralov, Silvio Lattanzi, Aida Mousavifar, Christian Sohler

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

Abstract

Given a graph $G$ that can be partitioned into $k$ disjoint expanders with outer conductance upper bounded by $\epsilon\ll 1$, can we efficiently construct a small space data structure that allows quickly classif

spectral clustering expanders data structure sublinear time spectral embeddings

发现论文，激发创造

改进预处理时间的次线性时间谱聚类预测模型

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

Oct, 2023

带符号图的亚线性时间聚类神谕

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

Jun, 2022

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

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

Oct, 2023

近似扩张剖面和几乎最优局部图聚类

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

Apr, 2012

扩张图的划分

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

Sep, 2013

测试图的聚类能力：算法和下限

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

Aug, 2018

测试图的聚类结构

在有界度模型的性质测试框架中研究了识别图的集群结构问题，提出了一个亚线性算法，可识别由参数 k, phi, epsilon 制定的 (d) 有界度图，并且是渐近最优的，关键是集群内外的 conductance。

Apr, 2015

核范数中的快速谱密度估计与稀疏化

利用一种随机算法和核稀疏化的方法，该研究提出了一种新的图谱估计方法，可在线性时间和多项式查询复杂度下，准确估计归一化邻接矩阵的谱密度。这一方法在复杂度和准确性方面均具有优势，且创造性地解决了图的稀疏化和添加谱稀疏化的相关问题。

Jun, 2024

改进的 Cheeger 不等式：通过高阶谱间隙分析谱分裂算法

该研究证明了基于谱的划分算法可以在保证性能的同时，实现稀疏切割，同时将分析扩展到其他图划分问题中。

Jan, 2013

基于 SDP 的线性大小谱稀疏化算法

本篇研究将提出一种计算效率更高的算法来构建图的 $(1 + ϵ)$- 频谱稀疏子图，该算法基于三种新技术，并使用新的潜力函数，通过半定规划求解构造单侧频谱稀疏子图。

Feb, 2017