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 nontrivial 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 suboptimal heuristics. In this work we show how Geometric Deep Learning, the generalization of Deep Learning to nonEuclidean domains like graphs, can aid the computation of NPhard 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 realworld networks. For both problems, the stateoftheart 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.
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 nontrivial 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 suboptimal heuristics. In this work we show how Geometric Deep Learning, the generalization of Deep Learning to nonEuclidean domains like graphs, can aid the computation of NPhard 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 realworld networks. For both problems, the stateoftheart 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.
Learning NPhard problems on networks using Geometric Deep Learning
GRASSIA, MARCO
2022
Abstract
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 nontrivial 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 suboptimal heuristics. In this work we show how Geometric Deep Learning, the generalization of Deep Learning to nonEuclidean domains like graphs, can aid the computation of NPhard 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 realworld networks. For both problems, the stateoftheart 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.File  Dimensione  Formato  

Tesi di dottorato  GRASSIA MARCO 20211109123531.pdf
accesso aperto
Dimensione
16.72 MB
Formato
Adobe PDF

16.72 MB  Adobe PDF  Visualizza/Apri 
I documenti in UNITESI sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/20.500.14242/72021
URN:NBN:IT:UNICT72021