Mapper Algorithm: Topological Skeleton of High-Dimensional Data

Цели урока

• Understand the four-step Mapper pipeline
• Choose an appropriate lens function for an exploratory task
• Tune resolution and gain with stability in mind
• Apply Mapper to neural-network interpretation and biomedical data

Предварительные знания

• Basic Mapper (top-29)
• Bottleneck and Wasserstein distances (top-33)
• Clustering (DBSCAN, single-linkage)
• Dimensionality reduction (PCA, UMAP)

• Mapper Algorithm (basic)
• Bottleneck/Wasserstein
• Stability Theorem

Mapper found a new breast-cancer subtype that no clusterer could see - 9 patients with 100 percent survival.

• **Genomics**: breast-cancer subtype discovery with 100 percent survival in the identified flare group
• **Neuroscience**: fMRI brain dynamics via cyclic Mapper structures
• **Drug discovery**: mapping 100 thousand molecules in chemical space
• **Explainable AI**: topological interpretation of neural-network activations
• **Finance**: correlation-matrix analysis of financial instruments

Mapper from Stanford to Ayasdi

The Mapper algorithm was presented by Gurjeet Singh, Facundo Memoli, and Gunnar Carlsson at the Symposium on Point-Based Graphics in 2007. In 2008 Carlsson, Singh, and Dara Entekhabi founded Ayasdi to commercialise TDA tools including Mapper. The turning point was the Nicolau, Levine, Carlsson paper in PNAS 2012: Mapper revealed a breast-cancer subtype with superior survival in 9 patients. This work became a landmark of TDA in biomedicine and drew wide attention. Today Mapper is implemented in open libraries (kepler-mapper, scikit-tda, Giotto-TDA) and widely used in computational biology and neuroscience.

Mapper Pipeline: From Data to Graph

2012. Monica Nicolau and Stanford colleagues run Mapper on 295 gene-expression profiles of breast-cancer patients. Standard k-means clustering finds the expected 3 subtypes. But Mapper reveals something different - a flare, a small connected branch of the topological skeleton, detached from the main network. The flare contains 9 patients. This group shows 100 percent five-year survival while the rest of the cohort shows 60 to 70 percent. Mapper found a new breast-cancer subtype no clusterer could see. The paper appeared in PNAS and became a flagship demonstration of TDA in biomedicine.

Mapper proceeds in four clear steps. The lens compresses data into a low-dimensional representation, the cover slices the image into overlapping pieces, clustering in preimages turns pieces into graph nodes, and the nerve from nodes and intersections yields the final topological skeleton. The output is a simplicial complex, typically visualised as a graph.

Mapper is neither classical statistics nor machine learning. It is a topological exploration tool: it visualises data connectivity making no distributional assumptions. Clustering produces nodes; Mapper produces a connectivity graph among them.

Mapper visualises the activation space of a neural-network final layer. Each node is a cluster of test examples with similar activations. Node colour is the dominant class. The Mapper graph shows the topological structure of decisions: which classes neighbour each other, where the decision boundary lies, which examples fit no cluster.

Unlike persistence diagrams, the Mapper graph depends on three arbitrary choices: lens, cover, and clustering. The same dataset yields different graphs under different parameters. This is both a strength (multiple aspects visible) and a weakness (no canonical answer).

Choosing the Lens Function

The lens is the most influential Mapper parameter. The same dataset, different lenses, different graphs, different discoveries. The original 2012 paper used L2-eccentricity: the distance of each point to the cloud centre of mass. This lens highlighted peripheral patients - the flare group lived in the farthest eccentricity region.

Standard lens options: (1) L2-eccentricity - distance to centre, (2) density - count of neighbours in a fixed radius, (3) PCA projection - first or first two principal components, (4) UMAP/t-SNE embedding in R^2, (5) domain-specific - survival time, time to event, expression of one gene.

An autoencoder bottleneck trained on the same data Mapper will run on provides an optimal lens for nonlinear structure. For 20000-gene genomic data, embedding to 2-3 dimensions. Mapper on this embedding reveals cell-differentiation trajectories.

If the lens itself contains errors (e.g. a poorly trained autoencoder), the Mapper graph inherits all those artefacts. Validate the lens separately: for instance check stability under bootstrap resampling of data.

No lens is universally best. Lens choice is part of the research process. Practice: run Mapper with multiple lenses, compare graphs, look for common stable structures. If every lens shows the same branch - that is a strong signal. If a structure vanishes under a lens swap - it is an artefact of a specific choice.

Cover Parameters and Stability

Cover is the second half of Mapper. After the lens, one decides how to slice the one-dimensional (or k-dimensional) image into pieces. Two parameters govern this: resolution r - number of intervals, gain g - overlap fraction between adjacent intervals. Small r yields a coarse graph, large r a detailed one. Small g leaves the graph disconnected, large g produces a tightly connected one.

Typical practical parameter values: r from 10 to 50 (depending on dataset size), g from 0.3 to 0.5 (standard). Larger gain yields a more connected graph, smaller gain produces more separate components. Parameter tuning is iterative with visual feedback.

Running Mapper over a grid of (r, g) values yields a graph ensemble. Stable structures appearing over a wide grid region are deemed reliable. MultiNerve and Mapper Interleaving techniques formalise this: they select parameters under which Mapper output is stable.

Unlike persistence diagrams, Mapper lacks a universal 2007-style stability theorem. Carriere and Oudot in 2018 proved limited stability under careful parameter choice, but generally Mapper is unstable. Conclusions need care: one Mapper graph alone is not proof.

Modern libraries (kepler-mapper, scikit-tda, Giotto-TDA) automate parameter tuning: they run grid search and measure output similarity. If neighbouring grid cells produce graphs with small Wasserstein distance between Mapper diagrams, the configuration is deemed stable.

Applications: Genomics, Neuroscience, Drug Discovery

Over fifteen years Mapper has become a standard topological-exploration tool across several scientific fields. Genomics uses it to find new disease subtypes. Neuroscience uses it to analyse brain functional connectivity. Pharma uses it to map the chemical space of potential drugs. Finance uses it to analyse market correlation structures. Mapper does not replace statistics or ML - it complements them with a topological perspective.

Five flagship Mapper applications: (1) breast-cancer subtype discovery (Nicolau 2012), (2) T-cell differentiation (Rizvi 2017), (3) fMRI brain dynamics (Saggar 2018), (4) chemical-space mapping in drug discovery, (5) market-correlation analysis in finance.

A Mapper graph of ResNet50 final-layer activations on ImageNet reveals: classes organise not discretely but as a continuous manifold. Cats and dogs neighbour topologically through breeds. This explains why the network confuses specific class pairs - they lie close on the graph.

Mapper generates hypotheses; it does not confirm them. Every discovery via Mapper (such as the flare in breast cancer) needs independent validation via statistical methods on held-out data. A graph alone is not a statistically significant statement.

Modern Mapper implementations: kepler-mapper (Python, actively maintained), scikit-tda (part of the scikit-learn ecosystem), Giotto-TDA (industrial TDA stack), TDAMapper (R). All support export to visualisation tools (NetworkX, Graphviz, D3.js) and integrate with pandas/sklearn pipelines.

Extensions and applications of Mapper

Mapper integrates into the modern data-science stack as a data-exploration tool.

• TDA in neural networks — Related topic
• Witness complexes — Related topic
• TDA for time series — Related topic
• Persistent homology (advanced) — Related topic

Key ideas

• Mapper is a four-step pipeline: lens, cover, clustering, nerve
• The lens chooses which aspect of the data to study - L2-eccentricity, density, learned embedding
• Resolution and gain control graph detail and connectivity
• Mapper has no universal stability - robustness comes from grid search and output comparison
• Applications: breast-cancer subtypes, brain dynamics, drug discovery, explainable AI
• Mapper generates hypotheses; it does not statistically confirm them

Вопросы для размышления

• Which data properties make Mapper more informative than k-means clustering?
• Why does production deployment demand parameter stability, and how is it assessed for Mapper?
• Which limitations does Mapper carry compared to persistence diagrams?

Связанные уроки

• top-29 — basic version of the Mapper algorithm
• top-33 — metrics for comparing Mapper outputs
• top-32 — stability for Mapper graphs
• top-37 — Mapper for neural network interpretability
• alg-12-bfs