PaperlayerView exact revision on arXiv

Source-linked AI summary

GRPE: Relative Positional Encoding for Graph Transformer

Wonpyo Park, Woonggi Chang, Donggeon Lee, Juntae Kim, Seung-won Hwang

arXiv:2201.12787v3cs.LGcs.AI

TL;DR

Graph Transformers need positional information, but graphs lack inherent absolute node positions, and existing encodings either lose relative-position precision through linearization or omit tight node-edge and node-topology interaction. GRPE encodes these relations through node-feature interactions on attention maps and values. The paper reports state-of-the-art performance across varied graph datasets and tasks.

  • Problem

    Graph Transformers need positional information despite graphs lacking inherent absolute node positions, while existing encodings lose relative-position precision through linearization or omit tight node-edge and node-topology interaction.

    Source: Introduction · p. 1

  • Method

    GRPE uses learnable topology and edge encodings that interact with node features, encoding graph relations on both attention maps and values.

    Source: Introduction · p. 1, Our Approach · p. 3

  • Results

    The authors report state-of-the-art performance on various graph datasets across graph classification, regression, and node classification tasks.

    Source: Introduction · p. 2

  • Takeaways & Limitations

    The paper validates GRPE quantitatively and qualitatively across tasks and datasets with diverse sizes and characteristics.

    Source: Conclusion · p. 7

Abstract

from arXiv · show

We propose a novel positional encoding for learning graph on Transformer architecture. Existing approaches either linearize a graph to encode absolute position in the sequence of nodes, or encode relative position with another node using bias terms. The former loses preciseness of relative position from linearization, while the latter loses a tight integration of node-edge and node-topology interaction. To overcome the weakness of the previous approaches, our method encodes a graph without linearization and considers both node-topology and node-edge interaction. We name our method Graph Relative Positional Encoding dedicated to graph representation learning. Experiments conducted on various graph datasets show that the proposed method outperforms previous approaches significantly. Our code is publicly available at https://github.com/lenscloth/GRPE.

Introduction

Because a Transformer is permutation equivariant, graph nodes need positional information despite lacking an inherent absolute order. GRPE encodes relative topology and edge information through interactions with node features, and the paper reports state-of-the-art results on varied graph tasks.

Introduction

  • Prior graph approaches either linearize nodes for absolute positions, losing positional precision, or use relative-position biases that omit tight node-edge and node-topology integration.The Transformer’s permutation equivariance makes explicit positional representations important, but graph nodes have no inherent absolute order.Source: Introduction · p. 1
  • GRPE models graph position through topology and edge encodings that interact with node features, placing positional information on both the attention map and value.The method avoids linearizing the graph and integrates node-topology and node-edge relations.Source: Introduction · pp. 1–2, Figure 2 · p. 2
  • GRPE generalizes relative positional encoding from 1D sequences to graph-relative positions and graph-specific properties.The paper relates its approach to work on relative position in sequences, which it says does not generalize to graphs.Source: Introduction · p. 2
  • The authors report state-of-the-art performance on various graph datasets across graph classification, graph regression, and node classification tasks.They name the method Graph Relative Positional Encoding (GRPE).Source: Introduction · p. 2

Related Work

Graph Transformer work has progressed from attention without explicit positional information to absolute encodings and relative-position biases. These approaches differ in how they represent graph structure and in what information their encodings retain.

Related Work

  • Earlier models either restrict self-attention to neighboring nodes or interleave it with graph convolution, without giving self-attention explicit positional information.In the latter approach, affinity is considered only in the graph-convolution layers.Source: Related Work · p. 2
  • Absolute positional methods linearize a graph into a node sequence and add encodings to input features, but lose positional precision through linearization.Examples use graph Laplacian or learnable encodings based on the Laplacian spectrum.Source: Related Work · p. 2
  • Graphormer adds relative-position bias to attention, while Shaw, Uszkoreit, and Vaswani’s relative encoding models sequences and is adapted here to graph-specific edge and topology relations.The passage says Graphormer’s bias terms are parameterized by relative position and do not interact with node features.Source: Related Work · p. 2

Background

The background defines graph notation and the self-attention operations used in the paper. It then reviews graph positional encodings in attention or input features, and introduces virtual-node and Laplacian examples.

Notation

  • The graph is represented by indexed nodes and edges, with N denoting the number of nodes, N_i the neighbors of node n_i, and ψ(i,j) a function encoding topological relations.Node and edge indices can denote types such as molecule atoms and bonds.Source: Notation · p. 2

Self-attention

  • Self-attention transforms node input features x_i into queries, keys, and values, computes an attention map from query-key similarity, and uses weighted values to produce the next hidden feature.The input and output features are denoted x_i and z_i, respectively.Source: Self-attention · pp. 2–3

Graph with Transformer

  • Graphormer adds topology and edge terms to the attention map, whereas Laplacian methods add graph positional encodings to input features.The cited Laplacian encoding uses eigenvectors of a normalized graph Laplacian and represents topology with respect to each node.Source: Graph with Transformer · p. 3
  • A virtual node connects to all other nodes and represents the graph; GRPE assigns it special edge and topology encodings, while its shortest-path relation to other nodes is excluded.The virtual node’s output feature is used as input to the downstream prediction branch.Source: Figure 3 · p. 3

Our Approach

GRPE integrates node–topology and node–edge interactions in attention, and also adds relative positional information to self-attention value features. Its node-aware attention works node-wise, while graph-encoded values work channel-wise.

Our Approach

  • GRPE combines node–topology and node–edge interactions in attention with relative positional information added to self-attention value features.Node-aware attention operates node-wise; graph-encoded values operate channel-wise.Source: Our Approach · p. 3

Relative Positional Encoding for Graph

Node-Aware Attention

  • Node-aware attention adds topology- and edge-interaction maps to scaled dot-product attention, allowing query and key features to yield different topology values than Graphormer's distance-only bias.The maps consider node–topology and node–edge relations.Source: Node-Aware Attention · p. 4

Graph-Encoded Value

  • Graph-encoded values add topology and edge information to attention-weighted hidden features, enriching channels and enabling channel-wise attention.This encodes relative position directly on hidden features rather than on linearized input positions.Source: Graph-Encoded Value · p. 4

Complexity Analysis

  • Precomputing node-feature interactions reduces the stated complexity from O(N^2dz) to O(NLdz) for topology and O(NEdz) for edge encodings.The passage attributes the reduction to L and E being much smaller than the number of nodes N.Source: Complexity Analysis · p. 4

Experiment

GRPE is evaluated on molecular graph classification and regression benchmarks, with the authors reporting state-of-the-art results across ZINC, MolHIV, and MolPCBA. The experiments use graph-specific positional encodings and a virtual node for downstream prediction.

Implementation Details

Graph Classification and Regression

  • The authors report state-of-the-art MAE on ZINC, AP on MolPCBA, and AUC on MolHIV, with fewer parameters than Graphormer on MolHIV.The reported metrics are mean absolute error, average precision, and area under the curve, respectively.Source: Table 2 · p. 5, Table 3 · p. 5, Table 4 · p. 5
  • The experiments cover ZINC regression, MolHIV HIV-replication prediction, and MolPCBA multi-label molecular-property prediction, evaluated with MAE, AUC, and AP, respectively.The datasets contain 12,000, 41,127, and 437,929 graphs, respectively.Source: Graph Classification and Regression · p. 5

Node Classification

The node-wise classification experiments evaluate GRPE on PATTERN and CLUSTER. The authors report state-of-the-art accuracy for PATTERN at a 500K-parameter scale and a significant weighted-accuracy improvement on CLUSTER.

Node Classification

  • PATTERN tests graph-pattern recognition with two node classes, while CLUSTER tests semi-supervised clustering with six classes.The datasets contain 14,000 and 12,000 graphs, respectively.Source: Node Classification · p. 5
  • GRPE models achieve state-of-the-art PATTERN accuracy at around 500K parameters.The study uses GRPE-Small (<500K parameters) and GRPE-Tiny (<100K parameters) for fair comparisons.Source: Node Classification · p. 6
  • On CLUSTER, the authors report a significant improvement in weighted accuracy.The compared models have fewer than 500K parameters for GRPE-Small and fewer than 100K for GRPE-Tiny.Source: Node Classification · p. 6

OGB Large Scale Challenge

The large-scale experiments predict molecular HOMO-LUMO energy gaps on PCQM4M and PCQM4Mv2 using only 2D molecular graphs. GRPE ranks second on PCQM4M validation and best on PCQM4Mv2 validation, while the large model's test-dev result is not reported.

OGB Large Scale Challenge

  • Both datasets target molecular HOMO-LUMO energy-gap prediction; PCQM4Mv2 contains 3D structures, but these experiments use only 2D graphs.The datasets contain about four million graphs in total.Source: OGB Large Scale Challenge · p. 6
  • On PCQM4M, GRPE achieves the second-best validation MAE, about 0.0001 behind the best model.The paper says it could not measure PCQM4M test MAE because the test dataset was deprecated.Source: OGB Large Scale Challenge · p. 6
  • On PCQM4Mv2, the large GRPE model achieves the best validation result, but its test-dev MAE is unreported.The evaluation server allowed only one submission per week.Source: OGB Large Scale Challenge · p. 6

Ablation Study on Components of GRPE

The ZINC ablation compares positional-encoding components and graph-encoded values. The reported errors decrease as topology and edge encodings are added, with a further improvement from graph-encoded values.

Ablation Study on Components of GRPE

Effects of Maximum Shortest Path Distance L

The ablation tests how the maximum shortest-path distance L affects GRPE-Standard trained from scratch. AUC improves as L increases from one to four, with no further improvement beyond four.

Effects of Maximum Shortest Path Distance L

Sharing Topology Encoding and Edge Encoding

Sharing topology and edge encodings improves ZINC MAE, but not significantly. Attention visualizations show a shift from neighboring nodes in lower layers toward the virtual node in deeper layers.

Sharing Topology Encoding and Edge Encoding

Attention Map of GRPE

  • Lower layers attend to neighboring nodes, while deeper layers give higher attention to the virtual node.The visualization averages 32 attention heads from GRPE-Standard trained for graph regression on PCQM4Mv2.Source: Attention Map of GRPE · p. 7
  • The deeper-layer attention to the virtual node indicates that layers focus on the entire graph rather than on each node.Source: Attention Map of GRPE · p. 7

Conclusion

The conclusion frames the work as improving graph structural representation by adding node-topology and node-edge relations. It reports validation across diverse tasks and datasets.

Conclusion

  • The paper studies positional encoding to represent graph structure better by adding node-topology and node-edge relations.Source: Conclusion · p. 7
  • The authors report quantitative and qualitative validation across tasks and datasets with diverse sizes and characteristics.Source: Conclusion · p. 7
  • Examples include HIV replication prediction from MolHIV molecule graphs and semi-supervised clustering on synthetic CLUSTER graphs.Source: Conclusion · p. 7
Loading 2201.12787v3…