  Graph-based Semi-Supervised Learning (GSSL) is a practical solution to learn
from a limited amount of labelled data together with a vast amount of
unlabelled data. However, due to their reliance on the known labels to infer
the unknown labels, these algorithms are sensitive to data quality. It is
therefore essential to study the potential threats related to the labelled
data, more specifically, label poisoning. In this paper, we propose a novel
data poisoning method which efficiently approximates the result of label
inference to identify the inputs which, if poisoned, would produce the highest
number of incorrectly inferred labels. We extensively evaluate our approach on
three classification problems under 24 different experimental settings each.
Compared to the state of the art, our influence-driven attack produces an
average increase of error rate 50\% higher, while being faster by multiple
orders of magnitude. Moreover, our method can inform engineers of inputs that
deserve investigation (relabelling them) before training the learning model. We
show that relabelling one-third of the poisoned inputs (selected based on their
influence) reduces the poisoning effect by 50\%.
