  We consider effective preconditioners for solving Laplacians of general
weighted graphs. Theoretically, spectral sparsifiers (SSs) provide
preconditioners of optimal computational complexity. However, they are not easy
to use for real-world applications due to the implementation complications.
Multigrid (MG) methods, on the contrary, are computationally efficient but lack
of theoretical justifications. To bridge the gap between theory and practice,
we adopt ideas of MG and SS methods and proposed preconditioners that can be
used in practice with theoretical guarantees. We expand the original graph
based on a multilevel structure to obtain an equivalent expanded graph.
Although the expanded graph has a low diameter, a favorable property for
constructing SSs, it has negatively weighted edges, which is an unfavorable
property for the SSs. We design an algorithm to properly eliminate the
negatively weighted edges and prove that the resulting expanded graph with
positively weighted edges is spectrally equivalent to the expanded graph, thus,
the original graph. Due to the low-diameter property of the positively-weighted
expanded graph preconditioner (PEGP), existing algorithms for finding SSs can
be easily applied. To demonstrate the advantage of working with the PEGP, we
propose a type of SS, multilevel sparsifier preconditioner (MSP), that can be
constructed in an easy and deterministic manner. We provide some preliminary
numerical experiments to verify our theoretical findings and illustrate the
practical effectiveness of PEGP and MSP in real-world applications.
