Gaussian processes (GPs) are probabilistic models that predict a function's value at a node of a graph together with an honest error bar. Exact GPs cost cubic time in the number of nodes, so most scalable versions replace the full covariance matrix with a low-rank one. These low-rank versions either summarize the graph through a few hundred "inducing" nodes or keep only the smoothest few hundred eigenvectors of the graph Laplacian. A separate line of graph-embedding theory has shown that low-rank inner-product representations cannot faithfully describe real networks, which are sparse yet full of triangles. This proposal argues that the two facts are the same fact. A covariance matrix that correlates each node mainly with its few clustered neighbors has an effective rank close to the number of nodes divided by the size of a typical neighborhood. Any rank-$m$ approximation below that floor must either discard local correlation and treat it as noise, or invent correlation between unrelated nodes. Both errors leave a predictable signature in the posterior.
The project has three parts. It turns this observation into a quantity that can be computed before training, the rank floor, which says how many inducing points or eigenvectors a graph GP needs. It tests whether the floor predicts where existing approximations break. It then asks whether a cheap fix works better than the obvious alternatives. The fix splits the kernel into a global low-rank part, which captures smooth long-range variation, and a local part built from small graph patches. Those patches are known to be low-dimensional even when the whole graph is not, as Implications of sparsity and high triangle density for graph representation learning showed.
Core Claim
The tool is the Rank Lemma that The impossibility of low-rank representations for triangle-rich complex networks used to show that dot-product embeddings of sparse, triangle-rich graphs need rank $\Omega(n/\log^2 n)$. For any positive semidefinite matrix $A$, $\mathrm{rank}(A) \ge \mathrm{tr}(A)^2/\|A\|_F^2$. Apply this to a graph kernel normalized to unit variance, with correlations $\rho_{ij}$ between nodes $i$ and $j$:
$$\mathrm{rank}(K) \;\ge\; \frac{n}{1+\bar s}, \qquad \bar s = \frac{1}{n}\sum_{i\neq j}\rho_{ij}^2,$$
Here $\bar s$ is the average squared-correlation mass per node. On a sparse graph with a localized kernel, such as a diffusion or Matérn kernel with a short length scale, $\bar s$ is on the order of the size of a node's clustered neighborhood. The floor is therefore nearly linear in $n$.
The same inequality, applied to an approximation $\widetilde K$ of rank $m$ whose diagonal retains a fraction $1-\delta$ of the true variance, forces $\|\widetilde K\|_F^2 \ge n^2(1-\delta)^2/m$. When $m \ll n/(1+\bar s)$, this Frobenius mass cannot fit inside the true local correlations. It must appear either as spurious long-range correlation, the "crowding" effect, or as a large variance deficit $\delta$. Sparse variational methods typically push that deficit into noise.
The empirical prediction is sharp. Below the floor, Nyström-style and truncated-Fourier graph GPs should revert toward the prior mean at unlabeled nodes that sit inside labeled triangles. They should also report variances that ignore the presence of labeled neighbors. Above the floor, these artifacts should disappear. Sparse, non-low-rank approximations should not show the artifact at any budget. This last prediction runs against the file's suggestion that graph random features inherit the sign-rank bottleneck. Their sketches are sparse vectors indexed by nodes, so the Rank Lemma does not bind them. We will test this rather than assume it.
The new ingredient is the link between embedding lower bounds and the approximation budget of scalable GPs. Implications of sparsity and high triangle density for graph representation learning proves global non-recoverability for embeddings, not for GP posteriors. The impossibility of low-rank representations for triangle-rich complex networks bounds adjacency approximations, not covariance approximations. The scalable graph GP papers choose their budgets heuristically and never relate them to triangle structure.
Research Program
The first part is theory and diagnostics. We will make the bound above precise for the Matérn and diffusion kernels of Matérn Gaussian Processes on Graphs. That paper defines graph GPs through a stochastic differential equation on the Laplacian and scales them with truncated Laplacian eigenvectors plus inducing points, which makes it the canonical low-rank method our floor targets. We will also derive the posterior consequence: a lower bound on the excess predictive error at a held-out node in terms of the variance deficit and that node's local correlation mass. Estimating $\bar s$ needs only kernel entries within a few hops of sampled nodes, so the floor costs roughly linear time to compute. We will also report how $\bar s$ depends on clustering. For a fixed degree, triangle-rich neighborhoods keep correlation mass local, and this is where triangle density enters the argument.
The second part is an audit of existing approximations. We will measure posterior error against the computed floor for each of four approximations. The first two are truncated Fourier features and inducing-node variational GPs following Matérn Gaussian Processes on Graphs, with budget $m$ swept across the floor. The third is the inducing-graph construction in Bayesian Link Prediction with Deep Graph Convolutional Gaussian Processes, a deep GP for link prediction whose inducing graph caps its rank and which its authors evaluate only up to thousands of nodes. The fourth is Graph Random Features for Scalable Gaussian Processes. That method builds sparse random-walk feature vectors per node, solves with conjugate gradients in $O(N^{3/2})$ time, and is our prediction for a method that sits above the floor by construction.
The third part is a local-plus-global kernel. We write $K \approx K_{\text{glob}} + K_{\text{loc}}$. Here $K_{\text{glob}}$ is a low-rank part, with $m$ well below the floor, fit to the smoothest Laplacian components. $K_{\text{loc}}$ is block-sparse. Each block is an exact GP covariance restricted to a core-periphery patch, in the sense of Implications of sparsity and high triangle density for graph representation learning, who found that such slices of real graphs such as ca-HepPh are well described in about five dimensions. Overlapping patches are reconciled at prediction time by nearest-patch weighting. This is borrowed from Leveraging Locality and Robustness to Achieve Massively Scalable Gaussian Process Regression, which predicts from local neighbors only, fits hyperparameters on a subset, and recalibrates variance with a cheap post-hoc correction. Its main weakness is nearest-neighbor search in high-dimensional inputs, and graph hops avoid that weakness.
The local part restores the diagonal and near-diagonal mass that the low-rank part cannot hold. The global part supplies the long-range coupling that patches miss. This is a GP-side answer to the open problem Sansford et al. raise about stitching local views together. Hyperbolic (Paul Berg et al.) and metric (How Low Can You Go?) embeddings are out of scope. They address representation dimension but supply no posterior, and the metric-decoder exactness results in that paper also come with the overfitting caveat raised by Nicolas Menand and C. Seshadhri.
Baselines
The reference point on graphs small enough to allow it is the exact GP with the same Matérn or diffusion kernel and hyperparameters. This applies to Facebook (about 4,000 nodes) and Cora. Every approximation's posterior mean and variance is measured as a deviation from this exact posterior, so we isolate approximation error from kernel choice. The "do nothing" point is the prior-mean predictor. It shows how close a below-floor approximation comes to having learned nothing at interior nodes.
The canonical low-rank competitor is the truncated-Fourier and inducing-point graph Matérn GP of Matérn Gaussian Processes on Graphs. It reports about 79% node-classification accuracy on Cora and an MSE of 1.37 on San Jose freeway traffic interpolation. We rerun it on identical splits and use its own reported numbers as a sanity check of our reimplementation. It is run at budgets of 0.1, 0.3, 1, 3 and 10 times the computed floor, all within a matched wall-clock budget.
The strongest scalable competitor is Graph Random Features for Scalable Gaussian Processes with its learnable modulation function. It is strongest because it is sparse rather than low-rank and has already run Thompson-sampling Bayesian optimization on the 1.1-million-node YouTube graph on a single GPU. The file reports no accuracy or error number for GRF on any benchmark we use; it reports only scaling, such as being 50 times faster than its dense version on an 8,000-node graph. We will therefore treat our own tuned run as the number to beat. It receives the same hyperparameter search budget, the same random-walk budget per node as the patch construction uses in hops, and the same GPU.
For link prediction, the reference is Link-DGP from Bayesian Link Prediction with Deep Graph Convolutional Gaussian Processes. It reports 97.72% AUC on Power against 79.23% for a variational graph autoencoder. There we vary only its inducing-graph size relative to the floor.
Two ablations isolate the key ingredient. One drops $K_{\text{loc}}$, which leaves a low-rank model, and the other drops $K_{\text{glob}}$, which leaves a pure patch GP close to nearest-neighbor GP regression on graphs. A third control replaces core-periphery patches with plain $k$-hop balls of equal size.
The proposal beats the low-rank baselines if, at equal compute, it closes most of the gap to the exact posterior below the floor. Concretely, we will compare its error at interior nodes, its predictive log-likelihood, and its calibration curves to those of the low-rank models at the same $m$. Against GRF, the bar is matching accuracy and predictive log-likelihood with lower runtime or better calibration. If it only ties GRF, we will report that.
Why not just…?
Why not just raise the number of inducing points or eigenvectors? The floor says the needed budget is about $n/(1+\bar s)$. On sparse graphs this is a sizable fraction of $n$, which returns variational GP cost toward cubic. The embedding evidence points the same way: on Facebook, even rank 2,000 for 4,000 nodes failed to reproduce the triangle distribution in The impossibility of low-rank representations for triangle-rich complex networks. Our budget sweep measures this directly. If error falls smoothly well before the floor, the theory is too pessimistic and we will say so.
Why not just use graph random features? This is the real threat. Our own argument predicts that GRF is not rank-limited, so it may simply match the proposal. If it does, the contribution reduces to the diagnostic: a computable rule for when low-rank graph GPs are unsafe and sparse ones are required, which is still useful because the low-rank methods remain the default for spectral and inducing-point pipelines. The comparison could still go our way for one reason. GRF carries a diagonal bias of order $1/n$ and a learned modulation that may oversmooth sharp local signals. Patches give exact local blocks, so calibration at interior nodes is where a difference would show.
Why not just use a graph neural network or graph autoencoder? These give no calibrated posterior, which Bayesian optimization and active learning need. They also degrade on sparse labels and edges: Link-DGP's 97.72% versus 79.23% AUC on Power, and its robustness at 20% of edges, both come from Bayesian Link Prediction with Deep Graph Convolutional Gaussian Processes. We include no such network baseline beyond that reported comparison.
Why not just run nearest-neighbor GP regression over graph hops? That is the global-free ablation. It will show whether the low-rank global part earns its keep on signals with long-range structure. Traffic along freeways and wind fields are the likely cases where it does.
Proposed Experiments
The decisive test uses planted signals. We sample functions from exact Matérn GPs on Facebook, ca-HepPh and cit-HepPh across length scales, which varies $\bar s$ and hence the floor. We then fit every method from 10–30% of node labels. The theory is confirmed if, for low-rank methods, excess error at held-out nodes inside labeled triangles collapses onto a single curve when plotted against $m(1+\bar s)/n$, with a knee near 1, while GRF and the patch methods show no knee. It is refuted if the knee position does not track $\bar s$ across length scales.
The real-data tests are Cora classification and San Jose traffic interpolation, compared against the reported 79% and 1.37 MSE, plus link prediction on Power, Yeast and Router with the Link-DGP inducing graph swept across the floor.
The scale test runs Thompson-sampling Bayesian optimization on YouTube against GRF. Its target is a localized planted objective, a peak inside one dense community, chosen because Approximation-Aware Bayesian Optimization shows that budget-limited inducing points smooth over localized optima. We report simple regret over evaluations and wall-clock time. The file gives no reported result for YouTube optimization quality, so both sides are run by us under identical budgets.
References
- Implications of sparsity and high triangle density for graph representation learning
- The impossibility of low-rank representations for triangle-rich complex networks
- Matérn Gaussian Processes on Graphs
- Bayesian Link Prediction with Deep Graph Convolutional Gaussian Processes
- Graph Random Features for Scalable Gaussian Processes
- Leveraging Locality and Robustness to Achieve Massively Scalable Gaussian Process Regression
- Horospherical Learning with Smart Prototypes
- How Low Can You Go? Searching for the Intrinsic Dimensionality of Complex Networks using Metric Node Embeddings
- Link prediction using low-dimensional node embeddings: The measurement problem
- Approximation-Aware Bayesian Optimization