Politecnico di Torino (logo)

Graph neural networks for the MCS problem

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

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
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) Modify record (reserved for operators)