Mapper is a popular tool for summarizing the shape of a dataset as a small graph: project the data onto one or two "lens" values, cover the projected range with overlapping bins, cluster the points inside each bin, and connect clusters that share points. Its output is notoriously sensitive to its settings. Changing the number of bins, how much they overlap, or the clustering threshold can split one loop into two, erase a branch, or break the graph into pieces. Practitioners respond by sweeping a grid of settings and eyeballing which result looks stable. We propose replacing that eyeballing with a proof. For a whole box of parameter settings, the method certifies that the Mapper graph's topology stays the same across every setting in the box: its number of connected components, its number of independent loops, and its set of long branches. The core observation is that Mapper, like a ReLU network, is piecewise constant. Its output changes only when a data point crosses a bin edge or when a pairwise distance crosses the clustering threshold. This lets us reuse the machinery that made neural network verification scale.
The transfer is close to literal. A neural network verifier asks whether every input in a region satisfies a property. The hard part is the "unstable" neurons, whose on/off state is not fixed over the region. The standard fix is to bound cheaply, find the few undecided units, and split only on those (Evaluating Robustness of Neural Networks with Mixed Integer Programming). Here the region is a box of hyperparameters, and the undecided units are point-to-bin memberships and within-bin cluster links whose state flips somewhere inside the box. The property is not "the graph is identical" but "the graph's coarse topology is unchanged." Many flips do not affect that coarse topology, so the verifier can certify large regions without ever enumerating every distinct graph.
Core Claim
Over a hyperparameter box of lens bandwidth, bin overlap (gain) and clustering threshold, with the integer number of bins (resolution) enumerated, a branch-and-bound procedure can do two things. It can partition the box into regions certified to have constant Betti numbers and constant long-branch structure, plus a residual set of provably unstable regions. It can do this much faster than exact enumeration of all combinatorially distinct Mapper graphs once two or more parameters vary jointly. We further claim that choosing parameters from the largest certified plateau recovers known structure as well as or better than published hand-tuned or statistically selected choices.
This is a different object from existing guarantees for Mapper. Statistical Analysis and Parameter Selection for Mapper proves that Mapper consistently estimates the underlying Reeb graph (the "skeleton" of a function on a space). It also gives bootstrap confidence bands that separate real loops and branches from sampling noise. Its parameter guidance is asymptotic, and it offers no deterministic statement about neighboring parameter values on the observed data. Deconstructing the Mapper algorithm shows empirically that resolution and gain are tightly coupled, with high resolution but low gain shattering the graph. That finding motivates our proposal: the fragile directions in parameter space are joint, not axis-by-axis, so one-dimensional sweeps can mislead.
Research Program
The first component is a sound bounding step. On a parameter sub-box, each bin endpoint is a closed-form rational function of gain and lens range, so interval arithmetic gives the range of every point's signed distance to every bin edge. A membership is "decided" if that sign is fixed. The same holds for single-linkage cluster links: a link is decided unless the pairwise distance lies inside the threshold interval. If the lens itself depends on a parameter, for example a distance-to-measure lens with mass parameter $m_0$, lens values also become intervals.
From decided memberships and links we build two graphs. The "must" structure contains only decided items. The "may" structure adds every undecided item. The topological invariant is certified constant on the box when every undecided item is provably irrelevant to it. The simplest such case is an undecided link between two points already joined by decided links. Another is an undecided membership whose resolution cannot change a nerve edge. When the undecided set is small, we resolve it exactly by enumeration, which plays the role of the exact final solve in Tjeng et al..
The second component is branching. We never split at box midpoints. Instead we split at the exact parameter value where some undecided item flips, which is computable in closed form. Every leaf is therefore either certified or a genuine change point, which makes the procedure complete. Which item to split on is chosen by an influence score in the spirit of the indirect-effect scoring in DEEPSPLIT. That work ranks a neuron split by how much it tightens bounds on all downstream layers, and its authors report that dropping this indirect term inflates the search tree from 8,643 to 174,040 branches on an MNIST benchmark. Our analogue scores a flip event by how many other undecided items it resolves and whether it touches a cluster that bridges two otherwise separate parts of the may-graph.
The third component is the output and selection rule. The output is a certified map of parameter space showing plateaus, their certified invariants, and thin unstable seams between them. The selection rule picks the largest plateau, measured in normalized parameter volume, whose invariant contains the most long branches. Branch length uses the extended-persistence criterion of Carrière et al., so our certificates speak the same language as their bootstrap bands.
We deliberately do not pursue two other routes. The first is verifying networks that ingest Persistence Spheres. Because that paper shows its vectorization is a weighted sum of ReLUs, such networks already fall into existing verifiers with no new mechanism needed. The second is topology-guided branching for ReLU verifiers, where the file offers no evidence that activation-graph homology predicts good splits.
Baselines
The naive reference point is dense grid search. We evaluate Mapper at a regular lattice over the same box and declare a setting stable if its lattice neighbors share its invariant. It gets the same wall-clock budget as our verifier, with grid density raised until the budget is spent. Beating it means our method finds unstable seams the grid misses, reported as the fraction of grid-declared "stable" points that actually lie within one flip of an invariant change. It must also do so at equal or lower cost. Carrière et al. already argue that this brute-force approach lacks guarantees and cannot tell real features from discretization artifacts. We quantify that failure rather than assume it.
The strongest complete competitor is exact event enumeration. It computes every flip value, forms the full arrangement of cells in parameter space, recomputes Mapper once per cell, and merges cells with equal invariants. It gives the same guarantee as our method, so the comparison is purely about cost: cells visited and wall time on identical data and identical invariants. Beating it means an order-of-magnitude reduction in Mapper evaluations once at least two continuous parameters vary. With gain alone, we expect enumeration to be competitive and will report that honestly.
The strongest existing statistical method is the bottleneck bootstrap of Carrière et al.. On Miller-Reaven it assigns "an 85% certainty to the 'flares' representing distinct clinical progressions." We run it at their parameters and at our plateau-selected parameters. The target is not to beat 85% on the same quantity, because the two guarantees differ. The target is to show that our selected plateau contains their chosen setting and certifies the same flares, or else to document where their setting sits near a seam.
Two ablations isolate the key ingredients. The first replaces flip-point splitting with midpoint bisection, which loses completeness and should increase the number of boxes. The second replaces the influence score with uniform choice of the undecided item, mirroring the DEEPSPLIT ablation.
Why not just…?
Why not just use a dense grid search? A grid of finite resolution cannot rule out a thin cell between two lattice points where the graph shatters. The coupling found by Haşegan et al. suggests such cells lie along diagonal directions that axis-aligned grids sample poorly. Our seam-miss-rate experiment tests this directly. If grids at feasible density rarely miss seams on real data, the method's value shrinks to "a certificate" rather than "better choices," and we will say so.
Why not just rely on stability theorems or persistence vineyards? For filtrations like Vietoris–Rips or distance-to-measure, classical stability already bounds how much a persistence diagram moves when the filtration function moves. In that setting, interval bounds on $m_0$ would be trivial and we would not need our machinery. Mapper is different because clustering and cover membership are discrete, so no such Lipschitz bound exists. Vineyards track changes along a single one-parameter path, not across a multi-dimensional box.
Why not just enumerate all flip events exactly? This is the real threat. In one continuous parameter, the flip events number $O(nr)$ for $n$ points and $r$ bins, and enumeration is cheap. Our bet is that cell counts explode combinatorially with two or three joint parameters, while the property-directed search avoids cells whose differences do not affect Betti numbers. The scaling experiment below settles this. If the gap stays small, the contribution reduces to the certified-plateau selection rule on top of enumeration.
Why not just bootstrap? The bootstrap answers a different question, namely what happens if the data were resampled. It does not tell us whether a nearby parameter choice on the same data gives a different picture. The two are complementary, and we report them side by side.
Proposed Experiments
On the SPHERES synthetic data from Topological Autoencoders, and on simple synthetic shapes with known Reeb graphs, we check correctness. Every certified plateau must carry the true invariant, or a documented discretization of it. We also measure the fraction of the box certified, with and without the ablations.
On Miller-Reaven, we compare against the bootstrap as described above.
On simulated BOLD signals and the CMP fMRI data from Haşegan et al., we test downstream value. Their optimized choices give an average transition-detection delay of 5.7 seconds, against up to 42 seconds for correlation distance. We ask whether plateau-selected parameters, found without looking at transition labels, match or beat 5.7 seconds. We also ask whether their optimized setting lies inside a certified plateau or on a seam.
The decisive scaling experiment varies the number of jointly free continuous parameters from one to three and sample size from hundreds to tens of thousands. It plots Mapper evaluations and wall time for our verifier against exact enumeration. The central claim fails if the ratio does not grow with dimension.
References
- Evaluating Robustness of Neural Networks with Mixed Integer Programming
- Statistical Analysis and Parameter Selection for Mapper
- Deconstructing the Mapper algorithm to extract richer topological and temporal features from functional neuroimaging data
- DEEPSPLIT: An Efficient Splitting Method for Neural Network Verification via Indirect Effect Analysis
- PERSISTENCE SPHERES: BI-CONTINUOUS REPRESENTATIONS OF PERSISTENCE DIAGRAMS.
- Topological Autoencoders