Principal Geodesic Analysis of Merge Trees (and Persistence Diagrams)

• URL: http://arxiv.org/abs/2207.10960v1
• Date: Fri, 22 Jul 2022 09:17:22 GMT
• Title: Principal Geodesic Analysis of Merge Trees (and Persistence Diagrams)
• Authors: Mathieu Pont, Jules Vidal and Julien Tierny
• Abstract summary: We introduce an efficient, iterative algorithm which exploits shared-memory parallelism, as well as an analytic expression of the fitting energy gradient. We show the utility of our contributions by extending to merge trees two typical PCA applications. We present a dimensionality reduction framework exploiting the first two directions of the MT-PGA basis to generate two-dimensional layouts.
• Score: 8.430851504111585
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper presents a computational framework for the Principal Geodesic Analysis of merge trees (MT-PGA), a novel adaptation of the celebrated Principal Component Analysis (PCA) framework [87] to the Wasserstein metric space of merge trees [92]. We formulate MT-PGA computation as a constrained optimization problem, aiming at adjusting a basis of orthogonal geodesic axes, while minimizing a fitting energy. We introduce an efficient, iterative algorithm which exploits shared-memory parallelism, as well as an analytic expression of the fitting energy gradient, to ensure fast iterations. Our approach also trivially extends to extremum persistence diagrams. Extensive experiments on public ensembles demonstrate the efficiency of our approach - with MT-PGA computations in the orders of minutes for the largest examples. We show the utility of our contributions by extending to merge trees two typical PCA applications. First, we apply MT-PGA to data reduction and reliably compress merge trees by concisely representing them by their first coordinates in the MT-PGA basis. Second, we present a dimensionality reduction framework exploiting the first two directions of the MT-PGA basis to generate two-dimensional layouts of the ensemble. We augment these layouts with persistence correlation views, enabling global and local visual inspections of the feature variability in the ensemble. In both applications, quantitative experiments assess the relevance of our framework. Finally, we provide a lightweight C++ implementation that can be used to reproduce our results.

Related papers

• Graph Vertex Embeddings: Distance, Regularization and Community Detection [0.0]
  Graph embeddings have emerged as a powerful tool for representing complex network structures in a low-dimensional space. We present a family of flexible distance functions that faithfully capture the topological distance between different vertices. We evaluate the effectiveness of our proposed embedding constructions by performing community detection on a host of benchmark datasets.
  arXiv  Detail & Related papers  (2024-04-09T09:03:53Z)
• Pair then Relation: Pair-Net for Panoptic Scene Graph Generation [54.92476119356985]
  Panoptic Scene Graph (PSG) aims to create a more comprehensive scene graph representation using panoptic segmentation instead of boxes. Current PSG methods have limited performance, which hinders downstream tasks or applications. We present a novel framework: Pair then Relation (Pair-Net), which uses a Pair Proposal Network (PPN) to learn and filter sparse pair-wise relationships between subjects and objects.
  arXiv  Detail & Related papers  (2023-07-17T17:58:37Z)
• Wasserstein Auto-Encoders of Merge Trees (and Persistence Diagrams) [5.384630221560809]
  This paper presents a computational framework for the Wasserstein auto-encoding of merge trees (MT-WAE) In contrast to traditional auto-encoders which operate on vectorized data, our formulation explicitly manipulates merge trees on their associated metric space at each layer of the network. Experiments on public ensembles demonstrate the efficiency of our algorithms, with MT-WAE computations in the orders of minutes on average.
  arXiv  Detail & Related papers  (2023-07-05T09:46:52Z)
• Interactive Segmentation as Gaussian Process Classification [58.44673380545409]
  Click-based interactive segmentation (IS) aims to extract the target objects under user interaction. Most of the current deep learning (DL)-based methods mainly follow the general pipelines of semantic segmentation. We propose to formulate the IS task as a Gaussian process (GP)-based pixel-wise binary classification model on each image.
  arXiv  Detail & Related papers  (2023-02-28T14:01:01Z)
• Graph Spectral Embedding using the Geodesic Betweeness Centrality [76.27138343125985]
  We introduce the Graph Sylvester Embedding (GSE), an unsupervised graph representation of local similarity, connectivity, and global structure. GSE uses the solution of the Sylvester equation to capture both network structure and neighborhood proximity in a single representation.
  arXiv  Detail & Related papers  (2022-05-07T04:11:23Z)
• Graph-based hierarchical record clustering for unsupervised entity resolution [0.0]
  We build upon a state-of-the-art probabilistic framework named the Data Washing Machine (DWM) We introduce a graph-based hierarchical 2-step record clustering method (GDWM) that first identifies large, connected components or soft clusters in the matched record pairs. That is followed by breaking down the discovered soft clusters into more precise entity clusters in a hierarchical manner.
  arXiv  Detail & Related papers  (2021-12-12T21:58:07Z)
• Wasserstein Distances, Geodesics and Barycenters of Merge Trees [9.149293243237778]
  This paper presents a unified computational framework for the estimation of distances, geodesics and barycenters of merge trees. We introduce a new metric, called the Wasserstein distance between merge trees, which is purposely designed to enable efficient computations of geodesics and barycenters.
  arXiv  Detail & Related papers  (2021-07-16T09:27:49Z)
• DAGs with No Curl: An Efficient DAG Structure Learning Approach [62.885572432958504]
  Recently directed acyclic graph (DAG) structure learning is formulated as a constrained continuous optimization problem with continuous acyclicity constraints. We propose a novel learning framework to model and learn the weighted adjacency matrices in the DAG space directly. We show that our method provides comparable accuracy but better efficiency than baseline DAG structure learning methods on both linear and generalized structural equation models.
  arXiv  Detail & Related papers  (2021-06-14T07:11:36Z)
• Self-supervised Geometric Perception [96.89966337518854]
  Self-supervised geometric perception is a framework to learn a feature descriptor for correspondence matching without any ground-truth geometric model labels. We show that SGP achieves state-of-the-art performance that is on-par or superior to the supervised oracles trained using ground-truth labels.
  arXiv  Detail & Related papers  (2021-03-04T15:34:43Z)
• 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.