Research map / Graph learning / GNN architectures
Greener GRASS: Enhancing GNNs with Encoding, Rewiring, and Attention
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 GRASS, a sparse graph transformer-style GNN combining (D-)RRWP encodings, random regular graph rewiring resampled each iteration, and a graph-tailored additive edge-based attention, reaching SOTA on several GNN benchmarks and LRGB.
Problem
GNNs struggle with long-range communication (underreaching, oversquashing), oversmoothing, and expressive structural encoding; existing graph transformers use dot-product attention ill-suited to graphs and are costly to encode structure.
Approach
Combine RRWP structural encoding (plus a truncated-eigendecomposition variant D-RRWP for efficiency), per-iteration random regular graph superimposition for rewiring, random edge removal, and an additive attention whose weights come from edge representations updated by an MLP, with alternating edge direction across layers.
Key results
- GRASS reaches MAE 0.047 on ZINC, a 20.3% reduction relative to GRIT (second best).
- GRASS achieves 83.750% on CIFAR10 and 89.177% on PATTERN, ranking first on both among compared models.
- On PascalVOC-SP GRASS reaches Macro F1 0.5670, above NeuralWalker's 0.4912.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use GRASS instead of GRIT | GNN benchmark models · ZINC | MAE: 0.059 ± 0.002 -> 0.047 ± 0.001 | Helped |
| replace RRWP with D-RRWP (ablation) | GRASS · ZINC | MAE: 0.0470 ± 0.0013 -> 0.0473 ± 0.0021 | No clear effect |
| replace RRWP with LapPE (ablation) | GRASS · ZINC | MAE: 0.0470 ± 0.0013 -> 0.0829 ± 0.0041 | Hurt |
| rewire once before training instead of every epoch (ablation) | GRASS · ZINC | MAE: 0.0470 ± 0.0013 -> 0.0645 ± 0.0015 | Hurt |
| replace GRASS attention with GAT attention (ablation) | GRASS · ZINC | MAE: 0.0470 ± 0.0013 -> 0.0592 ± 0.0023 | Hurt |
| remove random edge removal (ablation) | GRASS · ZINC | MAE: 0.0470 ± 0.0013 -> 0.0500 ± 0.0018 | Hurt |
| remove edge flipping (ablation) | GRASS · ZINC | MAE: 0.0470 ± 0.0013 -> 0.0470 ± 0.0010 | No clear effect |
| replace batch normalization with layer normalization (ablation) | GRASS · ZINC | MAE: 0.0470 ± 0.0013 -> 0.0497 ± 0.0009 | No clear effect |
| replace sum pooling with mean pooling (ablation) | GRASS · ZINC | MAE: 0.0470 ± 0.0013 -> 0.0493 ± 0.0024 | No clear effect |
| replace Lion with AdamW (ablation) | GRASS · ZINC | MAE: 0.0470 ± 0.0013 -> 0.0499 ± 0.0006 | No clear effect |
| use RRWP instead of D-RRWP (ablation) | GRASS · PascalVOC-SP | Macro F1: 0.5670 ± 0.0049 -> 0.5690 ± 0.0045 | No clear effect |
| replace D-RRWP with LapPE (ablation) | GRASS · PascalVOC-SP | Macro F1: 0.5670 ± 0.0049 -> 0.5387 ± 0.0070 | Hurt |
Surprising findings
- Fixing random rewired edges across epochs instead of resampling each epoch increases ZINC MAE by 37.2%, showing rewiring randomness matters.
- D-RRWP performs comparably to RRWP on ZINC and PascalVOC-SP but underperforms RRWP on Peptides-struct.
Limitations
- Scalability to extremely large graphs is not empirically evaluated.
- Model output is nondeterministic due to random rewiring, requiring seeding for deterministic use cases.
- GRASS underperforms on Peptides-func (fifth place) and CLUSTER is second best rather than first.
Experimental setup
Datasets: ZINC MNIST CIFAR10 PATTERN CLUSTER Peptides-func Peptides-struct PascalVOC-SP COCO-SP roman-empire
Benchmarks: ZINC MNIST CIFAR10 PATTERN CLUSTER Peptides-func Peptides-struct PascalVOC-SP COCO-SP roman-empire
Metrics: MAE accuracy AP Macro F1
Baselines: GRIT NeuralWalker GPS Exphormer EGT SAN GatedGCN GAT
Builds on: RRWP encoding BigBird GPS Exphormer DropKey
Closest papers by meaning
- On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks (ICML 2025 · similarity 0.88)
- Locality-Aware Graph Rewiring in GNNs (ICLR 2024 · similarity 0.88)
- How Graph Neural Networks Learn: Lessons from Training Dynamics (ICML 2024 · similarity 0.87)
- Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence (ICML 2025 · similarity 0.87)
- GNNs Getting ComFy: Community and Feature Similarity Guided Rewiring (ICLR 2025 · similarity 0.87)
- Non-convolutional graph neural networks. (NeurIPS 2024 · similarity 0.87)
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.