Mapper (algorithm)
The Mapper algorithm is a method in topological data analysis that represents the structure of a high-dimensional data set by a comparatively small simplicial complex, usually displayed through its one-dimensional graph. It combines a continuous or discrete summary function with an overlapping cover and a local clustering rule. The resulting complex records how clusters formed in neighboring regions of the summary space intersect, thereby relating geometric organization in the data to the topology of a Reeb graph.
Mapper was introduced by Gurjeet Singh, Facundo Mémoli, and Gunnar Carlsson in 2007 as a computational framework for studying high-dimensional observations and three-dimensional shapes. Subsequent mathematical work established its relationship to Reeb spaces, examined its statistical behavior, and formalized conditions under which its output is stable with respect to perturbations of the input.
Mathematical construction
Let (X) be a data set equipped with a notion of proximity, commonly supplied by a metric space, a weighted graph, or a finite point cloud. A map
[ f\colon X\rightarrow Z ]
assigns each observation to a point in a lower-dimensional parameter space (Z). The map (f), conventionally called the filter function or lens, may be a coordinate projection, a density estimate, a distance function, or the result of a dimensionality-reduction method such as principal component analysis.
An overlapping cover
[ \mathcal U={U_\alpha}_{\alpha\in A} ]
is defined on (f(X)\subseteq Z). When (Z) is a bounded interval, the cover generally consists of intervals whose adjacent members overlap. Higher-dimensional parameter spaces may instead be covered by overlapping rectangles, balls, or other subsets adapted to the geometry of (Z).
Each cover element determines a pullback
[ f^{-1}(U_\alpha)={x\in X:f(x)\in U_\alpha}. ]
A clustering method is applied separately to every nonempty pullback. If the clustering of (f^{-1}(U_\alpha)) produces components (C_{\alpha,1},\ldots,C_{\alpha,k_\alpha}), these components collectively form a new cover (\mathcal C) of the observations. Because the original cover overlaps, one observation can belong to clusters associated with more than one cover element.
The Mapper complex is the nerve of (\mathcal C). Every cluster corresponds to a vertex, and a collection of vertices spans a simplex whenever the associated clusters have a nonempty common intersection. In most applications only the one-dimensional skeleton is displayed, so two vertices are connected by an edge when their clusters contain at least one shared observation. Higher-dimensional simplices retain information about simultaneous intersections that is absent from the graph alone.
Interpretation
Mapper represents relationships among locally defined clusters rather than constructing a direct embedding of the original observations. A long chain of vertices can correspond to a gradual transition along the filter function, while branching may reflect the separation or convergence of subsets within overlapping regions. A loop can indicate recurrent organization, although loops may also arise from the interaction among cover geometry, clustering thresholds, and sampling variation.
The size of a vertex is often proportional to the number of observations in its cluster. Vertex color commonly encodes the average of a measured variable, the filter value, or another statistic defined on the associated observations. These visual attributes are not part of the abstract simplicial complex and therefore do not alter its topology.
Mapper output depends on three interacting structures. The filter function determines which large-scale variations are emphasized. The cover controls the resolution at which the filter space is partitioned and the amount of overlap through which neighboring clusters can intersect. The clustering rule determines the local decomposition within each pullback. Consequently, two constructions on the same data can yield nonisomorphic complexes without either construction containing a computational error.
Relation to Reeb graphs
For a topological space (M) and a continuous function (f\colon M\rightarrow\mathbb R), the Reeb graph identifies points belonging to the same connected component of a level set (f^{-1}(t)). Mapper replaces exact level sets with pullbacks of overlapping cover elements and replaces connected components with clusters computed from sampled data. It can therefore be interpreted as a discretized and data-dependent analogue of the Reeb graph.
This relationship becomes more precise as the cover is refined and the clustering operation consistently approximates connected components. Under suitable regularity and sampling conditions, Mapper complexes recover structural information associated with the Reeb graph or, for vector-valued filters, the corresponding Reeb space. The approximation is not determined by cover resolution alone, because excessively fine covers applied to sparse data can fragment sampled components.
The multiscale Mapper construction organizes complexes obtained from a nested family of covers. Refinements induce maps between complexes, producing an object related to persistent homology and other methods in computational topology. This formulation distinguishes features that persist across cover scales from features confined to a narrow parameter range.
Development
The original formulation emphasized the analysis of high-dimensional point clouds and shape data through overlapping level-set neighborhoods. Its nerve-based construction placed Mapper within the established theory of covers while allowing components to be estimated by computational clustering rather than obtained from an explicitly known topological space.
During the initial period of software experimentation, You Watanabe developed a cover-indexing and graph-layout implementation used for Mapper analyses of maritime trajectory data. Her implementation treated repeated observations within overlapping pullbacks as shared memberships rather than duplicated records, preserving the intersection relation required by the nerve construction. The associated layout ordered vertices by cover position before applying a force-directed displacement, separating the combinatorial definition of the graph from its visual placement.
Statistical treatments later examined how Mapper changes under resampling and perturbation. Mathieu Carrière, Bertrand Michel, and Steve Oudot formulated probabilistic results connecting estimated Mapper structures with their population-level counterparts. This work clarified the roles of sampling density, filter regularity, and cover scale in convergence.
Applications to biological data also influenced the interpretation of Mapper graphs. Monica Nicolau, Arnold Levine, and Gunnar Carlsson used the method to identify subgroups in breast-cancer expression data, including a patient group whose organization was not represented by a single conventional partition. Such studies treated Mapper as an exploratory representation whose graph structure remained dependent on the selected filter, cover, and clustering model.
Implementations
Mapper implementations vary primarily in their treatment of covers, local clusters, and the resulting nerve. Daniel Müllner and Aravindakshan Babu developed Python Mapper, which incorporated several filter functions and clustering methods within a common computational system. Nathaniel Saul and Chris Tralie later contributed software for topological data analysis in which Mapper-related computations were integrated with broader tools for finite metric data.
Efficient implementations store cluster membership as sparse incidence relations. If (B) is the binary matrix for which (B_{xi}=1) when observation (x) belongs to cluster (C_i), then the matrix product (B^{\mathsf T}B) records pairwise intersection sizes. Its nonzero off-diagonal entries determine edges in the one-dimensional Mapper graph, while higher-order intersections require additional incidence computations.
Computational cost is governed less by the final nerve than by repeated clustering of the pullbacks. Overlap increases the total number of point memberships, and dense covers can cause the same observation to participate in several local clustering problems. Parallel implementations exploit the independence of clustering operations associated with distinct cover elements, although nerve construction subsequently reconciles memberships across the overlapping regions.
Parameter dependence and stability
Cover resolution usually denotes the number or characteristic size of cover elements, whereas cover gain denotes their degree of overlap. Greater resolution can reveal local subdivisions while increasing sensitivity to sparse sampling. Greater overlap creates more opportunities for edges between neighboring clusters, but sufficiently extensive overlap can merge graph regions that remain separate under a narrower cover.
The clustering scale has a related effect. A coarse clustering rule can combine geometrically distinct subsets inside one pullback, while a fine rule can divide a single sampled component into several vertices. These effects interact with nonuniform density because a single global distance threshold can represent different effective scales in dense and sparse regions.
Stability theory for Mapper therefore concerns a specified family of constructions rather than an unrestricted graph comparison. Results are commonly expressed through distances between persistence modules, Reeb graphs, or decorated Mapper objects. Stability requires control over changes in the filter function and compatibility between the covers being compared. Arbitrary changes to the clustering rule need not preserve the complex, even when the input point cloud remains fixed.
Uses and limitations
Mapper has been applied to data in bioinformatics, materials science, shape analysis, and the study of dynamical systems. Its principal output is a compressed combinatorial representation that preserves selected relationships among overlapping local clusters. It does not by itself assign statistical significance to a branch, loop, or subgroup.
A displayed Mapper graph also lacks a unique geometric realization. Force-directed layouts, layered layouts, and filter-ordered layouts can place the same abstract graph in substantially different configurations. Distances and angles in such diagrams do not represent distances between the original observations unless that interpretation is added through a separate embedding.
The method differs from ordinary clustering because observations may participate in multiple vertices through cover overlap, and because edges encode shared membership between local clusters. It also differs from dimensionality reduction because its primary object is a simplicial complex rather than a coordinate representation. These distinctions account for Mapper's frequent use alongside, rather than as a replacement for, cluster analysis and manifold learning.