FIVES: Feature Interaction Via Edge Search for Large-Scale Tabular Data

We consider the ubiquitous tabular data where each column represents a feature and each row represents a sample. Without loss of generality, we assume that numeric features have been discretized and thus all considered features are categorical ones, for example, feature “user city” takes value from $\{\text{New York},\text{London},\ldots\}$, and feature “user age” takes value from $\{\text{under}\;10,10\;\text{to}\;20,\ldots\}$. Based on these, we first define the high-order interactive feature:

Since the interactive features bring in non-linearity, e.g., the Cartesian product of two binary features enables a linear model to predict the label of their XOR relation, they are widely adopted to improve the performance of machine learning methods on tabular data. The goal of interactive feature generation is to find a set $\mathcal{F}=\{f_{1}^{k_{1}},f_{2}^{k_{2}},\ldots,f_{n}^{k_{n}}\}$ of such interactive features. To evaluate the usefulness of generated interactive features, we measure the performance improvements introduced by the generated features. Following the majority of literature (Liu et al., 2020b; Luo et al., 2019; Li et al., 2019), we take the CTR prediction as an application scenario where the usefulness can be measured by the AUC improvements. The interactive feature generation task distinguishes from a standard classification task in its emphasis on identifying the useful interactive features that can be fed into other components of machine learning pipelines, including but not limited to other models, data preprocessing, result post-explanations.

As the number of all possible interactions from $m$ original features is $O(2^{m})$, it is challenging to search for the optimal set of interactive features from such a huge space, not to mention the evaluation of a proposed feature can be costly and noisy. Thus some recent methods model the search procedure as the optimization of designed DNNs, transforming it into a one-shot training at the cost of interpretability. In the rest of this section, we present our proposed method—FIVES, which can provide explicit interaction results via an efficient differentiable search.

As aforementioned, exhaustively traversal of the exponentially growing interactive feature space seems intractable. By Definition 2.1, any $k$-order interactive features could be regarded as the interaction (i.e., Cartesian product) of several lower-order features, with many choices of the decomposition. This raises a question that could we solve the task of generating interactive features in a bottom-up manner? To be specific, could we generate interactive features in an inductive manner, that is, searching for a group of informative $k$-order features from the interactions between original features and the group of $(k-1)$-order features identified in previous step? We present the following proposition to provide theoretical evidence for discussing the question.

We defer the proof to Appendix A. Specifically, the random variable $X$ and $Y$ stands for the feature and the label respectively, and the joint of $X$s stands for their interaction. Recall that: 1) As the considered raw features are categorical, modeling each feature as a Bernoulli random variable would not sacrifice much generality; 2) In practice, the raw features are preprocessed to remove redundant ones, so the weak correlation assumption holds. Based on these, our proposition indicates that, for small $\rho$ we have $\log(2\rho^{2}+1)\approx 0$, thereby the information gain introduced by interaction of features is at most that of the individuals. This proposition therefore could be interpreted as—under practical assumptions, it is unlikely to construct an informative feature from the interaction of uninformative ones. This proposition supports the bottom-up search strategy, as lower-order features that have not been identified as informative are less likely to be a useful building brick of high-order features. Besides, the identified $(k-1)$-order features are recursively constructed from the identified ones of lower-orders, and thus they are likely to include sufficient information for generating informative $k$-order features. We also empirically validate this strategy in Section 3.2 and Section 3.4. Although this inductive search strategy cannot guarantee to generate all useful interactive features, the generated interactive features in such a way are likely to be useful ones, based on the above proposition. This can be regarded as a trade-off between the usefulness of generated interactive features and the completeness of them, under the constraint of limited computation resources.

To instantiate our inductive search strategy, we conceptually regard the original features as a feature graph and model the interactions among features by a designed GNN.

First, we denote the feature graph as $G=(\mathcal{N},\mathcal{E})$ where each node $n_{i}\in\mathcal{N}$ corresponds to a feature $f_{i}$ and each edge $e_{i,j}\in\mathcal{E}$ indicates an interaction between node $n_{i}$ and node $n_{j}$. We use $\mathbf{n}_{i}^{(0)}$ as the initial node representation for node $n_{i}$ that conventionally takes the embedding looked up by $f_{i}$ from the feature embedding matrix $\mathbf{W}_{F}$ as its value. It is easy to show that, by applying a vanilla graph convolutional operator to such a graph, the output $\mathbf{n}_{i}^{(1)}$ is capable of expressing the $2$-order interactive features. However, gradually propagating the node representations with only one adjacency matrix fails to express higher-order ($k>2$) interactions. Thus, to generate at highest $K$-order interactive features, we extend the feature graph by defining an adjacency tensor $\mathbf{A}\in\{0,1\}^{K\times m\times m}$ to indicate the interactions among features at each order, where each slice $\mathbf{A}^{(k)}\in\{0,1\}^{m\times m},k=0,\ldots,(K-1)$ represents a layer-wise adjacency matrix and $m=|\mathcal{N}|$ is the number of original features (nodes). Once an entry $\mathbf{A}^{(k)}_{i,j},i,j\in{1,\ldots,m}$ is active, we intend to generate a $(k+1)$-order feature based on node $n_{i}$ by $\mathbf{n}_{i}^{(k-1)}\odot\mathbf{n}_{j}^{(0)}$ and synthesize these into $\mathbf{n}_{i}^{(k)}$. Formally, with an adjacency tensor $\mathbf{A}$, our dedicated graph convolutional operator produces the node representations layer-by-layer, in the following way:

Here “MEAN” is adopted as the aggregator, and $\odot$ denotes the element-wise product. $\mathbf{W}_{j}$ is the transformation matrix for node $n_{j}$, and $n^{(0)}_{i}$ is the initial input to the GNN and described as the feature embeddings of node $n_{i}$. Assume that the capacity of our GNN and embedding matrix is sufficient for $(\mathbf{W}_{j}\mathbf{n}_{j}^{(0)})\odot\mathbf{n}_{i}^{(0)}$ to express $f_{i}\otimes f_{j}$, we can show that the node representation at $k$-th layer $\mathbf{n}^{(k)}=[\mathbf{n}_{1}^{(k)},\ldots,\mathbf{n}_{m}^{(k)}]$ corresponds to the generated $(k+1)$-order interactive features:

where the choices of which features should be combined are determined by the adjacency tensor $\mathbf{A}$.

As shown above, the feature graph and the associated GNN is capable of conceptually expressing our inductive search strategy. Thus from the perspective of feature graph, the task of generating interactive features is equivalent to learning an optimal adjacency tensor $\mathbf{A}$, so-called edge search in our study. In order to evaluate the quality of generated features, i.e., the learned adjacency tensor $\mathbf{A}$, we apply a linear output layer to the concatenation of node representations at each layer:

where $\mathbf{W}^{(k)}$ and $b^{(k)}$ are the projection matrix and bias term respectively, and $\sigma(\cdot)$ denotes the sigmoid function. We pack all the parameters as $\mathbf{\Theta}=(\mathbf{W}_{F},\mathbf{W}^{(k)},b^{(k)},\mathbf{W}_{j}|0\leq k<K,1\leq j\leq m)$. Then we define a cross-entropy loss function (denoted as CE) for the joint of $\mathbf{A}$ and $\mathbf{\Theta}$:

where $\mathcal{D}$ is the considered dataset, $y_{i}$ denotes the ground truth label of $i$-th instance from $\mathcal{D}$, and $\hat{y}_{i}^{(k)}$ denotes its prediction based on the node representations from $k$-th layer.

Eventually, the edge search task could be formulated as a bilevel optimization problem:

where $\mathcal{D}_{\text{train}}$ and $\mathcal{D}_{\text{val}}$ denote the training and the validation dataset respectively. Such a nested formulation in Eq. (5) has also been studied recently in differentiable NAS (Liu et al., 2019; Cai et al., 2019; Noy et al., 2019), where the architecture parameters ($\mathbf{A}$ in our formulation) and network parameters ($\mathbf{\Theta}$ in our formulation) are alternatively updated during the search procedure. However, most of NAS methods ignored the dependencies among architecture parameters (Zhou et al., 2019), which are critical for our task as the higher-order interactive features are generated based on the choice of previous layers.

Directly solving the optimization problem in Eq. (5) is intractable because of its bilevel nature and the binary values of $\mathbf{A}$. Existing methods AutoInt (Song et al., 2019) and Fi-GNN (Li et al., 2019) tackle the issue of binary $\mathbf{A}$ by calculating it on-the-fly, that is, the set of features to be aggregated for interaction is determined by a self-attention layer. This solution enables efficient optimization, but the attention weights dynamically change from sample to sample. Thus it is hard to interpret these attention weights to know which interactive features should be generated. On the other hand, there are some straightforward ways to learn a stationary adjacency tensor. To be specific, we can regard $\mathbf{A}$ as Bernoulli random variables parameterized by $\mathbf{H}\in[0,1]^{K\times m\times m}$. Then, in the forward phase, we sample each slice $\mathbf{A}^{(k)}\sim\Pr(\cdot|\mathbf{H}^{(k)})$; and in the backward phase, we update $\mathbf{H}$ based on straight-through estimation (STE) (Bengio et al., 2013b). This technique has also been adopted for solving problems like Eq. (5) in some NAS studies (Cai et al., 2019).

Following the search strategy in Section 2.2, the adjacency tensor $\mathbf{A}$ should be determined slice-by-slice from $0$ to $(K-1)$. In addition, since that which $k$-order features should be generated depend on those $(k-1)$-order features have been generated, the optimization of $\mathbf{A}^{(k)}$ should be conditioned on $\mathbf{A}^{(k-1)}$. Our inductive search strategy would be precisely instantiated, only when such dependencies are modeled. Thus, we parameterize the adjacency tensor $\mathbf{A}$ by $\mathbf{H}\in\mathbb{R}^{K\times m\times m}$ in this recursive way:

where $\varphi(\cdot)$ is a binarization function with a tunable threshold, and $\mathbf{D}^{(k-1)}$ is the degree matrix of $\mathbf{A}^{(k-1)}$ serving as a normalizer.

We illustrate the intuition behind Eq. (6) in Figure 1. Specifically, if we regard each $(k+1)$-order interactive feature, e.g., $f_{i}\otimes\cdots\otimes f_{j}$ as a $k$-hop path jumping from $n_{i}$ to $n_{j}$, then $\mathbf{A}^{(k)}$ can be treated as a binary sample drawn from the $k$-hop transition matrix where $\mathbf{A}_{i,j}^{(k)}$ indicates the $k$-hop visibility (or say accessibility) from $n_{i}$ to $n_{j}$. Conventionally, the transition matrix of $k$-hop can be calculated by multiplying that of $(k-1)$-hop with the normalized adjacency matrix. Following the motivation of defining an adjacency tensor such that the topological structures at different layers tend to vary from each other, we design $\sigma(\mathbf{H}^{(k)})$ as a layer-wise (unnormalized) transition matrix. In this way, with Eq. (6), we make the adjacency matrix of each layer depend on that of previous layer, which exactly instantiates our search strategy.

Since there is a binarization function in Eq. (6), $\mathbf{H}$ cannot be directly optimized via a differentiable way w.r.t. the loss function in Eq. (4). One possible solution is to use policy gradient (Sutton et al., 2000), Gumbel-max trick (Jang et al., 2017), or other approximations (Nayman et al., 2019). However, it can be inefficient when the action space (here the possible interactions) is too large.

To make the optimization more efficient, we allow to use a soft $\mathbf{A}^{(k)}$ for propagation at the $k$-th layer, while the calculation of $\mathbf{A}^{(k)}$ still depends on a binarized $\mathbf{A}^{(k-1)}$:

However, the entries of an optimized $\mathbf{A}$ may still lie near the borderline (around $0.5$). When we use these borderline values for generating interactive features, the gap between the binary decisions and the learned $\mathbf{A}$ cannot be neglected (Noy et al., 2019). To fill this gap, we re-scale each entry of $\mathbf{A}^{(k)}$ through dividing it by a temperature $\tau$ before using it for propagation, which can be formatted as:

where $A^{(k)}_{i,j}$ denotes the entry of $\mathbf{A}^{(k)}$. As $\tau$ anneals from $1$ to a small value, e.g., $0.02$ along the search phase, the re-scaled value becomes close to either $0$ or $1$.

Finally, our modeling allows us to solve the optimization problem in Eq. (5) with gradient descent method. The whole optimization algorithm is summarized in Algorithm 1.

By Algorithm 1, the adjacency tensor $\mathbf{A}$ and the model parameters $\mathbf{\Theta}$ are learned and can solely serve as a predictive model. Moreover, one can derive useful high-order interactive features according to the learned adjacency tensor $\mathbf{A}$, which means that FIVES can also serve as a feature generator. In general, we are allowed to specify layer-wise thresholds for binarizing the learned $\mathbf{A}$ and then derive the useful $k$-order ($1\leq k\leq K$) interactive features suggested by $\mathbf{A}$ inductively. An example of the interactive feature derivation is shown in Figure 2.

Specifically, given an adjacency matrix $\mathbf{A}^{(k)}$, which is the $k$-th slice of the binarized adjacency tensor $\mathbf{A}$, we can determine the feature graph (denoted as “Feature Graph” in the figure) at the $k$-th layer based on it, where $\mathbf{A}^{(k)}_{i,j}=1$ represents there exists a directed edge from the start node $n_{i}$ to the end node $n_{j}$. Then, we can derive useful interactive features (denoted as “Generated Features” in the figure) from the feature graphs layer-by-layer in an inductively manner. At each layer, a directed edge means to apply the crossing operation (i.e., $\otimes$) between each of the features represented by the start node and that represented by the end node, which generates some interactive features. As defined in Eq. (2), the features represented by a node are different when it serves as a start node or an end node. At the $k$-th layer, when a node $n_{i}$ serves as a start node, it represents the interactive features that have been generated by the edges starting from $n_{i}$ at the $(k-1)$-th order; elsewise, it just represents the corresponding original feature $f_{i}$. Particularly, when $k=1$, no matter a node serves as a start node or an end node, it represents the corresponding original feature.

Take the instance in Figure 2 as an example: In the middle column, $n_{4}$ is an end node in the connection $n_{1}\rightarrow n_{4}$, thus it represents the original feature $f_{4}$; In the right column, $n_{4}$ is a start node in the connection $n_{4}\rightarrow n_{3}$, thus it represents the interactive feature $f_{4}\otimes f_{2}$, which is propagated from crossing in the previous order. The generated interactive features via crossing at each layer are synthesized in the start node and propagated to the next layer. The edge and propagation are denoted as the dotted frames and dotted arrows in different colors respectively in the figure.

Formally, the useful interactive features suggested by FIVES can be given as $\{f_{c_{1}}\otimes\cdots\otimes f_{c_{k}}\otimes f_{i}|\exists c_{1},\ldots,c_{k},\text{ s.t. }\mathbf{A}_{i,c_{j}}^{(j)}=1,j=1,\ldots,k$}.

As mentioned in Section 2.4, the learned $(\mathbf{A},\mathbf{\Theta})$ of FIVES is a predictive model by itself. We adopt the following methods as baselines, including those frequently used in practical recommender systems and state-of-the-art feature generation methods: (1) LR: Logistic Regression with only the original features (more settings of LR will be given in next part). (2) DNN: The standard Deep Neural Network with fully connected cascade and a output layer with sigmoid function. (3) FM (Rendle, 2010): The factorization machine uses the inner product of two original features to express their interactions. (4) Wide&Deep (Cheng et al., 2016): This method jointly trains wide linear models and deep neural networks. (5) AutoInt (Song et al., 2019): A DNN-based feature generation method, in which the multi-head self-attentive neural network with residual connections is proposed to model feature interactions. (6) Fi-GNN (Li et al., 2019): It proposes to represent the multi-field features as a graph structure for the first time, and the interactions of features are modeled as the attentional edge weights. The implementation details of these methods can be found in Appendix C.

After hyperparameter optimization for all methods (see supplementary material for details), we use the optimal configuration to run each method for 10 times and conduct independent t-test between the results of FIVES and the strongest baseline method to show the significance: “$\ast\ast$” represents $p<0.01$ and “$\ast$” represents $p<0.05$. The experimental results are summarized in Table  2.

The experimental results demonstrate that FIVES can significantly improve the performance compared to baselines on most datasets. Especially on the large-scale datasets, FIVES outperforms all other baseline methods by a considerable large margin.

In practice, the generated interactive features are often used to augment original features, and then all of them are fed into some lightweight models to meet the requirement of inference speed. In specific, we adopt LR as the basic model to compare the usefulness of the interactive features discovered by different methods. It is worth pointing out that LR is widely adopted for such experiments in this area (Luo et al., 2019; Rosales et al., 2012; Lian et al., 2018), since it is simple, scalable, and interpretable.

As aforementioned, we can explicitly derive useful interactive features from the learned adjacency tensor $\mathbf{A}$. We call this method FIVES+LR and compare it with the following methods: (1) Random+LR: LR with original features and randomly selected interactive features; (2) CMI+LR: conditional mutual information (CMI) as a filter to select useful interactive features from all possible $2$-order interactions; (3) AutoCross+LR (Luo et al., 2019): a recent search-based method, which performs beam search in a tree-structured space. We also run the experiments for 10 times and analyze the results by t-test to draw statistically significant conclusions. The results are summarized in Table 3.

On all the datasets, the interactive features FIVES indicated consistently improve the performance of a LR. The improvements are larger than that of other search-based method on most datasets, which is particularly significant on the largest one (i.e., Criteo). The degeneration of some reference methods may be caused by redundant features that harden the optimization of a LR.

The above experiments evaluate the usefulness of the interactive features generated by FIVES from the perspective of augmenting the feature set for lightweight models. Here, we further evaluate the usefulness of generated features from more different perspectives.

First, we can directly calculate the AUCs of making predictions by each interactive feature. Then we plot the features as points in Figure 5, with the value of their entries $\mathbf{A}_{i,j}^{(k)}$ as x-axis and corresponding AUC values as y-axis, which illustrates a positive correlation between $\mathbf{A}_{i,j}^{(k)}$ and the feature’s AUC. This correlation confirms that the generated interactive features are indeed useful.

Another way to assess the usefulness of generated features is to compare different choices of the adjacency tensor $\mathbf{A}$. From the view of NAS, $\mathbf{A}$ acts as the architecture parameters. If it represents a useful architecture, we shall achieve satisfactory performance by tuning the model parameters $\mathbf{\Theta}$ w.r.t. it. Specifically, we can fix a well learned $\mathbf{A}$ and learn just the predictive model parameters $\mathbf{\Theta}$. We consider the following different settings: (1) $\mathbf{\Theta}$ is learned from scratch (denoted as LFS); (2) $\mathbf{\Theta}$ is fine-tuned with the output of Algorithm 1 as its initialization (denoted as FT). We also show the performance of a random architecture (i.e., $\mathbf{A}$ is random initialized and will not be optimized) as the baseline (denoted as Random).

The experimental results in Figure 6 show the advantage of the searched architecture against a random one. Since the architecture parameter $\mathbf{A}$ indicates which interactive features should be generated, the effectiveness of searched architecture confirms the usefulness of generated interactive features. On the contrary, the randomly generated interactions can degrade the performance, especially when the original feature is relatively scarce, e.g., on Employee dataset. Meanwhile, the improvement from “FIVES” to “FT” shows that, given a searched architecture (i.e., learned $\mathbf{A}$), improvement for predictive performance can be achieved via fine-tuning $\mathbf{\Theta}$.

To study the efficiency of the proposed method, we empirically compare it against other DNN-based methods in terms of both convergence rate and run-time per epoch. As Figure 7 shows, although we formulate the edge search task as a bilevel optimization problem, FIVES achieves comparable validation AUC at each different number of training steps, which indicates a comparable convergence rate. Meanwhile, the run-time per epoch of all the DNN-based methods is at the same order, even though, the run-time per epoch of both Fi-GNN and FIVES is relatively larger than that of others due to the complexity of graph convolutional operator. Actually, with 4 Nvidia GTX1080Ti GPU cards, FIVES can complete its search phase on Criteo (traversal of 3 epochs) within $2$ hours. In contrast, both dozens of hours and hundreds of times of computational resources are needed for search-based methods due to their trial-and-error nature.

We conduct an online A/B testing for one week on a leading e-commerce platform, Tabobao, to verify the effectiveness of FIVES. Specifically, we first train FIVES on the training data collected from search logs, and then derive the top 5 interactive features with the highest probability according to the learned adjacency tensor $\mathbf{A}$ (please refer to Section 2.5 for the derivation process). The interactive features generated by FIVES are deployed on the online serving system, so that the deployed CTR prediction models (of various architectures) are fed with these features, which eventually affect the ranking of items. The one-week observations show that the interactive features provided by FIVES contributes 0.42% pCTR (page click-through rate, i.e., the ratio of page clicks and page views) and 0.28% uCTR (user click-through rate, i.e., the ratio of user clicks and user views) improvements in the online A/B testing, which demonstrates the effectiveness of FIVES for real-world e-commerce platforms.

Moreover, we deploy FIVES as AI utilities on Alibaba Cloud¹¹1https://cn.aliyun.com/product/bigdata/product/learn to empower a broader range of real-world businesses. The data scientists from both Alibaba and the customers of Alibaba Cloud who want to generate useful interactive features can benefit from our proposed FIVES, especially those who demand for the interpretability of generated features.