Certifiable Robustness to Discrete Adversarial Perturbations for Factorization Machines

Factorization machines (FMs) have been widely adopted to model the discrete feature interactions in recommender systems. Despite their great success, currently there is no study of their robustness to discrete adversarial perturbations. Whether modifying a certain number of the discrete input features has a dramatic effect on the FM's prediction? Although there exist robust training methods for FMs, they neglect the discrete property of input features and lack of an effective mechanism to verify the model robustness.

In our work, we propose the first method for the certifiable robustness of factorization machines with respect to the discrete perturbation on input features. If an instance is certifiably robust, it is guaranteed to be robust (under the considered space) no matter what the perturbations and attack models are. Likewise, we provide non-robust certificates via the existence of discrete adversarial perturbations that change the FM's prediction. Through such robustness certificates, we show that FMs and the current robust training methods are vulnerable to discrete adversarial perturbations. The vulnerability makes the outcome unreliable and restricts the application of FMs. To enhance the FM's robustness against such perturbations, a robust training procedure is presented whose core idea is to increase the number of instances that are certifiably robust. Extensive experiments on three real-world datasets demonstrate that our method significantly enhances the robustness of the factorization machines with little impact on predictive accuracy.