PaperlayerView exact revision on arXiv

Source-linked AI summary

N-Gram Graph: Simple Unsupervised Representation for Graphs, with Applications to Molecules

Shengchao Liu, Mehmet Furkan Demirel, Yingyu Liang

arXiv:1806.09206v2cs.LGstat.ML

TL;DR

Molecule property prediction requires representations for abstract attributed graphs, while existing fingerprints and GNNs trade efficiency and reusability against expressiveness and supervised training. N-gram graph learns vertex embeddings, aggregates them over short graph walks through a training-free GNN formulation, and reports better overall performance than traditional methods and several recent GNNs across 60 tasks from 10 datasets.

  • Problem

    Molecule property prediction needs suitable representations for abstract atom-and-bond graphs, while fingerprints and GNNs offer different trade-offs in efficiency, reusability, expressiveness, and supervised training.

  • Method

    N-gram graph unsupervisedly embeds vertices and constructs a compact graph representation by assembling vertex embeddings along graph walks, equivalently using a parameter-free GNN.

  • Results

    N-gram graph achieves overall better performance than classic representations and several popular GNNs across 60 tasks from 10 benchmark datasets.

  • Takeaways & Limitations

    The representation is simple, efficient, compact, permutation invariant, and reusable across tasks and machine-learning models.

  • Takeaways & Limitations

    The theoretical analysis uses a simplifying assumption, and the version that excludes the relevant walks is not presented because of its higher computational cost.

Abstract

from arXiv · show

Machine learning techniques have recently been adopted in various applications in medicine, biology, chemistry, and material engineering. An important task is to predict the properties of molecules, which serves as the main subroutine in many downstream applications such as virtual screening and drug design. Despite the increasing interest, the key challenge is to construct proper representations of molecules for learning algorithms. This paper introduces the N-gram graph, a simple unsupervised representation for molecules. The method first embeds the vertices in the molecule graph. It then constructs a compact representation for the graph by assembling the vertex embeddings in short walks in the graph, which we show is equivalent to a simple graph neural network that needs no training. The representations can thus be efficiently computed and then used with supervised learning methods for prediction. Experiments on 60 tasks from 10 benchmark datasets demonstrate its advantages over both popular graph neural networks and traditional representation methods. This is complemented by theoretical analysis showing its strong representation and prediction power.

1 Introduction

Molecule property prediction needs representations suited to graph-structured atom data. N-gram graph is introduced as an unsupervised, efficient alternative intended to combine the reusability of fingerprints with the predictive strength of graph neural networks.

  • Motivation: Virtual screening uses machine learning to predict molecular properties and can filter millions of molecules before costly physical experiments.The paper contrasts rapid virtual screening with accurate but slow and expensive physical screening.
  • Motivation: Molecule property prediction is difficult because raw inputs are abstract graphs of atoms with attributes that existing learning algorithms do not directly handle well.The paper identifies careful representation construction as the central challenge.
  • Existing approaches: Chemical fingerprints are simple, efficient, unsupervised, and reusable across machine-learning methods, whereas GNNs are more expressive but require labeled-data training and retraining for new tasks.GNN training is also described as computationally expensive and non-trivial.
  • Contribution: N-gram graph embeds vertices, assembles embeddings along graph walks, and forms a compact unsupervised representation without training its graph-embedding step.The method is evaluated on 60 tasks from 10 benchmark datasets and is reported to outperform classic representations and several popular GNNs overall.
  • Related work: The paper situates N-gram graph among chemical fingerprints, GNNs, and graph kernels, noting its relation to the Weisfeiler-Lehman kernel and GIN.These methods are presented as established approaches for graph-structured molecular data.

2 Preliminaries

Molecules are represented as attributed graphs, with atoms as vertices and bonds as edges. The paper motivates N-gram graph through NLP n-gram counts and lower-dimensional word-embedding sums.

  • Molecular graphs: A molecule is modeled as a graph whose vertices are atoms with attributes and whose edges encode bonds.Vertex attributes are stored in V, while bonding information is stored in adjacency matrix A.
  • Molecular graphs: Vertex attributes include discrete chemical information such as atom symbol, atom degree, and acceptor or donor indicators.Additional bond types and pairwise 3D distances are outside this work’s scope.
  • N-gram preliminaries: In NLP, an n-gram is a consecutive sequence of words, and an n-gram vector records how often each sequence occurs.For vocabulary V, the n-gram vector has dimension |V|^n.
  • N-gram preliminaries: Summing word embeddings transforms a high-dimensional count representation into a lower-dimensional vector while retaining a strong baseline.The construction is expressed as f(1) = Wc(1), where W contains word embeddings.

3 N-gram Graph Representation

N-gram graph first learns vertex embeddings from local attribute contexts, then represents a molecule by combining those embeddings across walks of increasing length. Its graph-embedding computation is a parameter-free, training-free GNN and the resulting representation is reusable across tasks and models.

  • Overview: N-gram graph has two stages: embed vertices first, then embed the graph using those vertex embeddings.The method separates representation learning for vertices from graph-level construction.
  • 3.1 Vertex Embedding: Each attribute value receives an embedding, and the embeddings for a vertex’s attributes are concatenated into a vertex representation.The attribute-specific matrices W^j are concatenated into W.
  • 3.1 Vertex Embedding: A CBoW-like neural network learns vertex embeddings by predicting a vertex’s attributes from the embeddings of its neighboring vertices.The neighborhood embeddings are summed before a fully connected network predicts the target attributes.
  • 3.1 Vertex Embedding: The vertex-embedding procedure is unsupervised and can transfer embeddings across datasets; even random vertex embeddings can provide reasonable performance.Numeric attributes can be padded to the learned embeddings for other attributes.
  • 3.2 Graph Embedding: An n-gram is a graph walk, and its embedding is the element-wise product of the vertex embeddings along that walk; walk-set embeddings are summed and concatenated through length T.The final representation fG has dimension Tr.
  • 3.2 Graph Embedding: The Bag-of-Walks construction is equivalent to a parameter-free GNN that updates each vertex by multiplying its embedding with the summed embeddings of its neighbors.The runtime is O(rT(m + me)), with r the embedding dimension, T the walk length, m the number of vertices, and me the number of edges.
  • Properties: The resulting representation is permutation invariant and can be reused for different tasks and machine-learning models.This follows from the method’s unsupervised construction and invariance to atom ordering.

4 Theoretical Analysis

The theoretical analysis argues that N-gram graph embeddings preserve walk-count information and support predictors competitive with those using count statistics or raw graphs under stated conditions.

  • Assumptions and Scope: The analysis excludes walks containing two vertices with identical attributes, an assumption that simplifies the proof; experiments without those walks show similar performance.The excluded-walk version is not presented as the main method because of its higher computational cost.
  • Representation Power: N-gram graph embeddings compress bag-of-n-cooccurrence count statistics while preserving their information.The count statistics concatenate attribute-value histograms across walks of lengths 1 through T.
  • Representation Power: Because walk-count statistics typically determine the graph, the N-gram representation can have full representation power for the graph.The paper illustrates this with a linear graph whose 2-grams suffice to reconstruct its structure.
  • Prediction Power: There exists a predictor on N-gram embeddings that performs as well as any predictor based on count statistics and, typically, raw graph input.For linear ℓ2-regularized classifiers, the paper provides a formal performance guarantee; nonlinear dependencies are handled empirically with classical models.

5 Experiments

Experiments evaluate N-gram graph across 60 molecular property tasks, comparing representations, learners, transferability, runtime, 3D-information settings, and hyperparameters. N-gram graph is generally competitive or superior, with especially strong results using XGBoost.

  • Experimental setup: The evaluation covers 60 tasks across six regression and four classification datasets, comparing N-gram graph with WL kernels, Morgan fingerprints, and graph neural networks.Tasks are evaluated independently with five-fold cross-validation; ROC-AUC or PR-AUC is used for classification because labels are highly skewed.
  • Overall performance: N-gram graph with XGBoost ranks first on 21 of 60 tasks and among the top three on 48, outperforming or matching competing methods.The advantage is consistent on Tox21 and significant on several QM9 tasks.
  • Overall performance: Random forest with Morgan fingerprints also outperforms recent graph neural networks on classification tasks.The authors suggest that using up to 4000 trees, rather than 75, may explain the improved performance.
  • Transferability: Vertex embeddings transferred from other datasets produce comparable Tox21 results, and even random embeddings can achieve good performance.The experiment uses N-gram graph with XGBoost on 12 Tox21 tasks and compares six embedding sources.
  • Computational cost: N-gram graph is much faster to construct than graph neural networks and the kernel method, although Morgan fingerprints can be faster.Vertex embeddings can be amortized across tasks or transferred, leaving graph embedding as the main runtime cost.
  • 3D information: On QM8 and QM9, N-gram graph achieves performance comparable to models using 3D information despite excluding spatial information.The comparison uses MAE against DTNN and MPNN-style models that exploit 3D information.
  • Hyperparameters: Increasing N-gram length T generally improves performance, whereas changing vertex embedding dimension r generally has little effect.This pattern is reported for 12 Tox21 classification tasks using ROC-AUC and for additional regression tasks.

6 Conclusion

The paper introduces N-gram graph as a simple, efficient, unsupervised molecule representation that produces compact embeddings usable with different learning methods. Experiments report overall better performance than traditional methods and several recent graph neural networks, while the method also supports broader graph-structured data applications.

  • N-gram graph provides a simple, efficient, compact, unsupervised representation for molecule learning.It can be applied with different learning methods.
  • Experiments show overall better performance than prototypical traditional representations and several recent graph neural networks.
  • The method was inspired by word embeddings and traditional N-gram methods in natural language processing.
  • N-gram graph can be formulated as a simple graph neural network and may handle general graph-structured data such as social networks.Future work includes applications to other graph-structured data, pre-training and fine-tuning vertex embeddings, and more powerful variants.

B.1 Raw Data: Representation as Graphs With Vertex Attributes

Molecules are represented as graphs whose vertices are atoms with discrete attributes and whose edges encode bonds. The section reviews fingerprint, sequence, graph-neural-network, and compressed-sensing foundations relevant to representing and predicting from these graphs.

  • Raw molecular graphs: A molecule graph has one vertex per atom, with atom attributes encoded in V and bonding information encoded in adjacency matrix A.The graph is denoted G = (V, A).
  • Vertex attributes: Molecular attributes are typically discrete, including atom symbol, degree, charge, acceptor status, and donor status.
  • Traditional representations: Morgan fingerprints iteratively hash circular molecular substructures into identifiers, while SMILES describes molecular structures as character sequences.SMILES can lose ring and branching information because molecules cannot be simply represented as linear sequences.
  • Graph neural networks: Graph neural networks iteratively aggregate neighborhood information, allowing each vertex to capture information from increasingly distant hops.After t iterations, a vertex captures information from vertices at most t hops away.
  • Compressed-sensing foundations: Compressed-sensing analysis studies when linear measurements preserve sparse signals and support exact recovery through RIP conditions.The cited recovery result states that k-sparse signals are recovered exactly under the relevant RIP condition.
  • Prediction analysis: The paper uses RIP-based results to connect preserved graph-walk statistics with prediction by linear classifiers on N-gram graph embeddings.Under the specified conditions, the constructed mappings satisfy the required RIP property with high probability.

D Task Specification

The task specification records the positive-example counts and total molecule counts for benchmark classification tasks across Tox21, ClinTox, MUV, and HIV datasets.

  • Table S1 reports positive and total molecule counts for 12 Tox21 tasks.
  • Table S2 reports positive and total molecule counts for 2 ClinTox tasks.
  • Table S3 reports positive and total molecule counts for 17 MUV tasks.
  • Table S4 reports positive and total molecule counts for 1 HIV task.

E Atom Feature Specification

The experiments encode molecular atoms with categorical feature attributes, use dataset-specific feature availability, and compare N-gram graph with fingerprint, neural-network, kernel, and tree-based baselines under specified training procedures.

  • Atom features: The atom representation uses d = 42 features divided into S = 8 attributes, with an Unknown value for unenumerated or missing property values.
  • Dataset-specific features: QM8 and QM9 use only d = 32 features across S = 5 attributes because some atom properties cannot be extracted while retaining 3D information.
  • Baselines: Morgan fingerprints use 1024 bits and radius 2, following the benchmark hyperparameters.
  • Baselines: Graph CNN, Weave Neural Network, Deep Tensor Neural Network, and Message-Passing Neural Network use dataset-specific optimal hyperparameter schemes.
  • N-gram graph: N-gram graph hyperparameters include random dimension r and n-gram number T, whose effects are discussed separately.
  • Baselines: Weisfeiler-Lehman kernel, random forest, XGBoost, and Graph Isomorphism Network baselines use grid-search hyperparameter sweeps.
  • Training procedure: Vertex embeddings are learned with an unsupervised CBoW-like model using 5-fold cross-validation, then applied to target molecules before supervised training.The process separately trains the vertex embedding and graph embedding stages.

H Complete Results on 60 Regression and Classification Tasks

The supplementary results compare N-Gram Path and N-Gram Walk representations across 28 regression and 32 classification tasks, using random forest and XGBoost predictors. N-Gram Walk generally performs better, especially with XGBoost on regression tasks.

  • The evaluations cover 28 regression tasks and 32 classification tasks using 5-fold cross-validation and means over 5 runs.
  • N-Gram Path and N-Gram Walk use the same vertex embeddings, with random forest and XGBoost trained on top of the graph representations.
  • N-Gram Walk with XGBoost excels on 27 of 28 regression tasks, while N-Gram Path achieves comparable performance.
  • N-Gram Walk with random forest and XGBoost excels on 5 and 15 of 32 classification tasks, respectively.
  • Average classification performance is better with N-Gram Walk for both random forest and XGBoost, except XGBoost on HIV.

J Additional Experiments on Datasets with 3D Information

The paper evaluates N-Gram graph on datasets containing 3D molecular information and on Tox21 tasks while varying representation parameters. It reports comparable performance without using 3D information and generally improved Tox21 ROC-AUC as the walk length increases.

  • The 3D-information comparison uses DTNN and MPNN on the two datasets QM8 and QM9.
  • N-Gram graph achieves comparable performance to DTNN and MPNN on QM8 and QM9 despite not using 3D information.
  • Across 12 Tox21 classification tasks, ROC-AUC generally rises as the N-gram parameter T increases.
  • ROC-AUC does not increase as vertex embedding dimension r increases on the Tox21 test set.
  • The authors suggest insufficient data and ROC-AUC’s ranking-based evaluation as two possible reasons for the unstable relationship between r and performance.

K.2 On 3 Regression Tasks (Delaney, Malaria, CEP)

Experiments on Delaney, Malaria, and CEP examine how vertex-embedding dimension r and N-gram parameter T affect regression performance. Increasing T can reduce loss, whereas performance varies substantially with r and T, motivating r = 100 and T = 6 as reasonable choices.

  • The experiments vary vertex embedding dimension r and N-gram parameter T on Delaney, Malaria, and CEP.
  • Increasing T can reduce loss on the Delaney, Malaria, and CEP regression tasks, while performance fluctuates substantially as r and T increase.
  • Vertex embedding dimension r shows comparatively unstable performance across the three regression tasks.
  • The authors conjecture that data insufficiency may cause the high variance observed across parameter settings.
  • The reported conclusion is that r = 100 and T = 6 are reasonable choices for each machine learning algorithm.
  • A statistical test compares the new and original atom-attribute schemes across message-passing graph methods on 12 Tox21 tasks.
Loading 1806.09206v2…