Sparse but Strong: Crafting Adversarially Robust Graph Lottery Tickets
This work addresses the problem of adversarial robustness for sparse graph neural networks, which is important for applications requiring efficient and secure graph-based machine learning, though it is incremental as it builds on existing GLT concepts.
The paper tackles the vulnerability of Graph Lottery Tickets (GLTs) to adversarial structure perturbations by proposing an adversarially robust graph sparsification (ARGS) framework, which finds highly sparse GLTs that achieve competitive performance under various attacks, with evaluations showing significant robustness improvements even at high sparsity levels.
Graph Lottery Tickets (GLTs), comprising a sparse adjacency matrix and a sparse graph neural network (GNN), can significantly reduce the inference latency and compute footprint compared to their dense counterparts. Despite these benefits, their performance against adversarial structure perturbations remains to be fully explored. In this work, we first investigate the resilience of GLTs against different structure perturbation attacks and observe that they are highly vulnerable and show a large drop in classification accuracy. Based on this observation, we then present an adversarially robust graph sparsification (ARGS) framework that prunes the adjacency matrix and the GNN weights by optimizing a novel loss function capturing the graph homophily property and information associated with both the true labels of the train nodes and the pseudo labels of the test nodes. By iteratively applying ARGS to prune both the perturbed graph adjacency matrix and the GNN model weights, we can find adversarially robust graph lottery tickets that are highly sparse yet achieve competitive performance under different untargeted training-time structure attacks. Evaluations conducted on various benchmarks, considering different poisoning structure attacks, namely, PGD, MetaAttack, Meta-PGD, and PR-BCD demonstrate that the GLTs generated by ARGS can significantly improve the robustness, even when subjected to high levels of sparsity.