# Connecting Spectral Clustering to Maximum Margins and Level Sets

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

## Key facts

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

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

- [Optimization of Inter-group Criteria for Clustering with Minimum Size Constraints](https://mlsanity.com/paper/2401.07091/) (2024)
- [Refining Heuristic-Based Bitcoin Address Clustering with Graph Neural Networks](https://mlsanity.com/paper/2609.01942/) (2026)

## Abstract (arXiv)

We study the connections between spectral clustering and the problems of maximum margin clustering, and estimation of the components of level sets of a density function. Specifically, we obtain bounds on the eigenvectors of graph Laplacian matrices in terms of the between cluster separation, and within cluster connectivity. These bounds ensure that the spectral clustering solution converges to the maximum margin clustering solution as the scaling parameter is reduced towards zero. The sensitivity of maximum margin clustering solutions to outlying points is well known, but can be mitigated by first removing such outliers, and applying maximum margin clustering to the remaining points. If outliers are identified using an estimate of the underlying probability density, then the remaining points may be seen as an estimate of a level set of this density function. We show that such an approach can be used to consistently estimate the components of the level sets of a density function under very mild assumptions.