  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.
