Gaussian processes (GPs) are probabilistic regression models that give calibrated error bars. Exact inference costs cubic time in the number of data points, so the fastest large-scale variants condition each point only on its few nearest neighbors. That turns a dense $N \times N$ correlation structure into a sparse graph, and the graph is built with plain Euclidean distance. This works when nearby inputs are the most correlated ones. It fails when the kernel, the function that encodes which inputs move together, says otherwise. A daily-periodic electricity load is most correlated with the same hour yesterday, not with ten minutes ago. An additive kernel cares about agreement in individual coordinates, not overall closeness. In such cases a Euclidean neighbor graph conditions each point on the wrong points, however well the kernel itself has been learned.
We propose building the sparse conditioning graph in the kernel's own geometry and rebuilding it as the kernel's parameters are learned. Concretely, every kernel defines a distance between inputs. We approximate that distance with a low-dimensional random feature embedding, so a standard approximate nearest-neighbor index can search it, and we plug the resulting graph into a variational nearest-neighbor GP. The claim is narrow and testable. For kernels whose correlation is not a monotone function of a rescaled Euclidean distance, such as periodic, quasi-periodic, and additive kernels, kernel-metric neighbors should give a better posterior at the same neighbor count $K$. Euclidean neighbors with a much larger $K$ should not close the gap at matched compute.
What already exists, and the gap
Two lines of work supply the machinery. Variational nearest neighbor Gaussian process (VNNGP) places inducing points at every data location. It makes each one depend only on its $K$ nearest predecessors in a fixed ordering, which gives a sparse precision factor and a training objective that splits into minibatches at $\mathcal{O}(K^3)$ cost per step. Its authors flag Euclidean neighbor selection as suboptimal for periodic or anisotropic data. We reuse VNNGP unchanged except for the graph. Leveraging Locality and Robustness to Achieve Massively Scalable Gaussian Process Regression (GPnn) conditions each test prediction on its $m$ Euclidean nearest training points. It proves that prediction error becomes insensitive to kernel misspecification as $N \to \infty$. Our method applies equally to GPnn's test-time neighbor lookup, and we evaluate both.
The closest prior work is Scalable Gaussian-process regression and variable selection using Vecchia approximations. It already searches neighbors in an iteratively rescaled space defined by per-dimension lengthscales. For stationary kernels whose correlation decays monotonically in lengthscale-scaled distance (RBF, Matérn with per-dimension lengthscales), the kernel-induced distance below orders points exactly as scaled Euclidean distance does. In that regime our proposal reduces to theirs and offers nothing new. We therefore stake no claim there and treat it as a negative control. The new content lies where axis rescaling cannot help: kernels with periodic or additive structure, where the most correlated points can be far away in every rescaled Euclidean sense.
The graph-sparsification literature motivates the premise that the metric used to build a neighbor graph is decisive. An Empirical Study of Graph-Based Approaches for Semi-supervised Time Series Classification shows that the choice of distance and the $k$-NN pruning drastically change downstream accuracy on UCR time series. Identifying The Most Informative Features Using A Structurally Interacting Elastic Net shows that keeping only true nearest neighbors removes a long tail of noisy edges. Neither connects the graph metric to a model being learned at the same time.
Core mechanism
For a kernel $k_\theta$ with parameters $\theta$, the kernel-induced distance between inputs $x$ and $y$ is
$$ d_\theta(x,y)^2 = k_\theta(x,x) + k_\theta(y,y) - 2\,k_\theta(x,y). $$
This is the Euclidean distance between $x$ and $y$ after mapping both into the kernel's feature space. For a stationary kernel, nearest neighbors under $d_\theta$ are exactly the points with the highest prior correlation. To search it at scale, we draw $D'$ random Fourier features $\phi_\theta(x) \in \mathbb{R}^{D'}$ with $\phi_\theta(x)^\top \phi_\theta(y) \approx k_\theta(x,y)$. Then $\|\phi_\theta(x)-\phi_\theta(y)\|$ approximates $d_\theta$, and we build an ordinary approximate nearest-neighbor index on the $\phi_\theta(x_i)$. For periodic kernels the embedding has an explicit low-dimensional form: sine and cosine of the phase plus the non-periodic coordinates. For additive kernels the feature maps of the individual coordinates are stacked.
Training alternates two steps. The first is ordinary VNNGP minibatch updates for $T$ steps. The second refits $\phi_\theta$ to the current $\theta$, rebuilds the index, and recomputes each point's predecessor set. Variational parameters are stored per point, so they persist across rebuilds. Only the conditioning sets change. The data ordering stays fixed, which deliberately separates the metric question from VNNGP's unsolved ordering problem. Rebuilding the graph changes the objective being optimized. We will measure whether this causes oscillation, and we will compare rebuilding on a schedule against freezing the graph after a warm-up phase.
Research Program
The work has three parts. First, a controlled synthetic study. We draw functions from quasi-periodic and additive GPs with $N = 10^4$, small enough that the exact posterior is computable. This lets us measure the gap from the exact posterior directly as a function of the number of random features $D'$, the neighbor count $K$, the rebuild interval $T$, and the ratio of period to sampling density. Second, a short analysis of when kernel neighbors and Euclidean neighbors coincide. The aim is a usable diagnostic: the overlap of the two neighbor sets under the learned $\theta$, which predicts in advance whether the method can help on a given dataset. Third, real-data evaluation on the benchmarks below, applied to both VNNGP training and GPnn prediction.
Baselines
The naive reference point is VNNGP exactly as published in Variational nearest neighbor Gaussian process: Euclidean neighbors with $K \in \{32, 64\}$, using the same periodic or additive kernel as our method. It shares every component except the graph, so any gain is attributable to neighbor selection. Our method must beat it on held-out negative log-likelihood (NLL) and root mean squared error (RMSE) at equal $K$ and equal wall-clock time, with the rebuild cost included. No reported scalar result was found on Lacuna for VNNGP on Precipitation or HouseElectric. The file reports only that VNNGP achieved the lowest NLL on almost all spatial datasets, and that with $K=32$ it outperformed SVGP with 1024 inducing points on UKHousing, with values given only in figures. We will therefore rerun it ourselves.
The strongest existing competitor for the metric question is the scaled Vecchia approach of Scalable Gaussian-process regression and variable selection using Vecchia approximations, which uses neighbors in the lengthscale-rescaled space. We implement that rescaling inside the same VNNGP code, so it differs from our method only in the metric, and we refresh its neighbors on the same rebuild schedule. Beating it on periodic and additive data, while tying it on stationary data, is the core result. Winning on stationary data would indicate a bug rather than a discovery.
Global low-rank approximation is represented by the stochastic variational GP (SVGP), which summarizes the data with $M$ learned pseudo-points, run with the same kernel and $M = 1024$. We also run GPnn from Leveraging Locality and Robustness to Achieve Massively Scalable Gaussian Process Regression with its calibration step, using both Euclidean and kernel-metric test-time neighbors. For GPnn, the file reports training on $1.6\times10^6$ points in "approximately 30 seconds on a basic laptop" but gives no accuracy scalars.
One ablation isolates the key ingredient: kernel-metric neighbors computed once from warm-up hyperparameters and then frozen. This separates the value of the metric from the value of adapting it during training. A second ablation replaces random features with brute-force exact $d_\theta$ on the synthetic sets, which measures how much the approximate search costs. All methods get the same data splits, the same hyperparameter search budget, the same GPU, and five random seeds.
Why not just…?
Why not just use more Euclidean neighbors? If the relevant points one period away eventually enter the Euclidean neighbor set, a larger $K$ could recover the same posterior. This is the most serious threat. Cost grows as $K^3$, but for moderate period-to-density ratios it may still be affordable. We settle it with a matched-compute sweep, with Euclidean $K$ up to 256 against kernel-metric $K = 32$, and report the crossover as a function of how many samples fall within one period. If Euclidean neighbors with large $K$ match us at equal wall-clock time on the real datasets, we will report that the gain is confined to the synthetic regime.
Why not just rescale axes as scaled Vecchia does, or add the phase as an extra input feature? Axis rescaling cannot make points one period apart close to each other. Hand-adding sine and cosine of a known period is in fact a special case of our embedding. We include it as a strong hand-engineered baseline on HouseElectric, where the daily period is known. Our method's advantage must then come from learned periods, quasi-periodic decay, and additive structure, which a hand-built feature does not adapt to.
Why not just use SVGP with the periodic kernel? Low-rank models capture global periodic shape well. However, VNNGP's results on UKHousing ($K=32$ beating 1024 inducing points) indicate that they blur local detail. On Precipitation, which has both seasonality and sharp spatial variation, we expect SVGP to lose on NLL. The experiment checks this directly.
Proposed Experiments
The synthetic study reports the KL divergence from the exact posterior and the overlap between kernel-metric and Euclidean neighbor sets. The decisive prediction is that the gain grows as overlap falls and vanishes as overlap approaches one.
The real-data study uses three datasets with distinct roles. Precipitation from Variational nearest neighbor Gaussian process tests spatiotemporal data with seasonality. HouseElectric from Leveraging Locality and Robustness to Achieve Massively Scalable Gaussian Process Regression tests periodic structure at about a million points. UKHousing and 3DRoad serve as stationary controls where we predict a tie. On Protein and the 386-dimensional CT Slice data, we test additive kernels, where each coordinate's feature map is low-dimensional even though the inputs are not. This addresses the high-dimensional failure of Euclidean neighbor search that the GPnn authors report.
Metrics are NLL, RMSE, the coverage of 90% predictive intervals (a stronger calibration check than GPnn's variance matching), and wall-clock time with index rebuilds included. The proposal succeeds if, on Precipitation and HouseElectric, kernel-metric neighbors reduce NLL relative to both Euclidean and scaled-Vecchia VNNGP at matched time, the controls show no difference, and the neighbor-overlap diagnostic predicts which datasets benefit.
References
- Variational nearest neighbor Gaussian process
- Leveraging Locality and Robustness to Achieve Massively Scalable Gaussian Process Regression
- Scalable Gaussian-process regression and variable selection using Vecchia approximations
- An Empirical Study of Graph-Based Approaches for Semi-supervised Time Series Classification
- Identifying the most informative features using a structurally interacting elastic net