  Adversarial attacks on Graph Neural Networks (GNNs) reveal their security
vulnerabilities, limiting their adoption in safety-critical applications.
However, existing attack strategies rely on the knowledge of either the GNN
model being used or the predictive task being attacked. Is this knowledge
necessary? For example, a graph may be used for multiple downstream tasks
unknown to a practical attacker. It is thus important to test the vulnerability
of GNNs to adversarial perturbations in a model and task agnostic setting. In
this work, we study this problem and show that GNNs remain vulnerable even when
the downstream task and model are unknown. The proposed algorithm, TANDIS
(Targeted Attack via Neighborhood DIStortion) shows that distortion of node
neighborhoods is effective in drastically compromising prediction performance.
Although neighborhood distortion is an NP-hard problem, TANDIS designs an
effective heuristic through a novel combination of Graph Isomorphism Network
with deep Q-learning. Extensive experiments on real datasets and
state-of-the-art models show that, on average, TANDIS is up to 50% more
effective than state-of-the-art techniques, while being more than 1000 times
faster.
