Spectral partitioning with blends of eigenvectors

James P. Fairbanks, David A. Bader, Geoffrey D. Sanders

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


Many common methods for data analysis rely on linear algebra. We provide new results connecting data analysis error to numerical accuracy in the context of spectral graph partitioning. We provide pointwise convergence guarantees so that spectral blends (linear combinations of eigenvectors) can be employed to solve data analysis problems with confidence in their accuracy.We apply this theory to an accessible model problem, the ring of cliques, by deriving the relevant eigenpairs and finding necessary and sufficient solver tolerances. Analysis of the ring of cliques provides an upper bound on eigensolver tolerances for graph partitioning problems. These results bridge the gap between linear algebra based data analysis methods and the convergence theory of iterative approximation methods. These results explain how the combinatorial structure of a problem can be recovered much faster than numerically accurate solutions to the associated linear algebra problem.

Original languageEnglish (US)
Article numbercnw033
Pages (from-to)551-580
Number of pages30
JournalJournal of Complex Networks
Issue number4
StatePublished - Aug 1 2017
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Management Science and Operations Research
  • Control and Optimization
  • Computational Mathematics
  • Applied Mathematics


  • Approximation algorithms
  • Community detection
  • Data analysis
  • Data mining
  • Eigenvalues and eigenfunctions
  • Graph partitioning
  • Iterative methods
  • Laplace equations
  • Partitioning algorithms


Dive into the research topics of 'Spectral partitioning with blends of eigenvectors'. Together they form a unique fingerprint.

Cite this