Adaptive Distance Message Passing From the Multi-Relational Edge View

Zhongtian Sun, Alexandra I. Cristea, Pietro Lio, Jialin YuOpenReview 2023 · Submission to Tiny Papers @ ICLR · OpenReview

Standard Graph Neural Networks (GNNs) are often "short-sighted." They typically pass information over a fixed distance regardless of the type of connection between nodes. To address this, researchers have introduced ADMPE (Adaptive Distance Message Passing from Edge view), a method that allows different types of edges—such as single versus double bonds in a molecule—to learn their own optimal communication range. This approach leads to better performance on molecular property prediction tasks by respecting the underlying physics of the data.

The Problem: Uniform Message Passing

Most Message-Passing Graph Neural Networks (MP-GNNs) operate on a "uniform length" principle: if a model has $k$ layers, every node aggregates information from exactly $k$ hops away. This rigid architecture introduces two major flaws:

  1. Relational Blindness: In many real-world graphs, not all connections are equal. In a molecule, an aromatic bond might influence distant atoms differently than a single bond. Treating them as having the same "reach" ignores the logic of the data.
  2. The Depth Dilemma: To capture long-range dependencies, researchers usually stack more layers. However, stacking too many layers often leads to "over-squashing"—where information is compressed too tightly to be useful—or a loss of generalization.

The ADMPE Solution

The authors aim to break the rigid link between the number of layers and the distance messages can travel by making the propagation distance dependent on the edge type. They propose ADMPE, which modifies the standard GNN aggregation step.

Conceptual representation of multi-relational graphs where different edge types can dictate varying propagation distances.
  • Learnable Hops: Instead of a global $k$-hop limit, the model assigns a learnable parameter $k_r$ to each edge type $r$. These are initialized as integers between 1 and 10.
  • Modified Aggregation: During the update phase, the model doesn't just look at immediate neighbors. It considers a "hop count set" $M(r)$, which includes nodes within the specific maximum hop length allowed for that edge type.
  • Integration: ADMPE is designed to be a "plug-and-play" module. The authors successfully integrated it into two state-of-the-art architectures: GPS (a Graph Transformer) and Graph MLP-Mixer.

Essentially, the model learns that one edge type might be a long-range broadcaster, while another is only relevant to its immediate neighbors.

Datasets and Key Results

The researchers evaluated their method on two benchmark datasets focused on molecular learning: ZINC (12,000 molecular graphs for regression, featuring 4 distinct edge types) and MolHIV (41,127 graphs for binary classification).

The addition of ADMPE consistently improved the performance of the baseline models across both datasets.

Performance comparison of baseline models with and without the ADMPE module on ZINC and MolHIV datasets.
  • On ZINC (Lower MAE is better): GPS improved from 0.070 to 0.069, and Graph MLP-Mixer improved from 0.075 to 0.072.
  • On MolHIV (Higher ROCAUC is better): GPS improved from 0.781 to 0.785, and Graph MLP-Mixer improved from 0.807 to 0.811.

While the numerical gains on GPS were modest, the improvement for the Graph MLP-Mixer was more pronounced. This suggests that ADMPE is particularly effective at helping non-transformer models capture complex structural dependencies.

Key Insights

  • Decoupling Depth from Distance: The most significant takeaway is that we don't need 10 layers to see 10 hops away. By allowing specific edge types to "jump" further in a single layer, models can capture long-range context without the architectural baggage of ultra-deep networks.
  • Chemical Intuition as Architecture: The paper leverages chemical reality—specifically that double bonds have higher electron density and different stability/reactivity than single bonds—to justify why their "influence" shouldn't be treated uniformly.
  • Edge-Centric Intelligence: While much of GNN research focuses on better node representations or global attention, this work highlights that edges (relations) are often the most underutilized source of structural information.

Limitations and Future Work

The current version of ADMPE requires the dataset to have predefined edge types; it cannot currently "discover" different types of relations on its own in a simple homogeneous graph. Additionally, calculating multi-hop neighborhoods for specific edge types likely increases the computational cost per layer compared to standard 1-hop aggregation. Future work will likely investigate how to apply this logic to datasets where edge types are unknown or need to be inferred latently.

Summary updated

Abstract

Message-passing graph neural networks (MP-GNNs) excel in deep learning on graphs. Despite their success in various studies, they are limited by passing information to the fixed length $k$ distance neighbouring nodes, where $k$ is the number of layers. In reality, different types of edges (alternatively relations) may influence nodes at varying distance and should not be uniformly treated. This paper proposes an adaptive distance message-passing method that considers the unique roles of edge types, addressing this issue. Experiments on real-world datasets validate the effectiveness of our approach.
BibTeX
@misc{sun2023adaptive,
  author = {Zhongtian Sun and Alexandra I. Cristea and Pietro Lio and Jialin Yu},
  title = {{Adaptive Distance Message Passing From the Multi-Relational Edge View}},
  year = {2023},
  url = {https://openreview.net/forum?id=rAT51tL04I2},
  howpublished = {OpenReview},
  note = {Submitted to Tiny Papers @ ICLR},
}
Figure