Scalable Adversarial Attack on Graph Neural Networks with Alternating
  Direction Method of Multipliers
  Graph neural networks (GNNs) have achieved high performance in analyzing
graph-structured data and have been widely deployed in safety-critical areas,
such as finance and autonomous driving. However, only a few works have explored
GNNs' robustness to adversarial attacks, and their designs are usually limited
by the scale of input datasets (i.e., focusing on small graphs with only
thousands of nodes). In this work, we propose, SAG, the first scalable
adversarial attack method with Alternating Direction Method of Multipliers
(ADMM). We first decouple the large-scale graph into several smaller graph
partitions and cast the original problem into several subproblems. Then, we
propose to solve these subproblems using projected gradient descent on both the
graph topology and the node features that lead to considerably lower memory
consumption compared to the conventional attack methods. Rigorous experiments
further demonstrate that SAG can significantly reduce the computation and
memory overhead compared with the state-of-the-art approach, making SAG
applicable towards graphs with large size of nodes and edges.
