# Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 60 references that are in the map.
- First posted on arXiv 3 Dec 2021.

## Builds on (most cited first, 20 of 20)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Dueling Network Architectures for Deep Reinforcement Learning](https://mlsanity.com/paper/1511.06581/) (2015)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Spatial-Temporal Fusion Graph Neural Networks for Traffic Flow Forecasting](https://mlsanity.com/paper/2012.09641/) (2020)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Averaged-DQN: Variance Reduction and Stabilization for Deep Reinforcement Learning](https://mlsanity.com/paper/1611.01929/) (2016)
- [Exploratory Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1909.04063/) (2019)
- [Knowledge-aware Coupled Graph Neural Network for Social Recommendation](https://mlsanity.com/paper/2110.03987/) (2021)
- [Influence maximization in unknown social networks: Learning Policies for Effective Graph Sampling](https://mlsanity.com/paper/1907.11625/) (2019)
- [GLSearch: Maximum Common Subgraph Detection via Learning to Search](https://mlsanity.com/paper/2002.03129/) (2020)
- [Relational Fusion Networks: Graph Convolutional Networks for Road Networks](https://mlsanity.com/paper/2006.09030/) (2020)
- [Discovery of Important Crossroads in Road Network using Massive Taxi Trajectories](https://mlsanity.com/paper/1407.2506/) (2014)
- [Memetic search for identifying critical nodes in sparse graphs](https://mlsanity.com/paper/1705.04119/) (2017)
- [Variable Population Memetic Search: A Case Study on the Critical Node Problem](https://mlsanity.com/paper/1909.08691/) (2019)
- [Predicting Critical Nodes in Temporal Networks by Dynamic Graph Convolutional Networks](https://mlsanity.com/paper/2106.10419/) (2021)

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

- [Critical Nodes Identification in Complex Networks: A Survey](https://mlsanity.com/paper/2507.06164/) (2025)
- [Learning to Rank Critical Road Segments via Heterogeneous Graphs with Origin-Destination Flow Integration](https://mlsanity.com/paper/2504.19199/) (2025)

## Abstract (arXiv)

Detecting critical nodes in sparse graphs is important in a variety of application domains, such as network vulnerability assessment, epidemic control, and drug design. The critical node problem (CNP) aims to find a set of critical nodes from a network whose deletion maximally degrades the pairwise connectivity of the residual network. Due to its general NP-hard nature, state-of-the-art CNP solutions are based on heuristic approaches. Domain knowledge and trial-and-error are usually required when designing such approaches, thus consuming considerable effort and time. This work proposes a feature importance-aware graph attention network for node representation and combines it with dueling double deep Q-network to create an end-to-end algorithm to solve CNP for the first time. It does not need any problem-specific knowledge or labeled datasets as required by most of existing methods. Once the model is trained, it can be generalized to cope with various types of CNPs (with different sizes and topological structures) without re-training. Computational experiments on 28 real-world networks show that the proposed method is highly comparable to state-of-the-art methods. It does not require any problem-specific knowledge and, hence, can be applicable to many applications including those impossible ones by using the existing approaches. It can be combined with some local search methods to further improve its solution quality. Extensive comparison results are given to show its effectiveness in solving CNP.