# Block-Diagonal Guided DBSCAN Clustering

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 88 references that are in the map.
- First posted on arXiv 31 Mar 2024.

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

- [Unsupervised Deep Embedding for Clustering Analysis](https://mlsanity.com/paper/1511.06335/) (2015)
- [Fairness in Graph Mining: A Survey](https://mlsanity.com/paper/2204.09888/) (2022)
- [Deep Spectral Clustering using Dual Autoencoder Network](https://mlsanity.com/paper/1904.13113/) (2019)
- [Hard Sample Aware Network for Contrastive Deep Graph Clustering](https://mlsanity.com/paper/2212.08665/) (2022)
- [Simple Contrastive Graph Clustering](https://mlsanity.com/paper/2205.07865/) (2022)
- [Subspace Clustering by Block Diagonal Representation](https://mlsanity.com/paper/1805.09243/) (2018)
- [Rethinking Graph Auto-Encoder Models for Attributed Graph Clustering](https://mlsanity.com/paper/2107.08562/) (2021)
- [Density Level Set Estimation on Manifolds with DBSCAN](https://mlsanity.com/paper/1703.03503/) (2017)
- [Faster DBSCAN via subsampled similarity queries](https://mlsanity.com/paper/2006.06743/) (2020)
- [Consistency and Diversity induced Human Motion Segmentation](https://mlsanity.com/paper/2202.04861/) (2022)
- [How to Use K-means for Big Data Clustering?](https://mlsanity.com/paper/2204.07485/) (2022)
- [Subspace clustering without knowing the number of clusters: A parameter free approach](https://mlsanity.com/paper/1909.04406/) (2019)
- [Convex Subspace Clustering by Adaptive Block Diagonal Representation](https://mlsanity.com/paper/2009.09386/) (2020)
- [Fast and Robust Sparsity-Aware Block Diagonal Representation](https://mlsanity.com/paper/2312.01137/) (2023)

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

- [Blind Construction of Angular Power Maps in Massive MIMO Networks](https://mlsanity.com/paper/2510.07071/) (2025)
- [Temporal Visual Semantics-Induced Human Motion Understanding with Large Language Models](https://mlsanity.com/paper/2512.22249/) (2025)

## Abstract (arXiv)

Cluster analysis plays a crucial role in database mining, and one of the most widely used algorithms in this field is DBSCAN. However, DBSCAN has several limitations, such as difficulty in handling high-dimensional large-scale data, sensitivity to input parameters, and lack of robustness in producing clustering results. This paper introduces an improved version of DBSCAN that leverages the block-diagonal property of the similarity graph to guide the clustering procedure of DBSCAN. The key idea is to construct a graph that measures the similarity between high-dimensional large-scale data points and has the potential to be transformed into a block-diagonal form through an unknown permutation, followed by a cluster-ordering procedure to generate the desired permutation. The clustering structure can be easily determined by identifying the diagonal blocks in the permuted graph. We propose a gradient descent-based method to solve the proposed problem. Additionally, we develop a DBSCAN-based points traversal algorithm that identifies clusters with high densities in the graph and generates an augmented ordering of clusters. The block-diagonal structure of the graph is then achieved through permutation based on the traversal order, providing a flexible foundation for both automatic and interactive cluster analysis. We introduce a split-and-refine algorithm to automatically search for all diagonal blocks in the permuted graph with theoretically optimal guarantees under specific cases. We extensively evaluate our proposed approach on twelve challenging real-world benchmark clustering datasets and demonstrate its superior performance compared to the state-of-the-art clustering method on every dataset.