PaperlayerView exact revision on arXiv

Source-linked AI summary

Long Range Graph Benchmark

Vijay Prakash Dwivedi, Ladislav Rampášek, Mikhail Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, Dominique Beaini

arXiv:2206.08164v4cs.LG

TL;DR

Message-passing GNNs can fail to capture long-range interactions, while existing benchmarks often emphasize local structure. The paper introduces LRGB, five datasets designed to require long-range reasoning, and evaluates local MP-GNNs against fully connected Graph Transformers. Across the proposed datasets, Transformers significantly outperform message passing, while the results also expose limitations in current Transformer designs.

  • Problem

    Existing graph benchmarks often rely primarily on local structure, providing limited evidence for evaluating models intended to capture long-range dependencies.

  • Method

    The paper constructs LRGB, a benchmark of five computer-vision and chemistry datasets characterized by graph size, task range, and global-structure dependence, then compares local MP-GNNs with fully connected Graph Transformers.

  • Results

    Transformers significantly outperform message passing on the proposed LRGB datasets.

  • Takeaways & Limitations

    LRGB provides a benchmark for developing and evaluating graph models with long-range dependencies.

  • Takeaways & Limitations

    Current Transformers still have limitations in using irregular sparse structure information and propagating long-range signals, while positional encoding alone contributes little or no gain.

Abstract

from arXiv · show

Graph Neural Networks (GNNs) that are based on the message passing (MP) paradigm generally exchange information between 1-hop neighbors to build node representations at each layer. In principle, such networks are not able to capture long-range interactions (LRI) that may be desired or necessary for learning a given task on graphs. Recently, there has been an increasing interest in development of Transformer-based methods for graphs that can consider full node connectivity beyond the original sparse structure, thus enabling the modeling of LRI. However, MP-GNNs that simply rely on 1-hop message passing often fare better in several existing graph benchmarks when combined with positional feature representations, among other innovations, hence limiting the perceived utility and ranking of Transformer-like architectures. Here, we present the Long Range Graph Benchmark (LRGB) with 5 graph learning datasets: PascalVOC-SP, COCO-SP, PCQM-Contact, Peptides-func and Peptides-struct that arguably require LRI reasoning to achieve strong performance in a given task. We benchmark both baseline GNNs and Graph Transformer networks to verify that the models which capture long-range dependencies perform significantly better on these tasks. Therefore, these datasets are suitable for benchmarking and exploration of MP-GNNs and Graph Transformer architectures that are intended to capture LRI.

1 Introduction

Message-passing GNNs can lose distant information through information oversquashing, while many existing benchmarks emphasize local structure. LRGB addresses this gap with five real-world datasets designed to depend on long-range signals and baseline evidence favoring fully connected models.

  • Limitations of local message passing: Message-passing GNNs update nodes from neighborhoods and require L layers to propagate information across L hops.As the receptive field grows, the amount of information to encode increases exponentially.
  • Limitations of local message passing: Information oversquashing causes distant signals to be lost during iterative message aggregation, limiting long-range dependency capture.The bottleneck arises because increasingly large neighborhoods must be compressed into one vector.
  • Benchmark gap: Many common graph benchmarks primarily rely on local structure, and local MP-GNNs often top their leaderboards despite Transformer models’ full connectivity.This limits the ability of those benchmarks to distinguish models that capture long-range interactions.
  • LRGB contribution: The paper introduces five real-world LRGB datasets from computer vision and chemistry whose tasks depend on long-range signal handling.The datasets are PascalVOC-SP, COCO-SP, PCQM-Contact, Peptides-func, and Peptides-struct.
  • Related benchmarks: Prior work has proposed synthetic, semi-real, and real-world benchmarks to evaluate architectures designed for long-range interactions.Examples include Graph MNIST, color connectivity, oversquashing probes, and Chains.

2 Characterizing Long-Range Interactions

The paper characterizes LRI suitability using graph size, task range, and the contribution of global structure. These factors jointly indicate when local message passing may face bottlenecks and when non-local models are appropriate.

  • Scope: The characterization discussion focuses on inductive datasets containing many graphs rather than a single large graph.This defines the scope of the proposed dataset-level analysis.
  • Graph Size: For LRI benchmarks, graph sizes should be sufficiently large to separate local MP-GNN performance from models that model long-range interactions.A node’s receptive field grows as O(exp(L)) when the number of layers reaches the task’s interaction radius.
  • Nature of Task: Task nature determines whether interactions are short-range or long-range, so large graphs alone do not establish that long-range propagation is needed.Tasks may require only local exchange or information from far outside the near-local neighborhood.
  • Contribution of global graph structure to task: Global graph structure can provide positional and distant-node signals that local MP-GNNs may miss but fully connected Transformer-like networks can propagate.This factor concerns both global positional encoding and critical signals from distant nodes.

3 Proposed LRGB Datasets

LRGB proposes five datasets spanning computer vision and chemistry whose tasks depend on long-range signal handling, global graph structure, or large graph sizes. The datasets include superpixel node classification, molecular contact prediction, and peptide-level functional and structural prediction.

  • PascalVOC-SP: PascalVOC-SP represents images as rag-boundary graphs of up to 500 SLIC superpixel nodes for semantic node classification.Each superpixel receives one of 21 semantic segmentation labels.
  • COCO-SP: COCO-SP applies the same superpixel and rag-boundary construction to MS COCO images, predicting one of 81 semantic classes per node.The dataset contains 123,286 image graphs averaging 476.88 nodes.
  • PCQM-Contact: PCQM-Contact frames long-range molecular reasoning as inductive link prediction for atom pairs more than 5 hops apart that contact within 3.5Å in 3D space.Molecules use covalent-bond edge types, while predicted contact links have no explicit edge type.
  • Peptide datasets: Peptides-func and Peptides-struct reuse 15,535 peptide graphs but define different graph-level tasks: multi-label function classification and regression of aggregated 3D properties.Peptides-struct predicts normalized inertia, length, sphericity, and plane-fit properties intended to reflect complex 3D interactions.

4 Experiments and Discussion

Experiments compare local MP-GNNs with fully connected Graph Transformers across LRGB, testing whether shallow local aggregation, positional encodings, and long-range-capable architectures affect performance. Transformers generally perform best, while scalability and positional-encoding limitations remain.

  • Baseline experiments: The experiments compare local MP-GNNs with fully connected Graph Transformers under fair baseline settings across the LRGB datasets.The evaluated MP-GNN baselines include GCN, GCNII, GINE, and GatedGCN.
  • Results and Analysis: Simple local MP-GNNs such as GCN and GINE perform poorly on all datasets except Peptides-func.This pattern is consistent with their greater susceptibility to information oversquashing than attention-based MP-GNNs.
  • Results and Analysis: Shallow MP-GNNs with L = 2 significantly underfit and generalize poorly compared with deeper models using L = 5 or 8 layers.The comparison indicates that increased receptive fields are important for the proposed tasks.
  • Results and Analysis: Fully connected Transformer and SAN models rank among the best baselines across Tables 3–5, with the clearest performance gap on Peptides-func and Peptides-struct.SAN outperforms vanilla Transformer+LapPE comparatively on PascalVOC-SP and PCQM-Contact, whereas Transformer and GatedGCN differ only slightly on COCO-SP.
  • Results and Analysis: PCQM-Contact tests long-range reasoning through distant-node pair prediction, while Peptides-* combine long-range tasks with substantial graph statistics.These task and graph characteristics help explain why fully connected Transformer baselines excel on the proposed datasets.
  • Challenges and future directions: The benchmark results suggest that positional encodings alone provide little or no performance gain, while current Transformers still face design and scalability limitations.The paper highlights the need for methods that use irregular sparse structure, propagate long-range interactions, and avoid inefficient O(N^2) computation.

5 Conclusion

The paper introduces LRGB, a five-dataset benchmark for node-, edge-, and graph-level prediction tasks involving long-range dependencies. Baseline experiments show that Transformers significantly outperform message-passing models, positioning LRGB for evaluating and developing long-range graph models.

  • Conclusion: LRGB consists of five datasets covering node-, edge-, and graph-level prediction tasks.The datasets are intended to evaluate models enabled with long-range dependencies.
  • Conclusion: The datasets’ graph sizes and task designs make them suitable for evaluating and developing models with long-range dependencies.The conclusion links the benchmark’s characterization factors to its intended use.
  • Conclusion: Extensive baselines show that Transformers significantly outperform message-passing models on the proposed datasets.The comparison includes local and non-local GNN classes.
  • Conclusion: LRGB is intended to support prototyping new ideas and ranking models by their ability to capture long-range interactions.This stated use follows the benchmark’s dedicated focus on long-range graph learning.

Checklist

The checklist reports that the paper addresses contributions, limitations, reproducibility, asset licensing, and ethics-related documentation. It also states that the benchmark uses molecular and imaging datasets without personal information or offensive content.

  • Checklist: The authors report that the paper describes its contributions and scope and discusses its limitations.The checklist points readers to Section 2 for the limitations discussion.
  • Checklist: The authors report that source code, dataset-download instructions, training details, error bars, and compute information are available.Experiments were run four times with different random seeds, with means and standard deviations reported.
  • Checklist: The checklist states that existing assets are cited and their licenses are discussed.The source code and datasets are described as available in the supplemental material.
  • Checklist: The benchmark is reported to use molecular and imaging datasets without personal information or offensive content.The checklist states that the work has no immediate societal impacts.

A.1 Optional variants of PascalVOC-SP and COCO-SP datasets

Optional PascalVOC-SP and COCO-SP variants change the SLIC compactness parameter and graph construction format. The coo and coo-feat variants use weighted 8-nearest-neighbor graphs, and their statistics and baseline results are reported separately.

  • Dataset construction: The default PascalVOC-SP and COCO-SP graphs use rag-boundary construction with SLIC compactness 30.Optional variants use SLIC compactness 10 or alternative coo and coo-feat graph formats.
  • Dataset construction: Coo and coo-feat construct 8-nearest-neighbor graphs by selecting edges with the highest adjacency weights.Coo weights use superpixel coordinates, whereas coo-feat weights use coordinates and feature intensities.
  • Dataset construction: The optional graph variants assign 12-dimensional RGB features to superpixel nodes and one-dimensional weights to edges.The edge weights are computed using the corresponding coordinate-only or coordinate-and-feature equations.
  • Statistics and Baseline Results: Statistics and baseline experiments are reported for six tried PascalVOC-SP and COCO-SP dataset versions.The default SLIC: 30 and rag-boundary configuration is distinguished from the optional versions.
  • Statistics and Baseline Results: The PascalVOC-SP and COCO-SP optional variants are evaluated on node classification using macro F1.The baseline comparison uses approximately 500k parameters, with eight-layer MP-GNNs and four-layer Transformer models.

A.3 Extended Results for Peptides-struct

Peptides-struct evaluation reports extended R2 metrics alongside the MAE results. Label correlations are generally limited, with some expected structural relationships, supporting multi-label regression.

  • Extended metrics: Table A.3 extends Peptides-struct evaluation by reporting training and testing performance using coefficient of determination R2 alongside MAE.The table supplements, rather than replaces, the MAE reported in Table 4.
  • Label correlations: Peptides-struct exhibits some expected correlations because inertia relates to length and spherocity, but overall label correlation remains limited.The limited correlation motivates treating the task as multi-label regression.
  • Task formulation: Peptides-func is evaluated as multi-label classification, whereas Peptides-struct is evaluated as multi-label regression.

C Experimental Details

Table C.1 specifies baseline hyperparameters for seven models across the five LRGB benchmarks. It records hidden representation size, layer count, and applicable positional or structural embeddings.

  • Baseline coverage: Table C.1 covers seven evaluated baseline models on the five new LRGB benchmarks.
  • Model dimensions: The table reports hidden node representation size d and number of layers L for each baseline.
  • Encodings: Where applicable, Table C.1 identifies positional or structural embeddings, including LapPE-k and RWSE-m variants.LapPE-k denotes Laplacian positional encoding with the first k non-trivial eigenvectors; RWSE-m denotes random-walk structural encoding.

C.1 Details on Baseline Experiments Setup

The experiments compare local MP-GNNs and fully connected Graph Transformers under a controlled parameter budget and repeated training runs. Training uses Adam with model- and dataset-dependent learning rates, while runtime is measured on A100 hardware.

  • Compared models: The baseline suite includes GCN, GCNII, GINE, GatedGCN, fully connected Transformer with LapPE, and SAN with LapPE or RWSE.The models span local message-passing and fully connected Transformer classes.
  • Controlled setup: Baselines are configured at approximately 500k learnable parameters using 4–8 layers with adjusted hidden dimensions, and each experiment is run four times with different random seeds.
  • Optimization: Optimization uses Adam, learning rates from 0.0003 to 0.001, and a 0.5 decay factor after validation-loss plateaus, with training capped at 60 hours except for slow SAN convergence on COCO-SP.
  • Implementation and resources: Experiments use GraphGPS on PyG and GraphGym across shared CPU/GPU infrastructure, with one GPU, four CPUs, and up to 32GB system RAM per experiment.
  • Runtime reporting: Table C.2 reports average epoch wall-clock times for each model–dataset combination and lists precomputation times for LapPE and RWSE statistics.

D Additional Experiments with L = 2 MP-GNNs

Additional experiments test 2-layer MP-GNNs within the same 500k-parameter budget to assess narrow receptive fields and the role of positional or structural encodings. These shallow models generally perform worse than deeper versions, while encoded GatedGCN can improve substantially on several peptide and contact tasks.

  • Experimental design: The shallow baselines use L=2 and enlarge hidden representations to fill the 500k parameter budget.They are designed to test whether limited receptive fields hinder performance on LRGB.
  • Depth comparison: 2-layer MP-GNNs generally show markedly lower performance than deeper versions, although their relative performance ordering remains largely unchanged.
  • Encoding effects: GatedGCN with LapPE or RWSE substantially outperforms standard GatedGCN and other tested MP-GNNs particularly on PCQM-Contact, Peptides-func, and Peptides-struct.This stronger encoding effect appears for shallow models but not for deeper GatedGCN configurations.
  • Reported tasks: Tables D.2–D.4 report shallow MP-GNN baselines for PascalVOC-SP, COCO-SP, Peptides-func, Peptides-struct, and PCQM-Contact.The reported tasks cover node classification, graph classification, graph regression, and link prediction.

E Inspection of Transformer attention

Inspection of Transformer+LapPE attention shows dataset- and layer-dependent weighting beyond local neighborhoods across the LRGB datasets, unlike the predominantly local attention observed on MNIST. The patterns vary from early long-range emphasis to distance-decaying attention across layers.

  • Overall patterns: Transformer attention generally extends beyond local neighborhoods across the five LRGB datasets.The inspection averages attention by shortest-path distance over trained models and test graphs.
  • PascalVOC-SP and COCO-SP: PascalVOC-SP and COCO-SP emphasize mid- and long-distance nodes in the first layer, shift toward close neighbors in middle layers, and become most evenly distributed in the last layer.The final layer retains some bias toward close-by nodes.
  • PCQM-Contact: PCQM-Contact has broadly similar layer-wise distributions, but its first layer is more uniform and lightly favors the first half of the distance range.The comparison concerns attention aggregated by node distance.
  • Peptides-func and Peptides-struct: Peptides-func and Peptides-struct show more consistent attention across layers, with mostly linear weight decay as shortest-path distance increases.Their distributions differ from the stronger layer-wise shifts reported for PascalVOC-SP and COCO-SP.
  • MNIST comparison: MNIST attention is mainly concentrated on neighbors up to 4 hops away after the first layer, contrasting with the broader LRGB attention patterns.The Transformer+LapPE model achieved 97.89% test accuracy on MNIST under the stated parameter budget and split.
Loading 2206.08164v4…