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

Feb, 2017

本研究提出了第一个近乎线性时间的算法，用于构建具有线性大小的图谱稀疏化。该算法采用文献中用于构建光谱稀疏化的两种技术的新组合：基于有效电阻的随机采样和基于障碍函数的自适应构造。

Aug, 2015

本文考虑保留原图的一个子图、寻找 k - 边加权图来加强原图的谱稀疏化问题，给出可行条件及多项式时间算法，并在超稀疏化问题和谱优化问题方面得出了应用结果。

Dec, 2009

本文研究了网络或图谱的光谱问题。在图太大无法明确计算光谱的情况下，提出了一种次线性时间算法，可以计算光谱的简洁表示，并证明了其实用性。同时探讨了该算法在有界度图模型下的属性测试的实际应用。

Dec, 2017

本文提出了一种面向有向图的射影逼近概念，并利用该方法构建了一个广泛启发自 Peng-Spielman 的对称线性系统求解框架，通过结合近乎线性时间的稀疏化算法，得到求解定向 Laplacian 线性系统的近乎线性时间算法，本算法的时间复杂度优于现有最优解。

Nov, 2016

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

Jan, 2021

本文提出了一套可证明的逼近算法，通过删除最小成本的边（建立隔离区）或节点（建立疫苗接种）来减少网络的谱半径，主要算法基于敲定特定长度封闭路径的思想，性能较之前的启发式算法更优，实验证明了算法的可行性和解的属性。

Jan, 2015

本文提出了一种基于图拉普拉斯矩阵谱相似性的新型图稀疏化方法，证明了任何图都有近乎线性大小的谱稀疏化，并给出了一个可在几乎线性时间内构建谱稀疏化的算法，该方法的关键组成部分之一是对具有强保证的近乎线性时间图划分算法的使用。

Aug, 2008

我们提出了一种动态半流模型下用于计算图形谱稀疏化的首个单趟算法，该算法使用线性素描将 G 的入射矩阵维护为 O ((1/epsilon^2) n*.polylog (n)) 维，可以输出高概率下 G 的 (1+/-epsilon) 谱稀疏化。该方法利用了 G 的粗略稀疏器和 G 的入射矩阵的线性素描，通过等效电阻抽样边缘以得到任意精度的谱稀疏化。

Jul, 2014

本文提出了一种相似性感知的谱图稀疏化框架，利用有效的谱偏树边嵌入和过滤方案构建谱稀疏化，实现了保证谱相似度（相对条件数）水平的过滤，同时介绍了迭代图密度增加方案以促进高度病态问题的有效过滤。该方法已验证了各种公共领域稀疏矩阵收集到的图表，包括与 VLSI CAD、有限元分析、社会和数据网络频繁研究的许多机器学习和数据挖掘应用相关的图表。

Nov, 2019