Geometry-Aware Merge Tree Comparisons for Time-Varying Data with Interleaving Distances

Lin Yan, Talha Bin Masood, Farhan Rasheed, Ingrid Hotz, Bei WangIEEE TVCG 2021 · OpenReview

TL;DR

This paper introduces a novel method for comparing "merge trees," which are topological summaries of data, by incorporating geometric information from the original data. This "geometry-aware" approach allows for more insightful analysis of time-varying datasets, enabling better detection of structural changes, clusters, and periodic patterns.

What Problem Does This Paper Address?

Analyzing large and complex datasets, especially those that change over time, is a significant challenge. Topological Data Analysis (TDA) offers powerful tools like "merge trees" to abstract and summarize essential data structures. Merge trees are particularly useful for time-varying data because they provide compressed representations and allow for comparisons to understand relationships like clusters or outliers. However, existing methods for comparing merge trees often ignore the geometric context of the original data (e.g., the spatial locations of features) and can be computationally expensive due to considering all possible correspondences between critical points. This paper addresses this gap by proposing a method to integrate geometric information into merge tree comparisons, making them more sensitive to real-world data characteristics and more efficient.

Methods

The core contribution is a two-step framework for geometry-aware merge tree comparisons:

  1. Labeling Step: This is the novel part. Instead of just comparing the abstract tree structures, this step establishes correspondences between the critical points (like local minima and maxima) of two merge trees by encoding geometric information from the original scalar fields. This includes:
  2. Tree Mapping: Uses intrinsic tree distances and geometric embeddings.
  3. Euclidean Mapping: Relies on the spatial distances between critical points.
  4. Hybrid Mapping: A generalized approach combining tree and Euclidean distances, controlled by a parameter $\lambda$.
  5. Morse Mapping: Leverages unstable manifolds of critical points, inspired by Morse theory.
  6. Dummy Leaves/Vertices: Strategies to ensure comparable merge trees by adding artificial nodes when necessary.
  7. Time-Varying Pivot Tree: A strategy for handling sequences of merge trees where labels are propagated sequentially, adapting to temporal changes.
  8. Comparison Step: Once labeled, the merge trees are transformed into "induced matrices." Distances are then computed between these matrices using standard norms (L∞, L¹, L²), which are referred to as labeled interleaving distances. This approach is more efficient than brute-force methods because the labeling step pre-establishes correspondences, avoiding the need to consider all possible pairings.

Datasets

The authors evaluate their framework on several datasets:

  • Moving Gaussian Dataset: A synthetic time-varying dataset with 12 time steps, designed to demonstrate tracking a moving feature.
  • Corner Flow Dataset: A 2D viscous flow simulation dataset with 94 time instances, used to detect structural transitions.
  • Heated Flow Dataset: A 2D turbulent plume simulation dataset with 300 time steps, also used for detecting structural transitions.
  • Red Sea Dataset: A dataset from a high-resolution ocean circulation model with 60 time steps, used to demonstrate cluster detection.
  • Wing Dataset: A simulation of a starting vortex behind an aerofoil with 40 time steps, used for cluster detection.
  • Vortex Street Dataset: A classic 2D von Kárman vortex street dataset, used to detect periodicities.

Key Insights and Ideas

  • Geometry Matters: The core idea is that ignoring geometric information in merge tree comparisons leads to a loss of crucial insights, especially for time-varying data where spatial relationships are key.
  • Decoupling for Efficiency and Generality: Separating the problem into a "labeling" (correspondence finding) and "comparison" (distance calculation) step makes the framework more general and computationally tractable.
  • Labeling as the Key: The variety of labeling strategies (tree, Euclidean, hybrid, Morse) allows for flexible integration of domain knowledge and geometric context.
  • Time-Varying Dynamics: The "time-varying pivot tree" strategy is crucial for effectively analyzing sequences of data, capturing how topological features evolve and shift over time.
  • Diagnosing Transitions: The labeled interleaving distance, particularly when visualized as a distance matrix, can clearly highlight points in time where significant structural changes occur.

Key Results

The paper demonstrates that their geometry-aware merge tree comparisons effectively:

  • Detect Structural Transitions: The method successfully identified transitions in flow datasets (Corner Flow, Heated Flow), often highlighting changes caused by the disappearance or appearance of critical points. In some cases, their method detected transitions missed by other metrics or identified artifacts introduced by simplification.
  • Detect Clusters: For datasets like the Red Sea and Wing, the framework revealed distinct clusters of time instances with similar topological structures, which were visually corroborated by examining the scalar fields and their corresponding merge trees. The labeled interleaving distance ($d_I$) often provided clearer and more separable clusters than other metrics.
  • Detect Periodicities: In the Vortex Street dataset, the method, especially with a pivot-free strategy, captured periodicities of length 37 and 75, with the longer periodicity being attributed to the metric's sensitivity to geometric information.
  • Efficiency: By pre-establishing correspondences, the framework reduces the computational burden compared to methods that explore all possible pairings.

Limitations and Future Work

  • Robustness to Noise: The authors acknowledge that while the method is robust to certain geometric changes, it might not be as robust as some other metrics when dealing with data that has a large amount of noise or a very large number of features. Improving robustness is a direction for future work.
  • Computational Efficiency: While more efficient than some alternatives, computing the labeled interleaving distance naively takes $O(n^2)$ time. Future work could explore more scalable computation methods, potentially inspired by existing research.
  • Choosing the Right Strategy: The paper presents various labeling strategies but notes that choosing the most appropriate one for a given dataset remains an open question.
  • Integration of Domain Knowledge: The framework is designed to easily incorporate domain-specific knowledge during the labeling process, which could be further explored.

Summary updated

Abstract

Merge trees, a type of topological descriptor, serve to identify and summarize the topological characteristics associated with scalar fields. They present a great potential for the analysis and visualization of time-varying data. First, they give compressed and topology-preserving representations of data instances. Second, their comparisons provide a basis for studying the relations among data instances, such as their distributions, clusters, outliers, and periodicities. A number of comparative measures have been developed for merge trees. However, these measures are often computationally expensive since they implicitly consider all possible correspondences between critical points of the merge trees. In this paper, we perform geometry-aware comparisons of merge trees using labeled interleaving distances. The main idea is to decouple the computation of a comparative measure into two steps: a labeling step that generates a correspondence between the critical points of two merge trees, and a comparison step that computes distances between a pair of labeled merge trees by encoding them as matrices. We show that our approach is general, computationally efficient, and practically useful. Our general framework makes it possible to integrate geometric information of the data domain in the labeling process. At the same time, it reduces the computational complexity since not all possible correspondences have to be considered. We demonstrate via experiments that such geometry-aware merge tree comparisons help to detect transitions, clusters, and periodicities of time-varying datasets, as well as to diagnose and highlight the topological changes between adjacent data instances.
BibTeX
@article{yan2021geometry,
  author = {Lin Yan and Talha Bin Masood and Farhan Rasheed and Ingrid Hotz and Bei Wang},
  title = {{Geometry-Aware Merge Tree Comparisons for Time-Varying Data with Interleaving Distances}},
  journal = {IEEE Trans. Vis. Comput. Graph.},
  year = {2021},
  url = {https://openreview.net/forum?id=JxRGdTJeKS},
}
Figure