Technical Summary: ExDBSCAN – Explaining DBSCAN with Counterfactual Reasoning

Problem Statement

Clustering is a fundamental unsupervised learning technique, yet it suffers from a significant interpretability gap compared to supervised learning. While counterfactual explanations (CEs) have become a standard for explaining supervised models by identifying minimal input changes that alter predictions, they are not directly applicable to clustering. This gap is particularly acute for DBSCAN (Density-Based Spatial Clustering of Applications with Noise), a popular algorithm capable of finding arbitrary-shaped clusters and identifying noise.

DBSCAN assigns points as core, border, or noise based on density-reachability defined by parameters $\varepsilon$ and $minPts$. However, it offers no insight into why a specific point received its assignment or whether that assignment is robust to small data changes. Existing CE methods face three primary hurdles when applied to DBSCAN:

1. Lack of Differentiability: DBSCAN does not use a differentiable loss function, preventing the use of gradient-based search methods common in supervised CE generation.
2. Absence of Probabilities: Unlike classification models, DBSCAN provides discrete, connectivity-based memberships rather than continuous class probabilities, which many model-agnostic CE methods rely on.
3. Complex Similarity Structure: DBSCAN's density-connectivity means that two points can be close in Euclidean space but effectively distant in terms of cluster membership (requiring a long density-connected path). Standard Euclidean distance metrics used by other CE methods fail to capture this, potentially generating redundant or invalid counterfactuals.

Methodology: ExDBSCAN

The authors propose ExDBSCAN, the first post-hoc explanation method tailored specifically for DBSCAN. It generates actionable counterfactuals for both noise-to-cluster and cluster-to-cluster transitions with theoretical guarantees of validity.

Core Components

1. Graph-Based Similarity Representation:
   Instead of relying on Euclidean distance, ExDBSCAN models the cluster structure as an undirected weighted graph $G(V, E)$.

   • Vertices ($V$): Represent the core points of a cluster.
   • Edges: Connect two vertices if they are directly density-reachable (distance $< \varepsilon$).
   • Weights: The Euclidean distance between connected core points.
   • Distance Metric: The distance between any two points is defined as the weighted shortest path in $G$. This ensures that "proximity" respects the density-connectivity structure of the cluster.

2. Physics-Inspired Optimization:
   To generate a set of $k$ diverse and proximal counterfactuals, ExDBSCAN models the selection of reference core points as a physical energy minimization problem. The system treats candidate core points as charged particles subject to two forces:

   • Repulsion (Diversity): Modeled after Coulomb's law, candidate core points repel each other. The repulsion force is inversely proportional to the weighted shortest-path distance between them. This ensures selected counterfactuals are spread out across the cluster's density structure, avoiding redundancy.
   • Attraction (Proximity): Modeled after Hooke's law (spring forces), candidate core points are attracted to the original instance $p$ to be explained. The force increases linearly with the distance, biasing the selection toward the nearest valid core points.

   The total energy $E_{C'}$ of a set of selected core points $C'$ is defined as:
   $$E_{C'} = \sum_{V_i \in C'} \sum_{V_j \in C': j > i} \frac{1}{D(V_i, V_j)} + \sum_{V_i \in C'} d^2(p, V_i)$$
   Where $D$ is the weighted graph distance and $d$ is the Euclidean distance to the original point.

3. Optimization and Construction:

   • NP-Hardness: Finding the optimal set of core points to minimize this energy is proven to be NP-hard. ExDBSCAN employs a greedy algorithm to approximate the solution. It iteratively selects the core point that minimizes the total system energy given the currently selected set.
   • Counterfactual Generation: Once a set of reference core points is selected, the final counterfactuals are constructed within the $\varepsilon$-neighbourhood of these cores. Specifically, a counterfactual $p'$ is placed at distance $\varepsilon$ from the reference core $q$ in the direction of the original point $p$.
   • Validity Guarantee: By construction, every generated counterfactual lies within $\varepsilon$ of a core point in the target cluster, ensuring it satisfies DBSCAN's density-connectivity criteria and is a valid member of the target cluster.

4. Handling Constraints:
   The method accounts for non-actionable features (e.g., age, gender) by restricting the search space. It filters core points such that their $\varepsilon$-neighbourhoods are reachable without modifying non-actionable attributes, ensuring explanations remain realistic.

Key Contributions

• First DBSCAN-Specific CE Method: ExDBSCAN is the first method designed to generate counterfactual explanations specifically for density-based clustering, covering both noise-to-cluster and cluster-to-cluster transitions.
• Novel Physics-Inspired Model: The authors introduce a model that balances proximity and diversity using electrostatic repulsion and spring-like attraction, explicitly accounting for the density-connectivity structure of DBSCAN via a weighted graph.
• Theoretical Validity: The method provides a theoretical guarantee (Theorem 3.1) that every generated counterfactual is valid under DBSCAN's assignment rules.
• Empirical Superiority: Extensive evaluation on 30 tabular datasets demonstrates that ExDBSCAN outperforms existing baselines (including model-agnostic methods like BayCon, DiCE, and Growing Spheres) in validity, proximity, and diversity.

Experimental Results

The authors evaluated ExDBSCAN on 30 OpenML tabular datasets against seven baselines (including DiCE, BayCon, Growing Spheres, and random variants).

• Validity: ExDBSCAN achieved 100% validity across all queries. In contrast, surrogate-based methods (DiCE-Surrogate, GS-Surrogate) and model-agnostic methods (BayCon) struggled significantly, often achieving validity rates below 50%. This is attributed to the mismatch between their continuous optimization objectives and DBSCAN's discrete, density-based assignment.
• Proximity: Among methods achieving high validity, ExDBSCAN produced counterfactuals significantly closer to the original instances than competitors. This is attributed to the explicit optimization of the spring-like attraction term using the graph-based distance.
• Diversity: ExDBSCAN achieved the highest diversity scores. Its repulsion mechanism, based on the weighted shortest-path distance within the cluster graph, ensured that selected counterfactuals represented distinct alternatives within the cluster's topology, rather than just being close in Euclidean space.
• Runtime: While ExDBSCAN is computationally more intensive than a simple random heuristic, it is generally faster than the heavy optimization required by DiCE and BayCon, particularly when those methods fail to find valid counterfactuals.

Significance and Claims

The paper positions ExDBSCAN as a critical step toward bridging the interpretability gap in unsupervised learning. The authors claim that by leveraging counterfactual reasoning tailored to DBSCAN's specific mechanics, practitioners can gain:

• Actionable Insights: Understanding which features drive a point's assignment to a cluster or its status as noise.
• Robustness Checks: Assessing whether cluster assignments are stable or sensitive to small perturbations.
• Trust and Transparency: Providing "what-if" scenarios that reflect the true density-based structure of the data, rather than artificial boundaries created by surrogate models.

The authors modestly note that while a formal user study is beyond the scope of this work, the method provides concrete, theoretically grounded examples of how cluster assignments can be altered. They suggest future work could extend ExDBSCAN to incremental or streaming scenarios and explore more sophisticated optimization strategies beyond the current greedy approximation.