ECE Seminar: Towards Scalable Spectral Sparsification of Large Graphs, Integrated Circuits and Data Networks

Spectral graph sparsification aims to find ultra-sparse graph sparsifiers (subgraphs) that can well preserve the key eigenvalues and eigenvectors of the original graph Laplacians. Recent theoretic computer science research results show that spectral graph sparsification can lead to the development of a series of ``theoretically nearly-linear-time" numerical and graph algorithms for solving sparse matrices, graph-based semi-supervised learning (SSL), spectral graph partitioning (data clustering), and max-flow problems. For example, spectrally sparsified transportation networks will lead to the development of more scalable navigation or routing algorithms for large transportation systems; spectrally sparsified social networks will enable more effective understanding and prediction of information propagation in large social networks; spectrally sparsified data networks will allow more efficiently storing, partitioning, and analyzing big data networks; spectrally sparsified matrices can be leveraged to more efficiently compute the solution of large linear system of equations; spectrally sparsified circuit networks can lead to more scalable design automation of large integrated circuit systems, etc. However, the long-standing question of whether there exists a practically-efficient spectral graph sparsification algorithm for tackling general large-scale, real-world graphs still remains.