RetroGraph: Retrosynthetic Planning with Graph Search

• URL: http://arxiv.org/abs/2206.11477v1
• Date: Thu, 23 Jun 2022 05:01:29 GMT
• Title: RetroGraph: Retrosynthetic Planning with Graph Search
• Authors: Shufang Xie, Rui Yan, Peng Han, Yingce Xia, Lijun Wu, Chenjuan Guo, Bin Yang, Tao Qin
• Abstract summary: Retrosynthetic planning aims to find a reaction pathway to synthesize a target molecule. We propose a graph-based search policy that eliminates the redundant explorations of any intermediate molecules. Our method can search a batch of targets together in the graph and remove the inter-target duplication in the tree-based search methods.
• Score: 101.92603715499112
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Retrosynthetic planning, which aims to find a reaction pathway to synthesize a target molecule, plays an important role in chemistry and drug discovery. This task is usually modeled as a search problem. Recently, data-driven methods have attracted many research interests and shown promising results for retrosynthetic planning. We observe that the same intermediate molecules are visited many times in the searching process, and they are usually independently treated in previous tree-based methods (e.g., AND-OR tree search, Monte Carlo tree search). Such redundancies make the search process inefficient. We propose a graph-based search policy that eliminates the redundant explorations of any intermediate molecules. As searching over a graph is more complicated than over a tree, we further adopt a graph neural network to guide the search over graphs. Meanwhile, our method can search a batch of targets together in the graph and remove the inter-target duplication in the tree-based search methods. Experimental results on two datasets demonstrate the effectiveness of our method. Especially on the widely used USPTO benchmark, we improve the search success rate to 99.47%, advancing previous state-of-the-art performance for 2.6 points.

Related papers

• Tree Search for Language Model Agents [69.43007235771383]
  We propose an inference-time search algorithm for LM agents to perform exploration and multi-step planning in interactive web environments. Our approach is a form of best-first tree search that operates within the actual environment space. It is the first tree search algorithm for LM agents that shows effectiveness on realistic web tasks.
  arXiv  Detail & Related papers  (2024-07-01T17:07:55Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  This study introduces a novel guided tree search algorithm with dynamic node selection and node-level exploration budget. Experiments conducted on the GSM8K and TabMWP datasets demonstrate that our approach enjoys significantly lower computational costs compared to baseline methods.
  arXiv  Detail & Related papers  (2024-06-29T05:14:04Z)
• Evolutionary Retrosynthetic Route Planning [8.19851864095418]
  This paper proposes a novel approach for retrosynthetic route planning based on evolutionary optimization. It marks the first use of Evolutionary Algorithm (EA) in the field of multi-step retrosynthesis.
  arXiv  Detail & Related papers  (2023-10-08T14:47:41Z)
• Learning Graph Search Heuristics [48.83557172525969]
  We present PHIL (Path Heuristic with Imitation Learning), a novel neural architecture and a training algorithm for discovering graph search and navigations from data. Our function learns graph embeddings useful for inferring node distances, runs in constant time independent of graph sizes, and can be easily incorporated in an algorithm such as A* at test time. Experiments show that PHIL reduces the number of explored nodes compared to state-of-the-art methods on benchmark datasets by 58.5% on average.
  arXiv  Detail & Related papers  (2022-12-07T22:28:00Z)
• Subgraph Matching via Query-Conditioned Subgraph Matching Neural Networks and Bi-Level Tree Search [33.9052190473029]
  Subgraph Matching is a core operation in graph database search, biomedical analysis, social group finding, etc. In this paper, we propose a novel encoder-decoder neural network architecture to dynamically compute the matching information between the query and the target graphs. Experiments on five large real-world target graphs show that N-BLS can significantly improve the subgraph matching performance.
  arXiv  Detail & Related papers  (2022-07-21T04:47:21Z)
• Automatic Relation-aware Graph Network Proliferation [182.30735195376792]
  We propose Automatic Relation-aware Graph Network Proliferation (ARGNP) for efficiently searching GNNs. These operations can extract hierarchical node/relational information and provide anisotropic guidance for message passing on a graph. Experiments on six datasets for four graph learning tasks demonstrate that GNNs produced by our method are superior to the current state-of-the-art hand-crafted and search-based GNNs.
  arXiv  Detail & Related papers  (2022-05-31T10:38:04Z)
• ExPoSe: Combining State-Based Exploration with Gradient-Based Online Search [14.90561531943247]
  A tree-based online search algorithm iteratively simulates trajectories and updates Q-value information on a set of states represented by a tree structure. Or, policy gradient based online search algorithms update the information obtained from simulated trajectories directly onto the parameters of the policy. We show that it is possible to combine and leverage the strengths of these two methods for improved search performance.
  arXiv  Detail & Related papers  (2022-02-03T08:39:25Z)
• Retro*: Learning Retrosynthetic Planning with Neural Guided A* Search [83.22850633478302]
  Retrosynthetic planning identifies a series of reactions that can lead to the synthesis of a target product. Existing methods either require expensive return estimation by rollout with high variance, or optimize for search speed rather than the quality. We propose Retro*, a neural-based A*-like algorithm that finds high-quality synthetic routes efficiently.
  arXiv  Detail & Related papers  (2020-06-29T05:53:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.