The Central Spanning Tree Problem

• URL: http://arxiv.org/abs/2404.06447v1
• Date: Tue, 9 Apr 2024 16:49:42 GMT
• Title: The Central Spanning Tree Problem
• Authors: Enrique Fita Sanmartín, Christoph Schnörr, Fred A. Hamprecht,
• Abstract summary: Spanning trees are an important primitive in many data analysis tasks, when a data set needs to be summarized in terms of its "skeleton" We show empirically that the (branched) central spanning tree is more robust to noise in the data, and as such is better suited to summarize a data set in terms of its skeleton.
• Score: 20.14154858576556
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Spanning trees are an important primitive in many data analysis tasks, when a data set needs to be summarized in terms of its "skeleton", or when a tree-shaped graph over all observations is required for downstream processing. Popular definitions of spanning trees include the minimum spanning tree and the optimum distance spanning tree, a.k.a. the minimum routing cost tree. When searching for the shortest spanning tree but admitting additional branching points, even shorter spanning trees can be realized: Steiner trees. Unfortunately, both minimum spanning and Steiner trees are not robust with respect to noise in the observations; that is, small perturbations of the original data set often lead to drastic changes in the associated spanning trees. In response, we make two contributions when the data lies in a Euclidean space: on the theoretical side, we introduce a new optimization problem, the "(branched) central spanning tree", which subsumes all previously mentioned definitions as special cases. On the practical side, we show empirically that the (branched) central spanning tree is more robust to noise in the data, and as such is better suited to summarize a data set in terms of its skeleton. We also propose a heuristic to address the NP-hard optimization problem, and illustrate its use on single cell RNA expression data from biology and 3D point clouds of plants.

Related papers

• Learning a Decision Tree Algorithm with Transformers [75.96920867382859]
  We introduce MetaTree, a transformer-based model trained via meta-learning to directly produce strong decision trees. We fit both greedy decision trees and globally optimized decision trees on a large number of datasets, and train MetaTree to produce only the trees that achieve strong generalization performance.
  arXiv  Detail & Related papers  (2024-02-06T07:40:53Z)
• Prediction Algorithms Achieving Bayesian Decision Theoretical Optimality Based on Decision Trees as Data Observation Processes [1.2774526936067927]
  This paper uses trees to represent data observation processes behind given data. We derive the statistically optimal prediction, which is robust against overfitting. We solve this by a Markov chain Monte Carlo method, whose step size is adaptively tuned according to a posterior distribution for the trees.
  arXiv  Detail & Related papers  (2023-06-12T12:14:57Z)
• HyperAid: Denoising in hyperbolic spaces for tree-fitting and hierarchical clustering [36.738414547278154]
  We propose a new approach to treemetric denoising (HyperAid) in hyperbolic spaces. It transforms original data into data that is more'' tree-like, when evaluated in terms of Gromov's $delta$ hyperbolicity. We integrate HyperAid with schemes for enforcing nonnegative edge-weights.
  arXiv  Detail & Related papers  (2022-05-19T17:33:16Z)
• Spectral Top-Down Recovery of Latent Tree Models [13.681975313065477]
  Spectral Top-Down Recovery (STDR) is a divide-and-conquer approach for inference of large latent tree models. STDR's partitioning step is non-random. Instead, it is based on the Fiedler vector of a suitable Laplacian matrix related to the observed nodes. We prove that STDR is statistically consistent, and bound the number of samples required to accurately recover the tree with high probability.
  arXiv  Detail & Related papers  (2021-02-26T02:47:42Z)
• Visualizing hierarchies in scRNA-seq data using a density tree-biased autoencoder [50.591267188664666]
  We propose an approach for identifying a meaningful tree structure from high-dimensional scRNA-seq data. We then introduce DTAE, a tree-biased autoencoder that emphasizes the tree structure of the data in low dimensional space.
  arXiv  Detail & Related papers  (2021-02-11T08:48:48Z)
• SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples [75.32013242448151]
  We consider learning Ising tree models when the observations from the nodes are corrupted by independent but non-identically distributed noise. Katiyar et al. (2020) showed that although the exact tree structure cannot be recovered, one can recover a partial tree structure. We propose Symmetrized Geometric Averaging (SGA), a more statistically robust algorithm for partial tree recovery.
  arXiv  Detail & Related papers  (2021-01-22T01:57:35Z)
• Growing Deep Forests Efficiently with Soft Routing and Learned Connectivity [79.83903179393164]
  This paper further extends the deep forest idea in several important aspects. We employ a probabilistic tree whose nodes make probabilistic routing decisions, a.k.a., soft routing, rather than hard binary decisions. Experiments on the MNIST dataset demonstrate that our empowered deep forests can achieve better or comparable performance than [1],[3].
  arXiv  Detail & Related papers  (2020-12-29T18:05:05Z)
• Forest R-CNN: Large-Vocabulary Long-Tailed Object Detection and Instance Segmentation [75.93960390191262]
  We exploit prior knowledge of the relations among object categories to cluster fine-grained classes into coarser parent classes. We propose a simple yet effective resampling method, NMS Resampling, to re-balance the data distribution. Our method, termed as Forest R-CNN, can serve as a plug-and-play module being applied to most object recognition models.
  arXiv  Detail & Related papers  (2020-08-13T03:52:37Z)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  We present a novel algorithm for learning optimal classification trees based on dynamic programming and search. Our approach uses only a fraction of the time required by the state-of-the-art and can handle datasets with tens of thousands of instances.
  arXiv  Detail & Related papers  (2020-07-24T17:06:55Z)
• Bounds of the sum of edge lengths in linear arrangements of trees [0.90238471756546]
  In particular, we investigate various problems on the sum of edge lengths in trees of a fixed size. We establish some foundations for research on optimality scores for spatial networks in one dimension.
  arXiv  Detail & Related papers  (2020-06-24T21:53:39Z)

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.