Robustness Guarantees for Density Clustering

Heinrich Jiang, Jennifer Jang, Ofir NachumAISTATS 2019 · OpenReview

Abstract

Density-based clustering algorithms like DBSCAN are widely used for their ability to identify clusters of arbitrary shapes. However, these methods are notoriously sensitive to noise and adversarial perturbations, where minor data modifications can lead to significant changes in cluster assignments. This paper introduces Robust DBSCAN, a modification that decouples density estimation from connectivity. By employing two distinct distance scales, the algorithm provides the first formal theoretical guarantees for robustness and consistency in density clustering, even under adversarial corruption.

Introduction

Density-based clustering identifies groups by locating regions of high point density. While flexible, these methods lack inherent robustness. An adversary can manipulate results through two primary strategies: augmentation, where points are added to "bridge" distinct clusters, and deletion, where points are removed to fragment a single cluster. This sensitivity poses risks in security-sensitive applications and leads to instability during data curation. Prior to this work, a rigorous mathematical framework for guaranteeing resistance to such corruptions in density clustering was largely absent.

Methods: Robust DBSCAN

The authors propose Robust DBSCAN, a modification of the classic algorithm that introduces a "safety buffer" between density detection and cluster connectivity.

  • Standard DBSCAN: Uses a single distance parameter $\epsilon$ to identify "core points" (points with at least $k$ neighbors within distance $\epsilon$) and connects them if they are within distance $\epsilon$ of each other.
  • Robust DBSCAN: Decouples these steps. It identifies core points using the original $\epsilon$, but connects them into clusters using a larger distance parameter $\tilde{\epsilon} > \epsilon$.

This decoupling makes the algorithm significantly harder to subvert. The larger connectivity radius ($\tilde{\epsilon}$) requires an adversary to delete many more points to break a cluster. Conversely, the strict core point requirement (using the smaller $\epsilon$) prevents the creation of "fake" clusters in low-density noise regions. The authors prove that under specific regularity assumptions—namely, that the underlying density is smooth ($\alpha$-Hölder continuous) and cluster boundaries are sufficiently "sharp" (curvature $\beta$)—this method is guaranteed to maintain a stable cluster count.

Theoretical Insights

The robustness of the proposed method is rooted in several key theoretical observations:

  • Pruning for Adversarial Defense: While using different radii for density and connectivity (pruning) has been used to mitigate random noise, this paper provides the first proof of its efficacy against adversarial corruption.
  • Density Salience: Robustness is tied to the "curvature" of the density function. Sharp density drops at cluster edges make it harder for adversaries to trick the algorithm.
  • Safety Margin: The gap between $\epsilon$ and $\tilde{\epsilon}$ acts as a buffer. The paper provides a formula for the required size of this buffer based on the number of adversarial points ($\ell$) and the total sample size ($n$).
  • One-to-One Mapping: The authors prove that under contamination, there is a one-to-one correspondence between original and estimated clusters, ensuring that clusters do not merge or drift arbitrarily.

Experimental Evaluation

The algorithm was evaluated across synthetic benchmarks, real-world datasets from the UCI repository, and image segmentation tasks.

Comparison of DBSCAN and Robust DBSCAN on adversarial datasets. Standard DBSCAN frequently over-segments or fails to maintain cluster integrity when faced with adversarial perturbations, while Robust DBSCAN remains stable.

Key Results

  • Adversarial Resistance: In synthetic tests (Circles, Moons), standard DBSCAN's cluster count often exploded due to "fake" clusters created by adversarial points. Robust DBSCAN maintained a stable and correct cluster count.
  • Consistency Rates: The authors established a convergence rate for the Hausdorff distance between estimated and true clusters. Under $\epsilon$-fraction contamination, the error scales as $O(E^{\alpha/(\beta\alpha + \beta D)})$, where $D$ is the dimensionality.
  • UCI Benchmarks: On 9 real-world datasets (e.g., Iris, Wine, Banknote), Robust DBSCAN consistently outperformed the standard version when subjected to "minimum vertex cut" attacks designed to break clusters efficiently.
  • Image Robustness: In pixel-level segmentation of a corrupted image, Robust DBSCAN successfully ignored artificial white lines that caused standard DBSCAN to over-segment the subject into numerous small fragments.

Discussion and Conclusion

Despite its theoretical strengths, Robust DBSCAN faces practical challenges. Choosing the optimal $\epsilon$ and $\tilde{\epsilon}$ requires knowledge of density smoothness ($\alpha$) and curvature ($\beta$), which are typically unknown. Additionally, the reliance on $k$-Nearest Neighbor density estimators can lead to high computational costs in very high-dimensional spaces. Future research may focus on automated parameter estimation to make the "Robust" settings more accessible for general datasets. In conclusion, Robust DBSCAN provides a principled approach to density clustering that balances flexibility with rigorous robustness guarantees.

Summary updated

Abstract

Despite the practical relevance of density-based clustering algorithms, there is little understanding in its statistical robustness properties under possibly adversarial contamination of the input ...
BibTeX
@inproceedings{jiang2019robustness,
  author = {Heinrich Jiang and Jennifer Jang and Ofir Nachum},
  title = {{Robustness Guarantees for Density Clustering}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=yjEPcbr5qFk},
}
Figure