Robustness Verification of Deep Graph Neural Networks Tightened by Linear Approximation

Recent research indicates that adding residual connections in Graph Neural Networks (GNNs) would amplify susceptibility to anomalous nodes, consequently undermining the robustness of deep GNNs in practical settings. However, existing verification methods encounter challenges with the increasing number of parameters and computational overhead in deep GNNs. In this paper, we derive the general form of the residual connections and apply the dual backpropagation network to deep GNNs. Considering the heightened computational errors arising from the increased number of layers in deep GNNs, we propose a new method for calculating intermediate activation bounds of GNNs based on linear approximation. Experimental results show that new method can effectively enhance the verification accuracy. Notably, the maximum perturbation value of nodes correctly classified shows an average improvement of 119.5%. To showcase the the efficacy and scalability of our method, we verify robustness of deep GNNs on six different graph datasets, and our method can effectively verify the robustness of deep GNNs even with 32 layers of residual connections, i.e. verify over 87.29% of nodes in the Citeseer dataset. Furthermore, we analyse the influence of the graph structural properties on the robustness of the model.