Approximation Guarantees for Kernel Clustering via b-Matching
Tony Jebara, Columbia University

Kernel clustering is an important problem in applied machine learning and can be reformulated as graph partitioning by associating nodes with datapoints and edge weights with kernel evaluations. Partitioning via e.g. the sparsest cut criterion, is NP-hard but has a traditionally been approximated using spectral methods which need time cubic in the number of nodes. Though spectral methods only achieve O(\sqrt{n}) approximation guarantees, they remain popular in machine learning.  Recently, however, improved methods have emerged including the O(\sqrt{\log(n)}) approximation for regular graphs by Arora, Rao and Vazirani which uses semidefinite programming to recover an \ell_2^2 embedding. We extend this algorithm to the general weighted graphs in clustering problems by finding the closest regular graph to the input graph using b-matching.  This permits the O(\sqrt{\log(n)}) guarantee to apply more generally.  Furthermore, if the appropriate (Laplace) kernel is used, semidefinite programming can be avoided altogether since the \ell_2^2 property is automatic. Only the matching step is necessary which, when implemented via belief propagation, scales to large data sets and can sometimes converge in only quadratic time. This permits efficient kernel clustering while providing improved approximation guarantees.