We introduce and study a new notion of graph partitioning, intimately connected to both the k-means clustering problem (for clustering points in Euclidean space), and the spectral clustering algorithm (for partitioning graphs into pieces). Informally, our graph partitioning objective asks for the optimal spectral simplification of a graph as a disjoint union of k normalized cliques, and can be thought of as a real-valued variant of graph decomposition into expanders, which has received much attention recently.
To motivate our objective, we show that it is closely connected to the spectral clustering algorithm, and can be seen as an "implicit objective function" that the spectral clustering algorithm is optimizing. Using this connection, we show that the spectral clustering algorithm applied to a given graph gives good approximation guarantees for our new objective function. Additionally, we also show that our objective function arises naturally as the dual problem to the k-means problem (to cluster points in Euclidean space). We also illustrate the power of our new notion, by showing that approximation algorithms for our new objective can be used in a black box fashion to approximately recover a partition of a graph into k pieces with high internal expansion and low external expansion, provided we are given a guarantee that a good partition exists. This extends (and potentially simplifies) previous work on this topic.
Joint work with Pranjal Awasthi, Moses Charikar, and Ali Kemal Sinop.