Graph Alignment for Benchmarking Graph Neural Networks and Learning Positional Encodings

We propose a novel benchmarking methodology for graph neural networks (GNNs) based on the graph alignment problem, a combinatorial optimization task that generalizes graph isomorphism by aligning two unlabeled graphs to maximize overlapping edges. We frame this problem as a self-supervised learning task and present several methods to generate graph alignment datasets using synthetic random graphs and real-world graph datasets from multiple domains. For a given graph dataset, we generate a family of graph alignment datasets with increasing difficulty, allowing us to rank the performance of various architectures. Our experiments prove that there is an optimal task difficulty for having a statistically relevant ranking of different models and that, even on a structure-only task, anisotropic models perform better compared to isotropic ones. To further prove that our synthetic task capture meaningful information, we show its effectiveness for self-supervised GNN pre-training: the learned node embeddings can be leveraged as positional encodings by transformers for graph regression or can be used to reconstruct the full structure of the graph with $98\%$ accuracy. To support reproducibility and further research, we provide an open-source Python package to generate graph alignment datasets and benchmark new GNN architectures. The source code is available at [graph-alignment-benchmark](https://github.com/adrien-lagesse/graph-alignment-benchmark).

Graphs — networks of connected points — describe everything from molecules to social networks to citation databases. Specialized AI models called Graph Neural Networks (GNNs) learn from such data, but comparing them is surprisingly hard: real-world tasks mix understanding the graph's shape with processing other information like atom types, so it's unclear whether one model beats another because of better structural insight or for unrelated reasons. The few benchmarks that test pure shape understanding only cover narrow slices of the many graph types found in practice. We turn an old combinatorial puzzle into a flexible benchmark: given two slightly corrupted copies of the same graph, can a GNN figure out which point in one corresponds to which point in the other? Starting from any real graph collection, we generate matching tasks with tunable difficulty and show there is a "sweet spot" where competing architectures separate most clearly, making the ranking statistically reliable. The representations GNNs learn while solving this puzzle prove broadly useful beyond the puzzle itself: they help transformers predict molecular properties more accurately, and compress graph structure so faithfully that the original connections can be reconstructed with 98% accuracy. We release an open-source package so the community can benchmark new architectures on their own graphs.