SF-GRASS: Solver-Free Graph Spectral Sparsification
SF-GRASS: Solver-Free Graph Spectral Sparsification
复制标题
DOI：
10.1145/3400302.3415629
复制
发表时间：
2020-08
期刊：
影响因子：
--
通讯作者：
Ying Zhang;Zhiqiang Zhao;Zhuo Feng
中科院分区：
文献类型：
--
作者：
Ying Zhang;Zhiqiang Zhao;Zhuo Feng
最近的谱图稀疏化技术在加速许多数值和图形算法方面表现出了良好的性能，例如用于求解大型稀疏矩阵的迭代方法，无向图的谱划分，电力/热网格的无向量验证，大型图的表示学习等。然而，先前的谱图稀疏化方法依赖于快速拉普拉斯矩阵求解器，这些求解器通常在实践中具有挑战性。这项工作，第一次，介绍了一种无求解器的方法（SF-GRASS）的频谱图稀疏化，利用新兴的频谱图粗化和图形信号处理（GSP）技术。我们引入了一个局部谱嵌入方案，用于有效地识别谱临界边缘，这些边缘是保持图谱特性的关键，例如前几个拉普拉斯特征值和特征向量。由于SF-GRASS中的关键核函数可以使用稀疏矩阵向量乘法（SpMV）有效地实现，因此所提出的谱方法易于实现并且具有固有的并行友好性。我们广泛的实验结果表明，所提出的方法可以产生一个层次的高品质的频谱稀疏在近线性时间的各种现实世界中，大规模的图形和电路网络相比，与现有的国家的最先进的频谱方法。
Recent spectral graph sparsification techniques have shown promising performance in accelerating many numerical and graph algorithms, such as iterative methods for solving large sparse matrices, spectral partitioning of undirected graphs, vectorless verification of power/thermal grids, representation learning of large graphs, etc. However, prior spectral graph sparsification methods rely on fast Laplacian matrix solvers that are usually challenging to implement in practice. This work, for the first time, introduces a solver-free approach (SF-GRASS) for spectral graph sparsification by leveraging emerging spectral graph coarsening and graph signal processing (GSP) techniques. We introduce a local spectral embedding scheme for efficiently identifying spectrally-critical edges that are key to preserving graph spectral properties, such as the first few Laplacian eigenvalues and eigenvectors. Since the key kernel functions in SF-GRASS can be efficiently implemented using sparse-matrix-vector-multiplications (SpMVs), the proposed spectral approach is simple to implement and inherently parallel friendly. Our extensive experimental results show that the proposed method can produce a hierarchy of high-quality spectral sparsifiers in nearly-linear time for a variety of real-world, large-scale graphs and circuit networks when compared with prior state-of-the-art spectral methods.