Why Every Multiparameter Persistence Feature Map Lies About Its Geometry

Topological data analysis extracts shape from data: clusters, loops, voids, and their higher-dimensional analogs. The standard tool is persistent homology, which tracks how topological features appear and disappear across a filtration parameter. For a single parameter (say, scale), the output is a barcode, and a growing family of methods turns that barcode into a feature vector for downstream classification. These methods all share one property that nobody talks about: they are one-sided Lipschitz. That is, if two barcodes are close in bottleneck distance, their feature vectors are close in Euclidean space. But the converse is never guaranteed. If two feature vectors are far apart, you cannot conclude the underlying barcodes are far apart. There is no lower bound on distortion, no certificate that the embedding is faithful, and no way to attach a per-prediction stability guarantee to any downstream decision.

This is not a theoretical curiosity. In multiparameter persistence, where the filtration depends on two or more parameters simultaneously (say, scale and density), the problem is worse. No complete discrete invariant exists for modules over R^d when d >= 2. The fibered barcode, which records one-parameter barcodes along every line through the parameter space, is already a lossy summary. Every vectorization built on top of it, from persistence landscapes to signed measures to the Gril learned landscape, compounds an unavoidable loss on top of an avoidable one, with no lower bound to catch the damage. The result is that practitioners train classifiers on these features and hope the geometry is preserved. Nobody can check.

The COMPLEX paper, by Majhi, Mitra, Virk, and Bagchi, fixes this. It supplies the missing lower bound for multiparameter persistence features, making faithfulness measurable for the first time. The construction is closed-form and training-free, and it sets state-of-the-art accuracy on both Orbit benchmarks without learning any embedding at all.

How the Slice-Stack Works

The construction is built on top of PLACE and PALACE, which already solve the single-parameter case. Given a one-parameter persistence diagram, PLACE embeds it as a vector of landmark coordinates: place K landmark points in the diagram space, and for each landmark, compute how many diagram points fall within a ball of fixed radius around it. This produces a K-dimensional vector. PALACE makes this data-adaptive by placing landmarks via farthest-point sampling (class-aware) and setting radius caps so diagonal points contribute nothing. The result is a closed-form embedding with a certified lower distortion bound, rho_-, derived from labels alone with no tuning.

COMPLEX lifts this to multiparameter modules through a slice-stack. A multiparameter persistence module over R^d can be restricted to any line of positive slope, yielding a one-parameter barcode. The full module is summarized by its behavior along a finite net of such lines, called slices. COMPLEX fixes a near-diagonal fan of S slices, applies the PALACE landmark map to each slice's barcode independently, weights each block by the slice's reparametrization weight, and concatenates. The result is an S-by-K dimensional vector (typically 1,600 dimensions with S=8 slices and K=200 landmarks per slice). Everything is closed-form: the net is fixed, the landmarks are placed by farthest-point sampling, and each block is a finite sum of hat coordinates.

The key theoretical contribution is a two-sided distortion bound for this embedding. The upper bound is straightforward: the slice-stack is 1-Lipschitz up to a factor of sqrt(S) times the bar budget N_max, so nearby modules produce nearby feature vectors. The lower bound is new and depends on a condition called witnessing-slice coherence. Under this condition, which the authors verify holds on 100% of audited cross-class pairs on Orbit5k at the headline configuration, a single witnessing slice carries a closed-form lower gauge: if two modules are separated in the sliced matching distance by at least tau, their embedded vectors are separated by at least rho_-(tau) = tau times w_min divided by 4, where w_min is the minimum slice weight. Separated modules stay separated in the embedding. With both bounds, this is the first two-sided distortion guarantee for any multiparameter persistence feature map.

Certified Prediction: What the Guarantee Can and Cannot Do

The lower bound enables per-prediction certification. A nearest-centroid classifier returns a label along with a decision gap: the difference between the centroid distance to the assigned class and the nearest competing class. If this gap exceeds the certified floor, the prediction is stable under module perturbations up to a computed radius. A nearest-neighbor classifier does better: it returns, with each accepted label, a stability radius in the module metric itself. The ratio B/rho_- (where B is the embedding norm bound) controls a generalization bound for the robust rule, though it is numerically vacuous in practice.

The catch is that certification and accuracy pull in different directions. On Orbit5k, the certified nearest-centroid rule reaches only 73.4% accuracy, while an RBF-SVM on the same features reaches 91.2%. The certified 1-NN rule accepts under 1.5% of test modules at the budgets that maximize accuracy. The mechanism is structural: on the same embedding, the median ratio of runner-up to nearest neighbor distance is only 1.10 at K=200 landmarks, meaning the runner-up class is just 10% farther away. Only 2.8% of test modules have a runner-up even 1.5x behind. The discriminative information is global, carried by the kernel's nonlinear decision surface, while rho_- certifies a local separation in classes interleaved at neighbor scale.

This is not specific to persistence. It applies to any landmark embedding whose lower gauge is witnessed by one coordinate. The SVM head is a high-gain map of the embedding, with Lipschitz constants running from 300 to 15,000. A guarantee attached to the fitted decision function is vacuous because the function itself amplifies small embedding differences into large margin changes. The accurate head, if one exists, is not a Lipschitz one. Five local repairs attempted by the authors all fail at the same wall.

State-of-the-Art Accuracy Without Learning

The experimental results are striking given the method's simplicity. On Orbit5k (5,000 point clouds, 5 classes), COMPLEX with an RBF-SVM head reaches 91.95% accuracy with no learned embedding and no held-out calibration. This is level with or above Euler-characteristic surfaces (91.8% in the literature, 89.5% when re-run with a matched bifiltration), transformers (Persformer at 91.2%), and the GNN-trained graphcode (88.5%). On Orbit100k (100,000 point clouds), COMPLEX reaches 92.98%, above graphcode's previous 92.3% and Persformer's 92.0%.

On molecular graphs, the comparison is with Gril, the leading multiparameter persistence method. With one fixed configuration, COMPLEX exceeds Gril on all four shared benchmarks:

  • MUTAG: 89.7% vs. 87.8% (+1.9 points)
  • DHFR: 80.1% vs. 77.6% (+2.5 points)
  • COX2: 81.7% vs. 79.8% (+1.9 points)
  • PROTEINS: 72.2% vs. 70.9% (+1.3 points)

COX2 is the most notable result. Every previously published entry on this dataset sits within 1.6 points of the majority baseline at 78.2%. COMPLEX's multi-bifiltration configuration is the only multiparameter method to clear it by more than three points, at 81.7%.

On IMDB-Binary, a graph classification benchmark, COMPLEX reaches 70.0% versus D-Gril's 62.6%, a 7.4-point margin on equal footing. The full Orbit5k experiment runs in 6.8 minutes on 16 CPU cores with no GPU. One Orbit100k fold takes 166 minutes, with most of that in the Nyström kernel head at 4,000 components.

Closed-Form Selection Beats Gradient Adaptation

The paper tests whether learning helps. SELECT-MULTI selects the bifiltration set from a closed-form bank of 21 pairs, gaining up to 5.4 points on PTC_MR and 2.9 on NCI1. D-COMPLEX makes the slice-stack differentiable and learns the bifiltration by gradient. The result: gradient-shaped adaptation buys nothing. On five molecular datasets, learned filtrations improve on three but hurt on two, with no reliable advantage over the fixed default. The certificate survives gradient training (coherence holds on 100% of audited pairs after learning), but the improvement is in scale, not in guarantee quality.

Kernel selection is where closed-form selection pays off. Swapping the Gaussian kernel for chi-squared or Hellinger (both certificate-preserving) gains 5.4 points on PTC_MR, 2.9 on NCI1, and 1.4 on COX2, while costing about 1 point on MUTAG and DHFR. The choice is per-dataset and made by cross-validation, not by gradient optimization.

The slice net itself is best fixed. Near-diagonal fan slices decisively beat axis-aligned percentile slices (91.2% vs. 85.7% on Orbit5k). Data-adaptive nets, whether certified-adaptive or gradient-trained, fall at or below the fixed fan. Offset slices (adding base-point variation) also sit at or below the origin fan in every configuration tested.

Outlier Robustness and the Tightness of the Floor

Under outlier contamination, COMPLEX degrades gracefully but not uniquely. At 30% label noise, COMPLEX drops 29.1 points from clean accuracy, while Euler-characteristic surfaces drop 26.7 points. Against matched single-parameter methods (PALACE-1p, Euler-characteristic curves, persistence images), the second parameter grows the margin from 3.7 points on clean data to 12.4 points at 30% contamination. The second parameter buys robustness specifically against label corruption.

The lower bound is tight within a small factor of realized distances. At the headline configuration (alpha=4, S=8, K=200), the median embedded cross-class distance is 0.227, which is 10.5 times rho_-. The minimum embedded cross-class distance is 0.095, which is 4.4 times rho_-. At the default radius (alpha=1.75), the ratios shrink to 6.2x and 2.5x respectively. The floor is not vacuous; it tracks realized geometry within a small constant factor. The gap to the within-class radius (27 times rho_- at headline) is where the certification fails: the class structure is interleaved at a scale the local certificate cannot reach, but the kernel can.

What This Means for Practice

If you work with multiparameter persistence features, COMPLEX provides three things. First, a way to measure whether your feature map is faithful: the two-sided bound gives you a concrete number (rho_-) for how much separation in the module metric is preserved in the embedding. Second, a training-free baseline that is competitive with or better than learned methods on standard benchmarks. Third, a certified per-prediction rule (nearest-neighbor with a stability radius) that, while conservative, gives you a deterministic, split-free guarantee with no calibration set required.

The limitation is real: the certified rule is much less accurate than the uncertified kernel head, and no local repair closes the gap. The discriminative power lives in the global kernel decision surface, not in local coordinate separations. This is a structural fact about landmark embeddings, not a deficiency of COMPLEX specifically. Any future method that wants to certify multiparameter persistence predictions must either find a way to certify the kernel or accept that certification and accuracy occupy different operating points on the same curve.

For researchers, the witnessing-slice coherence condition provides a checkable criterion for when the lower bound applies. On Orbit5k, it holds on 100% of audited pairs at the headline configuration. At the default radius, it holds on 97.5% to 98% of pairs, with the failures coming from sum-pooling blind spots that are expected and non-fatal. The condition has a matching-free sufficient proposition (Proposition 2.11) that makes verification practical.

COMPLEX is released as a single fixed configuration that works across point clouds and graphs without per-dataset tuning. The closed-form selection of landmarks, radius, kernel, and bifiltration set buys further accuracy when you do tune. Gradient-shaped adaptation does not. This is a method where the math tells you what to do and the experiments confirm it: fix the net, place the landmarks by farthest-point sampling, set the radius cap, and let the certified geometry speak for itself.