Wednesday, February 21, 2024 2pm to 3pm
About this Event
3620 South Vermont Avenue, Los Angeles, CA 90089
Catherine Babecki, Caltech
Abstract: 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.