  With the great popularity of Graph Neural Networks (GNNs), their robustness
to adversarial topology attacks has received significant attention. Although
many attack methods have been proposed, they mainly focus on fixed-budget
attacks, aiming at finding the most adversarial perturbations within a fixed
budget for target node. However, considering the varied robustness of each
node, there is an inevitable dilemma caused by the fixed budget, i.e., no
successful perturbation is found when the budget is relatively small, while if
it is too large, the yielding redundant perturbations will hurt the
invisibility. To break this dilemma, we propose a new type of topology attack,
named minimum-budget topology attack, aiming to adaptively find the minimum
perturbation sufficient for a successful attack on each node. To this end, we
propose an attack model, named MiBTack, based on a dynamic projected gradient
descent algorithm, which can effectively solve the involving non-convex
constraint optimization on discrete topology. Extensive results on three GNNs
and four real-world datasets show that MiBTack can successfully lead all target
nodes misclassified with the minimum perturbation edges. Moreover, the obtained
minimum budget can be used to measure node robustness, so we can explore the
relationships of robustness, topology, and uncertainty for nodes, which is
beyond what the current fixed-budget topology attacks can offer.
