Learning Network Dismantling without Handcrafted Inputs
This work addresses the computational cost and bias introduced by handcrafted features in network science problems, offering a more efficient and generalizable approach for tasks like vital node identification.
The paper tackles the problem of network dismantling, an NP-hard task with real-world applications, by eliminating the need for handcrafted structural features in graph neural networks, resulting in a model that generalizes to large real networks with millions of nodes and outperforms state-of-the-art methods.
The application of message-passing Graph Neural Networks has been a breakthrough for important network science problems. However, the competitive performance often relies on using handcrafted structural features as inputs, which increases computational cost and introduces bias into the otherwise purely data-driven network representations. Here, we eliminate the need for handcrafted features by introducing an attention mechanism and utilizing message-iteration profiles, in addition to an effective algorithmic approach to generate a structurally diverse training set of small synthetic networks. Thereby, we build an expressive message-passing framework and use it to efficiently solve the NP-hard problem of Network Dismantling, virtually equivalent to vital node identification, with significant real-world applications. Trained solely on diversified synthetic networks, our proposed model -- MIND: Message Iteration Network Dismantler -- generalizes to large, unseen real networks with millions of nodes, outperforming state-of-the-art network dismantling methods. Increased efficiency and generalizability of the proposed model can be leveraged beyond dismantling in a range of complex network problems.