Effective-resistance preserving spectral reduction of graphs

Zhiqiang Zhao, Zhuo Feng

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

9 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationProceedings of the 56th Annual Design Automation Conference 2019, DAC 2019
ISBN (Electronic)9781450367257
DOIs
StatePublished - 2 Jun 2019
Event56th Annual Design Automation Conference, DAC 2019 - Las Vegas, United States
Duration: 2 Jun 20196 Jun 2019

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0738-100X

Conference

Conference56th Annual Design Automation Conference, DAC 2019
Country/TerritoryUnited States
CityLas Vegas
Period2/06/196/06/19

Keywords

  • Graph reduction
  • Spectral graph theory
  • Spectral partitioning

Fingerprint

Dive into the research topics of 'Effective-resistance preserving spectral reduction of graphs'. Together they form a unique fingerprint.

Cite this