# Sketching Merge Trees for Scientific Data Visualization

arXiv: https://arxiv.org/abs/2101.03196 · HTML: https://mlsanity.com/paper/2101.03196/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 63 references that are in the map.
- First posted on arXiv 8 Jan 2021.

## Builds on (most cited first, 13 of 13)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Fast Computation of Wasserstein Barycenters](https://mlsanity.com/paper/1310.4375/) (2013)
- [Optimal Transport for structured data with application on graphs](https://mlsanity.com/paper/1805.09114/) (2018)
- [Gromov-Wasserstein Learning for Graph Matching and Node Embedding](https://mlsanity.com/paper/1901.06003/) (2019)
- [Gromov-Wasserstein Alignment of Word Embedding Spaces](https://mlsanity.com/paper/1809.00013/) (2018)
- [Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching](https://mlsanity.com/paper/1905.07645/) (2019)
- [Sliced Gromov-Wasserstein](https://mlsanity.com/paper/1905.10124/) (2019)
- [Coresets and Sketches](https://mlsanity.com/paper/1601.00617/) (2016)
- [Learning Generative Models across Incomparable Spaces](https://mlsanity.com/paper/1905.05461/) (2019)
- [Frequent Directions : Simple and Deterministic Matrix Sketching](https://mlsanity.com/paper/1501.01711/) (2015)
- [Gromov-Wasserstein Averaging in a Riemannian Framework](https://mlsanity.com/paper/1910.04308/) (2019)
- [Sketching and Clustering Metric Measure Spaces](https://mlsanity.com/paper/1801.00551/) (2018)
- [Intrinsic Interleaving Distance for Merge Trees](https://mlsanity.com/paper/1908.00063/) (2019)

## Built on by (most cited first, 2 of 2)

- [Principal Geodesic Analysis of Merge Trees (and Persistence Diagrams)](https://mlsanity.com/paper/2207.10960/) (2022)
- [Visualizing the loss landscapes of physics-informed neural networks](https://mlsanity.com/paper/2602.05849/) (2026)

## Abstract (arXiv)

Merge trees are a type of topological descriptors that record the connectivity among the sublevel sets of scalar fields. They are among the most widely used topological tools in visualization. In this paper, we are interested in sketching a set of merge trees. That is, given a large set T of merge trees, we would like to find a much smaller basis set S such that each tree in T can be approximately reconstructed from a linear combination of merge trees in S. A set of high-dimensional vectors can be sketched via matrix sketching techniques such as principal component analysis and column subset selection. However, up until now, topological descriptors such as merge trees have not been known to be sketchable. We develop a framework for sketching a set of merge trees that combines the Gromov-Wasserstein probabilistic matching with techniques from matrix sketching. We demonstrate the applications of our framework in sketching merge trees that arise from time-varying scientific simulations. Specifically, our framework obtains a much smaller representation of a large set of merge trees for downstream analysis and visualization. It is shown to be useful in identifying good representatives and outliers with respect to a chosen basis. Finally, our work shows a promising direction of utilizing randomized linear algebra within scientific visualization.