  It has become cognitive inertia to employ cross-entropy loss function in
classification related tasks. In the untargeted attacks on graph structure, the
gradients derived from the attack objective are the attacker's basis for
evaluating a perturbation scheme. Previous methods use negative cross-entropy
loss as the attack objective in attacking node-level classification models.
However, the suitability of the cross-entropy function for constructing the
untargeted attack objective has yet been discussed in previous works. This
paper argues about the previous unreasonable attack objective from the
perspective of budget allocation. We demonstrate theoretically and empirically
that negative cross-entropy tends to produce more significant gradients from
nodes with lower confidence in the labeled classes, even if the predicted
classes of these nodes have been misled. To free up these inefficient attack
budgets, we propose a simple attack model for untargeted attacks on graph
structure based on a novel attack objective which generates unweighted
gradients on graph structures that are not affected by the node confidence. By
conducting experiments in gray-box poisoning attack scenarios, we demonstrate
that a reasonable budget allocation can significantly improve the effectiveness
of gradient-based edge perturbations without any extra hyper-parameter.

Machine Learning;Cryptography and Security