Spectral Sparsification of Random-Walk Matrix Polynomials

Dehua Cheng, Yu Cheng, Yan Liu +2

We consider a fundamental algorithmic question in spectral graph theory: Compute a spectral sparsifier of random-walk matrix-polynomial $$L_{\alpha }(G)=D-\sum _{r=1}^d{\alpha }_{r}D(D^{-1}A{)}^r$$ whe…