Research map / Graph learning / GNN architectures
Beyond Message Passing: Neural Graph Pattern Machine
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Neural Graph Pattern Machine (GPM), which bypasses message passing by sampling random-walk graph patterns, encoding semantic and anonymous paths separately, and aggregating them with a transformer that identifies important patterns.
Problem
Message passing GNNs struggle to explicitly capture substructure patterns such as triangles, cliques, and rings, limiting expressiveness, long-range dependency modeling, and interpretability across node, link, and graph tasks.
Approach
Tokenize each instance into random-walk graph patterns, encode each pattern as the joint of a semantic path (node features via transformer) and an anonymous path (loop-based adjacency via GRU), then use a transformer with a class token to weight the important patterns, with no message passing.
Key results
- GPM reaches 82.62 on Products and 92.28 on Computer node classification, best among compared methods on 8 of 9 node datasets (CoraFull is best for NAGphormer at 71.51 vs 71.23).
- On ZINC graph regression, GPM achieves MAE 0.064 vs 0.070 for the next best (GPS), and 0.021 on ZINC-Full.
- GPM distinguishes all graphs in CSL, EXP, and SR25 (100% each), where many message passing models fail.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GPM instead of the strongest listed baseline | node classification · CoraFull | accuracy: 71.51 -> 71.23 | Hurt |
| Use GPM instead of the strongest listed baseline | GPM · Products | accuracy: 82.00 -> 82.62 | Helped |
| Use GPM instead of the strongest listed baseline | GPM · Cora link prediction | Hits@20: 89.95 -> 92.85 | Helped |
| Use GPM instead of the strongest listed baseline | GPM · ZINC | MAE: 0.070 -> 0.064 | Helped |
| add positional embeddings (ablation) | GPM · Products | accuracy: 82.47 -> 82.62 | Helped |
| add anonymous path encoding (ablation) | GPM · Products | accuracy: 81.99 -> 82.62 | Helped |
| add both positional embeddings and anonymous path encoding (ablation) | GPM · Products | accuracy: 80.74 -> 82.62 | Helped |
| use Transformer rather than mean for the semantic-path encoder (ablation) | GPM · Products | accuracy: 80.42 -> 82.62 | Helped |
| use Transformer rather than GRU for the semantic-path encoder (ablation) | GPM · Products | accuracy: 80.91 -> 82.62 | Helped |
| use multi-scale pattern lengths (ablation) | GPM · average accuracy across evaluated tasks | accuracy: 70.72 to 72.34 | Helped |
| use fewer patterns in training and more at inference (test-time augmentation) (ablation) | GPM · average accuracy across evaluated tasks | accuracy: 72.43 to 72.34 | Hurt |
| use unbiased random-walk sampling instead of localized or long-range sampling (ablation) | GPM · Products | accuracy | Helped |
Surprising findings
- Message passing GNNs and RUM fail to perfectly fit TreeNeighborsMatching training data as early as radius 4, while GPM fits up to radius 7.
- Training with 16 patterns and testing with 128 yields nearly the same accuracy as training with 128 (72.34 vs 72.43 average), cutting training cost.
Limitations
- Performance depends on quality of randomly sampled patterns; random sampling may raise training and tuning cost.
- Current implementation is limited to supervised tasks.
- Some reported gains depend on a dataset-specific choice among positional embeddings, anonymous path encoders, and sampling parameters.
Experimental setup
Datasets: Products Computer Arxiv WikiCS CoraFull Deezer Blog Flickr Flickr-S Cora Pubmed ogbl-Collab
Benchmarks: Products Computer Arxiv WikiCS CoraFull Deezer Blog Flickr Flickr-S Cora Pubmed ogbl-Collab
Metrics: accuracy Hits@20 Hits@50 AUC MAE
Baselines: GCN GAT APPNP GPRGNN OrderedGNN RUM GraphGPS NAGphormer GCFormer GraphMamba GIN GMT
Builds on: anonymous walks graph transformer random walk structural embeddings Laplacian eigenvector positional encoding
Closest papers by meaning
- Generative Graph Pattern Machine (NeurIPS 2025 · similarity 0.92)
- Towards Dynamic Message Passing on Graphs (NeurIPS 2024 · similarity 0.89)
- How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension (ICLR 2025 · similarity 0.89)
- Deep Homomorphism Networks (NeurIPS 2024 · similarity 0.89)
- Homomorphism Counts for Graph Neural Networks: All About That Basis (ICML 2024 · similarity 0.89)
- Weisfeiler and Lehman Go Paths: Learning Topological Features via Path Complexes (AAAI 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.