  Many graph-based machine learning models are known to be vulnerable to
adversarial attacks, where even limited perturbations on input data can result
in dramatic performance deterioration. Most existing works focus on moderate
settings in which the attacker is either aware of the model structure and
parameters (white-box), or able to send queries to fetch model information. In
this paper, we propose a query-free black-box adversarial attack on graphs, in
which the attacker has no knowledge of the target model and no query access to
the model. With the mere observation of the graph topology, the proposed attack
strategy flips a limited number of links to mislead the graph models. We prove
that the impact of the flipped links on the target model can be quantified by
spectral changes, and thus be approximated using the eigenvalue perturbation
theory. Accordingly, we model the proposed attack strategy as an optimization
problem, and adopt a greedy algorithm to select the links to be flipped. Due to
its simplicity and scalability, the proposed model is not only generic in
various graph-based models, but can be easily extended when different knowledge
levels are accessible as well. Extensive experiments demonstrate the
effectiveness and efficiency of the proposed model on various downstream tasks,
as well as several different graph-based learning models.
