Fast Inference of Removal-Based Node Influence

Abstract

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.

Published in the Web Conference 2024

References in corpus (14)

• Learning and Evaluating Graph Neural Network Explanations based on Counterfactual and Factual Reasoning
• A Learning Convolutional Neural Network Approach for Network Robustness Prediction
• Single Node Injection Attack against Graph Neural Networks
• TIMME: Twitter Ideology-detection via Multi-task Multi-relational Embedding
• Unsupervised Graph Poisoning Attack via Contrastive Loss Back-propagation
• A hybrid algorithm based on Community Detection and Multi-Attribute Decision-Making for Influence Maximization
• Understanding and Improving Graph Injection Attack by Promoting Unnoticeability
• CLEAR: Generative Counterfactual Explanations on Graphs
• Dismantling Complex Networks by a Neural Model Trained from Tiny Networks
• Black-box Node Injection Attack for Graph Neural Networks
• Betweenness Approximation for Edge Computing with Hypergraph Neural Network
• More Effective Centrality-Based Attacks on Weighted Networks
• Let Graph be the Go Board: Gradient-free Node Injection Attack for Graph Neural Networks via Reinforcement Learning
• Embedding-aided network dismantling