Multi-way spectral partitioning and higher-order cheeger inequalities

DOI10.1145/2213977.2214078zbMath1286.05091arXiv1111.1055OpenAlexW2165755074MaRDI QIDQ5415539

James R. Lee, Luca Trevisan, Shayan Oveis Gharan

Publication date: 13 May 2014

Published in: Journal of the ACM, Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1111.1055

zbMATH Keywords

Cheeger's inequalityspectral algorithmsspectral clusteringsparsest cutCheeger inequalitiesspectral partitioningrandom partitions of metric spaces

Mathematics Subject Classification ID

Combinatorial probability (60C05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (62)

Spectral concentration and greedy \(k\)-clustering ⋮ On the multiplicity of Laplacian eigenvalues and Fiedler partitions ⋮ Unnamed Item ⋮ Improvements on Spectral Bisection ⋮ The structure of the genetic code as an optimal graph clustering problem ⋮ Cheeger Inequalities for General Edge-Weighted Directed Graphs ⋮ Unnamed Item ⋮ Persistent Laplacians: Properties, Algorithms and Implications ⋮ Mean isoperimetry with control on outliers: exact and approximation algorithms ⋮ Cheeger estimates of Dirichlet-to-Neumann operators on infinite subgraphs of graphs ⋮ Average Sensitivity of Graph Algorithms ⋮ Proof of the honeycomb asymptotics for optimal Cheeger clusters ⋮ Time-optimal construction of overlay networks ⋮ Unnamed Item ⋮ Clustering and outlier detection using isoperimetric number of trees ⋮ Multiway Spectral Graph Partitioning: Cut Functions, Cheeger Inequalities, and a Simple Algorithm ⋮ Upper bounds for higher-order Poincaré constants ⋮ Pseudo-orthogonality for graph 1-Laplacian eigenvectors and applications to higher Cheeger constants and data clustering ⋮ Some recent developments on the Steklov eigenvalue problem ⋮ A generalized Cheeger inequality ⋮ The Geometric Meaning of Curvature: Local and Nonlocal Aspects of Ricci Curvature ⋮ Step-by-step community detection in volume-regular graphs ⋮ A Note on Cheeger Inequalities for Piecewise Flat Surfaces ⋮ Localization of Neumann eigenfunctions near irregular boundaries ⋮ Multi-way sparsest cut problem on trees with a control on the number of parts and outliers ⋮ Graph Clustering using Effective Resistance ⋮ Multi-way dual Cheeger constants and spectral bounds of graphs ⋮ Criteria of spectral gap for Markov operators ⋮ Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile ⋮ Approximating Spectral Clustering via Sampling: A Review ⋮ On the Structure of Isometrically Embeddable Metric Spaces ⋮ On the hot spots of quantum graphs ⋮ Unnamed Item ⋮ Core–periphery structure in directed networks ⋮ The quality of genetic code models in terms of their robustness against point mutations ⋮ Partitioning Well-Clustered Graphs: Spectral Clustering Works! ⋮ Good (K-means) clusterings are unique (up to small perturbations) ⋮ Unnamed Item ⋮ Cheeger constants, structural balance, and spectral clustering analysis for signed graphs ⋮ Cheeger's cut, maxcut and the spectral theory of 1-Laplacian on graphs ⋮ Generalizing the hypergraph Laplacian via a diffusion process with mediators ⋮ Spectral graph theory via higher order eigenvalues and applications to the analysis of random walks ⋮ Frustration index and Cheeger inequalities for discrete and continuous magnetic Laplacians ⋮ Metropolis-Hastings reversiblizations of non-reversible Markov chains ⋮ Bipartite communities via spectral partitioning ⋮ Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem ⋮ Generalized quasirandom properties of expanding graph sequences ⋮ Convex programming based spectral clustering ⋮ Dirichlet \(p\)-Laplacian eigenvalues and Cheeger constants on symmetric graphs ⋮ Explore Intrinsic Geometry of Sleep Dynamics and Predict Sleep Stage by Unsupervised Learning Techniques ⋮ A distributed algorithm for spectral sparsification of graphs with applications to data clustering ⋮ Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs ⋮ Diffusion operator and spectral analysis for directed hypergraph Laplacian ⋮ Conformal growth rates and spectral geometry on distributional limits of graphs ⋮ Cheeger inequalities for the discrete magnetic Laplacian ⋮ On a Cheeger type inequality in Cayley graphs of finite groups ⋮ A Performance Guarantee for Spectral Clustering ⋮ Cheeger bounds on spin-two fields ⋮ On hyperboundedness and spectrum of Markov operators ⋮ Spectral distances on graphs ⋮ Escobar constants of planar domains ⋮ Distributed detection of clusters of arbitrary size

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On nodal domains and higher-order Cheeger inequalities of finite reversible Markov processes
• Probability in Banach spaces. Isoperimetry and processes
• Metric uniformization and spectral bounds for graphs
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• On eigenfunctions of Markov processes on trees
• Eigenvalues and expanders
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Inequalities in Fourier analysis
• Extending Lipschitz functions via random metric partitions
• On hyperboundedness and spectrum of Markov operators
• Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
• Hypercontra ctive semigroups and two dimensional self-coupled Bose fields
• A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs
• Approximations for the isoperimetric and spectral profile of graphs and related parameters
• Graph expansion and the unique games conjecture
• Algorithmic Extensions of Cheeger’s Inequality to Higher Eigenvalues and Partitions
• Subexponential Algorithms for Unique Games and Related Problems
• Graph Coloring Using Eigenvalue Decomposition
• Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Excluded minors, network decomposition, and multicommodity flow
• Hypercontractivity, sum-of-squares proofs, and their applications
• Many sparse cuts via higher eigenvalues
• A Nearly-m log n Time Solver for SDD Linear Systems
• A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

This page was built for publication: Multi-way spectral partitioning and higher-order cheeger inequalities