Range-aware Positional Encoding via High-order Pretraining: Theory and Practice

Viet Anh Nguyen, Nhat Khang Ngo, Truong Son Hy

Abstract

Graph Neural Networks (GNNs) often struggle with structural expressiveness and long-range dependencies. This paper introduces HOPE-WavePE, a domain-agnostic pre-training strategy that leverages multi-resolution spectral graph wavelets and high-order connectivity reconstruction. By focusing on topology rather than domain-specific features, HOPE-WavePE generates range-aware positional encodings that significantly enhance performance across diverse graph learning tasks, from molecular chemistry to social network analysis.

Introduction

The effectiveness of Graph Neural Networks (GNNs) in fields like drug discovery and materials science is often hampered by three fundamental bottlenecks: expressiveness (distinguishing structures), over-smoothing (feature convergence), and over-squashing (information loss in long-range interactions). While Graph Transformers and various Positional Encodings (PE) have been proposed to mitigate these issues, they frequently suffer from task-specificity and a lack of "range-awareness"—the ability to effectively capture both local and global graph structures across varying scales.

HOPE-WavePE (High-Order Permutation-Equivariant Wavelet Positional Encoding) addresses these challenges by pre-training a structural encoder on purely topological data. This approach ensures the resulting encodings are universal and capable of transferring across disparate domains.

Methodology

The HOPE-WavePE framework centers on three key components designed to capture the "skeleton" of a graph:

Spectral Graph Wavelets

Instead of relying on standard adjacency matrices, the model utilizes wavelet signals at multiple resolutions. These signals function as a "zoom lens," where low scales capture localized structural details and high scales provide a smoother, global view of the graph topology.

Multi-resolution wavelet signals capturing structural information at different scales, from localized (left) to global (right).

High-Order Autoencoder

A permutation-equivariant autoencoder is pre-trained to reconstruct the graph's connectivity. Unlike traditional methods, it is tasked with predicting high-degree adjacency matrices (j-hop neighbors), effectively "pre-computing" long-range interactions that standard message-passing GNNs often fail to reach.

Range-Aware Loss Masking

To ensure generalizability across graphs of different sizes, a masking technique is employed during pre-training. This prevents the model from becoming "lazy" on small graphs and forces it to learn long-range connectivity independently of the specific graph diameter.

Experimental Results

The researchers conducted extensive evaluations across a massive variety of benchmarks, demonstrating the robustness of the approach:

  • Molecular Benchmarks: On the MoleculeNet benchmark, the "MPNN + HOPE-WavePE" model consistently achieved Top 3 results across all five datasets, often outperforming much larger, domain-specific pretrained models like GROVER.
  • Long-Range Dependencies: In the Long-Range Graph Benchmark (LRGB), the method achieved a state-of-the-art Mean Absolute Error (MAE) of 0.2433 on Peptides-struct, outperforming standard GatedGCNs and Graph Transformers.
  • Cross-Domain Transfer: A notable finding was the model's incredible transferability. A HOPE-WavePE encoder pre-trained on molecular data could reconstruct the structure of image-based graphs (MNIST) with over 97% accuracy. It also significantly improved performance on social network datasets like IMDB-B/M.

Conclusion

HOPE-WavePE demonstrates that focusing on universal topological features through high-order wavelet reconstruction provides a powerful, domain-agnostic tool for graph representation learning. By providing range-aware structural context, it overcomes traditional GNN limitations and sets a new standard for positional encoding transferability across diverse scientific and social domains.

Summary updated

Abstract

Unsupervised pre-training on vast amounts of graph data is critical in real-world applications wherein labeled data is limited, such as molecule properties prediction or materials science. Existing approaches pre-train models for specific graph domains, neglecting the inherent connections within networks. This limits their ability to transfer knowledge to various supervised tasks. In this work, we propose a novel pre-training strategy on graphs that focuses on modeling their multi-resolution structural information, allowing us to capture global information of the whole graph while preserving local structures around its nodes. We extend the work of Wave}let Positional Encoding (WavePE) from (Ngo et al., 2023) by pretraining a High-Order Permutation-Equivariant Autoencoder (HOPE-WavePE) to reconstruct node connectivities from their multi-resolution wavelet signals. Unlike existing positional encodings, our method is designed to become sensitivity to the input graph size in downstream tasks, which efficiently capture global structure on graphs. Since our approach relies solely on the graph structure, it is also domain-agnostic and adaptable to datasets from various domains, therefore paving the wave for developing general graph structure encoders and graph foundation models. We theoretically demonstrate that there exists a parametrization of such architecture that it can predict the output adjacency up to arbitrarily low error. We also evaluate HOPE-WavePE on graph-level prediction tasks of different areas and show its superiority compared to other methods.
BibTeX
@inproceedings{nguyen2024range,
  author = {Viet Anh Nguyen and Nhat Khang Ngo and Truong Son Hy},
  title = {{Range-aware Positional Encoding via High-order Pretraining: Theory and Practice}},
  booktitle = {NeurReps @ NeurIPS},
  year = {2024},
  url = {https://openreview.net/forum?id=tN0n5BuLEI},
}
Figure