On the Maximal Error of Spectral Approximation of Graph Bisection
For researchers using spectral methods for graph partitioning, this work highlights a fundamental limitation, showing that the heuristic can be arbitrarily bad.
The paper proves that spectral graph bisection can produce bisections far from optimal, with a lower bound on the maximum error proportional to the square of the graph order.
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.