Spectral Embedding of k-Cliques, Graph Partitioning and k-Means

We introduce and study a new notion of graph partitioning, intimately connected to spectral clustering and k-means clustering. Formally, given a graph G on n vertices, we ask to find a graph H that is the union of k cliques on n vertices, such that L_G > λ L_H where λ is maximized. Here L_G and L_H are the (normalized) Laplacians of the graphs G and H respectively. Informally, our graph partitioning objective asks for the optimal spectral simplification of a given graph as a disjoint union of k cliques.

We justify this objective function in several ways. First and foremost, we show that a commonly used spectral clustering algorithm implicitly optimizes this objective function, up to a factor of O(k). Using this connection, we immediately get an O(k)-approximation algorithm to our new objective function by simply using the spectral clustering algorithm on G. Next, we demonstrate another application of our objective function: we use it as a means to proving that simple spectral clustering algorithms can solve some well-studied graph partitioning problems (such as partitioning into expanders). Additionally, we also show that (a relaxation of) this optimization problem naturally arises as the dual problem to the question of finding the worst-case integrality gap instance for the classical k-means SDP. Finally, owing to these close connection between some classical clustering techniques (such as k-means and spectral clustering), we argue that a more complete understanding of this optimization problem could lead to new algorithmic insights and techniques for the area of graph partitioning.