Measuring Structure in Graph Benchmark Datasets Using Graph Invariants

Source: arxiv.org/abs/2605.06462

Richard von Moos, Mathieu Alain, Bastian Rieck

arXivarxiv/2605.06462May 7, 2026cs.LGscore 0

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…

JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2605.06462
curl -X POST /api/v1/records/arxiv/2605.06462/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.06462/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'