Abstract
GP Inference on large datasets is computationally expensive, especially when the observation likelihood is non-Gaussian. To reduce the computation, many recent variational inference methods define a variational distribution using a small set of inducing points. However, these methods often fail to capture local correlations. This paper proposes Amortized Variational Inference with Graph Convolutional Networks (AIGP), which localizes inference to small neighborhoods and uses GCNs to amortize the cost.
Introduction
Gaussian Processes (GPs) are a cornerstone of Bayesian non-parametrics, prized for their expressive power and principled uncertainty quantification. However, their standard $O(N^3)$ scaling limits their application to large datasets. Traditional scaling techniques, such as inducing point methods, approximate the GP using a small set of $M$ representative "inducing" points. While this reduces complexity to $O(NM^2)$, it introduces a "hard tradeoff": a small $M$ fails to capture local dependencies, while a large $M$ negates computational gains.
In their AISTATS 2019 paper, Liu and Liu propose a localized approach. By focusing on immediate neighborhoods—where the most significant correlations occur for many kernels—they bypass the limitations of global low-rank approximations.
Localized Variational Distribution
The authors define a variational posterior $q(\mathbf{f})$ with a covariance structure governed by a sparse lower triangular matrix $L$. This sparsity is informed by a directed graph where each data point is connected only to its $K$ nearest neighbors in the prior covariance space.
This localization allows the Evidence Lower Bound (ELBO) to be decomposed, facilitating efficient mini-batch optimization. However, optimizing individual variational parameters for millions of points remains a massive task.
Amortization via Graph Convolutional Networks
To address the optimization bottleneck, AIGP utilizes Graph Convolutional Networks (GCNs) as an inference network. Instead of optimizing parameters $\mu_i$ and $L_i$ for each point $i$ directly, a GCN is trained to predict these parameters based on local neighborhood observations. Since GCN weights are shared across the entire dataset, the number of parameters to optimize remains constant regardless of $N$, effectively amortizing the cost of inference.
Experimental Evaluation
AIGP was evaluated against state-of-the-art methods like SVGP, SAVIGP, and Deep GPs (DGP) on three large-scale tasks:
- eBird Dataset: Modeling Savannah Sparrow abundance (15k observations, Poisson likelihood).
- NightLight Raster: Fitting satellite imagery of US nighttime lights (56k pixels).
- Flight Delay Dataset: A massive regression task with 800k records.
Key Results and Insights
AIGP consistently outperformed inducing point methods in both speed and accuracy. On the NightLight dataset, it reached convergence in seconds, whereas competing methods required significantly more time for inferior results. On the 800k-point Flight Delay dataset, amortization proved essential; the non-amortized "pre-AIGP" version failed due to the overwhelming number of parameters, while the GCN-based AIGP handled it seamlessly.
As shown in the results, AIGP tends to prefer smaller length scales than inducing point methods, which are better suited for capturing the strong local correlations that AIGP prioritizes. The performance is also sensitive to the neighborhood size $K$, with larger $K$ generally improving accuracy at the cost of computation.
Conclusion
AIGP represents a significant shift in scaling GPs, moving from global low-rank approximations to localized, amortized inference. By leveraging the natural graph structure of GP covariances through GCNs, it provides a scalable, non-parametric solution that excels in capturing the local correlations often missed by traditional sparse GP methods.
Summary updated