# A parameter-free graph reduction for spectral clustering and SpectralNet

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 36 references that are in the map.
- First posted on arXiv 25 Feb 2023.

## Builds on (most cited first, 4 of 4)

- [SpectralNet: Spectral Clustering using Deep Neural Networks](https://mlsanity.com/paper/1801.01587/) (2018)
- [Out-of-sample extension of graph adjacency spectral embedding](https://mlsanity.com/paper/1802.06307/) (2018)
- [Refining a k-nearest neighbor graph for a computationally efficient spectral clustering](https://mlsanity.com/paper/2302.11296/) (2023)
- [Kernel Two-Dimensional Ridge Regression for Subspace Clustering](https://mlsanity.com/paper/2011.01477/) (2020)

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

- [Integrating Graph Neural Networks with Scattering Transform for Anomaly Detection](https://mlsanity.com/paper/2404.10800/) (2024)

## Abstract (arXiv)

Graph-based clustering methods like spectral clustering and SpectralNet are very efficient in detecting clusters of non-convex shapes. Unlike the popular k-means, graph-based clustering methods do not assume that each cluster has a single mean. However, these methods need a graph where vertices in the same cluster are connected by edges of large weights. To achieve this goal, many studies have proposed graph reduction methods with parameters. Unfortunately, these parameters have to be tuned for every dataset. We introduce a graph reduction method that does not require any parameters. First, the distances from every point p to its neighbors are filtered using an adaptive threshold to only keep neighbors with similar surrounding density. Second, the similarities with close neighbors are computed and only high similarities are kept. The edges that survive these two filtering steps form the constructed graph that was passed to spectral clustering and SpectralNet. The experiments showed that our method provides a stable alternative, where other methods performance fluctuated according to the setting of their parameters.