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

Aug, 2008

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

Feb, 2017

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

Jul, 2014

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

Nov, 2016

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

Dec, 2009

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

Jun, 2024

这篇论文证明了每个图形都有一个谱稀疏器，其边数与其顶点数成线性关系。特别地，通过 Laplacian matrices 构造的谱稀疏器提供了对图形的光谱映射，令其成为扩展图的推广。此外，该论文提供了一个简单的确定性多项式时间算法来构造这种稀疏器。

Aug, 2008

本论文解决了计算矩阵多项式的谱稀疏矩阵的基本算法问题，在最近线性时间内构造了一个带有少量非零元的拉普拉斯矩阵，近似于给定的矩阵多项式；该算法可用于多步时间可逆马尔可夫模型的有效电阻的构建，以及网络分析中的其他任务。

Feb, 2015

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

Nov, 2019

该研究提出一种几乎线性时间算法，用于生成加权图的高质量减少子集。算法包含一个独立的子程序，可用于在几乎线性时间内创建数据结构，从而可以在 $O (log n)$ 时间内查询图中任意两个顶点之间的近似有效电阻。

Mar, 2008