Graph models are increasingly pre-trained on pooled collections of graphs drawn from many domains: molecules, proteins, social ego-networks, and collaboration graphs. They are then evaluated on downstream benchmarks drawn from the same domains. Nobody checks whether the test graphs, or near-copies of them, were already in the pre-training pool.
In text, this problem has a name, benchmark data contamination, and a toolkit of detection methods. Graphs break that toolkit, because there is no n-gram to match. The same molecule can be stored under any node ordering, and two molecules that differ by one bond are "different" to a string matcher but nearly identical to a model. We propose to measure graph contamination by structural distance rather than string identity. We will then use controlled injection experiments to establish how much each level of structural overlap inflates downstream scores, and whether that inflation depends on the kind of graph domain.
The concrete deliverables are an audit, a causal estimate, and a protocol. The audit asks how close downstream test graphs sit to a realistic multi-domain pre-training pool. The causal estimate asks how many points a test graph gains from having an exact or near-duplicate in pre-training, broken down by domain. The protocol is a contamination-stratified way of reporting results, together with a decontamination rule calibrated by the injection results rather than by convenience.
Core Claim
The closest prior work, Position: Graph Matching Systems Deserve Better Benchmarks, shows that graph-similarity benchmarks such as LINUX, IMDB and AIDS leak isomorphic graphs between their own train and test splits. It reports 94.8% cross-train-test-pair leakage on LINUX. When those leaked pairs are filtered out, ISONET's mean squared error on LINUX rises from 0.323 to 5.146. That paper studies one task, graph edit distance, within one benchmark's splits, and only for exact isomorphism.
Our claim differs on three axes. First, contamination in the pre-training era is cross-dataset: a molecule in ogbg-molhiv may also appear in ZINC250K or ChEMBL. Second, contamination is graded rather than binary. Near-duplicates, such as one or two edits away or a shared scaffold, may inflate scores almost as much as exact copies. If so, exact isomorphism filtering of the kind used in the Position paper is not sufficient. Third, the size of the inflation should depend on domain structure.
The third claim has a specific source. Memorization in Graph Neural Networks finds memorization near 0% on homophilic graphs, where connected nodes tend to share labels, such as Cora and PubMed. It finds memorization above 50% on heterophilic graphs, where neighbors tend to differ, such as Squirrel and Chameleon. If that result transfers from training-set memorization to pre-training overlap, contamination should matter most exactly where structure is least informative.
Research Program
We define the contamination distance of a test graph $G$ as
$$d(G) = \min_{H \in \mathcal{P}} \mathrm{dist}(G, H),$$
where $\mathcal{P}$ is the pre-training pool. The distance measure $\mathrm{dist}$ is a ladder of increasingly loose matches, each a superset of the previous one:
- an exact isomorphism check;
- equality of Weisfeiler–Lehman hashes, a fast fingerprint that iteratively relabels each node by its neighbors' labels;
- approximate graph edit distance of at most $k$;
- for molecules, a shared ring scaffold.
This ladder plays the role of the four contamination levels in Benchmark Data Contamination of Large Language Models: A Survey. That survey separates exposure to similar topics, to metadata, to unlabeled test items, and to labeled test items. We add a label axis: whether the matched pre-training graph carried the same property label, or only its structure.
The pre-training pool. We build it from the multi-domain collection in GraphGT, which curates 36 datasets across 9 domains. From it we take:
- QM9, ZINC250K, MOSES and ChEMBL as molecular sources;
- Protein and Enzyme as biological sources;
- Ego and CollabNet as social sources.
The audit. The audit computes $d(G)$ for every test graph in five downstream benchmarks: ogbg-molhiv, NCI1, Mutagenicity, AIDS and IMDB-MULTI. Its output is a per-domain distribution of contamination distances.
Why injection is needed. A naive comparison of scores on near and far test items is confounded. Near-duplicate test graphs are also more in-distribution, so they may be easier for reasons that have nothing to do with leakage. We therefore run a controlled experiment.
We start from a pool that has been cleaned at the loosest rung of the ladder. We then inject a held-out subset of test graphs back into it at known rates $r$ and at a chosen rung: exact copies, WL-equivalent relabelings, $k$-edit perturbations, or scaffold siblings. Labels are injected either with or without the graphs. We pre-train self-supervised models on each pool and measure the injection gain
$$\Delta(r, \ell) = S_{\text{injected}}(r, \ell) - S_{\text{clean}},$$
where $S$ is the downstream score on the injected items and $\ell$ is the rung of the ladder. The comparison is made against the same items under the clean pool. This mirrors canary insertion in text-contamination work, but the items are structurally varied rather than verbatim.
Models. We use the self-supervised models benchmarked in GraphFM. Its contrastive models are BGRL, CCA-SSG and GCA. Its generative models, which pre-train by reconstructing masked parts of the graph, are GraphMAE and S2GAE. GraphFM found that generative models excel at feature-driven tasks and contrastive models excel at relational tasks. That contrast lets us test whether reconstruction objectives memorize injected structure more readily.
Node-level arm. A smaller arm tests the homophily hypothesis directly. We use syn-cora, a synthetic version of Cora with controlled homophily. We inject test-node ego-networks, the subgraph around each test node, into pre-training and track $\Delta$ as homophily is varied.
Baselines
Naive reference. Pre-train on the uncleaned pooled corpus and report downstream scores the way current multi-domain graph pre-training papers do. This is the number the field currently trusts. Any contamination gain we find is measured against it.
Exact isomorphism filtering. This is the strongest existing method. It removes every pre-training graph that is isomorphic to a test graph, operationalized as in Position: Graph Matching Systems Deserve Better Benchmarks. That paper reports a jump in ISONET mean squared error from 0.323 to 5.146 on LINUX after filtering. We run it on the same pool, with the same models and the same 20-configuration random hyperparameter budget. That budget follows Overcoming Pitfalls in Graph Contrastive Learning Evaluation, which showed that tuning self-supervised models on downstream labels inflates results. No reported result was found on Lacuna for exact-isomorphism decontamination of multi-domain pre-training on ogbg-molhiv, NCI1 or IMDB-MULTI. We will establish that number ourselves.
Our graded filter beats exact filtering if a substantial share of the inflation survives it. Concretely, beating it means two things: injected WL-equivalent or $k$-edit variants produce a statistically reliable $\Delta$ across seeds, and removing them changes the clean score by more than seed variance.
Per-item membership inference. This baseline asks the model itself whether it has seen an item. We adapt the leave-one-out confidence gap of NCMemo from Memorization in Graph Neural Networks. It is the natural competitor for detecting contamination when the pre-training pool is unknown. We score it by how well it ranks the injected items above non-injected ones, measured as area under the ROC curve. Distance-based audit wins if it detects injected items at lower false-positive rates when the pool is available. Membership inference earns its place if it works when the pool is not available.
Ablation of the key ingredient. We collapse the distance ladder to its exact-match rung. This isolates whether grading by structural distance is what carries the result.
Why not just…?
Why not just deduplicate with canonical SMILES or Weisfeiler–Lehman hashes? This is the real threat. If injected near-duplicates produce no measurable $\Delta$ beyond exact copies, cheap hashing is sufficient, and we will say so. The prediction that it is not sufficient rests on indirect evidence. Can LLMs Effectively Leverage Graph Structural Information through Prompts, and Why? shows models exploit neighbor similarity rather than exact structure: LLM accuracy fell only 0.25% under rewiring, against 5.55% for message-passing networks. The $k$-edit and scaffold-sibling injection arms settle the question directly.
Why not just use temporal cutoff splits like arxiv-2023? Temporal splits need timestamped text. Molecules in ZINC, protein graphs and ego-networks have no meaningful release date relative to a pre-training crawl. The same survey (Benchmark Data Contamination Survey) also notes that such splits expire as soon as newer crawls are used for training.
Why not just evaluate on freshly generated synthetic graphs, as DyVal or GraphOmni do? DyVal and GraphOmni generate graphs from random families, such as Erdős–Rényi or DAG generators, and pose algorithmic questions. That avoids leakage but answers a different question. Whether a pre-trained model predicts HIV activity on real molecules cannot be measured on Erdős–Rényi graphs. Our goal is to make real-domain benchmarks trustworthy, not to replace them.
Why not just use training-free heuristics, which cannot be contaminated? Link Prediction Without Learning shows heuristics are strong for link prediction. Its authors concede they do not cover graph classification or transferable representations, which are the tasks at issue here.
Proposed Experiments and Decisive Checks
The audit. The first experiment is the audit itself: the share of test graphs in ogbg-molhiv, NCI1, Mutagenicity, AIDS and IMDB-MULTI at each rung of the distance ladder against the GraphGT-derived pool. We expect small molecules and small ego-networks to show high overlap, since the Position paper already found heavy isomorphic repetition within IMDB and AIDS.
The injection grid. The second experiment crosses four factors:
- injection rate $r$ of 0, 1%, 5% or 20% of held-out test items;
- rung of the ladder;
- labels present or absent;
- model family, generative or contrastive.
Each cell uses five seeds and the fixed 20-configuration hyperparameter budget. The primary metric is ROC-AUC for ogbg-molhiv and accuracy elsewhere, reported as $\Delta$ with confidence intervals.
Decisive checks. Three outcomes decide the main claims:
- Graded contamination. The claim requires that $\Delta$ at the $k$-edit or scaffold rung is non-zero and at least a sizable fraction of the exact-copy $\Delta$. If it is near zero, exact deduplication suffices.
- Domain dependence. The claim requires that $\Delta$ is larger for generative than contrastive pre-training, and larger for low-homophily syn-cora than high-homophily syn-cora. A flat $\Delta$ across homophily would falsify the transfer of the memorization result from Memorization in Graph Neural Networks.
- Ranking changes. We check whether the ranking of the five GraphFM models on the downstream benchmarks changes between the naive pool and the graded-clean pool. A ranking change would be the practical evidence that current multi-domain graph benchmarks report inflated comparisons.
References
- Position: Graph Matching Systems Deserve Better Benchmarks
- Memorization in Graph Neural Networks
- Benchmark Data Contamination of Large Language Models: A Survey
- GraphGT: Machine Learning Datasets for Graph Generation and Transformation
- GraphFM: A Comprehensive Benchmark for Graph Foundation Model
- Overcoming Pitfalls in Graph Contrastive Learning Evaluation: Toward Comprehensive Benchmarks
- Can LLMs Effectively Leverage Graph Structural Information through Prompts, and Why?
- DyVal: Dynamic Evaluation of Large Language Models for Reasoning Tasks
- GraphOmni: A Comprehensive and Extensible Benchmark Framework for Large Language Models on Graph-theoretic Tasks
- Link Prediction Without Learning