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

We introduce and study a new notion of graph partitioning, intimately connected to k-means clustering. Informally, our graph partitioning objective asks for the optimal spectral simplification of a graph as a disjoint union of $k$ normalized cliques. It is a variant of graph decomposition into expanders (where expansion is not measured w.r.t. the induced graph). Optimizing this new objective is closely related to clustering the effective resistance embedding of the original graph. We present a factor-$k$ approximation algorithm for this problem.

In order to illustrate the power of our new notion, we show 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 given a guarantee that such a partition exists with sufficiently large gap in internal and external conductance.

Joint work with Pranjal Awasthi, Moses Charikar and Ravishankar Krishnaswamy.