Wasserstein Distances, Geodesics and Barycenters of Merge Trees

Mathieu Pont, Jules Vidal, Julie Delon, Julien Tierny

External link (DOI)
View presentation:2021-10-28T13:45:00ZGMT-0600Change your timezone on the schedule page
2021-10-28T13:45:00Z
Exemplar figure, described by caption below
The merge trees of three members (a-c) of the Isabel ensemble (wind velocity) concisely and visually encode the number, the salience and the connectivity of the features of interest found in the data. The pointwise mean for the three members (d) exhibits 5 salient maxima and its merge tree is not representative of the input trees, in contrast of the Wasserstein barycenter tree (e). Our framework for distances, geodesics and barycenters enables a variety of applications, including (f) feature tracking, (g) temporal reduction and (h) ensemble clustering and summarization of the main trends of features found in the ensemble.
Fast forward

Direct link to video on YouTube: https://youtu.be/ifVvH0uMW6k

Abstract

This paper presents a unified computational framework for the estimation of distances, geodesics and barycenters of merge trees. We extend recent work on the edit distance and introduce a new metric, called the Wasserstein distance between merge trees, which is purposely designed to enable efficient computations of geodesics and barycenters. Specifically, our new distance is strictly equivalent to the L 2 -Wasserstein distance between extremum persistence diagrams, but it is restricted to a smaller solution space, namely, the space of rooted partial isomorphisms between branch decomposition trees. This enables a simple extension of existing optimization frameworks for geodesics and barycenters from persistence diagrams to merge trees. We introduce a task-based algorithm which can be generically applied to distance, geodesic, barycenter or cluster computation. The task-based nature of our approach enables further accelerations with shared-memory parallelism. Extensive experiments on public ensembles and SciVis contest benchmarks demonstrate the efficiency of our approach – with barycenter computations in the orders of minutes for the largest examples – as well as its qualitative ability to generate representative barycenter merge trees, visually summarizing the features of interest found in the ensemble. We show the utility of our contributions with dedicated visualization applications: feature tracking, temporal reduction and ensemble clustering. We provide a lightweight C++ implementation that can be used to reproduce our results.