A Closed-Form Adaptive-Landmark Kernel for Certified Point-Cloud and Graph Classification

2026/05/05 by Sushovan Majhi, Atish Mitra, Žiga Virk +1 · 1 voice
Computer Science · Mathematics · #cs.LG #math.AT

paper · pdf · doi:10.48550/arxiv.2605.04046

Abstract

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 λ(τ;ν) on D_n under cross-diagram non-interference, with a (D/L)² budget reduction over the uniform grid when diagrams concentrate. (ii) Equal weights w_k = 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)/(γ√m_min)) with binary necessity threshold m = Ω(√ K/γ) from a matching Le Cam lower bound, and a closed-form filtration-selection rule. The kernel-Mahalanobis margin ρ_Mah is the strongest closed-form ranker across the chemical-graph pool (mean Spearman ρ≈ +0.60); the isotropic surrogate γ/√(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).

Citations

• Geometric embeddings of spaces of persistence diagrams with explicit distortions
• Persformer: A Transformer Architecture for Topological Machine Learning
• A Topology Layer for Machine Learning
• Learning metrics for persistence-based summaries and applications for graph classification
• PersLay: A Neural Network Layer for Persistence Diagrams and New Graph Topological Signatures
• How Powerful are Graph Neural Networks?
• RetGK: Graph Kernels based on Return Probabilities of Random Walks
• Persistence Fisher Kernel: A Riemannian Manifold Kernel for Persistence Diagrams
• Deep Learning with Topological Signatures
• Sliced Wasserstein Kernel for Persistence Diagrams
• Persistence weighted Gaussian kernel for topological data analysis
• A Stable Multi-Scale Kernel for Topological Machine Learning
• Statistical topological data analysis using persistence landscapes
• The structure and stability of persistence modules
• A Unified Framework for Approximating and Clustering Data
• A unified framework for approximating and clustering data
• Ricci curvature of Markov chains on metric spaces
• Ricci curvature of Markov chains on metric spaces
• Clustering to minimize the maximum intercluster distance

Discussions

• The real surprise here isn't the closed-form guarantees—it's that the Lebesgue-number criterion on the landmark cover turns a computational geometry trick into a certificate for graph isomorphism. Mos [bsky, 1 points, 0 comments]

Related

• A Quest for Structure: Jointly Learning the Graph Structure and Semi-Supervised Classification
• Mahalanobis k-NN: A Statistical Lens for Robust Point-Cloud Registrations
• Revisiting Point Cloud Completion: Are We Ready For The Real-World?
• Point Ladder Tuning: Parameter-Efficient Hierarchical Adaptation for 3D Point Cloud Understanding
• PC-Adapter: Topology-Aware Adapter for Efficient Domain Adaption on Point Clouds with Rectified Pseudo-label