Pith. sign in

REVIEW 3 major objections 6 minor 31 references

Disjunctive and Conjunctive Normal Form Explanations of Clusters Using Auxiliary Information

T0 review · 3 major / 6 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read CNF cluster explanations add detail when one-line tags fail

desk verdict A diligent but modest application of known hitting-set descriptors whose central claim about two-clause CNF adding insight is undermined by silent item-dropping during construction and post hoc filtering. read the letter →

arxiv 2504.20846 v1 pith:3BAHRTPX submitted 2025-04-29 cs.AI

Robert F. Downey , S. S. Ravi This is my paper · ORCID
classification cs.AI
keywords clusterdescriptorshittingsetconjunctivenormalformexplanationsdisjunctiveauxiliarytagsintegerlinearprogrammingexplainableclusteringk-means
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that post-hoc explanations of clusters can be made more informative by replacing a single disjunctive tag set with a two-clause conjunctive normal form (CNF) description of the form “$D_1$ and $D_2$”. It builds these explanations from auxiliary tags that were not used during clustering, and computes minimal descriptors through integer linear programming and a greedy hitting-set heuristic. Across four datasets, the CNF form often supplies additional tags when the disjunctive form reduces to one uninformative tag. If the claim holds, CNF-style descriptors give practitioners a cheap way to extract richer, still human-readable reasons for why a clustering algorithm grouped items.

What carries the argument

The central object is the hitting set: a subset of tags that intersects every data item's tag set, so a minimal disjunctive descriptor is exactly a minimum hitting set. The CNF construction runs the hitting-set solver twice—first find $D_1$, remove $D_1$'s tags from every item's tag set, then find $D_2$ on the reduced sets—and outputs “$D_1$ and $D_2$” as the descriptor. The two solver methods are an integer linear program that minimizes the number of chosen tags subject to a covering constraint, and a greedy heuristic that repeatedly picks the tag appearing in the largest number of unhit sets.

What would settle it

Run the same four datasets through the descriptor pipeline with all filters disabled; if the CNF clauses then reduce to uninformative complementary pairs such as “below median” and “above median” while the filtered version produces distinct narrative tags, it would show that the insight comes from the filter rather than from the CNF construction.

Watch

Extended reading notes

Core claim

The paper's central claim is that a two-clause conjunctive normal form descriptor—a pair of disjoint disjunctive tag sets, “$D_1$ and $D_2$”, such that every item in the cluster is covered by at least one tag from each clause—can provide more informative cluster explanations than a single disjunctive set. The proposed construction obtains $D_1$ as a minimal hitting set over the cluster's tag sets, removes $D_1$ from each item's tags, and then obtains $D_2$ as a minimal hitting set over the reduced sets; the paper states that this CNF descriptor form has not been considered in the literature. Empirically, the CNF form adds information mainly when the disjunctive form is degenerate—for example, when one tag covers the whole cluster—as illustrated by the Movies dataset, where the second clause supplies genre and release-era tags. The paper also reports scalability results indicating that the CNF algorithm runs roughly twice as long as the disjunctive solvers, consistent with solving two hitting-set problems.

Load-bearing premise

The load-bearing premise is that the filters used to discard complementary or shared tags do not remove real signal; if those tags carry information about the clusters, the reported descriptors and insights are artifacts of filter choices rather than properties of the clusters.

Editorial extensions

If this is right

  • If CNF descriptors are adopted, cluster explanations can carry two connected notions (for example, “high budget AND recent release”) instead of one, without requiring any new data beyond the existing tags.
  • The two-clause construction roughly doubles runtime relative to the disjunctive approach, but remains tractable at the tested scale, and the paper deliberately limits CNF to two clauses because more clauses would cost more and become harder for humans to read.
  • The non-complementarity and shared-tag filters make descriptors more distinctive across clusters, at the cost of excluding frequent tags that might themselves be meaningful.
  • Because descriptors are built from tags not used in clustering, the method explains clusters in terms that a domain expert can audit, rather than in the original feature coordinates of the clustering algorithm.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the filters are removed, many of the reported insights would likely collapse to trivial tags such as “female/male” or “below/above median,” which suggests that the practical value of CNF descriptors depends heavily on choosing a good filter policy rather than on the CNF form alone.
  • The same two-stage hitting-set construction could be extended to three or more clauses, and a natural test is whether additional clauses continue to add genuinely new information or simply rephrase the first clause.
  • A head-to-head comparison with other post-hoc explanation styles, such as exemplar-based descriptions or rule lists, would clarify whether the added tags CNF provides are uniquely useful to human interpreters.
  • Since many tags in the experiments are defined by median splits, complementary tag pairs are guaranteed; the proposed truncation filter is one possible policy, but other policies such as significance weighting could change which descriptors are produced.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper studies post-hoc explanations of clusters using auxiliary tags. It formalizes cluster descriptors in disjunctive form and in a two-clause conjunctive normal form (CNF), and observes that finding minimum descriptors is exactly the minimum hitting set problem. The authors implement an ILP-based exact solver and a greedy heuristic for the disjunctive case, and a two-step procedure for CNF: compute a first hitting set D1, subtract its tags from every item's tag set, then compute a second hitting set D2 on the residual sets. The methods are applied to four datasets (College Majors, Movies, Divorce Predictors, Census), with qualitative discussions of the resulting descriptors and a scalability study on synthetic data. The paper claims that CNF descriptors have not been considered before in this literature and that the CNF form can supply additional tags when disjunctive descriptors are uninformative (Section 1.1, Table 9).

Significance. The computational core of the paper is sound: the reduction to hitting set is standard, the ILP formulation is correct, and the greedy heuristic is a reasonable baseline. The two-step CNF construction is a natural and simple extension, and the synthetic scalability experiments give useful ballpark runtime indications. The paper is also transparent about its limitations (Section 6), which is commendable. However, the empirical claims rest on anecdotal inspection of descriptors that are produced by post hoc filters, and the CNF construction drops items from clusters without any reporting of coverage. If the authors add quantitative coverage and sensitivity analyses, the central claim that CNF adds insight could become credible. As it stands, the strength of the paper is in its clean formulation and heuristics rather than in a validated demonstration of explanatory value.

major comments (3)
  1. [3.6, Definition 2.2] Section 3.6 and Definition 2.2: The CNF descriptors reported in Tables 5, 9, 12, and 14 are only guaranteed to be valid for a reduced cluster C', not for the original cluster C. Definition 2.2 requires both D1 and D2 to be valid disjunctive descriptors for C, but the algorithm in Section 3.5 removes, in Step 3, every item whose tag set becomes empty after subtracting D1, and Section 3.6 additionally removes all items with single-tag tag sets before the procedure begins. The paper never reports, for any cluster, how many items were removed or what percentage of the original cluster the CNF descriptor covers. This matters because the paper's own stated goal (Section 1.2) is to explain all data items in a cluster, and the headline claim that CNF 'can aid in providing additional tags' (Section 1.1, Table 9) is only meaningful if the descriptor applies to the cluster as produced by k-means, not to a curated subset. Please report the removal counts and coverage percentages for every cluster, and either restrict the CNF claims to the covered subset or modify the construction to avoid dropping items.
  2. [5.2, 5.3, Tables 6 and 10] Sections 5.2 and 5.3, Tables 6 and 10: The filters that generate the 'insightful' descriptors are chosen post hoc, with the non-complementarity rule of Section 5.2 and the shared-percentage thresholds of 50% and 56% in Table 10 set after inspecting the unfiltered outputs. No justification is given for these specific thresholds, and no sensitivity analysis is presented. Because the central empirical message—that CNF supplies additional tags when the disjunctive form is uninformative—is illustrated precisely with these filtered outputs, the reader cannot tell whether the reported insights are properties of the clusters or artifacts of the filtering choices. Please justify the thresholds a priori or report how the descriptors vary across a range of threshold values.
  3. [5 and Appendix A] Section 5 and Appendix A: The evaluation of explanation quality is entirely anecdotal. There is no quantitative metric of explanation quality (e.g., coverage of each clause, tag purity, or comparison against a random tag baseline), no report of variance across k-means initializations, and no error bars for the tag percentages in the appendix tables. Under these conditions, the claimed practical insights are not reproducible in a statistical sense. Please add summary statistics such as coverage rates and variability across clustering runs, and at least one quantitative comparison (e.g., descriptor size and coverage relative to random baselines) to support the qualitative interpretations.
minor comments (6)
  1. [5.4, Table 12] Section 5.4, Table 12: The statement 'For both clusters, the CNF form of the explanation provides no additional information beyond the tags in the disjunctive sets' is contradicted by the table, because for Cluster 2 the CNF second clause contains t18 and t40, which are not in the disjunctive heuristic set [t20, t38]. Please correct this sentence.
  2. [4.3, Table 1] Section 4.3 and Table 1: The Movies dataset is described as containing 636 films in Section 4.3 but 638 in Table 1; since the cluster sizes in Section 5.3 sum to 638, the 636 should be corrected.
  3. [Table 25] Table 25: The column header 't15-t19' appears twice; the last column should presumably be 't16-t19'. Please correct.
  4. [3.7, Figures 2 and 3] Section 3.7, Figures 2 and 3: The sentence 'the disjunctive exact algorithm performs slower on smaller datasets, highlighting an even greater advantage of heuristic solvers for these cases' is unclear; if the exact algorithm is slower on small datasets, one would expect the heuristic advantage to be larger, not smaller, on large datasets. Please rephrase and reconcile with the figures.
  5. [1.1, contribution 1] Section 1.1, contribution 1: The claim that 'the CNF form of descriptors has not been considered in the literature' is stated as a novelty assertion without a systematic literature search; the related work section (Section 1.2) does not discuss conjunctive description formalisms from conceptual clustering or concept learning, so the claim should be either substantiated or softened.
  6. [General reproducibility] The paper does not mention whether any code or tag definitions will be released; for reproducibility of the qualitative experiments, the scripts and exact tag definitions used for the four datasets should be made available.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper's CNF construction is self-contained, its heuristics and filters are transparent, and its empirical insights are not forced predictions from fitted parameters.

full rationale

The paper's derivation chain is straightforward: a cluster's tag sets are fed to standard hitting-set solvers (a greedy heuristic and an ILP), and the CNF descriptor is produced by computing a first hitting set D1, removing its tags from every tag set, and computing a second hitting set D2 on the residual tag sets (Section 3.5). Definition 2.2 and Section 3.5 are explicit about this construction, and Section 3.6 openly states the coverage caveat: items whose tag sets become empty after removing D1 are removed from C to obtain a smaller cluster C'. That caveat is a correctness or coverage limitation, not a circular step, and Section 6 repeats the limitation. None of the reported descriptors is a fitted parameter renamed as a prediction; the non-complementarity filter (Section 5.2) and the shared-percentage filter (Section 5.3) are transparent preprocessing choices that restrict the tag universe before solving. The paper does cite prior work involving co-author S. S. Ravi (Davidson et al. [6] for the problem definition, and Sambaturu et al. [25] for near-optimal descriptor algorithms), but it explicitly says it does not use the algorithms from [25], and the hitting-set relationship is standard external material (Garey and Johnson [12], Vazirani [27]), implemented with the Gurobi solver. No uniqueness theorem and no load-bearing self-citation forces the paper's choices. The claim that the CNF form can provide additional tags is an empirical observation about the datasets; although the second clause is by construction a disjoint set of tags, the paper's stated insight concerns the informativeness of those tags relative to a non-descript disjunctive descriptor, which is not derived from the definition alone. Thus no circular step is present.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The central results depend on the free parameters listed above; the cluster number and tag thresholds shape every descriptor, and the filter thresholds determine which descriptors are reported. No new theoretical entities are introduced.

free parameters (3)
  • Number of clusters K = 3 (College Majors), 4 (Movies), 2 (Divorce), 2 (Census)
    Chosen by elbow method, affects all cluster contents and therefore descriptors.
  • Tag thresholds = median/mean splits, e.g., Movies budget 60-80M, age 37, education 10 years, capital gain 1086
    Hand-chosen to binarize continuous features; determines which tags exist.
  • Filter thresholds = 50% and 56% shared-percentage thresholds for Movies; non-complementarity rule for all datasets
    Chosen post hoc to produce more distinctive hitting sets; not justified independently.
assumptions (5)
  • standard math Minimum hitting set is NP-hard
    Invoked in Section 3.2 as the reason for using ILP and heuristics.
  • standard math Greedy hitting set heuristic approximates the optimum
    Used in Section 3.3 as an alternative to the exact ILP solver.
  • domain assumption Tags are available for every item and are faithful descriptors of cluster membership
    The entire method in Sections 2-5 assumes tags meaningfully represent each data item.
  • ad hoc to paper The two-step CNF construction produces a valid descriptor only when no tag set becomes empty; items with empty sets are removed from the cluster
    Section 3.6 drops data items when the first clause eliminates all their tags, changing the cluster being explained.
  • ad hoc to paper Filters that discard complementary or shared tags do not bias the explanations
    Sections 5.2 and 5.3 introduce these filters to avoid trivial hitting sets, but the paper does not validate that the excluded tags are uninformative.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Disjunctive and Conjunctive Normal Form Explanations of Clusters Using Auxiliary Information." pith.science (2026). https://pith.science/paper/3BAHRTPX

@misc{pith2026250420846,
  author       = {Pith},
  title        = {Pith review of: Disjunctive and Conjunctive Normal Form Explanations of Clusters Using Auxiliary Information},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3BAHRTPX}},
  note         = {Machine review of arXiv:2504.20846}
}
read the original abstract

We consider generating post-hoc explanations of clusters generated from various datasets using auxiliary information which was not used by clustering algorithms. Following terminology used in previous work, we refer to the auxiliary information as tags. Our focus is on two forms of explanations, namely disjunctive form (where the explanation for a cluster consists of a set of tags) and a two-clause conjunctive normal form (CNF) explanation (where the explanation consists of two sets of tags, combined through the AND operator). We use integer linear programming (ILP) as well as heuristic methods to generate these explanations. We experiment with a variety of datasets and discuss the insights obtained from our explanations. We also present experimental results regarding the scalability of our explanation methods.

Figures

Figures reproduced from arXiv: 2504.20846 by the authors.

Figure 1
Figure 1. A Greedy Heuristic for Finding a Small Hitting Set (i.e., Disjunctive Descriptor) [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 3
Figure 3. Algorithm Execution Times for 100,000 Datapoints using Python 3.10.9 scripts. The experiments involved constructing synthetic datasets and taking the average of 10 time calculations for the designated number of data points of each iteration. The results are shown in Figures 2 and 3. As can be seen from these figures, the disjunctive exact algorithm performs slower on smaller datasets, highlighting an even greater ad… view at source ↗
Figure 5
Figure 5. College Majors Data: Principal Component Analysis. or patterns within each cluster. These tags are used to interpret the reasons behind the clustering, providing insights into the common attributes of the data points in each group. Visualization techniques, such as principal component analysis, are used to display the clustering results and facilitate further analysis. In the following subsections, the above process… view at source ↗
Figures from the paper (3 more)
Figure 7
Figure 7. Figure 7: Movies Data: Principal Component Analysis. Using the elbow method, which evaluates the sum of squared errors for an increasing number of clusters, 4 clusters were determined to be the optimal number (see [PITH_FULL_IMAGE:figures/full_fig_p020_7.png]
Figure 8
Figure 8. Figure 8: Divorce Predictors Data: Elbow Method [PITH_FULL_IMAGE:figures/full_fig_p022_8.png]
Figure 11
Figure 11. Figure 11: Census Data: Principal Component [PITH_FULL_IMAGE:figures/full_fig_p028_11.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 26 canonical work pages

  1. [25]

    Prathyush Sambaturu, Aparna Gupta, Ian Davidson, S. S. Ravi, Anil Vullikanti, and Andrew Warren. Efficient algorithms for generating provably near-optimal cluster descriptors for explainability. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, New York, NY, USA , pages 1636–1643. AAAI Press, 2020

    work page 2020

  2. [1]

    Peeking inside the black-box: a survey on explainable artificial intelligence (xai)

    Amina Adadi and Mohammed Berrada. Peeking inside the black-box: a survey on explainable artificial intelligence (xai). IEEE access, 6:52138–52160, 2018

    2018

  3. [2]

    Towards description of block model on graph

    Zilong Bai, SS Ravi, and Ian Davidson. Towards description of block model on graph. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2020, Ghent, Belgium, September 14–18, 2020, Proceedings, Part III , pages 37–53. Springer, 2021

    work page 2020

  4. [3]

    Barry Becker and Ronny Kohavi. Adult. UCI Machine Learning Repository, 1996. DOI: https://doi.org/10.24432/C5XW20

    doi:10.24432/c5xw20 1996

  5. [4]

    https://github.com/starik222/ BooruDatasetTagManager, 2022

    Booru dataset tag manager. https://github.com/starik222/ BooruDatasetTagManager, 2022. Last accessessed: March 2025

    work page 2022

  6. [5]

    ExKMC: Expanding explainable k-means clustering

    Sanjoy Dasgupta, Nave Frost, Michal Moshkovitz, and Cyrus Rashtchian. ExKMC: Expanding explainable k-means clustering. In ICML 2020, pages 7055–7065, 2020

    work page 2020

  7. [6]

    Davidson, A

    I. Davidson, A. Gourru, and S. S. Ravi. The cluster description problem - complexity results, formulations and approximations. In Proc. NeurIPS, pages 6193–6203, 2018

    work page 2018

  8. [7]

    Behavioral differences: insights, explanations and comparisons of french and us twitter usage during elections

    Ian Davidson, Antoine Gourru, Julien Velcin, and Yue Wu. Behavioral differences: insights, explanations and comparisons of french and us twitter usage during elections. Social Network Analysis and Mining , 10:1–27, 2020

    work page 2020

Show all 31 references
  1. [8]

    Livanos, Antoine Gourru, Peter B

    Ian Davidson, Michael J. Livanos, Antoine Gourru, Peter B. Walker, Julien Velcin, and S. S. Ravi. An exemplars-based approach for explainable clustering: Complexity and efficient approximation algorithms. In Shashi Shekhar, Vagelis Papalexakis, Jing Gao, Zhe Jiang, and Matteo ...

    2024

  2. [9]

    F. K. Dosilovic, M. Brcic, and N. Hupic. Explainable Artificial Intelligence: A Survey. In Proc. 41st MIPRO, pages 210–215, 2018

    2018

  3. [10]

    Divorce predictors data set

    Dheeru Dua and Casey Graff. Divorce predictors data set. https://archive.ics. uci.edu/ml/datasets/Divorce+Predictors+data+set, 2019. Accessed: 2024-05- 22. 25

    2019

  4. [11]

    College Majors, 2017

    FiveThirtyEight. College Majors, 2017. DOI: https://data.world/ fivethirtyeight/college-majors

    2017

  5. [12]

    M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman & Co., San Francisco, 1979

    1979

  6. [13]

    D. Gunning. Explainable Artificial Intelligence (XAI). DARPA Program Up- date Document, 2017. Available from https://www.darpa.mil/attachments/ XAIProgramUpdate.pdf

    2017

  7. [14]

    Gurobi Optimizer Reference Manual, 2023

    Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023

    2023

  8. [15]

    Data Mining: Concepts and Techniques

    Jiawei Han, Micheline Kamber, and Jian Pei. Data Mining: Concepts and Techniques . Morgan Kaufmann Publishers, Boston, MA, 2012

    2012

  9. [16]

    The gottman method

    Gottman Institute. The gottman method. https://www.gottman.com/about/ the-gottman-method/. Accessed: 2024-05-22

    2024

  10. [17]

    Towards practical explainability with cluster descriptors

    Xiaoyuan Liu, Ilya Tyagin, Hayato Ushijima-Mwesigwa, Indradeep Ghosh, and Ilya Safro. Towards practical explainability with cluster descriptors. In K. Sel¸ cuk Candan, Thang N. Dinh, My T. Thai, and Takashi Washio, editors, IEEE International Con- ference on Data Mining Worksh...

    2022

  11. [18]

    Learning from observation: Conceptual clustering

    Ryszard S Michalski and Robert E Stepp. Learning from observation: Conceptual clustering. In Machine learning, pages 331–363. Springer, 1983

    1983

  12. [19]

    T. Miller. Explanation in Artitificial Intelligence: Insights from the Social Sciences. ArXiv Report: 1706.07269v3 [cs.AI], 2018

    2018 arXiv

  13. [20]

    Y. Ming. A survey on visualization for explainable classifiers. Tech Report, Hong Kong University of Science and Technology, 2017

    2017

  14. [21]

    data.world, 2020

    Movies dataset. data.world, 2020. DOI: https://data.world/jamesgaskin/movies

    2020

  15. [22]

    IJCAI-17 Workshop on Explainable AI (XAI)

    Proc. IJCAI-17 Workshop on Explainable AI (XAI). http://www. intelligentrobots.org/files/IJCAI2017/IJCAI-17_XAI_WS_Proceedings.pdf, 2017

    2017

  16. [23]

    IJCAI-ECAI-2018 Workshop on Explainable AI (XAI)

    Proc. IJCAI-ECAI-2018 Workshop on Explainable AI (XAI). https://www.dropbox. com/s/jgzkfws41ulkzxl/proceedings.pdf?dl=0, 2018

    2018

  17. [24]

    Balancing the tradeoff between clustering value and interpretability

    Sandhya Saisubramanian, Sainyam Galhotra, and Shlomo Zilberstein. Balancing the tradeoff between clustering value and interpretability. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society , pages 351–357, 2020. 26

    2020

  18. [26]

    Introduction to Data Mining

    Pang-Ning Tan, Michael Steinbach, Anuj Karpatne, and Vipin Kumar. Introduction to Data Mining . Pearson Co., New York, NY, 2 edition, 2019

    2019

  19. [27]

    Vazirani

    Vijay V. Vazirani. Approximation Algorithms. Springer, New York, NY, 2001

    2001

  20. [28]

    Multilevel exemplar theory

    Michael Walsh, Bernd M¨ obius, Travis Wade, and Hinrich Sch¨ utze. Multilevel exemplar theory. Cognitive Science, 34(4):537–582, 2010

    2010

  21. [29]

    Zaki and Wagner Meira Jr

    Mohammed J. Zaki and Wagner Meira Jr. Data Mining and Machine Learning: Fun- damental Concepts and Algorithms . Cambridge University Press, Cambridge, MA, 2 edition, 2020

    2020

  22. [30]

    Zhang and X

    Y. Zhang and X. Chen. Explainable Recommendation: A Survey and New Perspec- tives. ArXiv Report: 1804.11192v4 [cs.IR], 2018. 87 pages

    2018 arXiv

  23. [31]

    black ethnicity

    Z. Zheng, C. Miao, C. Leung, and C. J. Jih. Building more explainable Artificial Intelligence. In Proc. SIGAI Doctoral Consortium, pages 8044–8055, 2018. 27 Figure 10: Census Data: Elbow Method. Figure 11: Census Data: Principal Component Analysis. 7 Appendix A: Results for th...

    2018

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.