Graph neural networks for the MCS problem

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.