A Closed-Form Adaptive-Landmark Kernel for Certified Point-Cloud and Graph Classification
Not on the map. Why?
Abstract (arXiv)
We introduce PALACE (Persistence Adaptive-Landmark Analytic Classification Engine), the data-adaptive companion to PLACE, paying a small cross-validation tier on three knobs (budget, radii, bandwidth; ≤ 5 choices each). A cover-theoretic core (Lebesgue-number criterion on the landmark cover) yields four closed-form guarantees. (i) A structural lower distortion bound λ(τ;nu) on Dn under cross-diagram non-interference, with a (D/L)2 budget reduction over the uniform grid when diagrams concentrate. (ii) Equal weights wk = K-1/2 maximizing λ, and farthest-point-sampling positions 2-approximating the optimal k-center covering radius; both derived from training labels alone, no gradient training. (iii) A kernel-RKHS classification rate O((k-1)√K/(γ√mmin)) with binary necessity threshold m = Omega(√ K/γ) from a matching Le Cam lower bound, and a closed-form filtration-selection rule. The kernel-Mahalanobis margin hatρMah is the strongest closed-form ranker across the chemical-graph pool (mean Spearman ρ ≈ +0.60); the isotropic surrogate hatγ/√K admits a selection-consistency rate, and widehatλ from (i) provides an independent data-level signal (positive on COX2 and PTC). (iv) A per-prediction certificate, in non-asymptotic Pinelis and asymptotic Gaussian forms, with no calibration split. Empirically, PALACE is the strongest closed-form diagram-based method on Orbit5k (91.3 ± 1.0%, matching Persformer), leads every diagram-based competitor on COX2 and MUTAG, and is competitive on DHFR (within 1 pp of ECP). At 8× domain inflation, adaptive placement maintains 94% while the uniform grid collapses to chance (25% on 4-class data).
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 14 of its 40 references that are in the map. First posted on arXiv 5 May 2026.
Builds on
14 of 40 references.
References · 14
- 2018How Powerful are Graph Neural Networks?cited by 4,355
- 2015Persistence Images: A Stable Vector Representation of Persistent Homologycited by 235
- 2019PersLay: A Neural Network Layer for Persistence Diagrams and New Graph Topological Signaturescited by 125
- 2017Deep Learning with Topological Signaturescited by 113
- 2019A Topology Layer for Machine Learningcited by 79
- 2017Sliced Wasserstein Kernel for Persistence Diagramscited by 77
- 2014A Stable Multi-Scale Kernel for Topological Machine Learningcited by 74
- 2019Learning metrics for persistence-based summaries and applications for graph classificationcited by 57
- 2018Persistence Fisher Kernel: A Riemannian Manifold Kernel for Persistence Diagramscited by 33
- 2018RetGK: Graph Kernels based on Return Probabilities of Random Walkscited by 32
- 2021Persformer: A Transformer Architecture for Topological Machine Learningcited by 19
- 2018DTM-based Filtrationscited by 16
Built on by
Citing papers per year: 2026: 2.
2 papers.