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

Dec, 2009

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

Aug, 2008

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

Aug, 2015

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

Aug, 2008

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

Jul, 2014

本研究介绍了一种基于递增稀疏化的算法，可在输入 n 个顶点和 m 条边的加权图以及一个值 k 后，产生一个有限边数为 n-1+m/k 的递增稀疏化图，较好地维持了图的条件数，并以很快的速度求解出满足一定误差要求的向量，这一算法基于 Chebyshev 迭代和递归算法实现。

Mar, 2010

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

Jun, 2024

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

Mar, 2008

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

Nov, 2016

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

Feb, 2015