PaperlayerView exact revision on arXiv

Source-linked AI summary

A Generalization of Transformer Networks to Graphs

Vijay Prakash Dwivedi, Xavier Bresson

arXiv:2012.09699v2cs.LG

TL;DR

The paper addresses how to adapt transformers, whose fully connected attention does not inherently exploit graph topology, to arbitrary graphs. It introduces a Graph Transformer using neighborhood connectivity, Laplacian positional encodings, batch normalization, and edge-feature representations. Experiments report improved performance over baseline GNNs, while comparisons with several positional encodings remain limited.

  • Problem

    Transformers do not inherently exploit graph connectivity, while graph positional encodings are challenging because graph symmetries prevent canonical node positions.

  • Method

    The paper generalizes transformers to arbitrary homogeneous graphs with neighborhood-aware attention, Laplacian eigenvector positional encodings, batch normalization, and an edge-feature pipeline.

  • Results

    The proposed architecture surpasses baseline isotropic and anisotropic GNNs and performs best across the benchmark settings when using Laplacian positional encodings with batch normalization.

  • Takeaways & Limitations

    The simple, generic architecture is proposed as a baseline for future graph applications involving node attention.

  • Takeaways & Limitations

    The experiments do not empirically compare with most other positional encodings in the Graph Transformer literature because some methods omit positional encodings or use specialized schemes.

Abstract

from arXiv · show

We propose a generalization of transformer neural network architecture for arbitrary graphs. The original transformer was designed for Natural Language Processing (NLP), which operates on fully connected graphs representing all connections between the words in a sequence. Such architecture does not leverage the graph connectivity inductive bias, and can perform poorly when the graph topology is important and has not been encoded into the node features. We introduce a graph transformer with four new properties compared to the standard model. First, the attention mechanism is a function of the neighborhood connectivity for each node in the graph. Second, the positional encoding is represented by the Laplacian eigenvectors, which naturally generalize the sinusoidal positional encodings often used in NLP. Third, the layer normalization is replaced by a batch normalization layer, which provides faster training and better generalization performance. Finally, the architecture is extended to edge feature representation, which can be critical to tasks s.a. chemistry (bond type) or link prediction (entity relationship in knowledge graphs). Numerical experiments on a graph benchmark demonstrate the performance of the proposed graph transformer architecture. This work closes the gap between the original transformer, which was designed for the limited case of line graphs, and graph neural networks, that can work with arbitrary graphs. As our architecture is simple and generic, we believe it can be used as a black box for future applications that wish to consider transformer and graphs.

1 Introduction

The paper generalizes transformers from fully connected word graphs to arbitrary graphs by combining graph sparsity, positional encodings, and attention-based message passing. It introduces a generic Graph Transformer with Laplacian positional features and explicit edge-feature support.

  • Transformers model fully connected word graphs, whereas graph neural networks exploit graph structure across applications including knowledge graphs, social sciences, and physics.
  • Graph Transformer preserves graph sparsity and local contexts instead of attending to all graph nodes, using positional features to incorporate structural information.The paper identifies sparsity and positional encodings as key aspects of graph transformers.
  • The proposed model generalizes transformer networks to homogeneous graphs of arbitrary structure and extends them with a dedicated pipeline for explicit edge features.Edge features provide domain information that can be maintained through the architecture.
  • Laplacian eigenvectors fuse node positional features for graph datasets and are presented as a generic positional encoding for arbitrary homogeneous graphs.The method uses Laplacian eigenvectors because graph node positions are difficult to define canonically under graph symmetries.
  • The architecture outperforms baseline isotropic and anisotropic GNNs while serving as both an attention-based GNN baseline and a transformer baseline for graph datasets.

2 Proposed Architecture

The proposed Graph Transformer adapts transformer-style attention to arbitrary graph connectivity while incorporating graph positional information and optional edge attributes. It uses Laplacian eigenvectors for node positions and supports a separate edge-feature representation pipeline.

  • Motivation: Graph Transformer exploits arbitrary graph connectivity as an inductive bias instead of treating every node pair as connected.Graph datasets provide domain-specific connectivity, while fully connected processing is impractical for very large graphs.
  • Positional Encodings: Laplacian eigenvectors provide node positional encodings intended to preserve positional information in graphs with structural symmetries.The model uses the k smallest non-trivial eigenvectors and projects them into the node feature space at the input layer.
  • Input Representations: Input node and edge features are linearly projected into hidden representations before graph-transformer processing.Projected positional encodings are added to node features only at the input layer.
  • Graph Transformer Layer: The Graph Transformer layer computes multi-head attention over each node’s neighborhood, followed by feed-forward, residual, and normalization components.The architecture is closely related to the original transformer but restricts attention to graph neighbors.
  • Edge Features: The edge-feature extension ties explicit edge attributes to pairwise attention scores and propagates edge representations across layers.This design maintains a designated edge-feature pipeline alongside node updates.

3 Numerical Experiments

The experiments evaluate the proposed Graph Transformer on ZINC, PATTERN, and CLUSTER under a common graph-benchmarking protocol. ZINC uses the edge-feature model, while PATTERN and CLUSTER use the simpler Graph Transformer because they lack explicit edge features.

  • Benchmark Datasets: The evaluation covers three benchmark datasets: ZINC, PATTERN, and CLUSTER.The datasets span molecular graph regression and synthetic node-classification or clustering tasks.
  • ZINC: ZINC tests graph property regression for constrained solubility using molecular graphs whose bonds provide edge attributes.The experiments use the 12K subset and the Graph Transformer with edge features.
  • PATTERN: PATTERN is a 14K-graph node-classification dataset requiring assignment of nodes to two communities.Because PATTERN has no explicit edge features, the simple Graph Transformer is used.
  • CLUSTER: CLUSTER assigns each node one of six cluster labels in a 12K-graph synthetic dataset.Like PATTERN, CLUSTER lacks explicit edge features and uses the simple Graph Transformer.
  • Protocol: The benchmarking protocol uses 10 layers, 8 attention heads per layer, approximately 500k parameters, learning-rate decay, and four random seeds.Reported results are means and average performance measures across the four runs.

4 Analysis and Discussion

Experiments show that Laplacian positional encodings with batch normalization provide the strongest Graph Transformer configuration, outperforming standard GNN baselines and benefiting from sparse connectivity. The edge-feature extension approaches GatedGCN on ZINC, while WL-PE can overfit SBM datasets.

  • Configuration: Laplacian positional encodings with batch normalization achieved the highest performance across all three benchmark datasets.The comparison includes alternative positional encodings and normalization choices.
  • Baseline comparison: The proposed architecture significantly outperformed GCN and GAT, establishing an improved attention-based GNN baseline.Table 2 compares models using 500k parameters; GatedGCN and Graph Transformer use ZINC edge attributes.
  • Connectivity: Sparse graph connectivity is a critical inductive bias for datasets with arbitrary graph structure.Experiments compare the given sparse graphs with fully connected versions.
  • Edge features: The edge-feature Graph Transformer reached close to GatedGCN, the best-performing GNN, on ZINC.The comparison uses the available edge attributes for both models.
  • Positional encodings: Laplacian positional encodings outperformed WL-PE because they better capture structural and positional information.WL-PEs tended to overfit SBM datasets and produced poor generalization.

5 Conclusion

The paper presents a simple, generic Graph Transformer for arbitrary graphs. Experiments consistently found that Laplacian eigenvectors and batch normalization enhance performance, supporting the model as a baseline for future graph applications.

  • Conclusion: The proposed architecture generalizes transformer networks to arbitrary graphs through a simple and effective design.The authors position it as a generic model rather than a task-specific best-performing architecture.
  • Conclusion: Laplacian eigenvectors and batch normalization consistently enhanced the transformer across all experiments.Batch normalization replaces layer normalization around the transformer feed-forward layers.
  • Future use: The model is proposed as a baseline for further improvement across graph applications using node attention.Future work includes efficient training on large graphs and applicability to heterogeneous domains.

A.1 Task based MLP layer equations

Task-specific MLP layers convert final node or graph representations into prediction scores. Their objectives and inputs differ between graph prediction, node prediction, and adaptable edge-prediction settings.

  • Graph prediction: Graph prediction averages final node features into a graph-level vector before applying an MLP.For ZINC, the model performs single-target regression with C = 1 and minimizes L1 loss.
  • Node prediction: Node prediction passes each node feature vector through an MLP to compute class scores.Training uses cross-entropy loss weighted inversely by class size.
  • Edge prediction: Edge prediction can use Graph Transformer edge outputs with task-specific MLP layers defined analogously to node prediction.Final or intermediate Graph Transformer layers can also feed the task MLPs, including JK Readout-style schemes.

A.2 Hardware Information

Experiments ran on a multi-GPU Intel Xeon server under a 24-hour per-experiment training limit.

  • Hardware: Experiments used an Intel Xeon E5-2690 v4 server with four Nvidia 1080Ti GPUs.Four experiments ran concurrently, with one experiment assigned to each GPU.
  • Runtime: Each experiment had a maximum training time of 24 hours.The stated limit applied to every experiment on the server.
Loading 2012.09699v2…