TY - GEN
T1 - Towards scalable spectral sparsification of directed graphs
AU - Zhang, Ying
AU - Zhao, Zhiqiang
AU - Feng, Zhuo
N1 - Publisher Copyright:
© 2019 IEEE.
PY - 2019/6
Y1 - 2019/6
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85070856448&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85070856448&partnerID=8YFLogxK
U2 - 10.1109/ICESS.2019.8782449
DO - 10.1109/ICESS.2019.8782449
M3 - Conference contribution
AN - SCOPUS:85070856448
T3 - 2019 IEEE International Conference on Embedded Software and Systems, ICESS 2019
BT - 2019 IEEE International Conference on Embedded Software and Systems, ICESS 2019
T2 - 2019 IEEE International Conference on Embedded Software and Systems, ICESS 2019
Y2 - 2 June 2019 through 3 June 2019
ER -