Learning NP-hard problems on networks using Geometric Deep Learning

Many systems from a wide range of domains can be modeled as networks, i.e., a set of nodes that represent the entities of the system and a set of links between nodes that represent relations among them. For instance, social networks can be used to describe how people interact with each other, computer networks can represent communication channels (physical mediums, logical connections, etc.), trophic networks show how animals feed, and so on. The underlying complexity of the modeled systems translates into non-trivial patterns in the networks, and, thus, they are often called \emph{complex networks}. The increasing importance of networks in many domains (e.g., social, technological, biological, etc.) and the need of methodologies and tools to study complex networks led to the rise of Network Science, the field that studies networks and their applications. However, many problems on networks remain hard to define formally and even harder to solve exactly (for instance for computational constraints), requiring sub-optimal heuristics. In this work we show how Geometric Deep Learning, the generalization of Deep Learning to non-Euclidean domains like graphs, can aid the computation of NP-hard problems and learn heuristics from the data. Specifically, we define a framework, namely GDM, to learn how to solve the Network Dismantling and Link Building problems on the optimal solutions computed on small synthetic graphs, and then generalize to large real-world networks. For both problems, the state-of-the-art heuristics are outperformed significantly. This result can be achieved thanks to the generalization performance of the Graph Neural Network (GNN) layers employed. We also define mGNN, a framework to generalize any GNN to Multilayer Networks, and wsGAT, a new GNN extending the Graph Attention Network (GAT) layers to handle signed and weighted networks.