  Graph Neural Networks(GNNs) are vulnerable to adversarial attack that cause
performance degradation by adding small perturbations to the graph.
Gradient-based attacks are one of the most commonly used methods and have
achieved good performance in many attack scenarios. However, current gradient
attacks face the problems of easy to fall into local optima and poor attack
invisibility. Specifically, most gradient attacks use greedy strategies to
generate perturbations, which tend to fall into local optima leading to
underperformance of the attack. In addition, many attacks only consider the
effectiveness of the attack and ignore the invisibility of the attack, making
the attacks easily exposed leading to failure. To address the above problems,
this paper proposes an attack on GNNs, called AGSOA, which consists of an
average gradient calculation and a structre optimization module. In the average
gradient calculation module, we compute the average of the gradient information
over all moments to guide the attack to generate perturbed edges, which
stabilizes the direction of the attack update and gets rid of undesirable local
maxima. In the structure optimization module, we calculate the similarity and
homogeneity of the target node's with other nodes to adjust the graph structure
so as to improve the invisibility and transferability of the attack. Extensive
experiments on three commonly used datasets show that AGSOA improves the
misclassification rate by 2$\%$-8$\%$ compared to other state-of-the-art
models.
