The Kernel Interaction Trick: Fast Bayesian Discovery of Pairwise Interactions in High Dimensions

Raj Agrawal, Jonathan H. Huggins, Brian Trippe, Tamara Broderick

TL;DR

The "Kernel Interaction Trick" enables fast Bayesian discovery of pairwise interactions in high-dimensional data by reducing the computational complexity from quadratic to linear in the number of covariates ($p$). By representing hierarchical models as Gaussian Processes, the authors achieve orders-of-magnitude speedups and better error rates than state-of-the-art LASSO methods, all while maintaining the robust uncertainty quantification inherent to Bayesian inference.

What Problem Does This Paper Address?

In fields like genomics and precision medicine, researchers often look for "interaction effects"—cases where two variables (like two different genes) together impact an outcome more than the sum of their individual parts. The challenge is that as the number of variables $p$ grows, the number of possible pairs grows quadratically ($p^2$).

While Bayesian methods are excellent for this task because they handle uncertainty well and can incorporate prior knowledge, they are notoriously slow. A "naive" Bayesian approach requires tracking and updating $O(p^2)$ parameters, which becomes computationally impossible even for moderate datasets. Frequentist alternatives like the LASSO are faster but struggle to provide valid confidence intervals or handle the "multiple comparisons" problem effectively in these high-dimensional spaces.

Methods

The authors introduce two main innovations to bypass the $O(p^2)$ bottleneck:

  1. Kernel Interaction Sampler (KIS): The authors prove that many hierarchical Bayesian models can be re-parameterized as a Gaussian Process (GP). Instead of sampling every interaction term, they run Markov chain Monte Carlo (MCMC) over a much smaller set of $O(p)$ hyperparameters. This reduces the per-iteration time complexity to $O(pN^2 + N^3)$, where $N$ is the number of observations.
  2. Kernel Interaction Trick (KIT): Even if you sample efficiently, reporting the results for all $p^2$ interactions is expensive. The authors show that you can recover the posterior mean and variance for any specific interaction term in $O(1)$ time by evaluating the GP at specific test points (like unit vectors), without ever explicitly calculating the full set of parameters.

They apply these tricks to a new model called SKIM (Sparse Kernel Interaction Model), which uses sparsity-inducing priors (similar to the horseshoe prior) to identify a small subset of important interactions while enforcing "strong hierarchy"—the idea that an interaction is only likely if its constituent "main effects" are also significant.

Table 1: Per-iteration MCMC runtime and memory scaling of methods for sampling two-way interactions. NAIVE refers to explicitly factorizing ΣN,τ to compute p(D | τ, σ2), WOODBURY refers to using the Woodbury identity and matrix determinant lemma to compute p(D | τ, σ2), and FULL refers to jointly sampling θ and τ. The third column provides the number of parameters sampled.

Datasets

The authors evaluated their approach using:

  • Synthetic Datasets: 36 different configurations varying the number of observations ($N$), dimensions ($p$), and signal-to-noise ratios to test variable selection quality.
  • Residential Building Data Set (UCI): A real-world dataset where covariates are highly correlated, used to test how the model handles complex data geometry.
  • Auto MPG Dataset (UCI): Used to demonstrate the model's robustness by adding hundreds of "fake" noise variables to see if the method could still correctly identify the true underlying interactions.

Key Insights and Ideas

  • The GP Duality: The "aha moment" is realizing that we don't need to represent interactions explicitly to learn about them. By working in the "weight-space" of a GP, the kernel function implicitly handles all $O(p^2)$ interactions.
  • Linear Scaling is Possible: By carefully choosing the kernel (specifically sums of polynomial kernels), the authors ensure the kernel evaluation itself stays linear in $p$.
  • Lazy Evaluation: The KIT allows for a "lazy" strategy. You can find the most important main effects first and then only query the posterior for interactions between those specific variables, saving massive amounts of memory.
  • Bayesian Shrinkage vs. Multiple Testing: The hierarchical prior naturally "shrinks" unimportant effects toward zero. This acts as an automatic correction for multiple comparisons, which is a major headache for frequentist methods in high dimensions.

Key Results

  • Speed and Memory: As shown in Figure 1, the KIS method scales linearly with $p$, whereas traditional "Naive" or "Woodbury" methods explode. For $p=10^5$, KIS remains tractable while baselines fail.
  • Accuracy: In synthetic tests, SKIM-KIS consistently provided lower Type I (false discovery) and Type II (missed discovery) errors compared to both standard LASSO and Hierarchical LASSO.
  • Robustness: On the Auto MPG dataset with added noise, SKIM correctly ignored "fake" interactions that led LASSO-based methods to report hundreds of false positives.
Empirical evaluation of (a) time and (b) memory scaling with dimension of marginal likelihood computation.

Limitations and Future Work

The primary limitation is the cubic scaling with $N$ ($O(N^3)$). While the method is "fast" relative to $p$, it becomes slow as the number of observations increases. The authors suggest that future work could integrate standard GP acceleration techniques, such as "inducing points," to reduce this $N^3$ dependence. Additionally, while the paper focuses on pairwise interactions, the authors provide a theoretical framework in the appendix for extending this to higher-order (3-way, 4-way) interactions.

Summary updated

Abstract

Discovering interaction effects on a response of interest is a fundamental problem faced in biology, medicine, economics, and many other scientific disciplines. In theory, Bayesian methods for discovering pairwise interactions enjoy many benefits such as coherent uncertainty quantification, the ability to incorporate background knowledge, and desirable shrinkage properties. In practice, however, Bayesian methods are often computationally intractable for even moderate-dimensional problems. Our key insight is that many hierarchical models of practical interest admit a particular Gaussian process (GP) representation; the GP allows us to capture the posterior with a vector of O(p) kernel hyper-parameters rather than O(p^2) interactions and main effects. With the implicit representation, we can run Markov chain Monte Carlo (MCMC) over model hyper-parameters in time and memory linear in p per iteration. We focus on sparsity-inducing models and show on datasets with a variety of covariate behaviors that our method: (1) reduces runtime by orders of magnitude over naive applications of MCMC, (2) provides lower Type I and Type II error relative to state-of-the-art LASSO-based approaches, and (3) offers improved computational scaling in high dimensions relative to existing Bayesian and LASSO-based approaches.
BibTeX
@inproceedings{agrawal2019kernel,
  author = {Raj Agrawal and Jonathan H. Huggins and Brian Trippe and Tamara Broderick},
  title = {{The Kernel Interaction Trick: Fast Bayesian Discovery of Pairwise Interactions in High Dimensions}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
}
Figure