Pattern can be solved by memorizing past examples in graph tasks
PATTERN Can Be Solved from Memory: Generator-Aware Baselines for Synthetic Node Classification
Machine Learning
Summary
This paper looks at a popular test called PATTERN, where computers try to find specific small shapes inside larger random networks. The authors found that just remembering the exact patterns seen during training, without learning new models, beats the best existing computer methods in identifying these shapes. When testing on new, unseen patterns, models trained on repeated patterns do worse than a simple pattern-blind approach. The authors suggest testing with fresh patterns and providing baseline methods based on how patterns are generated.
What this means in practice
- •For graph algorithm developers: Assess graph model performance using fresh patterns and generator-based baselines to ensure genuine generalization beyond memorization.
- •For machine learning benchmarking teams: Design synthetic node classification benchmarks that differentiate between memorization and learning by including unseen pattern evaluation.
Authors
Amin Najafgholizadeh, Mohsen Afsharchi
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.