Measuring Structure in Graph Benchmark Datasets Using Graph Invariants
Abstract
Progress in graph learning is hindered by benchmark practices that conflate the contributions of node features and graph structure, making it hard to tell whether a model actually learns from the graph, or whether it even needs to. We propose measuring this using graph invariants, i.e., permutation-invariant, task-agnostic structural descriptors. Our analysis on datasets substantiates three tacit assumptions in graph learning, namely that (i) a curated subset of invariants is more expressive than standard GNNs, (ii) benchmark datasets exhibit structural heterogeneity even when originating from the same domain, and (iii) simple models are often competitive with, and sometimes exceed, approaches based on transformers or message passing. We thus posit that graph invariants should become a standard tool for measuring graph learning task complexity and the relevance of graph structure.
Related
- A Critical Audit of Spatiotemporal Forecasting Benchmark Datasets and Models
- Below what training size do deep tabular generators stop beating trivial baselines? A preregistered benchmark on a size ladder of clinical and standard datasets
- K-theoretic invariants of the Toeplitz operator system and its dual, and of all graph operator systems
- ℓ2-Betti numbers and Σ-invariants of graph products of cyclic groups and their automorphisms
- Shannon Capacity and Related Graph Invariants for Lexicographic Products
BibTeX
@misc{moos2026measuring,
title = {{Measuring Structure in Graph Benchmark Datasets Using Graph Invariants}},
author = {Richard von Moos and Mathieu Alain and Bastian Rieck},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2605.06462},
eprint = {2605.06462},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.06462},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Measuring Structure in Graph Benchmark Datasets Using Graph Invariants
AU - Richard von Moos
AU - Mathieu Alain
AU - Bastian Rieck
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2605.06462
UR - https://arxiv.org/abs/2605.06462
AB - Progress in graph learning is hindered by benchmark practices that conflate the contributions of node features and graph structure, making it hard to tell whether a model actually learns from the graph, or whether it even needs to. We propose measuring this using graph invariants, i.e., permutation-invariant, task-agnostic structural descriptors. Our analysis on datasets substantiates three tacit assumptions in graph learning, namely that (i) a curated subset of invariants is more expressive than standard GNNs, (ii) benchmark datasets exhibit structural heterogeneity even when originating from the same domain, and (iii) simple models are often competitive with, and sometimes exceed, approaches based on transformers or message passing. We thus posit that graph invariants should become a standard tool for measuring graph learning task complexity and the relevance of graph structure.
ER -