Pursuing More Effective Graph Spectral Sparsifiers via Approximate Trace Reduction
TimeWednesday, July 13th1:30pm - 2pm PDT
Location3004, Level 3
Event Type
Research Manuscript
Analog Design, Simulation, Verification and Test
DescriptionSpectral graph sparsification aims to find ultra-sparse subgraphs which can preserve spectral properties of original graphs. In this paper, a novel spectral graph sparsification algorithm is proposed. 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 incomplete inverse method are proposed for computing approximate trace reduction efficiently. Combining these techniques with the iterative densification scheme, we develop a highly effective graph sparsification algorithm. Experimental results show that the proposed method is more effective than the state-of-the-art method GRASS under both sparsity-aware and similarity-aware settings.