First-principles multiway spectral partitioning of graphs

Understand

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.