A basic fact in spectral graph theory is that the number of connected components in an undirected graph is equal to the multiplicity of the eigenvalue zero in the Laplacian matrix of the graph. In particular, the graph is disconnected if and only if there are at least two eigenvalues equal to zero. Cheeger's inequality and its variants provide an approximate version of the latter fact; they state that a graph has a sparse cut if and only if there are at least two eigenvalues that are close to zero. It has been conjectured that an analogous characterization holds for higher multiplicities, i.e., there are k eigenvalues close to zero if and only if the vertex set can be partitioned into k subsets, each defining a sparse cut. We resolve this conjecture. Our result provides a theoretical justification for clustering algorithms that use the bottom k eigenvectors to embed the vertices into Rk, and then apply geometric considerations to the embedding. We also show that these techniques yield a nearly optimal tradeoff between the expansion of sets of size ≈n/k, and the kth smallest eigenvalue of the normalized Laplacian matrix, denoted λk. In particular, we show that in every graph there is a set of size at most 2n/k which has expansion at most O(λklogk−−−−−−√). This bound is tight, up to constant factors, for the "noisy hypercube" graphs.

Multiway spectral partitioning and higher-order cheeger inequalities

Trevisan, Luca
Membro del Collaboration Group
2014

Abstract

A basic fact in spectral graph theory is that the number of connected components in an undirected graph is equal to the multiplicity of the eigenvalue zero in the Laplacian matrix of the graph. In particular, the graph is disconnected if and only if there are at least two eigenvalues equal to zero. Cheeger's inequality and its variants provide an approximate version of the latter fact; they state that a graph has a sparse cut if and only if there are at least two eigenvalues that are close to zero. It has been conjectured that an analogous characterization holds for higher multiplicities, i.e., there are k eigenvalues close to zero if and only if the vertex set can be partitioned into k subsets, each defining a sparse cut. We resolve this conjecture. Our result provides a theoretical justification for clustering algorithms that use the bottom k eigenvectors to embed the vertices into Rk, and then apply geometric considerations to the embedding. We also show that these techniques yield a nearly optimal tradeoff between the expansion of sets of size ≈n/k, and the kth smallest eigenvalue of the normalized Laplacian matrix, denoted λk. In particular, we show that in every graph there is a set of size at most 2n/k which has expansion at most O(λklogk−−−−−−√). This bound is tight, up to constant factors, for the "noisy hypercube" graphs.
2014
Lee, James R.; Gharan, Shayan Oveis; Trevisan, Luca
File in questo prodotto:
File Dimensione Formato  
2665063.pdf

non disponibili

Descrizione: article
Tipologia: Pdf editoriale (Publisher's layout)
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 287.61 kB
Formato Adobe PDF
287.61 kB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11565/4035321
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 117
  • ???jsp.display-item.citation.isi??? 101
social impact