Research map / Graph learning / GNN architectures
Generative 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.
Introduces G²PM, a message-passing-free Transformer that tokenizes graphs into random-walk substructure sequences and pre-trains with masked substructure modeling against an EMA target encoder, showing scaling on node, link, and graph tasks.
Problem
GNNs built on message passing suffer from limited expressiveness, over-smoothing, over-squashing, and poor long-range modeling, so they do not scale with data or model size; generative Transformer pre-training has not transferred to graphs.
Approach
Represent any graph instance (node, edge, or graph) as a sequence of random-walk substructure tokens encoded by a Transformer, then pre-train a Transformer encoder-decoder by masked substructure modeling, reconstructing EMA-encoder embeddings of masked walks rather than low-level features.
Key results
- On ogbn-arxiv linear probing, G2PM reaches 72.31% accuracy at 60M parameters, while GraphMAE and BGRL degrade with scale; G2PM ranks second overall on node classification (average rank 2.0) behind supervised GPM.
- On ogbn-products G2PM reaches 80.56 vs. 79.33 for the next best self-supervised method (GraphMAE 2).
- G2PM achieves the best linear-probe results on all seven graph classification datasets, e.g., HIV 78.7 vs. 77.8 for GraphMAE.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| pre-train with G²PM rather than use G²PM without pre-training (ablation) | G²PM · ogbn-arxiv | accuracy: 69.64 ± 0.08 -> 72.31 ± 0.07 | Helped |
| pre-train with G²PM rather than use G²PM without pre-training (ablation) | G²PM · HIV | accuracy: 69.8 ± 0.1 -> 78.7 ± 0.1 | Helped |
| increase hidden dimension to 768 (ablation) | G²PM · ogbn-arxiv | accuracy: 68.2 -> 72.3 | Helped |
| replace Transformer substructure encoder with GRU (ablation) | G²PM · ogbn-arxiv | accuracy: 72.3 -> 63.4 | Hurt |
| add node positional embeddings (ablation) | G²PM · ogbn-arxiv | accuracy: 72.3 -> 72.4 | No clear effect |
| replace learnable mask token with fixed token (ablation) | G²PM · ogbn-arxiv | accuracy: 72.3 -> 71.8 | Hurt |
| replace learnable mask token with random token (ablation) | G²PM · ogbn-arxiv | accuracy: 72.3 -> 67.6 | Hurt |
| remove mixed augmentation (ablation) | G²PM · ogbn-arxiv | accuracy: 72.3 -> 70.8 | Hurt |
| replace EMA semantic target with mean-pooled feature target (ablation) | G²PM · HIV | accuracy: 78.7 -> 73.5 | Hurt |
| replace L2 loss with L1 loss (ablation) | G²PM · HIV | accuracy: 78.7 -> 72.3 | Hurt |
| add topological reconstruction objective (ablation) | G²PM · ogbn-arxiv | accuracy: 72.3 -> 72.9 | Helped |
| remove EMA update for the online encoder (ablation) | G²PM · ogbn-arxiv | accuracy: 72.3 -> 25.2 | Hurt |
Surprising findings
- Without pre-training, G2PM performs competitively on small graphs (e.g., Pubmed 83.9, WikiCS 78.5), and pre-training matters mainly on larger datasets like ogbn-arxiv and ogbn-products.
- Positional embeddings (Laplacian PE, random walk PE) gave no consistent gain, and removing the EMA target update causes collapse (ogbn-arxiv accuracy 25.2).
Limitations
- Substructure sequences are treated as unordered, so the approach relies on masked-token prediction rather than next-token generation.
- Performance on heterophilous graphs such as Actor shows no clear dependence on receptive field size, and gains on small graphs come mostly without pre-training.
- Random-walk PE and Laplacian PE did not help, and the tokenizer is fixed rather than learnable.
Experimental setup
Datasets: Pubmed Photo Computers WikiCS Flickr ogbn-arxiv ogbn-products HIV PCBA Sider MUV ClinTox
Benchmarks: ogbn-arxiv ogbn-products Pubmed Photo Computers WikiCS Flickr HIV PCBA Sider MUV ClinTox
Metrics: accuracy Hit@20 Hit@50 average rank
Baselines: GAT GPM GCA BGRL CCA-SSG GraphMAE GraphMAE 2 S2GAE Bandana GIN GraphCL JOAO
Builds on: GraphMAE GPM masked autoencoders BERT-style masked language modeling
Closest papers by meaning
- Beyond Message Passing: Neural Graph Pattern Machine (ICML 2025 · similarity 0.92)
- Evaluating Graph Generative Models with Contrastively Learned Features (NeurIPS 2022 · similarity 0.90)
- Fine-Tuning Graph Neural Networks by Preserving Graph Generative Patterns (AAAI 2024 · similarity 0.90)
- Graph Generative Pre-trained Transformer (ICML 2025 · similarity 0.90)
- Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence (ICML 2025 · similarity 0.89)
- Towards Addressing Frontiers in Graph Generation (AAAI 2025 · similarity 0.89)
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.