  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.
