First-principles multiway spectral partitioning of graphs

Abstract

We consider the minimum-cut partitioning of a graph into more than two parts using spectral methods. While there exist well-established spectral algorithms for this problem that give good results, they have traditionally not been well motivated. Rather than being derived from first principles by minimizing graph cuts, they are typically presented without direct derivation and then proved after the fact to work. In this paper, we take a contrasting approach in which we start with a matrix formulation of the minimum cut problem and then show, via a relaxed optimization, how it can be mapped onto a spectral embedding defined by the leading eigenvectors of the graph Laplacian. The end result is an algorithm that is similar in spirit to, but different in detail from, previous spectral partitioning approaches. In tests of the algorithm we find that it outperforms previous approaches on certain particularly difficult partitioning problems.

12 pages, 9 figures

References in corpus (1)

• Multiway Spectral Clustering: A Margin-Based Perspective

Cited by in corpus (7)

• Spectral methods for network community detection and graph partitioning
• Generalized Network Dismantling
• Underestimated cost of targeted attacks on complex networks
• Community detection in networks via nonlinear modularity eigenvectors
• Exact and rapid linear clustering of networks with dynamic programming
• Extending the Davis-Kahan theorem for comparing eigenvectors of two symmetric matrices I: Theory
• Analyzing Large and Sparse Tensor Data using Spectral Low-Rank Approximation