Abstract

 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.