Thomas Madeo
Graph neural networks for the MCS problem.
Rel. Stefano Quer, Giovanni Squillero, Andrea Calabrese. Politecnico di Torino, Corso di laurea magistrale in Ingegneria Informatica (Computer Engineering), 2022
|
PDF (Tesi_di_laurea)
- Tesi
Licenza: Creative Commons Attribution Non-commercial No Derivatives. Download (1MB) | Preview |
Abstract: |
The Maximum Common Subgraph (MCS) problem consists in finding the largest graph that is simultaneously isomorphic to a subgraph of two given graphs. Finding the MCS has been proven to be NP-hard, however it has many practical applications such as malware detection, cloud computing, drug synthesis, etc. The state-of-the-art MCS solver is based on the branch and bound paradigm. Its core section includes a node degree-based heuristic for node selection. This thesis extends and modify the MCS solver with the objective of finding a large solution in a limited budget time. We use Graph Neural Networks (GNN) to learn node embeddings and derive a better heuristic for the node selection. Our experimental analysis shows a substantial improvement over the original method. We also provide a solver variant which uses heuristics to directly selects node pairs instead of single nodes. Finally, we build a custom neural network to learn which nodes are likely to be part of a big solution by using the solver results as a ground truth. In these cases, performances are still under investigation, but the methodologies look promising. |
---|---|
Relators: | Stefano Quer, Giovanni Squillero, Andrea Calabrese |
Academic year: | 2021/22 |
Publication type: | Electronic |
Number of Pages: | 75 |
Subjects: | |
Corso di laurea: | Corso di laurea magistrale in Ingegneria Informatica (Computer Engineering) |
Classe di laurea: | New organization > Master science > LM-32 - COMPUTER SYSTEMS ENGINEERING |
Aziende collaboratrici: | UNSPECIFIED |
URI: | http://webthesis.biblio.polito.it/id/eprint/22683 |
Modify record (reserved for operators) |