Functional Data Representation with Merge Trees
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Statistics. The day in statistics: methods, theory and the inference under them.
Tom: We're looking at the paper: "Functional Data Representation with Merge Trees".
Jane: Here's the gist of the paper. In this paper, authors propose functional data representation using merge trees as an alternative to persistence diagrams for topological data analysis, establishing a metric structure and proving theoretical results on their stability and consistency for functional data analysis Topological Representation of Functions The paper introduces merge trees as a representation of functions by tracking the topological changes along the sublevel set filtration of the function, which is invariant under homeomorphic reparametrizations of the domain The process involves transforming a function into a sequence of nested subsets and then tracking topological changes along this sequence to turn that information into a tree structure The construction of the merge tree is based on critical values and rules that define vertices as local minima or maxima, with the height function encoding these critical values Metric Structure and Invariance The authors define a metric structure for the space of merge trees based on edit distances, denoted as dE, which is specifically designed for comparing topological summaries by allowing modifications like shrinking edges or deleting edges with defined costs A key theoretical result established is that the isomorphism class of the merge tree of a function f is invariant under homeomorphic re-parametrization of f, meaning that if functions can be aligned by an homeomorphism, their associated merge trees are isomorphic This invariance allows for statistical analysis to be indifferent to functional misalignment Stability and Estimators The paper develops a new theoretical analysis on the stability/continuity of merge trees with respect to perturbations of the original functions, which is fundamental for building consistent estimators Theorem 12 states that if two functions are pointwise close, then we can turn the merge tree associated to the first function into the merge tree associated to the second function using at most one edit per vertex, and each edit has a small cost Furthermore, Theorem 20 provides a convergence rate for estimators based on piecewise affine interpolants of noisy samples, showing that P(dE(Tf, TfˆP L n,m) < 4ε) ≥ (1 − hn(C1ε))(1 − gn(C2ε))(1 − qn(C3ε/m)) Application to Functional Data Analysis The topological approach is tested on the Aneurisk65 dataset, where it is compared against traditional FDA pipelines, and the authors observe that merge trees and persistence diagrams capture different but highly correlated pieces of information about the current functional data set In a classification task, they found that when curvature and radius are jointly considered as descriptors, the distance metric based on dE yields a better classifier for merge trees while for PDs accuracy decreases The paper concludes that methods from TDA can be fruitfully added to functional data analysis, especially when non trivial smoothing and alignment are required for data representation The authors suggest that careful smoothing of the functional representation is enough to obtain good estimates of merge trees, and they point out that the information collected by merge trees is contained in the ordering and amplitude of extremal points rather than their exact abscissa The existence of Frech´et means in the space of merge trees may lead to extensions of existing frameworks, though it requires replacing uniqueness assumptions with locality assumptions for well-posedness The choice between merge trees and persistence diagrams should be guided by Occam’s razor based on whether the exact abscissa carries valuable information for the analysis The paper also discusses how to combine curvature and radius data using a metric defined as dp, which is a metric on the space of functions Appendix Summary Appendix A provides visual examples highlighting differences between PDs and merge trees for various functions, such as Figure 6 showing functions with the same PD but different merge trees Appendix D contains proofs for key theorems, including the proof of Theorem 6 which shows the isomorphism between the merge tree and persistence diagram when considering a homeomorphism Appendix C illustrates qualitative differences between PDs and merge trees, such as Example III where merge trees are more suitable to separate clusters based on merging structure The case study analysis confirms the advantages of the topological approach in achieving robust classification results The appendix also details the construction of merge trees under tameness assumptions, including Assumption 2 and Assumption 3 regarding regularity The appendix further presents a metric combining curvature and radius data using Proposition 31 References The paper cites numerous foundational works in functional data analysis, including Ramsay and Silverman (2005), and various papers on topological data analysis such as Hatcher (2000) It also references works on edit distances, such as Bille (2005), and specific topological data analysis methods like persistence diagrams by Cohen-Steiner et al.
Tom: (2007) The paper also cites works on functional data alignment, such as Srivastava et al.
Jane: (2011a), and work related to derivative estimation, such as Mack and Müller (1989) The references cover a broad range of topics from functional data analysis to algebraic topology and computational geometry The bibliography includes recent work on topological methods for data analysis, such as Justin Curry et al.
Tom: (2021), and work on merge trees by Morozov and Weber (2013) The references also include foundational texts like Rudin (1987) and works on kernel estimators like Nadaraya (1964) The collection of references demonstrates the interdisciplinary nature of the research, spanning statistics, topology, and computational methods The bibliography is extensive and supports the theoretical claims made in the paper regarding stability and consistency The references also include work on shape analysis, such as Dryden and Mardia (1998), and work on functional data alignment using the Fisher-Rao metric The references also include practical applications, such as the AneuRisk65 dataset analysis by Sangalli et al.
Title and authors: Tom: We've covered the basics of "Functional Data Representation with Merge Trees" and how it uses merge trees instead of persistence diagrams to represent functions, focusing on their invariance under reparametrization. Now we’re diving into what the authors are proposing about improving this representation and analysis >
Jane: They are suggesting that the main improvement is defining a new metric structure for these merge trees based on edit distances, called dE. This is designed specifically to compare topological summaries by allowing defined costs for modifications like shrinking edges or deleting edges >
Lu: That dE metric is crucial because it allows them to prove theoretical results on its specific implementation when merge trees represent functions, establishing a class of consistent estimators with convergence rates >
Meng: Consistency and convergence are good, but I need to know how this scales when we move from theory to actual production. Can we actually deploy an estimator that reliably estimates these merge trees from noisy data without it breaking at scale?
Tom: They address that in their work on stability. Theorem twelve states that if two functions are pointwise close, you can turn the merge tree of the first function into the second using at most one edit per vertex with a small cost > <ref:2108.13147#pg1>
Jane: And they follow up with Theorem twenty which provides a convergence rate for estimators based on piecewise affine interpolants of noisy samples, showing that error falls with terms like C1 times the infinity norm of the difference between functions, plus terms involving the difference in their derivatives >
Lu: That convergence rate is pretty strong. It shows that the error decreases with respect to m to some power, specifically P(dE(Tf, TfˆP L n,m) < four epsilon) greater than (one minus h times C1 epsilon)(one minus g times C2 epsilon)(one minus q times C3 over m) >
Meng: That looks like a complex convergence guarantee. What does that actually mean for the deployment cost? Is it a constant time operation, or is it something that depends heavily on the complexity of the tree?
Tom: It’s not constant time, but they are showing how fast it converges for piecewise affine interpolants. They use these interpolants to approximate the trees and get that guarantee >
Jane: So they’re showing a pathway from noisy samples to a good estimate of the merge tree, even if the data is messy >
The paper's summary: Tom: We just talked about how they define metrics like dE for comparing trees and the convergence rates for estimators derived from noisy samples. Now let’s get back to what this whole paper actually claims about this topological representation of functions using merge trees >
Jane: They propose using merge trees as an alternative to persistence diagrams because they are invariant under homeomorphic reparametrizations, which means the statistical analysis can be indifferent to functional misalignment >
Lu: The core idea is that instead of fixing a topology and extracting homology groups from a space, you get a sequence of topological spaces along various pipelines, and tracking how those homology groups evolve along this sequence is the most interesting for real valued functions >
Meng: So it’s about tracking the evolution of holes as you move through the sublevel sets of the function, which seems like a very detailed way to capture shape information >
Tom: It’s a very detailed way to capture that structure, and they test this on the Aneurisk65 dataset, and they found that merge trees and persistence diagrams capture different but highly correlated pieces of information about the data set >
Jane: That correlation is key because it suggests you don't have to choose one or the other blindly; you can get rich information from both approaches >
The paper's improvements: Tom: So what are the actual improvements they are suggesting for using this method, beyond just the basic representation and comparison metrics? What’s next for this approach?
Jane: They suggest that when non trivial smoothing and alignment are required for data representation, these topological methods can be fruitfully added to functional data analysis >
Lu: They point out that careful smoothing of the functional representation is enough to obtain good estimates of merge trees, which is a way to simplify the estimation process >
Meng: So instead of needing perfect alignment upfront, we just need some reasonable smoothing to get good results? That sounds like a major reduction in required preprocessing work >
Tom: It’s about simplifying the estimation pipeline by focusing on what actually matters. They also suggest that when you need precise differential information about the data, you should look at other methods >
Jane: And they also point out that for classification, when curvature and radius are jointly considered as descriptors, using the mixed distance metric based on dE yields a better classifier for merge trees compared to persistence diagrams >
Lu: It seems like they’re moving towards fusing information. They're suggesting that we should combine curvature and radius data using a metric defined as dp, which is a metric on the space of functions >
Conclusion: Tom: So, to wrap up on "Functional Data Representation with Merge Trees," the main point is that this method offers a representation based on equivalence classes that are invariant with respect to homeomorphic transformations of the abscissa >
Jane: It gives us a way to handle functional data by using merge trees that are invariant under reparametrizations, making statistical analysis indifferent to functional misalignment >
Lu: They established the metric structure and proved theoretical results on its stability and consistency for these representations, providing a framework for building consistent estimators with convergence rates >
Meng: For deployment, it means we need good smoothing to get good estimates of merge trees rather than perfect alignment upfront >
Tom: So, this paper is about using topological tools to represent functions in a way that handles the structure of functional data without forcing us into a specific choice between different topological summaries >
Jane: It’s about giving us more flexible ways to analyze complex functional data by looking at the ordering and amplitude of extremal points rather than their exact abscissa >
Lu: This framework is solid for building consistent estimators, and it provides a framework that’s quite solid for building things on top of >
Meng: It’s a viable path forward when you need to handle functional data representation with merge trees, but we still have to deal with the practicalities of deployment and smoothing >
Matteo Pegoraro, Piercesare Secchi
Aalborg University · Politecnico di Milano
stat.ME, math.ST, stat.OT, stat.TH
Submitted: 2021-08-30
Updated: 2026-10-30
Project page: https://statistics.mox.polimi.it/aneurisk
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 85/100
The gist: In this paper, authors propose functional data representation using merge trees as an alternative to persistence diagrams for topological data analysis…
Key concepts
- Merge Trees
- A tree structure representing a function by tracking its topological changes along a sublevel set filtration. Vertices are defined by critical values (local minima or maxima), encoding the function's shape through this nested subset sequence.
- Metric Structure (dE)
- A distance metric, denoted dE, specifically designed to compare merge trees. It allows for modifications like shrinking or deleting edges with defined costs, providing a robust way to measure the topological difference between two functions.
- Invariance under Homeomorphic Reparametrization
- The key property where the merge tree of a function remains the same if the function is reparametrized homeomorphically. This means statistical analysis based on these trees is independent of how the input function's domain is mapped.
- Stability and Estimators
- Theoretical results proving that estimators built from noisy samples converge to the true merge tree structure. If two functions are close, their corresponding merge trees will also be close under a defined edit distance, ensuring consistent estimation.
Terminology
Summary
In this paper, authors propose functional data representation using merge trees as an alternative to persistence diagrams for topological data analysis, establishing a metric structure and proving theoretical results on their stability and consistency for functional data analysis
Topological Representation of Functions
The paper introduces merge trees as a representation of functions by tracking the topological changes along the sublevel set filtration of the function, which is invariant under homeomorphic reparametrizations of the domain The process involves transforming a function into a sequence of nested subsets and then tracking topological changes along this sequence to turn that information into a tree structure The construction of the merge tree is based on critical values and rules that define vertices as local minima or maxima, with the height function encoding these critical values
Metric Structure and Invariance
The authors define a metric structure for the space of merge trees based on edit distances, denoted as dE, which is specifically designed for comparing topological summaries by allowing modifications like shrinking edges or deleting edges with defined costs A key theoretical result established is that the isomorphism class of the merge tree of a function f is invariant under homeomorphic re-parametrization of f, meaning that if functions can be aligned by an homeomorphism, their associated merge trees are isomorphic This invariance allows for statistical analysis to be indifferent to functional misalignment
Stability and Estimators
The paper develops a new theoretical analysis on the stability/continuity of merge trees with respect to perturbations of the original functions, which is fundamental for building consistent estimators Theorem 12 states that if two functions are pointwise close, then we can turn the merge tree associated to the first function into the merge tree associated to the second function using at most one edit per vertex, and each edit has a small cost Furthermore, Theorem 20 provides a convergence rate for estimators based on piecewise affine interpolants of noisy samples, showing that P(dE(Tf, TfˆP L n,m) < 4ε) ≥ (1 − hn(C1ε))(1 − gn(C2ε))(1 − qn(C3ε/m))
Application to Functional Data Analysis
The topological approach is tested on the Aneurisk65 dataset, where it is compared against traditional FDA pipelines, and the authors observe that merge trees and persistence diagrams capture different but highly correlated pieces of information about the current functional data set In a classification task, they found that when curvature and radius are jointly considered as descriptors, the distance metric based on dE yields a better classifier for merge trees while for PDs accuracy decreases
Conclusion and Future Directions
The paper concludes that methods from TDA can be fruitfully added to functional data analysis, especially when non trivial smoothing and alignment are required for data representation The authors suggest that careful smoothing of the functional representation is enough to obtain good estimates of merge trees, and they point out that the information collected by merge trees is contained in the ordering and amplitude of extremal points rather than their exact abscissa The existence of Frech´et means in the space of merge trees may lead to extensions of existing frameworks, though it requires replacing uniqueness assumptions with locality assumptions for well-posedness The choice between merge trees and persistence diagrams should be guided by Occam’s razor based on whether the exact abscissa carries valuable information for the analysis The paper also discusses how to combine curvature and radius data using a metric defined as dp, which is a metric on the space of functions
Appendix Summary
Appendix A provides visual examples highlighting differences between PDs and merge trees for various functions, such as Figure 6 showing functions with the same PD but different merge trees Appendix D contains proofs for key theorems, including the proof of Theorem 6 which shows the isomorphism between the merge tree and persistence diagram when considering a homeomorphism Appendix C illustrates qualitative differences between PDs and merge trees, such as Example III where merge trees are more suitable to separate clusters based on merging structure The case study analysis confirms the advantages of the topological approach in achieving robust classification results The appendix also details the construction of merge trees under tameness assumptions, including Assumption 2 and Assumption 3 regarding regularity The appendix further presents a metric combining curvature and radius data using Proposition 31
References
The paper cites numerous foundational works in functional data analysis, including Ramsay and Silverman (2005), and various papers on topological data analysis such as Hatcher (2000) It also references works on edit distances, such as Bille (2005), and specific topological data analysis methods like persistence diagrams by Cohen-Steiner et al. (2007) The paper also cites works on functional data alignment, such as Srivastava et al. p. 1 (2011a), and work related to derivative estimation, such as Mack and Müller (1989) The references cover a broad range of topics from functional data analysis to algebraic topology and computational geometry The bibliography includes recent work on topological methods for data analysis, such as Justin Curry et al. p. 1 (2021), and work on merge trees by Morozov and Weber (2013) The references also include foundational texts like Rudin (1987) and works on kernel estimators like Nadaraya (1964) The collection of references demonstrates the interdisciplinary nature of the research, spanning statistics, topology, and computational methods The bibliography is extensive and supports the theoretical claims made in the paper regarding stability and consistency The references also include work on shape analysis, such as Dryden and Mardia (1998), and work on functional data alignment using the Fisher-Rao metric The references also include practical applications, such as the AneuRisk65 dataset analysis by Sangalli et al. (2009b) The bibliography is comprehensive and supports the paper's claims regarding the comparison between merge trees and persistence diagrams The references also include work on edit distance metrics by Bille (2005) and topological consistency via kernel estimation by Bobrowski et al. (2017) The references also include work on the stability of persistence diagrams by Cohen-Steiner et al. p. 2 (2007), and work on topological trajectory classification by Pokorny et al. p. 0 (2023) The references also include work on the topological inverse problem, such as Justin Curry et al. (2021), and work on topological trajectory classification with filtrations of simplicial complexes by Pokorny et al. p. 0 (2016) The bibliography is rich and supports the theoretical framework proposed in the paper regarding merge trees
Appendix A Summary
Appendix A provides visual examples highlighting differences between PDs and merge trees for various functions, such as Figure 6 showing functions with the same PD but different merge trees It also shows examples of functions f0, f1, and f2 with their associated topological representations The appendix includes a comparative analysis of the Aneurisk65 dataset, illustrating how merge trees and PDs perform in supervised classification tasks
Appendix B Summary
Appendix B introduces formal definitions for representing a real valued function f: X → R by means of a merge tree under conditions (A0), including the formal definition of tameness (Assumption 2) and regularity (Assumption 3) These assumptions ensure that all topological changes happen at critical values, which is crucial for the construction of merge trees
Appendix C Summary
Appendix C presents qualitative ideas on what kind of variability between functions is better captured by PDs versus merge trees, exemplified in Example I where functions are distinguished by their merging structure despite having the same persistence diagram Example II demonstrates that PDs perform much better than merge trees when distinguishing clusters based on amplitude of oscillations Example III shows that merge trees can effectively separate two clusters when the merging structure is the discriminating feature, even if persistence diagrams are similar
Appendix D Summary
Appendix D contains proofs for key theorems, including the proof of Theorem 6 which establishes the isomorphism between merge tree and persistence diagram under homeomorphism The appendix also includes proofs for Theorems 11 and 12, which deal with the properties of leaf correspondence in merge trees and stability results for estimators
Appendix E Summary
Appendix E details the construction of the edit path between two merge trees F and G, showing how deletions, ghosting, and shrinking operations are performed to induce an edit path with a cost less than 2ε This process involves pruning internal vertices and coupling them using the LCA operator to obtain the final distance bound Appendix F shows how deletions are performed on both trees to establish cost bounds for deleted vertices
Appendix G Summary
Appendix G focuses on the internal vertices of the merge trees, proving Lemma 27 and Lemma 28 which provide bounds on the height difference between corresponding internal vertices in two trees under small perturbations The section concludes by showing how to couple these internal vertices to establish an edit path with a cost less than 2ε
Appendix H Summary
Appendix H summarizes the proof of Theorem 20, which establishes the convergence rate for merge tree estimators based on piecewise affine interpolants, showing that dE(Tf, TfˆP L n,m) ≤ C1∥ f − ˆfn∥∞ +C2∥ Df − D ˆfn∥∞ +C3∥ D2 ˆfn − D2f∥∞ m+C4/m This proof relies on the convergence of the functional estimators and the approximation properties of piecewise affine functions The appendix also includes an example of a functional estimator derived from kernel methods, such as Theorem 21 The final section concludes with a case study on the Aneurisk65 dataset, comparing classification results obtained using merge trees and persistence diagrams
References Summary
The paper cites a wide range of literature spanning functional data analysis, algebraic topology, and computational geometry Key references include Ramsay and Silverman (2005), Hatcher (2000), Cohen-Steiner et al. (2007), Bille (2005), and various papers on merge tree metrics by Morozov and Weber (2013) The bibliography is extensive and supports the theoretical framework proposed in the paper regarding stability and consistency It also includes work on shape analysis, such as Dryden and Mardia (1998) and functional data alignment using the Fisher-Rao metric The references include practical applications like Sangalli et al. (2009b), and works on derivative estimation by Mack and Müller (1989) The references also include work on topological trajectory classification by Pokorny et al. (2023) and topological inverse problems by Justin Curry et al. p. 7 (2021) The bibliography is rich and supports the theoretical framework proposed in the paper regarding merge trees
Case Study Summary
The case study on the Aneurisk65 dataset demonstrates that while PDs perform better when examining radius data separately, when curvature and radius are jointly considered using the mixed distance metric d2 mixed, merge trees yield a better classifier for classification tasks This suggests that merge trees capture informative interactions between curvature and radius that PDs do not The overall conclusion is that the topological approach, especially when combined with careful smoothing, provides robust results comparable to traditional FDA methods This supports the use of merge trees as a viable representation for functional data analysis The authors emphasize that the invariance property of merge trees lightens the burden of careful alignment, making them advantageous in scenarios where reparametrization is possible
Final Thoughts
The paper concludes that while both PDs and merge trees are useful tools, merge trees offer a representation based on equivalence classes that are invariant with respect to homeomorphic transformations of the abscissa The authors suggest that Occam’s razor should guide the analyst’s final choice, noting that if the order of critical points is important for analysis, persistence diagrams should be avoided Ultimately, careful smoothing is mandatory for precise estimation of merge trees and when precise differential information about the data is needed The work opens avenues for future research into multivariate functional data and statistical tools to better interpret populations of trees
Acknowledgements
The authors thank Steve Marron who initiated them to algebraic topology for the statistical analysis of functional data during seminal discussions They also thank the AneuRisk Project for providing the data analyzed in the case study The authors express gratitude to the editor and reviewers for their constructive comments which contributed to a significant improvement of the original manuscript
The paper cites a wide range of literature spanning functional data analysis, algebraic topology, and computational geometry Key references include Ramsay and Silverman (2005), Hatcher (2000), Cohen-Steiner et al. (2007), Bille (2005), and various papers on merge tree metrics by Morozov and Weber (2013) The bibliography is extensive and supports the theoretical framework proposed in the paper regarding stability and consistency It also includes work on shape analysis, such as Dryden and Mardia (1998), and functional data alignment using the Fisher-Rao metric The references include practical applications like Sangalli et al.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Topological Data Representation for Functional Data Analysis This allows AI systems to represent functions by means of merge trees which are invariant under homeomorphic reparametrizations, making statistical analysis indifferent to functional misalignment and decoupling phase and amplitude variabilities.
-
Robust Classification on Misaligned Data The AI system can perform supervised classification on misaligned functional data using a pipeline that compares merge tree representations with persistence diagrams, showing that
merge trees capture different but highly correlated pieces of information about the current functional data set
while achieving good accuracy in separating classes like U from L and N in the Aneurisk65 dataset. -
Consistent Estimation from Noisy Samples Estimators for Merge Trees The system can estimate merge trees from noisy samples using regression estimators, ensuring that if two functions are pointwise close,
dE(Tf, Tfˆn) goes to 0
when the number of vertices is bounded, providing a consistent estimator. -
High-Dimensional Feature Fusion for Classification Classification pipelines can be improved by blending discriminatory information from curvature and radius scores using the mixed distance formula m2 i,j = c2 i,j + r2 i,j to create a new distance matrix dmixed that yields a better classifier for merge trees than persistence diagrams.
-
Computationally Tractable Approximations for Merge Trees The system can compute an estimator for merge trees by using piecewise affine interpolants f P L n,m which allows the exact computation of the tree's critical points and provides convergence guarantees like P(dE(Tf, TfˆP L n,m) < 4ε) ≥ (1 − hn(C1ε))(1 − gn(C2ε))(1 − qn(C3ε/m)).
Sources
- Geodesic Mixed Effects Models for Repeatedly Observed/Longitudinal Random Objects
- From Trees to Barcodes and Back Again II: Combinatorial and Probabilistic Aspects of a Topological Inverse Problem
- A Persistence-Driven Edit Distance for Trees with Abstract Weights
- A Finitely Stable Edit Distance for Merge Trees
- Generic families of finite metric spaces with identical or trivial 1-dimensional persistence
Related papers
- Neural Estimation of Summary Statistics for Simulation-Based Inference with Non-Asymptotic Guarantees
- Spectral divide-and-conquer MCMC for long stationary time series
- Improving the Efficiency of Subgroup Analysis in Randomized Controlled Trials with TMLE
- Personalized Federated Vector Autoregression with Personalization Diversity
- Doubly Robust and Efficient Calibration of Prediction Sets for Right-Censored Time-to-Event Outcomes
- Covariance-Calibrated Prediction-Powered Inference