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

Source: arXiv - 2605.04046v1

Overview

The paper presents PALACE (Persistence Adaptive‑Landmark Analytic Classification Engine), a new kernel‑based method for classifying point‑clouds and graphs using topological data analysis (TDA). By adapting the placement of landmarks to the training data, PALACE delivers provable performance guarantees and per‑prediction confidence certificates—something that most existing TDA pipelines lack.

Key Contributions

• Adaptive landmark selection that requires only a tiny cross‑validation grid (≤ 5 choices for each of three hyper‑parameters).
• Four closed‑form theoretical guarantees, including:
  1. A lower‑distortion bound that reduces the required landmark budget by a factor ((D/L)^2) when persistence diagrams are clustered.
  2. An optimal weighting scheme ((w_k = K^{-1/2})) and a farthest‑point‑sampling strategy that approximates the optimal (k)-center covering radius without any gradient‑based training.
  3. A kernel‑RKHS classification rate bound (O!\big((k-1)\sqrt{K}/(\gamma\sqrt{m_{\min}})\big)) together with a matching Le Cam lower bound, plus a closed‑form rule for selecting the filtration.
  4. A per‑prediction certification mechanism (non‑asymptotic Pinelis and asymptotic Gaussian forms) that does not need a separate calibration split.
• Empirical dominance over existing closed‑form diagram kernels on several benchmark graph datasets (Orbit5k, COX2, MUTAG, DHFR), matching or surpassing deep‑learning baselines while remaining fully analytic.
• Robustness to domain shift: under an 8× domain inflation experiment, PALACE retains ~94 % accuracy whereas a uniform grid baseline drops to random‑guess levels.

Methodology

1. Persistence diagrams as features – Each graph or point cloud is turned into a persistence diagram using a chosen filtration (e.g., sublevel sets of a graph‑based function).
2. Landmark cover – Instead of a fixed uniform grid, PALACE builds a cover of the diagram space using a small set of landmarks. The landmarks are chosen by farthest‑point sampling on the training diagrams, guaranteeing a near‑optimal covering radius.
3. Adaptive weighting – All landmarks receive equal weight (w_k = K^{-1/2}), which maximizes the derived distortion lower bound (\lambda(\tau;\nu)).
4. Closed‑form kernel – The kernel between two diagrams is computed analytically from the distances to the landmarks, yielding a Mahalanobis‑type similarity (\hat\rho_{\text{Mah}}). No iterative training or back‑propagation is required.
5. Certification – Using concentration inequalities (Pinelis) and Gaussian approximations, PALACE produces a confidence interval for each prediction directly from the kernel scores.

The whole pipeline can be run with a handful of hyper‑parameter choices (budget (K), landmark radii, kernel bandwidth), selected via a tiny cross‑validation sweep.

Results & Findings

• The Mahalanobis margin (\hat\rho_{\text{Mah}}) achieved the highest Spearman correlation (≈ 0.60) with ground‑truth rankings across the chemical‑graph pool.
• In a synthetic “domain inflation” test (multiplying the number of classes and perturbing the data), PALACE’s adaptive landmarks kept performance at ~94 % while a uniform grid collapsed to ~25 % accuracy.
• The per‑prediction certificates were well‑calibrated: predictions flagged as low‑confidence indeed corresponded to higher error rates.

Practical Implications

• Plug‑and‑play TDA kernel: Developers can add topological features to existing ML pipelines without costly hyper‑parameter tuning or GPU training.
• Resource‑efficient: Because the method is analytic, inference is fast and memory‑light—ideal for edge devices or large‑scale graph mining.
• Certified predictions: The built‑in confidence scores enable risk‑aware deployment (e.g., drug‑discovery pipelines where false positives are costly).
• Robust to distribution shift: Adaptive landmark placement makes the model resilient when the data geometry changes, a common scenario in evolving networks or sensor streams.

Potential use‑cases include:

• Molecular property prediction (chemical graphs) where topological descriptors are known to be informative.
• 3‑D point‑cloud classification in robotics or autonomous driving, where persistence diagrams capture shape information that complements point‑wise features.
• Network anomaly detection, leveraging graph persistence to spot structural deviations.

Limitations & Future Work

• The theoretical guarantees assume cross‑diagram non‑interference and rely on the Lebesgue‑number condition; pathological diagram distributions may violate these assumptions.
• Landmark selection, while analytic, still depends on a modest cross‑validation sweep; fully parameter‑free adaptation remains an open question.
• Experiments focus on relatively small‑to‑medium graph benchmarks; scaling to massive graphs (millions of nodes) will require further engineering (e.g., approximate filtrations).
• Extending the certification framework to multi‑label or regression tasks, and integrating with deep‑learning backbones for hybrid models, are promising directions the authors suggest.

Authors

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

Paper Information

• arXiv ID: 2605.04046v1
• Categories: cs.LG, math.AT
• Published: May 5, 2026
• PDF: Download PDF