Spectrahedral geometry of graph sparsifiers (Q7020160)

In this paper, the authors propose an approach to graph sparsification based on the idea of preserving the smallest \(k\) eigenvalues and their corresponding eigenvectors of the graph Laplacian. It 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 those of \(G\) is the intersection of a polyhedron with a cone of positive semidefinite matrices. The geometry of these sets is discussed, and the natural scale of \(k\) is deduced. Various families of graphs illustrate the construction. The results obtained in this paper are interesting. One may see the important relationship between the spectral graph theory and the geometry of graphs.