Source-linked AI summary
GraphiT: Encoding Graph Structure in Transformers
Grégoire Mialon, Dexiong Chen, Margot Selosse, Julien Mairal
TL;DR
Graph representation learning needs structural and positional information that transformers do not obtain from unordered node sets. GraphiT adds kernel-based relative positional attention and local substructure features, and performs as well as or better than baseline GNNs across benchmarks while supporting motif interpretation.
Problem
Transformers are permutation-invariant on graph node sets, while graph positional encoding is challenging because graph structures vary and node position is ill-defined.
Method
GraphiT uses transformer attention with graph-kernel relative positional encodings and enriches node features with enumerated local substructures such as GCKN paths.
Results
Across classification and regression benchmarks, GraphiT performs as well as or better than baseline GNNs, with relative positional encoding and structure encoding each effective and their combination improving results.
Takeaways & Limitations
GraphiT provides a transformer-based graph representation approach with attention-based visualization mechanisms for discovering discriminative graph motifs.
Takeaways & Limitations
Self-attention complexity scales quadratically with input-sequence size, potentially limiting GraphiT’s application to large graphs.
Abstract
from arXiv · showhide
We show that viewing graphs as sets of node features and incorporating structural and positional information into a transformer architecture is able to outperform representations learned with classical graph neural networks (GNNs). Our model, GraphiT, encodes such information by (i) leveraging relative positional encoding strategies in self-attention scores based on positive definite kernels on graphs, and (ii) enumerating and encoding local sub-structures such as paths of short length. We thoroughly evaluate these two ideas on many classification and regression tasks, demonstrating the effectiveness of each of them independently, as well as their combination. In addition to performing well on standard benchmarks, our model also admits natural visualization mechanisms for interpreting graph motifs explaining the predictions, making it a potentially strong candidate for scientific applications where interpretation is important. Code available at https://github.com/inria-thoth/GraphiT.
1 Introduction
Graph representation learning must balance tractability, task adaptability, and sensitivity to topology and local structure across diverse scientific graph data. GraphiT uses transformer global communication while injecting graph structure through relative positional encodings and local substructure features.
- Graph-structured data arise in applications including proteins, molecules, shapes, electronic health records, and social-network communities.
- Graph representation methods must be computationally tractable, adaptable to tasks, and able to distinguish topology and local characteristics.
- Transformers can communicate across all graph nodes in one self-attention layer, unlike GNNs’ successive local neighbor aggregation, but require graph positional information.
- GraphiT encodes graph structure with positive-definite-kernel relative positional attention and features from enumerated local substructures such as short paths.
- GraphiT performs competitively across classification and regression benchmarks, including outperforming GNNs on various tasks and supporting visualization of discriminative graph motifs.
2 Related work
Related work spans graph kernels, message-passing GNNs, and transformer-based graph models. GraphiT differs by using graph structure and node positional encodings to make vanilla transformers competitive with GNNs for graph prediction.
- Graph kernels embed graphs by counting local substructure occurrences, including walks, shortest paths, subtrees, and graphlets.
- Graph kernels seek expressive, discriminative substructure representations while retaining efficient inner-product computation.
- GNNs use message passing between neighboring nodes, while GAT applies attention to aggregate local information.
- Prior graph transformers use all-node attention without positional encoding, sampled subgraphs, aggregated encodings, or graph transformations through meta-paths.
- GraphiT is presented as the first model to show that vanilla transformers with appropriate node positional encoding can compete with GNNs in graph prediction tasks.
3 Preliminaries about Kernels on Graphs
Graph kernels on graphs are constructed from graph Laplacian spectra and provide positive-definite measures of node similarity. Diffusion and random-walk kernels offer dense or sparse structural connectivity that can be incorporated into transformer attention.
- The graph Laplacian is L = D − A, with D containing node degrees and A the adjacency matrix.
- Laplacian eigenvectors characterize graph-function oscillation and provide a discrete analogue of Fourier bases; normalized Laplacians preserve this interpretation.
- Applying a non-increasing regularization function r to the Laplacian spectrum produces a family of positive-definite graph kernels.
- The diffusion kernel uses r(λ_i) = e^(-βλ_i) and can be interpreted as substance accumulated after diffusion over time controlled by β.
- The p-step random-walk kernel uses r(λ_i) = (1 − γλ_i)^p and connects nodes only when a path of length p exists.
- Random-walk kernels are sparse with limited connectivity, whereas diffusion kernels are dense, and their Gram matrices can encode structural node similarity in transformers.
4 Encoding Graph Structure in Transformers
GraphiT treats graphs as sets of node features processed by a transformer, then injects structural information through attention kernels and local substructure encodings. These mechanisms support either global or local communication while addressing permutation invariance and graph-specific positional ambiguity.
- Transformer architecture: GraphiT processes graphs as sets of node features through a vanilla transformer encoder for classification and regression tasks.The encoder maps X in R^n×d_in to representations in R^n×d_out across successive layers.
- Transformer architecture: Because transformer outputs are permutation-invariant, GraphiT must provide information about graph structure and node positions.The paper contrasts this requirement with local aggregation baselines similar to GAT or earlier graph transformers.
- Relative position encoding: GraphiT modulates attention scores with Gram matrices from graph kernels, using structural similarity between nodes as relative positional information.The approach avoids relying on transferable absolute positional encodings between different graph Laplacians.
- Relative position encoding: The modulated attention performs kernel smoothing by combining content-based attention with graph-based positional similarity before row normalization.The resulting non-negative weights form a combined node kernel and sum to one across each row.
- Relative position encoding: Kernel choice encodes prior structural knowledge, while its parameter controls the attention span from nearby-focused to more homogeneous.For diffusion kernels, β represents diffusion duration: smaller β focuses attention on close neighbors, whereas larger β broadens it.
- Topological structure encoding: GraphiT also enriches node features with local substructures, especially short paths encoded through GCKN-style kernel embeddings.Each GCKN layer enumerates paths up to a chosen length, embeds them, and aggregates their representations, producing features richer than traditional neighborhood aggregation.
5 Experiments
The experiments evaluate GraphiT against GNNs and positional-encoding baselines across graph classification and regression tasks. Results support combining relative positional encoding with structural node features, while attention visualizations identify chemically meaningful motifs.
- Benchmark and baselines: The evaluation compares GraphiT, GNNs, transformer, and positional-encoding baselines on MUTAG, PROTEINS, PTC, NCI1, and ZINC.The benchmark includes four classification datasets and one regression dataset, with repeated train/validation/test splits for most datasets.
- Comparison with baselines: GraphiT performs as well as or better than baseline GNNs across datasets and outperforms all previous baselines by a large margin on ZINC.The authors report a positive answer to whether appropriately encoded transformers can outperform GNNs.
- Relative position encoding: Diffusion-kernel positional encoding preserves global communication while achieving performance close to sparse local encodings, and adjacency encoding is effective on many datasets.The results indicate that sparse local positional encoding is generally useful, tempering the broader conclusion about global attention.
- Structure encoding: Encoding topology directly in node features substantially improves vanilla transformers on almost all datasets, with GCKN-path features generally outperforming Laplacian positional encoding.GCKN provides a pronounced boost on ZINC, except that its advantage does not hold on MUTAG and PROTEINS.
- Combined encoding: Combining relative positional encoding with structural node features globally improves performance, with GCKN plus relative encoding producing the strongest reported combinations.GCKN with adjacency encoding performs best for MUTAG and NCI1, while GCKN with the 3-step random-walk kernel is second-best for ZINC.
- Visualization: Attention scores provide visualization mechanisms that identify discriminative graph motifs, including nitro and amino groups associated with correctly classified mutagenic compounds.Later attention layers become sparser, and salient columns indicate important nodes; examples also include long-range intramolecular hydrogen bonds.
6 Conclusion
GraphiT uses transformers to aggregate local graph substructures with positional encoding, while attention scores provide a simple route to model interpretation and future scaling studies.
- GraphiT combines transformer aggregation of local substructures with appropriate positional encoding for graph representation.
- Attention scores provide simple mechanisms for interpreting the model.
- Evaluating whether GNNs and GraphiT scale similarly during large self-supervised pre-training is proposed as future work.
A Experimental Details
This section provides implementation details and additional experimental results.
- The appendix section reports implementation details.
- The appendix section also reports additional experimental results.
- The section is supplementary to the paper’s main presentation.
A.1 General Details.
The experiments used Tesla V100 GPUs, approximately 20k GPU hours, and specified kernel and structure-encoding parameters across datasets.
- Computing infrastructure: Computations used a GPU cluster equipped with Tesla V100-16G and Tesla V100-32G cards.
- Computing infrastructure: Approximately 20k GPU hours covered preliminary experiments, model design, baseline evaluation, and final experiments.
- Position and structure encoding: The diffusion-kernel parameter β was fixed to 1.0, while γ was fixed to 0.5 for both 2- and 3-step random-walk kernels.
- Position and structure encoding: Laplacian positional encoding used dimension 8 for ZINC and dimension 2 for graph-classification datasets.
- Other details: GraphiT feed-forward hidden layers were fixed at twice the attention dimensions.
A.2 Graph Classification Datasets
The graph-classification experiments covered five molecular and protein datasets, used specified train/validation procedures, and selected models through validation performance and parameter grids.
- Datasets: The experiments covered MUTAG, PROTEINS, PTC, NCI1, and Mutagenicity graph-classification datasets.Tasks included molecular mutagenicity, protein-enzyme, carcinogenicity, lung-cancer, and compound-mutagenicity classification.
- Training splits: MUTAG, PROTEINS, PTC, and NCI1 used outer splits from, with inner train-validation splits provided in the code.
- Training splits: Test-accuracy error bars for four datasets were standard deviations across 10 outer folds.
- Hyperparameter choices: Parameter grids were specified separately for GNNs, GCKN, and transformer-based models, with best models selected using validation scores.
- Optimization: GraphiT and the comparison transformer used batch size 32, a learning-rate-halving schedule every 50 epochs, and 300 training epochs.
A.3 Graph Regression Dataset
The ZINC appendix evaluates graph-property regression under controlled training and comparison settings. Larger models and modified diffusion-kernel attention improve performance, with the best result obtained by combining diffusion-kernel positional encoding and GCKN node features.
- Dataset: ZINC contains 250k compounds, with constrained solubility prediction formulated as graph-property regression.The reported subset uses 10k, 1k, and 1k graphs for training, validation, and testing.
- Experimental setup: The experiments use matched architectural settings and reported baselines to support fair comparisons with prior work.The transformers use 10 layers, 8 heads, and hidden dimension 64; their parameter count is two-thirds that of the compared model.
- Additional results: Increasing hidden dimensions generally boosts performance, especially for transformer variants using Laplacian positional encoding in node features.The additional results compare larger models with 128 hidden dimensions.
- Additional results: Zeroing the attention-kernel diagonal considerably improves longer-range relative positional encodings.The improvement is especially pronounced for diffusion-kernel positional encoding combined with GCKN features.
- Additional results: The diffusion-kernel transformer combined with GCKN node features achieves the best performance among the reported positional-encoding variants.The comparison also reports sparse local positional encoding as more useful than diffusion-kernel positional encoding before this diagonal modification.
B Additional visualization of Mutagenicity compounds
The Mutagenicity visualization analysis uses attention scores to identify molecular substructures associated with correctly classified mutagenic compounds. Across the examples, highlighted atoms or groups correspond to chemically known mutagenicity-related structures.
- Visualization approach: Attention scores are analyzed across layers for correctly classified mutagenic molecules to detect potentially explanatory substructures.The visualization uses scores averaged across heads and examines samples from the Mutagenicity dataset.
- 1,2-Dibromo-3-Chloropropane: For DBCP, attention focuses on the carbon skeleton and both bromine atoms, which are associated with mutagenicity.The corresponding figure compares a diffusion-kernel pattern with the model’s salient nodes.
- Nitrobenzene-nitroimidazothiazole: For nitrobenzene-nitroimidazothiazole, the model emphasizes two nitro groups known to induce mutagenicity.The attention visualization is presented alongside the compound structure.
- Triethylenemelamine: For triethylenemelamine, the model focuses on three nitrogen atoms in aziridine groups, themselves mutagenic compounds.The figure reports these nitrogen atoms as salient in the attention visualization.