CHARM: Certified Homology-Aware Reverse-scale Mapping via Diffusion-Guided Quotient Towers

Zhe Li

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:

  1. 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.
  2. 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.
  3. 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.
  4. 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.
The joint display of geometry and homology supports across various datasets. The first column highlights certified supports (red/blue for voids), showing how CHARM localizes high-dimensional structures in the 2D view.

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

Abstract

Widely used dimensionality reduction methods prioritize neighborhood or distance 1 preservation, yet planar coordinates alone cannot certify the homological type or 2 sample-level support of higher-order structures. Obtaining this evidence directly 3 is costly because simplicial complexes grow rapidly with dimension. We propose 4 Certified Homology-Aware Reverse-scale Mapping (CHARM), which combines 5 two-dimensional coordinates with certified homology records and sample-level 6 localization. Diffusion coordinates guide cover proposals; safe contractions and a 7 Cover Quotient Tower reduce the domain of structural computation; exact algebra 8 certifies and tracks homology representatives; and reverse-scale layout places their 9 supports in shared coordinates. Safe contraction preserves the homotopy type of 10 the input flag complex. The quotient tower is multiplicatively 3-interleaved with 11 the coarse-graph hop-distance Rips filtration. Verifiable distance-distortion bounds 12 give an additive guarantee between the original Euclidean and coarse-graph Rips 13 filtrations, and composite multiplicative guarantees for the tower on positive scales. 14 Across 22 datasets and 41,637 samples under a fixed configuration, CHARM 15 ranks among the top two on all 15 sample-weighted metrics for nonsynthetic data, 16 including the smallest values on all four Euclidean persistence-diagram distances. 17 It also provides 957 traceable support records across the full benchmark. On a 18 spherical shell, one certified H2 record identifies 1,578 original samples in the 19 two-dimensional view. CHARM thus combines geometric exploration with explicit 20 evidence of homological type and location.
BibTeX
@misc{li2026charm,
  author = {Zhe Li},
  title = {{CHARM: Certified Homology-Aware Reverse-scale Mapping via Diffusion-Guided Quotient Towers}},
  year = {2026},
  eprint = {2611.10375},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.10375},
}
Figure