Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness
This addresses the challenge of detecting critical nodes for applications like network vulnerability assessment and epidemic control, offering a more automated and generalizable approach compared to heuristic methods.
The paper tackles the critical node problem (CNP) in sparse graphs by proposing an end-to-end algorithm using a feature importance-aware graph attention network and dueling double deep Q-network, which achieves performance highly comparable to state-of-the-art methods on 28 real-world networks without requiring problem-specific knowledge or labeled datasets.
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.