From Trees to Barcodes and Back Again II: Combinatorial and Probabilistic Aspects of a Topological Inverse Problem

Justin Curry, Jordan DeSha, Adélie Garin, Kathryn Hess, Lida Kanari, Brendan MalleryComput. Geom 2021

TL;DR

This paper delves into the "inverse problem" of constructing merge trees from barcodes, a fundamental task in Topological Data Analysis (TDA). The authors establish a novel combinatorial link between merge trees and permutations, leading to precise formulas for the number of merge trees realizing a given barcode. This work provides a crucial "null hypothesis" for analyzing real-world data, particularly in neuroscience.

What Problem Does This Paper Address?

Topological Data Analysis (TDA) uses "barcodes" (or persistence diagrams) as summaries of the shape of data. However, these summaries are lossy, meaning many different data structures can produce the same barcode. The "inverse problem" in TDA is to understand what these original structures are, given a barcode. This paper focuses on the specific inverse problem of reconstructing "merge trees" from barcodes. Merge trees are a type of rooted tree used to represent hierarchical structures, like neuron morphologies.

The authors highlight two key aspects:

  1. Distinguishing Tree Types: They clarify the combinatorial differences between "phylogenetic trees" (used in evolutionary biology) and "merge trees" (used in TDA).
  2. Quantifying Realizations: They precisely calculate the number of merge trees that can generate a given barcode, especially when barcodes are sampled uniformly. This is crucial for understanding the "descriptive power" of barcodes and for developing statistical tools.

Methods

The paper employs a combination of combinatorial and algebraic techniques. Key methods include:

  • Left Inversion Vector: A novel approach is taken by relating the "tree realization number" (TRN) – the number of merge trees realizing a barcode – to the product of entries in the left inversion vector of the permutation associated with the barcode. This is a departure from traditional studies that focus on the sum of inversion vector entries.
  • Dirichlet Convolution: The distribution of TRNs is characterized using Dirichlet convolution, a powerful tool in number theory and combinatorics. This allows for recursive computation of probability distributions.
  • Combinatorial Equivalence: The authors define and utilize notions of combinatorial equivalence for both merge trees and barcodes, linking them to permutations in the symmetric group ($S_n$).
  • Bruhat Order: The relationship between the TRN and the Bruhat order on the symmetric group is explored, showing that the TRN is an order-preserving map.

Datasets

The paper does not introduce new datasets for training or evaluation. Instead, it uses:

  • Simulated Barcodes: Barcodes are generated using two methods:
  • Random birth and death times, leading to a non-uniform distribution on permutation types.
  • Separated birth and death times, designed to induce a uniform distribution on the symmetric group.
  • Real Neuron Data: The paper references real neuron data (basal and apical dendrites) as motivation and for comparison in Figure 2, showing that their barcodes exhibit different distributions than uniformly sampled ones.

Key Insights and Ideas

  • Permutation as a Barcode Signature: The paper solidifies the idea that the "permutation type" of a barcode (derived from the ordering of birth and death times) is a fundamental invariant that dictates the number of merge trees realizing it.
  • TRN as a Product of Inversions: The surprising discovery that the tree realization number is the product of the entries in the left inversion vector of the associated permutation. This offers a new perspective on permutation statistics.
  • Convexity of Barcode Spaces: Combinatorial equivalence classes of barcodes with the same permutation type form "convex" sets, meaning they can be connected by a continuous path of barcodes of the same type. This has implications for understanding the geometry of barcode space.
  • Merge Trees vs. Phylogenetic Trees: A clear combinatorial distinction is drawn, showing that merge trees are sensitive to the relative heights of internal (death) nodes, while phylogenetic trees are not. This leads to different counting formulas for their respective combinatorial classes.
  • A "Null Hypothesis" for Data Analysis: By studying the distribution of TRNs under a uniform distribution on barcodes, the paper provides a foundational "null hypothesis" against which real-world data (like neuron morphologies) can be tested.

Key Results

  • Combinatorial Distinction: The number of combinatorial equivalence classes of merge trees on $n+1$ leaves is $(n+1)!n!2^{-n}$, contrasting with $(2n-1)!!$ for phylogenetic trees.
  • TRN Formula: The tree realization number $R(B)$ for a strict barcode $B$ with $n$ finite length bars is given by the product of the indices of its bars: $R(B) = \prod_{j=1}^{n} \mu(I_j)$, where $\mu(I_j)$ is the number of bars containing $I_j$. This is further related to the product of entries in the left inversion vector of the barcode's associated permutation.
  • Sum of TRNs: The sum of realization numbers over all permutations in $S_n$ equals the number of maximal chains in the lattice of partitions, $(n+1)!n!2^{-n}$.
  • Probabilistic Distributions: Formulas are derived for the distribution of TRNs under a uniform barcode distribution, including the expected TRN $E[R] = \frac{(n+1)!}{2^n}$ and the variance.
  • Expected Log TRN: A closed-form formula for the expected log realization number is provided: $E[\log(R(B))] = \sum_{i=1}^{n} \frac{\log(i!)}{i}$.

Limitations and Future Work

  • Real Data vs. Uniform Hypothesis: The paper acknowledges that real-world data, particularly biological barcodes, are unlikely to follow a uniform distribution on permutation types. The uniform distribution serves as a baseline "null hypothesis."
  • Geometry of Barcode Space: The authors suggest that further work could explore the geometry of barcode space more deeply, potentially by describing it in terms of convex sets that fiber over the permutohedron.
  • Higher Moments: While the first and second moments of the TRN distribution are calculated, a general formula for higher moments is outlined but not fully computed.
  • Applications to Neuroscience: The paper motivates the study with neuroscience applications but leaves the detailed exploration of how to identify biological barcodes and generate artificial ones for future work.

Summary updated

Abstract

In this paper we consider two aspects of the inverse problem of how to construct merge trees realizing a given barcode. Much of our investigation exploits a recently discovered connection between the symmetric group and barcodes in general position, based on the simple observation that death order is a permutation of birth order. The first important outcome of our study is a clear combinatorial distinction between the space of phylogenetic trees (as defined by Billera, Holmes and Vogtmann) and the space of merge trees. Generic BHV trees on $n+1$ leaf nodes fall into $(2n-1)!!$ distinct strata, but the analogous number for merge trees is equal to the number of maximal chains in the lattice of partitions, i.e., $(n+1)!n!2^{-n}$. The second aspect of our study is the derivation of precise formulas for the distribution of tree realization numbers (the number of merge trees realizing a given barcode) when we assume that barcodes are sampled using a uniform distribution on the symmetric group. We are able to characterize some of the higher moments of this distribution, thanks in part to a reformulation in terms of Dirichlet convolution. This characterization provides a type of null hypothesis, apparently different from the distributions observed in real neuron data and opens the door to doing more precise science.
BibTeX
@article{curry2021from,
  author = {Justin Curry and Jordan DeSha and Adélie Garin and Kathryn Hess and Lida Kanari and Brendan Mallery},
  title = {{From Trees to Barcodes and Back Again II: Combinatorial and Probabilistic Aspects of a Topological Inverse Problem}},
  journal = {Comput. Geom},
  year = {2021},
}
Figure