# Scalable Graph Neural Network-based framework for identifying critical nodes and links in Complex Networks

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Dec 2020.

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

- [Challenges and Opportunities in Deep Reinforcement Learning with Graph Neural Networks: A Comprehensive review of Algorithms and Applications](https://mlsanity.com/paper/2206.07922/) (2022)
- [A Survey on Learning from Graphs with Heterophily: Recent Advances and Future Directions](https://mlsanity.com/paper/2401.09769/) (2024)
- [A General Framework for quantifying Aleatoric and Epistemic uncertainty in Graph Neural Networks](https://mlsanity.com/paper/2205.09968/) (2022)
- [Predicting Critical Nodes in Temporal Networks by Dynamic Graph Convolutional Networks](https://mlsanity.com/paper/2106.10419/) (2021)
- [GraMeR: Graph Meta Reinforcement Learning for Multi-Objective Influence Maximization](https://mlsanity.com/paper/2205.14834/) (2022)
- [Influential Simplices Mining via Simplicial Convolutional Network](https://mlsanity.com/paper/2307.05841/) (2023)
- [Critical Nodes Identification in Complex Networks: A Survey](https://mlsanity.com/paper/2507.06164/) (2025)
- [PINE: Pipeline for Important Node Exploration in Attributed Networks](https://mlsanity.com/paper/2512.07244/) (2025)
- [RW-NSGCN: A Robust Approach to Structural Attacks via Negative Sampling](https://mlsanity.com/paper/2408.06665/) (2024)
- [Graph Neural Network-Based Distributed Optimal Control for Linear Networked Systems: An Online Distributed Training Approach](https://mlsanity.com/paper/2504.06439/) (2025)

## Abstract (arXiv)

Identifying critical nodes and links in graphs is a crucial task. These nodes/links typically represent critical elements/communication links that play a key role in a system's performance. However, a majority of the methods available in the literature on the identification of critical nodes/links are based on an iterative approach that explores each node/link of a graph at a time, repeating for all nodes/links in the graph. Such methods suffer from high computational complexity and the resulting analysis is also network-specific. To overcome these challenges, this article proposes a scalable and generic graph neural network (GNN) based framework for identifying critical nodes/links in large complex networks. The proposed framework defines a GNN based model that learns the node/link criticality score on a small representative subset of nodes/links. An appropriately trained model can be employed to predict the scores of unseen nodes/links in large graphs and consequently identify the most critical ones. The scalability of the framework is demonstrated through prediction of nodes/links scores in large scale synthetic and real-world networks. The proposed approach is fairly accurate in approximating the criticality scores and offers a significant computational advantage over conventional approaches.