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

arXiv: https://arxiv.org/abs/1905.06501 · HTML: https://mlsanity.com/paper/1905.06501/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 May 2019.

## Built on by (most cited first, 10 of 10)

- [Improved Random Features for Dot Product Kernels](https://mlsanity.com/paper/2201.08712/) (2022)
- [The Shrinkage-Delinkage Trade-off: An Analysis of Factorized Gaussian Approximations for Variational Inference](https://mlsanity.com/paper/2302.09163/) (2023)
- [Variational Inference in Location-Scale Families: Exact Recovery of the Mean and Correlation Matrix](https://mlsanity.com/paper/2410.11067/) (2024)
- [Discovering Categorical Main and Interaction Effects Based on Association Rule Mining](https://mlsanity.com/paper/2104.04728/) (2021)
- [The SKIM-FA Kernel: High-Dimensional Variable Selection and Nonlinear Interaction Discovery in Linear Time](https://mlsanity.com/paper/2106.12408/) (2021)
- [Generalized Guarantees for Variational Inference in the Presence of Even and Elliptical Symmetry](https://mlsanity.com/paper/2511.01064/) (2025)
- [Random Intersection Chains](https://mlsanity.com/paper/2104.04714/) (2021)
- [Online Interaction Detection for Click-Through Rate Prediction](https://mlsanity.com/paper/2106.15400/) (2021)
- [Corrected Integrated Laplace Approximation for Bayesian Inference in Latent Gaussian Models](https://mlsanity.com/paper/2605.20345/) (2026)
- [PliableBVS: A flexible Bayesian variable selection method for modeling interactions with mandatory modifying variables](https://mlsanity.com/paper/2606.02017/) (2026)

## Abstract (arXiv)

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.