Towards scalable spectral sparsification of directed graphs

Ying Zhang, Zhiqiang Zhao, Zhuo Feng

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

2 Scopus citations

Abstract

Recent spectral graph sparsification research allows constructing nearly-linear-sized subgraphs that can well preserve the spectral (structural) properties of the original graph, such as the the first few eigenvalues and eigenvectors of the graph Laplacian, leading to the development of a variety of nearly-linear time numerical and graph algorithms. However, there is not a unified approach that allows for truly-scalable spectral sparsification of both directed and undirected graphs. For the first time, we prove the existence of linear-sized spectral sparsifiers for general directed graphs, and introduce a practically-efficient yet unified spectral graph sparsification approach that allows sparsifying real-world, large-scale directed and undirected graphs with guaranteed preservation of the original graph spectra. By exploiting a highly-scalable (nearly-linear complexity) spectral matrix perturbation analysis framework for constructing nearly-linear sized (directed) subgraphs, it enables to well preserve the key eigenvalues and eigenvectors of the original (directed) graph Laplacians.

Original languageEnglish
Title of host publication2019 IEEE International Conference on Embedded Software and Systems, ICESS 2019
ISBN (Electronic)9781728124377
DOIs
StatePublished - Jun 2019
Event2019 IEEE International Conference on Embedded Software and Systems, ICESS 2019 - Las Vegas, United States
Duration: 2 Jun 20193 Jun 2019

Publication series

Name2019 IEEE International Conference on Embedded Software and Systems, ICESS 2019

Conference

Conference2019 IEEE International Conference on Embedded Software and Systems, ICESS 2019
Country/TerritoryUnited States
CityLas Vegas
Period2/06/193/06/19

Fingerprint

Dive into the research topics of 'Towards scalable spectral sparsification of directed graphs'. Together they form a unique fingerprint.

Cite this