Clustering with Tangles: Algorithmic Framework and Theoretical Guarantees

Originally, tangles had been invented as an abstract tool in mathematical graph theory to prove the famous graph minor theorem. In this paper we showcase the practical potential of tangles in machine learning applications. Given a collection of weak cuts (bipartitions) of any dataset, tangles provide a mechanism to aggregate these cuts such that they point in the direction of a dense structure. As a result, a cluster is softly characterized by a set of consistent pointers. This highly flexible approach can solve soft clustering problems in a variety of setups, ranging from questionnaires over community detection in graphs to clustering points in metric spaces. The output of our proposed framework is of a hierarchical nature and induces the notion of a soft dendrogram, which can be helpful to explore the cluster structure of a dataset. The computational complexity of aggregating the cuts is only linear in the number of data points and places the bottleneck on generating the cuts, for which simple and fast algorithms form a sufficient basis. The contribution of this paper is to translate the abstract mathematical literature into algorithms that can be used in machine learning. We demonstrate the power of tangles in many different use cases and provide theoretical guarantees for their performance.