Robust Classification.pdf

Collective learning methods, such as Associative Markov Networks (AMN), exploit relations among data points to enhance classification performance. However, these relations expose an extra attack surface to adversaries, who can modify the graph structure at test time to reduce classification accuracy.

Approach: The problem of learning robust AMN is formulated as a bi-level program, where the inner optimization problem involves optimal structural attacks (adding or deleting edges). To address the technical challenge of non-linear integer programming, the inner adversarial optimization is relaxed, and duality is used to obtain a convex quadratic upper bound for the robust AMN problem.

Key Results:

An approximation bound is exhibited for the adversarial problem.
An approximation bound is established for the solutions of the approximate robust AMN approach.
Experimental results demonstrate the efficacy of the approach on real datasets, showing that robust AMN degrades gracefully under structural attacks, preserving the advantages of using relational information in classification.
Robust AMN is compared to a Graph Convolutional Network (GCN) classifier in a transductive learning setting under a structural attack, and is found to be significantly more robust than GCN, while being nearly as accurate as GCN on non-adversarial data.

Related Work: The work falls into the realm of learning robust classifiers against decision-time reliability attacks, with a focus on defending against structural attacks that exploit relations among data points. Prior work on robust learning has primarily considered settings that treat data independently, while this work addresses the vulnerability and robustness of collective learning models to structural attacks.