Designing New Maximum Common Subgraph Solvers: Heuristics, Multi-Threading and Graph Neural Networks

The Maximum Common Subgraph (MCS) is a complex theoretical computer science problem, generalization of the Subgraph Isomorphism problem, finding applications in diverse domains such as chemistry, biology, medicine, and network management. This research focuses on improving the performance of the McSplit algorithm, a popular recursive Branch-and-Bound MCS solver. The objective of this project is to develop a tool that efficiently identifies the largest subgraph within a given time limit, addressing real-world scenarios where finding the optimal solution is not always the primary goal. To achieve this, a diverse range of strategies have been explored to identify the most effective approaches for future advancements. Three distinct implementations have been developed as part of this effort. Firstly, novel sorting heuristics have been devised for the McSplit algorithm, aiming to establish a best-first vertex selection policy during the tree search. These heuristics have been combined with a newly designed multi-thread parallel architecture, optimizing the allocation of processor time to promising branches of the recursive algorithm. Additionally, Graph Neural Networks (GNNs) have been employed to identify and prioritize the most favorable branches at each intersection of the tree search. To assess the performance of these tools, extensive testing has been conducted using open-source datasets pertaining to Internet infrastructure networks and other relevant real-world applications. The evaluation of performance metrics demonstrates significant improvements over existing state-of-the-art MCS solvers in the targeted use cases. In conclusion, this research project has successfully enhanced the capabilities of the McSplit algorithm, providing notable advancements in solving the Maximum Common Subgraph problem for practical applications. These achievements have been recognized through the acceptance of our paper titled \textit{A web scraping algorithm to enhance maximum common subgraph computation} at ICSOFT 2023. Furthermore, the analysis of the proposed methodologies, including sorting heuristics, parallel architecture, and Graph Neural Networks, offer valuable insights for future research to determine the most promising strategies among the explored approaches.