Studying Adversarial Resilience over Graph Topology

Adversarial attacks to graph analytics are gaining increased attention. To date, two lines of countermeasures have been proposed to resist various graph adversarial attacks from the perspectives of either graph per se or graph neural networks. Nevertheless, a fundamental question lies in whether there exists an intrinsic adversarial resilience state within a graph regime and how to find out such a critical state if exists. This paper contributes to tackle the above research questions from three unique perspectives: i) we regard the process of adversarial learning on graph as a complex multi-object dynamic system, and model the behavior of adversarial attack; ii) we propose a generalized theoretical framework to show the existence of critical adversarial resilience state; and iii) we develop a condensed one-dimensional function to capture the dynamic variation of graph regime under adversarial perturbation, and pinpoint the critical state through solving the equilibrium point of adversarial perturbation-mapping function. Multi-facet experiments are conducted to show that the proposed approach can significantly outperform the state-of-the-art defense methods on five commonly-used real-world datasets.