# Toward Scalable Graph Unlearning: A Node Influence Maximization based Approach

arXiv: https://arxiv.org/abs/2501.11823 · HTML: https://mlsanity.com/paper/2501.11823/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Graph unlearning, one of 12 directions in LLM safety and security.
- Builds on 38 of its 65 references that are in the map.
- First posted on arXiv 21 Jan 2025.

## Placed in

- LLM safety and security / [Graph unlearning](https://mlsanity.com/safety/graph-unlearning/)

## Builds on (most cited first, 30 of 38)

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Optuna: A Next-generation Hyperparameter Optimization Framework](https://mlsanity.com/paper/1907.10902/) (2019)
- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Certified Data Removal from Machine Learning Models](https://mlsanity.com/paper/1911.03030/) (2019)
- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [SIGN: Scalable Inception Graph Neural Networks](https://mlsanity.com/paper/2004.11198/) (2020)
- [Graph Neural Networks for Graphs with Heterophily: A Survey](https://mlsanity.com/paper/2202.07082/) (2022)
- [Stealing Links from Graph Neural Networks](https://mlsanity.com/paper/2005.02131/) (2020)
- [Scalable Graph Neural Networks via Bidirectional Propagation](https://mlsanity.com/paper/2010.15421/) (2020)
- [Neo-GNNs: Neighborhood Overlap-aware Graph Neural Networks for Link Prediction](https://mlsanity.com/paper/2206.04216/) (2022)
- [Neural Common Neighbor with Completion for Link Prediction](https://mlsanity.com/paper/2302.00890/) (2023)
- [GIF: A General Graph Unlearning Strategy via Influence Function](https://mlsanity.com/paper/2304.02835/) (2023)
- [Topology-Imbalance Learning for Semi-Supervised Node Classification](https://mlsanity.com/paper/2110.04099/) (2021)
- [Node Dependent Local Smoothing for Scalable Graph Learning](https://mlsanity.com/paper/2110.14377/) (2021)
- [Federated Unlearning for On-Device Recommendation](https://mlsanity.com/paper/2210.10958/) (2022)
- [PaSca: a Graph Neural Architecture Search System under the Scalable Paradigm](https://mlsanity.com/paper/2203.00638/) (2022)
- [Unlearning Graph Classifiers with Limited Data Resources](https://mlsanity.com/paper/2211.03216/) (2022)
- [Towards Effective and General Graph Unlearning via Mutual Evolution](https://mlsanity.com/paper/2401.11760/) (2024)
- [GRAND+: Scalable Graph Random Neural Networks](https://mlsanity.com/paper/2203.06389/) (2022)
- [RIM: Reliable Influence-based Active Learning on Graphs](https://mlsanity.com/paper/2110.14854/) (2021)
- [Approximate Graph Propagation](https://mlsanity.com/paper/2106.03058/) (2021)
- [Efficiently Forgetting What You Have Learned in Graph Representation Learning via Projection](https://mlsanity.com/paper/2302.08990/) (2023)

## Built on by (most cited first, 2 of 2)

- [Re-understanding Graph Unlearning through Memorization](https://mlsanity.com/paper/2601.14694/) (2026)
- [Unlearning Algorithmic Biases over Graphs](https://mlsanity.com/paper/2505.14945/) (2025)

## Abstract (arXiv)

Machine unlearning, as a pivotal technology for enhancing model robustness and data privacy, has garnered significant attention in prevalent web mining applications, especially in thriving graph-based scenarios. However, most existing graph unlearning (GU) approaches face significant challenges due to the intricate interactions among web-scale graph elements during the model training: (1) The gradient-driven node entanglement hinders the complete knowledge removal in response to unlearning requests; (2) The billion-level graph elements in the web scenarios present inevitable scalability issues. To break the above limitations, we open up a new perspective by drawing a connection between GU and conventional social influence maximization. To this end, we propose Node Influence Maximization (NIM) through the decoupled influence propagation model and fine-grained influence function in a scalable manner, which is crafted to be a plug-and-play strategy to identify potential nodes affected by unlearning entities. This approach enables offline execution independent of GU, allowing it to be seamlessly integrated into most GU methods to improve their unlearning performance. Based on this, we introduce Scalable Graph Unlearning (SGU) as a new fine-tuned framework, which balances the forgetting and reasoning capability of the unlearned model by entity-specific optimizations. Extensive experiments on 14 datasets, including large-scale ogbn-papers100M, have demonstrated the effectiveness of our approach. Specifically, NIM enhances the forgetting capability of most GU methods, while SGU achieves comprehensive SOTA performance and maintains scalability.