  Machine learning models are shown to face a severe threat from Model
Extraction Attacks, where a well-trained private model owned by a service
provider can be stolen by an attacker pretending as a client. Unfortunately,
prior works focus on the models trained over the Euclidean space, e.g., images
and texts, while how to extract a GNN model that contains a graph structure and
node features is yet to be explored. In this paper, for the first time, we
comprehensively investigate and develop model extraction attacks against GNN
models. We first systematically formalise the threat modelling in the context
of GNN model extraction and classify the adversarial threats into seven
categories by considering different background knowledge of the attacker, e.g.,
attributes and/or neighbour connections of the nodes obtained by the attacker.
Then we present detailed methods which utilise the accessible knowledge in each
threat to implement the attacks. By evaluating over three real-world datasets,
our attacks are shown to extract duplicated models effectively, i.e., 84% - 89%
of the inputs in the target domain have the same output predictions as the
victim model.
