Kernel k-Groups via Hartigan's Method
  Energy statistics was proposed by Sz\' ekely in the 80's inspired by Newton's
gravitational potential in classical mechanics and it provides a model-free
hypothesis test for equality of distributions. In its original form, energy
statistics was formulated in Euclidean spaces. More recently, it was
generalized to metric spaces of negative type. In this paper, we consider a
formulation for the clustering problem using a weighted version of energy
statistics in spaces of negative type. We show that this approach leads to a
quadratically constrained quadratic program in the associated kernel space,
establishing connections with graph partitioning problems and kernel methods in
machine learning. To find local solutions of such an optimization problem, we
propose kernel k-groups, which is an extension of Hartigan's method to kernel
spaces. Kernel k-groups is cheaper than spectral clustering and has the same
computational cost as kernel k-means (which is based on Lloyd's heuristic) but
our numerical results show an improved performance, especially in higher
dimensions. Moreover, we verify the efficiency of kernel k-groups in community
detection in sparse stochastic block models which has fascinating applications
in several areas of science.
