🤖 machine learning

Graph Alignment for Benchmarking Graph Neural Networks and Learning Positional Encodings

This paper introduces a novel self-supervised benchmarking framework for Graph Neural Networks based on the graph alignment problem, demonstrating that task difficulty can effectively rank model architectures and that the resulting learned positional encodings significantly improve downstream graph tasks.

Original authors: Adrien Lagesse, Marc Lelarge

Published 2026-06-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Adrien Lagesse, Marc Lelarge

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Idea: A New "Gym" for AI

Imagine you want to test how strong a new weightlifter is. You wouldn't just ask them to lift a random box; you'd put them on a specific, adjustable weightlifting machine where you can control exactly how heavy the weights are.

This paper proposes a new "weightlifting machine" for Graph Neural Networks (GNNs). GNNs are a type of AI designed to understand data that looks like a map of connections (like social networks, chemical molecules, or road maps).

The authors argue that current ways of testing these AIs are flawed because they mix up the "shape" of the map with the "labels" on the map (like colors or names). They want to test the AI's ability to understand the shape alone. To do this, they created a benchmark based on a puzzle called Graph Alignment.

The Core Puzzle: The "Ghost Map" Game

Think of the Graph Alignment Problem like this:

Imagine you have a detailed map of a city (Graph A).
Now, imagine a "ghost" version of that same city (Graph B). It has the exact same streets and intersections, but the street names are scrambled, and a few streets have been randomly removed or new ones added.
The Challenge: Your AI must look at the Ghost Map and figure out which intersection on the Ghost Map corresponds to which intersection on the Original Map.

If the AI can successfully match up the two maps, it proves it truly understands the structure of the city, not just the names on the signs.

How They Built the Test

The researchers didn't just use one map. They built a whole gym with different types of terrain:

Synthetic Maps: Computer-generated random cities.
Real-World Maps: Actual data from social networks (like Twitter), chemical molecules, and scientific papers.

They also added a "difficulty slider" (called noise).

Low Noise: The Ghost Map is almost identical to the Original. The puzzle is easy.
High Noise: The Ghost Map is very messy, with many missing or fake streets. The puzzle is very hard.

The Discovery: They found that if the puzzle is too easy or too hard, all the AIs look the same (either they all get it right, or they all fail). But at a "Goldilocks" level of difficulty, the differences between the smartest and dumbest AIs become very clear. This allows researchers to rank the models accurately.

The Results: Who Wins the Gym?

When they ran the test, they found some interesting things about how different AI architectures work:

Isotropic vs. Anisotropic: Think of "Isotropic" models as people who treat every direction the same (like a person walking in a circle). "Anisotropic" models are like people who pay attention to the specific direction they are facing.
The Winner: The "direction-aware" (Anisotropic) models consistently beat the "direction-blind" (Isotropic) ones. This suggests that paying attention to the specific direction of connections helps the AI understand the map better.

The Bonus: Learning to "Read" the Map

The most exciting part of the paper is what happens after the AI solves the puzzle.

When the AI learns to align these maps, it creates a special "ID card" (called an embedding) for every single point on the map. These ID cards contain a deep understanding of where that point sits in the overall structure.

The authors showed that these ID cards are so good that they can be used as Positional Encodings for a different type of AI called a Transformer (the same kind of AI that powers chatbots and image generators).

The Analogy: Usually, Transformers are like people who can read a book but don't know where the words are located on the page. These "ID cards" act like a GPS for the words, telling the Transformer exactly where each piece of data sits in the structure.
The Result: When they used these AI-generated ID cards, the Transformer became incredibly good at predicting chemical properties (like how well a drug dissolves) and could even redraw the entire map from scratch with 98% accuracy.

Summary

In short, this paper says:

We need a better way to test if Graph AIs actually understand shapes, not just labels.
We created a "Ghost Map" puzzle (Graph Alignment) that lets us tune the difficulty to see which AI is truly the smartest.
We found that AIs that pay attention to direction work best.
The "lessons" these AIs learn from the puzzle are so powerful that they can be used to teach other AIs how to understand complex structures, leading to better predictions in science and chemistry.

The authors have also released a free toolkit so anyone can build these "Ghost Map" puzzles and test their own AI models.

Technical Summary: Graph Alignment for Benchmarking Graph Neural Networks and Learning Positional Encodings

Problem Statement

Graph Neural Networks (GNNs) are widely used across domains such as chemistry, material science, and social networks. However, evaluating their structural understanding remains challenging. Existing benchmarks often conflate structural capabilities with feature learning or rely on combinatorial optimization tasks (e.g., SAT, TSP) that are tied to specific problem topologies or synthetic models like the Stochastic Block Model (SBM), limiting their generalizability. Furthermore, current methods struggle to provide a fine-grained metric to compare models within the same expressivity class (e.g., the 1-Weisfeiler-Lehman class) or to quantify structural expressivity across diverse graph topologies found in real-world applications.

The authors propose addressing this gap by introducing a benchmarking methodology based on the Graph Alignment Problem (also known as Graph Matching). This task involves aligning two unlabeled graphs to maximize the number of overlapping edges, a combinatorial optimization problem that generalizes graph isomorphism.

Methodology

1. The Graph Alignment Task

The core task is defined as finding a permutation $\pi^*$ between two graphs $G$ and $\tilde{G}$ with $N$ vertices that maximizes the overlap of their adjacency matrices:
$\pi^* \in \arg \max_{\pi \in S_N} \sum_{i,j} A_{i,j} \tilde{A}_{\pi(i),\pi(j)}$
This is framed as a self-supervised learning task. The authors employ a Siamese architecture where a GNN processes both graphs to produce node embeddings $X$ and $\tilde{X}$ . A similarity matrix $\Sigma = X\tilde{X}^T$ is computed.

Training: The model minimizes binary cross-entropy loss between the predicted similarity matrix and the ground-truth alignment (planted permutation).
Evaluation: The Hungarian algorithm solves the Linear Assignment Problem on $\Sigma$ to extract the predicted permutation. Performance is measured by the percentage of correctly mapped nodes.

2. Dataset Construction

To overcome the limitations of previous synthetic datasets (e.g., Erdős-Rényi graphs only), the authors propose a method to generate Graph Alignment datasets from any existing graph dataset (base datasets).

Correlated Graph Generation: For a base graph $G$ , a correlated graph $\tilde{G}$ is generated by randomly adding and removing edges based on a noise level $\eta$ .
Planted Solution: Since the optimal alignment is known (the identity or a known permutation before noise), the ground truth is available without solving the NP-hard problem.
Scalability: For large graphs (e.g., OGBN-Arxiv), a Breadth-First Search (BFS) sampling algorithm is used to extract smaller subgraphs that preserve local topology, making them compatible with Message-Passing Neural Networks (MPNNs).
Difficulty Control: By varying the noise level $\eta$ (from 4% to 30%), the authors create a family of datasets with controllable difficulty, allowing for nuanced evaluation.

3. Positional Encoding Learning (GAPE)

The authors leverage the learned node embeddings from the Graph Alignment task as Graph Alignment Positional Encodings (GAPE). These embeddings are intended to serve as structural inputs for Transformer architectures, which lack inherent access to graph structure.

Key Contributions

Novel Benchmarking Task: Introduction of the Graph Alignment Problem as a benchmark for GNNs, which generalizes the Weisfeiler-Lehman test and allows for evaluation across diverse topologies (molecular, social, random) without modifying the underlying graph structures.
Dataset Generation Framework: A comprehensive methodology to generate Graph Alignment datasets from both synthetic and real-world base datasets, enabling the creation of datasets with varying difficulty levels.
Empirical Ranking of Architectures: A systematic benchmark of widely used MPNNs (GCN, GIN, GatedGCN, GAT, GATv2) demonstrating that anisotropic models consistently outperform isotropic models (like GCN and GIN) in structural analysis, even on homophilic graphs.
Optimal Difficulty Level: Discovery that there exists an "optimal noise level" where the performance gap between models is maximized, providing statistically significant rankings that are robust to hyperparameter choices and random seeds.
Positional Encodings (GAPE): Demonstration that embeddings learned via Graph Alignment serve as effective positional encodings for Transformers, outperforming or matching spectral and random-walk-based encodings on molecular regression tasks.
Graph Reconstruction: Evidence that GAPE embeddings compress the graph structure effectively, allowing for the reconstruction of the full adjacency matrix with ~98% accuracy using a simple decoder.
Open-Source Tooling: Provision of a Python package to generate these datasets and benchmark new architectures.

Results

Model Performance: In experiments across five base datasets (Erdős-Rényi, AQSOL, PCQM4Mv2, CoraFull, OGBN-Arxiv), anisotropic architectures (GatedGCN, GAT, GATv2) achieved higher alignment accuracy than isotropic ones (GCN, GIN).
Noise Sensitivity: The performance gap between models was negligible at very low or very high noise levels. The gap peaked at an optimal noise level (e.g., $\eta \approx 15\%$ for molecular graphs), where statistical significance was highest.
Downstream Tasks: When used as positional encodings for Transformers in molecular regression (AQSOL, PCQM4Mv2, ZINC), GAPE achieved state-of-the-art or competitive Mean Absolute Error (MAE) compared to Laplacian, Random Walk, and other spectral encodings. Specifically, GAPE+RWPE achieved the best results on AQSOL and PCQM4Mv2.
Reconstruction: An autoencoder with a frozen GAPE encoder achieved 98%+ accuracy in reconstructing the adjacency matrix, confirming that the embeddings capture the complete graph topology.
Correlation: A strong negative correlation ( $r < -0.90$ ) was observed between Graph Alignment accuracy and downstream molecular property prediction error, suggesting that structural alignment capability is a primary bottleneck for these tasks.

Significance and Claims

The paper claims to provide a robust, fine-grained framework for evaluating the structural expressivity of GNNs, independent of specific node or edge features. By isolating structural understanding, the benchmark reveals that anisotropic models offer a richer representation of graph topology than previously established isotropic models.

Furthermore, the authors argue that the Graph Alignment task is not merely a "puzzle" but a fundamental pre-training objective. The fact that the learned embeddings can be used for high-accuracy graph reconstruction and significantly improve downstream Transformer performance suggests that the task forces the model to learn a high-fidelity compression of the graph structure. This validates the benchmark's utility for both comparing architectures and generating useful representations for real-world applications in chemistry and materials science.

The work concludes that the Graph Alignment benchmark offers a flexible, domain-agnostic approach to GNN evaluation, capable of adapting to the specific topological characteristics of any target application domain.