SF-GRASS: Solver-Free Graph Spectral Sparsification

Ying Zhang, Zhiqiang Zhao, Zhuo Feng

Research output: Contribution to journalConference articlepeer-review

11 Scopus citations

Abstract

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.

Original languageEnglish
Article number9256784
JournalIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
Volume2020-November
DOIs
StatePublished - 2 Nov 2020
Event39th IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2020 - Virtual, San Diego, United States
Duration: 2 Nov 20205 Nov 2020

Keywords

  • Spectral graph sparsification
  • graph signal processing
  • spectral coarsening

Fingerprint

Dive into the research topics of 'SF-GRASS: Solver-Free Graph Spectral Sparsification'. Together they form a unique fingerprint.

Cite this