Graph Alignment for Benchmarking Graph Neural Networks and Learning Positional Encodings
Adrien Lagesse, Marc Lelarge · 2025
Read Graph Alignment for Benchmarking Graph Neural Networks and Learning Positional Encodings by Adrien Lagesse, Marc Lelarge (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-13087.txt.
Introduction
Adrien Lagesse and Marc Lelarge grade graph nets by how well they align two graphs. To align is to match nodes of two graphs with no labels so shared edges peak. It is a broad form of the graph match task. Cast as self-taught learning, the task forms a graded exam. The pair build data sets, both fake and real, in sets of rising test load.
Rank lists of net designs hold up only at one sweet spot of load. That point has real use for those who grade nets. On this pure shape task, nets that sense edge way beat nets that do not. Pre-work on the fake task pays off in new tasks. Learned node codes serve as place codes for graph transformers. They can rebuild a graph's full shape with 98% right calls. An open code pack lets others make the test and try new designs.
Catalog record
| CREATOR | Adrien Lagesse, Marc Lelarge |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 83 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-13087
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Graph Alignment for Benchmarking Graph Neural Networks and Learning Positional Encodings Adrien Lagesse, Marc Lelarge Abstract 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 % 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 . 1 Introduction Graphs are versatile and complex mathematical structures, making them adaptable for representing various data types across many scientific fields. In recent years, multiple architectures of Graph Neural Networks (GNNs) were developed ( Kipf and Welling, 2017 ; Veličković et al., 2018 ; Togninalli et al., 2019 ; Brody et al., 2022 ) , enabling the application of machine learning and deep learning techniques to graph-based data. These models are used to tackle challenges in areas such as chemistry ( Gilmer et al., 2017 ; Duvenaud et al., 2015 ; Reiser et al., 2022 ) , material science ( Jain et al., 2013 ; Reiser et al., 2022 ; Chanussot et al., 2021 ; Tran et al., 2023 ) , biology ( Stokes et al., 2020 ; Zhang et al., 2021 ) , and social networks ( Fan et al., 2019 ; Ying et al., 2018 ) . In parallel, several graph datasets were compiled to create benchmarks that encompass a diverse set of tasks ( Hu et al., 2020 ; Morris et al., 2020 ; Dwivedi et al., 2022 ) , facilitating the comparison and evaluation of different architectures. Moreover, task-specific datasets are often employed to compare architectures designed for particular applications, such as those by Chanussot et al. (2021) ; Tran et al. (2023) ; Lee et al. (2023) for material science, Wu et al. (2017) for chemistry, and Li et al. (2024) for the SAT problem. However, unlike text, images, videos, audio, and time-series data, a graph is not an Euclidean data type ( Bronstein et al., 2021 ) . Each graph in a dataset has a unique topology that carries critical information that needs to be interpreted by the GNN. This creates a dual challenge in real-world datasets, where both the structural information of the graph and its features (node features, edge features, graph features, etc… ) must be accounted for ( Liu et al., 2022 ) . While leveraging all available information is valuable in practice, it is not essential for a benchmark. In fact, it often complicates the process, as assessing an architecture’s structural and feature understanding simultaneously can be challenging. We risk diluting structural information, leading to concerning results, such as more theoretically powerful architectures underperforming compared to simpler models like the Graph Convolutional Network ( Kipf and Welling, 2017 ) . Currently, structural understanding in GNNs is typically assessed either theoretically through the Weisfeiler-Lehman test ( Xu et al., 2019 ; Morris et al., 2019 ; Azizian and Lelarge, 2021 ) or experimentally using combinatorial optimization benchmarks that lack key features we describe in this paper. All graph topologies Topologies from social networks Topologies from molecular chemistry CoraFull OGBN-Arxiv Erdös-Rényi AQSOL PCQM4Mv2 Figure 1 : Visualization of graph topologies: Graph topologies differ widely across application domains, and the performance of GNN architectures varies accordingly based on these topological differences. Furthermore, different tasks may share the same graph topologies (see Appendix O ). We believe there is a gap in the existing benchmarks available to the GNN community to have a more fine-grained metric to compare different models in the same Weisfeiler-Lehman class and to quantify their structural expressivity within that class. Additionally, we argue that evaluating GNN architectures based on graph topology provides broader, more generalizable information compared to task-specific performance. Indeed, this approach is particularly valuable as many different tasks share similar underlying graph topologies (see Figure 1 ). Contributions 1. We introduce a novel benchmarking task centered on the Graph Alignment Problem to evaluate the structural analysis capabilities of GNNs and we show that this task is a generalization of the Weisfeller-Lehman test. We provide a comprehensive methodology for generating datasets using both synthetic and real-world graph data, which also enables the creation of datasets with controllable levels of difficulty, allowing for more nuanced evaluations - Section 4 . 2. We further demonstrate the applicability of our framework by benchmarking widely used Message-Passing Neural Network (MPNN) architectures on datasets with varying graph topologies - Section 5 . 3. Our empirical analysis highlights that the graph alignment task compress the graph structure and can be effectively used for self-supervised GNN pre-training. The learned node embeddings can serve as positional encodings and can be leveraged by transformer-based models for downstream graph regression tasks and high accuracy graph reconstruction - Section 6 . 4. Additionally, we provide an open-source Python package that facilitates the creation of new datasets following our methodology, as well as tools for benchmarking alternative GNN architectures. 2 Related Work Existing methods for benchmarking GNNs. Understanding and comparing deep learning models is crucial to advance the field of machine learning, ImageNet ( Deng et al., 2009 ) was instrumental in shaping the current computer vision landscape, and advances in other machine learning fields are highly correlated with high-quality benchmarks. To benchmark graph neural networks, general-purpose and widely used datasets were compiled in TUDataset ( Morris et al., 2019 ) , Open Graph Benchmark ( Hu et al., 2020 ) and Benchmarking Graph Neural Networks ( Dwivedi et al., 2022 ) . In addition to those datasets, specialized benchmarks also exist in structural chemistry ( Wu et al., 2017 ) , material-science ( Jain et al., 2013 ; Chanussot et al., 2021 ; Tran et al., 2023 ; Lee et al., 2023 ) as well as benchmarks based on combinatorial optimization tasks such as neural algorithmic reasoning ( Veličković et al., 2022 ) and SAT ( Li et al., 2024 ) . Among these datasets, only neural algorithmic reasoning and combinatorial optimization tasks specifically benchmark the structural understanding of a graph neural network. However, they have a major limitation: their inability to adapt to a wide variety of graph topologies. The PATTERN, and CLUSTER datasets from Dwivedi et al. (2022) are inherently based on the Stochastic Block Model (SBM), which can only represent a small portion of graph topologies (molecular graphs for