Moses Charikar: Spectral Embedding of k-Cliques, Graph Partitioning and k-Means

Friday, February 13, 2015 - 12:45pm
Pizza at 12:30pm
MSR New England (Barton room on the 1st floor of One Memorial Drive building)
Moses Charikar: Spectral Embedding of k-Cliques, Graph Partitioning and k-Means

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 (where expansion is not measured w.r.t. the induced graph). Optimizing this new objective is equivalent to clustering the effective resistance embedding of the original 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 distance embedding. We also show that spectral clustering applied directly to the original graph gives guarantees for our new objective function.

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 with sufficiently large gap in internal and external conductance.

In the first half of this talk, I will introduce our new graph partitioning objective and describe our results without proof. I will also discuss spectral clustering, various theoretical explanations for its success and how our results fit into this body of work. I'll briefly
discuss results from a preliminary implementation of our new algorithm. I will also discuss the application of finding a good partition in a well clustered graph. In the second half of the talk, I will explain how the new graph partitioning objective arose from a study of the k-means objective, and I will show as many proofs as time allows.

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