LightCS: Selecting Quadratic Feature Crosses in Linear Complexity
Zhaocheng Du, Junhao Chen, Qinglin Jia, Chuhan Wu, Jieming Zhu, Zhenhua Dong, Ruiming Tang · 2024
Feature crosses, which represent joint features synthesized by two single features, are critical for deep recommender systems to model sophisticated feature relations. In practice, only a tiny fraction of feature crosses among massive possible ones are informative, while introducing irrelevant or noisy ones may increase online service latency and boost the risk of overfitting. Therefore, picking high-quality feature crosses is essential in practical recommender systems. However, even for selecting quadratic feature crosses, existing algorithms still incur either o(n2) time complexity or o(n2) space complexity, which is inefficient and unscalable in industrial scenarios. In this paper, we present an efficient and accurate quadratic feature cross selection method with both linear time and space complexity. Motivated by the idea of Quasi-Newton methods, we propose to use 2nd-order derivative matrix to evaluate all theoretically possible feature crosses concurrently without the need of constructing them explicitly, where an approximation of 2nd-order gradient is applied to guarantee both low time and space complexity. Furthermore, we decouple the feature crosses' novelty from single features' joint importance. Experiments on two public recommendation datasets and a private dataset validate the efficiency and effectiveness of our method, and it has also become a fundamental feature cross selection tool used by Huawei Ads Platform.