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

arXiv:2605.04046v1 Announce Type: new 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; leq 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 lambda(au;nu) on D_n under cross-diagram non-interference, with a (D/L)^2 budget reduction over the uniform grid when diagrams concentrate. (ii) Equal weights w_k = K^{-1/2} maximizing lambda, 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)sqrt{K}/(gammasqrt{m_{min}})) with binary necessity threshold m = Omega(sqrt K/gamma) from a matching Le Cam lower bound, and a closed-form filtration-selection rule. The kernel-Mahalanobis margin hatrho_{Mah} is the strongest closed-form ranker across the chemical-graph pool (mean Spearman rho approx +0.60); the isotropic surrogate hatgamma/sqrt{K} admits a selection-consistency rate, and widehat{lambda} 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 pm 1.0%, matching Persformer), leads every diagram-based competitor on COX2 and MUTAG, and is competitive on DHFR (within 1 pp of ECP). At 8imes domain inflation, adaptive placement maintains 94% while the uniform grid collapses to chance (25% on 4-class data).

Source: arXiv cs.LG | 2026-05-06