- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper introduces LUCID, a framework that constructs a global explanation tree for a given reference clustering by leveraging density-based connectivity distances, the Minimum Spanning Tree (MST) of a mutual reachability graph, and single-linkage hierarchical clustering. For each node, the method first identifies a density-respecting binary partition; it then selects an explanatory rule—drawn from a set of linear, symbolic, or connectivity-based rules—by balancing error against model complexity, with a fallback option to partition the data into its constituent maximal clusters when necessary. As the first framework designed for the global explanation of density-based clustering, LUCID reportedly outperforms methods such as SpEx, IMM, CART, and TAO across 67 datasets and five different reference clustering configurations. Evaluation is primarily conducted using metrics including AMI, ARI, DISCO, and DBCV, supplemented by ablation studies, statistical significance testing, and an analysis of node types.
Critical strengths
-
The problem is clearly defined; while global interpretability for density-based clustering has lacked systematic research, LUCID integrates density-connected hierarchies, interpretation trees, and a set of rules for three types of nodes into a comprehensive framework.
-
The experimental evaluation is extensive, encompassing 67 datasets, 5 reference clustering methods, and multi-metric assessment. Furthermore, the inclusion of significance testing and parameter ablation studies effectively demonstrates the method's capabilities within the context of density-based clustering.
-
The paper provides conditions for "exact recovery" and discloses implementation details, ensuring strong reproducibility and serving as a valuable reference for future comparative studies.
Critical weaknesses
-
The novelty of the proposed method is limited, as it primarily consists of a combination of existing components, dc-dist, MST, single-linkage hierarchical clustering, and interpretable trees are not new concepts. The theoretical analysis is restricted to "exact recovery," lacking both approximation guarantees and an assessment of the "price of explainability." Furthermore, the absence of guarantees for "fallback" nodes weakens the methodological contribution.
-
The experimental advantages may stem from an inherent bias toward density-based structures; LUCID shares either the dc-dist metric or density priors with DBSCAN, HDBSCAN, and SHADE. Its performance is merely comparable to Spectral clustering and shows only marginal improvements over the ground truth. Moreover, the method performs poorly on real-world high-dimensional datasets such as CIFAR and MNIST, making it difficult to claim general effectiveness.
-
The work suffers from issues regarding interpretability and the fairness of comparisons. The connection rules rely directly on actual data samples and dc-distance thresholds, yet no user studies or readability assessments were conducted. The rule-selection process, which prioritizes minimizing error, may result in the selection of non-intuitive rules. The set of baselines lacks rule-based, prototype-based, or polyhedral methods, and the reference clustering approaches rely on fixed heuristics without hyperparameter tuning. Additionally, the memory and quadratic time complexity limit the method's scalability.
Questions for authors
-
For reference clusterings that do not utilize dc-dist, how can it be demonstrated that the advantages of LUCID do not stem from a shared density prior? Could the evaluation be expanded to include reference methods that are independent of density, as well as baselines based on more robust rule sets?
-
Beyond the guarantee of "exact recovery," is it possible to provide an upper bound on the approximation error, or at least characterize the worst-case scenario for "fallback" nodes?
-
How is the human readability of the connection rule, defined as "the dc-dist to an instance is less than ", evaluated? Are there any user studies or metrics for measuring the complexity of the explanations?
-
Are the runtime and memory usage reported as functions of , , and ? Does the method remain feasible when ?
-
Could the heuristic used to fix the parameters for reference clusterings introduce a bias in favor of LUCID? Would it be possible to ensure a fairer comparison by selecting these parameters through independent tuning or cross-validation?
-
Given that the "price of explainability" is a key metric for assessing the interpretability of clusterings, why was this not analyzed?
5 comments
review
Thank you for your reply.
Could you clarify the relationship between your work and interpretable clustering, as well as its connection to the price of explainability? Since the "price" in interpretable clustering is important, and recent work focuse on how to reduce this price.
Thank you for the question and for giving us a chance to clarify this.
LUCID belongs to the family of tree-based interpretable clustering methods (IMM and its follow-ups), but our setting differs slightly. We focus on density-based clustering, which, in contrast to centroid-based clustering, does not assign points to clusters by solving an optimization problem.
In most k-means/k-median interpretable clustering, the goal is a threshold tree whose clustering has low cost under the same objective. The price of explainability is the worst-case ratio between the tree's cost and the optimal clustering's cost. This requires a clustering objective that is not present in the clustering methods we focus on. LUCID thus explains a given clustering post hoc, and we measure how faithfully the tree reproduces it (AMI/ARI, misclassification cost in Definition 1). Under that cost, the reference itself has cost zero, so a cost ratio is undefined. A bound in the price-of-explainability sense would first require a density-based clustering objective, which we consider an open problem and say so in the paper. What we report instead is the difference in clustering quality (DISCO/DBCV) with respect to the density structure, together with how well the tree aligns with the reference clustering (AMI/ARI). DISCO/DBCV can be used in a way similar to a cost or an objective, however, the difference is that both DISCO and DBCV are measures of clustering quality rather than objective functions that the algorithms optimize for.
In the rebuttal, we present two settings to control the resulting interpretability-fidelity tradeoff, i.e., the harder-to-read connectivity rules (lower interpretability) that allow us to capture more of the actual structure (alignment with structure and reference/fidelity): the feature cap and an error tolerance δ in rule selection.
We will add a paragraph to the related work and the limitations explaining this distinction. We hope that our answer could clarify your question, and we are happy to answer any further questions you may have!
Dear Reviewer,
Thank you very much for your helpful feedback.
W1 (novelty): dc-dist, MST, single linkage, and decision trees are existing, and we do not claim them. Our contributions are the problem setting (global explanation of density-based clusterings), density-aware trees that split at a cut in the density hierarchy and explain it with a rule, connectivity rules with their ultrametric-ball property (Lemma 1, Prop. 1), and the empirical study.
W2+Q1 (bias): LUCID performs best on density-based references because it is designed for them, not because the evaluation is biased. Density-based clusterings (DBSCAN, HDBSCAN, SHADE) are defined by density-connectivity rather than by an objective function, and existing explainable-clustering methods were not designed for this setting. IMM and its follow-ups explain centroid-based objectives (k-means/k-median), relying on convex cells around centers. TAO needs a cost function to optimize, and SpEx uses a graph-conductance criterion with axis-aligned cuts. All can run on arbitrary labels, but none is designed for density-connected, non-convex clusters, so they fall behind here.
On a k-means reference (App. G), LUCID is not significantly better than any competitor (AMI 0.820 vs. CART 0.805, IMM 0.811, SpEx 0.814, TAO 0.931), so we restrict the claims in the abstract and conclusion to density-based references.
On real high-dimensional data, LUCID’s lead shrinks with d, which we attribute to degrading reference quality. On new DENSIRED data (d up to 500, App. I), the pooled lead is positive at every d ≥ 20, so dimension alone does not cause the shrinkage seen on real data. Much of the growth at d ≥ 100 comes from the spectral reference. Without it the lead is about +0.02 at d = 100–500, still not a negative trend.
W3 (interpretability): Rule selection is lexicographic by (error, size), so a less direct rule is chosen only if it fits the target strictly better, favoring fidelity. Connectivity rules are harder to read but more expressive. Users can control the trade-off with the feature cap j_max and an added cap on connectivity nodes (one per tree gives AMI 0.916 vs. 0.933 full). An error tolerance δ (take the simplest rule whose error is within δ of the best) lowers the connectivity share from 17.2% to 5.2% (δ = 0.05), while the mean AMI drops from 0.933 to 0.886, so the default (δ = 0) is the best-aligned setting.
Rule-, prototype-, and polyhedral-based methods return per-cluster descriptions rather than a global tree, so we compare within the tree family.
Q2 + Q6 (bound, price of explainability): We have no bound beyond exact recovery and state this as an open problem. The price of explainability is the worst-case ratio between the cost of the best explanation tree and the cost of the reference clustering under a clustering objective such as k-means. Density-based clusterings optimize no such objective, and under our misclassification cost (Definition 1) the reference itself has cost zero, so the ratio is undefined. We thus report differences in DISCO/DBCV as measures for the change in quality.
At fallback nodes (30.75% of splits), where no density-respecting bipartition exists, there is no guarantee, so we characterize behavior empirically (App. I): 44% (729 of 1,655) are reproduced exactly (nodes: 61% linear, 17% signomial, 0% connectivity).
Q3 (readability): A connectivity rule “dc(x, z) < ε” reads: x is connected to the real example z through objects whose mutual-reachability distance stays below ε, i.e., x lies in the dense region around z. App. E prints examples with the feature values of z. We have not run a user study and list this as a limitation. We added the following complexity measures (LUCID/CART/IMM/SpEx/TAO): depth 3.21/2.74/3.24/2.93/1.98; conditions per path 2.35/2.17/2.36/2.24/1.80; distinct features per tree 2.81/2.48/2.35/2.39/45.8.
Q4 (runtime): App. H adds runtime experiments (DENSIRED, 5% noise, HDBSCAN reference). The original implementation spent 76 of 84 s (n = 20k, d = 10) on the n×n dc-distance matrix. An improved implementation computes one exact mutual-reachability MST and derives each node’s dendrogram from its sorted edges, returning identical labels (60/60 runs). At d = 10, n = 5k drops from 3.3 s to 0.45 s, n = 20k from 83.8 s (14.2 GB) to 3.3 s (0.24 GB), and n = 100k takes 46 s (0.54 GB). On real data, Pendigits takes 4.8 s and Beans 2.2 s. CART, IMM, and SpEx are faster than LUCID, and TAO is slower at d = 10 (n = 20k) but faster at d = 50 (2.1 vs. 11.7 s).
Q5 (parameters): We did not tune the references per dataset, so none is tuned toward LUCID. We varied µ_ref (App. G). LUCID’s lead over the best competitor for µ_ref = 2/5/10: DBSCAN +0.055/+0.115/+0.101; HDBSCAN −0.034/+0.071/+0.071; SHADE +0.146/+0.151/+0.150. Only HDBSCAN at µ_ref = 2 shows no advantage.
We did not use cross-validation since the target is a fixed clustering.