Spectrahedral Geometry of Graph Sparsifiers

We propose an approach to graph sparsification based on the idea of preserving the smallest k eigenvalues and eigenvectors of the Graph Laplacian. This is motivated by the fact that small eigenvalues and their associated eigenvectors tend to be more informative of the global structure and geometry of the graph than larger eigenvalues and their eigenvectors. The set of all weighted subgraphs of a graph G that have the same first k eigenvalues (and eigenvectors) as G is the intersection of a polyhedron with a cone of positive semidefinite matrices. We discuss the geometry of these sets and deduce the natural scale of k. Various families of graphs illustrate our construction.

National Science Foundation (NSF): DMS-2123224

National Science Foundation (NSF): DMS-1929284

 

Funding: The first author was supported by the NSF (DMS-1929284) while in residence at ICERM in Providence, Rhode Island, during the Discrete Optimization Semester program. The second author was supported by the NSF (DMS-2123224) and by the Alfred P. Sloan Foundation. The third author was supported by the Walker Family Endowed Professorship at the University of Washington.