Moses Charikar: The Hidden Objective of Spectral Clustering?

Abstract 
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. Optimizing this new objective is equivalent to clustering the effective resistance embedding of the graph. Our approximation algorithm for the new objective is closely related to spectral clustering: it optimizes the k-means objective on a certain smoothed version of the resistive embedding. 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 a good partition exists.

Joint work with Pranjal Awasthi, Ravishankar Krishnaswamy, and Ali Kemal Sinop.