  Spectral graph sparsification aims to find ultra-sparse subgraphs whose
Laplacian matrix can well approximate the original Laplacian eigenvalues and
eigenvectors. In recent years, spectral sparsification techniques have been
extensively studied for accelerating various numerical and graph-related
applications. Prior nearly-linear-time spectral sparsification methods first
extract low-stretch spanning tree from the original graph to form the backbone
of the sparsifier, and then recover small portions of spectrally-critical
off-tree edges to the spanning tree to significantly improve the approximation
quality. However, it is not clear how many off-tree edges should be recovered
for achieving a desired spectral similarity level within the sparsifier.
Motivated by recent graph signal processing techniques, this paper proposes a
similarity-aware spectral graph sparsification framework that leverages
efficient spectral off-tree edge embedding and filtering schemes to construct
spectral sparsifiers with guaranteed spectral similarity (relative condition
number) level. An iterative graph densification scheme is also introduced to
facilitate efficient and effective filtering of off-tree edges for highly
ill-conditioned problems. The proposed method has been validated using various
kinds of graphs obtained from public domain sparse matrix collections relevant
to VLSI CAD, finite element analysis, as well as social and data networks
frequently studied in many machine learning and data mining applications. For
instance, a sparse SDD matrix with 40 million unknowns and 180 million nonzeros
can be solved (1E-3 accuracy level) within two minutes using a single CPU core
and about 6GB memory.
