PaperlayerView exact revision on arXiv

Source-linked AI summary

Molecular Hypergraph Grammar with its Application to Molecular Optimization

Hiroshi Kajino

arXiv:1809.02745v2cs.LGstat.ML

TL;DR

Molecular optimization must search for molecules with desired properties while handling valid-molecule generation and costly property evaluation. This paper develops a molecular hypergraph grammar and combines it with a VAE in MHG-VAE. The authors report that it achieves the best performance among VAE-based methods and outperforms GCPN when target-function evaluations are limited.

  • Problem

    Molecular optimization is challenged by valid-molecule generation under chemical constraints and costly property evaluations that limit the available evaluation budget.

    Source: §1 · pp. 1–2

  • Method

    The paper develops MHG and an inference algorithm, then uses MHG to represent molecules as parse trees in a single-VAE MHG-VAE.

    Source: §1 · pp. 2–3

  • Results

    MHG-VAE achieves the best performance among VAE-based methods and performs better than GCPN when target-function evaluations are limited.

    Source: §9 · p. 10

  • Takeaways & Limitations

    The authors conclude that MHG-VAE combines atom-level connections and stereochemistry with a single VAE that can generate valid molecules.

    Source: §1 · p. 2, §9 · p. 10

    The prior tree representation captures only part of molecular properties, leaving atom-level connections and stereochemistry to auxiliary neural networks.

    Source: §1 · p. 2

Abstract

from arXiv · show

Molecular optimization aims to discover novel molecules with desirable properties. Two fundamental challenges are: (i) it is not trivial to generate valid molecules in a controllable way due to hard chemical constraints such as the valency conditions, and (ii) it is often costly to evaluate a property of a novel molecule, and therefore, the number of property evaluations is limited. These challenges are to some extent alleviated by a combination of a variational autoencoder (VAE) and Bayesian optimization (BO). VAE converts a molecule into/from its latent continuous vector, and BO optimizes a latent continuous vector (and its corresponding molecule) within a limited number of property evaluations. While the most recent work, for the first time, achieved 100% validity, its architecture is rather complex due to auxiliary neural networks other than VAE, making it difficult to train. This paper presents a molecular hypergraph grammar variational autoencoder (MHG-VAE), which uses a single VAE to achieve 100% validity. Our idea is to develop a graph grammar encoding the hard chemical constraints, called molecular hypergraph grammar (MHG), which guides VAE to always generate valid molecules. We also present an algorithm to construct MHG from a set of molecules.

1 Introduction

Molecular optimization seeks molecules with user-prescribed properties, but valid-molecule generation is difficult and property evaluations are costly. The paper introduces MHG and MHG-VAE to encode chemical constraints in a grammar, enabling a single VAE to generate valid molecules with stereochemistry.

1 Introduction

  • Property evaluations are often costly, sometimes requiring wet-lab experiments or day-long quantum-mechanics simulations, so only a small sample may be available.The optimization also searches a discrete set of valid molecules, making candidate generation difficult.Source: §1 · p. 1
  • VAE and Bayesian optimization address the discrete search and limited evaluations by mapping molecules to a continuous latent space and optimizing there.The VAE encodes and decodes molecules; Bayesian optimization iteratively proposes candidates under a limited evaluation budget.Source: §1 · p. 1
  • SMILES-based decoding can fail when generated strings violate its grammar, preventing a molecule from being obtained.Examples include an unclosed ring and a string that violates carbon valency.Source: §1 · p. 2
  • Earlier tree-based generation achieved 100% validity, but its representation omitted atom-level connections and stereochemistry, which required auxiliary neural networks.The approach enumerated possible configurations and used several auxiliary networks to select among them.Source: §1 · p. 2
  • MHG-VAE uses a single VAE with a molecular hypergraph grammar to generate valid molecules with stereochemistry, without auxiliary neural networks.The grammar represents molecules as parse trees and specifies atom-level connections and stereochemistry.Source: §1 · pp. 2–3
  • The MHG inference algorithm uses an irredundant tree decomposition so the inferred grammar generates valid molecular hypergraphs.The existing inference approach could produce hypergraphs with nodes shared by more than two hyperedges.Source: §1 · p. 3

2 Preliminaries

This section introduces hypergraphs, tree decompositions, and hyperedge replacement grammars as tools for representing and generating hypergraphs. It also defines parse trees and their equivalence to sequential production-rule application.

2 Preliminaries

  • A tree decomposition organizes a hypergraph into a tree while covering its nodes and hyperedges and keeping the occurrences of each node connected.Each hyperedge is contained in exactly one tree node's associated set.Source: §2 · p. 3
  • A hyperedge replacement grammar (HRG) generates hypergraphs by repeatedly replacing a non-terminal symbol with a hypergraph that may contain terminal and non-terminal symbols.An HRG comprises non-terminal and terminal labels, a starting non-terminal, and production rules.Source: §2 · p. 3
  • A parse tree labels each node with a production rule and orders children to match the non-terminals in the parent rule.Leaves use rules whose right-hand sides contain no non-terminals.Source: §2 · p. 4
  • Sequential application of production rules constructs the same hypergraph represented by a parse tree; this sequence is called a parse sequence.Source: §2 · p. 4

3 Molecular Graph and Hypergraph

The section defines molecular graphs and hypergraphs, then establishes an encoding and decoding between them. The representations preserve valency constraints and include stereochemical information.

3.1 Molecular Graph

  • Molecular graphs represent atoms as labeled nodes and bonds as labeled edges, with node degrees constrained by atom labels to satisfy valency.Source: §3.1 · p. 4
  • The graph labels encode tetrahedral chirality on nodes and E-Z configuration on edges; aromatic rings use a Kekule representation of alternating single and double bonds.Aromaticity is inferred from the Kekule representation rather than encoded explicitly.Source: §3.1 · p. 4

3.2 Molecular Hypergraph

  • A molecular hypergraph models atoms as hyperedges and bonds as nodes shared by the corresponding hyperedges.It must be 2-regular, and each hyperedge's cardinality is constrained by its label.Source: §3.2 · p. 4

3.3 Encoder and Decoder

  • The graph–hypergraph encoders and decoders swap nodes with hyperedges and edges with nodes, yielding an equivalent representation.The regularity condition ensures the swap works.Source: §3.2 · p. 4, §3.3 · p. 5

4 Molecular Hypergraph Grammar

A molecular hypergraph grammar (MHG) is an HRG whose generated language consists of molecular hypergraphs. Its encoder and decoder represent those hypergraphs as parse sequences and recover them.

4 Molecular Hypergraph Grammar

  • An MHG is an HRG that always generates molecular hypergraphs.Its language is the set of molecular hypergraphs it can generate.Source: §4 · p. 5
  • EncG maps molecular hypergraphs in the MHG language to parse sequences, while DecG applies production rules to map valid sequences back.The decoder accepts only sequences obtained from the MHG language.Source: §4 · p. 5
  • For every molecular hypergraph in the MHG language, decoding its encoded parse sequence recovers the original hypergraph.H = DecG(EncG(H)).Source: §4 · p. 5

5 MHG Inference Algorithm

The paper adapts HRG inference to produce an MHG from molecular hypergraphs. Its irredundant tree decomposition addresses a regularity violation in existing inference, while the resulting grammar covers the input and generates molecular hypergraphs.

5.1 Existing HRG Inference Algorithm

  • Existing HRG inference treats a rooted tree decomposition as a parse tree and extracts production rules from each parent-node-child triplet.The rules paste each node’s hypergraph onto its parent while leaving non-terminals for rules from the children.Source: §5.1 · p. 5

5.2 Our MHG Inference Algorithm

  • Existing inference can violate regularity, so the authors replace its generic tree decomposition with an irredundant one to infer an MHG.Irredundancy means tree nodes do not contain redundant nodes of the original hypergraph.Source: §5.2 · p. 5, §5 · p. 5
  • The irredundant tree decomposition is illustrated in Figure 3, alongside Figure 4’s redundant decomposition.The paper describes irredundancy as removing redundant original-hypergraph nodes from tree nodes.Source: §5.2 · p. 5, Figure 3 · p. 6, Figure 4 · p. 6
  • The algorithm repeatedly splits a hypergraph at a node that disconnects it, duplicating that node, until the pieces contain one hyperedge or a ring.It then splits ring-containing nodes into a ring skeleton and nodes for the individual hyperedges, reducing the number of production rules.Source: §5.2 · p. 6
  • The inferred HRG’s language includes the input hypergraphs and always generates molecular hypergraphs, making it an MHG.Theorem 2 summarizes these properties of the inference algorithm.Source: §5 · p. 5, §5.2 · p. 6

6 Application to Molecular Optimization

The molecular optimization application composes molecular-graph and grammar encoders with a sequence VAE, then uses Bayesian optimization in the latent space. The procedure infers a grammar and trains the model from input molecules and targets before decoding and evaluating new candidates.

6.1 Our Model

  • The model composes EncH, EncG, and a seq2seq GVAE encoder; its decoder uses the corresponding stages in reverse.Because the GVAE decoder outputs a parse sequence in the grammar decoder’s domain, DecG can decode it to a molecular hypergraph.Source: §6 · p. 6, §6.1 · p. 7

6 Application to Molecular Optimization

  • The application searches the molecular space for novel molecules with desirable properties using the encoders and decoders presented earlier.The optimization algorithms require the decoder, not the encoder, at the candidate-generation stage.Source: §6 · pp. 6–7, §6.2 · p. 7
  • The application first converts input molecular graphs to hypergraphs, infers an MHG and parse sequences, then trains neural networks and a predictor from those sequences and targets.The resulting latent vectors and decoders are used in the optimization stage.Source: §6 · p. 7

6.2 Molecular Optimization Algorithm

  • Global optimization fits a Gaussian process, obtains candidates through Bayesian optimization, decodes them into molecular graphs, evaluates their targets, and adds results to the data.This candidate-generation and evaluation cycle repeats for the specified number of iterations.Source: §6 · p. 7, §6.2 · p. 7

7 Related Work

Related work contrasts molecular optimization methods by evaluation cost and approaches to valid molecule generation. The paper positions MHG as a grammar-based alternative that models atom-level connections and stereochemistry while achieving 100% validity with a single VAE and predictor.

7 Related Work

  • For unlimited-oracle optimization, GCPN outperforms VAE-based methods when target evaluation cost is negligible.Table 1 covers reconstruction rate, predictive performance, and global optimization in this setting.Source: Table 1 · p. 8
  • VAE plus Bayesian optimization targets costly property evaluations, whereas reinforcement learning assumes evaluations are negligible and permits many trials.The paper associates the former setting with wet-lab experiments or computationally heavy first-principles calculations.Source: §7 · pp. 7–8
  • Earlier grammar-based SMILES methods address validity constraints incompletely: attribute grammars handle ring-bond matching and valence, but may still generate invalid molecules.The paper also notes that SMILES grammar is not totally context-free.Source: §7 · p. 8
  • Jin et al. (2018) report 100% validity with fragment trees, while MHG formalizes the representation to model atom-level connections and stereochemistry with a single VAE and predictor.The paper reports that its method outperforms alternatives, including GCPN, under the limited-oracle setting.Source: §7 · p. 8, Table 2 · p. 8

8 Empirical Studies

The experiments evaluate MHG-VAE on reconstruction and molecular optimization, including settings with unlimited and limited property evaluations. MHG-VAE outperforms other methods in the limited-oracle comparison and performs almost comparably there to its own unlimited-oracle result.

8 Empirical Studies

  • The experiments use ZINC with 220,011 training, 24,445 validation, and 5,000 test molecules, and maximize standardized penalized logP.The compared baselines include CVAE, GVAE, SD-VAE, JT-VAE, and GCPN.Source: §8 · p. 9

8.1 Reconstruction Rate

  • MHG-VAE improves reconstruction rate over the compared methods and is evaluated on random latent vectors for decoding validity.Reconstruction success means the decoded molecule is isomorphic to the test molecule; random-vector decoding succeeds when the result is valid.Source: §8.1 · p. 9

8.2 Global Molecular Optimization

  • The unlimited-oracle protocol allows arbitrary property queries, whereas the limited-oracle protocol compares methods under the same query budget.The limited-oracle scenario is the primary setting because property evaluation is assumed expensive.Source: §8.2 · p. 9
  • MHG-VAE clearly outperforms the other methods, including GCPN, with limited oracle calls and performs almost comparably to its unlimited-oracle result.The authors identify the limited-oracle setting as their primary concern.Source: §8.2 · p. 10
  • In the unlimited-oracle case, MHG-VAE achieves the best scores among VAE-based methods, while GCPN reports the highest individual target properties.For top-50 molecule statistics, MHG-VAE scores better than JT-VAE.Source: §8.2 · p. 10

9 Conclusion and Future Work

The paper concludes that MHG-VAE uses MHG parse trees to model atom-level connections and stereochemistry with a single VAE. It also describes an HRG inference procedure that extracts production rules from hypergraph tree decompositions.

9 Conclusion and Future Work

  • MHG-VAE combines MHG parse-tree representations with a single VAE, modeling atom-level connections and stereochemistry.The experiments report the best performance among VAE-based methods and better performance than GCPN when target-function evaluations are limited.Source: §9 · p. 10
  • The paper proposes optimizing MHG by manipulating tree decompositions under goodness criteria such as minimum description length or a Bayesian criterion.The resultant MHG depends on the tree decompositions.Source: §9 · p. 10
  • Retrosynthetic analysis is proposed as a future direction to derive synthesis pathways for target molecules.The authors state that this capability would allow the output molecule's property to be examined by synthesizing it.Source: §9 · p. 10

A HRG Inference Algorithm

  • The HRG inference algorithm extracts production rules from tree decompositions of input hypergraphs and removes duplicate rules before output.For each tree node, it uses the node, parent, and children to extract a rule that glues a local hypergraph to its parent using non-terminal hyperedges for children.Source: A HRG Inference Algorithm · p. 13

B Proofs

The proofs establish that the inferred grammar preserves the stated regularity and cardinality-consistency conditions. The model configuration uses a 72-dimensional latent vector and trains the VAE with a β-VAE objective.

B Proofs

  • The inferred HRG satisfies Condition 3, and a grammar satisfying that condition always generates a 2-regular hypergraph.Condition 3 requires external nodes of each production rule to have degree one and internal nodes degree two.Source: B Proofs · p. 13
  • The inferred HRG also preserves cardinality consistency when its input hypergraphs are cardinality-consistent.The proof combines this property with the regularity results to establish preservation of the molecular-hypergraph conditions.Source: B Proofs · p. 13
  • The proof analyzes how production rules preserve degree two through derivation, including replacements at external nodes.It considers the cases for tree nodes containing the two hyperedges incident with a given hypergraph node.Source: B Proofs · pp. 13, 15

C Model Configuration

  • The encoder produces a 72-dimensional Gaussian latent vector, and the encoder-decoder is trained with a β-VAE objective using β = 0.01.Both neural sequence components use three-layer GRUs with 384 hidden units; the predictive model is linear regression.Source: C Model Configuration · p. 15

D Basic Statistics of MHG

The inferred MHG has 2,031 production rules, though many starting rules are rarely used. Its estimated test-set coverage is 99.68%.

D Basic Statistics of MHG

  • 2,031 production rules were inferred from ZINC, including 1,424 starting rules, with an average of 25 production rules per molecule.Two-thirds of the starting rules (1,073) were used by fewer than ten molecules; together these rules appeared in 2,355 of 250,000 molecules.Source: D Basic Statistics of MHG · p. 15
  • Excluding the 1,073 starting rules used by fewer than ten molecules leaves a grammar the authors describe as moderate in size.These rules together were used by 2,355 of 250,000 molecules.Source: D Basic Statistics of MHG · p. 15
  • 99.68% of test-set molecules were estimated to be representable by the MHG, based on 16 of 5,000 molecules that could not be parsed.The estimate uses test-set parsing failures because the paper provides no theoretical validation of coverage.Source: D Basic Statistics of MHG · p. 15

E Local Molecular Optimization

In local molecular optimization, the method improves penalized logP more than JT-VAE at every tested similarity threshold. The paper also presents the top 50 molecules found through global optimization.

E Local Molecular Optimization

  • Local optimization seeks to improve a molecule's property without modifying it too much, using Tanimoto similarity with Morgan fingerprints of radius 2.The method approximately solves the constrained problem by substituting its predictive model for the unknown target function.Source: E Local Molecular Optimization · p. 16
  • The predictive model requires a large training dataset, making limited-oracle local optimization difficult; a tailored limited-oracle algorithm is left for future work.The paper places local optimization in the appendix because the unlimited-oracle scenario is out of scope.Source: E Local Molecular Optimization · p. 16
  • At every tested similarity threshold, the method improves the target property more than JT-VAE, while GCPN outperforms VAE-based methods in this unlimited-oracle setting.Success means that an output molecule exists satisfying the similarity constraint.Source: E Local Molecular Optimization · p. 16

F Molecules Discovered by Global Molecular Optimization

Related papers

Loading 1809.02745v2…