Expressive Graph Informer Networks

Jaak Simm, Adam Arany, Edward De Brouwer, Yves MoreauLod 2021 · DOI

TL;DR

This paper introduces "Graph Informer," a novel graph neural network architecture that enhances information flow by considering "routes" between nodes, not just direct connections. This allows it to capture longer-range dependencies and nonlocal graph topology, leading to state-of-the-art results in predicting molecular properties like NMR spectra and drug bioactivity.

What Problem Does This Paper Address?

Representing molecules as graphs is natural, but existing graph neural networks (GNNs) often suffer from an "information bottleneck." They primarily pass information between directly connected nodes (neighbors). To capture information from nodes further away, these networks require stacking many layers, which can be computationally expensive and lead to vanishing gradients. This limits their ability to understand the global structure and complex relationships within a graph, especially for tasks requiring nonlocal information.

Methods

The core innovation is the Graph Informer architecture, which builds upon the transformer's self-attention mechanism. It introduces Route-based Multi-Head Self-Attention (RouteMHSA). This mechanism augments the standard attention by incorporating features from "routes" connecting pairs of nodes. These routes can represent paths of varying lengths and include information about the edges along the path (e.g., bond types in molecules).

Key components:

  • Route Features: These are derived from the graph's adjacency matrix and edge labels, capturing information about paths between nodes.
  • Route Query and Key: The model learns to query and key representations for these routes, allowing them to be matched with node representations.
  • Route-based Attention: The attention scores are computed by combining the standard node-to-node attention with attention based on the route features. This allows a node to attend to information from nodes that are not its direct neighbors.
  • Multi-Head Attention: Similar to transformers, multiple RouteMHSA layers are run in parallel to capture diverse relationships.
  • Residual Network Architecture: The paper adopts a residual network structure with Layer Normalization, which proved more stable and easier to train than a direct transformer-style architecture for graph tasks.
  • Injective Graph Informer: A variant is proposed that is provably as powerful as the Weisfeiler-Lehman (WL) test for graph isomorphism, a standard benchmark for graph distinguishability.

Datasets

The paper evaluates Graph Informer on two main types of tasks:

  • Node-level task:
    • 13C Nuclear Magnetic Resonance (NMR) spectrum prediction: Using data from NMRShiftDB2, containing 25,645 molecules.
  • Graph-level tasks:
    • Drug bioactivity prediction: Using the ChEMBL v23 dataset (94 tasks, 87,415 molecules).
  • Compound toxicity prediction: Using the Tox21 dataset from MoleculeNet (12 tasks, 7,831 molecules).

The paper also uses synthetic datasets of regular graphs to test the expressiveness of the model, specifically highlighting its ability to distinguish graphs that the WL test cannot.

Key Insights and Ideas

  • Routes as a powerful graph representation: The paper demonstrates that explicitly considering "routes" between nodes, beyond direct adjacency, significantly enhances a GNN's ability to capture nonlocal graph structure. This is analogous to how dilated convolutions in CNNs allow for larger receptive fields.
  • Beyond the Weisfeiler-Lehman test: The Graph Informer, particularly its injective variant, shows promise in surpassing the expressiveness limitations of the WL test, which is a known bottleneck for many GNNs. This is crucial for distinguishing subtly different but structurally similar graphs.
  • Improved performance on challenging tasks: The architecture's ability to capture longer-range dependencies directly translates to better performance on tasks like NMR prediction, where subtle differences in molecular structure can lead to very close spectral peaks.

Key Results

  • NMR 13C Spectrum Prediction: Graph Informer achieved a state-of-the-art Mean Absolute Error (MAE) of 1.35 ppm, outperforming existing methods. This accuracy is critical for resolving densely packed spectral regions.
  • Graph-level Tasks (ChEMBL & Tox21): Graph Informer outperformed all baseline methods on both drug bioactivity and toxicity prediction tasks, achieving the highest AUC-ROC scores.
  • Graph Isomorphism: The model demonstrated the ability to distinguish between regular graphs that are indistinguishable by the WL test, showcasing its enhanced expressiveness.

Limitations and Future Work

  • Computational Complexity: The RouteMHSA has a quadratic complexity with respect to the number of nodes, limiting its direct application to graphs with a few hundred to a maximum of 1,000 nodes. However, the authors note this is sufficient for typical drug-like compounds.
  • Future Work: The paper suggests exploring more sophisticated route feature representations and investigating the model's capabilities on even larger and more complex graph structures. The potential for Graph Informer to go beyond the WL test is highlighted as a significant avenue for future research.

Summary updated

BibTeX
@inproceedings{simm2021expressive,
  author = {Jaak Simm and Adam Arany and Edward De Brouwer and Yves Moreau},
  title = {{Expressive Graph Informer Networks}},
  booktitle = {Lod},
  year = {2021},
  doi = {10.1007/978-3-030-95470-3\_15},
}
Figure