Simple and Efficient Partial Graph Adversarial Attack: A New Perspective
Guanghui Zhu Mengyu Chen Chunfeng Yuan Yihua Huang
As the study of graph neural networks becomes more intensive and
comprehensive, their robustness and security have received great research
interest. The existing global attack methods treat all nodes in the graph as
their attack targets. Although existing methods have achieved excellent
results, there is still considerable space for improvement. The key problem is
that the current approaches rigidly follow the definition of global attacks.
They ignore an important issue, i.e., different nodes have different robustness
and are not equally resilient to attacks. From a global attacker's view, we
should arrange the attack budget wisely, rather than wasting them on highly
robust nodes. To this end, we propose a totally new method named partial graph
attack (PGA), which selects the vulnerable nodes as attack targets. First, to
select the vulnerable items, we propose a hierarchical target selection policy,
which allows attackers to only focus on easy-to-attack nodes. Then, we propose
a cost-effective anchor-picking policy to pick the most promising anchors for
adding or removing edges, and a more aggressive iterative greedy-based attack
method to perform more efficient attacks. Extensive experimental results
demonstrate that PGA can achieve significant improvements in both attack effect
and attack efficiency compared to other existing graph global attack methods.