COMPLEX: A Closed-Form Certified Embedding of Multiparameter Persistence Modules

Sushovan Majhi; Atish Mitra; Žiga Virk; Pramita Bagchi

cs.LGSep 18, 2026

COMPLEX: A Closed-Form Certified Embedding of Multiparameter Persistence Modules

Authors: Sushovan Majhi, Atish Mitra, Žiga Virk, Pramita Bagchi

Organizations: Data Science, George Washington University, USA · Department of Mathematical Sciences, Montana Technological University, USA · Faculty of Computer and Information Science, University of Ljubljana, and Institute IMFM, Slovenia · Biostatistics and Bioinformatics, George Washington University, USA

Abstract

Every multiparameter persistence vectorization we know of carries a one-sided Lipschitz upper bound and nothing below it: without a lower gauge there is no sense in which the features are faithful, and no per-prediction guarantee can be built on them. This paper supplies the missing side. COMPLEX is a closed-form, training-free embedding of multiparameter modules -- slice the module along a fixed near-diagonal net, embed each slice barcode by the certified PLACE/PALACE landmark map, concatenate. Under a checkable witnessing-slice coherence condition, holding on 100% of audited pairs on Orbit5k, a single slice carries a closed-form lower gauge: separated modules stay separated in the embedding. With the standard upper bound this gives, to our knowledge, the first two-sided distortion bound for a multiparameter feature map, making faithfulness measurable. Measuring it, we find the floor tight within a small factor of realized distances yet operationally local: an RBF-SVM reaches 91% where 1-NN reaches 78% on the same features. Local per-prediction certification therefore fails for a structural reason common to every landmark embedding whose lower gauge is witnessed by one coordinate. With no learned embedding and no held-out calibration -- only a cross-validated SVM head -- COMPLEX sets the state of the art on both Orbit benchmarks (91.95% on Orbit5k, 92.98% on Orbit100k), level with or above Euler-characteristic surfaces and above transformers and graphcode. On graphs it exceeds GRIL on all four shared molecular benchmarks with one fixed configuration, including the only multiparameter method to clear COX2's majority baseline by more than three points. Closed-form selection -- of the landmark radius, the kernel (certificate-preserving), and the bifiltration set -- buys further accuracy; gradient-shaped adaptation buys none.

Figures & tables

	uncertified	certified (this paper)
training-free	mp-landscape/image, signed measures, ECS	COMPLEX
trained	Gril , D- Gril , graphcode, Persformer	D-COMPLEX

Table 1: The landscape of topological features computed from a multiparameter filtration (ECS reads the filtration but computes no persistence). Every prior method is uncertified; this paper supplies the certified version of both regimes.

$\ell_{\beta,u},\ s_{\beta,u},\ \omega$	slice, entry parameter, weight	$\nu=\{(p_{k},r_{k},w_{k})\}$	landmarks: points, radii, weights
$\mathcal{L}_{S},\ \vartheta_{s},\ \omega_{s}$	net, its angles and weights	$\varphi_{p,r},\ \Phi,\ \Psi$	hat coordinate, slice map, stack
$\mathcal{D}_{N},\ d_{\mathcal{B}},\ d_{\mathrm{mat}}^{S}$	diagrams, bottleneck, sliced matching	$K,\ S,\ N_{\max},\ \alpha$	landmarks/slice, slices, bar budget, radius factor
$\tau,\ t^{\star}=\tau/\omega_{s^{\star}}$	scale, its realized value on $s^{\star}$	$\lambda_{0},\ \mathcal{A}_{s}(\tau),\ w_{\min}$	func. Lebesgue number, active set, weight
$\rho_{-}(\tau)=\tfrac{1}{4}\tau w_{\min}$	certified floor	$B,\ B_{\infty}$	norm and coordinate bounds
$\widehat{\Delta},\ r_{m},\ \mathrm{gap}(M)$	centroid gap, radius, decision gap	$\varepsilon,\ d_{(1)},\ d_{(2)}$	nearest-neighbor distances
$\kappa,\ h,\ \kappa_{-},\ c_{D}$	kernel, bandwidth, ceiling, constant	$g_{\theta},\ \theta$	learned bifiltration, its parameters

Table 2: Notation.

One-parameter persistence
Method	Orbit5k	Orbit100k
SW kernel ∗	$83.6\pm 0.9$	–
Fisher kernel ∗	$85.9\pm 0.8$	–
PersLay ∗	$87.7\pm 1.0$	$89.2\pm 0.3$
xPerT (transformer) ∗	$87.0$	$91.1$
Persformer (transformer) ∗	$91.2\pm 0.8$	$\mathbf{92.0\pm 0.4}$

Table 3: Point-cloud accuracy (

\%

, mean

\pm

std over folds). COMPLEX’s embedding is closed-form and training-free (its SVM head is cross-validated); baselines are trained or tuned. Methods are grouped by family: the Euler-characteristic descriptors compute no persistence at all, and graphcode—GNN-trained,

70/30

split—is the only other multiparameter method reporting on these benchmarks. Bold

=

best in family. ∗ literature numbers, under each method’s own protocol. The COMPLEX RBF row uses the radius factor

\alpha=4

—PALACE’s published Orbit value, adopted unchanged (Remark 2.3 ; the sweep and the certified capped variant are priced in the text)—with, on Orbit5k, PALACE’s three-bifiltration recipe (DTM

k\in\{10,15,20\}

K=200

per block); the nearest-centroid row is at the

\alpha=1.75

default. † Orbit100k uses a Nyström feature map in place of the exact kernel (a

90\text{k}\times 90\text{k}

kernel is

{\sim}65

GB), provisioned at

4{,}000

components. Calibrated against the exact kernel on Orbit5k at

5

folds and the headline

\alpha=4

(nystrom_calib.py; exact head

91.58\pm 1.44

), the approximation reads

-0.48/-0.24/+0.04

points at

250/500/1{,}000

components and

+0.30/+0.36

2{,}000/4{,}000

, where it acts as a regularizer rather than an approximation (at

\alpha=1.75

the ladder is

-0.74/-0.04/+0.34/+0.52/+0.44

; the shape is the same). The row is

3

seeds

\times

3

folds, the protocol stated in the text; at the

10

-fold protocol used elsewhere in this paper the same configuration reads

93.10\pm 0.28

(seed

0

). At the

\alpha=1.75

default with

1{,}000

components the pipeline reads

92.28\pm 0.02

3

folds and

91.94\pm 0.35

10

Method	$p{=}0$	$0.05$	$0.1$	$0.2$	$0.3$	drop
COMPLEX	$\mathbf{90.9\pm 0.0}$	$\mathbf{83.8\pm 0.4}$	$\mathbf{80.7\pm 0.2}$	$72.5\pm 0.3$	$61.9\pm 0.2$	$-29.1$
ECS	$89.1\pm 0.2$	$83.4\pm 0.2$	$80.6\pm 0.3$	$\mathbf{72.7\pm 0.2}$	$\mathbf{62.4\pm 0.2}$	$\mathbf{-26.7}$
HT	$86.5\pm 0.1$	$76.8\pm 0.0$	$73.7\pm 0.2$	$65.0\pm 0.3$	$56.4\pm 0.2$	$-30.1$
ECC	$83.6\pm 0.1$	$72.3\pm 0.1$	$65.7\pm 0.3$	$55.6\pm 0.1$	$46.9\pm 0.3$	$-36.7$
PALACE-1p	$87.2\pm 0.1$	$78.1\pm 0.1$	$71.3\pm 0.3$	$61.4\pm 0.1$	$49.4\pm 0.3$	$-37.8$

Table 4: Outlier contamination on Orbit5k (accuracy

\%

, mean

\pm

std over

3

seeds,

5

-fold CV,

1{,}000

clouds per class). Each point is replaced by a uniform draw with probability

p

. Euler descriptors use a

40\times 40

surface and the better of XGB and RBF-SVM. drop is the accuracy lost from

p=0

p=0.3

; smaller magnitude is more robust. Bold

=

best in column.

Dataset	majority	geom.	$+$ label	multi	sel.	Gril ∗	mp-i ∗	mp-l ∗
		COMPLEX
MUTAG	$66.5$	$88.1\pm 1.1$	$\mathbf{89.7\pm 0.7}$	$88.5\pm 0.2$	$88.8\pm 0.4$	$87.8$	$85.6$	$85.7$
DHFR	$61.0$	$77.7\pm 0.8$	$80.6\pm 0.4$	$80.1\pm 0.5$	$\mathbf{81.8\pm 1.9}$	$77.6$	$80.2$	$79.5$
COX2	$78.2$	$78.0\pm 0.1$	$78.1\pm 0.2$	$\mathbf{81.7\pm 0.4}$	$81.5\pm 0.4$	$79.8$	$77.9$	$79.0$
PROTEINS	$59.6$	$69.5\pm 0.4$	$71.3\pm 0.5$	$\mathbf{72.2\pm 0.5}$	$70.9\pm 0.7$	$70.9$	$67.3$	$65.8$
NCI1	$50.1$	$69.5\pm 0.1$	$73.1\pm 0.2$	$74.4\pm 0.1$	$\mathbf{78.1\pm 0.2}$	–	–	–

Table 5: Graph accuracy (

\%

10

-fold CV; COMPLEX columns are mean

\pm

std over

3

seeds). “geom.”

=

HKS

\times

degree; “

+

label” adds the node-label axis; “multi” concatenates three bifiltrations (HKS

{}_{10}\times

degree, HKS

{}_{1}\times

closeness, HKS

{}_{10}\times

label) with the homology degrees kept separate—the per-degree form Theorem 2.6 requires—at matched total dimension, mean

\pm

std over

3

seeds. The multi column is one fixed configuration applied unchanged to every data set, not the best of several chosen per data set. Bold

=

best; ∗ literature, under each method’s own protocol and with a single bifiltration. “sel.” is SELECT-MULTI (Section 5 ): the top-

5

bifiltrations from the full

21

-pair bank, chosen per fold by inner cross-validation on the training fold only and concatenated—

k=5

fixed across data sets, same protocol and total budget as “multi”. “majority” is the constant-classifier rate. It matters most on COX2, where every previously published entry sits within

1.6

points of it and the single-bifiltration columns sit below it; the multi and selected configurations are the only entries in that row to clear it by more than

3

points.

Dataset	Gaussian	select	picks (of $30$ )
MUTAG	$\mathbf{86.9\pm 0.2}$	$86.2\pm 0.9$	rbf $15$ , Hellinger $9$ , $\chi^{2}$ $6$
COX2	$77.2\pm 0.6$	$\mathbf{78.6\pm 0.6}$	Hellinger $19$ , $\chi^{2}$ $9$
DHFR	$\mathbf{82.2\pm 0.6}$	$81.1\pm 0.5$	Hellinger $15$ , rbf $10$
PROTEINS	$73.3\pm 0.2$	$73.2\pm 0.5$	rbf $19$ , Hellinger $8$
NCI1	$76.3\pm 0.3$	$\mathbf{79.2\pm 0.2}$	$\chi^{2}$ $17$ , Hellinger $13$
PTC_MR	$52.0\pm 2.3$	$\mathbf{57.4\pm 0.2}$	$\chi^{2}$ $16$ , Hellinger $9$

Table 6: Kernel selection on the five-bifiltration stack (accuracy

\%

10

-fold CV, mean

\pm

std over

3

seeds). “Gaussian” fixes the RBF head; “select” chooses among Gaussian,

\chi^{2}

and Hellinger by inner CV on the training fold (

12

bandwidth

\times

C

candidates per kernel), which Remark 3.7 shows is certificate-preserving. “picks” counts the inner-CV winner over the

30

test folds. This pipeline differs from Table 5 (multi-big bank at

K=40

per block, no per-feature standardization), so only within-row comparisons are meaningful.

Net	$(S,a)$	nearest-centroid	RBF-SVM
percentile (axis-aligned)	$(4,-)$	$44.0$	$85.7$
near-diagonal fan	$(4,0.6)$	$72.6$	$90.9$
near-diagonal fan	$(8,0.6)$	$\mathbf{73.4}$	$\mathbf{91.2}$
near-diagonal fan	$(8,0.3)$	$68.6$	$90.7$
certified-adaptive ‡	$(4,0.7)$	$67.9$	$89.0$
certified-adaptive	$(8,0.7)$	$68.8$	$90.4$

Table 7: Slice-net ablation on Orbit5k (

10

-fold CV accuracy

\%

, mean over seeds). Only the net changes; embedding and classifier are fixed at the

\alpha=1.75

single-bifiltration default, so the absolute level sits below the headline configuration and only the ordering matters here. ‡ The adaptive rows use a non-degeneracy proxy for the certifiability filter of Proposition 2.13 , not the full

\rho_{-}\geq\rho_{0}

admissibility test.

Panel of Figure 1 — Figure 1: The two swept levers behind “The obstruction, stated” (Orbit5k, $K=200$ unless swept, cert_1nn.py). Left: the shortfall $\varepsilon/(\rho_{-}/2)$ of Corollary 3.3 ’s acceptance test against the landmark budget at $n=500$ —flat near $12\times$ at the $\alpha=1.75$ default, where $\varepsilon$ and $\rho_{-}$ both scale as $K^{-1/2}$ , and rising from $9\times$ to $25\times$ at the capped $\alpha=4$ headline; the dashed line is the certified regime. Right: the median nearest-training-neighbor distance $\varepsilon$ against training-set size, stationary over an eightfold range, with the acceptance threshold $\rho_{-}/2$ (equal for the two $\alpha$ to within $1\%$ ) $12$ – $25\times$ below it. The floor’s tightness and the $\ell^{\infty}$ reading are reported in the text.

Panel of Figure 2 — Figure 2: Certified selective classification (Orbit5k, near-diagonal fan $S=8$ ). Selective accuracy of the certified nearest-centroid head vs. coverage; dashed line is the uncertified RBF-SVM.

Data set	NC	Radius ( 15 )	Bernstein	Gaussian	BE
Orbit5k	$63.3$	$8.3$ ( $84.7$ )	$26.9$ ( $85.9$ )	$67.0$ ( $73.2$ )	$0.28$
MUTAG	$87.0$	$0$	$0$	$66.1$ ( $91.8$ )	$0.33$
PROTEINS	$58.5$	$31.6$ ( $66.6$ )	$9.5$ ( $90.3$ )	$84.1$ ( $61.0$ )	$0.26$
NCI1	$63.6$	$54.0$ ( $67.8$ )	$\mathbf{74.0}$ ( $66.4$ )	$88.7$ ( $65.2$ )	$0.10$
NCI109	$63.6$	$47.5$ ( $68.2$ )	$\mathbf{68.7}$ ( $67.1$ )	$85.8$ ( $65.3$ )	$0.09$
DD	$74.8$	$45.1$ ( $80.0$ )	$\mathbf{71.4}$ ( $79.2$ )	$92.0$ ( $76.4$ )	$0.13$

Table 8: The nearest-centroid certificate read per prediction (five seeds

\times

ten folds; pointwise_cert.py). Cells give the percentage of test points certified and, in parentheses, nearest-centroid accuracy on them; “NC” is that head’s accuracy over all test points. “Radius ( 15 )” is the gap test of Theorem 3.2 evaluated per point, which is valid on the concentration event whether or not the rule-level condition

r_{m}<\tfrac{1}{2}\widehat{\Delta}

holds; “Bernstein” and “Gaussian” are the two forms of Proposition B.1 ; “BE” is the Berry–Esseen charge subtracted from the Gaussian form’s confidence. Orbit5k is the capped single-bifiltration configuration at

\alpha=4

; the graph rows are the multi configuration of Table 5 . The five omitted benchmarks certify nothing under the radius and Bernstein columns.

		closed-form (Mahalanobis)		inner-CV
Dataset	fixed (HKS $\times$ deg)	selected	pair (folds)	selected	pair (folds)
COX2	$78.2\pm 1.6$	$\mathbf{80.1\pm 3.0}$	HKS ${}_{1}\times$ clus. ( $5/5$ )	$81.0\pm 3.8$	HKS ${}_{1}\times$ clos. ( $3/5$ )
MUTAG	$\mathbf{88.8\pm 1.0}$	$86.7\pm 4.0$	HKS ${}_{10}\times$ deg. ( $4/5$ )	$88.3\pm 2.7$	HKS ${}_{10}\times$ clos. ( $2/5$ )
DHFR	$\mathbf{76.9\pm 1.3}$	$75.9\pm 3.2$	HKS ${}_{1}\times$ clus. ( $2/5$ )	$75.6\pm 7.4$	(five pairs in five folds)

Table 9: SELECT-COMPLEX: selected vs. fixed bifiltration (

5

-fold CV accuracy

\%

, RBF-SVM), under two selection criteria. Both are train-only, so the certificate and the fold protocol hold for either. The closed-form criterion is the shrinkage-regularized Fisher/Mahalanobis margin ( 20 ); inner-CV is a

3

-fold cross-validated nearest-centroid accuracy on the training fold. Inner-CV is

0.7

points better on average but is a held-out search, so we report the closed-form criterion as the default and inner-CV as the variant. “pair (folds)” gives the modal choice and how many of the five folds agree on it—the closed-form criterion is markedly more stable. This experiment uses a lighter configuration than Table 5 (

5

folds,

K=120

landmarks,

S\leq 6

slices), so only the within-row comparison is meaningful.

Dataset	selected $-$ fixed	learned $-$ fixed
COX2	$+1.9$	$+0.8$
MUTAG	$-2.1$	$-2.0$
DHFR	$-1.0$	$-2.0$
NCI1	–	$+3.4$
PROTEINS	–	$+1.0$

Table 10: Adapting the filtration: gain over the fixed HKS

\times

degree bifiltration (accuracy points, mean over

3

seeds, fixed net). Neither route is reliable: closed-form selection helps on COX2 and hurts on MUTAG and DHFR; gradient learning helps on three of five sets and hurts on two. The selector column is the fold-matched difference of Table 9 under the closed-form criterion and is reported only where that experiment was run.

Topological Representation Learning

Topological representation learning uses connectivity, holes, and higher-order structure to build or analyze machine-learning features.

See all 67 papers

May 4, 2026

A Closed-Form Persistence-Landmark Pipeline for Certified Point-Cloud and Graph Classification

We introduce PLACE (Persistence-Landmark Analytic Classification Engine), a closed-form pipeline for classifying point clouds and graphs through their persistent-homology signatures. Three quantitative guarantees -- a margin-based excess-risk rate, a closed-form descriptor-selection rule, and a per-prediction certificate -- are derived from training labels alone, with no learned weights or held-out calibration. The embedding sums Mitra-Virk single-point coordinate functions over a sparse landmark grid; the closed-form weight rule

w_k^2 \propto (d_{k+1}^2 - d_k^2)/R_k^2

maximizes the distortion slope in Mitra-Virk's affine certificate under

ν

-coherence. (i) An

O(kR/(Δ\sqrt{m_{\min}}))

margin bound, driven by class-mean separation

Δ

and embedding radius

R

, matched in the sample-starved regime

m \lesssim R/Δ

by a Le Cam minimax lower bound. (ii) The Mahalanobis margin under Ledoit-Wolf-shrunk covariance is the strongest closed-form ranker on a 64-descriptor chemical-graph pool (mean Spearman

ρ= +0.56

across 11 benchmarks, positive on 10 of 11); the isotropic surrogate

Δ/\sqrt{\ell}

admits a closed-form selection-consistency rate on the homogeneous protein/social pools. (iii) A training-time-decided certificate, with no per-prediction overhead, in three concrete radii (Pinelis, Gaussian plug-in, and variance-aware Pinelis-Bernstein). Empirically, PLACE is the strongest diagram-based method on Orbit5k and matches the strongest topology-based baseline within statistical noise on MUTAG and COX2; remaining gaps fall into two diagnosable regimes (descriptor blindness on NCI1/NCI109; pool-coverage limits elsewhere). The Pinelis-Bernstein radius fires on 8 of the 12 benchmarks; on MUTAG the empirical and population nearest-centroid rules agree on every one of 940 held-out test predictions, validating the certificate's mechanism.

Sushovan Majhi, Atish Mitra, Žiga Virk +1

Data Science, George Washington University, USA · Department of Mathematical Sciences, Montana Technological University, USA · Faculty of Computer and Information Science, University of Ljubljana, Institute IMFM, Slovenia +1

Point Cloud Classification Classification Graph Classification Persistent Homology Statistical Learning Theory

Ask PDF

Aug 2, 2026

How fine a change can moments see? A scale law for detecting distribution shift, with a kernel calibration rule

Detecting that a stream of high-dimensional embeddings has changed is usually framed as a choice of statistic. We give a scale law that constrains any moment-based choice and test it against topological alternatives. The law: certifying a feature of spatial scale eps carrying mass fraction f requires polynomial tests of degree N* >= log(1/f)/(2 eps), proved via the Chebyshev extremal problem; a Gauss-quadrature construction gives N* >= 4b-1 for a b-scale topology, so cost is set by feature fineness, not feature count. The law is one-sided: we exhibit an annulus whose mean, covariance and all fourth-order moments equal those of a filled disk, yet H_1 is nonzero. Its practical content is a calibration rule. The upper bound is attained by Gaussian test functions, the RKHS witness of an RBF kernel, so the law predicts which bandwidth an MMD test should use: the feature scale. On real embedding streams we measure sigma*/eps with median 1.12 (IQR 1.01-1.52, n=26) over three settings and three scales, and a data-driven bandwidth reaches AUC >= 0.95. Against an adversary optimised against the defender's statistics (mean, covariance, k-NN, kurtosis), only a bandwidth-matched kernel test still detects. For persistent homology the verdict is mixed and depends on choices usually left implicit. The summary matters more than the filtration: total persistence attains recall 0.75 at FPR 1% where the first persistence landscape attains 0.00. What survives is a cost gap, not a power gap: where persistence works it costs 116x kurtosis, which works at least as well. We conclude not that topological summaries are useless, but that on this task a kernel test whose bandwidth the law sets dominates them.

Adel Kaleche

Independent researcher, France

Two-Sample Testing Distribution Shift Maximum Mean Discrepancy Distribution Shift Detection

Ask PDF

Oct 13, 2026

Persistence Positional Encoding: A Minimal Transformer Recipe for Persistence Diagrams

Persistence diagrams (PDs) represent multiscale topological information as multisets of birth-death pairs

(b,d)

. How best to use them with Transformers, however, remains unclear. Connecting PDs to Transformers requires choosing how topological information is tokenized and exposed to self-attention. Prior methods use specialized designs for tokenization, aggregation, Transformer blocks, or attention, but are hard to compare since reported results rarely share PD inputs, splits, or model-selection rules. We instead confine the diagram-specific design to point representation, mapping each birth-death pair through fixed random Fourier features while leaving the Transformer backbone unchanged, and call this recipe Persistence Positional Encoding (PPE). In matched controls on eight TU graph benchmarks (TU8), changing only point representation shifts macro accuracy by 5.49 to 6.47 percentage points (pp), against 0.47 to 1.45 pp from changing the downstream module, identifying point representation as the dominant design variable tested. We further reevaluate vectorizations, kernels, learned representations, and Transformer-based models under one protocol with shared PD inputs, outer folds, and validation-only selection. Among all evaluated PD methods and downstream configurations, PPE achieves the highest mean on most benchmarks, including TU8, ORBIT5K, and MCB-C. Finally, we prove that grid averaging leaves a reconstruction error at any resolution, whereas a Transformer with fixed random Fourier frequencies is almost surely universal. PPE thus offers a minimal, Transformer-native baseline for persistence diagrams, and a common protocol for future comparison.

Eunwoo Heo, Ganghyun Kim, Jaejun Yoo

Graduate School of Artificial Intelligence, Ulsan National Institute of Science and Technology

Topological Representation Learning Persistent Homology Graph Classification Transformer

Ask PDF

Abstract

Topological Representation Learning

Explore similar work

A Closed-Form Persistence-Landmark Pipeline for Certified Point-Cloud and Graph Classification

How fine a change can moments see? A scale law for detecting distribution shift, with a kernel calibration rule

Persistence Positional Encoding: A Minimal Transformer Recipe for Persistence Diagrams