More Web Proxy on the site http://driver.im/

research-article

Multi-way spectral partitioning and higher-order cheeger inequalities

Authors:

Shayan Oveis Gharan,

Luca TrevisanAuthors Info & Claims

STOC '12: Proceedings of the forty-fourth annual ACM symposium on Theory of computing

Pages 1117 - 1130

https://doi.org/10.1145/2213977.2214078

Published: 19 May 2012 Publication History

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 R^k, and then apply geometric considerations to the embedding.

We also show that these techniques yield a nearly optimal quantitative connection between the expansion of sets of size ≈ n/k and λ_k, the kth smallest eigenvalue of the normalized Laplacian, where n is the number of vertices. In particular, we show that in every graph there are at least k/2 disjoint sets (one of which will have size at most 2n/k), each having expansion at most O(√(λ_k log k)). Louis, Raghavendra, Tetali, and Vempala have independently proved a slightly weaker version of this last result [LRTV12]. The √(log k) bound is tight, up to constant factors, for the "noisy hypercube" graphs.

Supplementary Material

JPG File (stoc_13a_1.jpg)

Download
10.42 KB

MP4 File (stoc_13a_1.mp4)

Download
60.56 MB

References

[1]

Sanjeev Arora, Boaz Barak, and David Steurer. Subexponential algorithms for unique games and related problems. In FOCS, pages 563--572, Washington, DC, USA, 2010. IEEE Computer Society.

Digital Library

[2]

Bengt Aspvall and John R. Gilbert. Graph coloring using eigenvalue decomposition. Technical report, Ithaca, NY, USA, 1983.

Digital Library

[3]

Noga Alon and Nabil Kahale. A spectral technique for coloring random 3-colorable graphs. SIAM Journal on Computing, 26:1733--1748, 1997.

Digital Library

[4]

N Alon. Eigenvalues and expanders. Combinatorica, 6:83--96, January 1986.

Digital Library

[5]

N. Alon and V. Milman. Isoperimetric inequalities for graphs, and superconcentrators. Journal of Combinatorial Theory, Series B, 38(1):73--88, feb 1985.

[6]

William Beckner. Inequalities in Fourier analysis. Ann. of Math. (2), 102(1):159--182, 1975.

[7]

Aline Bonami. Étude des coefficients de Fourier des fonctions de L^p(G). Ann. Inst. Fourier (Grenoble), 20(fasc. 2):335--402 (1971), 1970.

[8]

S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. In Proceedings of the seventh International Wide Web Conference, 1998.

Digital Library

[9]

8}CCGGP98M. Charikar, C. Chekuri, A. Goel, S. Guha, and S. Plotkin. Approximating a finite metric by a small number of tree metrics. In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, 1998.

Digital Library

[10]

M. Charikar, C. Chekuri, A. Goel, and S. Guha. Rounding via trees: deterministic approximation algorithms for group Steiner trees and k-median. In 30th Annual ACM Symposium on Theory of Computing, pages 114--123. ACM, New York, 1998.

Digital Library

[11]

F. R. K. Chung. Laplacians of graphs and Cheeger's inequalities. In Combinatorics, Paul Erdos is eighty, Vol. 2 (Keszthely, 1993), volume 2 of Bolyai Soc. Math. Stud., pages 157--172. János Bolyai Math. Soc., Budapest, 1996.

[12]

Fan R. K. Chung. Spectral graph theory, volume 92 of CBMS Regional Conference Series in Mathematics. Published for the Conference Board of the Mathematical Sciences, Washington, DC, 1997.

[13]

J. Fakcharoenphol and K. Talwar. An improved decomposition theorem for graphs excluding a fixed minor. In Proceedings of 6th Workshop on Approximation, Randomization, and Combinatorial Optimization, volume 2764 of Lecture Notes in Computer Science, pages 36--46. Springer, 2003.

[14]

Anupam Gupta, Robert Krauthgamer, and James R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In 44th Symposium on Foundations of Computer Science, pages 534--543, 2003.

Digital Library

[15]

Jon M. Kleinberg. Authoritative sources in a hyperlinked environment. Journal of the ACM, 46:668--677, 1999.

Digital Library

[16]

J. Kelner, J. R. Lee, G. Price, and S.-H. Teng. Metric uniformization and spectral bounds for graphs. Geom. Funct. Anal., 21(5):1117--1143, 2011.

[17]

Philip N. Klein, Serge A. Plotkin, and Satish Rao. Excluded minors, network decomposition, and multicommodity flow. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing, pages 682--690, 1993.

Digital Library

[18]

James R. Lee and Assaf Naor. Extending Lipschitz functions via random metric partitions. Invent. Math., 160(1):59--95, 2005.

[19]

Anand Louis, Prasad Raghavendra, Prasad Tetali, and Santosh Vempala. Algorithmic extensions of Cheeger's inequality to higher eigenvalues and partitions. In APPROX-RANDOM, pages 315--326, 2011.

Digital Library

[20]

Anand Louis, Prasad Raghavendra, Prasad Tetali, and Santosh Vempala. Many sparse cuts via higher eigenvalues. In STOC, 2012.

Digital Library

[21]

J. R. Lee and A. Sidiropoulos. Genus and the geometry of the cut graph. In Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 193--201, 2010.

Digital Library

[22]

Michel Ledoux and Michel Talagrand. Probability in Banach spaces. Classics in Mathematics. Springer-Verlag, Berlin, 2011. Isoperimetry and processes, Reprint of the 1991 edition.

[23]

J. Matousek. Lectures on discrete geometry, volume 212 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2002.

Digital Library

[24]

Laurent Miclo. On eigenfunctions of Markov processes on trees. Probability Theory and Related Fields, 142(3--4):561--594, 2008.

[25]

Andrew Ng, Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. In NIPS'02, 2002.

[26]

Prasad Raghavendra and David Steurer. Graph expansion and the unique games conjecture. In STOC, pages 755--764, New York, NY, USA, 2010. ACM.

Digital Library

[27]

Prasad Raghavendra, David Steurer, and Prasad Tetali. Approximations for the isoperimetric and spectral profile of graphs and related parameters. In STOC, pages 631--640, New York, NY, USA, 2010. ACM.

Digital Library

[28]

Alistair J. Sinclair and Mark R. Jerrum. Approximative counting, uniform generation and rapidly mixing Markov chains. Information and Computation, 82(1):93--133, 1989.

Digital Library

[29]

Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell., 22(8):888--905, 2000.

Digital Library

[30]

David A. Tolliver and Gary L. Miller. Graph partitioning by spectral rounding: Applications in image segmentation and clustering. In CVPR '06: Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 1053--1060. IEEE Computer Society, 2006.

Digital Library

Cited By

Lau LTung KWang RSaha BServedio R(2023)Cheeger Inequalities for Directed Graphs and Hypergraphs using Reweighted EigenvaluesProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585139(1834-1847)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585139
Wu JChen XBadakhshan SZhang JWang P(2023)Spectral Graph Clustering for Intentional Islanding Operations in Resilient Hybrid Energy SystemsIEEE Transactions on Industrial Informatics10.1109/TII.2022.319924019:4(5956-5964)Online publication date: Apr-2023
https://doi.org/10.1109/TII.2022.3199240
Kwok TLau LTung K(2022)Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00042(366-377)Online publication date: Oct-2022
https://doi.org/10.1109/FOCS54457.2022.00042
Show More Cited By

Index Terms

Multi-way spectral partitioning and higher-order cheeger inequalities
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Multiway Spectral Partitioning and Higher-Order Cheeger Inequalities

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 ...
Cheeger Inequalities for Directed Graphs and Hypergraphs using Reweighted Eigenvalues
STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing

We derive Cheeger inequalities for directed graphs and hypergraphs using the reweighted eigenvalue approach that was recently developed for vertex expansion in undirected graphs. The goal is to develop a new spectral theory for directed graphs and an ...
Spectral partitioning works: planar graphs and finite element meshes
FOCS '96: Proceedings of the 37th Annual Symposium on Foundations of Computer Science

Spectral partitioning methods use the Fiedler vector-the eigenvector of the second-smallest eigenvalue of the Laplacian matrix-to find a small separator of a graph. These methods are important components of many scientific numerical algorithms and have ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '12: Proceedings of the forty-fourth annual ACM symposium on Theory of computing

May 2012

1310 pages

ISBN:9781450312455

DOI:10.1145/2213977

General Chair:
Howard Karloff
AT&T Labs--Research
,
Program Chair:
Toniann Pitassi
University of Toronto

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 May 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC'12

Sponsor:

SIGACT

STOC'12: Symposium on Theory of Computing

May 19 - 22, 2012

New York, New York, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

44
Total Citations
View Citations
60
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)3

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lau LTung KWang RSaha BServedio R(2023)Cheeger Inequalities for Directed Graphs and Hypergraphs using Reweighted EigenvaluesProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585139(1834-1847)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585139
Wu JChen XBadakhshan SZhang JWang P(2023)Spectral Graph Clustering for Intentional Islanding Operations in Resilient Hybrid Energy SystemsIEEE Transactions on Industrial Informatics10.1109/TII.2022.319924019:4(5956-5964)Online publication date: Apr-2023
https://doi.org/10.1109/TII.2022.3199240
Kwok TLau LTung K(2022)Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00042(366-377)Online publication date: Oct-2022
https://doi.org/10.1109/FOCS54457.2022.00042
Yan H(2022)Cheeger Inequalities for the Discrete Magnetic LaplacianThe Journal of Geometric Analysis10.1007/s12220-021-00813-y32:3Online publication date: 12-Jan-2022
https://doi.org/10.1007/s12220-021-00813-y
Liu JXia KWu JYau SWei G(2022)Biomolecular Topology: Modelling and AnalysisActa Mathematica Sinica, English Series10.1007/s10114-022-2326-538:10(1901-1938)Online publication date: 15-Oct-2022
https://doi.org/10.1007/s10114-022-2326-5
John JBeiranvand ACuffe P(2020)Clustering Nodes in a Directed Acyclic Graph By Identifying Corridors of Coherent Flow2020 6th IEEE International Energy Conference (ENERGYCon)10.1109/ENERGYCon48941.2020.9236507(604-609)Online publication date: 28-Sep-2020
https://doi.org/10.1109/ENERGYCon48941.2020.9236507
Funano KSakurai Y(2020)Upper bounds for higher-order Poincaré constantsTransactions of the American Mathematical Society10.1090/tran/8049373:6(4415-4436)Online publication date: 9-Mar-2020
https://doi.org/10.1090/tran/8049
Mizutani T(2020)Improved analysis of spectral algorithm for clusteringOptimization Letters10.1007/s11590-020-01639-3Online publication date: 8-Sep-2020
https://doi.org/10.1007/s11590-020-01639-3
Yancey KYancey M(2020)Bipartite communities via spectral partitioningJournal of Combinatorial Optimization10.1007/s10878-020-00574-444:3(1995-2028)Online publication date: 25-Apr-2020
https://doi.org/10.1007/s10878-020-00574-4
Kelle DAbur A(2019)Improving Performance of Multi-Area State Estimation Using Spectral Clustering2019 North American Power Symposium (NAPS)10.1109/NAPS46351.2019.8999981(1-6)Online publication date: Oct-2019
https://doi.org/10.1109/NAPS46351.2019.8999981
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents