Exploring Graph Traversal Algorithms in Graph-Based Molecular Generation

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 data set of natural products. These metrics include percent validity, molecular coverage, and molecular shape. We also observe that by using either a breadth- or depth-first traversal it is possible to overtrain the generative models, at which point the results with either graph traversal algorithm are identical.

Automated summary

The impact of different graph traversal algorithms on molecular graph generation was explored in this study. Using a breadth-first traversal led to better coverage of training data features compared to a depth-first traversal, but overtraining can make the results with either graph traversal algorithm identical.