Fast Inference of Removal-Based Node Influence

Weikai Li, Zhiping Xiao, Xiao Luo, Yizhou Sun

Abstract

Graph neural networks (GNNs) are widely utilized to capture information spreading patterns in graphs. While remarkable performance has been achieved, evaluating node influence remains a critical challenge. We propose a new method for evaluating node influence that measures the prediction change of a trained GNN model caused by removing a node. For example, in predicting Twitter accounts' polarity, we ask: "Had a particular account been removed, how would others' polarity change?" While brute-force removal is reliable, it is computationally prohibitive. We introduce NOde-Removal-based fAst GNN inference (NORA), which uses gradient information to approximate node-removal influence in just one forward and one backpropagation pass. Extensive experiments on six datasets and six GNN models verify NORA's effectiveness and efficiency.

The Challenge of Task-Specific Influence

In network analysis, identifying influential nodes is a classic problem. Traditionally, influence is defined by static graph structures (like PageRank) or generic propagation models. However, these definitions are not task-specific. If a GNN is used to predict political polarity on social media, we need to know which account's removal most drastically shifts the predicted polarity of the remaining users.

The brute-force approach to measuring node influence by comparing predictions on the original graph G and the modified graph G-vi.

The "ground truth" way to measure this is brute-force: remove a node, re-run the GNN, measure the change, and repeat for every node in the graph. For large-scale graphs like ogbn-arxiv (160k+ nodes), this process can take dozens of hours, making it impractical for real-time or large-scale applications.

NORA: Fast Approximation via Gradients

NORA overcomes the $O(N)$ cost of brute-force removal by using an efficient approximation method. The core innovation lies in decomposing the influence of removing a node into three distinct components that can be captured via first-order derivatives:

  1. Disappearance of the message: The direct loss of the removed node's latent representation as a message to its immediate neighbors.
  2. Change of aggregation terms: The structural impact on neighbors' normalization (e.g., degree-based normalization changes when a neighbor is removed).
  3. Propagation: The "ripple effect" where these changes spread to multi-hop neighbors through subsequent GNN layers.
NORA decomposes node influence into three steps: removing messages, changing aggregation terms, and propagating embedding changes.

By applying the chain rule and first-order Taylor expansions, NORA uses the gradient of the GNN's output with respect to node embeddings to estimate the total variation distance in predictions. This allows influence scores for all nodes to be calculated simultaneously after a single backward pass.

Experimental Evaluation

The researchers evaluated NORA across six representative datasets, including citation networks (Cora, CiteSeer, PubMed, ogbn-arxiv) and social media interactions (Twitter).

Key Results

  • Massive Speedup: On the ogbn-arxiv dataset, the brute-force method required 41 hours. NORA generated the same influence scores in less than one minute.
  • High Fidelity: NORA achieved a Pearson correlation coefficient of 0.90 to 0.98 with ground truth influence scores across most citation datasets, indicating the approximation is highly reliable for ranking nodes.
  • Structural vs. Semantic Balance: NORA successfully balances "semantic" influence (node features) and "structural" influence (connectivity). Ablation studies confirmed that ignoring either component significantly degrades the approximation accuracy.

Conclusion and Future Work

NORA demonstrates that while GNNs are highly non-linear, first-order gradients provide a surprisingly accurate local approximation of node-removal impacts. While highly effective, NORA may face challenges with GNNs featuring extreme non-linearities or complex attention mechanisms (like GAT) where linear approximations are less stable. Future work will focus on refining these approximations for more complex aggregators and irregular power-law graphs.

Summary updated

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.
BibTeX
@inproceedings{li2024fast,
  author = {Weikai Li and Zhiping Xiao and Xiao Luo and Yizhou Sun},
  title = {{Fast Inference of Removal-Based Node Influence}},
  booktitle = {The Web Conference},
  year = {2024},
  doi = {10.1145/3589334.3645389},
}
Figure