Certified Neighbor Graphs for Kernels That Keep Learning

Many streaming systems need two things at once. They need a similarity graph over their data, where each point is linked to its nearest neighbors, for clustering, label propagation, or search. They also need the similarity measure itself, the kernel, to keep improving as labels and new data arrive. Today these two jobs live in separate literatures. Dynamic graph algorithms keep a neighbor graph or spectral sparsifier up to date under insertions and deletions, but always for a kernel that is fixed in advance. Gradient-based kernel learning tunes bandwidths and per-feature lengthscales by backpropagation, but assumes the data sit in a static array or an unindexed stream. Put them together naively and the result breaks: every gradient step on the kernel moves every pairwise distance at once, so the maintained graph goes stale everywhere.

This note proposes a simple way to let the kernel learn without rebuilding the graph after each step. For the common family of per-feature (ARD, "automatic relevance determination") lengthscale kernels, a change in lengthscales distorts all distances by a factor bounded by a single number computed from the parameters. That bound gives each node a cheap local test. The node checks whether its stored, slightly oversized candidate list provably still contains its exact $k$ nearest neighbors under the new kernel. Only nodes that fail the test are re-queried. The graph therefore stays exactly the $k$-nearest-neighbor graph of the current kernel, gradients through it are exact, and repair work is proportional to how far the metric has actually drifted rather than to how often it was updated.

Core Claim

Bandwidth changes alone do not alter a $k$-nearest-neighbor graph's topology, only its edge weights. Topology changes only when the relative scaling between features changes. Write the learned squared distance as $d_\theta(x,y)^2=\sum_i (x_i-y_i)^2/\ell_i^2$, with lengthscales $\ell_i$. Let $\ell^0$ be the lengthscales at which the graph was last anchored, and let $s_i=\ell^0_i/\ell_i$. Then every distance satisfies $s_{\min} d_0 \le d_\theta \le s_{\max} d_0$. Define the distortion $\rho=s_{\max}/s_{\min}$. Suppose a node $x$ stores its $K>k$ nearest neighbors under the anchor metric, with anchor radii $r^0_k(x)$ and $r^0_K(x)$. Then

$$ \rho\, r^0_k(x) \le r^0_K(x) \;\Longrightarrow\; \text{the stored } K \text{ candidates contain all } k \text{ nearest neighbors of } x \text{ under } d_\theta . $$

The reason is short. Any true new neighbor $y$ has $d_\theta(x,y)\le r^\theta_k(x)\le s_{\max} r^0_k(x)$, so $d_0(x,y)\le \rho\, r^0_k(x)$. For a full Mahalanobis metric the same argument holds, with $\rho$ the condition number of the relative linear map. The test costs $O(1)$ per node after an $O(\text{dim})$ computation of $\rho$.

The claim to be tested is that this certificate lets a system run online gradient descent on kernel parameters while maintaining an exact learned-metric neighbor graph, at a small fraction of the cost of periodic rebuilds. It should also beat frozen-kernel dynamic graphs on drifting streams. The certificate-and-repair layer works with the existing dynamic index structures rather than replacing them.

Relation to Prior Work

Several papers maintain kernel-defined graphs dynamically, and they motivate the gap. Dynamic Similarity Graph Construction with Kernel Density Estimation maintains a cluster-preserving sparse similarity graph under insertions using dynamic kernel density estimation (estimating how densely points crowd each location), but its bandwidth is a constant. Dynamic Kernel Sparsifiers keeps a spectral sparsifier under point moves in $n^{o(1)}$ time per move, also for a fixed kernel. A kernel parameter update is equivalent to moving all $n$ points simultaneously, so that structure would pay roughly $n^{1+o(1)}$ per gradient step. That is exactly the cost this proposal avoids. Fully Dynamic Coreset Spectral Clustering maintains a spectral-clustering coreset under edge and node updates with fixed edge weights. Our work is a candidate front end for it: its edge stream would be produced by our certified graph.

The online multi-kernel learning papers that use graphs differ in what the graph is. Graph-Aided Online Multi-Kernel Learning uses a fixed side-information graph to weight a fixed dictionary of kernels. Online Multi-Kernel Learning with Graph-Structured Feedback uses a graph to describe which kernels' losses are observed. Multi-Kernel Kriged Kalman Filtering tracks signals on a fixed sensor graph. In none of them does the graph depend on the kernel being learned. In ours it does.

On the method side, Efficient Hyperparameter Tuning for Large Scale Kernel Ridge Regression supplies two ingredients. The first is stochastic trace estimation, which approximates large matrix traces from random probe vectors. The second is a warning that constrains our objective: unbiased criteria such as hold-out loss overfit badly when many lengthscales are tuned at once, while a biased complexity-penalized objective does not. Large-scale Online Kernel Learning with Random Feature Reparameterization shows that online gradient updates to kernel parameters substantially reduce error on streams. It is also our strongest graph-free competitor.

On the index side, the DiskANN library and SPatch supply candidate retrieval and deletion handling under the anchor metric. Both assume embeddings and distances never change.

One tension needs facing directly. Dynamic Kernel Sparsifiers requires smooth, multiplicatively Lipschitz kernels for its guarantees, and learned kernels can be sharp. We deliberately restrict the certificate to learned metrics inside a fixed radial kernel profile. The topology guarantee then holds regardless of the profile's smoothness, and the more expressive kernels of Neural Kernel Networks are out of scope.

Research Program

The system has four parts.

The first is an anchor index. A Vamana or HNSW-style graph under the anchor metric $d_0$ answers range queries and supplies each node's $K$ anchor candidates. Deletions are handled by SPatch-style local patching, and insertions by standard greedy insertion.

The second is the certified learned graph. It holds each node's exact $k$ neighbors under $d_\theta$, chosen from its $K$ candidates, together with Gaussian edge weights $\exp(-d_\theta^2/2\sigma^2)$. After each kernel step we recompute $\rho$. Every node that fails the inequality issues an anchor range query of radius $\rho\, r^0_k(x)$ to refresh its candidates. When the fraction of failing nodes passes a threshold $\tau$, we re-anchor, setting $\ell^0\leftarrow\ell$, and rebuild lazily in the background. The cost of re-anchoring is charged to the method in all comparisons.

The third is the learning objective. Labels arrive sparsely in the stream. Predictions $f_\theta$ come from Laplacian-regularized label propagation on the current graph, meaning labels spread to nearby points along graph edges. We minimize

$$ \mathcal{L}(\theta)=\frac{1}{|S|}\sum_{i\in S}\big(f_\theta(x_i)-y_i\big)^2+\beta\,\mathrm{tr}\!\big((I+\lambda L_\theta)^{-1}\big), $$

Here $S$ is the labeled set, $L_\theta$ is the graph Laplacian under the current kernel, $\lambda$ is the propagation strength, and the trace term is an effective-dimension penalty with weight $\beta$. That penalty is adapted from the complexity regularizer in Efficient Hyperparameter Tuning for Large Scale Kernel Ridge Regression. Gradients with respect to $\theta=(\ell,\sigma)$ are computed through the edge weights by implicit differentiation, using conjugate-gradient solves on the sparse Laplacian, which iteratively solve the linear system without forming its inverse. The trace is estimated with Hutchinson probes.

The fourth part is analysis. We will measure how $\rho$ evolves during learning and the fraction of nodes failing per step. We will also derive the expected repair cost as a function of $K/k$ and the local growth rate of neighbor radii. For data with intrinsic dimension $m$, $r_K/r_k\approx (K/k)^{1/m}$, which gives an explicit drift tolerance.

Baselines

The naive reference point is a frozen kernel. Lengthscales are fit once by gradient descent on the first 10% of the stream with the same objective. The graph is then maintained under that fixed metric by the same anchor index, with no further learning. This isolates whether continued kernel learning matters at all.

The strongest systems competitor is exact periodic rebuilding. The learned-metric $k$-NN graph is rebuilt from scratch every $T$ gradient steps, sweeping $T$ over a log grid, and stale graphs are used between rebuilds. It is run on the same hardware, with the same index code and the same gradient-step budget. We compare on the accuracy-versus-total-compute curve. Our method beats it only if it dominates every point of the sweep, not just a hand-picked $T$.

The strongest learning competitor is graph-free online kernel learning with reparameterized random features from Large-scale Online Kernel Learning with Random Feature Reparameterization. That paper reports a 3.68% mistake rate on ijcnn1 against 8.35% for the next best baseline. We will reproduce it on ijcnn1 and run it on our streams with the same labels and a matched tuning budget. The comparison is fair because both methods see identical labeled points. Our method beats it if label propagation on the learned graph gives lower error in the label-scarce regime, roughly 1% labels or fewer.

The ablation that isolates the certificate replaces it with an uncertified heuristic. Nodes are re-queried with probability proportional to $\rho-1$ at equal repair budget, and we measure neighbor-recall loss against the exact learned-metric graph.

A second ablation drops the trace penalty to test whether the overfitting reported for unbiased criteria reappears in this graph setting.

Why not just…?

Why not just rebuild the graph every few hundred gradient steps? This is the real threat. If lengthscales settle quickly after warm-up, a rarely rebuilt graph may be good enough. The certificate's value is that it repairs exactly where and when the metric has moved, and it is free when nothing changed. Periodic rebuilds either waste compute during stable phases or serve stale neighbors during drift. The $T$-sweep against an exact-graph oracle settles this. If periodic rebuilding matches us on stationary streams, we will report that and confine the claim to drifting streams.

Why not just learn the kernel offline and freeze it? The dynamic coarsening work in Adapting to Evolving Graphs documents "error lock-in" when early structural choices are frozen. The random-feature results show that fixed bandwidths cost accuracy on streams. However, neither involves a maintained graph under a learned metric. The frozen baseline on class-incremental and temporally ordered streams tests this directly.

Why not drop the graph and run an online random-feature kernel classifier? With plentiful labels it may well win, and we expect that. The graph earns its place only when unlabeled structure carries information, so the comparison is run across label rates. The crossover point is itself a result.

Why not use a dynamic kernel sparsifier and treat a kernel step as point moves? As argued above, one step moves all $n$ points. That costs about $n^{1+o(1)}$ under Dynamic Kernel Sparsifiers, which is no better than rebuilding, and its guarantees exclude non-Lipschitz kernels.

Proposed Experiments

The streams are built from mnist, EMNIST, covtype, census, and cifar10 embeddings. Each is ordered three ways: randomly, by class arrival (class-incremental), and by natural order for covtype. A 50% deletion phase is added to exercise the SPatch-style handling.

The main metrics are streaming error on held-out labeled points, NMI and ARI of spectral clustering on the maintained graph, exact-$k$-NN recall of the maintained graph against brute force under the current $\theta$, and total wall-clock time and repair queries per gradient step.

There is no reported result found on Lacuna for semi-supervised label propagation with learned lengthscales on these streams. The only cited number for the graph-free competitor is the ijcnn1 mistake rate above. For clustering fidelity, Fully Dynamic Coreset Spectral Clustering reports ARI "nearly identical" to the full static algorithm on mnist but gives no figure. We will feed its coreset our certified edge stream and check that this property survives a learning kernel.

The decisive checks are threefold. First, the certified graph's neighbor recall must be exactly 1.0 by construction; any shortfall indicates an implementation error. Second, repair cost per step must track measured $\rho-1$ and stay far below rebuild cost on drifting streams. Third, the learned kernel must beat the frozen one on class-incremental orderings while matching periodic rebuilding's accuracy at a fraction of its compute. If the second check fails because $\rho$ jumps beyond the slack $K/k$ allows on real data, the method reduces to periodic rebuilding. We will report that, along with the measured relationship between $K/k$, intrinsic dimension, and drift tolerance.