Multiway Spectral Graph Partitioning: Cut Functions, Cheeger Inequalities, and a Simple Algorithm

DOI10.1137/23m1551936arXiv2302.03615OpenAlexW4390741814MaRDI QIDQ6139651

Lars Eldén

Publication date: 19 January 2024

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

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

zbMATH Keywords

eigenvalueadjacency matrixundirected graphcut functionCheeger inequalityindicator formmultiway spectral partitioning

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) 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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A local search approximation algorithm for \(k\)-means clustering
• Multiway spectral clustering: a margin-based perspective
• Multiway \(p\)-spectral graph cuts on Grassmann manifolds
• Measuring the stability of spectral clustering
• Semi-sparse PCA
• Partitioning Sparse Matrices with Eigenvectors of Graphs
• The Geometry of Algorithms with Orthogonality Constraints
• A Note On Spectral Clustering
• First-principles multiway spectral partitioning of graphs
• Multi-Scale attributed node embedding
• Simple, direct and efficient multi-way spectral clustering
• Collective dynamics of ‘small-world’ networks
• Multi-way spectral partitioning and higher-order cheeger inequalities
• Many sparse cuts via higher eigenvalues
• Depth-First Search and Linear Graph Algorithms
• Partitioning Well-Clustered Graphs: Spectral Clustering Works!
• Matrix Analysis and Applied Linear Algebra, Second Edition