# Kernel k-Groups via Hartigan's Method

arXiv: https://arxiv.org/abs/1710.09859 · HTML: https://mlsanity.com/paper/1710.09859/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Oct 2017.

## Built on by (most cited first, 9 of 9)

- [Kernel KMeans clustering splits for end-to-end unsupervised decision trees](https://mlsanity.com/paper/2402.12232/) (2024)
- [Kernel Biclustering algorithm in Hilbert Spaces](https://mlsanity.com/paper/2208.03675/) (2022)
- [Hypothesis testing for matched pairs with missing data by maximum mean discrepancy: An application to continuous glucose monitoring](https://mlsanity.com/paper/2206.01590/) (2022)
- [Sparse and geometry-aware generalisation of the mutual information for joint discriminative clustering and feature selection](https://mlsanity.com/paper/2302.03391/) (2023)
- [Generalised Mutual Information: a Framework for Discriminative Clustering](https://mlsanity.com/paper/2309.02858/) (2023)
- [Clustering-Based Validation Splits for Model Selection under Domain Shift](https://mlsanity.com/paper/2405.19461/) (2024)
- [A Tutorial on Discriminative Clustering and Mutual Information](https://mlsanity.com/paper/2505.04484/) (2025)
- [Distributional Random Forests for Complex Survey Designs](https://mlsanity.com/paper/2512.08179/) (2025)
- [Gaussian mixture models in Hilbert spaces via kernel methods](https://mlsanity.com/paper/2605.05996/) (2026)

## Abstract (arXiv)

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.