Separating Memorization from Selective Reporting in Graph Classification Benchmarks

Graph classification benchmarks such as MUTAG, PROTEINS and COX2 are small, and many of their graphs are copies or near-copies of one another. When a test graph has a near-twin in the training set, a model can score well by recalling the twin's label instead of generalizing. At the same time, published results on these benchmarks are filtered the way all literatures are: methods that beat the baseline get written up, and the datasets and seeds that flatter a method get reported. Both effects push reported accuracy up, and both look strongest on the smallest datasets. The standard publication-bias diagnostic, which asks whether imprecise results report larger effects than precise ones, therefore cannot tell them apart. This note proposes to measure the first effect directly with graded graph distances and then use it as a known covariate in a publication-bias analysis of the published benchmark literature. The question is whether the "small datasets report bigger gains" pattern survives once memorization is accounted for.

The key move is to treat the graph-isomorphism toolbox as a source of measurable heterogeneity. Meta-scientists usually cannot observe heterogeneity: funnel asymmetry can come from real between-study differences rather than suppression, and that confound is one of the main open problems in the publication-bias direction. Here a large part of the heterogeneity can be computed. A continuous relaxation of isomorphism testing gives every test graph a distance to its nearest training graph. Retraining with those near neighbors removed then shows how much accuracy depended on them.

Core Claim

Reported accuracy gains on small graph classification benchmarks mix three things: real generalization, memorization of near-isomorphic training neighbors, and selective reporting. We claim the second can be estimated per dataset and per method family from a counterfactual retraining experiment. We further claim that putting this estimate into a selection model fitted to published results will substantially reduce, but not eliminate, the precision–effect asymmetry that a naive test finds. Whatever asymmetry remains is the better estimate of selective reporting. Either outcome is informative. If the asymmetry vanishes, much of the apparent bias in this literature is leakage. If it persists, the field has a reporting problem that cleaner splits alone will not fix.

What Prior Work Gives Us and Leaves Open

The motivating evidence is Understanding Isomorphism Bias in Graph Data Sets. It audited 54 benchmarks with the exact isomorphism tool nauty and found that over 80% of datasets contain at least 10% isomorphic graphs. It also found that duplication can inflate reported accuracy by as much as 5%, and that "peering" models which simply memorize training labels often beat GNNs and kernels. That audit is binary: two graphs are either identical or not. Its own MUTAG result shows how brittle this is, since adding node labels drops the detected duplicate share from 42% to 19%. It also never connects inflation to the published record. We keep its question and replace the yes/no test with a distance, and we add the step from dataset audit to literature-level inference.

The distances come from the continuous-isomorphism line. Weisfeiler-Lehman Meets Gromov-Wasserstein turns the Weisfeiler-Lehman color-refinement test, which repeatedly relabels each node by the multiset of its neighbors' labels, into an optimal-transport distance $d_{WL}$. It also gives a cheaper lower bound $d_{WLLB}$ costing $O(n^3 \log(kn))$. The paper constrains our design as well: its normalization makes small and large graphs with the same local structure indistinguishable, so we append graph size and degree as node attributes. Wasserstein Weisfeiler-Lehman Graph Kernels computes Earth Mover's distance between clouds of WL node embeddings. Fine-grained Expressivity of Graph Neural Networks and Position: Future Directions in the Theory of Graph Machine Learning argue that binary equivalence jumps discontinuously under a single edge change, which is exactly why exact deduplication undercounts near-twins. None of these papers looks at evaluation leakage or reporting.

The inference side reuses selection models. Testing for publication bias in meta-analysis under Copas selection model models the chance that a study is reported as a function of its effect and precision. It handles the parameter that disappears under the null with a supremum score test and a parametric bootstrap. A Robust Bayesian Copas Selection Model for Quantifying and Correcting Publication Bias adds heavy-tailed effect distributions and a Hellinger-distance shift measure $D$. A regression-based method for detecting publication bias in multivariate meta-analysis shows how to borrow strength across correlated outcomes, which we need because one paper reports on several datasets. Two closer ML-meta-science papers frame the gap. Unraveling overoptimism and publication bias in ML-driven science separates an overfitting term from a publication threshold in reported accuracy, but its overfitting term is a fitted $\zeta n^{-0.5}$ curve. Our inflation term is measured from the data's own structure. Dead Science Walking: Publication Bias and the AI Scientist Pipeline shows reporting bias compounding in automated pipelines; it motivates the stakes but supplies no method we reuse.

Research Program

The first component is a leakage map for each benchmark. For each test graph $g$ in a split, we compute its nearest-training-neighbor radius

$$r(g) = \min_{h \in \text{train}} d(g, h),$$

where $d$ is one of several graph distances. We also record whether that nearest neighbor shares $g$'s label. To keep this tractable on datasets with thousands of graphs, we prefilter candidates with cheap WL-histogram distances and compute $d_{WLLB}$ only on each graph's top candidates. TU graphs are small, so this is feasible.

The second component is the counterfactual inflation estimate, which is the core measurement. Plotting accuracy against $r(g)$ alone would be misleading, because test graphs with no near-twin may simply be harder. Instead, for a radius $\varepsilon$, we retrain each method after deleting every training graph within $\varepsilon$ of some test graph. We then compare accuracy on those affected test graphs with a control run that deletes the same number of randomly chosen training graphs:

$$I(\varepsilon) = \text{acc}_{\text{random removal}} - \text{acc}_{\text{neighbor removal}}.$$

The random-removal control holds training-set size fixed, so $I(\varepsilon)$ isolates the contribution of near-twins. We compute it for each dataset and method family. The families are WL kernels, WWL, GIN-style message-passing networks, and the nearest-neighbor "peering" model. Separate families matter because memorization capacity differs across them.

The third component is a corpus of published results on the TU datasets named below, built by extracting reported mean accuracy and spread from papers. The effect for each result is reported accuracy minus a fixed reference method on the same dataset, and its standard error comes from the reported fold variance or, failing that, from test-set size. We fit a Copas-type selection model with the inflation estimate for that dataset and method family as a covariate on the mean effect. We use the score test of Testing for publication bias in meta-analysis under Copas selection model for detection and the heavy-tailed variant for correction. Results from the same paper are treated as correlated outcomes.

The fourth component is a ground-truth test of the whole pipeline. Real literatures have no registry of unpublished results. We can build one: run every method across many seeds, splits and datasets ourselves, so that all results are observed. We then simulate selective reporting by keeping only results that beat the reference, or only the best seed per dataset. This plays the role that the FDA antidepressant registry plays for clinical meta-analysis, and it tells us whether the adjusted test recovers the injected selection without mistaking leakage for it.

Baselines

The do-nothing reference is the published or random-split accuracy taken at face value, with no deduplication and no bias test. For the strongest existing graph methods on continuous-attribute data, Wasserstein Weisfeiler-Lehman Graph Kernels reports 84.42% accuracy on BZR and 78.29% on COX2. We rerun WWL under our splits and expect to reproduce these numbers to within fold noise before measuring any inflation. For $d_{WL}$ and $d_{WLLB}$, Weisfeiler-Lehman Meets Gromov-Wasserstein shows them matching or beating WWL in figures; the file contains no tabulated per-dataset accuracies for these, so no reported result was found on Lacuna for exact $d_{WL}$ numbers.

The strongest existing leakage baseline is exact deduplication with nauty as in Understanding Isomorphism Bias in Graph Data Sets, which reports inflation up to 5%. We run it on identical splits and compute its inflation as the accuracy change after removing exact duplicates. Graded distances beat it if neighbor removal at some $\varepsilon > 0$ produces a significantly larger $I(\varepsilon)$ than exact removal, relative to the random-removal control, on most datasets. The key ablation pits binary against graded distance. Within the graded distances, we compare a cheap WL-subtree histogram distance with WWL and $d_{WLLB}$ under the same retraining budget. A second ablation compares label-aware and label-free distances, which addresses the MUTAG 42%-to-19% sensitivity.

On the inference side, the baselines are Egger's regression, Begg's rank test and trim-and-fill applied to the published corpus. Empirical Comparison of Publication Bias Tests in Meta-Analysis found that, on Cochrane data, Egger flags 13.5% to 15.7% of meta-analyses while Begg and trim-and-fill flag 6.7% to 8.2%, with Begg–Egger agreement κ < 0.5. The Copas score test without the leakage covariate is the strongest competitor, since it detected bias that Egger missed in the chewing-gum example (p = 0.03 versus p = 0.12). All tests see the same corpus. In the simulated-registry study, the adjusted model beats them if it holds nominal false-positive rates when only leakage is present and keeps detection power when selection is injected. The unadjusted tests should then show a high false-positive rate under leakage alone.

Why not just…?

Why not just deduplicate with nauty and rerun? Exact isomorphism misses graphs that differ by one edge or one attribute value. The MUTAG drop from 42% to 19% when labels are added shows how much the count depends on representation choices rather than on structure. Deduplication also does nothing about the existing published record. The binary-versus-graded ablation directly measures how much inflation exact matching leaves behind. If that residual is near zero on most datasets, the graded part of this proposal is unnecessary and we will say so.

Why not just use cheap WL color histograms instead of optimal-transport distances? This is a real threat. A histogram distance over a few WL iterations may find near-twins about as well as $d_{WLLB}$ at a fraction of the cost. Weisfeiler-Lehman Meets Gromov-Wasserstein and Wasserstein Weisfeiler-Lehman Graph Kernels give reasons to expect transport to resolve finer differences, but that evidence concerns classification, not leakage detection. The proposal's claim therefore does not depend on optimal transport. The contribution is the counterfactual inflation measurement and its use as a covariate. If the cheap distance yields the same $I(\varepsilon)$, it becomes the recommended tool.

Why not just run Egger's test on published accuracies? Precision in this literature tracks dataset size, and small datasets are also the most duplicate-heavy, so Egger's test confounds leakage with suppression. This is the heterogeneity problem the publication-bias literature names but usually cannot observe, and the poor test agreement reported in Empirical Comparison of Publication Bias Tests in Meta-Analysis shows how fragile scalar tests are. The simulated-registry experiment settles this by injecting leakage without selection and counting how often each test raises a false alarm.

Why not just fix splits going forward? Leakage-aware splits are a good outcome of this work, but they do not reinterpret a decade of reported progress. They also do not remove selective reporting, which the residual asymmetry estimate targets separately.

Proposed Experiments

The benchmarks are MUTAG, PROTEINS, PTC-FM, PTC-MR, COX2, BZR, IMDB-B and IMDB-M, the sets evaluated in the WWL and $d_{WL}$ papers. We include them because the isomorphism audit flags their duplication. The first decisive check is whether $I(\varepsilon)$ is significantly positive for the peering model and the WL kernel on the duplicate-heavy datasets, measured over repeated splits. We expect it to be smaller for methods with less capacity to memorize, and that ordering is a falsifiable prediction. The second check, on the simulated registry, is whether the leakage-adjusted selection model keeps its false-positive rate near nominal under leakage-only scenarios where unadjusted Egger and Copas do not. The third check, on the published corpus, is the headline result: how much of the naive precision–effect slope disappears once the inflation covariate is added, and whether the remaining selection parameter is still detected by the supremum score test with bootstrap p-values.

The main risk is the quality of the corpus. Reported spreads are inconsistent, and some papers tune on test folds. We will code evaluation protocol as an additional moderator and report results separately for papers that do and do not state their protocol. A null result is still worth publishing: if leakage-adjusted asymmetry is indistinguishable from zero, the field's apparent reporting bias on these benchmarks is mostly a dataset artifact, and that changes what should be fixed.