ABSTRACT

Spectral methods are playing increasingly important roles in many graph and numerical applications. This research plan will investigate a truly-scalable yet unified spectral graph reduction approach that allows reducing large-scale, real-world directed and undirected graphs with guaranteed preservation of the original graph spectra. The success of the proposed research will significantly advance the state of the arts in spectral graph theory, electronic design automation (EDA), data mining, machine learning, as well as scientific computing, leading to the development of much faster numerical and graph-based algorithms. The algorithms and methodologies to be developed will be disseminated to leading technology companies such as EDA software and network companies for potential industrial adoptions. Spectral graph reduction algorithms/software packages will also be made available to other researchers through collaborations.

The project will investigate a truly-scalable yet unified spectral graph reduction approach by exploiting a scalable (nearly-linear complexity) spectral matrix perturbation analysis framework for constructing nearly-linear sized subgraphs that can well preserve the key eigenvalues and eigenvectors of the original graph Laplacians. Unlike prior methods that are only suitable for handling specific types of graphs (e.g. undirected or strongly-connected graphs), this project uses a more universal approach and thus will allow for spectral reduction of a much wider range of real-world graphs that may involve billions of elements: spectrally-reduced social (data) networks allow for more efficiently modeling, mining and analysis of large social (data) networks; spectrally-reduced neural networks allow for more scalable model training and processing in emerging machine learning tasks; spectrally-reduced web-graphs allow for much faster computations of personalized PageRank vectors; spectrally-reduced integrated circuit networks will lead to more efficient partitioning, modeling, simulation, optimization and verification of large chip designs, etc.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

Please report errors in award information by writing to: awardsearch@nsf.gov.