Robust Collective Classification against Structural Attacks
This addresses the vulnerability of collective learning systems to structural attacks, which is an incremental improvement for security in graph-based machine learning.
The paper tackles the problem of adversarial robustness in collective classification methods, specifically for Associative Markov Networks (AMN), by developing a robust learning approach against structural attacks that modify graph edges at test time. The result shows that robust AMN is much more robust than state-of-the-art deep learning methods while sacrificing little accuracy on non-adversarial data.
Collective learning methods exploit relations among data points to enhance classification performance. However, such relations, represented as edges in the underlying graphical model, expose an extra attack surface to the adversaries. We study adversarial robustness of an important class of such graphical models, Associative Markov Networks (AMN), to structural attacks, where an attacker can modify the graph structure at test time. We formulate the task of learning a robust AMN classifier as a bi-level program, where the inner problem is a challenging non-linear integer program that computes optimal structural changes to the AMN. To address this technical challenge, we first relax the attacker problem, and then use duality to obtain a convex quadratic upper bound for the robust AMN problem. We then prove a bound on the quality of the resulting approximately optimal solutions, and experimentally demonstrate the efficacy of our approach. Finally, we apply our approach in a transductive learning setting, and show that robust AMN is much more robust than state-of-the-art deep learning methods, while sacrificing little in accuracy on non-adversarial data.