TL;DR
CHARM (Certified Homology-Aware Reverse-scale Mapping) is a new dimensionality reduction framework that doesn't just cluster data in 2D, but mathematically "certifies" the topological structures (like loops and voids) present in the original high-dimensional space. By combining diffusion geometry with efficient "quotient towers," it provides a visually coherent layout where every identified topological feature is linked back to the specific data points that support it.
What Problem Does This Paper Address?
Dimensionality reduction (DR) tools like t-SNE and UMAP are staples for visualizing complex data, but they have a major blind spot: they prioritize local neighborhood preservation over global topological integrity. A "hole" in a 2D plot might be a genuine feature of the high-dimensional data, or it might just be an artifact of the projection (the "crowding problem").
Conversely, Topological Data Analysis (TDA) can identify these structures (homology) with mathematical rigor, but doing so is computationally expensive—simplicial complexes grow exponentially with data size and dimension. Furthermore, TDA often produces abstract "barcodes" that are difficult to map back to the visual clusters seen in DR plots. CHARM bridges this gap by providing a DR method that is "homology-aware," offering formal guarantees that the structures you see are real and traceable.
Methods
CHARM operates in four integrated stages:
- Diffusion-Guided Proposals & Safe Contraction: The algorithm uses diffusion coordinates (which smooth out noise) to propose regions of the data to compress. It employs "safe graph contractions" that are mathematically proven to preserve the base homotopy type—meaning it shrinks the data without "plugging" any holes or creating new ones.
- Cover Quotient Towers: To handle multi-scale data efficiently, CHARM builds a "Quotient Tower." This structure allows for compressed topological computation while maintaining a 3-interleaving guarantee with the original data's Rips filtration. This ensures that the topological features found in the compressed version are a faithful approximation of the true features.
- Exact Algebraic Certification: Instead of relying on heuristics, CHARM uses exact algebra on incidence blocks to certify homology representatives ($H_1$ for loops, $H_2$ for voids). It tracks these features across different scales to determine their persistence.
- Reverse-scale Layout: Finally, the method uses a shared coordinate optimization. It starts at the coarsest scale to establish the global structure and refines down to individual points, ensuring the final 2D view respects both local neighborhoods and the certified global topology.
Datasets
The authors evaluated CHARM across 22 datasets totaling 41,637 samples:
- 9 Nonsynthetic Datasets: Including MNIST, Fashion-MNIST, COIL-20, COIL-100, mouse scRNA-seq data, and Google News word embeddings.
- 13 Synthetic Datasets: Designed to test specific topological features, such as spheres, intersecting spheres, a Klein bottle, and various tori.
Key Insights and Ideas
- Localization is Key: Unlike standard TDA which tells you that a hole exists, CHARM tells you where it is by identifying the "homology support"—the specific set of original samples that form the boundary of the hole.
- Compression without Loss: The "safe contraction" condition is a standout idea. By checking for chordless four-cycles in the graph before contracting an edge, the algorithm ensures the "skeleton" of the data remains topologically identical to the original.
- Bridging Scales: The use of a "Reverse-scale" procedure allows the layout to be initialized by the global topological structure, preventing the "drift" often seen in purely local DR methods.
- Certification as a First-Class Citizen: Homology isn't just a post-processing step; it's baked into the optimization objective, providing a "certified" label for structures in the 2D view.
Key Results
CHARM demonstrates state-of-the-art performance in both geometric and topological preservation:
- Top-Tier Performance: Across 22 datasets, CHARM ranked in the top two on all 15 sample-weighted metrics for nonsynthetic data.
- Topological Accuracy: It achieved the smallest error values on all four Euclidean persistence-diagram distances (Bottleneck and Wasserstein distances for $H_0$ and $H_1$), proving it preserves the "shape" of the data better than t-SNE, UMAP, or Isomap.
- Traceable Evidence: The method provided 957 traceable support records across the benchmark. For example, in a spherical shell dataset, it correctly identified a certified $H_2$ void supported by 1,578 original samples.
Limitations and Future Work
While powerful, the authors note several areas for further exploration:
- Parameter Sensitivity: Future work is needed to test how robust the localization is to changes in diffusion parameters and noise levels.
- Higher-Order Discovery: While CHARM handles $H_1$ and $H_2$ well, extending efficient discovery and certification to even higher dimensions ($H_k$ for $k \ge 3$) remains a computational challenge.
- Computational Cost: Although the quotient tower significantly reduces the domain, the search for higher-dimensional simplices can still hit resource budgets on extremely complex datasets, leading to "indeterminate" states.
Summary updated