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 inequality spectral algorithms spectral clustering sparsest cut Cheeger inequalities spectral partitioning random 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

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