************************************************************************************** === ORFE Optimization Seminar === DATE: Thursday, November 20, 2014 TIME: 4:30pm ***new time*** LOCATION: Sherrerd Hall room 101 ***new room*** SPEAKER: Moses Charikar, Computer Science Dept., Princeton University TITLE: 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 semidefinite programming based 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. **************************************************************************************