{"id":"arxiv/2605.06462","url":"https://arxiv.org/abs/2605.06462","tags":["cs.LG","math.CO"],"score":0,"title":"Measuring Structure in Graph Benchmark Datasets Using Graph Invariants","domain":"cs.LG","source":"arxiv","authors":["Richard von Moos","Mathieu Alain","Bastian Rieck"],"reviews":0,"subject":"cs.LG","summary":"Progress in graph learning is hindered by benchmark practices that conflate the contributions of node features and graph structure, making it hard to tell whether a model actually learns from the graph, or whether it even needs to. We propose measuring this using graph invariants, i.e., permutation-invariant, task-agnostic structural descriptors. Our analysis on datasets substantiates three tacit assumptions in graph learning, namely that (i) a curated subset of invariants is more expressive than standard GNNs, (ii) benchmark datasets exhibit structural heterogeneity even when originating…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-07","reactions":{}}