EvA: Evolutionary Attacks on Graphs
This work addresses security vulnerabilities in graph neural networks for applications like social networks or recommendation systems, offering a more effective attack method that is incremental in improving adversarial robustness.
The paper tackles the problem of graph neural networks being vulnerable to structural perturbations by introducing an evolutionary-based attack method that directly solves the discrete optimization problem, resulting in an average 11% additional drop in accuracy compared to previous attacks.
Even a slight perturbation in the graph structure can cause a significant drop in the accuracy of graph neural networks (GNNs). Most existing attacks leverage gradient information to perturb edges. This relaxes the attack's optimization problem from a discrete to a continuous space, resulting in solutions far from optimal. It also restricts the adaptability of the attack to non-differentiable objectives. Instead, we introduce a few simple yet effective enhancements of an evolutionary-based algorithm to solve the discrete optimization problem directly. Our Evolutionary Attack (EvA) works with any black-box model and objective, eliminating the need for a differentiable proxy loss. This allows us to design two novel attacks that reduce the effectiveness of robustness certificates and break conformal sets. The memory complexity of our attack is linear in the attack budget. Among our experiments, EvA shows $\sim$11\% additional drop in accuracy on average compared to the best previous attack, revealing significant untapped potential in designing attacks.