# Random Intersection Chains

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 31 references that are in the map.
- First posted on arXiv 10 Apr 2021.

## Builds on (most cited first, 14 of 14)

- [Wide & Deep Learning for Recommender Systems](https://mlsanity.com/paper/1606.07792/) (2016)
- [DeepFM: A Factorization-Machine based Neural Network for CTR Prediction](https://mlsanity.com/paper/1703.04247/) (2017)
- [Deep & Cross Network for Ad Click Predictions](https://mlsanity.com/paper/1708.05123/) (2017)
- [AutoInt: Automatic Feature Interaction Learning via Self-Attentive Neural Networks](https://mlsanity.com/paper/1810.11921/) (2018)
- [xDeepFM: Combining Explicit and Implicit Feature Interactions for Recommender Systems](https://mlsanity.com/paper/1803.05170/) (2018)
- [Product-based Neural Networks for User Response Prediction](https://mlsanity.com/paper/1611.00144/) (2016)
- [Detecting Statistical Interactions from Neural Network Weights](https://mlsanity.com/paper/1705.04977/) (2017)
- [Towards Automated Neural Interaction Discovery for Click-Through Rate Prediction](https://mlsanity.com/paper/2007.06434/) (2020)
- [Feature Interaction Interpretability: A Case for Explaining Ad-Recommendation Systems via Neural Interaction Detection](https://mlsanity.com/paper/2006.10966/) (2020)
- [The Kernel Interaction Trick: Fast Bayesian Discovery of Pairwise Interactions in High Dimensions](https://mlsanity.com/paper/1905.06501/) (2019)
- [Model Selection for High Dimensional Quadratic Regression via Regularization](https://mlsanity.com/paper/1501.00049/) (2014)
- [Reluctant Interaction Modeling](https://mlsanity.com/paper/1907.08414/) (2019)
- [Random Intersection Trees](https://mlsanity.com/paper/1303.6223/) (2013)
- [The xyz algorithm for fast interaction search in high-dimensional data](https://mlsanity.com/paper/1610.05108/) (2016)

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

- [Online Interaction Detection for Click-Through Rate Prediction](https://mlsanity.com/paper/2106.15400/) (2021)

## Abstract (arXiv)

Interactions between several features sometimes play an important role in prediction tasks. But taking all the interactions into consideration will lead to an extremely heavy computational burden. For categorical features, the situation is more complicated since the input will be extremely high-dimensional and sparse if one-hot encoding is applied. Inspired by association rule mining, we propose a method that selects interactions of categorical features, called Random Intersection Chains. It uses random intersections to detect frequent patterns, then selects the most meaningful ones among them. At first a number of chains are generated, in which each node is the intersection of the previous node and a random chosen observation. The frequency of patterns in the tail nodes is estimated by maximum likelihood estimation, then the patterns with largest estimated frequency are selected. After that, their confidence is calculated by Bayes' theorem. The most confident patterns are finally returned by Random Intersection Chains. We show that if the number and length of chains are appropriately chosen, the patterns in the tail nodes are indeed the most frequent ones in the data set. We analyze the computation complexity of the proposed algorithm and prove the convergence of the estimators. The results of a series of experiments verify the efficiency and effectiveness of the algorithm.