Source-linked AI summary
Visualization of Very Large High-Dimensional Data Sets as Minimum Spanning Trees
Daniel Probst, Jean-Louis Reymond
TL;DR
Large, high-dimensional chemical data are difficult to visualize because dimensionality reduction can be lossy and computationally expensive. TMAP represents such data as a two-dimensional tree, preserving neighborhood relationships and producing detailed, interpretable visualizations, while also revealing limitations in some modeling applications.
Problem
Visualizing large, high-dimensional data for human interpretation is difficult because dimensionality reduction is both lossy and computationally expensive.
Method
TMAP generates two-dimensional tree representations of high-dimensional data and defines structurally similar nearest neighbors for the visualization.
Results
TMAP preserves 1-nearest-neighbor relationships much better than UMAP under topological and Euclidean metrics, and visualized a protein data set in 32 seconds while clustering proteins by construction.
Takeaways & Limitations
TMAP generates highly detailed and interpretable representations of high-dimensional data sets for exploration and interpretation.
Takeaways & Limitations
The visualization hints at limitations when estimating solubility for polycyclic aromatic compounds and calculating hydration.
Abstract
from arXiv · showhide
The chemical sciences are producing an unprecedented amount of large, high-dimensional data sets containing chemical structures and associated properties. However, there are currently no algorithms to visualize such data while preserving both global and local features with a sufficient level of detail to allow for human inspection and interpretation. Here, we propose a solution to this problem with a new data visualization method, TMAP, capable of representing data sets of up to millions of data points and arbitrary high dimensionality as a two-dimensional tree (http://tmap.gdb.tools). Visualizations based on TMAP are better suited than t-SNE or UMAP for the exploration and interpretation of large data sets due to their tree-like nature, increased local and global neighborhood and structure preservation, and the transparency of the methods the algorithm is based on. We apply TMAP to the most used chemistry data sets including databases of molecules such as ChEMBL, FDB17, the Natural Products Atlas, DSSTox, as well as to the MoleculeNet benchmark collection of data sets. We also show its broad applicability with further examples from biology, particle physics, and literature.
Introduction
Large high-dimensional chemical data sets are difficult to visualize because dimensionality reduction is lossy and computationally expensive while preserving local and global structure. TMAP addresses this gap with a scalable tree-based visualization for detailed human inspection.
- Data scale and scope: Chemical databases contain millions of molecules and associated properties, including ChEMBL with n=1,159,881 and DSSTox with n=848,816.Other examples include FDB17, the Natural Products Atlas, DrugBank, and the 16-data-set MoleculeNet benchmark.
- Visualization gap: Linear dimensionality reduction preserves global features but mostly loses local nearest-neighbor relationships between molecules.These local relationships are important for understanding data structure and applicability to visualization.
- Existing approaches: Nonlinear manifold-learning methods preserve nearest-neighbor relationships better, but their assumption is that data lie on a lower-dimensional manifold.Examples include NLPCA, t-SNE, UMAP, GTM, and SOM.
- Existing approaches: At least O(n^1.14) to O(n^5) time complexities limit the size of data that existing nonlinear algorithms can visualize.Neighbor-joining and related tree methods face similar data-set-size limitations; ChemTreeMap visualizes approximately 10,000 data points at most.
- TMAP: TMAP generates intuitive two-dimensional tree visualizations for data sets of up to 10^7 points and arbitrary dimensionality.It combines locality-sensitive hashing, graph theory, and modern web technology, and integrates with established analysis and plotting workflows.
- TMAP: TMAP’s tree layout supports high-resolution inspection by showing closest distances between clusters and detailed cluster structure through branches and sub-branches.The authors report that TMAP surpasses t-SNE and UMAP in time and space complexity and apply it across chemistry and other scientific fields.
Methods
TMAP processes arbitrary data through approximate neighbor indexing, graph construction, minimum-spanning-tree extraction, and planar layout. Its central design removes graph cycles before embedding, while the layout phase is the computational bottleneck.
- Pipeline: TMAP uses four phases: LSH-forest indexing, approximate k-nearest-neighbor graph construction, minimum-spanning-tree calculation, and tree layout.The pipeline accepts an arbitrary data set as input.
- Phase I: indexing: LSH Forest enables approximate k-nearest-neighbor searches with sub-linear time complexity in n.MinHash encodes text and binary data, weighted MinHash encodes integer and floating-point data, and parameters d and l control memory and query speed.
- Phase II: graph construction: The approximate k-nearest-neighbor graph uses k and k_c to control neighbor searches and assigns each edge its endpoints’ Jaccard distance as weight.Its construction has overall time complexity O(n(k·k_c + log n)); practically, k·k_c > log n.
- Phase II: graph construction: The graph may be disconnected because of outliers or highly connected clusters, but subsequent phases remain applicable and can produce a minimum spanning forest.An arbitrary weighted graph can also be supplied as an edge list.
- Phase III: MST construction: Kruskal’s algorithm constructs the MST and removes all cycles, lowering the computational complexity of the low-dimensional embedding.Its time complexity is O(E + log V), making this phase negligible relative to graph construction.
- Phase IV: layout: TMAP lays out the unrooted MST in the Euclidean plane using a spring-electrical model with multilevel multipole-based force approximation.The OGDF framework supports layout adjustments, while parameter p must be adjusted according to input-data-set size; this phase is the computational bottleneck.
Results and Discussion
TMAP represents large, high-dimensional data as connected two-dimensional trees that preserve local and global relationships while exposing detailed cluster structure. Across chemical, biological, image, literature, and particle-physics examples, it provides interpretable visualizations at scales reaching millions of data points.
- TMAP versus UMAP: TMAP distributes clusters across MST branches and subbranches, producing a more even canvas distribution and higher visual resolution than UMAP.It explicitly represents relations both between and within clusters.
- TMAP versus UMAP: TMAP preserves nearest-neighbor locality better than UMAP under both topological and Euclidean metrics, although locality preservation depends strongly on parameter d.Parameters k and k_c have only minor influence on locality preservation.
- TMAP versus UMAP: TMAP is reproducible across identical runs, whereas comparable algorithms such as UMAP change considerably between runs.
- Chemical applications: In chemical maps, TMAP groups molecules by structural and biological similarities, revealing activity-associated branches and specialized structural regions.Examples include toxic polycyclic aromatic hydrocarbon regions in DSSTox and genus-associated branches in the Natural Products Atlas.
Conclusion
TMAP is introduced as a scalable visualization method that preserves global and local features in high-dimensional data while supporting high interpretability. It enables detailed visualizations of millions of data points across diverse data types without specialized hardware.
- TMAP represents very large, high-dimensional data sets as two-dimensional trees while preserving global and local features.The method is presented for data sets containing millions of points and arbitrary data types.
- TMAP combined with MHFP6 visualizes millions of organic molecules and associated properties at high resolution.The paper states that this resolution was not possible with previous methods.
- TMAP is applicable beyond chemistry to images, text, RNA-seq data, biology, computational linguistics, particle physics, and literature.Interactive visualizations, source code, and a Python package are also provided.
- TMAP shows low memory usage and running time, with performance reported as superior to t-SNE, UMAP, and PCA.The conclusion links this performance to adjustable parameters and output-quality or memory-use trade-offs.
- TMAP has an empirical sub-linear time complexity of O(n^0.931), enabling visualization of much larger high-dimensional data sets.The authors state that this scaling supports data sets with millions of points.
Supplementary Information
Supplementary evaluations examine locality preservation, parameter effects, and stability for TMAP compared with UMAP. They show strong nearest-neighbor preservation for TMAP on MNIST, while different parameters affect locality, aesthetics, memory, and speed unevenly.
- Parameter effects: Extreme values where d≈l deteriorate visualization quality, while larger parameter values increase memory usage and larger l also decreases query speed.These observations identify practical trade-offs when configuring the LSH Forest.
- Parameter effects: Point size p affects visualization aesthetics by controlling tree sparseness and the distance between points and branches.Reducing p allows the layout algorithm to draw points closer to their respective branches.
- Locality preservation: TMAP and UMAP were compared on sampled hyperspheres with dimensions n∈{3, 10, 100, 1000} and sample sizes from 100 to 1,000.The evaluation ranked the projected distances of each point’s 10 original-space nearest neighbors.
- Locality preservation: TMAP preserves more than 80% of true 1-nearest neighbors using topological distance and more than 35% using Euclidean distance on MNIST.UMAP preserves less than 10% of true 1-nearest neighbors in the same evaluation.
- Parameter effects: Parameters d and l strongly influence locality-preservation performance, whereas k and k_c have only marginal influence.The supplementary analysis identifies d and l as the dominant locality-related controls.
- Stability: Repeated runs produced perceived-identical TMAP outputs, whereas UMAP showed considerable differences between runs.Both algorithms were run four times on the same data sets with identical parameters.