Wasserstein Distances, Geodesics and Barycenters of Merge Trees

Area of Science:

• Computational Topology
• Data Analysis
• Scientific Visualization

Background:

• Merge trees are crucial for analyzing complex datasets.
• Existing methods for merge tree analysis lack efficient computational frameworks for distances and barycenters.
• The edit distance and persistence diagrams have limitations in representing merge tree structures.

Purpose of the Study:

• To develop a unified computational framework for estimating distances, geodesics, and barycenters of merge trees.
• To introduce a novel Wasserstein distance metric tailored for merge trees.
• To enable efficient and scalable computation of merge tree properties for data analysis and visualization.

Main Methods:

• Introduced a Wasserstein distance for merge trees, equivalent to the L2-Wasserstein distance on persistence diagrams but restricted to a smaller solution space.
• Extended existing optimization frameworks for persistence diagrams to merge trees.
• Developed a task-based algorithm for generic computation of distances, geodesics, barycenters, and clusters, leveraging shared-memory parallelism.

Main Results:

• Demonstrated the efficiency of the framework with barycenter computations taking minutes for large datasets.
• Showcased the qualitative ability to generate representative barycenter merge trees that visually summarize ensemble features.
• Validated the approach on public ensembles and SciVis contest benchmarks.

Conclusions:

• The proposed Wasserstein distance and computational framework provide an efficient and scalable solution for merge tree analysis.
• The framework facilitates advanced visualization applications such as feature tracking, temporal reduction, and ensemble clustering.
• A lightweight C++ implementation is available for reproducing the results.