# Scalable Laplacian K-modes

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Oct 2018.

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

- [In Search for a Generalizable Method for Source Free Domain Adaptation](https://mlsanity.com/paper/2302.06658/) (2023)
- [Transductive Few-Shot Learning: Clustering is All You Need?](https://mlsanity.com/paper/2106.09516/) (2021)
- [Attention-based Dynamic Subspace Learners for Medical Image Analysis](https://mlsanity.com/paper/2206.09068/) (2022)
- [Simplex Clustering via sBeta with Applications to Online Adjustment of Black-Box Predictions](https://mlsanity.com/paper/2208.00287/) (2022)

## Abstract (arXiv)

We advocate Laplacian K-modes for joint clustering and density mode finding, and propose a concave-convex relaxation of the problem, which yields a parallel algorithm that scales up to large datasets and high dimensions. We optimize a tight bound (auxiliary function) of our relaxation, which, at each iteration, amounts to computing an independent update for each cluster-assignment variable, with guaranteed convergence. Therefore, our bound optimizer can be trivially distributed for large-scale data sets. Furthermore, we show that the density modes can be obtained as byproducts of the assignment variables via simple maximum-value operations whose additional computational cost is linear in the number of data points. Our formulation does not need storing a full affinity matrix and computing its eigenvalue decomposition, neither does it perform expensive projection steps and Lagrangian-dual inner iterates for the simplex constraints of each point. Furthermore, unlike mean-shift, our density-mode estimation does not require inner-loop gradient-ascent iterates. It has a complexity independent of feature-space dimension, yields modes that are valid data points in the input set and is applicable to discrete domains as well as arbitrary kernels. We report comprehensive experiments over various data sets, which show that our algorithm yields very competitive performances in term of optimization quality (i.e., the value of the discrete-variable objective at convergence) and clustering accuracy.