On the maximal error of spectral approximation of graph bisection

DOI10.1080/03081087.2015.1133557MaRDI QIDQ3179158zbMATH OpenOpenAlexFDO

Authors John C. Urschel, Ludmil T. Zikatanov

Publication date 20 December 2016

Published in Linear and Multilinear Algebra (Search for Journal in Brave)

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

zbMATH Keywords

graph LaplacianFiedler vectorspectral bisection

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)

Abstract: Spectral graph bisections are a popular heuristic aimed at approximating the solution of the NP-complete graph bisection problem. This technique, however, does not always provide a robust tool for graph partitioning. Using a special class of graphs, we prove that the standard spectral graph bisection can produce bisections that are far from optimal. In particular, we show that the maximum error in the spectral approximation of the optimal bisection (partition sizes exactly equal) cut for such graphs is bounded below by a constant multiple of the order of the graph squared.

Recommendations

• Approximating the minimum bisection size (extended abstract)
• A spectral heuristic for bisecting random graphs
• A Polylogarithmic Approximation of the Minimum Bisection
• Spectral methods for graph bisection problems.
• New abilities and limitations of spectral graph bisection

Cites work

• A cascadic multigrid algorithm for computing the Fiedler vector of graph Laplacians
• A note on Laplacian graph eigenvalues
• A survey of graph laplacians
• Graph partitioning by eigenvectors
• Graph theory
• Laplacian graph eigenvectors
• Laplacian matrices of graphs: A survey
• Old and new results on algebraic connectivity of graphs
• On the Optimality of the Median Cut Spectral Bisection Graph Partitioning Method
• On the Quality of Spectral Separators
• Parallel Multilevel series k-Way Partitioning Scheme for Irregular Graphs
• Partitioning Sparse Matrices with Eigenvectors of Graphs
• Spectral bisection of graphs and connectedness

Cited in

(6)

• Agglomeration of polygonal grids using graph neural networks with applications to multigrid solvers
• Spectral methods for graph bisection problems.
• Fiedler vectors with unbalanced sign patterns
• On the structure of isometrically embeddable metric spaces
• Diffuse interface models on graphs for classification of high dimensional data
• Combinatorial Fiedler theory and graph partition

This page was built for publication: On the maximal error of spectral approximation of graph bisection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3179158)