Spectrahedral geometry of graph sparsifiers
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.
- Codes, cubes, and graphical designs
- Diffusion maps
- Eigenpolytope Universality and Graphical Designs
- Expander graphs and their applications
- Generalized designs on graphs: Sampling, spectra, symmetries
- Graphical designs and extremal combinatorics
- Graphical designs and gale duality
- scientific article; zbMATH DE number 3337135 (Why is no real title available?)
- Improved Cheeger's inequality and analysis of local graph partitioning using vertex expansion and expansion profile
- Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
- Laplacian graph eigenvectors
- Multi-way dual Cheeger constants and spectral bounds of graphs
- Multi-way spectral partitioning and higher-order Cheeger inequalities
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- On the diffusion geometry of graph Laplacians and applications
- Semidefinite Optimization and Convex Algebraic Geometry
- Sparse sums of positive semidefinite matrices
- Spectra of graphs
- Spectral clustering revisited: information hidden in the Fiedler vector
- Spectral concentration and greedy k-clustering
- Spectral limitations of quadrature rules and generalized spherical designs
- Spectral sparsification of graphs
- The geometry of nodal sets and outlier detection
- The product of two high-frequency graph Laplacian eigenfunctions is smooth
- Twice-Ramanujan sparsifiers
- Universal matrix sparsifiers and fast deterministic algorithms for linear algebra
This page was built for publication: Spectrahedral geometry of graph sparsifiers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7020160)
