Tangles and Hierarchical Clustering

• URL: http://arxiv.org/abs/2203.08731v1
• Date: Wed, 16 Mar 2022 16:23:48 GMT
• Title: Tangles and Hierarchical Clustering
• Authors: Eva Fluck
• Abstract summary: We show that the central duality theorem connecting tangles with hierarchical decompositions holds if submodularity is replaced by a different property that we call maximum-submodular. We show that the data structure that represents hierarchical clustering results, called dendograms, are equivalent to maximum-submodular connectivity functions and their tangles.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We establish a connection between tangles, a concept from structural graph theory that plays a central role in Robertson and Seymour's graph minor project, and hierarchical clustering. Tangles cannot only be defined for graphs, but in fact for arbitrary connectivity functions, which are functions defined on the subsets of some finite universe. In typical clustering applications these universes consist of points in some metric space. Connectivity functions are usually required to be submodular. It is our first contribution to show that the central duality theorem connecting tangles with hierarchical decompositions (so-called branch decompositions) also holds if submodularity is replaced by a different property that we call maximum-submodular. We then define a connectivity function on finite data sets in an arbitrary metric space and prove that its tangles are in one-to-one correspondence with the clusters obtained by applying the well-known single linkage clustering algorithms to the same data set. Lastly we generalize this correspondence for any hierarchical clustering. We show that the data structure that represents hierarchical clustering results, called dendograms, are equivalent to maximum-submodular connectivity functions and their tangles. The idea of viewing tangles as clusters has first been proposed by Diestel and Whittle in 2016 as an approach to image segmentation. To the best of our knowledge, our result is the first that establishes a precise technical connection between tangles and clusters.

Related papers

• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means one-step dimensionality reduction clustering method has made some progress in addressing the curse of dimensionality in clustering tasks. We propose a unified framework that integrates manifold learning with K-means, resulting in the self-supervised graph embedding framework.
  arXiv  Detail & Related papers  (2024-09-24T08:59:51Z)
• HeNCler: Node Clustering in Heterophilous Graphs through Learned Asymmetric Similarity [55.27586970082595]
  HeNCler is a novel approach for Heterophilous Node Clustering. We show that HeNCler significantly enhances performance in node clustering tasks within heterophilous graph contexts.
  arXiv  Detail & Related papers  (2024-05-27T11:04:05Z)
• Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
  We propose a new deep graph clustering method termed Reinforcement Graph Clustering. In our proposed method, cluster number determination and unsupervised representation learning are unified into a uniform framework. In order to conduct feedback actions, the clustering-oriented reward function is proposed to enhance the cohesion of the same clusters and separate the different clusters.
  arXiv  Detail & Related papers  (2023-08-13T18:12:28Z)
• Contrastive Hierarchical Clustering [8.068701201341065]
  CoHiClust is a Contrastive Hierarchical Clustering model based on deep neural networks. By employing a self-supervised learning approach, CoHiClust distills the base network into a binary tree without access to any labeled data.
  arXiv  Detail & Related papers  (2023-03-03T07:54:19Z)
• flow-based clustering and spectral clustering: a comparison [0.688204255655161]
  We study a novel graph clustering method for data with an intrinsic network structure. We exploit an intrinsic network structure of data to construct Euclidean feature vectors. Our results indicate that our clustering methods can cope with certain graph structures.
  arXiv  Detail & Related papers  (2022-06-20T21:49:52Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  We propose a novel semi-supervised subspace clustering method, which is able to simultaneously augment the initial supervisory information and construct a discriminative affinity matrix. Comprehensive experimental results on six commonly-used benchmark datasets demonstrate the superiority of our method over state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-05-21T01:47:17Z)
• Structured Graph Learning for Clustering and Semi-supervised Classification [74.35376212789132]
  We propose a graph learning framework to preserve both the local and global structure of data. Our method uses the self-expressiveness of samples to capture the global structure and adaptive neighbor approach to respect the local structure. Our model is equivalent to a combination of kernel k-means and k-means methods under certain condition.
  arXiv  Detail & Related papers  (2020-08-31T08:41:20Z)
• Clustering with Tangles: Algorithmic Framework and Theoretical Guarantees [10.992467680364962]
  In this paper, we showcase the practical potential of tangles in machine learning applications. Given a collection of cuts of any dataset, tangles aggregate these cuts to point in the direction of a dense structure. We construct the algorithmic framework for clustering with tangles, prove theoretical guarantees in various settings, and provide extensive simulations and use cases.
  arXiv  Detail & Related papers  (2020-06-25T14:23:56Z)
• Graph Neural Networks with Composite Kernels [60.81504431653264]
  We re-interpret node aggregation from the perspective of kernel weighting. We present a framework to consider feature similarity in an aggregation scheme. We propose feature aggregation as the composition of the original neighbor-based kernel and a learnable kernel to encode feature similarities in a feature space.
  arXiv  Detail & Related papers  (2020-05-16T04:44:29Z)
• Order preserving hierarchical agglomerative clustering [0.0]
  We study the problem of order preserving hierarchical clustering of this kind of ordered data. The clustering is similarity based and uses standard linkage functions, such as single- and complete linkage. An optimal hierarchical clustering is defined as the partial dendrogram corresponding to the ultrametric closest to the original dissimilarity measure.
  arXiv  Detail & Related papers  (2020-04-26T21:58:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.