Exploring graph traversal algorithms in graph-based molecular generation

Abstract

Here we explore the impact of different graph traversal algorithms on molecular graph generation. We do this by training a graph-based deep molecular generative model to build structures using a node order determined via either a breadth- or depth-first search algorithm. What we observe is that using a breadth-first traversal leads to better coverage of training data features compared to a depth-first traversal. We have quantified these differences using a variety of metrics on a dataset of natural products. These metrics include: percent validity, molecular coverage, and molecular shape. We also observe that using either a breadth- or depth-first traversal it is possible to over-train the generative models, at which point the results with the graph traversal algorithm are identical

Related Papers

• → Graph Traversal Techniques and the Maximum Flow Problem in Distributed Computation(1983)104 cited
• → A parallel search algorithm for directed acyclic graphs(1984)48 cited
• → Chaotic Traversal (CHAT): Very Large Graphs Traversal Using Chaotic Dynamics(2017)2 cited
• → Exploring graph traversal algorithms in graph-based molecular generation(2021)1 cited
• → Trees and Graph Traversals(2018)