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.
Joint work with Pranjal Awasthi, Ravishankar Krishnaswamy, and Ali Kemal Sinop
Moses Charikar is a professor of Computer Science at Princeton University. He obtained his PhD from Stanford University in 2000, spent a year in the research group at Google and has been at Princeton since 2001. He is broadly interested in the design and analysis of algorithms with an emphasis on approximation algorithms for hard problems, metric embeddings and algorithmic techniques for big data. His work on dimension reduction won the best paper award at FOCS 2003. He was jointly awarded the 2012 Paris Kanellakis Theory and Practice Award for work on locality sensitive hashing, and was recently named a Simons Investigator in theoretical computer science.