Research map / Graph learning / GNN architectures
Recurrent Distance Filtering for Graph Representation Learning
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 GRED, a graph architecture that groups nodes by shortest-distance hop sets, aggregates each hop with a multiset function, and encodes the hop sequence with a diagonal linear RNN (LRU), achieving graph-transformer-level accuracy without positional encoding at lower training cost.
Problem
Message passing GNNs struggle to use information from distant nodes (over-squashing), while graph transformers lack graph inductive bias and rely on ad-hoc positional encodings and are computationally expensive.
Approach
For each target node, aggregate nodes per shortest-distance hop with an injective multiset function, then process the hop sequence (far to near) with a diagonal complex linear RNN (LRU) whose eigenvalues learn how fast distant signals decay; the RNN is shown to be injective over sequences, making the layer more expressive than 1-WL, with no positional encoding needed.
Key results
- GRED achieves 98.383% on MNIST and 76.853% on CIFAR10, the best reported in the paper's comparison table, outperforming GRIT (76.468%) and Graph MLP-Mixer.
- On Peptides-func GRED reaches 0.7085 AP without positional encoding (0.7133 with LapPE), significantly above most baselines but below DRew+LapPE (0.7150).
- Training is up to 8.8x faster per epoch than GRIT on CIFAR10 (27.8s vs 244.4s) with lower memory on ZINC and CIFAR10.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add Laplacian positional encoding (ablation) | GRED · Peptides-func | test AP: 0.7085$\pm$0.0027 -> 0.7133$\pm$0.0011 | Helped |
| Add Laplacian positional encoding (ablation) | GRED · Peptides-struct | test MAE: 0.2503$\pm$0.0019 -> 0.2455$\pm$0.0013 | Helped |
| Replace LRU with a vanilla RNN (ablation) | GRED · CIFAR10 and Peptides-func | performance | Hurt |
| Replace LRU with a standard LSTM cell (ablation) | GRED · CIFAR10 and Peptides-func | performance | Hurt |
| Replace LRU with 8-head self-attention (ablation) | GRED · ZINC 12K | performance | Hurt |
| Replace LRU with 8-head self-attention (ablation) | GRED · Peptides-func | performance | Helped |
| Vary recurrence length K (ablation) | GRED · CIFAR10 and ZINC 12K | performance | Mixed |
| Increase K to 60 from K=40 (ablation) | GRED · Peptides-func | performance | No clear effect |
| Use GRED instead of GRIT | GRED · ZINC 12K | training time per epoch: 23.9s -> 3.7s | Helped |
| Use GRED instead of GRIT | GRED · CIFAR10 | training time per epoch: 244.4s -> 27.8s | Helped |
| Use GRED instead of GRIT | GRED · Peptides-func | training time per epoch: 225.6s -> 158.9s | Helped |
Surprising findings
- Learned eigenvalues are pushed close to 1 on the long-range Peptides-func task but are smaller on CIFAR10, showing the RNN adapts its distance decay to task range.
- The best K on CIFAR10 and ZINC lies strictly between 1 and the graph diameter rather than at the diameter.
Limitations
- Does not outperform GRIT on ZINC (0.077 vs 0.059 MAE) or on PATTERN, and does not beat DRew+LapPE on Peptides-func.
- Results use four seeds per benchmark and hyperparameter tuning; the expressiveness beyond 1-WL is theoretical rather than benchmarked.
- Complexity scales with K times edges, so large-diameter graphs need smaller K and more depth.
Experimental setup
Datasets: MNIST CIFAR10 PATTERN CLUSTER ZINC 12K Peptides-func Peptides-struct NCI1 PROTEINS Tree-NeighborsMatch
Benchmarks: MNIST CIFAR10 PATTERN CLUSTER ZINC 12K Peptides-func Peptides-struct NCI1 PROTEINS
Metrics: accuracy MAE average precision training time per epoch GPU memory
Baselines: GRIT GPS Graph MLP-Mixer SAN DRew PathNN SPN GatedGCN
Builds on: LRU (Linear Recurrent Unit) GIN 1-WL Graphormer SPN
Closest papers by meaning
- On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning (NeurIPS 2025 · similarity 0.89)
- Locality-Aware Graph Rewiring in GNNs (ICLR 2024 · similarity 0.88)
- Learning Long Range Dependencies on Graphs via Random Walks (ICLR 2025 · similarity 0.88)
- Spatio-Spectral Graph Neural Networks (NeurIPS 2024 · similarity 0.87)
- Higher-Order Graphon Neural Networks: Approximation and Cut Distance (ICLR 2025 · similarity 0.87)
- Forward Learning of Graph Neural Networks (ICLR 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.