Invariant-Based Diagnostics for Graph Benchmarks
Richard von Moos, Mathieu Alain, Bastian Rieck · 2026
Read Invariant-Based Diagnostics for Graph Benchmarks by Richard von Moos, Mathieu Alain, Bastian Rieck (2026) 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-2605-06462.txt.
Introduction
Richard von Moos, Mathieu Alain, and Bastian Rieck argue that graph learning benchmarks should measure graph structure directly. Progress is hard to judge when node features and graph structure are mixed together, since a model might win without using the graph at all. Their tool is graph invariants: descriptors that ignore node ordering and do not depend on the task.
Their analysis supports three claims. A curated set of invariants can be more expressive than standard graph networks, datasets from one domain still differ structurally, and simple models often match fancier ones. They propose invariants as a standard way to gauge task complexity and whether structure matters.
Catalog record
| CREATOR | Richard von Moos, Mathieu Alain, Bastian Rieck |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.06462
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Invariant-Based Diagnostics for Graph Benchmarks Richard von Moos, Mathieu Alain, Bastian Rieck Abstract Progress on graph foundation models 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 connectivity, or whether it even needs to. We propose addressing this using graph invariants , i.e., permutation-invariant, task-agnostic structural descriptors that serve as a diagnostic framework for graph benchmarks. We show that (i) invariants are more expressive than standard GNNs, (ii) invariants characterize structural heterogeneity within and across benchmark datasets, (iii) invariants predict multi-task performance, and (iv) simple invariant-based models are competitive with, and sometimes exceed, transformer and message-passing baselines across 26 datasets. Our results suggest that expressivity is not the main driver of predictive performance, and that on tasks where structure matters, a non-trainable structural proxy often matches trained message-passing models. We thus posit that invariant baselines should become a standard for evaluating whether structure is required for a task and whether a model picks up on it, serving as a stepping stone towards graph foundation models. 1 Introduction Graphs offer a parsimonious representation for a wide variety of datasets and tasks [ 41 ] , giving rise to efficient machine learning models that are predominantly based on the message-passing paradigm [ 9 ] . However, even though a plethora of graph learning models exists, the community is still split when it comes to the existence of graph foundation models , with some researchers stating that domain-specific models already exist [ 28 ] , whereas others are citing the absence of an agreed-upon “backbone architecture”, among other things, as an indicator that substantial challenges have yet to be tackled. In parallel to this discussion, prior work [ 4 , 10 , 33 , 3 ] also pointed out issues concerning the evaluation practices of the field, including (i) small dataset sizes, which often prevent making statistically significant statements concerning predictive performance, (ii) a lack of structural diversity within datasets, thus preventing model generalization, and (iii) a focus on metrics like expressivity that are not a priori aligned with or even required for a specific task. Our work deals with assessing the obstructions towards achieving graph foundation models (GFMs), with a specific focus on assessing the interplay of graph structure and graph features . We consider understanding the impact of graph structure to be a crucial aspect, since GFMs need to be able to handle large heterogeneous datasets and generalize based on structural information they contain. However, standard graph learning models are unsuitable for measuring structure due to the fact that they intertwine it with features during message-passing . We thus present a principled, fundamentals-first approach that leverages graph invariants to create structural fingerprints of a graph. With invariants serving as computable proxies for graph structure, we can study to what extent structure is important for existing graph benchmark datasets. Alongside raising important questions about dataset quality, we also contribute a novel experimental evaluation methodology based on graph invariant baselines . We show that such baselines are often competitive, thus serving as a simple diagnostic tool to discover model–task misalignment. 2 Using graph invariants in graph learning Invariants. Although local aggregation is central to architectures such as graph convolutional networks [ 22 ] and graph attention networks [ 40 ] , incorporating global structural information remains challenging. One natural way to encode such information is through graph invariants: interpretable, permutation-invariant quantities. Formally, let \mathcal{G} denote the space of finite undirected graphs without self-loops. A function I\colon\mathcal{G}\to\mathbb{R} is a graph invariant if, for any two isomorphic graphs G,H\in\mathcal{G} , then I(G)=I(H) . For example, the Wiener index [ 43 ] measures the spread of a connected graph G=(V,E) by summing shortest-path distances over all pairs of vertices: I(G)\coloneq\frac{1}{2}\sum_{i\in V}\sum_{j\in V}d(i,j). Path graphs have large Wiener index, whereas complete graphs have small Wiener index. The Wiener index has therefore been widely used as a simple descriptor of molecular structure and biological activity [ 37 ] . Such graph invariants provide a natural lens through which to study graph expressivity. While a single invariant is usually not sufficient to distinguish all non-isomorphic graphs, families of invariants from different domains can capture increasingly rich structural information. Thus, graph invariants offer a concrete way to encode global graph structure rather than only local aggregation patterns. To use invariants as model inputs, we concatenate them into a single vector, yielding one feature vector per graph. Models. Throughout our experiments, we rely on two families of models: graph neural networks (GNNs) and gradient-boosted tree ensembles. Specifically, we use the Graph Isomorphism Network (GIN) [ 45 ] , which follows the message-passing paradigm [ 9 ] by iteratively updating node representations through aggregation over local neighbourhoods. We employ GIN in a multi-task setup in Section 3.3 . For all benchmark comparisons in Section 3.4 , we instead use XGBoost [ 8 ] , a gradient-boosted tree ensemble that operates on tabular inputs. This choice is deliberate: invariants yield a tabular fingerprint of each graph, and feature sets can likewise be aggregated into a single vector. Compared to GNNs, XGBoost is computationally more efficient, exposes fewer hyperparameters, and is therefore easier to tune exhaustively, an important property given the breadth of datasets and configurations we evaluate. 3 Experiments: How invariants support graph learning tasks In the following, we will be assessing the utility of invariants in four different scenarios. The commonality of all subsequent experiments is that we precompute invariants for all graphs of a dataset (when feasible) but we use them in different ways, ranging from static features for expressivity analysis to augmentation of graph-level representations for various classification tasks. Our main questions are: Q1: How expressive are invariants? Q2: To what extent do invariants characterize existing datasets? Q3: Can invariants predict multi-task learning performance? Q4: Do invariants capture the relevance of graph structure? 3.1 Invariants are expressive Certain types of invariants (e.g., local homomorphism counts , laplacian eigenvalues , molecular indices ) have already been shown to capture relevant structural information for graph learning tasks [ 21 , 13 , 30 ] . We thus hypothesize that the combination of multiple invariants should be capable to capture structural information across many classes of graphs. To quantify this, we investigate the ability of invariants to differentiate between non-isomorphic pairs of graphs. Our experiment uses the BREC dataset [ 42 ] , which consists of 400 graphs that are not distinguishable by 1 -WL , the Weisfeiler–Lehman test for graph isomorphism [ 32 ] . This dataset is commonly used to assess the realized expressivity of graph learning models. To determine whether an encoding method can distinguish between two graphs, the encodings of both graphs are compared to encodings of their isomorphic relabellings, with the requirement that differences between the pair have to be consistently large, whereas differences between their relabelled versions have to be consistently small [ 42 ] . Since graph invariants are invariant under any graph isomorphism, this criterion is substantially simplified and only requires us assessing whether two invariants have the same value for a pair of non-isomorphic graphs. Table 1 : Excerpt from table in 42 with two additional rows