# CAST: A Correlation-based Adaptive Spectral Clustering Algorithm on Multi-scale Data

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jun 2020.

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

- [Finding Global Homophily in Graph Neural Networks When Meeting Heterophily](https://mlsanity.com/paper/2205.07308/) (2022)
- [CDC: A Simple Framework for Complex Data Clustering](https://mlsanity.com/paper/2403.03670/) (2024)
- [SIGMA: An Efficient Heterophilous Graph Neural Network with Fast Global Aggregation](https://mlsanity.com/paper/2305.09958/) (2023)
- [Rethinking Spectral Graph Neural Networks with Spatially Adaptive Filtering](https://mlsanity.com/paper/2401.09071/) (2024)
- [Factor Adjusted Spectral Clustering for Mixture Models](https://mlsanity.com/paper/2408.12564/) (2024)
- [Aggregation-aware MLP: An Unsupervised Approach for Graph Message-passing](https://mlsanity.com/paper/2507.20127/) (2025)
- [Attention Beyond Neighborhoods: Reviving Transformer for Graph Clustering](https://mlsanity.com/paper/2509.15024/) (2025)

## Abstract (arXiv)

We study the problem of applying spectral clustering to cluster multi-scale data, which is data whose clusters are of various sizes and densities. Traditional spectral clustering techniques discover clusters by processing a similarity matrix that reflects the proximity of objects. For multi-scale data, distance-based similarity is not effective because objects of a sparse cluster could be far apart while those of a dense cluster have to be sufficiently close. Following [16], we solve the problem of spectral clustering on multi-scale data by integrating the concept of objects' "reachability similarity" with a given distance-based similarity to derive an objects' coefficient matrix. We propose the algorithm CAST that applies trace Lasso to regularize the coefficient matrix. We prove that the resulting coefficient matrix has the "grouping effect" and that it exhibits "sparsity". We show that these two characteristics imply very effective spectral clustering. We evaluate CAST and 10 other clustering methods on a wide range of datasets w.r.t. various measures. Experimental results show that CAST provides excellent performance and is highly robust across test cases of multi-scale data.