TY - GEN
T1 - Effective-resistance preserving spectral reduction of graphs
AU - Zhao, Zhiqiang
AU - Feng, Zhuo
N1 - Publisher Copyright:
© 2019 Association for Computing Machinery.
PY - 2019/6/2
Y1 - 2019/6/2
N2 - This paper proposes a scalable algorithmic framework for effectiveresistance preserving spectral reduction of large undirected graphs. The proposed method allows computing much smaller graphs while preserving the key spectral (structural) properties of the original graph. Our framework is built upon the following three key components: a spectrum-preserving node aggregation and reduction scheme, a spectral graph sparsification framework with iterative edge weight scaling, as well as effective-resistance preserving postscaling and iterative solution refinement schemes. By leveraging recent similarity-aware spectral sparsification method and graphtheoretic algebraic multigrid (AMG) Laplacian solver, a novel constrained stochastic gradient descent (SGD) optimization approach has been proposed for achieving truly scalable performance (nearlylinear complexity) for spectral graph reduction. We show that the resultant spectrally-reduced graphs can robustly preserve the first few nontrivial eigenvalues and eigenvectors of the original graph Laplacian and thus allow for developing highly-scalable spectral graph partitioning and circuit simulation algorithms.
AB - This paper proposes a scalable algorithmic framework for effectiveresistance preserving spectral reduction of large undirected graphs. The proposed method allows computing much smaller graphs while preserving the key spectral (structural) properties of the original graph. Our framework is built upon the following three key components: a spectrum-preserving node aggregation and reduction scheme, a spectral graph sparsification framework with iterative edge weight scaling, as well as effective-resistance preserving postscaling and iterative solution refinement schemes. By leveraging recent similarity-aware spectral sparsification method and graphtheoretic algebraic multigrid (AMG) Laplacian solver, a novel constrained stochastic gradient descent (SGD) optimization approach has been proposed for achieving truly scalable performance (nearlylinear complexity) for spectral graph reduction. We show that the resultant spectrally-reduced graphs can robustly preserve the first few nontrivial eigenvalues and eigenvectors of the original graph Laplacian and thus allow for developing highly-scalable spectral graph partitioning and circuit simulation algorithms.
KW - Graph reduction
KW - Spectral graph theory
KW - Spectral partitioning
UR - http://www.scopus.com/inward/record.url?scp=85067833488&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85067833488&partnerID=8YFLogxK
U2 - 10.1145/3316781.3317809
DO - 10.1145/3316781.3317809
M3 - Conference contribution
AN - SCOPUS:85067833488
T3 - Proceedings - Design Automation Conference
BT - Proceedings of the 56th Annual Design Automation Conference 2019, DAC 2019
T2 - 56th Annual Design Automation Conference, DAC 2019
Y2 - 2 June 2019 through 6 June 2019
ER -