PATTERN Can Be Solved from Memory: Generator-Aware Baselines for Synthetic Node Classification

arXiv:2610.15020 · cs.LG · Submitted 2026-10-10 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "PATTERN Can Be Solved from Memory".

Jane: The gist The matcher reaches 99.2 class-weighted accuracy with no trained parameters,

Tom: First, who's behind it and why it matters.

Title and authors: Tom: The paper's title is "PATTERN Can Be Solved from Memory: Generator-Aware Baselines for Synthetic Node Classification". It really emphasizes that the way you set up your training data, using these generators, directly impacts how well a model generalizes to new things.

Jane: And it’s about using those generator-aware baselines to give us a better picture of what models actually learn versus just memorizing the training data structure. It suggests that relying only on standard published scores isn't enough when you want to know if a model truly understands the underlying concepts or just pattern matching.

Lu: The core idea is testing whether trained models actually use the memory that comes from having different splits, which they test by drawing new graphs with fresh patterns after training on old ones. This directly addresses how much knowledge is being transferred across those splits >

Meng: From an engineering standpoint, this means if you train a model on one set of patterns and then test it on a graph with a pattern completely different from the training set, you can quantify exactly how much accuracy drops because the model isn't generalizing well. That helps us know when we need more diverse training data >

Lalam: The paper sets up tests to see if models like CKGConv or GRIT retain performance on fresh patterns versus old ones, and it shows that both of those models fall below this pattern-blind predictor when they encounter new graphs with fresh patterns >

The paper's summary: Tom: So the paper summarizes how they compare different inference methods against a baseline called a pattern-blind predictor, which scores eighty-six point eight under the generator without any specific patterns used for inference <ref:2610.15020#pg1>. It sets up some tests to see how much models depend on the patterns they were trained on.

Jane: What’s important is that when you train models like CKGConv or GRIT with a new pattern in every graph, their accuracy on fresh patterns goes up by about two points, reaching the level of that pattern-blind predictor, even though it costs them some performance on the reused patterns >

Lu: They also show how inference under the generator without the patterns reaches eighty-two point three for CLUSTER and they look at Minesweeper too, where inference from just revealed counts without training gets a very high score of ninety-nine point eight six ROC AUC, which is above every published result they found > <ref:2610.15020#pg1,inference under the generator without the patterns reaches>

Meng: That high score on Minesweeper inference from the revealed counts alone is interesting because it suggests that sometimes just looking at what you've already seen, even without full training, can give you a very good idea of what's going on in those graph structures >

Lalam: The paper also introduces methods like a likelihood matcher that reads this set of patterns off the training labels and finds induced copies with matching features in each test graph >

The paper's improvements: Tom: The authors suggest a few improvements. First, they recommend that synthetic benchmarks report scores on fresh templates alongside reused ones, which is something they felt was missing before. Second, they suggest publishing baselines built directly from their generators and clearly stating how their metric is weighted and pooled for comparison >

Jane: And a key finding they push is that training on fresh patterns raises accuracy on fresh patterns by two point zero points or two point one points over the original models, which is a paired interval above zero, showing that adapting the training protocol actually helps when you need to generalize > <ref:2610.15020#pg1,accuracy on fresh patterns by>

Lu: They also found that CKGConv can score eighty-four point five when trained with all patterns because of a paired difference of negative one point and nine hundredths compared to not having seen them, which shows a measurable deficit when withholding specific patterns during training > <ref:2610.15020#pg1>

Meng: From a deployment view, this means we should probably be thinking about how to design our training loops so that they intentionally expose the model to variations in the pattern structure, not just run it on a static set of known graphs >

Lalam: And they suggest using CLUSTER and Minesweeper inference under the generator as baselines because it establishes a benchmark for what's possible for methods that see a stated set of inputs >

Conclusion: Tom: So to wrap up, the PATTERN Can Be Solved from Memory paper shows that the matcher can hit ninety-nine point two class-weighted accuracy with no trained parameters, which beats the eighty-nine point eight of some published models > <ref:2610.15020#pg1,99.2 class-weighted accuracy with no trained parameters>

Jane: It really suggests that even without any training on a specific pattern, if you have a good way to read those patterns and look them up in a test graph, you can get very high performance >

Lu: And they found that CKGConv and GRIT both fall below the pattern-blind predictor when they encounter fresh patterns, and training with a new pattern in every graph helps them reach that blind level on fresh graphs >

Meng: The implication for us is that we need to be careful about how we train models; if we don't introduce variation in the pattern structure, their performance on new data will suffer when they see something different >

Lalam: Ultimately, the paper suggests synthetic benchmarks would say more if they reported scores on fresh templates beside reused ones and baselines built from their generators are essential for a fair comparison >

Amin Najafgholizadeh, Mohsen Afsharchi

cs.LG

Submitted: 2026-10-10

Updated: 2026-10-10

Comments: 30 pages, 4 figures

Code: https://github.com/graphdeeplearning/benchmarking-gnns

License: http://creativecommons.org/licenses/by/4.0/

The gist: The gist The matcher reaches 99.2 class-weighted accuracy with no trained parameters, against 89.8 for the best published model How it works PATTERN is a synthetic node-classification benchmark that

Key concepts

PATTERN Benchmark: A synthetic test where a random subgraph is planted in a random host graph, and the task is to identify which nodes belong to that hidden subgraph. It serves as a standard for evaluating node classification models on graph structures.
Generator-Aware Baselines: Models like CKGConv and GRIT are tested on new graphs with unseen patterns. The paper investigates how much these trained models rely on the specific patterns they were trained on versus their general understanding of graph structure.
Pattern-Blind Predictor: A baseline method that attempts to predict subgraph membership without using any learned parameters or explicit knowledge of the training labels. It serves as a benchmark to show how much performance gains can be achieved through pattern recognition.

Summary

The gist The matcher reaches 99.2 class-weighted accuracy with no trained parameters, against 89.8 for the best published model

How it works

PATTERN is a synthetic node-classification benchmark that plants a random subgraph in a random host graph and asks which nodes belong to it The generator draws 100 patterns once and plants the same ones in every split, so each test graph carries a pattern that also appears in 100 training graphs A matcher that reads these patterns off the training labels and looks them up in each test graph reaches 99.2 class-weighted accuracy with no trained parameters, against 89.8 for the best published model This matches the best published result on CLUSTER and, without any training, scores above every published result we found on Minesweeper’s released board The matcher reaches 99.2 class-weighted accuracy on the official test split, above every published model (Table 2 and Figure 2) The likelihood matcher reads this set of patterns off the training labels and finds induced copies with matching features in each test graph

Benchmark Generators

The generators for PATTERN, CLUSTER, and Minesweeper draw different structures for every graph For PATTERN, the host is a stochastic block model with five blocks of random sizes, denser within blocks than across them, and its node features are drawn uniformly The pattern is a random graph with node features of its own CLUSTER draws each graph independently from a six-block stochastic block model where in each block one randomly chosen node carries the block’s index as its feature, and the other nodes carry an uninformative feature Minesweeper is a single graph, a square grid in which each cell is joined to its eight neighbors

Model Dependencies and Transfer

The paper investigates whether trained models use the memory that the split allows by testing on new graphs with fresh patterns CKGConv (Ma et al., 2024) keeps its official accuracy on the familiar patterns but falls below the pattern-blind predictor on the fresh ones, in both seeds GRIT (Ma et al., 2023), whose official score is close to the pattern-blind level, also drops on fresh patterns Training CKGConv with a new pattern in every graph raises its accuracy on fresh patterns by about 2 points, to the level of the pattern-blind predictor, at some cost on the reused patterns The same kind of inference under the generator matches the best published result on CLUSTER and, without any training, scores above every published result we found on Minesweeper’s released board

Inference Methods and Baselines

The paper compares several inference methods against a pattern-blind predictor which reaches 86.8 (Section 4.1) The likelihood matcher reaches 99.2 class-weighted accuracy on the official test split, above every published model (Table 2 and Figure 2) The largest-match rule scores just under the range first written for it, 97 to 100, both on the first random sample and on the whole test split For CLUSTER, inference under the generator scores 82.3 (95% graph interval 81.5 to 83.0) For Minesweeper, inference from the revealed counts alone, without training, reaches 99.86 ROC AUC, above every published result we found (99.55)

Recommendations for Benchmarks

The authors recommend that synthetic benchmarks report scores on fresh templates beside reused ones They also suggest publishing baselines built from their generators and stating how their metric is weighted and pooled A key finding is that training on fresh patterns raises accuracy on fresh patterns by 2.0 and 2.1 points over the original models, with paired intervals above zero

CLUSTER and Minesweeper Inference

For CLUSTER, the posterior is over assignments of the other nodes to the six blocks given the edges and one revealed label per block under the generator’s edge probabilities, size prior, and rule for revealing labels For Minesweeper, a sampler that redraws narrow strips of rows or columns from their exact conditionals reaches 99.86 ROC AUC across the official masks when its conditional probabilities are averaged over updates and chains

Conclusion

Synthetic benchmarks would say more if they reported scores on fresh templates, baselines built from their generators, and how their metric is weighted and pooled The matcher reaches 99.2 class-weighted accuracy with no trained parameters, against 89.8 for the best published model CKGConv and GRIT fall below the pattern-blind predictor on fresh patterns, and holding patterns out of CKGConv’s training lowers its accuracy on the graphs that carry them Trained with a new pattern in every training and validation graph, CKGConv reaches the pattern-blind level on fresh patterns The same kind of inference under the generator matches the best published score on CLUSTER and, without any training, exceeds every published score we found on Minesweeper’s released board

Code and Data Availability

The code, result records, scoring programs, regenerated graphs, and held-out pattern split will be released publicly The replay rescores saved predictions; it does not retrain the neural models The code and data will be released publicly; until then they are available from the authors on request

References

Emmanuel Abbe. Community detection and stochastic block models: Recent developments. Journal of Machine Learning Research, 18(177):1–86, 2018 Eren Akbiyik, Florian Grötschla, Beni Egressy, and Roger Wattenhofer. Graphtester: Exploring theoretical boundaries of GNNs on graph datasets. In Data-centric Machine Learning Research (DMLR) Workshop at ICML, 2023. arXiv:2306.17482 AndyJZhao. Explanation of node classification tasks. GitHub issue 66, https://github.com/graphdeeplearning/benchmarking-gnns/issues/66, 2021 Björn Barz and Joachim Denzler. Do we train on test data? Purging CIFAR of near-duplicates. Journal of Imaging, 6(6):41, 2020. doi: 10.3390/jimaging6060041 Dominique Beaini, Saro Passaro, Vincent Létourneau, William L. Hamilton, Gabriele Corso, and Pietro Liò. Directional graph networks. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 748–758, 2021. arXiv:2010.02863 Maya Bechler-Speicher, Ben Finkelshtein, Fabrizio Frasca, Luis Müller, Jan Tönshoff, Antoine Siraudin, Viktor Zaverkin, Michael M. Bronstein, Mathias Niepert, Bryan Perozzi, Mikhail Galkin, and Christopher Morris. Position: Graph learning will lose relevance due to poor benchmarks. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pp. 81067–81089, 2025. arXiv:2502.14546 Blai Bonet and Hector Geffner. Factored probabilistic belief tracking. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI), pp. 3045–3052, 2016. arXiv:1909.13779 C. K. Carter and R. Kohn. On Gibbs sampling for state space models. Biometrika, 81(3):541–553, 1994 Dexiong Chen, Leslie O’Bray, and Karsten Borgwardt. Structure-aware transformer for graph representation learning. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 3469–3489, 2022. arXiv:2202.03036 Ji Chen, Song Chen, Chengzhang Gong, Li Fan, and Chao Xu. Swarm-inspired generation of collective behaviors in graph dynamical systems. arXiv:2606.24958 Gábor Csárdi and Tamás Nepusz. The igraph software package for complex network research.

Improvements for AI systems

Bold Header: Pattern-Aware Inference Engine

This system can solve PATTERN test splits by reading training labels and looking them up in test graphs, reaching 99.2 class-weighted accuracy with no trained parameters. It achieves this by using a matcher that reads the patterns off the training labels and looks them up in each test graph to rank candidates by their log-likelihood ratio against the hypothesis that every node belongs to the host.

Bold Header: Pattern-Blind Predictor Integration

The system can serve as a baseline predictor, achieving 86.8 (Section 4.1) accuracy under the generator without patterns, allowing for a comparison of how much performance is due to pattern knowledge versus general graph structure recognition. This predictor approximates the posterior using a Gibbs sampler and sets a threshold based on class counts.

Bold Header: Adaptive Training Protocol for New Patterns

The system can be trained with a new pattern in every training and validation graph to reach the pattern-blind level on fresh patterns, achieving gains of 1.97 [and] 2.12 points over original models on fresh test graphs. This demonstrates that adapting the training protocol changes the distinctness of patterns, their size, and feature makeup to improve transfer to unseen data.

Bold Header: Model Dependency Analysis

The system can quantify how much a model depend[s] on the patterns they were trained on by comparing scores on reused graphs versus fresh patterns. For instance, CKGConv can score 84.5 (a paired difference of −1.9 points) when trained with all patterns, showing a measurable deficit when withholding specific patterns during training.

Bold Header: Generator-Based Baselines

The system can establish robust baselines by using baselines built from the generators of CLUSTER and Minesweeper, scoring them under the generator's law to find the best possible score for a method that sees a stated set of inputs. This provides a more informative comparison than relying solely on published scores.

Bold Header: Metric Reporting Recommendations

The system can enforce rigorous reporting standards by recommending that benchmarks report scores on fresh templates beside reused ones, publish baselines built from their generators, and state how their metric is weighted and pooled, ensuring comparability across different scoring conventions like plain node accuracy versus class-weighted accuracy.

Abstract

PATTERN, a synthetic node-classification benchmark still used to rank graph networks, plants a random subgraph in a random host graph and asks which nodes belong to it. Its generator draws 100 patterns once and plants the same ones in every split, so each test graph carries a pattern that also appears in 100 training graphs. A matcher that reads these patterns off the training labels and looks them up in each test graph reaches 99.2 class-weighted accuracy with no trained parameters, against 89.8 for the best published model. Inference under the generator without the patterns reaches 86.8. Two published models, CKGConv and GRIT, score lower on patterns they have not seen: on new graphs with fresh patterns both fall below this pattern-blind predictor, and withholding patterns from CKGConv's training lowers its accuracy on the test graphs that carry them. Training CKGConv with a new pattern in every graph raises its accuracy on fresh patterns by about 2 points, to the level of the pattern-blind predictor, at some cost on the reused patterns. The same kind of inference under the generator matches the best published result on CLUSTER and, without any training, scores above every published result we found on Minesweeper's released board. We recommend that synthetic benchmarks report scores on fresh templates beside reused ones, publish baselines built from their generators, and state how their metric is weighted and pooled.