No Metric to Rule Them All: Toward Principled Evaluations of Graph-Learning Datasets
Authors: Corinna Coupette
Jeremy Wayland
Emily Simons
Bastian Rieck
Venue: ICML 2025 poster (2025)
Keywords: data-centric graph learning
network data
dataset evaluation
Primary area: deep_learning->graph_neural_networks
TL;DR: We introduce a framework for assessing the quality of graph-learning datasets by measuring differences between the original dataset and its perturbed representations.

Abstract: Benchmark datasets have proved pivotal to the success of graph learning, and *good* benchmark datasets are crucial to guide the development of the field. Recent research has highlighted problems with graph-learning datasets and benchmarking practices—revealing, for example, that methods which ignore the graph structure can outperform graph-based approaches. Such findings raise two questions: (1) What makes a good graph-learning dataset, and (2) how can we evaluate dataset quality in graph learning? Our work addresses these questions. As the classic evaluation setup uses datasets to evaluate models, it does not apply to dataset evaluation. Hence, we start from first principles. Observing that graph-learning datasets uniquely combine two modes—graph structure and node features—, we introduce RINGS, a flexible and extensible *mode-perturbation framework* to assess the quality of graph-learning datasets based on *dataset ablations*—i.e., quantifying differences between the original dataset and its perturbed representations. Within this framework, we propose two measures—*performance separability* and *mode complementarity*—as evaluation tools, each assessing the capacity of a graph dataset to benchmark the power and efficacy of graph-learning methods from a distinct angle. We demonstrate the utility of our framework for dataset evaluation via extensive experiments on graph-level tasks and derive actionable recommendations for improving the evaluation of graph-learning methods. Our work opens new research directions in data-centric graph learning, and it constitutes a step toward the systematic *evaluation of evaluations*.

No Metric to Rule Them All: Toward Principled Evaluations of Graph-Learning Datasets
Corinna Coupette 12
Jeremy Wayland 34
Emily Simons
34
Bastian Rieck 345
Abstract
1. Introduction
Benchmark datasets have proved pivotal to the success of graph learning, and good benchmark datasets are crucial to guide the development of the field. Recent research has highlighted prob- lems with graph-learning datasets and benchmark- ing practices-revealinn
Over the past decade, graph learning has established itself prominent approach making predictions from rela- tional data, with remarkable success in areas from small molecules (Fang et al., 2022; Stokes et al., 2020) to large social networks (Sharma et al., 2024; Ying et al., 2018). 8). Despite significant progress on the theory of graph neural networks (Morris et al., 2024), however, many empirical intricacies of graph-learning tasks, models, and datasets remain poorly understood. For example, recent research has revealed that (1) purported performance gaps disappear with proper hyperparameter tuning (Tönshoff et al., 2023), (2) popular graph-learning datasets occupy a very peculiar part of the space of all possible graphs (Palowitch et al., 2022), (3) some graph-learning tasks can be solved without using the graph structure (Errica et al., 2020), and (4) graph- learning models struggle to ignore the graph structure when the features alone are sufficiently informative for the task at hand (Bechler-Speicher et al., 2024). These findings sug- gest need for better infrastructure to assess graph-learning methods, supporting rigorous evaluations that paint a realis- tic picture of the progress made by the community.
for example, that meth- ods which ignore the graph structure can outper- form graph-based approaches. Such findings raise two questions: (1) What makes a good graph- learning dataset, and (2) how can we evaluate dataset quality in graph learning? Our work ad- dresses these questions. As the classic evalua- tion setup uses datasets to evaluate models, it does not apply to dataset evaluation. Hence, we start from first principles. Observing that graph-lcarning datasets uniquely combine two godes-graph structure and node features-, we introduce RINGS, a flexible and extensible mode- perturbation framework to assess the quality of graph-lcarning datasets based on dataset abla- tions i.e., quantifying differences between the original dataset and its perturbed representations. Within this framework, we propose two mea- sures--erformance separability and mode com- plementarity as evaluation tools, each assess- ing the capacity of graph dataset to benchmark the power and efficacy of graph-learning meth- ods from a distinct angle. We demonstrate the utility of our framework for dataset evaluation via extensive experiments on graph-level tasks and derive actionable recommendations for im- proving the evaluation of graph-learning methods. Our work opens new research directions in data- centric graph leaming, and it constitutes step toward the systematic evaluation of evaluations.
Necessity and Challenges of Dataset Evaluation. Bench- mark datasets play key role in the evaluation of graph- learning methods, but the results cited above highlight that not all (collections of) graphs are equally suitable for that purpose. This motivates us to flip the script on graph- learning evaluation, asking how well graph-learning datasets can characterize the capabilities of graph-learning methods, rather than how well these methods can solve tasks on graph learning datasets. Our work is guided by two questions:
Q1 What characterizes good graph-learning dataset? Q2 How can we evaluate dataset quality in graph learning?
Addressing these questions is not straightforward. First, the classic evaluation setup, which compares performance across models while holding the dataset constant, cannot be used to evaluate datasets. Second, comparing performance levels across datasets while holding the model constant yields measurements that are confounded by model capabil- ities. Third, while performance levels indicate the difficulty of a dataset for existing methods, these levels provide little
'Equal contribution. 'Aalto University, Finland Max Planck Institute for Informatics, Germany 'Helmholtz Munich, Germany "TU Munich, Germany University of Fribourg, Switzerland. Cor- respondence to: Corinna Coupette ecorinna.coupetter @ fi>
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

No Metric to Rule them All: Toward Principled Evaluations of Graph-Learning Datasets
information about dataset quality: A difficult dataset of high quality may guide the field toward methodological innova- tion, but difficult dataset of low quality may detract from real progress. Hence, our work starts from first principles.
Graph Structure
Original [o]
Empty [eg]
Complete [eg]
Random [rg]
Desirable Properties of observe that attributed graphs combine two types of infor- mation, the graph structure and the node features. Graph- learning methods leverage both of these modes to tackle given learning task.' This suggests the following desirable property for a dataset to reveal powerful insights into the capabilities of graph-learning methods, given a specific task:
Datasets. We
Original [o]
Emply [ef] Complete [cf] Random [rf]
PO
The graph structure and the node features should con- tain complementary lusk-relevant information.
Node Features
Figure 1: Overview of our main mode perturbations. Given ring of cliques on 12 nodes (top left panel) with 12-dimensional node features (bottom left panel), we show our input data for the original and perturbed states of the graph structure (top row) and the features (bottom row).
Assessing whether this property is present poses theoretical and practical challenges- not only due to the limitations of existing graph-learning methods but also because the relationship between task relevance and complementarity is potentially complicated. However, we can identify the following necessary conditions for PO to be satisfied:
P1
The graph structure and the node features should both contain task-relevant information.
turbations: performance separability, addressing P1, and mode complementarity, addressing P2.
P2 The graph structure and the node features should con- tain complementary information.
C3 Experiments. We demonstrate the value of our frame- work and measures through extensive experiments, fo- cusing on real-world datasets with graph-level tasks. C4 Recommendations, Based C1-C3, we derive con- crete recommendations for improving benchmarking and evaluation practices in graph learning.
Notably, while P1 is lask-dependent, P2 is task-independen.
Principled Evaluations via Mode Perturbations. Both P1 and P2 address the relationship between the different modes of a graph-learning dataset. Therefore, test datasets for these properties, we propose RINGS (Relevant Information in Node features and Graph Structure), dataset-evaluution framework based on the concept of mode perturbation. As il- lustrated in Figure 1, a mode perturbation maps an attributed graph (G, X) to an attributed graph (G', X'), replacing the original edge set or feature set with modified version according given transformation (e.g., randomization). This allows to make measurements on both (G, X) and (G', X'). Given appropriate measures, the difference be- tween the resulting measurements can then provide insights into P1 and P2. In analogy to model ablations in the eval- uation of graph-learning methods, mode perturbations can also be thought of as dataset ablations.
Our work opens new research directions in data-centric graph learning, and it constitutes a first step toward our long-term vision of enabling evaluations of evaluations: systematic assessments of the quality of evidence provided for the performance of new graph-learning methods.
Structure. In Section 2, we formally introduce RINGS, our pottepperturbation framework for evaluating graph-learning datasets, along with our proposed dataset quality measures. Having reviewed related work in Section we demonstrate the practical utility of our framework through extensive experiments in Section 4. We discuss conclusions, limita- tions, and avenues for future work in Section 5. Detailed supplementaries are provided in Appendices A to E.
Our Contributions. We make four main contributions:
2. The RINGS Framework
C1 Framework. We develop RINGS, flexible and exten- sible framework to assess the quality of graph-learning datasets by quantifying differences between the origi- nal dataset and its perturbed representations.
After establishing our notation, we develop RINGS, our framework for evaluating graph-learning datasets. We do so in three steps, intuitively introducing and formally defining mode perturbations (2.1), performance separability (2.2), and mode complementarity (2.3).
C2 Measures. As part of RINGS, we introduce two mea- sures for evaluating graph datasets based on mode per-
Preliminaries. We work with attributed graphs (G, X), where = (V, E) is graph with n = [V] nodes and m = [E] edges, X R the space of k-dimensional node
Notably, to be amenable to graph learning, even non-attributed graphs need to he assigned node features (c.g., one-hot encodings).
2

---

No Metric to Rule them All: Toward Principled Evaluations of Graph-Learning Datasets
features, and we assume w.l.o.g. that X n. For graph- level tasks, we have datasets D {G1.- ......... .x ). where N is the total number of graphs. Given a set S, 2 is its power set, and (5) is the set of all é-element subsets of S. Multisets are denoted by {()). and the set of positive integers no greater than & is written as [Q = ii E 10 E).
To modify entire collections of graphs, apply mode per- turbations element-wise to all graphs in given collection. Definition 2.4 (Dataset Perturbation). Given a dataset D of attributed graphs and a mode perturbation yp, a dataset per- turbation is given by (pD) = (x(G, (G, E D).
2.2. Performance Separability
2.1. Mode Perturbations
By systematically applying mode perturbations to a dataset D, we create a set of datasets that contains several different versions of D, capturing potentially interesting variation. This variation can be leveraged to investigate the properties derived in Section 1. First addressing P1, we now introduce performance separability as measure to assess the extent to which both the graph structure and the node features of an attributed graph contain task-relevant information.
Given an attributed graph X), both data i... the graph structure and the node features-ard are naturally as- sociated with metric spaces that encode pairwise distances between nodes (i.e., distance matrices"). In our RINGS framework, we modify these metric spaces reveal infor- mation about the quality of graph-learning datasets. This idea is formalized in the notion of mode perturbation.
Definition 2.1 (Mode Perturbation). A mode perturbation yp is a map between attributed graphs such that yo: XG H
Intuitively, given two perturbations ip, sp of a dataset D as well as task to be solved on D, performance separability measures the distance between performance distributions associated with (DD) and (D). For a formal definition, we need notation describing these distributions.
This definition is very general, allowing y, inter alia, to act on both the graph structure and the node features. For the purposes of understanding the connection between graph structure and node features in graph-learning datasets, how- ever, we focus on mode perturbations that modify either the graph structure or the node features, as illustrated in Figure 1. We start by formalizing our feature perturbations. Definition 2.2 (Feature Perturbations). Given an attributed graph () on nodes with features X c R* we define:
Definition 2.5 (Tuned Model). A tuned model M is a triple M == (D, A, O). where D represents the dataset and associ- ated task, A the architecture used during training, and 0 denotes the tuned parameters for the specific architecture.
To elucidate the relationship between the graph structure and the node features as it pertains to performance, within RINGS, we tune models not only on datasets D but also on perturbed datasets (DD).
Per: : (G, X) -> (G, O,))
[empty features]
Par: (G, + In)
[complete features]
Definition 2.6 (Tuned Perturbed Model). For mode per- turbation yp, MM == (D)(D), A. 0) denotes a model tuned to solve the task associated with D under mode perturbation po
Pit : (G,X) + (G, Rx())
[random features]
Here, RE Ra*k - Roxk' randomizes the features X.
The performance distributions underlying our notion of per- formance separability can then be defined as follows. Definition 2.7 (Empirical Performance Distribution). For tuned (perturbed) model MMp. given an evaluation metric and a set of initialization conditions Z, the empirical performance distribution pf." of Mi is the distribution associated with performance measurements
We can define a matching set of structural perturbations by modifying our original edge set.
Definition 2.3 (Structural Perturbations). Given an at- tributed graph (G, X) with edge set E, we define:
Peg X), + X)
[empty graph]
Pog: XG, + ((V (x)) x)
[complete graph]
{(((M.:)) () 1 IEE 2))
(1)
Prg (G,X) + ((V, Rs(E))
[random graph]
With performance separability, we now enable pairwise comparisons between the performance distributions of mod- els trained and evaluated on distinct perturbations of D. Definition 2.8 (Performance Separability). Fix a dataset D. an evaluation metric f, and initialization conditions Z, and let ye, s be mode perturbations. We define the performance separability 57 of y and sp' as
Here, Rs : 2(h) + 2(x) randomizes the edge set E.
For consistency, we also define the original perturbation Po: : (G,X) + (G, X) [original].
DDeferring further details to Appendix A, we note that for finite metric spaces, we have (Y, d) v D E "x" i.c., finite matrix encoding pairwise distances between elements in Y. We use D in contexts that rely on matrix operations, and (Y,d) d) emphasize both the original space and the associated metric.
2 <7 = D(P Pf.
(2)
where DD a method comparing distributions.
3

---

No Metric to Rule them All: Toward Principled Evaluations of Graph-Learning Datasets
In our experiments (Section 4.1), use the Kolmogorov- Smirnov (KS) statistic with permutation testing instantiate 4/ This allows us to assess whether the performance dis- tributions associated with Ma and Mar are significantly different. To evaluate Pl, we can then interpret lack of (sta- tistical) performance separability between a model trained on the original data and a model trained on a mode pertur- bation as evidence that the perturbed mode does not contain (non-redundant) task-relevant information.
(G, X)
D3
17p
D3
D7
D's
D4
D's
D
D/s
D
D'g D3.
2.3. Mode Complementarity
Figure Setup for mode-complementarity
assessment.
For (G, X) from Figure I, we show the metric spaces arising from original graph structure (D2),, original node features (D+), and 3 feature perturbations (De, De Dj), along with the differences between D3 and the feature spaces that underlie our mode-coomlemmentariy computations. For structural perturbations, we swap the roles of D's and D'r- Note that the spaces arising from complete graph and com- plete (one-hot) features are equivalent, as are the (degener- ate) spaces arising from empty graph and empty features.
While performance separability allows us to assess dataset quality in setting similar to traditional model evaluation, it has three main limitations. First, it is task-dependent due to its focus on Pl, and thus risks underestimating datasets whose tasks are simply misaligned with the information con- tained in them. Second, it is measured based on, and hence still to some extent confounded by, model capabilities. And third, it resource- inntesceentenssve to compute. To address P2 and forego these limitations, we propose mode complementarity.
Intuitively, as illustrated in Figure 2, for attributed graph X) mode complementarity measures the distance be- tween a metric space constructed from the graph structure and a metric space constructed from the node features. To formalize this, we define a process for constructing metric spaces from both modes in (G,X) using lift functions.
With mode complementarity, we then measure the distance between the normalized metric spaces arising from the graph structure and the node features.
Definition 2.12 (Mode Complementarity). Given at- tributed graph (G, X) with structural metric ds, derived from G, and feature metric dp, derived from X, we define the mode complementarity of XG as
Definition 2.9 (Metric-Space Construction). For attributed graph (G.X) and metric d, we construct metric spaces as
P. = Cp.g (Ds, Dr),
(6)
La : (G, (V.d);
(3)
where C is a comparator from Definition 2.11,
i.e. lifts that take in either structure-basee distances aris- ing from G or feature-based distances arising from X and produce a metric space over the node set V.
Ds == Ds/diam(Dg) for Dg == Las (G, X);
(7)
Dr == DT/ /dimm for Dj = Lar (G,X),
(8)
In RINGS, combine these lifts with mode perturbations.
using the lifts from Definition 2.9, and we leave (degenerate) zero-diameter spaces unchanged.
Definition 2.10 (Perturbed Metric Space). Given an at- tributed graph (G, X) and an associated metric d, the &- perturbed metric space of (G, under is
Note that since mode complementarity takes an Lp. norm of normalized metric spaces, we have (G, E [o. 1] by construction. To extend mode complementarity to mode perturbations, we again leverage function composition. (4)
D = o (G,X),
Definition 2.13 (Perturbed Mode Complementarity). Given an attributed graph (G. X) and mode perturbation yp, the mode complementarity of (p(G, X) is
which we construe as distance matrix.
This allows us to assess differences between mode perturba- tions by comparing metric spaces.
7. o (G, = CD DG)
(9)
Definition 2.11 (Metric-Space Comparison). For a fixed set of n points and two metrics d and d', we compare the metric spaces that arise from d and d' by computing the Lp.q norm of the difference of their n. X n matrix representations, i.e.,
For notational clarity, we use subscript convention to de- note the mode complementarity of (G. X) under specific (G, mode perturbations, i.e., 7. " ) = 7 px (G, X)).
Da - Da
To assess P2, we can interpret high levels of mode comple- mentarity under given mode perturbation as evidence that,
(Da Dx)
2 n
4

---

No Metric to Rule them All: Toward Principled Evaluations of Graph-Learning Datasets
in the metric spaces associated with that perturbation, the graph structure and the features contain complementary in- formation. We can also gain further insights by assessing the differences between mode-comp complemetaal levels across mode perturbations. Depending on the mode perturbations compared, these differences reveal information about the nature of the connection between the graph structure and the node features, or about the diversity present in G and X.
2021; Luan et al., 2023; Platonov al., 2023a;b). While homophily characterizes the task-dependent relationship between graph structure and node labels, mode complemen- tarity assesses the inse-independent relationship between graph structure and node features. For node classification, Dong & Kluger (2023) propose the edge signal-to-noiss ra- tio (ESNR), Qian et al. (2022) develop a subspace alignment measure (SAM), and Thang et al. (2022) analyze relations between node features and graph structure (FvS). However, with mode complementarity, we craft score that (1) treats graph structure and node features as equal (unlike ESNR), (2) works on graphs without node labels and does not make assumptions about the spaces arising from edge connectivity and node features (unlike SAM, FvS), and (3) specifically in- forms graph-level learning tasks (unlike all of these works).
In Proposition A.10 (Appendix A), formalize the rela- tionship between empty mode perturbations SPew and what we call ceeeleeomleeettriityy showing that " X) mea- sures the geometric structure of the unperturbed mode. Based on both limiting behaviors of (G, which correspond to uninformative metric-space structures, we can then define notion of mode diversity.
Definition 2.14 (Mode Diversity). Given an attributed graph XG, the mode diversity of (G, X) for {f.g) is
4. Experiments
We now demonstrate how to use RINGS to evaluate the quality of graph-learning datasets, guided by the principles developed in Scction I. Leveraging our mode- codee-eetturbttoon framework, we explore P1 via performance separability and P2 via mode complementarity, before distilling our obser- vations into actionable taxonomy of recommendations. For further details and additional results, including regres- sion tasks, transformer architectures, and graph-level perfor- mance comparisons between models, see Appendix D.
A, = 1 1 - 2 2 (G, X) E [0, 1].
(10)
Intuitively, the mode diversity A. scores the ability of d. to produce non-trivial geometric structure. Note that A! X)) + 0 implies that La. + On, or Ld. + 1, I,, our canonical uninformative metric spaces.
In our experiments, we instantiate de with the Euclidean distance between node features and ds with diffusion distance based on the graph structure (explained in Ap- pendix B) to approximate the computations underlying graph-learning methods. We further choose the L1, norm as our comparator, which yields a favorable duality, proved in Appendix A, between empty and complete perturbations.
Evaluated Datasets. In our main experiments, we evalu- ate 13 popular grash-classification datasets: From the life sciences, we select AIDS, oghg-molhiv (MolHIV), MU- TAG, and NCI1 (small molecules), as well DD, Enzymes, Peptides-fune (Peptides), and PROTEINS-full (Proteins) (larger chemical structures). From the social sciences, we take COLLAB, IMDB-B, and IMDB-M (collaboration ego- networks), as well as REDDIT-B and REDDIT-M (online interactions). To approximate the standard evaluation setup as closely as possible and ensure compatibility with a wide range of models, for all datasets, we use the node features as encoded by PyTorch-geometric and disregard the edge features. See Appendix C for details and references.
Theorem 2.15 (Perturbation Duality). Fix an attributed graph (G, X) and corresponding distances dg for lift- ing each mode into a metric space. For * E (ff.g, Defini- tion 2. 12 of y yields the equivalence
Yor (G, () = Neu 12 (G, X)
(11)
3. Related Work
Here, we briefly contextualize our contributions, deferring deeper discussion of related work to Appendix E.
4.1. Performance Separability (P1)
Expectations. (1) For a siructure- and feature-based task, the original dataset should separably outperform all other mode perturbations. (2) For a structure-based task, the original dataset should separably outperform all structural perturbations. (3) For a feature-based tusk, the original dataset should separably outperform all feature perturba- tions. (4) If the original dataset is separably outperformed
Relating to mode perturbations and performance separabil- iry, Errica et al. (2020) create GNN experiments to improve reproducibilityy and Bechler-Speicher et al. (2024) show that GNNs use the graph structure even when it not conducive to task (i.e., Pog. separably outperforms (².). RINGS is in- spired by, and goes beyond, these works, providing general framework for perturbation- baaed dataset evaluation.
"Our reproducibility package is publicly available via Zenodo at 10.5281/2enodo.1553 15543332. The code is maintained on GitHub at https///ithub..commados lawii///b.ooomididdaaaiiia.go
Connecting with mode complementarity, researchers have been particularly interested in the effects of homo- and heterophily on node-classification performance (Lim et al.,
5

---

No Metric to Rule them All: Toward Principled Evaluations of Graph-Learning Datasets
1.0
original
Aecuracy
0.6
0.8
emply graph
complete graph
random grapb
0.4
complete
0.2
random features
0.0
1.0
AUROC
0.6
0.4
0.2
0.0
AIDS
COLLAB
DD
Enzymes
IMDB-B IMDB-M MUTAG MolHIV
NCII
Peprides
Proteins
Reddit-B B Reddit-M -
Figure 3: Comparing GNN performance across different versions of the same dataset. We show the mean (dot) and 95th percentile interval (bars) of accuracy and AUROC across 100 runs of the best (as measured by the respective performance mean) among our tuned GAT, GCN, and GIN models, for the original version and perturbations of 13 graph-learning datasets. Black resp. silver horizontal lines show best mean trained resp. untrained performance the original data. For Reddit-M, the complete-grann and complete- features perturbations failed to train due to memory problems, but the existing results already allow us to conclude that this dataset lacks performance separability. Note that AUROC is the recommended evaluation metric for MolHIV; we include accuracy here only for completeness.
Dataset
Accuracy
AUROC
Structure
Features
Evaluation
AIDS
<f>>
0> eg rf >>> cg/g > eg c/híf
eflcg/tg > eg/o ff cg/g > eg if > of rg >>> cffcc//e//orf
uninformative informative uninformative uninformative
uninformative
COLLAB
informative
rg > eg of eg/o
uninformative
Enzymes
eg > cg/o > df
eg <g>0><0
of if o>cg > cg/gg > if of
informative
IMDB-B
ctfcg/cg/ohtiig cg/cg/o/ng <f If
(un)informative (un)informative (un)informative informative informative (un)informative uninformative
(un)informative
IMDB-M
cglcg/g > of
informative
MUTAG
et/cglolg > eg >f
2 cglcghtingg
uninformative
MolHIV
o> o> cffeg/ng > eg
o a><g>d>>g>> 1g
rf 0> a><g><>>BB eg/if eg <>>0><>< of rf ctlcg/cg/offiigg
informative
NCTI
0> og > of d
eg rf
informative
++
Peptides
0> 0g>>2g2>0
informative
Proteins
<f> eg/oor
uninformative
Reddit-B
ef >>> eg/if
ng > >>> cg/eg/r
uninformative uninformative
Reddit-M
rf rg >0>
rg r> eg
uninformative
uninformative
Table 1: Measuring pererrmanne separability between different versions of the same dataset. To quantify the conclusions permutation tests with 10 000
from Figure 3 and further account for performance distributions (Definition 2.7), random permutations and the Dolmogorov-Smimoo (KS) statistic as our test statistic at a-level of 0.01, Bonferroni- corrected for multiple hypothesis testing within each individual dataset. Here, for sets S₁ and Sy, S1 > S, denotes that the elements in the set S separably outperform the elements in the set S2 (i.e., the pairwise distances between 81 and #2 are statistically significantly different for all 81 E S₁ and 82 E S2), and we represent the sets in condensed notation, concatenating elements with We see that original datasets are often separably outperformed by their perturbed variants.
by structural (feature) perturbation, the structural (feature) mode of the dataset poorly aligned with the task.
For each version of each dataset, identify the model with the best performance under evaluation metric f E {accuracy, AUROC} as (A*, 0*) = arg (ax(A,0) E [MM {)], us- ing the performance distribution of the top model, M = (A" (") to assess performance separability.
Measurement. To evaluate performance separability, we train 3 standard GNN architectures (GAT, GCN, GIN) in the RINGS framework on the original and perturbations of our 13 main datasets: (empty, complete, random} graph, and (complete, random) features. With the setup described in Appendix Table 4, tune and evaluate total of 273 models. Although any GNN architecture could be used to evaluate performance separability within RINGS, using stan- dard architectures allows us to focus on dataset evaluation.
To compare performance distributions, we use permutation tests with the -ommigo (KS) statistic, Bonfer- roni correcting for multiple hypothesis testing within each individual dataset and testing differences for significance at a-level of 0.01 (see Appendix Tables 10 and 11 for substantively identical results using different setups).
"GNN cannot train with orr due to uninformative gradients.
Results.
We show the performance of the best GNN models
6

---

No Metric to Rule them All: Toward Principled Evaluations of Graph-Learning Datasets
1.0+
original
Mode Complmentnty Mode Conenene
0.8-
complete graph
empty graph
complete feattures
0.4
empty features
0.2-1
0.0
1.00
original
random graph
0.6
shuffled graph
random features
shuffled features
0.2
COLLAB
Eszymes
IMDB-B
MUTAG
MolHIV
NCII
Peptides
Proteins
Reddir-B
Roddi-MM
Figure 4: Comparing levels of mode complementarity across different versions of the same dataset. We show the mean (dot) and 95th percentile intervals (bars) of complementarity scores for the original version well as 4 deterministic perturbations (top) and 4 randomized perturbations (bottom) of 13 graph-learning datasets, computed with t =1 diffusson steps. Black horizontal lines indicate mean mode complementarities of the original dataset, and the silver horizontal line marks the 0.5 threshold relevant for assessing mode diversity. Note that Tog = 7eg and Yor = Not by Theorem 2.15.
in Figure 3, for the original and 5 mode perturbations over our main datasets and 2 evaluation statistics, and sum-
As
AP
Structure
Features
Dataset
/
P
marize the associated statistical performance-scparabiinn results in Table 1. We find that only 3 datasets- MolHIV, and NCII-satisfy satisfy the performance-separiinn relations expected from structure- and feature-based tasks (with Peptides coming close), whereas 5 datasets-AIDS, DD, Proteins, Reddit-B. B, and Reddit-M do not satisfy any separability requirements, highlighting their low quality from the perspective of P1. Among our striking results, the original dataset is separably outperformed by (1) the random-graue graph perturbation on DD, (2) the empty-graph per- turbation on Enzymes, and (3) the complete-feature and random-gras graphh perturbations on Reddit-Br B, indicating that the affected modes are poorly aligned with their current task.
AIDS
0.52
0.07
0.81
0.14
++
COLLAB
0.30
0.20
0.27
0.24
DD
0.62
0.09
0.13
0.03
++
Enzymes
0.38
0.10
0.66
0.13
++
IMDB-B B
0.18
0.11
0.55
0.29
0
IMDB-M
0.09
0.11
0.30
0.34
MUTAG
0.51
0.02
0.76
0.14
MolHIV
0.55
0.05
0.69
0.21
++
NCII
0.56
0.05
0.78 0.16
++
Peptides
0.61
0.01
0.71 0.23
++
++
Proteins
0.36
0.12
0.76 0.08
Reddit-B
0.71
0.05
0.80 0.12
Reddit-M
0.72
0.03
0.85 0.11
Table 2: Evaluating mode diversity. We assess the mean (μ) and standard deviation (a)) of structural diversity (As) and feature diversity (Ar) for 13 graph-learning datasets.
4.2. Mode Complementarity (P2)
Expectations. (1) For a structure- and feature-basee based task, the original dataset should have high mode complementarity, and both modes should have high mode diversity (indicated by high mode complementarity of the empty and complete perturbations of their dual mode). (2) For a structure-based task, the structural mode should have high mode diversity. (3) For a feature-bass -baed task, the feature mode should have high mode diversity. (4) If the original dataset has low mode complementarity. the information contained in structure and features is redundant. (5) If both modes have low mode diversity, the dataset contains little insightful variation.
bation, we instantiate Definition 2.12 using the Euclidean distance as our feature distance, the diffusion distance (see Appendix B) for number of diffusion steps E [10) as graph distance, and the L1, norm as our comparator (see Appendix B for examples of other choices).
Results. In Figure 4, we show the mean and 95th per- centile intervals of the mode-coompeementariy distributions at / = 1, for the original and the 8 other selected mode perturbations, for each of our 13 main datasets. We observe interesting differences between conllccomllementaritt pro- files across datasets. For example, (1) COLLAB, IMDB-B. B, and IMDB-M stand out for their large ranges (likely due to their nature as ego-networks); (2) DD attains extreme values with its complete-gras and empty- -gaahh perturba- tions (likely due to the absence of features in the original dataset, translated into complete-type features by Py
Measurement. We evaluate mode complementarity for the original as well as 4 fixed and randomized mode pertur- bations: {complete, empty, random, shuffled} x {graph, features} (see Appendix D for detailed descriptions). To measure mode complementarity (and the mode diversity derived from it), for each graph in a given dataset pertur-
7

---

No Metric to Rule them All: Toward Principled Evaluations of Graph-Learning Datasets
geometric); and (3) Peptides has mode complementarities in the random-graph and the complete-graph perturbations that are noticeably higher than that of the original dataset (possibly related to the presence of long-range connections).
1.0
DATASET
Proteins
AIDS
Roddit-B
4 1000
COLLAB
Reddit M
0.8
DD
PERTURBATION
AUROC
Farymes
original
Supplementing Figure 4 with mode-diversity scores in Ta- ble 2, we find that feature diversity is more common than structural diversity, and variation in structural diversity is almost always low. Notably, (1) COLLAB, IMDB-B, and IMDB-M, judged favorably or neutral by performance sep- arability, score poorly on structural and feature diversity, suggesting that their tasks may not reveal much information about the power of graph-learning methods; (2) conversely, among the datasets judged problematic by performance sep- arability, DD exhibits high levels of structural diversity, in- dicating its potential for adequately aligned structural tasks; and (3) Reddit-B B and Reddit-M show high levels of struc- tural and feature diversity, indicating untapped potential for graph-learning tasks that are based on both structure and features, as well as high quality from the perspective of P2.
IMDB-B
complete graph
IMDB-M
emppy griph
0.6
MUTAG
random graph
4000
1040000
MolitIV
complete features
NCII
random features
Pepcides
0.4
0.1
0.4
0.7
1.0
Mode Complementarity
Figure 5: Mode complementarity and performance. We show mean AUROC (y) as function of mean mode comple- mentarity (x), for the original version and 5 perturbations of our 13 main datasets, based on our nest-on-average models (as in Figure 3). Each marker represents a (dataset, pertur- bation, t) tuple, where t [10] is the number of diffusion steps in the diffusion distance. Higher mean mode comple- mentarity is associated with higher AUROC, and datasets differ in the range of their mode-comppleenttariy shifts.
To conclude, we explore the relationship between mean mode complementarity and mean (AUROC) performance across all mode perturbations in Figure 5 (see Appendix Figure 10 and Table 18 for extended results). We find that higher mode complementarity is generally associated with higher performance, with exceptions for some tasks we pre- viously identified as misaligned (DD and Reddit-M). Since evaluating performance separability is comparatively costly, this further underscores the value of mode complementarity datasets.
on the definition and interpretation of each action category.
Keep (t))) This category contains datasets with high per- formance separability and high structural diversity. These datasets constitute valuable graph-learning benchmarks.
Realign (t). We call a dataset misaligned if it exhibits low performance separability but high structural diversity. Re- alignment, then, collectively denotes several potential op- crations, including changing the prediction targets (c.g.. using different categories to classify discussion threads in Reddit-B Reddit-M) or changing the prediction task (e.g.. moving from graph-level to a node-level task).
as task-anneeeed insseinneenndent diagnostic for
4.3. Dataset Taxonomy
From our observations on performance separability (P1) and mode complementarity (P2), we can distill the following actionable dataset taxonomy, where we note evidence from performance separability (f) and mode complementarity (t):
Deprecate (t). This category contains datasets with high performance separability but low structural diversity. Al- though both structure and features may be needed to achieve state-of-the-art performance, these datasets do not contain interesting structural variation, and as such, they do little to probe the capabilities of graph-learning models.
Action
Datasets
Keep (
MolHIV, NCII, Peptides
Realign (+)
AIDS, DD, MUTAG, Reddit-B, Reddit-M COLLAB, IMDB-B, IMDB-M
Deprecate (1)
Deprecate (+ Enzymes, Proteins
Deprecate (t]t). This category contains datasets that exhibit low structural diversity and low performance separability. These datasets do not currently require the capabilities of graph-learning models to integrate information from struc- ture and features, and they also do not hold sufficient struc- tural diversity to change this via realignment.
Taxonomy, categories, and interpretation. Our taxonomy built on our measures of performance separability and structural diversity (derived from mode complementarity). Here, we emphasize structural diversity over feature di- versity because the structural mode is characteristic of the graph-learning setting, acknowledging that datasets with high feature diversity could still be useful as benchmarks in settings outside of graph learning. Here, we call the value of a measure high if it is judged as o, +, or ++ (see Tables and 2), and low otherwise. In the following, we elaborate
Separability, complementarity, and misalignment. While our experiments show that higher mode complementarity is associated with higher performance (see Figure 4), we make no claims about the relationship between mode diversity and performance separability. Since performance separability assesses the task task-specific performance gap between dataset
8

---

No Metric to Rule them All: Toward Principled Evaluations of Graph-Lcarnnig Datasets
and its perturbations, and mode diversity measures the task- agnostic variation contained in the modes of individual dataset, we would not expect high mode diversity to be consistently associated with high performance separability. For example, a dataset could have high structural and feature diversity but low mode complementarity, which could lead to complete graph and complete features performing on par with the original mode, eliminating separability.
notion of mode complementarity is task-independent and model-agnostic. This allows to gain insights into datasets, but the inclusion of additional information about models would enable claims about (model, dataset, task) triples.
Future Work. We envision RINGS to support the design of better datasets and more challenging tasks for graph learn- ing, and we hope that the community will use our measures to further scrutinize its evaluation infrastructure. Addition- ally, we highlight four concrete avenues for future work.
Misalignment occurs when there is interesting variation in the data that models could leverage in their predictions (high mode diversity). but the existing relationship between this variation and the prediction target does not provide a sig- nificant performance advantage over settings in which this relationship is deliberately destroyed (lack of performance separability). While the lack of performance separability could also be due to limitations of the models employed (i.e., they may not be expressive enough), given our com- prehensive measurement setup, we deem it more likely that the relationship between the variation in the data and the prediction target is strained, prompting the need for realign- ment. However, more work is needed to disentangle the model-related and the data-related factors contributing lack of performance separability.
F1 Theoretical analysis. While we provided initial theoret- ical results on the behavior of perturbed mode comple- mentarity, a comprehensive theoretical analysis of its properties is yet outstanding. Adopting an information- theoretic perspective could yield valuable insights F2 Task coverage. Our work focused on graph-level tasks, but node-level tasks and edge-level tasks, too, merit closer inspection. While performance separability immediately applies to such tasks, extending mode complementarity requires further conceptual advances. These advances might also naturally give rise to a lo- calized notion of mode complementarity.
F3 Feature coverage and graph coverage. RINGS natu- rally accounts for node features, but some datasets also contain edge features or graph-level features that could be incorporated into our framework. Likewise, defining mode complementarity for more expressive types of graphs- from temporal graphs to hypergraphs-would constitute a valuable extension of RINGS.
5. Discussion
Conclusions. We introduced RINGS, a principled frame- work for evaluating graph-learning datasets based on mode perturbations-iie. controlled changes to their graph struc- ture and node features. In RINGS, we developed perfor- mance separability as a task-dependent, and mode comple- mentarity task-independent measure of dataset qual- ity. Using our framework to categorize 13 popular graph- classification datasets, we identified several benchmarks that require realignment (e.g., by better data modeling) or complete deprecation.
F4 Model interpretability. While RINGS was designed for dataset evaluation, it can also enhance the inter- pretability of graph-learning models. For example, one could study how mode complementarity changes during training, or how mode-complemenntrity distri- butions impact train-eval- interesting insights into the relationship between mode complementarity and performance, and it could help elucidate the inner workings of individual models.
splits. This could yield
While some datasets have been observed to be problematic in prior work, with RINGS, we offer full perturbation- based evaluation pipeline. We designed our initial set of perturbations from data-centric perspective, but additional, cleverly crafted perturbations could also isolate and confirm the performance separability of new model contributions. Thus, we hope that RINGS will raise the standard of proof for model-centric evaluation in graph learning as well.
Finally, RINGS could support the design of better graph- learning models. As highlighted by our dataset taxonomy, by identifying datasets that do not require the specific capa- bilities of graph-learning models, performance separability helps direct devellede resources to where they are most needed. Moreover, mode complementarity and mode diversity could guide architectural choices for specific task on specific dataset (e.g., whether a model should focus on leveraging the graph structure or the node features). These measures could also inform model designs that incorporate data-centric components to enhance performance adaptively (both at the level of individual observations and at the level of entire datasets)-e.g, by preprocessing the data to in- crease mode complementarity. However, more research is needed to realize the potential of RINGS in these domains.
Limitations. Given that message passing is the predominant paradigm in graph learning, our performance-separdaen experiments mostly targeted passing GNNs, at the exclusion of other architectures. While RINGS is a general framework, our current norm-based comparison of metric spaces assumes that nodes and node features are paired. Thus, we presently do not measure aspects like the metric distortion arising from different mappings. Moreover, our
9

---

No Metric to Rule them All: Toward Principled Evaluations of Graph-Learning Datasets
Acknowledgments
Bonabi Mobaraki, E. and Khan, A. A demonstration of interpretability methods for Graph Neural Networks. In Proceedings of the 6th Joint Workshop on Graph Data Management Experiences & Systems ( (GRADES) and Net- work Data Analytics (NDA), pp. 1023.
This work has received funding from the Swiss State Secre- tariat for Education, Research, and Innovation (SERI). We acknowledge the use of the High Performance Computing cluster at Helmholtz Munich, maintained by the Scientific Computing and DigIT teams, as well as the computational resources provided by the Aalto Science-IT project.
Borgwardt, K., Ghisu, E., Llinares-Lóópez, F., O' O'Bray, L.,, and Rieck, B. Graph kernels: State-of-the-art and future challenges. Foundations and Trends in Machine Learning, 13(5-6):531-712 2020.
Impact Statement
With RINGS, we introduce principled data-centric frame- work for evaluating the quality of graph-learnngg datasets. We expect our framework to help improve data and evalu- ation practices in graph learning, enabling the community to focus on datasets that truly require resource-intensive graph-learning approaches via mode complementarity and encouraging greater experimental rigor via performance separability. Thus, we hope to contribute to reducing the environmental impact of the machine-learinng community, and to the development of scientifically sound, responsible Al methods.
Borgwardt, K. M., Ong, C. S., Schönauer, S., Vishwanathan, S. V. N., Smola, A. J., and Kriegel, H.-P. Protein func- tion prediction via graph kernlss. Bioinformatics, 21(1): 47-56, 2005.
Cai, C. and Wang. Y. A simple yet effective baseline for non-attributed graph classification. In Representation Learning Graphs and Manifolds Workshop at ICLR, 2018.
Chen, J., Chen, S., Bai, M., Gao, J.. Zhang. J., and Pu, J. SA-MLP: Distilling Graph Knowledge from GNNs into Structure-Aware MIP, 2022. arXiv:2210.09009 [cs].
References
Chen, T., Bian, S., and Sun, Y. Are powerful graph neu- ral nets necessary? A dissection on graph classification, 2020. AXXi:1905.00577 [cs].
Agarwal, C., Queen, O., Lakkaraju, H., and Zitnik, M. Eval- uating explainability for graph neural networks, Scientific Data, 10(1) (014):144, 2023.
Chuang, C.-Y. and Jegelka, S. Tree mover's distance: Bridg- ing graph metrics and stability of graph neural networks. In Advances in Neural Information Processing Systems, pp. 2944-2955 2022.
Akbiyik, E., Grötschla, F., Egressy, B., and Wattenhofer, R. Graphtester: Exploring theoretical boundaries of gnns on graph datasets. In Datu-centric Machine Learning Research (DMLR) Workshop at ICML, 2023.
Coifman, R. R. and Lafon, S. Diffusion maps. Applied and Computational Harmonic Analysis, 21(1):5-30, 2006. Special Issue: Diffusion Maps and Wavelets.
Alon, U. and Yahav, E. On the bottleneck of Graph Neural Networks and its practical implications. In International Conference on Learning Representations, 2021.
Debnath, A. K., Lopez de Compadre, R. L.., Debnath, G., Shusterman, A. J., and Hansch, C. Structure-activity rela- tionship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of Medicinal Chemistry, 34 (2): (2)7786-797, 1991.
Bai, X. and Hancock, E. R. Heat kernels, manifolds and graph embedding. In Structural, Syntactic, and Statisti- cal Pattern Recognition: Joint IAPR International Work- shops, pp. 198-206. Springer, 2004.
Barabási, A.-L. Network science. Cambridge University Press, 2016.
Di Giovanni, F., Giusti, L., Barbero, F., Luise, G., Lio, P., and Bronstein, M. M. On over-squashing in message passing neural networks: The impact of width, depth, and topology. In International Conference on Machine Learning, pp. 7865-7885, 2023.
Bechler-Speicher, M., Amos, I., GilaadBBahhaan R., and Globerson, A. Graph neural networks use graphs when they shouldn't. In International Conference on Learning Representations, 2024.
Ding, J. and Li, X. An approach for validating quality of datasets for machine learning. In IEEE International Conference on Big Data, pp. 2795-2803, 2018
Biderman, S. and Scheirer, W. J. Pitfalls in machine learn- ing research: Reexamining the development cycle. In Proceedings on "I Can't it Believe It's Not Better!" at NeurIPS Workshops, volume 137 of Proceedings of Ma- chine Learning Research, pp. 106-117. PMLR, 2020.
Dobson, P. D. and Doig, A. Distinguishing enzyme struc- tures from non-enzymes without alignments. Journal of Molecular Biology, 330(4):771-783 2003.
10

---

No Metric to Rule them All: Toward Principled Evaluations of Graph-Learning Datasets
Dong, M. and Kluger, Y. Towards understanding and re- ducing graph structural noise for gnns. In International Conference on Machine Learning, pp. 8202-8226, 2023.
Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. Open graph benchmark: Datasets for machine learning on graphs, 2020.
Dwivedi, V. P., Rampášek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A. T., and Beaini, D. Long range graph bench- mark. In Advances in Neural Information Processing Systems, pp. 22226-22222322 22340, 2022.
Jin, W., Barzilay, R., and Jaakkola, T. Junction tree vari- ational autoencoder for molecular graph generation. In Dy, J. and Krause, A. (eds.), Proceedings of the 35th International Conference on Machine Learning, vol- ume 80 of Proceedings of Machine Learning Research, pp. 2323-2332. PMLR, July 2018. URL https:// proceedings ml r press / v 1on00/ninn111m Ba h.tmml......
Dwivedi, V. Joshi, C. K., Luu, A. T., Laurent, T., Bengio, Y., and Bresson, X. Benchmarking graph neural net- works. Journal of Machine Learning Research, 24(43):1- 48, 2023. URL http:/ http//mmr../// wamlx.org//ii.. wttpp/prs.pppppp/eeeeoaeeese.ese 22- 0567 html.
Kersting, K., Kriege, N. M., Morris, C., Mutzel, P., and Neumann, M. Benchmark data sets for graph kernels, 2016.
Errica, F., Podda, M., Bacciu, D., and Micheli, A. fair comparison of graph neural networks for graph classifica- tion. In International Conference on Learning Represen- lutions, 2020.
Kipf. T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. In International Conference on Learning Representations, 2017.
Faber, L.. K. Moghaddam, A., and Wattenhofer. R. When comparing to ground truth is wrong: On evaluating GNN explanation methods. In Proceedings of the ACM SIGKDD Conference on Knowledge Discovery Data
Kriege, N. M., Johansson, F, D., and Morris, C. A survey on graph kernels. Applied Network Science, 5(1), 2020.
Kusner, M. J., Paige, B., and Hernández-Lobato, J. M.
Grammar variational autoencoder. In Precup, D. and Teh, Y. W. (eds.), Proceedings of the 34th International Con- ference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1945-1954. PMIR,, August 2017. URL https: /pppceeeeogggsss mllr. press / http///////k//////////// ....mmll.
Mining, pp. 332-341, 2021.
Fan, X., Gong, M., Xie, Y., Jiang, F., and Li, H. Structured self-attention architecture for graph-level representation learning. Pattern Recognition, 100:107084, 2020.
Fang, X., Liu, L., Lei, J., He, D., Zhang, S., Zhou, J., Wang, F., Wu, H., and Wang, H. Geometry-enhane molecular representation learning for property prediction. Nature Machine Intelligence, 1(2):127-134, 2022.
Leskovec, J., Kleinberg, J., and Faloutsos, C. Graphs over time: densification laws, shrinking diameters and possible explanations. In Proceedings of the ACM SIGKDD In- ternational Conference on Knowledge Discovery in Data Mining, pp. 177-187, 2005.
Fenza, G., Gallo, M., Loia, V., Orciuoli, F., and Herrera- Viedma, E. Data set quality in Machine Learning: Consis- tency measure based on group decision making. Applied Soft Computing, 106:107366, 2021.
Li, P., Yang, Y., Pagnucco, M., and Song, Y. Explainability in graph neural networks: An experimental survey, March 2022. arXiv:2203.0922 [cs].
Fey, M. and Lenssen, Fast graph represeetatiioonnn learning with pytorch geometric. In Representation Learning on Graphs and Manifolds Workshop at ICLR, 2019.
Li, Z., Cao, Y., Shuai, K., Miao, Y., and Hwang, K. Re- thinking the effectiveness of graph classification datasets in benchmarks for assessing gnns. In Proceedings of the Internationnl Joint Conference on Artificial Intelligence, pp. 2144-2152, 2024.
Gao, X., Xiao, B., Tao, D., and Li, X. A survey of graph edit distance. Pattern Analysis and Applications, 13(1): 113-129, 2010.
Lim, D., Hohne, F., Li, X., Huang, S. L.., Gupta, V., Bhalerao, O., and Lim, S. Large scale learning on non- homophilous graphs: New benchmarks and strong simple methods. In Advances in Neural Information P Processing Systems, pp. 20887-20902, 2021.
Germani, E., Fromont, E., Maurel, P., and Maumet, C. The HCP multi-pipeline dataset: An opportunity investi- gate analytical variability in fMRI data analysis, 2023. arXiv:2312. 14493 [q-bio].
Han, H., Liu, X., Ma, L., Torkamani, M., Liu, H., Tang, J., and Yamada, M. Structural Fairness-aware Active Learning for Graph Neural Networks. In International Conference on Learning Representations, 2023.
Limbeck, K., Andreeva, R., Sarkar, R., and Rieck, B. Met- ric space magnitude for evaluating the diversity of latent representations. In Advances in Neural Information Pro- cessing Systems, 2024.

---

No Metric to Rule them All: Toward Principled Evaluations of Graph-Lcarning Datasets
Lin, Y., Yang, M., Yu, J., Hu, P., Zhang, C., and Peng, X. Graph matching with bi-level noisy correspondence. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 23362-23377 2023.
Palowitch, J., Tsitsulin, A., Mayer, B. A., and Perozzi, B. Graphworld: Fake graphs bring real insights for gnns. In Proceedings of the ACM SIGKDD Conference on Knowl- edge Discovery and Data Mining, pp. 3691-3701, 2022.
Luan, S., Hua, C., Lu, Q. Zhu. J., Zhao, M.. Zhang, S., Chang, X., and Precup. D. Revisiting heterophily for graph neural networks. In Advances in Neural Informa- tion Processing Systems, 2022.
Platonov, O., Kuznedelev, D., Babenko, A., and Prokhorenkova, L. Characterizing graph datasets for node classification: Homophily-heterophiyy dichotomy and be- yond. In Advances in Neural Information Processing Systems, 2023a.
Luan, S., Hua, C., Xu, M., Lu, Q.. Zhu, J., Chang, X., Fu, J., Leskovec, J., and Precup. D. When do graph neural networks help with node classification? investigating the homophily principle on node distinguishability. In Ad- vances in Neural Information P Processing Systems, 2023.
Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A., and Prokhorenkova, L. A critical look at the evaluation of gnns under heterophily: Are we really making progress? In International Conference Learning Representations, 2023b.
Mao, H., Chen, Z., Jin, W., Han, H., Ma. Y., Zhao, T., Shah, N., and Tang, J. Demystifying structural disparity in graph neural networks: Can one size fit all? In Advances in Neural Information Processing Systems, 2023.
Qian, Y., Expert, P., Rieu, T., Panzarasa, P., and Barahona, M. Quantifying the alignment of graph and features in deep learning. IEEE Trans. Neural Networks Learn. Syst., 33(4):166331672 2022.
Mazumder, M., Banbury, C., Yao, X., Karlaš, B., Gaviria Ro- jas, W., Diamos, S., Diamos, G., He, I.., Parrish, A., Kirk, H. R., Quaye, J., Rastogi. C., Kiela, D., Jurado, D., Kan- ter, D., Mosquera, R., Cukierski, W., Ciro, J., Aroyo, L., Acun, B., Chen, L., Raje, M., Bartolo, M., Eyuboglu, E. S., Ghorbani, A., Goodman, E., Howard, A., Inel, O., Kane, T., Kirkpatrick, C. R., Sculley, D., Kuo, T.- S., Mueller, J. W., Thrush, T., Vansehoren, J., Warren, M., Williams, A., Yeung, S., Ardalani, N., Paritosh, P., Zhang, C., Zou, J. Y., Wu, C.-J., Coleman, C., Ng, A., Mattson, P., and Janapa Reddi, V. DataPerf: Benchmarks for data-centric AI development. In Advances in Neural Information Processing Systems, pp. 5320-53477 2023.
Rampásek, L.., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., and Beaini, D. Recipe for general, powerful, seal- able graph transformer. In Advances in Neural Informa- tion Processing Systems, 2022.
Randić, M. and Klein, D. Resistance distance. J. Math. Chem, 12:81-95, 1993.
Rathee, M., Funke, T., Anand, A., and Khosla, M. BAGEL: A Benchmark for Assessing Graph Neural Network Ex- planations, 2022. arXiv:2206.1 139833 [cs].
Riesen, K. and Bunke, H. IAM graph database repository for graph based pattern recognition and machine learning. In da Vitoria Lobo, N., Kasparis, T., Roli, F., Kwok, J. T., Georgiopoulos, M., Anagnostopoulos, G. C., and Loog, M. (eds.), Structural, Syntactic, and Statistical Pattern Recognition, pp. 287-297, 2008.
Michel, G., Nikolentzos, G., Lutzeyer, J., and Vazirgiannis, M. Path Neural Networks: Expressive and accurate graph neural networks. In International Conference on Machine Learning, 2023.
Sanmartín, E. F., Damrich, S., and Hamprecht, A. The algebraic path problem for graph metrics. In International Conference on Machine Learning, 2022.
Morris, C., Kriege, N. M., Bause, F., Kersting, K., Mutzel, P., and Neumann, M. Tudataset: collection of bench- mark datasets for learning with graphs. In Graph Rep- resentation Learning and Beyond Workshop at ICML, 2020.
Schomburg, I., Chang, A., Fbeling, C., Gremse, M., Heldt, C., Huhn, G., and Schomburg, D. BRENDA, the enzyme database: updates and major new developments. Nucleic Acids Research, 32:D431-D433 2004.
Morris, C., Frasca, F., Dym, N., Maron, H., Ceylan, I. I., Levie, R., Lim, D., Bronstein, M. M., Grohe, M., and Jegelka, S. Position: Future directions in the theory of graph machine learning. In International Conference on Machine Learning, 2024.
Sharma, K., Lee, Y.-C,, Nambi, S., Salian, A., Shah, S., Kim, S.-W., and Kumar, S. A survey of graph neural networks for social recommender systems. ACM Comput. 56(10), 2024.
Newman, M. Networks. Oxford University Press, 2018
Shervashidze, N., Schweitzer, P., van Leeuwen, E. J., Mehlhorn, K., and Borgwardt, K. M. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(77):2539-255 2011.
NIH National Cancer Institute, AIDS antiviral screen data, 2004.
12

---

No Metric to Rule them All: Toward Principled Evaluations of Graph-Learning Datasets
Simson, J., Pfisterer, F., and Kern, C. One model many scores: Using multiverse analysis prevent fairesss hack- ing and evaluate the influence of model design decisions. In ACM Conference on Fairness, Accountabiliry, and Transparency, pp. 1305-1320, 2024.
Wayland, J., Coupette, C., and Rieck, B. Mapping the multiverse of latent representations. In International Conference on Machine Learning, 2024.
Wu, Z., Ramsundar, B., Feinberg, E. N., Gomes, J., Ge- niesse, C., Pappu, A. S., Leswing, K., and Pande, V. Moleculenet: benchmark for molecular machine learning. Chem. Sci., 9:513-530, 2018a. doi: 10. 1039/C7SC026644,, URLhttp: /xx./xx/oo/// doi org/10. 1039/C7SC0266AM
Sonthalia, R. and Gilbert, A. Tree! I am no tree! am a low dimensional hyperbolic embedding. Advances in Neural Information Processing Systems, 33:845-856, 2020.
Sterling, T. and Irwin, J. Zine 15 ligand discovery for everyone. Journal of Chemical Information and Mod- eling, (5(11):2324-2337, 2015, doi: 10. 10.1021/acs.jcim 5b00559. URL https:://///.. /tt///oiiio//// 10t...0000...10//........ 1021/acc. jai m. 5b00559.
Wu, Z., Ramsundar, B., Feinberg, E. N., Gomes, J., Ge- niesse, C., Pappu, A. S., Leswing, K., and Pande, V. Moleculenet: a benchmark for molecular machine learn- ing. Chemical science, 9()):133-330 2018b.
Stokes, J. M.. Yang, K., Swanson, K., Jin, W., Cubillos- Ruiz, A., Donghia, N. M., MacNair, C. R., French, S.,
Xie, Y., Katariya, S., Tang, X., Huang, E., Rao, N., Sub- bian, K., and Ji, S. Task-agnostie graph explanations. In Advances in Neural Information Processing Systems, pp. 12027-12039, 2022.
Carfrae, L. A., Bloom-Ackermane Z., et al. A deep learning approach to antibiotic discovery. Cell, 180(4):
688-702, 2020.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks?, 2019. arX1v:1810.00826 [es].
Taha, D., Zhao, W., Riestenberg, J. M., and Strube, M. Normed spaces for graph embedding. Transactions on Machine Learning Research, 2023.
Yanardag, and Vishwanathan, S. Deep graph kernels. In Proceedings of the ACM SIGKDD International Con- ference on Knowledge Discovery and Data Mining, pp. 1365-1374 2015.
Tang. J., Zhang, W., Li, J., Zhao, K., Tsung, F., and Li, J. Robust attributed graph alignment via joint structure learning and optimal transport. In International Confer- ence on Data Engineering, pp. 1638-1651, 2023.
Yang. J., Liu, Z., Xiao, S., Li, C., Lian, D., Agrawal, S., Singh, A., Sun, G., and Xie, X. Graphformers: Gnn- nested transformers for representation learning on textual graph. In Ranzato, M., Beygelzimer, A., Dauphin, Y. N., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 28798- 28810, 2021.
Thang, D. C., Dat, T., Tam, N. T., Jo, J., Hung. Q. V., and Aberer, K. Nature vs. nurture: Feature vs. structure for graph neural networks. Pallern Recognition Letters, 159:46-53, 2022.
Tönshoff, J.. Ritzert, M., Rosenbluth, E., and Grohe, M. Where did the gap go? reassessing the long-range graph benchmark. In Learning on Graphs Conference, 2023.
Yang, M., Shen, Y., Li, R., Qi, H., Zhang, Q., and Yin, B. A new perspective the effects of spectrum in graph neural networks. In International Conference on Machine Learning, pp. 25261-25279, 2022.
Toyokuni, A. and Yamada, M. Structural explanations for Graph Neural Networks using HSIC, February 2023. arXiv:2302.02139 [es, stat].
Ying, R., He, R., Chen, K., Eksombatchai, P., Hamilton, W. L., and Leskovec, J. Graph convolutional neural net- works for web-scale recommender systems. In Proceed- ings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 974-983, 2018.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph attention networks. In International Conference on Learning Representations, 2018.
Zambon, D., Alippi, C., and Livi, L. Graph random neural features for distance-preserving graph representations. International Conference on Machine Learning, pp.
Wale, N. and Karypis, G. Comparison of descriptor spaces for chemical compound retrieval and classification. In International Conference on Data Mining, pp. 678-689, 2006.
10968-10977, 2020.
Zhao, W., Zhou, D., Qiu, X., and Jiang, W. A pipeline for fair comparison of graph neural networks in node classification tasks, 2020. MrXiv:2012.10611 [cs].
Wang, X. and Shen, H.-W. GNNInterpreter: A probabilis- tic generative model-level explanation for Graph Neural Networks, 2023.
13

---

[complete features] No Metric to Rule them All: Toward Principled Evaluations of Graph-Learning Datasets
Appendix
Definition 2.9 (Metric-Space Construction). For attributed graph (G, X) and metric d, we construct metric spaces
In this appendix, we provide the following supplementary materials.
La (G, X) - (V,d),
A. Extended Theory. Definitions, proofs, and results omit- ted from the main text.
i.e., lifts that take in either structure-based distances aris- ing from G or Peature-based distances arising from X and produce metric space over the node set V.
B. Extended Methods. Further details properties and parts of our RINGS pipeline.
C. Extended Dataset Descriptions. Extra details, statis- tics, and observations on the selected benchmarks. D. Extended Experiments. Additional details and experi- ments complementing the discussion in the main paper. E. Extended Related Work. Discussion of additional re- lated work.
A.2. Perturbations
For convenience in referencing theory, repeat definitions here:
Definition 2.1 (Mode Perturbation). A mode perturbation is map between attributed graphs such that yp: (G) + (G',''.
A. Extended Theory
Definition 2.3 (Structural Perturbations). Given an at- tributed graph (G, X) with edge set F,, we define:
A.1. Metric Spaces
Peg (G,X) + ((V, X),
[empty graph]
Here, we introduce metric spaces as well as various related notions that improve our understanding mode comple- mentarity.
Peg (G,X) - (V) )
xx
[complete graph]
Prg (G,X) + ((V, (E)).
[random graph]
Definition A.1 (Metric Space). A metric space is a tu- ple d) that consists of a nonempty set together with function d: Y Y > R which satisfies the axioms of metric, i.e., (i) d(a,, y) 2 0 for all 2; Y and d(x, y) 0 if and only a y, (ii) d(xx, y) d(y, æ), and (iii) d(z. v) S d(xx + d(z.y).
Here, Rs 2(()) 2(x) randomizes the edge set E. Definition 2.2 (Feature Perturbations). Given an attributed graph (G, X) nodes with features X C R we define:
Pet : (G, + (G, O,.)
[empty features]
Definition A.2 (Isometry). Given two metric spaces xX,dx) and (Y, isometry if dy (f(x), f(y)) dx(x,)) y) for all æ, y X.
Per : (G, + (G, I,) Pr X) + Rr
call function f: X + Y
[random features]
Definition A.3 (Trivial Metric Space). We define trivial metric space as any metric space dY. in the equivalence class of {x} (the single point space) under isometry. In particular, this corresponds to any finite space paired with metric d such that d(æ,, y) for all v, y. For finite spaces of size n, we represent this as the n x n matrix of zeros, O,,-
Here, Rp Raxk k + R'* randomizes the features X. Definition A.5 (Randomization Methods). Assume we have nodes in (G, X). Let S - +S be permutation over ordered set.
(X, k) + {x: ~ ~N(00, (X) = T(X)
[random features]
Definition A.4 (Discrete Metric Space). A metric space (Y, d) is discrete metric space if satisfies
[shuffled features]
(s,) ER(n,,)
[random graph)
(G) = (V, (V))(E))
[shuffled graph]
[1. if +
d(r.v) 1 [1000 otherwise
(12)
where ER(n, p) represents an
model, ensuring that each edge (u, v) E (K) is included in independently with probability p.
For finite spaces of size n, represent this as the x n matrix of all ones with zero diagonal, 1, I, Note that when normalizing non-degenerate spaces to unit diameter, the discrete metric space is one where all non-equal elements are maximally distant from each other, (c.g. a complete graph).
A.3. Complementarity
Definition 2.10 (Perturbed Metric Space). Given an at- tributed graph (G, X) and an associated metric d, the y- perturbed metrie space of X) under
We go from attributed graphs to metric spaces using the lift construction presented in the main paper, restated here for completeness.
D = La o XG,
(4)
which we construe as a distance matrix.
14

---

No Metric to Rule them All: Toward Principled Evaluations of Graph-Learning Datasets
1. COMPARATORS
Proef. (+ = n) By Definition 2.2, we have Pet Per
O,). Since O, is isometric to fx), any metric must lift {x} to trivial metric space (by metric-space axiom (ii)..
Definition A.6 (nn Norm). For an X pairwise distance matrix D representing finite metric space (Y, d), we define the Lp.g norm
(* g) For structural metrics ds. we restrict to those derived from the adjacency matrix A of G. By convention, (V, 0) is represented as O,, Hence, an identical argument holds mutatis mutandis, as any metric derived from the zero matrix lifts to a trivial metric space.
4/p 1/9
Ei= (-=1(d(())) nnn - 1)
(13)
Definition 2.11 (Metric-Spacee Sprrii Comparison). For a fixed set of n points and two metrics dl and d', we compare the metric spaces that arise from and d' by computing the Lp.a norm of the difference of their n matrix representations, i...,
Lemma A.9 (Complete Perturbations Lift to Discrete Metric Spaces), Let (G, X) be an attributed graph. For any choice of dz, the image of La. as defined in Definition 2.9 under precomposition with Ses a discrete metric space, for {f.g).
(D, Da)= [aa - Darllpa
(5)
2
Proof. () By Definition 2.2, we have (e, I,). The identity matrix I, consists of standard basis vectors e, (i.e., the not encodings of nodes). We claim that any metric dr over I, must be discrete.
Definition 2.12 (Mode Complementarity) Given an at- tributed graph (G with structural metric dg, derived from G. and feature metric dp, derived from X, we define the mode complementarity of X) as
Toward a contradiction, assume otherwise. W.I.o.g., sup- pose the metric space is scaled to unit diameter, imply- ing that there exist i, such that (p(e,, e,) < 1. Since (In, dp) is uniform, is invariant under orthogonal transfor- mations, meaning we can permute the standard basis vectors while preserving distances. Thus, for all k * i, we have dr(e,, = dr(ez, ez) < 1, contradicting our assumption. Therefore, de (2, = 1 for all x + y. proving discreteness.
',, Cp. (Ds,
(6)
where C is comparator from Definition 2.11,
Dg = D D// /iam (Ds) for Ds = Las (G, X),
DF := Dp////innnn /a///daaapppp (pp) for Dp== Lap (G, X);
using the lifts from Definition 2.9, and we leave (degenerate) zero-diameter spaces unchanged.
(* = g) Here, XG. = (2). The edge set consists of all two-element subsets of V. forming fully connected graph. Similar to Lemma A.8, we restrict to metrics defined over the adjacency matrix A of G. By construction, A = 1,, - In, which has the same structure as I, under the isometry f : 24 + e,. Since all elements are maximally distant, any metric ds must lift to a discrete space.
A.3.2. COMPLEMENTARITY UNDER PERTURBATION
Definition 2.13 (Perturbed Mode Complementarity) Given an attributed graph (G, X) and a mode perturbation şo, the mode complementarity of ()) is
709 u X) (D3,
Definition A.7 (Complementarity for Disconnected Graphs). For disconnected attributed graph X) with nodes and C' connected components, we write G as union UG,- Let X Xlv, denote the subset of features corresponding to nodes in G; = (V, E.). We define the complementarity for disconnected graphs as the weighted average of the individual component scores
Theorem 2.15 (Perturbation Duality). Fix an attributed graph X) and corresponding distances dg for lift- ing each mode into a metric space. For * E (f.g), Defini- tion 2.12 of y yields the equivalence
Von (G, = - - (G,
(1I)
(G, = Σ T4 (G, n
Proof.
(14)
1.1 Teg (G, [,, X)
2.13 CI, Pox ,Dds)
where n, = IVgl. Axiom (ii) in Definition A.1, implies that isolated nodes then assigned trivial metric space.
Lem. A.9 C1.1 - -I, Day)
Lemma A.8 (Empty Perturbations Lift to Trivial Metric Spaces). Let (G, be an attributed graph. For any metric d., the image of La. as defined in Definition 2.9 under precomposition with Pex is a trivial metric space, for * E (f.g).
Def.
[[1nn - -In) - Dar 111,1
Def. A.6
1
n n
1 dr(i.
n² - n
#
15

---

No Metric to Rule them All: Toward Principled Evaluations of Graph-Learning Datasets
similarity measures are already known, such as graph ker- nels (Borgwardt et al., 2020; Kriege et al., 2020), graph edit distances (Gao et al., 2010), distance metrics on R The dashed arrows show our ability to study complementarity and selffcoomlementtriiy using metric spaces and principled mode perturbations.
11
n2
n2
11
n1
dr(i.))
i=1
Def. 118())
1
dF (1,5)
n12 n
i=1 ==1
Def. A.6
1-
|1appl1.
B.2. Metric Choices
Def. 2.13,LLm Lcm A.8
1- (G, X)
1.1
As outlined in Section 2.3, we would like to understand, for a given attributed graph (G, X) the complementarity between the information in the graph structure and the node features. Thus, we use (G, X) to score the difference in geometric information contained in the two modes. As per Definition 2.12, this requires choice of structural metric (ds) and feature metric (dp), which facilitate lifting the modes into metric space.
symmetrical argument can be applied to Yef 1.1 the proof.
concluding
Definition 2.14 (Mode Diversity). Given an attributed graph (G. the mode diversity of (G, X) for E {f.g} is
X)) = = 1- 11-11112 2 2 (G, X)| [0, (10)
Proposition A.10 (Seff-Complementarty))) Let dg and dr be metrics over the modes of an attributed graph (G,X). We define (Peg: dr) and (Pet, dg)) as dual pairs that can be used analyze the col-complemennarity of a single mode. By construction, for (f.g), we have:
While our experimental results are based on diffusion dis- tance as our structural distance metric (ds) and Euclidean distance in R our feature-based distance metric (dp), it is worth noting that the RINGS framework generalizes to other distance metrics. Below, we define the diffusion distance and Euclidean distance, as well as several other distance metrics suitable for the RINGS framework. To build intuition, we additionally depict the behavior of different graph-distance candidates under edge addition on toy data in Figure 6 and illustrate the interplay between metric choices for the
Lo (G 2 On
(15)
Thus, the complementarity under emply perturbations, P.4. measures the internal structure of the nonzero dual mode:
1
Peptides dataset in Figure 7.
Yex (G,
-I. llp.q.
(16)
V
B.2.1. STRUCTURAL METRICS
Due to the normalization, we obtain TEe (G, X) [0, 1]. The limiting behavior of (G, X), then, provides insights into the underlying metric structure of the dual mode:
Disconnected Graphs Here we define the metrics we use to lift a graph structure into a metric space. Although common practice assigns an infinite distance between uncon- nected nodes, due to our treatment of disconnected graphs in Definition A.7, we only lift metric spaces within con- nected component. Our treatment of isolated nodes assigns trivial metric spaces to each node, and their union we also treat as trivial as seen in Lemma A.8.
(1) If P: X) -+ then d, (Ix y) = 0 for all x. y.
(2) If Ter 2 XG + then d, (I. 3) 1 for all x + y.
B. Extended Methods
B.1. Mode Complementarity
Definition B.1 (Laplacian Variants), We define the Lapla- cian of G (V, E) as
The perturbations introduced with our RINGS framework are specifically designed to disentangle the relationship be- tween the structural mode and the feature mode of X). Unlike existing methods, RINGS allows us to leverage the relationships both between and within individual modes:
L D-D-A,
(17)
where is the n x n adjacency matrix specified by F, and D) is the degree matrix. We also define normalized Laplacian
G G
G
i -= D=D-1/22D-12
(18)
where D-1/2 diag
1 VDJ,
t X
Definition B.2 (Diffusion Distance [ds.] (Coifman & Lafon, 2006)), We define our distance over G' for diffusion steps
Here, all arrows indicate the calculation of potential simi- larity measures. Solid arrows describe settings for which
as
ds, (x. y) [[,.()) Ve(v))l
(19)
16

---

No Metric to Rule them All: Toward Principled Evaluations of Graph-Learning Datasets
0.7
Complementarty
ds
Diffusion
0.5
Heat Kernel
Resistance
Shortest Path
0.3
0.2
0.6
1.0
0.2
0.6
1.0
0.2
0.6
1.0
0.2
0.6
1.0
0.2
0.6
1.0
Density
Figure 6: Mode complementarity under different graph distances and varying density. We show the evolution of mode complementarity for 5 graphs on 10 nodes with normally distributed one-dimensional features as we randomly add edges to increase the density from the minimum for a connected graph (0.2) to the maximum (1.0), for different choices of graph distance ds. For the diffusion distance and the heat-kernel distance, which depend on the parameter t, we show the complementarity 1. The diffusion distance exhibits the smoothest behavior.
Complementarity
1.0
ds Diffusion
Finally, the heat-kernel distance between nodes and time t is then computed as:
Heat Kernel
0.5
Resistance
Shortest Path
he(u, v) Σ exp (A)
(21)
0.0
Cosine
Euclidean
Definition B.4 (Resistance Distance (Randić & Klein, 1993)). Given graph G with nodes, the resistance dis- tance between nodes u and v is given as:
dp
Figure 7: Real-world mode complementarity under dif- ferent graph distances ds and feature distances de. We show the 95th percentile of the conpeeermlle dis- tribution for the Peptides dataset, for varying combinations of graph distance dg and feature distance dy, using i for the t-dependent distances (diffusion and heat kernel).
Qu = Ais + Ag. - Ars AJa
(22)
where
A L
1,
with denoting the Moore-Penrose pseudoinverse.
where (1 } is family of diffusion maps computed from the spectrum of T.. particular,
Definition B.5 (Shortest- Path Distance). For a graph G (V, F), we define the shortest-pas distance between two nodes u, as the minimum number of edges any path between and
A (x)
V, (x:) A
B.2.2. FEATURE METRICS
(a)a(a))
Definition B.6 (Euclidean Distance [dp]). Given our fea- ture space C R let x, E IR* be two arbitrary feature vectors. Then the Euclidean distance (also known as the L2 norm) between x and y is defined as
where 7; bi are the tth eigenvalue and eigenvector of Z. Definition B.3 Heaat-Keree Distance (Bai & Hancock, 2004)). To compute the heat-kernel distance between nodes in graph G, we take the spectral decomposition of f. as
dr v)
Σ
(a y1)
(23)
ī= WAYT Σ A
(20)
Definition B.7 (Cosine Distance). Given a feature space X R let x, y Re be two arbitrary feature vectors. Then the cosine distance between æ and y defined as
where is the diagonal matrix with ordered eigenvalues and = (V1, 122, ..., t..) is the matrix with columns cor- responding to the ordered eigenvectors. The heat equation associated with the graph Laplacian, written in terms of the
d(z,y) = ||a ||
(24)
heat kernel h, and time f, is defined
Oh,
where x y is the dot product and y, and ||x|| is the L2 norm of x.
-Îhe
Øt
17

---

No Metric to Rule them All: Toward Principled Evaluations of Graph-Lcarning Datasets
C. Extended Dataset Descriptions
C.1.2. SOCIAL MEDIA
As we seek to evaluate the datasets in their capacity as graph-learning benchmarks, the formulation and properties of these datasets are worth detailed discussion. We summa- rize the basic statistics of these datasets in Table 3 and now describe the semantics and special characteristics of each dataset in turn.
We study two graph-learning datasets with origins in so- cial media: REDDIT-B and REDDIT-M (Yanardag & Vish- wanathan, 2015).
In the these datasets, a graph models a thread lifted from a subreddit (i.e., a specific discussion community). Nodes represent Reddit users and edges connect users if at least one of them has replied to comment made by the other (i.e., the users have had at least one interaction). Like COLLAB and IMDB, node features are constructed from the node degree. However, the REDDIT datasets score better on both structural and feature diversity (see Table 2). REDDIT's higher structural diversity reflects the fact that its graphs are not ego-networks. Its more complex graph structures also account for the higher diversity in node features (i.e., node degrees).
C.I. Social Sciences
C. 1.1.1. PROFESSIONAL COLLABORATIONS
In professional collaboration networks, nodes represent in- dividuals and edges connect those with a direct working relationship.
COLLAB (Yanardag & Vishwanathan, 2015) is a dataset of physics collaboration networks, where nodes represent physics researchers and edges connect co-authors. Graphs constructed as ego-networks around central physics researcher, whose subfield (high energy physics, condensed matter physics, or astrophysics) acts as the classification for the graph as a whole. The data to build these graphs is drawn from three public collaboration datasets based on the arXiv (Leskovec et al., 2005).
The REDDIT-B dataset draws from four popular subred- dits, two of which follow a Q&A structure (IAmA, AskRed- dit) and two of which are discussion- based (TrollXChromo- somes, atheism). The task is to classify graphs based on these two styles of thread. REDDIT-M graphs are drawn from five subreddits, which also act as the graph class (worldnews, videos, AdviceAnimals, aww and mildlyinter- esting).
Following a similar construction, the IMDB (Yanardag & Vishwanathan, 2015) datasets capture collaboration in movies. Graphs represent the ego-networks of actors and actresses, and edges connect those who appear in the same movie. The graph is classified according to the genre of the movies from which these shared acting credits are pulled. The task to predict this genre, a binary classification be- tween Action and Comedy in IMDB-B, and a multi-class classification between Comedy, Romance, and Sci-Fi in IMDB-M. (Note that genres are engineered to be mutu- ally exclusive.) As one might expect, we note in Figure 3 the lower GNN performance for IMDB-M as compared to IMDB-B, B, suggesting that the multi-class graph classification a more challenging task.
Similar to the difference between the IMDB binary and multi-class datasets, we observe better GNN performance on the REDDIT-B benchmark as compared to REDDIT-M (see Figure 3), despite the fact that REDDIT-M boasts more than twice as many graphs (see Table 3).
C.2. Life Sciences
C.2.1. MOLECULES AND COMPOUNDS
Graphs provide an elegant way to model molecules, with nodes representing atoms and edges representing the chemi- cal bonds between them.
The AIDS dataset (Riesen & Bunke, 2008), for example, is built from repository of molecules in the AIDS Antiviral Screen Database of Active Compounds (NIH National Can- cer Institute, 2004). Nodes have four features (Morris et al., 2020), most notably their unique atomic number. This is binary-classificatio dataset in which molecules are clas- sified by whether or not they demonstrate activity against the HIV virus. Among the 2 200 graphs in this dataset, note that the two classes are imbalanced: there are four times as many inactive molecules (1 600) as active (400). The Mol- HIV moolg-) dataset, introduced by the Open Graph Benchmark (Hu et al., 2020) with over 40,000 molecules from MoleculeNet (Wu et al., 2018b), proposes a similar task. Like AIDS, MolHIV classifies molecules into two classes based on their ability or inability to suppress the
COLLAB and IMDB datasets share two notable features that distinguish them from the remaining datasets. First, graphs are constructed as ego-networks. This means that they have a diameter of at most two, in stark contrast to more structurally complex graphs from other datasets. This lends insight into why COLLAB and IMDB are classified as having low structural diversity (see Table 2). Second, node features are constructed from the node degree, rather than providing new information independent of graph structure. Thus, the low diversity scores with high variability that we see in Table 2 are simply a reflection of the node-degree distributions in these datasets.
18

---

No Metric to Rule them All: Toward Principled Evaluations of Graph-Learning Datasets
n
m
6
P
711
YYo
N
j
0
0
JA
0
Dataset
AIDS
2000
15.69
13.69
32.39
30.02
2.01
0.20
0.19
0.08
0.29
0.08
0.28
0.06
COLLAB
5000
74.49
62.31
4914.43
12879.12
37.37
43.97
0.51
0.30
0.40
0.27
0.64
0.21
DD
1178
284.32
272.12
1431.32
1388.40
4.98
0.59
0.03
0.02
0.33
0.04
0.80
0.06
Enzymes
600
32.63
15.29
124.27
51.04
3.86
0.49
0.16
0.11
0.49
0.07
0.26
0.05
IMDB-B
1000
19.77
10.06
193.06
211.31
8.89
5.05
0.52
0.24
0.49
0.23
0.53
0.20
IMDB-M
1500
13,00
8.53
131.87
221.63
8.10
4.82
0.77
0.26
0.73
0.30
0.75
0.28
MUTAG
188
17.93
4.59
39.59
11.40
2.19
0.11
0.14
0.04
0.51
0.07
0.48
0.02
MolHIV
41127
25.51
12.11
54.94
26.43
2.14
0.11
0.10
0.04
0.42
0.11
0.33
0.08
NCTI
4110
29.87
13.57
64.60
29.87
2.16
0.11
0.09
0.04
0.54
0.05
0.51
0.03
Peptides
10873
151.54
84.10
308.54
171.99
2.03
0.04
0.02
0.02
0.38
0.09
0.26
0.04
Proteins
1113
39.06
45.78
145.63
169.27
3.73
0.42
0.21
0.20
0.45
0.04
0.26
0.06
Reddit-B
2000
429.63
554.20
995.51
1246.29
2.34
0.31
0.02
0.03
0.47
0.03
0.45
0.08
Reddit-M
4999
508.52
452.62
1189.75
1133.65
2.25
0.20
0.01
0.01
0.48
0.02
0.43
0.07
Table 3: Basic statisties of our 13 evaluated graph-learning datasets. We show the number of graphs (N) well the mean and standard deviation of the number of nodes (r), the number of edges (m)) the degree (6), the density (p), and mode complementarity at t E {1, 10} (7,, 710).
HIV virus. However, nodes in the MolHIV dataset have 9 features (compared to AIDS), including atomic number, chirality, and formal charge.
C.2.2. LARGER CHEMICAL STRUCTURES
The Peptides (Peptides-fnnce dataset (Dwivedi et al., 2022) classifies peptides by their function. Each graph represents peptide (i.e., a 1D amino acid chain), with nodes represent- ing heavy (non-hydrogen) atoms and edges representing the bonds between them. Peptides is multi-labe--lassificattio dataset, meaning that each peptide may belong to more than one of the 10 function classes (Anribacterial, Antiviral, cell-cell communication, etc.), with the average being 1.65 classes per peptide. Given the complexity of this task, is perhaps unsurprising to notice that our tuned GNNs achieve
MUTAG (Debnath et al., 1991) is relatively small molecu- lar dataset compared with its peers, having only 188 graphs (Morris et al., 2020). However, it does have a similar number of node features (7). Graphs represent aromatic or heteroaro- matic nitro compounds, which are divided into two classes by their mutagenicity towards the bacterium ryphimurium, i.e. their ability to cause mutations its DNA. While small, the dataset contains "extremely broad range of molecular structures" (Debnath et al., 1)91), which see reflected in a decent structural-diversity score in Table 2.
the lowest AURUC on this dataset (see Figure 3).
DD, ENZYMES, and Proteins (Proteins-full) are all protein datasets. Each dataset draws upon the framework introduced by (Borgwardt et al., 2005) to model 3D structures of folded proteins as graphs, with nodes representing amino acids and edges connecting amino acids within a given proximity measured in Angstroms. Both the Proteins-full database introduced by (Borgwardt al., 2005) and the DD database used by (Shervashidze et al., 2011) are based data from Dobson & Doig (2003), which classifies 1 178 proteins as either enzymes (59%) or non-enzymes (41%). Thus, these two datasets are binary-classification datasets.
When introducing the dataset, Debnath et al. (1991) found that both specific sets of atoms and certain structural features (namely the presence of or more fused rings), tended to be fairly well correlated with increased mutagenicity. This biologically supports that both modes could be informative, which is generally encouraging for lraph-learning datasets. Thus, although we do not observe the desired performance separability in Figure 3, we cannot rule out that MUTAG could be a good benchmark, given a different task.
NCII (Wale & Karypis, 2006) is binary-classffictinn dataset that splits molecules into two classes based whether or not they have inhibitary effect on the growth of human lung-cancer cell lines. Nodes have 37 features, a significant step up from other molecular datasets, which reflected in the richness of NCI/'s feature diversity (see Table 2).
Proteins-full only uses 128 of the 1 1778 proteins from Dobson Doig (2003) but encodes 29 descriptive node features, whereas DD encodes none (Kersting al., 2016; Morris et al., 2020). This distinction is responsible for Proteins-full's drastically higher feature diversity score and standard deviation, as seen in Table 2.
ENZYMES (Borgwardt et al., 2005) introduces a multi-class classification task on enzymes. Graphs represent enzymes from the BRENDA database (Schomburg al., 2004).
19

---

No Metric to Rule them All: Toward Principled Evaluations of Graph-Learning Datasets
Aspect
Details
Parameter
Values
Architectures
[GAT, GCN, ]
Activation
ReLU
Mode Perturbations
(Po Peg. Pegz Pat: Pest Peg.
Batch Size
{64, 128}
Tuning Strategy
5-fold CV x 64 consistent / for each (io(D),
Dropout
{0.1, 0.5}
Selection Metric
Validation AUROC
Fold
{0. 1, 3,
Evaluation Strategy
Tuned model (+(D), .A, 6) re-trained on distinct CV splits and random seeds, then evaluated on c(D)'s 's test set.
Hidden Dim
(128. 256]
Learning Rate (IR)
{0.01, 0.001)
Max Epochs
200
Normalization
Batch
Table 4: GNN setup to evaluate performance separability. Parameter combinations are specified in Table 5. Prg (D) perturbations were trained using a RF (-, 10) randomiza- tion. The top performing parameter combination 8* was selected based on validation statistics: primarily based on AUROC, with ties broken by accuracy and then loss.
Num Layers
3
Optimizer
Adam
Readout
Sum
Seed
42)
Weight Decay
{0.0005, 0.005}
Table 5: GNN tuning parameters. For consistency, all (p((), A) were tuned across a consistent hyperparameter grid search.
which are classified according to the 6 Enzyme Commis- sion top-level enzyme classes (EC classes). The dataset is roughly half the size of DD and Proteins-full, with only 600 enzymes (100 from each class). There are 18 node features, producing the high feature diversity observed in Table 2.
dependent on a specific architecture, we were limited in the number of GNN models that we could train and eval- uate over all of our datasets and their perturbations. As our goal is evaluate the intrinsic quality of datasets as graph-learning benchmarks, we more concerned with consistency across experiments than with using the newest methods, especially given finite computational resources.
C.3. Further Information
Several efforts have been made to consolidate information about the aforementioned datasets and their peers. In par- ticular, we direct the interested reader to the TUDataset documentation (Morris et al., 2020), TU Dortmund's s Bench- mark Data Sets for Graph Kernels (Kersting et al., 2016), and PyTorch Geometric (Fey & Lenssen, 2019).
In accordance with other "evaluation of evaluations" studies (Bechler-Speicher et al., 2024; Li et al., 2024), we opted to use several of the most common GNN architectures, namely GCN (Kipf & Welling, 2017), GAT (Veličković et al., 2018), 8), and GIN (Xu et al., 2019). As noted by Li et al. (2024), GCN and GIN provide good contrast in methodology, with GCN taking spectral approach and GIN taking a spatial approach.
D. Extended Experiments
D.1. Extended Setup
With the RINGS framework, we introduce principled pertur- bations to graph learning datasets that allow us to evaluate the extent to which graph structure and node features are leveraged in given task (performance separability) and to what extent the information in these modes complemen- tary redundant (mode complementarity). We do so with series of experiments, which we expand upon below.
For each (dataset, perturbation, architecture) triple, we tune the GNN hyperparameters as outlined in Table 4, using the tuning parameters (6) stated in Table 5. The mean and standard deviation of accuracy and AUROC for our tuned models are tabulated in Table 6 and Table 7, respectively.
D.2.2. PERFORMANCEE-SPPAABIIIII RESULTS
D.2. Extended Performance Separability
Reasoning from first principles, we assert that the most in- structive graph-learning datasets should have a separable original mode. In other words, we would like both the fea- tures and the graph structure to be informative and necessary to solve given task. When perturbed mode either outper- forms or is non-separable from the original, then we can say that the perturbed mode is non-essential for the task at hand.
We begin with a note on the chosen GNN architectures, before examining and supplementing the results of our per- formance separability evaluations.
1.2.1. A NOTE ON GNN ARCHITECTURES
By far the most computationally expensive part of our ex- periments tuning GNNs. While variation in the GNN models desirable to ensure that our results are not overly
Consider the Accuracy and AUROC columns of Table 1. (Overall we find AUROC be more expressive in determin-
20

---

No Metric to Rule them All: Toward Principled Evaluations of Graph-Learning Datasets
|
0
Datasct
0
cg
cg
eg
cg
cf
cf
rf
rf
AIDS
GAT
0.980
0.006
0.968
0.017
0.977
0.007
0.968
0.011
0.998
0.002
0.320
0.075
GCN
0.982
0.005
0.950
0.016
0,983
0.004
0.837
0.058
0.997
0.003
0.340
0.051
GIN
0.986
0.004
0.996
0.003
0,981
0.005
0.991
0.004
0.998
0.003
0.597
0.052
COLLAB
GAT
0.821
0.009
0.798
0.008
0.753
0.013
0.797
0.009
0.675
0.019
0.647
0.013
GCN
0.827
0.009
0.798
0.008
0.753
0.014
0.790
0.009
0.705
0.018
0.712
0.012
GIN
0.797
0.021
0.768
0.028
0.743
0.015
0.769
0.022
0.712
0.018
0.696
0.021
DD
GAT
0.580
0.085
0.747
0.029
0.598
0,086
0.696
0.090
0.721
0.045
0.579
0.049
GCN
0.691
0.028
0.746
0.032
0.678
0.057
0.767
0.025
0.731
0.022
0.606
0,014
GIN
0.683
0.037
0.601
0.073
0.670
0.050
0.594
0.074
0.710
0,030
0.597
0.018
Enzymes
GAT
0.470
0.054
0.415
0.065
0.530
0.044
0.406
0.053
0.414
0.044
0.173
0.032
GCN
0.563
0.036
0.566
0.033
0.615
0.029
0.448
0.041
0,410
0.038
0.169
0.035
GIN
0.572
0.058
0.332
0.068
0.607
0.094
0.338
0.062
0.400
0.048
0.182
0.029
IMDB-B
GAT
0.719
0.027
0.725
0.042
0.712
0.024
0.699
0.029
0.649
0.035
0.540
0.032
GCN 0.732
0.033
0.719
0.039
0.716
0.022
0.704
0.025
0.692
0.024
0.606
0.034
GIN
0.724
0.034
0.706
0.034
0.704
0.025
0.710
0.029
0.688
0.034
0.695
0.045
IMDB-M
GAT
0.493
0.023
0,489
0.017
0,478
0,028
0,489
0,019
0.431
0.029
0.349
0.026
GCN
0,504
0.021
0.484
0.018
0.496
0.015
0.487
0.018
0.451
0.026
0.383
0.021
GIN
0.475
0.047
0.476
0.032
0.484
0.025
0,489
0.019
0.452
0.031
0.398
0.041
MUTAG
GAT 0.707
0.051
0.677
0.083
0.667
0.042
0.688
0.038
0.755
0.087
0.624
0.079
GCN
0.718
0.044
0.710
0.081
0.733
0.061
0.756
0.061
0.842
0.075
0.625
0.059
GIN
0.767
0.140
0,814
0.068
0.707
0.056
0.801
0.068
0.821
0.078
0,689
0.042
MolHIV
GAT
0.962
0.003
0.653
0.151
0.964
0.001
0.955
0.005
0.966
0.001
0.965
0.001
GCN 0.967
0,002
0.966
0.001
0.963
0.002
0.966
0.001
0.965
0.001
0.965
0.001
GIN
0.968
0.002
0.965
0.001
0.963
0.001
0.965
0.002
0.965
0.001
0.965
0.001
NCII
GAT
0.562
0.056
0.580
0.037
0.506
0,004
0.575
0.031
0.666
0.014
0.500
0.001
GCN
0.720
0.019
0.664
0.012
0.563
0.022
0.639
0.014
0.670
0.013
0.501
0.002
GIN
0.769
0.016
0.681
0.030
0.561
0.019
0.648
0.011
0.667
0.015
0.548
0.039
Peptides
GAT
0.604
0.104
0.297
0.155
0.418
0.222
0.410
0.164
0,582
0.014
0.515
0.000
GCN
0.671
0.006
0.673
0.008
0.651
0.007
0.633
0.013
0.610
0.010
0.515
0.000
GIN
0.681
0.008
0.661
0.008
0.653
0.008
0.659
0.007
0.570
0.046
0.520
0.014
Proteins
GAT
0.600
0.01S
0.620
0.038
0.599
0.007
0.614
0.034
0.723
0.024
0.610
0.015
GCN
0.597
0.006
0.627
0.033
0.603
0.023
0.595
0.006
0.714
0.024
0.607
0.011
GIN
0.603
0.011
0.601
0.049
0.601
0.012
0.622
0.046
0.701
0.034
0.606
0.011
Reddit-B
GAT
0.730
0.029
0.595
0.080
0,520
0,032
0.678
0.061
0.700
0.064
0.518
0.024
GCN
0.781
0.018
0.742
0.026
0.540
0.050
0.794
0.023
0.823
0.019
0.580
0.039
GIN
0.699
0.109
0.564
0.038
0.693
0.107
0.699
0.085
0.561
0.087
R
GAT
0.422
0.021
0.331
0.060
0.307
0.097
0,284
0.039
GCN 0.472
0,017
0.446
0,026
0.497
0.013
0.454
0.018
GIN 0.474
0.027
0.420
0.041
0.422
0,051
0.501
0.042
Table 6: Accuracy of tuned perturbed models underlying our performance-spaarabllty computations. For Reddit-M, the complete- graph and complete-feature perturbations failed train due to memory problems. For Reddit-B, GIN failed for similar reasons.
ing separability, but we include both in our classifications.) Note that when training on PPg. we are removing any struc- tural information. Comparing the performance of 'Peg to that of the original, we can determine whether or not the structural information is being used at all. For example, for the ENZYMES dataset, we see that eg > o, which implies that the graph structure is unnecessary for solving the cur- rent classification task. Conversely, we have some tasks for which only the structural mode is essential. MUTAG is one example where ef and o are not separable, implying that node features are not essential and the task can be completed based on the graph structure alone. Given their dependency on graph mode, we would consider this type of dataset
interesting for structural tasks, but we would prefer bench- marks that combine structural and feature information.
Moving on to the Structure and Feature columns of Table 1, we formalize the notion of whether or not each mode is informative for each dataset and associated task. Let us con- sider the structural perturbations (Φeg. Pro- 2 and the performances of their tuned models. If the perturbed model performances are separably lower than the original. then we can classify the structure as informative (e.g., COLLAB). Similarly, turning to feature perturbations ( Φr and their associated performances, if the perturbed model per- formances are separably lower than the original, then the features are considered informative (e.g. ENZYMES). In
21

---

No Metric to Rule them All: Toward Principled Evaluations of Graph-Learning Datasets
07
0
/4
07
0
Datasct
0
cg
cg
cg
rg
cf
cf
rf
rf
AIDS
GAT
0.984
0.012
0.985
0.011
0.981
11981-
0.010
0.984
0.010
0.994
0.008
0.829
0.141
GCN
0.986
0.010
0.954
0.020
0,986
0.009
0.982
0,011
0.995
0.006
0.874
0.055
GIN
0.987
0.011
0.991
0.011
0,684
0,010
0.994
0.006
0.994
0.008
0,813
0.160
COLLAB
GAT
0.945
0.005
0.929
0.004
0,905
0.003
0,929
0.003
0.828
0.015
0.824
0.010
GCN
0.949
0.004
0.929
0.003
0.905
0.003
0,926
0.003
0.847
0.013
0.877
0.008
GIN
0.926
0.022
0.906
0.034
0.897
0.007
0.908
0.023
0.855
0.013
0.858
0.017
DD
GAT
0.642
0.163
0.801
0.029
0.720
0.198
0,766
0.126
0.773
0.030
0.703
0.113
GCN
0.749
0.028
0.797
0.034
0.770
0.072
0,830
0.026
0.763
0.021
0.762
0.024
GIN
0.762
0.053
0.755
0.120
0.769
0.044
0.733
0.130
0.751
0.038
0.747
0.059
Enzymes
GAT
0.767
0.033
0.729
0.044
0.797
0.022
0.729
0.033
0.730
0.028
0,513
0.032
GCN
0.816
0.017
0.811
0.020
0.829
0.017
0.758
0.025
0.718
0.025
0.505
0.030
GIN
0.828
0.032
0.671
0.047
0.840
0.053
0.682
0.044
0.722
0.033
0.534
0.031
IMDB-B
GAT
0.811
0.030
0.822
0.036
0.803
0.025
0.791
0.026
0.694
0.035
0.561
0.037
GCN
0.837
0.028
0.821
0.037
0.803
0.023
0.793
0.026
0.741
0.037
0.644
0.042
GIN
0.811
0.040
0.795
0.039
0.789
0.026
0.798
0.030
0.742
0.036
0.759
0.053
IMDB-M
GAT
0.687
0.024
0.673
0.0T9
0.668
0,022
0.683
0,020
0.597
0.022
0.527
0.023
GCN
0.704
0.020
0.668
0.019
0.684
0.021
0.679
0.020
0.623
0.029
0.566
0.019
GIN
0.671
0.037
0.658
0.027
0.674
0.018
0.677
0.019
0.623
0.028
0.594
0.036
MUTAG
GAT
0.836
0.063
0.761
0.119
0.867
0.081
0.840
0.062
0.898
0.062
0.618
0.110
GCN
0.846
0.048
0.744
0.075
0.814
0.068
0.825
0.058
0.908
0.066
0.585
0.092
GIN
0.874
0.155
0.874
0.067
0.814
0.075
0.865
0.048
0.882
0.078
0,838
0.079
MolHIV
GAT
0.689
0,016
0.633
0.048
0.452
0.022
0.654
0.019
0.685
0.023
0.359
0.017
GCN
0.726
0,014
0.630
0.011
0.588
0.007
0.645
0.016
0.691
0.028
0.361
0.018
GIN
0.777
0,013
0.696
0.022
0.590
0.019
0.646
0.023
0.670
0.028
0.409
0.028
NCII
GAT
0.572
0.135
0.680
0.051
0.679
0.017
0.664
0.065
0.727
0.016
0,683
0.016
GCN
0.797
0.017
0.735
0.013
0.647
0.029
0.685
0.017
0.731
0.017
0.648
0.022
GIN
0.843
0.014
0.741
0.031
0.640
0.034
0.701
0.022
0.722
0.016
0.656
0.024
Peptides
GAT
0.553
0.042
0.401
0.069
0.444
0.093
0.446
0.065
0,548
0.006
0.401
0.006
GCN 0.582
0.004
0.596
0.006
0.561
0.008
0.580
0.006
0.549
0.008
0,400
0.007
GIN
0.591
0.005
0.571
0.012
0.565
0.004
0.573
0.007
0.536
0.008
0,447
0.027
Proteins
GAT
0.775
0.018
0.752
0.042
0.786
0.016
0.764
0.035
0.758
0.022
0.720
0.030
GCN
0.782
0.021
0.782
0.027
0.773
0.028
0.780
0.024
0.758
0.027
0.730
0.031
GIN
0.782
0.028
0.735
0.092
0.736
0.061
0.751
0.046
0.742
0.034
0.765
0.032
Reddit-B
GAT 0.798
0.022
0.763
0.049
0.749
0.148
0.740
0.088
0.721
0.082
0.624
0.178
GCN
0.846
0.014
0.817
0.019
0.639
0.195
0.875
0.016
0.862
0.015
0.797
0.040
GIN
0.748
0.066
0.734
0.097
0.783
0.051
0.727
0.059
0.773
0.039
Reddit-M
GAT
0.717
0.014
0.733
0.053
0.644
0.120
0.717
0.036
GCN 0.766
0.009
0.759
0,013
0,805
0.006
0.777
0.009
GIN 0.770
0.018
0.742
0.035
0.746
0.031
0.797
0.016
Table 7: AUROC of tuned perturbed models underlying our performancessparabliiy computations. For Reddit-M, the complete- graph and complete-featuree perturbations failed train due to memory problems. For Reddit-B, GIN failed for similar reasons.
the case that AUROC and accuracy yield different outcomes for whether or not mode is informative then this is denoted as (un)informttive For the judgment depicted in the Evaluation column of scale from 0 5 as 1.5 S + 1. F, where S, F E {0, 1, mapping "uninformative" to 0. "(un)informative" to 1, and informative to 2, and giving the structural mode higher weight than the feature mode because we are dealing with graph-learning datasets. The final evaluation results from binning the scores as
conveyed by our results, we recommend considering the full, uncondensed separability results when assessing the quality of individual datasets.
Table 1, we score datasets
D.2.3. PERFORMANCE. CEAPORMANCE-SEPARRBILTTT EVALUATION
For each dataset, we evaluate the performance separability between its perturbed versions using two different statis- tics in our permutation tests KKolmogorov-Smimoo and Wilcoxon rank-sum) well as two different a-levels as significance cutoffs (0.01 and 0.005). Notably, we see very few differences in the separability results and the associated classification of datasets, confirming the robustness of our approach.
00, 1] + - (1,2) +
(2 3] + o, (3,4 + +, (4,5) ++.
While we include this categorization to simplify the message
22

---

No Metric to Rule them All: Toward Principled Evaluations of Graph-Learning Datasets
Component
Specifications
Available CPUs
Intel Xeon (Haswell, Broadwell, Skylake, Cascade Lake, Sapphire Rapids, Emerald Rapids)
Intel Xeon (6134, 6248R, 6142M, 6128, 6136, E5620)
Intel Platinum (82801., 8468, 8562Y4)
AMD Opteron (6164 HE, 6234, 6376 (x2), 6272, 6128)
AMD EPYC (7742. 7713, 7413, 7262)
Available GPUs
NVIDIA Tesla (K80, P100, V100, A100, H100, H200)
NVIDIA Quadro (RTX 8000, RTX 6000)
AMD MI100
Table 8: Summary of Compute Resources. Especially when tuning our models used to generate the performance separability results seen in Tables 6 and 7, we relied heavily on high performance cluster units multiple institutions that supported our work with the above hardware specifications.
that probes the separability of individual samples. Instead of asking how perturbations affect overall accuracy, we ask a more granular question: How similar are the sets of graphs that two given mode perturbations classify correctly? To explore this, we compute the average similarity of correctly classified graph sets across multiple test splits and random seeds. Table 12 outlines the configurations for two datasets from different categories in our dataset taxonomy: MUTAG and PROTEINS.
Parameter
Values
Feature Metric
Euclidean (P Pees iPo,: Pr. Diffusion
Perturbations
Structural Metric
Matrix Norm
L1,1
Diffusion Steps
{1, [1, 10}
Seed#
0, 2 22, 23,
For each (vp(D), pair, we extract the set of correctly clas- sified graphs and compare them across mode perturbations. We report two similarity metrics: the Jaceard Similarity, which measures the proportion of overlap between two sets, and an Asymmetric Overlap, which quantifies the fraction of correctly classified samples under a perturbation that are also classified correctly in the original setting. Formally, we define
Table 9: Complementarityycallllttto setup for random- ized mode perturbations. We compute complementarity under perturbations 2/2 as specified in the above table, with E {f.g). Without being subject gradient descent in our calculations,
e also compute Yey- For definition of Dif fusiinn, on, see Definition B.2 and note our treatment of disconnected graphs in Appendix B. Finally, seed is only varied over the random perturbations yr. and our results are aggregated based on the average complementarity.
1A A' IAU A'i'
JAnA' |A'
Jaccard (A, A')
Asymm(A',
D.2.4. SUPPLEMENTARY EXTENSIBILITY EXPERIMENTS
where A and A' denote the sets of graphs correctly classified for by the two models being compared.
The RINGS framework was developed from first principles to be tool for the graph-learning community. In the spirit of inspiring and facilitating new and more detailed analyses of graph-learning datasets, RINGS was designed to be modular and configurable.
Our findings are visualized Figure 8. Across both datasets, most configuration pairs show strong agreement in the graphs they classify correctly. However, in Figure 8b, the Pet perturbation exhibits consistently lower similarity scores across all architectures, suggesting that it correctly classifies a distinct-and likely outieer-subset of graphs. Combined with the results in the main paper, which show high accuracy but low AUROC for Proteins under yar this suggests that these models are exploiting superficial structural cues to memorize the dominant class, rather than learning meaning- ful patterns.
Just as adaptability to other feature and structure metrics has been established in Appendix B.2, we continue to explore the extensibility of RINGS in this section, demonstrating how can accomodate other tasks (graph regression), archi- tectures (transformer architectures), and different granu- larity of results (graph-level performance results).
Extending to graph-level performance results. Inspired by reviewer feedback during the rebuttal phase, we present a preview of a deeper suite of analyses enabled by RINGS sppeifiically, geveh-level investigation of performance
By analyzing graph-level similarity across perturbation modes and architectures, we provide a more nuanced view of model behavior one that moves beyond coarse aggre- gate metries to capture variation the level of individual
23

---

No Metric to Rule them All: Toward Principled Evaluations of Graph-Learning Datasets
Dataset
Accuracy
AUROC
Structure
Features
Evaluation
AIDS
<f> eg 1g 2g
cflcg/eg/orrg
uninformative informative
uninformative
COLLAB
0> o> cg/rg cg ofhff
o > cg/rg > eg > rf of rg > cffcg/eg/o/tf
informative
DD
rg > 0g >>>gg>ff> cg/o if eg > >f
uninformative
uninformative
Enzymes
eg/o eg > rg.. of if cg/o > eg/ng cf/ff o> eg/ng > <g>d>>>> cffc//eg/o/ffgg
uninformative
informative
IMDB-B
ellcg/eg/olrlhng cg/egloig >f
uninformative
(un)informative
IMDB-M
(un)informative
informative
MUTAG
clfcgleg/ohg >
uninformative
uninformative
MolHIV
o cffcg/g > ff eg
> cffe > >g> if cg rg> eg/tf > of
informative
informative
NCII
0> cg < >g> eg/if
informative
informative
Peptides
0> 0> > >g
(un)informative
informative
Proteins
cf cgleglohting
clcg/ee/ohring
uninformative
uninformative
Reddit-B
of m>>g>>>> 2 eg/if rf/rg> m>ggo>>
n gdd cg/eg/f
uninformative uninformative
Reddit-M
rf eg
uninformative
uninformative
Table 10: Measuring performance separability between different versions of the same dataset: Wilcoxon rank-sum test. Supplementing Table 1, we use the Wilcoxon rank-sum as a test statistic to replace the KS statistic in our permutation tests, with an otherwise identical setup (10 000 random permutations; a-level of 0.01; Bonferroni correction within each dataset). The results substantively the same, with the exceptions that IMDB-B gets downgraded from fair poor, and MUTAG gets downgraded from poor very poor.
Dataset
Accuracy
AUROC
Structure
Features
Evaluation
AIDS
cf cg rg eg/o If o cg/g > eg clfff
elieg/tg > eg/o
uninformative
uninformative
COLLAB
o > cg/r > eg > rf > of
informative
informative
DD
rg > og
cg/o >n
rg > cffcgleg/offf
uninformative
uninformative
Enzymes
eg > 1g>>>>>>>f>f of
eg/o > > rg of > if o> > cg > cg/ig ef/ff
uninformative
informative
IMDB-B
ctfcg/cg/ohtthgg
(un)informatiie
(un)informative
IMDB-M
cg/egloing> >f
o cgleghg > of
(un)informative
informative
MUTAG
cffcglo/t > >f
cflo > cg/eg/ffing
(un)informative
uninformative
MolHTV
o> <ffleg/g>ff>>
o> >> o 0> cg >><>>a>> eg/if <g>o>ラ>> df c/cglee/ooffitg
rf
informative
informative
NCII
0> cg c> >><>>d>>>>>>>>>>
informative
informative
Peptides
0> >g >f
(un)informative
informative
Proteins
cf> cg/eg/o/hig
uninformative
uninformative
Reddit-B
o/rg > > eg/if rf/rg >>>>>>>>
rg <> of o cg/eg/f > rf o eg
uninformative uninformative
Reddit-M
uninformative
uninformative
Table 11: Craasringgerformaate separability between different versions of the same dataset: a:50.055. Supplementing Table 1, we test at an a-level of 0.005 instead of 0.01, using an otherwise identical setup 000 random permutations; KS statistic; Bonferroni correction within each dataset). The results are substantively identical to Table 1.
samples. We hope that deeper investigation of graph-level performance through RINGS will uncover opportunities for dataset improvement and inform the design of robustness- enhancing interventions.
atoms. The PyG version has eleven node features, the first five being one-hot encoding of the atom type, and the rest representing measures such as the hybridization state and the number of hydrogen atoms. Nineteen regression tasks seek to predict a variety molecular properties. We focus on task 0 (as defined by PyG), regressing the dipole moment, which describes the spatial distribution of electrons.
Extending to regression datasets. While the primary analysis of the paper concerns graph classification datasets, RINGS is intrinsically task-agnostic. As a proof of con- cept, we also apply RINGS to two common graph regression datasets, QM9 and ZINC-12K. As recommended by their authors, datasets.
The ZINC-12 dataset (Dwivedi et al., 2023), which con- tains 12 000 molecules, is subset of the larger ZINC dataset (Sterling & Irwin, 2015), which contains 250 000 molecules. In ZINC-12K, each node has only one feature, which en- codes the type of atom. The task is to regress constrained solubility, defined as the water-octanol partition coefficient (logP) minus the synthetic accessibility score (SAS) and the number of cycles with more than six atoms. Constrained solubility has implications in drug design, and thus has been
MAE the performance metric for both
Dataset descriptions. QM9 (Wu et al., 2018a) is a molecular dataset of 133 885 graphs. Its name originates from its focus on quantum mechanical properties and the makeup of the dataset: stable, organic molecules with nine or fewer heavy
24

---

No Metric to Rule them All: Toward Principled Evaluations of Graph-Learning Datasets
1:00
1.00
0.04
3.90
1:00
1014
012
10:0
6071
0.01
3.81
09.00
200-4
O6T
C21
L42
0.00
0.7S
6.74
3:7
120
6/62
0.43
3.23
0.30
606
640
0.00
0.04
60%
9024g
0.6
0.5
6:15
0.24
0.96
6:66
9.96
6.06
3.82
0.92
6:00
642
0.77
0.05
144
6.0
0044
6.6
637
0.35
0.00
6108
9.84
0.0
3.34
0.34
600
6.12
9.33
0.85
0.00
LC0
172
605
60X
0054
6.6
1.43
0.05
00.9
6.71
0.07
6/6
6:11
3.44
6.22
9:57
0.64
0.00
144
10
0.
1000
09
6.0
C9A
100
E04
1.00
0.57
6:15
0.95
0.97
6.5
6:55
9.87
0.91
0.56
0.08
3.87
0.87
6.0
8.02
0.70
0.00
14
180
0.0
044
0.0
101
600
ECL
plud-
0.00
0.52
6:75
0.90
1.00
8:03
9:90
0.01
0.56
E.55
3.82
0.21
6.06
6.33
000
1967
pirt
(a) MUTAG
(b) Proteins
Figure 8: Graph-level agreement between (mode, architecture) pairs. Jaccard similarity (upper triangular) and asymmer- ric overlap (lower triangular) quantify the similarity between sets of graphs correctly classified by different models on the MUTAG (a) and Proteins (b) datasets. Higher values indicate larger shared set of correctly classified samples between (A) pairs.
Aspect
Details
Mode
QM9
ZINC- 12k
Global (PyTorcc)) Seeds
{42, 7. 123, 56, 89)
cg
0.39 0.05
1.31 + 0.02
Test/Train Split Seeds
[67, 23, 77, 88, 54]
eg
0.65 + 0.03
0.98 4 0.03
Transform Seeds
Random Modes: (34, 12, 99, 10) Fixed Modes: (34)
cf
0.07 0.01
1.40 =
0.60 + 0.02
0.80 0.03
Evaluation Strategy
Tuned model (so(D), A. 6) re- re-trained distinct CV splits and all unique groupings of random seeds, then evaluated on the test set of (DD).
rf
1.44 + 0.02
1.48 0.01
rg
0.93 + 0.01
1.39 + 0.02
Table 13: Performance results for regression datasets
using the GCN architecture. For the QM9 and ZINC-12K regression datasets, each entry is reported as MMAE - MAE-
Table 12: Granular evaluation setup. For our extended experiments--includin graph-level analyses, regression tasks, and new architectures introduce additional con- trols to account for randomness in performance separabil- ity: (I) model initialization via the PyTorch global seed, (2) train/test splitting, and (3) perturbation generation (ap- plicable to random-ge -gappgrrahhhhh and featuress modes). To ensure consistency across datasets, we use the same three sets of five unique seeds.
We thus opt to use bootstrapping, sampling 000 times with a confidence interval of 99%, yielding the results shown in Table 14. As RINGS was developed from first principles, we apply the same classification schema to the relevance of information in each mode and the overall dataset evaluation.
Interpretation of results. For QM9, performaane--sparabbii results suggest that neither the original mode nor its pertur- bations are particularly informative for the task. Notably, the original mode underperforms both Por and Pegg rais- ing concerns about its suitability as a default configuration. Depending on the diversity of available modes, this may warrant realignment- or even deprecation- QM9 in its current form. In contrast, ZINC- 112 yields more encourag- ing results: The original mode consistently outperforms all perturbations, indicating that it captures task-relevant struc- ture, and yielding a ++ overall classification. Interestingly, graph perturbations tend to outperform feature perturbations, suggesting that node features play a more critical role in this
used as the target for molecular graph generation models, as in (Jin et al., 2018) and (Kusner et al., 2017).
Performance separability results. Using the fine- ene-ggrined evaluation setup described in Table 12, we evaluate the per- formance of the two regression datasets using the GCN architecture, adapting the procedure to minimize MAE in- stead of maximizing AUROC. We report these results in Table 13. Note that we have far fewer successful runs as for our the graph classification experiments in the main paper (see Appendix D.2.4).
25

---

No Metric to Rule them All: Toward Principled Evaluations of Graph-Learning Datasets
Dataset
MAE
Structure
Features
Evaluation
QM9
cf < <g < 1g < if 0 0 eg eg rg/cf <f
uninformative informative
unformative
ZINC-12K
informative
++
Table 14: Performance separability for regression datasets following results in Table 13, Separability is computed using bootstrapping, sampling 10, 000 times with a confidence interval of 99%. The evaluation is based on the performance separability schema outlined in Table 1.
task than the underlying graph structure. For both datasets, more exhaustive training routine-as employed in the main paper-is necessary to draw definitive conclusions regarding their placement within the regression taxonomy.
Computational challenges. Rigorous evaluation of GNNs and their benchmark datasets introduces significant computational challenges. Despite access to substantial computing resources, notable portion of model trainings failed to snaverge-particulann and stringent experimental setups introduced in this work. For example, even in our original experimental configura- tions, GIN models on REDDIT-B could not be successfully tuned trained, and REDDIT-M experiments under the complete-graph and complete-featuure, perturbations (see Figure 3) also failed due to memory limitations or conver- gence issues. Our extended evaluations for ZINC, QM9, GPS, and graph-level analyses faced similar constraints, re- sulting in smaller sample sizes for these experiments relative to those reported in the main results.
under the more granular
Extending to transformer architectures. As recom- mended by our reviewers, we further demonstrate that RINGS also generalizes nicely transformer architectures such as the GPS Transformer, introduced by Rampásek et al. (2022). In contrast to GCN, GIN and GAT, GPS combines local message passing with global attention to overcome the expressivity and scalability limits of traditional GNNs. We compare the performance separability when consider- ing 4 architectures across three datasets (NCII, MUTAG, Proteins). Note that other transformer architectures, such as the Graphformer architecture proposed by Yang et al. (2021) that we originally planned to include in our extended experiments, are tailored to scenarios with non-graph data, which lie beyond the scope of this work.
At the graph level, we achieved full coverage for MUTAG and 97% coverage for Proteins (based on the grids estab- lished in Table 12), but other datasets were hindered by incomplete runs. These issues underscore the need for more adaptive configuration and tuning strategies to ensure stable model convergence across diverse datasets and architectures. Understanding and mitigating these failure modes remains important direction for future work. Our results reflect both the potential and the practical limitations of large-scale, rigorous GNN evaluation pipelines such as RINGS.
aeffomannc-separrabii results. Accuracy and AUROC results for the GPS architecture are reported in Table 16 and Table 15, respectively, alongside newly generated re- sults for GCN, GAT, and GlN-each run under the exact randomization schema outlined in Table 12.
Our goal is to assess whether incorporating a transformer- based architecture, specifically GPS, meaningfully alters performance separability outcomes. To this end, we com- pare separability results that include GPS with those based solely on the core architectures (GCN, GAT, GIN), as shown in Table 17. As reminder, performance separability is com- puted using the best-performing architecture for each mode.
D.3. Extended Mode Complementarity
In our mode-complemmnttariy computations, we need to distinguish fixed modes (original, empty, complete) from randomized modes (random, shuffled). To compute mode complementarity for the randomized modes, we use five different randomization seeds for each graph, resulting in the setup summarized in Appendix D.2.2.
To assess statistical significance, we apply bootstrapping with 10,000 resamples and report 99% confidence intervals, as shown in Table 17. We then apply the RINGS classifica- tion schema to evaluate the informativeness of each mode and determine the overall dataset classification.
To study how perturbations impact the complementarity of dataset, we refer to Figure 4 (see Figure 9 for supple- mentary visualization of mode complementarities computed for 7 OGB datasets). In the top panel, we compare the orig- inal complementarity score using the L1, norm, 7 to the complementarity under fixed perturbations 1.11 where & {Peg 'Peg Per PPt) with the randomized perturba- tions shown in the bottom panel. Note the symmetry intro- duced by Theorem 2.15, i.e., that 7e* perturbations, as per Proposition A.10, effectively measure
Interpretation of results. We find that the inclusion of GPS has negligible impact on performance separability and dataset classification. This validates our decision to focus on the core architectures in the main paper, which are computa- tionally lighter. yet still sufficient to support the conclusions drawn about dataset behavior.
1,1 1 1 7 These
26

---

No Metric to Rule them All: Toward Principled Evaluations of Graph-Learning Datasets
0
14
μ
0
A
0
Dataset
cg
cg
og
eg
1g
rg
cf
cf
rf
rf
MUTAG
GAT
0.882
0.100
0.782
0.163
0.877
0.123
0.867
0.104
0,920
0.050
0.658
0.143
GCN
0.885
0.097
0.827
0.140
0.862
0.097
0,851
0.091
0.903
0.062
0.598
0.136
GIN
0.926
0.072
0.887
0.162
0.844
0.107
0.913
0.058
0.914
0.054
0.846
0.095
GPS
0.727
0.245
0.483
0.399
0.415
0.386
0.476
0.398
0.719
0.330
0.849
0.180
NCII
GAT
0.552
0.140
0.672
0.056
0.667
0.026
0.655
0.070
0.738
0.017
0.683
0.033
GCN
0.794
0.020
0.736
0.015
0.646
0.027
0.685
0.032
0.745
0.014
0.648
0.038
GIN
0,844
0.017
0.740
0.046
0.628
0,041
0,693
0.036
0.731
0,019
0,653
0,032
GPS
0.661
0.097
0.626
0.018
0.677
0.064
0.677
0.058
0.675
0.035
0.671
0.047
PROTEINS
GAT
0.785
0.053
0.759
0.048
0.791
0.051
0.769
0.057
0.769
0.030
0.733
0.040
GCN
0.787
0.058
0.787
0.047
0.777
0.059
0.786
0.045
0.762
0.032
0.750
0.039
GIN 0.788
0.045
0.769
0.035
0.780
0.050
0.769
0.036
0.731
0.051
0.770
0.042
GPS
0.738
0.086
0.608
0.171
0.754
0.040
0.602
0.163
0.715
0.102
0.766
0.034
Table 15: AUROC results for GPS and core architectures. For each architecture, we report each mode's mean AUROC and its standard deviation. We do this for subset of our datasets, namely Proteins, NCI1, and MUTAG.
0
0
Dataset
cg
cg
eg
eg
rg
rg
cf
cf
rf
rf
MUTAG
GAT
0.736
0.102
0.701
0.099
0.654
0.106
0.677
0.079
0.736
0.104
0.647
0.104
GCN
0.744
0.099
0.783
0.107
0.736
0.106
0.789
0.080
0.834
0.077
0.631
0.095
GIN
0,853
0.087
0.826
0.137
0.701
0.125
0.845
0.077
0.839
0.067
0.682
0,082
GPS
0.570
0.176
0.485
0.185
0.465
0.179
0.485
0.180
0.590
0.159
0.648
0.105
NCTI
GAT 0.550
0.055
0.578
0.043
0.499
0.030
0.565
0.033
0.680
0.018
0.496
0.030
GCN
0.717
0.025
0.669
0.018
0.538
0.021
0.640
0.027
0.684
0.015
0.499
0.029
GIN
0.769
0.020
0.690
0.026
0.541
0.022
0.647
0.031
0.675
0.024
0.541
0.041
GPS
0.492
0.034
0.528
0.016
0.489
0.038
0.497
0.039
0.610
0.033
0.494
0.028
PROTEINS GAT
0.612
0.052
0.631
0.055
0.601
0.039
0.608
0.049
0.722
0.038
0.608
0.034
GCN 0.593
0.033
0.627
0.069
0.600
0.046
0.593
0.029
0.725
0,036
0.610
0.028
GIN 0.609
0.033
0.602
0.043
0.602
0.038
0.607
0.050
0.705
0.039
0.606
0.028
GPS 0.582 0.049
0.547
0.083
0.590
0.028
0.532
0.068
0.669
0.109
0.591
0.027
Table 16: Accuracy results for GPS and core architectures. For each architecture, we report each mode's mean accuracy and its standard deviation. We do this for a subset of our datasets, namely Proteins, NCII, and MUTAG.
Dataset
GPS Results
Accuracy
AUROC
Structure
Features
Evaluation
MUTAG
Present
> o/t//f/cg
> rf
o/cSltg/cg/eghf o/cf/tg/cg/eg
uninformative uninformative
uninformative uninformative
Absent
o/tg/cf/g > eg
NCII
Present
0> cg/cff > rg > eg/rf
> efteg > rg > rfleg o > elleg > rg > rf > eg
informative informative
informative
Absent
0 cg/cl > rg > eg/rl
informative
Proteins
Present
<f> cg > off/g/gg of >g>>gg>o ofrf/rg/gg
eg/o/cg/tg > rflef eg/olcg/tg rf/ef
uninformative
(un)informatie
Absent
uninformative (un)informative
Table 17: Comparison of performance-spaarbbiltyy classification with and without GPS. For Proteins, NCI1, and MUTAG, we compare performance separability results with and without including the GPS architecture. The evaluation is based on the performance--cpaarbbilty schema outlined Table 1.
the self-complementtarit of both modes, thus providing in- sights into the diversity of either the graph structure or the features contained in given dataset. In particular, extreme 1.1 scores imply that the metric space of the dual mode is uninteresting (i.e., it lacks any geometric diversity in the
distance matrix). We see this phenomenon, for example, in datasets with high Yej such as IMDB-B and IMDB-M -M, both notably ego-networks. Similarly, we note datasets with extreme 7111 including DD, whose node features are de- rived artificially from node degree. We formalize this notion
27

---

No Metric to Rule them All: Toward Principled Evaluations of Graph-Learning Datasets
1 98 Bo
ongital
1.0
DATASET
Proteins
empgyy graph
Roddit-B
84
complete festares
emppy foatnos
0.8
COLLAB
Reddit M
DD
PERTURBATION
Accuncy
Farymes
original
8a.
86
stuflled goph
ranion graph
onginal
0.6
0000000
IMDB-M
IMDB-B
emppy griph
complete graph
rasdon feutures
1H0000
MUTAG
random graph
duifial featores
0.4
MolitIV
complete features
0.00
milhoon
nevittp
molchissos
meleam
nulpchs methinc11
NCII
random features
Peprides
40000
Comparing levels of mode complementarity across different versions of the same dataset. We show the mean (dot) and 95th percentile intervals (bars) of com- plementarity scores for the original version well as 4 deterministic perturbations (top) and 4 randomized pertur- bations (bottom) of 7 OGB datasets, computed with t = diffusion steps. Black horizontal lines indicate mean mode complementarities of the original dataset, and the silver hor- izontal line marks the 0.5 threshold relevant for assessing mode diversity. Note that Yeg by definition. Contrasting with the variation apparent in Figure 4, the OGB mol-* datasets are remarkably similar in their mode- complemntly profiles.
Figure 9:
0.1
0.4
0.7
1.0
Mode Complementarity
Figure 10: Mode complementarity and performance: Ac- curacy as a performance measure. We show the mean accuracy (y) as a function of the mean mode complemen- tarity (x); for the original version and perturbations of 13 graph-learning datasets, based on our best-on-averee models (as in Figure 3). Each marker represents (dataset, perturbation, t) tuple, where E [10] is the number of dif- fusion steps used in the computation of diffusion distances on the graph. Higher mean mode complementarity appears to be associated with higher accuracy, and datasets differ in the range of their mode-complemmnttariy shifts.
Yeg and Yet = Yet
D.3.2. MODE COMPLEMENTARITY AND PERFORMANCE
of mode diversity in the following section.
Our intuition is that datasets with high complementarity (dif- ferent and high information content across the two modes) should perform better. In line with this expectation, we observe a generally positive relationship between mode complementarity and performance when measured by both AUROC and accuracy, as visualized in Figure 5 and Fig- ure 10, respectively. This correlation is further quantified in Table 18, where we symbolically categorize the observed correlations by creating five equal bins in the interval [-000, 1.0), i.e., [-1.0, -0.6), |-0.6, 0.6.--022). -0.2), [-0.2, 0.2), [0.2, 0.6). [0.6, 1.0]. Again, this categorization only serves to communicate our main message (here: that the correla- tions are mostly positive and substantively robust to different ways of measurement). but the numerical values should be consulted for gaining detailed insights.
1. MODE COMPLEMENTARITY AND MODE DIVERSITY
In Table 2, we compute A.-9 for each graph in the dataset and then compute the mean j and the standard deviation o of these scores. A low mean for mode is indicative of low diversity across the dataset, meaning we see little variation in the geometric structure of the corresponding metric space. To arrive at our symbolic scoring for μt, we divide the in- terval [o, 1] into five equal-width bins as [0, 0.2). [0.2, 0.4), [0.4, 0.6). [0.6, 0.8). [0.8, 1.0). We proceed similarly for a, using smaller brackets due to its different scale: [0.0, 0.05). [0.05, 0.1), (0.1.0.15) 10.15, 0.2), [0.2, As with our symbolic performance-separabllii scoring, these categories primarily serve to convey our main message, but the numer- ical values (which do not exhibit discontinuities) should be preferred when conducting in- in-depth dataset evaluations.
Taking a closer look Figure 5, we can observe how the relationship between mode complementarity and perfor- mance changes across mode perturbations (drawn as differ- ent shapes). Note that most datasets categorized as good graph-learning benchmarks (such as Peptides and NCI1) exhibit stronger positive trend between complementarity and performance among their perturbations. We see even stronger association with some datasets when the original mode (denoted by circle) is not only the best performer but also has the highest complementarity.
Simply put, datasets with (very) good diversity are candi- dates for new tasks that could leverage the diversity seen in these modes. In particular, we are interested in datasets that performed poorly in the performance separability evaluation (see Table 1) but have high structural diversity. This type of dataset may have potential as graph-leariig benchmark- if remodeled or assigned a new task that better leverages the information in both modes. As depicted in the second row of our taxonomy table in Section 4.3, these datasets are AIDS, DD, MUTAG, Reddit-B B, and Reddit-M.
For a given perturbed dataset, Figure 5 also shows the changes over different diffusion steps (i.e., the horizontal
28

---

No Metric to Rule them All: Toward Principled Evaluations of Graph-Learning Datasets
Accuracy Values k
AUROC Values
Accuracy k
AUROC
Evaluation
P
8
A:
8
k
Dataset
AIDS
0.51
0.33
0.23
0,44
0.29
0.19
+
+
+
0
+
COLLAB
0.21
0.28
0.19
0.22
0.25
0.18
+
DD
-0.17
-0.31
-0.20
-0.27
-0.24
-0.16
Enzymes
0.48
0.41
0.29
0.47
0.38
0.26
+
+
IMDB-B
0.33
0.28
0.19
0.57
0.50
0.34
+
O
+
+
IMDB-M
0.50
0.59
0.40
0.58
0.67
0,46
+
+
MUTAG
0.32
0.29
0.20
0.11
0.12
0.08
MolHIV
0.14
0.19
0.13
0.61
0.55
0.39
++
NCTI
0.66
0.69
0.48
0.47
0.59
0.40
++
++
+
++
Peptides
0.65
0.37
0.25
0.71
0.52
0,36
++
+
++
++
Proteins
0.21
0.20
0.12
0.09
0.10
0.07
Reddit-B
0.44
0.32
0.24
0.12
0.30
0.21
Reddit-M
-0.36
-0.46
-0.33
-0.33
-0.36
-0.24
Table 18: Mode complementarity and performance: Correlation statistics. We show the Pearson correlation between mode complementarity and test accuracy resp. AUROC for 13 graph-learning datasets, taken over 5 perturbations and t e [10] diffusion steps, based on our best-on-average models (as in Figure 3).
movement of points with the same color and shape). This has variable effect on the perturbed y score. This vari- ation merits further investigation, but we can already note some initial interesting patterns. For example, the Ye scores for MolHIV, Peptides, ENZYMES, MUTAG hardly change over diffusion, while the 7 score is more sensitive to the diffusion process. This may indicate that the metric spaces that arise from the graph modes are more similar to the metric spaces that arise from random features. This would suggest using Pet (as an "uninttrestinn" metric com- parison) to pick up more signal over diffusion process that occurs in GNNs.
selection, on the outcome. Even more broadly, Mazumder et (2023) present a call for data-centric machine learn- ing, emphasizing the need for considering foremost the data, including its quality and provenance, in the development cycle of machine-learinng models.
A crucial aspect of any data-centric approach is the devel- opment of suitable measures or metrics for the comparison of graphs or their respective (latent) representations. We find several prior works here (Lin et al., 2023; Tang et al., 2023; Zambon et al., 2020), but by their design, such mea- sures cannot focus beyond the comparison of individual graphs, remaining instead intrinsic with respect to specific dataset. Our mode complementarity overcomes this restric- tion by adopting a metric-space perspective. While some aspects of metric spaces based on graph structure have been studied (Chuang & Jegelka, 2022; Sanmartín et al., 2022; Sonthalia & Gilbert, 2020; Taha et al., 2023), the focus lies embeddings robust shortest paths, whereas our work is concerned with hamesssing metric-space information to provide insights into the interplay of graph structure and node features. Thus, our framework might also benefit from integrating metric space magnitude (Limbeck et al., 2024),
E. Related Work
Extending the discussion of related work begun in the main text, there are three relevant related lines of work followed in the graph-learning community, namely, (i) data-centric and multiverse approaches in machine learning, (ii) graph- learning benchmark datasets, and (ii) graph-learning eval- uations. Overall, we find that RINGS provides unique perspective on the challenges discussed in these fields.
Data-Centric and Multiverse Approaches. This cate- gory comprises works that assume a data-centric perspec- tive, potentially imbued with the multiverse notion, i.e., the notion that any data-analy anaa--n task necessitates an elaborate analysis of choices and "non-choices." " thus resulting not single outcome but multiverse of outcomes. This is novel perspective, originally arising from psychology. gaining trac- tion in general machine-lcarning applications (Biderman & Scheirer, 2020; Germani et al., 2023; Simson et al., 2024; Wayland et al., 2024), that serves to highlight the impact of different decisions, such as data preprocessing or model
Benchmark Datasets. Several publica- tions also present new benchmark datasets, driven either by the observation that existing datasets do not cover suffi- ciently "dense" part of the graph- landscape (Palow- itch et al., 2022), aiming present more challenging tasks that serve to explore the limitations of existing archi- tectures (Akbiyik et al., 2023; Dwivedi et al., 2022). For example, in the context of node-classification tasks, new datasets are proposed to assess the performance of GNNs in heterophilous (or, more precisely, non non-homophilous) regimes (Lim et al., 2021; Luan et al., 2022; 2023; Mao
29

---

No Metric to Rule them All: Toward Principled Evaluations of Graph-Learning Datasets
al., 2023; Platonov al., 2023a;b), typically drawing upon graph-level measures from network science (Barabási, 2016; Newman, 2018).
However, with mode complementariry, we seek a score that (1) treats graph structure and node features as equal, (2) works on graphs without node labels and does not make any assumptions about the spaces arising from edge con- nectivity and node features, and (3) specifically informs graph-level learning tasks such as graph classification. To the best of our knowledge, we are the first to propose a score fulfilling these desiderata.
Graph-Learning Evaluations. Previous work on evalu- ating graph learning can be broadly categorized into papers that, like ours, criticize the status quo in terms of dataset usage, the data quality such, or specific aspects of given GNN architecture. For the first category, we find works that criticize lack of suitable baseline comparison part- ners (Cai & Wang, 2018), issues with hyperparameter tun- ing and model selection (Errica et al., 2020; Tönshoff et al., 2023; Zhao et al., 2020), or problems with data-model mis- match (Chen et al., 2020). The second category comprises works that highlight the use of unsuitable datasets (Bechler- Speicher al., 2024; Li et al., 2024), problem that is also of relevance to other areas in machine learning (Ding & Li, 2018; Fenza et al., 2021). The third category, dealing with the shortcomings of existing architectures, is of particular relevance to practitioners, since it either inspires new re- search directions or provides practical guidance concerning which models to use in specific application.
Among the different shortcomings, issues inherent to the ressage-passingg paradigm are well-studied (Alon & Ya- hav, 2021; Di Giovanni et al., 2023; Yang et al., 2022), often leading to improved architectures (Chen et al., 2022;
Han et al., 2023; Michel et al., 2023), with a recent trend being the development
methods that obviate message passing (Fan et al., 2020). Beyond our brief categoriza- tion, we also observe interest in general GNN "explainabil- ity" strategies (Agarwal et al., 2023; Bonabi Mobaraki & Khan, 2023; Faber et al., 2021; Li et al., 2022; Rathee et al., 2022; Toyokuni & Yamada, 2023; Wang & Shen, 2023; Xie et al., 2022). However one has to bear in mind that such approaches are often tightly coupled to a specific task and a specific architecture, which, while valuable, cannot help in overcoming dataset deficiencies.
30


Reviews:
[{"review_id": "PcRZmuAHKP", "reviewer": "Reviewer_rJcn", "summary": "This paper introduces a novel framework, Rings, for evaluating the quality of graph-learning datasets by quantifying differences between the original dataset and its perturbed representations. The authors propose two key metrics: performance separability and mode complementarity, which assess the relevance and complementary nature of the graph structure and node features for a given task. The framework is applied to 13 popular graph-classification datasets, revealing significant insights into the quality and suitability of these datasets for graph-learning tasks. The paper is well-structured, methodologically sound, and provides actionable recommendations for improving benchmarking practices in graph learning.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments and your support of our work. In the following, we address C1 and C2 as well as your additional question (“Q1”).\n\n- **C1 (restriction to graph-level tasks).**  \nAs noted in “Discussion→Future Work” (ll. 431–435r), we see extending our framework to node-level and edge-level tasks as an interesting direction for future work. While assessing performance separability for such tasks will essentially work out-of-the-box, extending the notion of mode complementarity to these settings will require considerable additional research.  \n- **C2 (additional theoretical insights).**  \nAs stated in “Discussion→Future Work” (ll. 427–431r), we agree that further theoretical insights are desirable. However, we estimate that the corresponding analyses will merit a separate paper. We will provide some more guidance on how to arrive at additional theoretical insights (e.g., by taking an information-theoretic perspective) in the “Future Work” paragraph of the updated manuscript.  \n- **Q1 (model-design guidance).**  \nWe believe that RINGS could promote model design in several ways.   \n    1. As highlighted by our dataset taxonomy, performance separability can eliminate benchmark datasets that do not require the specific capabilities of graph-learning models to integrate information from both modes, helping the community direct model development to where it is most needed.  \n    2. Mode-complementarity and mode-diversity measurements could guide architectural choices for a specific task on a specific dataset (e.g., whether a model should focus on leveraging the graph structure or the node features).   \n    3. Mode-complementarity and mode-diversity measurements could inform model designs that incorporate data-centric components to adaptively enhance performance (both at the level of individual observations and at the level of entire datasets)–e.g., by preprocessing the data to increase mode complementarity (which is correlated with performance).  \n\n    We will add these suggestions to the updated manuscript but note that 2\\. and 3\\. merit further experimental confirmation.\n\nWe hope that these responses addressed your concerns and are happy to answer any further questions you may have.", "claims_and_evidence": "The claims are well supported by the empirical studies.", "methods_and_evaluation_criteria": "The methods and evaluation criteria are appropriate.", "theoretical_claims": "N.A.", "experimental_designs_or_analyses": "Experiments follow standard procedures in graph learning.", "relation_to_broader_scientific_literature": "This submission can inspire graph learning area, especially its understanding of datasets, which may promote the design of graph models.", "essential_references_not_discussed": "N.A.", "other_strengths_and_weaknesses": "Strengths:\n\nS1. The Rings framework offeres a principled approach to dataset evaluation that goes beyond traditional model-centric evaluations.\n\nS2. The extensive experiments on 13 datasets demonstrate the practical utility of the framework and provide valuable insights into the quality of these graph datasets.\n\nS3. The paper is well-written, with clear explanations of the methodology and rigorous experimental design.\n\n\nConcerns:\n\nC1. The current framework is primarily focused on graph-level tasks. Extending it to node-level and edge-level tasks could further enhance its applicability. \n\nC2. While the paper provides some theoretical insights, a more comprehensive theoretical analysis of the properties of several key concepts could strengthen the work.", "other_comments_or_suggestions": "NA.", "questions_for_authors": "In addition to C1 and C2, how does the RING framework affect (promote) the graph model design (under node-/edge-/graph-level tasks)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YZORX3lBD3", "reviewer": "Reviewer_7Dac", "summary": "This paper focuses on the problem of evaluating benchmark datasets for the task of graph classification. In particular, they consider studying the importance that both structure and node features have on performance. They consider measuring this by perturbing the original graph, both in terms of the structures and features, and measuring both the change in performance and change in graph properties. They do so across a variety of common datasets. They find that for many datasets, perturbing either the features or structure has little effect on both performance and mode complementarity. They argue that this indicates a need for newer datasets where both the features are structures are necessary for optimal performance.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging feedback. We address your points by the section in which they were raised.\n- **Methods And Evaluation Criteria: Measuring performance separability.**  \nWe designed performance separability mirroring model-centric evaluation practices to facilitate adoption but agree that a fine-grained perspective will provide additional insights. Following your suggestion, we will include an experiment that examines performance changes at the level of individual graphs in the updated manuscript. We did not log test-set performance at the level of individual graphs in our original experiments but are recomputing the necessary evaluations (*experiments in progress*).  \n- **Experimental Designs or Analyses.**   \n  - **Coverage of GNN models.**  \n  Following your suggestion, we will include results for the GPS and Graphformer models in the updated manuscript (*experiments in progress*).   \n  - **Interpreting the discrepancy between performance separability and mode diversity.**  \n\n    **(a)** We say that a dataset is “misaligned” if it does not exhibit performance separability, yet exhibits favorable mode diversity (derived from mode complementarity).   \n    **(b)** “Realignment” collectively denotes several potential operations, including (1) changing the benchmark setting (e.g., datasets with good feature diversity, such as MUTAG or AIDS, could serve as benchmarks for graph-free ML methods), (2) changing the prediction targets (e.g., using different categories to classify discussion threads in Reddit-B or Reddit-M), (3) amending the graph structure (if the dataset lacks structural diversity; this connects to the graph-rewiring discussion), and (4) amending the features (if the dataset lacks feature diversity, e.g., for DD). \n\n    **(c)** Our experiments show that *higher mode complementarity* is associated with *higher performance*; we do not make any claims about the relationship between *mode diversity* and *performance separability*. Since performance separability assesses the task-specific performance gap between a dataset and its perturbations, and mode diversity measures the task-agnostic variation contained in the modes of an individual dataset, we would not expect high mode diversity to be consistently associated with performance separability (e.g., a dataset could have high structural and feature diversity but low mode complementarity, which could lead to “complete graph” and “complete features” performing on par with the original dataset, eliminating performance separability). \n\n    *Misalignment* occurs when there is interesting variation in the data that models could leverage in their predictions (high mode diversity), but the existing relationship between this variation and the prediction target does not provide a significant performance advantage over settings in which this relationship is deliberately destroyed (lack of performance separability). While the lack of performance separability could also be due to limitations of the models employed (i.e., they may not be expressive enough), given our comprehensive measurement setup, we deem it more likely that the relationship between the variation in the data and the prediction target is strained, prompting the need for *realignment*. However, disentangling in detail the model-related and data-related factors contributing to a lack of performance separability would be a valuable next step to further enhance the RINGS framework. \n\n    We will include these clarifications in the “Dataset Taxonomy” section of our updated manuscript.\n\n- **Other Comments or Suggestions: Clarifying the focus on graph classification.**  \nWe currently mention the focus on graph classification in ll. 78–80r, ll. 245–247r, ll. 430–433l, and ll. 431–435r. With the inclusion of graph-regression datasets suggested by Reviewer 5Mv7, we will now have two graph-level tasks in our experiments. Hence, we will make the following amendments to clarify our scope:  \n  - Abstract ll. 42/43l: Insert “on graph-level tasks” after “extensive set of experiments”.   \n  - Introduction l. 80r: Rewrite “extensive experiments on real-world graph-classification datasets” to “extensive experiments, focusing on real-world datasets with graph-level tasks.”  \n- **Questions for Authors: Accuracy and AUROC on MolHIV.**  \nMolHIV is highly imbalanced, with only 1443 out of 41127 graphs labeled 1 (and the rest labeled 0), leading to consistently high accuracy. AUROC is the officially recommended evaluation metric for this dataset; we include accuracy for completeness only and will note this in the updated manuscript. MolHIV also highlights the need for careful evaluation-metric choices (e.g., given the very skewed class distribution, AUPRC may be preferable over AUROC). \n\nWe believe that the improvements to our manuscript prompted by your comments will further strengthen our submission and are happy to address any further questions you may have.", "claims_and_evidence": "I think the claims made in this paper are well supported by the provided evidence.", "methods_and_evaluation_criteria": "I think all the proposed method and evaluation are mostly well designed. Specifically,\n\n1. I appreciate that the authors considered multiple types of perturbations. The different levels of perturbation are really helpful for accounting for the various ways that both modifying the features and structure can effect performance. \n\n2. I like that the authors considered a wide variety of datasets, that cover the common ones used for graph classification. This allows for a more comprehensive study. Furthermore, I like the comprehensiveness of the final results.\n\nHowever, I disagree with how the authors measured performance separability. In Figure 3, the authors compare the final performance by perturbation type. However, I believe that looking at the overall performance is actually not the correct way to check the effect on performance. In reality, for two perturbations, it could be that they actually differ greatly in \"how\" they achieve similar performance. In an extreme example, let's say we get a 50% accuracy on both the original dataset and one perturbation. Naively, it seems that the perturbation has no effect. However, it could be that they are completely disjoint in which samples they correctly classify.\n\nAs such, I think Figure 3 should be supplemented with an additional metric that considers the overlap in correctly classified samples. A simple way would be too calculate the what \\% of correct samples for the perturbed dataset were correctly answered by the original dataset . That is, let $S$ be the set of correctly classified samples w/o perturbation. Furthermore, let $S_{\\phi}$ be the same under some perturbation $\\phi$. We can then calculate $({S_{\\phi} \\cap S}) / S_{\\phi}$, which will be $1$ when all the samples answered correctly by $\\phi$ were also correct when using the original dataset. This is of course just one example, the metric itself can vary. \n\nI should be clear, I don't think this will have much of an effect at all on the final results and conclusions made in the paper. However, I believe that the current strategy of just comparing the overall performance is too coarse, and that it's important that we're sure that perturbing the graph either does/doesn't effect the sample-level performance.", "theoretical_claims": "Yes, all of them.", "experimental_designs_or_analyses": "I think the experimental design and analyses are generally good.\n\nHowever, there are two instances where I think they can be improved:\n\n1. One area I think can be improved is which models were used. Currently, only basic GNNs are used in the study. However, many papers have shown that more expressive models can achieve much better performance that basic GNNs on graph-level tasks. More recently, graph transformers have shown very promising performance. I think incorporating 1 or 2 of these methods, such as [1], would enhance the conclusions made by this study. This is especially true when perturbing the graph structure, as these more recent methods shown an enhanced ability to distinguish more complicated graph structural patterns. \n\n2. It's unclear to me what it means when performance and mode separability aren't aligned. For example, for both Reddit datasets, the performance separability is very low, indicating that they are poor datasets. However you then show that the mode diversity is quite high for both structures and features. The authors argue that such datasets may be \"misaligned\", however it's unclear what this means. I think the authors need to answer: (a) What is meant by misaligned? (b) How can we better align such datasets? (c) If the mode diversity is high, then why is the performance separability so low? I'd argue that this last question is most important as to me it suggests that either: (a) the current methods for measuring $D_F$ and $D_S$ may be lacking (b) Or that the disparity may be due to the methods used. However, if the authors have another idea for the cause I'd be interested.\n\n[1] Rampášek, Ladislav, et al. \"Recipe for a general, powerful, scalable graph transformer.\" Advances in Neural Information Processing Systems 35 (2022): 14501-14515.", "relation_to_broader_scientific_literature": "I think this paper relates to a lot of work in the area of Graph ML. Particularly, I really like the motivation and the idea behind this study. I think that far too often we neglect the quality of our benchmark datasets, however they are essential for our understanding of the strengths and weaknesses of proposed methods.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "None.", "other_comments_or_suggestions": "1. I think you can be clearer in the introduction and abstract that you're only focusing on graph classification. This isn't a weakness or anything, just that by reading both the reader may come away with an impression that you study a variety of different graph tasks (as far as I can tell, it is only mentioned at the end of the intro that the focus is graph classification, my apologies if I missed something)", "questions_for_authors": "1. In Figure 3, the accuracy of MolHIV seems to stay unchanged at 100% (or close) across the original dataset and all perturbations. However, the AUC is much lower and varies a lot. I'm curious if the authors have an idea as to what may be causing this discrepancy? Because for all the other datasets, both AUC and accuracy tend to be in lockstep with one another.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rWA6AEZRTv", "reviewer": "Reviewer_5Mv7", "summary": "This paper is about evaluating graph datasets with the goal of finding good datasets. They argue that  for good datasets, graph structure and node features should have two properties: (P1) they should be task-relevant; (P2) they should contain complementary information. To test this, they propose creating dataset perturbations and measuring their impact: on model performance (P1); or complimentarity of structure and features (P2). By testing a variety of different datasets, the authors make suggestions for how certain datasets should be used in the future.\n\n## update after rebuttal\nSee my rebuttal comment: This is a good paper that should be accepted -- no changes to my review.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your perceptive comments and your support of our work. In the following, we address the points raised under “Weaknesses” (W1–W4) and “Other Comments Or Suggestions” (Q1–Q4). The point raised under “Methods and Evaluation Criteria” is addressed with W4.\n- **W1 (Accounting for edge features).**  \n  We agree that extending our framework to account for edge features would be valuable and will add this to “Future Work” (after ll. 431–434r) in the updated version of the manuscript.   \n- **W2 (GNN training code).**  \n  - We did not originally include the GNN training code in the reproducibility materials (mostly because the framework itself is already quite hefty) but have now added it to a separate folder (`gnn-training`) in the anonymously shared repository. We will include this code in our public reproducibility package (instead of the stripped-down `src`).  \n  - Consistent with our measurement setup, edge features were not taken into account in our experiments, and we will clarify this in the updated manuscript. Note also that not all datasets have edge features to begin with, not all architectures can take them into account, and the PyG implementations of GAT, GCN, and GIN ignore them by default.   \n- **W3 (Recommendations/taxonomy).**  \n  In a nutshell, our recommendation is “realign” for datasets that do not exhibit performance separability, yet exhibit favorable mode diversity (derived from mode complementarity). In this scenario, there exists interesting variation in the data that graph-learning models can be challenged to leverage in their predictions. However, the existing relationship between this variation and the prediction target, to the extent that it can be picked up by the architectures examined, does not provide a significant performance advantage over settings in which this relationship is deliberately destroyed.    \n  “Realignment”, then, collectively denotes several potential operations, including (1) changing the benchmark setting (e.g., datasets with good feature diversity, such as MUTAG or AIDS, could serve as benchmarks for graph-free ML methods), (2) changing the prediction targets (e.g., using different categories to classify discussion threads in Reddit-B and Reddit-M), (3) amending the graph structure (if the dataset lacks structural diversity; this connects to the discussion on graph rewiring), and (4) amending the features (if the dataset lacks feature diversity, as is the case for DD). We will expand the “Dataset Taxonomy” section to clarify our recommendations and their derivation in the updated manuscript.  \n- **W4 (ZINC-12k dataset).**  \n  Thank you for this suggestion. Since the task associated with ZINC-12k is graph regression, which is commonly evaluated with MAE (rather than accuracy or AUROC), we will take the opportunity to showcase the ability of RINGS to handle graph-regression tasks and include not only ZINC-12k but also two other graph-regression datasets, QM9 and ZINC-250k, adding a separate one-column plot with the graph-regression results to complement Figure 3 (_experiments in progress_). Note that the ZINC-12k dataset (and also QM9 and ZINC-250k) are largely “saturated” (i.e., progress has stalled at low levels of MAE), and it is known that they do not always necessitate a graph-based model, such that we expect high overall performance levels and low performance separability. Thus, we additionally aim to provide results for more challenging molecular benchmark datasets like MOSES and GuacaMol.  \n- **Q1 (Definition 2.4).**  \n  We originally adopted the uppercase notation to distinguish individual mode perturbations from perturbations applied to a whole dataset but will change this to lowercase following your suggestion. We will also add “and a mode perturbation $\\varphi$\" after “attributed graphs” in l. 114r of the revised manuscript.   \n- **Q2 (Definition 2.9).**  \n  While our experiments focus on perturbations that affect either the graph structure or the node features, we deliberately designed our framework to be more general, accommodating also perturbations that would require joint lifts of the structure and the features (as these might help isolate model contributions or dataset characteristics in future work). We will clarify this in the updated manuscript.  \n- **Q3 (Handling of categorical node features).**  \n  Correct. To match the setup encountered by most graph-learning models, we use the node-feature encodings provided by PyG, which one-hot-encodes categorical node features by default. However, we also appreciate that the one-hot handling of non-metric attributes in most standard graph-learning frameworks itself may not be ideal, and our framework can easily accommodate other distance metrics.   \n- **Q4 (Reference numbers).**  \n  Thank you for this suggestion, which we will implement in the updated manuscript.\n\nWe hope that our responses addressed your concerns and are happy to answer further questions.", "claims_and_evidence": "The claims are well support by evidence. The theoretical claims / assumptions (P1, P2) make intuitive sense. The measurement of these properties is done by an expertly designed experiment.", "methods_and_evaluation_criteria": "The proposed methods (of measuring the impact of P1 / P2) make sense. In, particular the authors base their claims on statistical significance testing, a practice which more machine learning papers should adopt.\n\nThe methods and evluation make sense for the goal. Datasets were chosen carefully to cover different domains. Finally, the way GNN hyperparameters were tuned seems remarkably fair (and compute intensive). I have nothing to criticize of the overall experimental design.\n\nHowever, I feel like the authors could have also investigated the `ZINC` (12k) dataset. As it is used in almost every GNN expressivity paper. Thus, the authors could strengthen and extend the impact of their work by also including this dataset.", "theoretical_claims": "I only skimmed the small proofs in the appendix as they do not have a large impact on this work.", "experimental_designs_or_analyses": "Yes, the design of measuring P1 and P2 makes sense.", "relation_to_broader_scientific_literature": "The relation to existing GNN literature is fairly discussed.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "**Strengths:**\n- (S1) Our understanding of graph datasets is severely lacking. This work represents an important first step of doing this.\n- (S2) The work is built on simple (and in my opinion correct) assumptions (P1, P2). The proposed methods are simple, elegant and easy to understand.\n- (S3) The evaluation procedure is extensive (many datasets), fair (extensive hyperparameter tuning) and is based on statistical significance testing.\n- (S4) Paper is well written, clear and has a good layout.\n\n**Weaknesses:**\n- (W1): Edge features. This work does not take edge features into account. \n- (W2): Code for GNNs. As far as I can tell, the released code does not include the training code for the GNNs? This makes it difficult to evaluate this part of the work. In particular, I am interested whether GNNs where trained without taking edge features into account (as this would best align with the framework).\n- (W3): The Recommendations (Dataset Taxonomy). One of the key contribution of this work are its recommendations on how to to move forward with how we use datasets (Section 4.3).  This is in my opinion, the most important, impactful and interesting part of this work. However, Section 4.3 is remarkably small and does not properly explain its recommandations. This is particularly problematic for the case of `realigning` datasets, as it is not clear to me what the authors mean by this (e.g. `better data modeling` is very abstract).\n- (W4): ZINC (see Methods And Evaluation Criteria).\n\n**To sum up,** this is a good paper that should be accepted.", "other_comments_or_suggestions": "- Definition 2.4 should define that $\\varphi$ is a perturbation. It might be easier for the reader to notate a dataset $\\mathcal{D}$ perturbed by $\\varphi$ as $\\varphi (\\mathcal{D})$ instead of $\\Phi (\\mathcal{D})$.\n- Definition 2.9: `lifts that take in either structure-based distances arising from G or feature-based distances arising from X`. To me it seems like you intend to create the metric space only from structure or only from the features. However, this definition allows for a combination of both as well, contradicting the explanation.\n- You use euclidean distance on node features as a metric. For categorical features, in my opinion this only makes sense if they are one-hot encoded,  is that the case?\n- The justifications in the proof of Theorem 2.15 are excellent as they make it easier for the reader to understand the proof. Unfortunately, they reference line numbers that are not part of the proof. As an alternative you could but the reference number on top of the $=$ signs (e.g. $\\stackrel{\\text{7}}{=} 1- ||D_{d_F}||_{1,1} $).", "questions_for_authors": "See previous points.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces a principled and well-motivated framework, RINGS, for evaluating the quality of graph-learning datasets through mode perturbations and dataset ablations. The authors propose novel metrics—performance separability and mode complementarity—to assess dataset utility from both structural and feature perspectives. The paper is clearly written, methodologically rigorous, and backed by extensive experiments on a wide range of benchmarks. The reviewers consistently praise the conceptual novelty, careful experimental design, and actionable insights for dataset curation and model evaluation. While suggestions were made regarding broader task coverage (e.g., node-level tasks, edge features) and additional metrics, the authors provided thoughtful and detailed rebuttals along with plans to incorporate improvements into the final version. Given the significance of the problem and the quality of the contribution, I recommend acceptance.
Decision: Accept (poster)