Adversarial Attack on Large Scale Graph
This work addresses a bottleneck in making adversarial attacks practical for large-scale graph data, which is important for security and robustness in graph-based machine learning applications, though it is incremental as it builds on existing gradient-based methods.
The paper tackles the problem of adversarial attacks on graph neural networks (GNNs) being inefficient for large-scale graphs due to high time and space complexity, and proposes a Simplified Gradient-based Attack (SGA) method that uses a smaller subgraph to achieve significant time and memory efficiency improvements while maintaining competitive attack performance.
Recent studies have shown that graph neural networks (GNNs) are vulnerable against perturbations due to lack of robustness and can therefore be easily fooled. Currently, most works on attacking GNNs are mainly using gradient information to guide the attack and achieve outstanding performance. However, the high complexity of time and space makes them unmanageable for large scale graphs and becomes the major bottleneck that prevents the practical usage. We argue that the main reason is that they have to use the whole graph for attacks, resulting in the increasing time and space complexity as the data scale grows. In this work, we propose an efficient Simplified Gradient-based Attack (SGA) method to bridge this gap. SGA can cause the GNNs to misclassify specific target nodes through a multi-stage attack framework, which needs only a much smaller subgraph. In addition, we present a practical metric named Degree Assortativity Change (DAC) to measure the impacts of adversarial attacks on graph data. We evaluate our attack method on four real-world graph networks by attacking several commonly used GNNs. The experimental results demonstrate that SGA can achieve significant time and memory efficiency improvements while maintaining competitive attack performance compared to state-of-art attack techniques. Codes are available via: https://github.com/EdisonLeeeee/SGAttack.