论文标题
通过近似痕量降低追求更有效的图形光谱稀疏器
Pursuing More Effective Graph Spectral Sparsifiers via Approximate Trace Reduction
论文作者
论文摘要
光谱图的稀疏旨在找到可以保留原始图的光谱特性的超图形子图。在本文中，首先引入了基于痕量降低的新频谱临界度度量，以识别频谱上重要的外部图边缘。然后，提出了一种由物理启发的截断策略和使用近似cholesky因子的近似逆因素的方法有效地计算近似痕量降低。将它们与\ cite {Feng2019grass}中的迭代致密化方案相结合，并在\ cite {fegrass}中排除了频谱上相似的外部边缘边缘的策略，我们开发了一种非常有效的图形稀疏算法。所提出的方法已通过各种图表进行了验证。实验结果表明，它始终以相同的计算成本产生比最先进的草\ cite {Feng2019grass}的稀疏器，其质量相同，从而使预处理的迭代方程求解器平均降低了40％以上的时间。在功率电网瞬态分析和光谱图分区的应用中，基于直接稀疏求解器的方法，派生的迭代求解器在运行时和内存成本上显示了3.3倍或更多优势。
Spectral graph sparsification aims to find ultra-sparse subgraphs which can preserve spectral properties of original graphs. In this paper, a new spectral criticality metric based on trace reduction is first introduced for identifying spectrally important off-subgraph edges. Then, a physics-inspired truncation strategy and an approach using approximate inverse of Cholesky factor are proposed to compute the approximate trace reduction efficiently. Combining them with the iterative densification scheme in \cite{feng2019grass} and the strategy of excluding spectrally similar off-subgraph edges in \cite{fegrass}, we develop a highly effective graph sparsification algorithm. The proposed method has been validated with various kinds of graphs. Experimental results show that it always produces sparsifiers with remarkably better quality than the state-of-the-art GRASS \cite{feng2019grass} in same computational cost, enabling more than 40% time reduction for preconditioned iterative equation solver on average. In the applications of power grid transient analysis and spectral graph partitioning, the derived iterative solver shows 3.3X or more advantages on runtime and memory cost, over the approach based on direct sparse solver.
