cs.CGOct 14, 2026

Geometric Kernel Diversity: An Axiomatic Diversity Measure in Euclidean Space

Authors: Ditbul Ban, Younghun Roh, Julian Shun, Vihan Lakshman

Organizations: MIT CSAIL

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Quantifying the diversity of a set of objects is a fundamental problem in machine learning and statistics. Mironov and Prokhorenkova (2025) recently showed that three axioms-monotonicity, uniqueness, and continuity-are crucial for a reliable diversity measure and that none of the standard metrics in the literature satisfy all three. They also constructed two measures that do satisfy the axioms, but both are NP-hard to compute, leaving open the question of whether efficient axiomatic diversity measures can exist. We study a Euclidean-restricted version of this question. We introduce Geometric Kernel Diversity (GKD), which associates a radial kernel solid with each point and measures the volume of their union. We show that canonical GKD satisfies all three Mironov-Prokhorenkova axioms on Euclidean-realizable inputs. For canonical GKD, we give exact polynomial-time algorithms in dimensions d≤3d \le 3. In arbitrary dimensions, we give a randomized algorithm that returns a (1±ε)(1 \pm \varepsilon)-approximation with probability at least 1−δ1-δ in time O(ndε2log⁡2δ)O \left(\frac{nd}{\varepsilon^2}\log\frac{2}δ\right) for nn points. The axiomatic guarantee applies to exact canonical GKD; the randomized algorithm approximates this deterministic quantity. We further show that the two diversity measures of Mironov and Prokhorenkova (2025) remain NP-hard on Euclidean-realizable inputs and, unless NP=RP\mathrm{NP} = \mathrm{RP}, admit no FPRAS even on this restricted domain.

Figures & tables

Figure 1: Union-volume interpretation of GKD in R2\mathbb{R}^{2} . (a) A point xi{\bm{x}}_{i} induces the under-graph solid Sϕ,2(xi)S_{\phi,2}({\bm{x}}_{i}) . (b) For a configuration X={x1,x2,x3}X=\{{\bm{x}}_{1},{\bm{x}}_{2},{\bm{x}}_{3}\} , GKD is the volume of the union of the corresponding solids, whose upper boundary is u=ϕ(dX(z))u=\phi(d_{X}({\bm{z}})) .
Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

MeasureInitialFinalRelative change
Monotonicity: c=1.76→1.99c=1.76\rightarrow 1.99
GKD1.888471.89442+0.315%+0.315\%
Average pairwise distance1.253331.33000+6.12%+6.12\%
Vendi Score2.293782.28758−0.270%-0.270\%
DPP0.375430.34676−7.64%-7.64\%
RKE0.679500.69101+1.69%+1.69\%
Appendix
Table 1: Numerical endpoint behavior in the controlled axiom stress tests. Relative change is computed from the first endpoint to the second. For DPP in the uniqueness example, both endpoint values are zero, so we report 0%0\% to indicate no change.
Figure 2: Controlled axiom stress tests. (a) Three-point monotonicity construction with d12=d13=1d_{12}=d_{13}=1 and d23=cd_{23}=c , where cc increases from 1.761.76 to 1.991.99 . (b) GKD increases along this expansion, while the Vendi Score decreases. (c) In the uniqueness construction, separating one member of a duplicate pair increases GKD while the Vendi Score decreases. The behavior of all comparison measures is reported in Table 1 .
Measureλ=0.1\lambda=0.1λ=0.25\lambda=0.25λ=0.5\lambda=0.5λ=1\lambda=1
Average pairwise distance0%0\%0%0\%0%0\%0%0\%
Vendi Score0.089%0.089\%0.438%0.438\%4.40%4.40\%33.61%33.61\%
DPP20.53%20.53\%39.46%39.46\%67.57%67.57\%88.21%88.21\%
RKE0%0\%0%0\%0%0\%0%0\%
Appendix
Table 2: Observed monotonicity reversal rates at the primary bandwidth h0h_{0} . Each column contains all 225,000225{,}000 single-edge expansions at the indicated value of λ\lambda .
Figure 3: Axiom stress tests on ImageNet/DINOv2 geometry. (a) Reversal rates under exhaustive single-edge Euclidean expansions. (b) Reversal rates under all 450,000450{,}000 ordered duplicate replacements. Error bars are 95%95\% percentile bootstrap intervals from resampling ImageNet classes.
Measureλ\lambda0.5h00.5h_{0}h0h_{0}2h02h_{0}
Vendi0.10.10.334%0.334\%0.089%0.089\%0.004%0.004\%
 0.250.250.877%0.877\%0.438%0.438\%0.029%0.029\%
 0.50.52.58%2.58\%4.40%4.40\%1.09%1.09\%
 116.94%6.94\%33.61%33.61\%62.24%62.24\%
DPP0.10.16.02%6.02\%20.53%20.53\%33.96%33.96\%
 0.250.2511.54%11.54\%39.46%39.46\%61.46%61.46\%
Appendix
Table 3: Observed monotonicity reversal rates across RBF bandwidths. Each entry is the percentage of 225,000225{,}000 single-edge expansions producing a wrong-direction change. Average pairwise distance and RKE have zero reversals throughout.
Measure0.5h00.5h_{0}h0h_{0}2h02h_{0}
Vendi Score0.008%0.008\%1.83%1.83\%8.96%8.96\%
DPP0%0\%0%0\%0%0\%
RKE0.74%0.74\%12.70%12.70\%26.18%26.18\%
Appendix
Table 4: Observed uniqueness reversal rates across RBF bandwidths. Average pairwise distance is bandwidth-independent and reverses 18.90%18.90\% of the ordered replacements.
More in this topic

Approximation Algorithms

Approximation algorithms find provably near-optimal solutions to computationally hard optimization problems when exact solutions are impractical.

See all 88 papers

Explore similar work

CardsList

  1. Streaming algorithms for robust max-min diversification

    Oct 1, 2026Andrea Pietracaprina, Geppino Pucci, Stefano ZanonCoreset SelectionApproximation Algorithms

    Department of Information Engineering, University of Padova, Italy

  2. A General Kernel Framework for Non-CND Distance Measures Using |D|-Dimensional Sparse Landmark Embeddings

    Sep 16, 2026Marcus M. Noack, Maher B. Alghalayini, Mark D. RisserKernel MethodsGaussian Process Regression

    Applied Mathematics and Computational Research Division, Lawrence Berkeley National Laboratory, Berkeley, CA 94720, USA · Climate and Ecosystem Sciences Division, Lawrence Berkeley National Laboratory, Berkeley, CA 94720, USA

  3. Low-Dimensional Embeddings for Gaussian Kernels on Manifolds

    Sep 14, 2026Soumik Dutta, Kunal DuttaFourier Feature EmbeddingsKernel Methods

    Institute of Informatics, University of Warsaw, Poland