$k$-Means Clustering for Persistent Homology

• URL: http://arxiv.org/abs/2210.10003v4
• Date: Sat, 25 Nov 2023 13:04:28 GMT
• Title: $k$-Means Clustering for Persistent Homology
• Authors: Yueqi Cao, Prudence Leung, Anthea Monod
• Abstract summary: We prove convergence of the $k$-means clustering algorithm on persistence diagram space. We also establish theoretical properties of the solution to the optimization problem in the Karush--Kuhn--Tucker framework.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Persistent homology is a methodology central to topological data analysis that extracts and summarizes the topological features within a dataset as a persistence diagram; it has recently gained much popularity from its myriad successful applications to many domains. However, its algebraic construction induces a metric space of persistence diagrams with a highly complex geometry. In this paper, we prove convergence of the $k$-means clustering algorithm on persistence diagram space and establish theoretical properties of the solution to the optimization problem in the Karush--Kuhn--Tucker framework. Additionally, we perform numerical experiments on various representations of persistent homology, including embeddings of persistence diagrams as well as diagrams themselves and their generalizations as persistence measures; we find that $k$-means clustering performance directly on persistence diagrams and measures outperform their vectorized representations.

Related papers

• Discrete transforms of quantized persistence diagrams [0.5249805590164902]
  We introduce Qupid, a novel and simple method for vectorizing persistence diagrams. Key features are the choice of log-scaled grids that emphasize information contained near the diagonal in persistence diagrams. We conduct an in-depth experimental analysis of Qupid, showing that the simplicity of our method results in very low computational costs.
  arXiv  Detail & Related papers  (2023-12-28T16:11:11Z)
• Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
  The reliability of graph embeddings depends on how much the geometry of the continuous space matches the graph structure. We introduce a new class of manifold, named soft manifold, that can solve this situation. Using soft manifold for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets.
  arXiv  Detail & Related papers  (2023-11-29T12:48:33Z)
• On the Expressivity of Persistent Homology in Graph Learning [13.608942872770855]
  Persistent homology, a technique from computational topology, has recently shown strong empirical performance in the context of graph classification. This paper provides a brief introduction to persistent homology in the context of graphs, as well as a theoretical discussion and empirical analysis of its expressivity for graph learning tasks.
  arXiv  Detail & Related papers  (2023-02-20T08:19:19Z)
• Geometry Contrastive Learning on Heterogeneous Graphs [50.58523799455101]
  This paper proposes a novel self-supervised learning method, termed as Geometry Contrastive Learning (GCL) GCL views a heterogeneous graph from Euclidean and hyperbolic perspective simultaneously, aiming to make a strong merger of the ability of modeling rich semantics and complex structures. Extensive experiments on four benchmarks data sets show that the proposed approach outperforms the strong baselines.
  arXiv  Detail & Related papers  (2022-06-25T03:54:53Z)
• Approximating Persistent Homology for Large Datasets [0.0]
  Persistent homology produces a statistical summary in the form of a persistence diagram. Despite its widespread use, persistent homology is simply impossible to implement when a dataset is very large. We show that the mean of the persistence diagrams of subsamples is a valid approximation of the true persistent homology of the larger dataset.
  arXiv  Detail & Related papers  (2022-04-19T23:07:27Z)
• Effective and Efficient Graph Learning for Multi-view Clustering [173.8313827799077]
  We propose an effective and efficient graph learning model for multi-view clustering. Our method exploits the view-similar between graphs of different views by the minimization of tensor Schatten p-norm. Our proposed algorithm is time-economical and obtains the stable results and scales well with the data size.
  arXiv  Detail & Related papers  (2021-08-15T13:14:28Z)
• Hermitian Symmetric Spaces for Graph Embeddings [0.0]
  We learn continuous representations of graphs in spaces of symmetric matrices over C. These spaces offer a rich geometry that simultaneously admits hyperbolic and Euclidean subspaces. The proposed models are able to automatically adapt to very dissimilar arrangements without any apriori estimates of graph features.
  arXiv  Detail & Related papers  (2021-05-11T18:14:52Z)
• Spatial-Spectral Clustering with Anchor Graph for Hyperspectral Image [88.60285937702304]
  This paper proposes a novel unsupervised approach called spatial-spectral clustering with anchor graph (SSCAG) for HSI data clustering. The proposed SSCAG is competitive against the state-of-the-art approaches.
  arXiv  Detail & Related papers  (2021-04-24T08:09:27Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  Joint network topology inference represents a canonical problem of learning multiple graph Laplacian matrices from heterogeneous graph signals. We propose a general graph estimator based on a novel structured fusion regularization. We show that the proposed graph estimator enjoys both high computational efficiency and rigorous theoretical guarantee.
  arXiv  Detail & Related papers  (2021-03-05T04:42:32Z)
• Robust Persistence Diagrams using Reproducing Kernels [15.772439913138161]
  We develop a framework for constructing robust persistence diagrams from superlevel filtrations of robust density estimators constructed using kernels. We demonstrate the superiority of the proposed approach on benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-17T17:16:52Z)
• Embedding Graph Auto-Encoder for Graph Clustering [90.8576971748142]
  Graph auto-encoder (GAE) models are based on semi-supervised graph convolution networks (GCN) We design a specific GAE-based model for graph clustering to be consistent with the theory, namely Embedding Graph Auto-Encoder (EGAE) EGAE consists of one encoder and dual decoders.
  arXiv  Detail & Related papers  (2020-02-20T09:53:28Z)

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.