The Cluster Description Problem -Complexity Results, Formulations and Approximations
Consider the situation where you are given an existing k-way clustering π. A challenge for explainable AI is to find a compact and distinct explanation of each cluster which in this paper is assumed to use instance-level descriptors/tags from a common dictionary. Since the descriptors/tags were not given to the clustering method, this is not a semi-supervised learning situation. We show that the feasibility problem of testing whether any distinct description (not necessarily the most compact) exists is generally intractable for just two clusters. This means that unless P = NP, there cannot exist an efficient algorithm for the cluster description problem. Hence, we explore ILP formulations for smaller problems and a relaxed but restricted setting that leads to a polynomial time algorithm for larger problems. We explore several extensions to the basic setting such as the ability to ignore some instances and composition constraints on the descriptions of the clusters. We show our formulation's usefulness on Twitter data where the communities were found using social connectivity (i.e. follower relation) but the explanation of the communities is based on behavioral properties of the nodes (i.e. hashtag usage) not available to the clustering method.
The main contributions of the paper are: - Formulating a cluster description problem as a combinatorial optimisation problem to find descriptions for clusters that are descriptive and non-overlapping - Showing NP-completeness of the problem, even if there are only two clusters - Providing  ILP encodings modelling (also extended) variants of the problem  - Providing a tractable subclass of the problem, and together with a polynomial time  algorithm for this subclass  Pros: - A novel problem that is relevant by providing explanations for previously computed clusterings - Well-written paper with a clear focus and clear contributions  Cons:  - In lines 102–103, it is stated that some version of DTDF can be reduced to SAT. Should not this be 2-SAT? Since DTDF is shown to be NP-complete, all versions of DTDF can be reduced to SAT, right? The NP-completeness should hold in general (if not, it should not be possible to devise and ILP encoding for the problem).  - The experimental section is missing some detail (see minor comments below)  Quality: The paper is technically sound and the proofs for complexity parts are provided in the supplementary material. While I did not check all the details in the supplementary, the constructions for reductions seem sound. The  cluster description problem is solved in general using a ILP formulation and also for a tractable subclass. The experimental evaluation supports the theoretical results.  Clarity: The paper is well written and I found it a pleasure to read. Being a reader with a strong background in combinatorial methods I found the level of details sufficient and discussion very concise, and I think that non-experts on combinatorial optimisation should be able to follow the paper.   Originality: The problem definition is novel to my knowledge. The work is placed well in context with other (not too similar) works.   Significance: The results and the new problem formulation have potential for significance. It is relevant for us to find new methods to understand and explain the solutions provided by machine learning algorithms.   Minor:  -line 61: descriptive -> description - the Twitter example with hashtags related to Trump-Clinton election could use some explanation about the meanings of hashtags etc. While currently these should be clear to many if not all, in couple of years it might not be as clear why #MakeAmericaGreatAgain should not go together with #ImWithHer. - It was not really clear to me, whether the IPL encoding or Algorithm 1 was used in the experimental section.  - Regarding Figure 3: how many tags were there in the left table? How many nodes were there in the right table? What is the meaning on *? Is the number of nodes forgotten correct for 25 tags and k=60?  AFTER AUTHOR RESPONSE: The response answered questions raised in the review in a satisfactory manner.