title: Deep Graph Learning in Subgraph Matching and Retrosynthesis
Creators: name: Lan, Zixun
Publisher: name: University of Liverpool Repository
Year: 2024

description: A graph is a set of nodes connected by a set of edges. It serves as a universal representation for diverse real-world data. Graph theory is an important branch of mathematics. It focuses on the graph and its applications, including Subgraph Matching, Maximum Common Subgraph, Graph Edit Distance, Graph Similarity Computation and so on. Deep graph learning aims to encode the structural characteristics of graphs. It has captured significant attention in various applications involving graph structures, such as node classification, link prediction, and community detection. This thesis focuses on using the currently popular deep graph learning to solve classic NP-hard graph theroy problems and some related applications:

The subgraph matching task involves identifying all subgraphs in a data graph that match a given query graph, posing challenges due to its NP-hard nature. We propose Subgraph matching network (Sub-GMN) and Adaptive Edge-Deleting Network (AEDNet), utilizing graph representation learning, metric learning, cross-attention and adaptive edge-deleting mechanism to model relationships between matched nodes. We applied the proposed two methods on six datasets with graph sizes varying from 20 to 2300. Our evaluations on six open datasets demonstrate that the proposed methods outperforms six state-of-the-arts and is about 200 times faster than the exact methods on large graphs. 

Graph similarity learning aims to compute a similarity score between input graphs. Our approach introduces an interpretable end-to-end paradigm by implicitly inferring Maximum Common Subgraphs and employing Positional Encoding based on permutation-invariant node ordering. Comprehensive experiments on various datasets validate the effectiveness of our method, with ablation studies confirming the contributions of individual components, supported by interpretability demonstrated through case studies and visualizations.

Identifying single or multiple reaction centers in chemical compounds is crucial for retrosynthetic analysis. We propose a unified framework, RCsearcher, which utilizes a deep graph learning based DQN to select node-induced subgraphs as predicted reaction centers. Extensive experiments on the USPTO-40k dataset validate the effectiveness and generalization of RCsearcher, with ablation studies confirming the efficacy of individual components.

Retrosynthesis prediction aims to predicting reactants from a specified core product in organic synthesis. We propose RetroSiG, a semi-template-based method, which utilizes graph-based mechanisms to predict reactions with multiple reaction centers and attaching the same leaving group to more than one atom. Comprehensive experiments demonstrate the competitive performance of RetroSiG, including its effectiveness in predicting complex reactions, with ablation experiments confirming the efficacy of specific elements.

This dissertation delves into five recent studies, focusing on the classical graph theroy problems and some practical application of Deep Graph Learning. Comprehensive experimentation reveals that the proposed methods based on Deep Graph Learning exhibit remarkable improvements when compared to the SOTAs of that time. It shows that deep graph learning model can be applied in the classicial graph theory problems, and its models can be good solutions in many of applications relating to graph structure data, such as retrosynthesis.