Naming the Most Anomalous Cluster in Hilbert Space for Structures with Attribute Information

Abstract

We consider datasets consisting of arbitrarily structured entities (e.g., molecules, sequences, graphs, etc) whose similarity can be assessed with a reproducing ker- nel (or a family thereof). These entities are assumed to additionally have a set of named attributes (e.g.: number_of_atoms, stock_price, etc). These attributes can be used to classify the structured entities in discrete sets (e.g., ‘number_of_atoms < 3’, ‘stock_price ≤ 100’, etc) and can effectively serve as Boolean predicates. Our goal is to use this side-information to provide explain- able kernel-based clustering. To this end, we propose a method which is able to find among all possible entity subsets that can be described as a conjunction of the available predicates either a) the optimal cluster within the Reproducing Kernel Hilbert Space, or b) the most anomalous subset within the same space. Our method works employs combinatorial optimisation via an adaptation of the Maximum-Mean-Discrepancy measure that captures the above intuition. Finally, we propose a criterion to select the optimal one out of a family of kernels in a way that preserves the available side-information. We provide several real world datasets that demonstrate the usefulness of our proposed method.