  Graph edge perturbations are dedicated to damaging the prediction of graph
neural networks by modifying the graph structure. Previous gray-box attackers
employ gradients from the surrogate model to locate the vulnerable edges to
perturb the graph structure. However, unreliability exists in gradients on
graph structures, which is rarely studied by previous works. In this paper, we
discuss and analyze the errors caused by the unreliability of the structural
gradients. These errors arise from rough gradient usage due to the discreteness
of the graph structure and from the unreliability in the meta-gradient on the
graph structure. In order to address these problems, we propose a novel attack
model with methods to reduce the errors inside the structural gradients. We
propose edge discrete sampling to select the edge perturbations associated with
hierarchical candidate selection to ensure computational efficiency. In
addition, semantic invariance and momentum gradient ensemble are proposed to
address the gradient fluctuation on semantic-augmented graphs and the
instability of the surrogate model. Experiments are conducted in untargeted
gray-box poisoning scenarios and demonstrate the improvement in the performance
of our approach.
