  Graph neural networks (GNNs) are widely utilized to capture the information
spreading patterns in graphs. While remarkable performance has been achieved,
there is a new trending topic of evaluating node influence. We propose a new
method of evaluating node influence, which measures the prediction change of a
trained GNN model caused by removing a node. A real-world application is, "In
the task of predicting Twitter accounts' polarity, had a particular account
been removed, how would others' polarity change?". We use the GNN as a
surrogate model whose prediction could simulate the change of nodes or edges
caused by node removal. Our target is to obtain the influence score for every
node, and a straightforward way is to alternately remove every node and apply
the trained GNN on the modified graph to generate new predictions. It is
reliable but time-consuming, so we need an efficient method. The related lines
of work, such as graph adversarial attack and counterfactual explanation,
cannot directly satisfy our needs, since their problem settings are different.
We propose an efficient, intuitive, and effective method, NOde-Removal-based
fAst GNN inference (NORA), which uses the gradient information to approximate
the node-removal influence. It only costs one forward propagation and one
backpropagation to approximate the influence score for all nodes. Extensive
experiments on six datasets and six GNN models verify the effectiveness of
NORA. Our code is available at https://github.com/weikai-li/NORA.git.
