# Feature Cross Search via Submodular Optimization

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 36 references that are in the map.
- First posted on arXiv 5 Jul 2021.

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

- [Restricted Strong Convexity Implies Weak Submodularity](https://mlsanity.com/paper/1612.00804/) (2016)
- [AutoCross: Automatic Feature Crossing for Tabular Data in Real-World Applications](https://mlsanity.com/paper/1904.12857/) (2019)
- [Generalized Linear Rule Models](https://mlsanity.com/paper/1906.01761/) (2019)
- [Data Summarization at Scale: A Two-Stage Submodular Approach](https://mlsanity.com/paper/1806.02815/) (2018)
- [Categorical Feature Compression via Submodular Optimization](https://mlsanity.com/paper/1904.13389/) (2019)

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

- [Sequential Attention for Feature Selection](https://mlsanity.com/paper/2209.14881/) (2022)
- [Tackling Provably Hard Representative Selection via Graph Neural Networks](https://mlsanity.com/paper/2205.10403/) (2022)
- [Greedy PIG: Adaptive Integrated Gradients](https://mlsanity.com/paper/2311.06192/) (2023)

## Abstract (arXiv)

In this paper, we study feature cross search as a fundamental primitive in feature engineering. The importance of feature cross search especially for the linear model has been known for a while, with well-known textbook examples. In this problem, the goal is to select a small subset of features, combine them to form a new feature (called the crossed feature) by considering their Cartesian product, and find feature crosses to learn an accurate model. In particular, we study the problem of maximizing a normalized Area Under the Curve (AUC) of the linear model trained on the crossed feature column. First, we show that it is not possible to provide an n1/loglog n-approximation algorithm for this problem unless the exponential time hypothesis fails. This result also rules out the possibility of solving this problem in polynomial time unless mathsfP=mathsfNP. On the positive side, by assuming the naive assumption, we show that there exists a simple greedy (1-1/e)-approximation algorithm for this problem. This result is established by relating the AUC to the total variation of the commutator of two probability measures and showing that the total variation of the commutator is monotone and submodular. To show this, we relate the submodularity of this function to the positive semi-definiteness of a corresponding kernel matrix. Then, we use Bochner's theorem to prove the positive semi-definiteness by showing that its inverse Fourier transform is non-negative everywhere. Our techniques and structural results might be of independent interest.