Research map / Graph learning / GNN architectures
Learning Efficient Positional Encodings with Graph Neural Networks
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 PEARL, learnable graph positional encodings generated by message-passing GNNs applied to random or basis node inputs with statistical pooling, achieving permutation equivariance with linear (random) or quadratic (basis) complexity.
Problem
Graph positional encodings must be stable, expressive, scalable and generic, but eigenvector-based PEs are costly (O(N^3)) or lose expressiveness and stability when only a subset of eigenvectors is used.
Approach
Message-passing GNNs act as nonlinear functions of GSO eigenvectors; initializing each node with M random samples (R-PEARL) or standard basis vectors (B-PEARL) breaks symmetries for expressiveness, and averaging or summing the GNN outputs over samples restores permutation equivariance.
Key results
- On REDDIT-M, R-PEARL reaches 60.6 ± 0.3 accuracy, above SignNet-8S (59.3 ± 0.5) and the full SPE/SignNet/BasisNet that run out of memory.
- On ZINC logP regression, B-PEARL achieves the best test MAE of 0.0644 ± 0.001 versus 0.0693 for full SPE.
- On DrugOOD Size OOD-Test AUC, B-PEARL reaches 66.58 ± 0.67, improving over BasisNet by about 9.5% and SignNet by about 3.8% as reported.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use R-PE instead of GIN | Graph classification model · REDDIT-M | accuracy: 56.9 \pm 2.0 -> 60.6 \pm 0.3 | Helped |
| Use R-PE instead of GIN | Graph classification model · REDDIT-B | accuracy: 91.8 \pm 1.0 -> 94.5 \pm 0.4 | Helped |
| Use B-PE instead of SPE | ZINC logP predictor · ZINC | test MAE: 0.0693 \pm 0.0040 -> 0.0644 \pm 0.001 | Helped |
| Use R-PE instead of B-PE | ZINC logP predictor · ZINC | generalization gap: 0.0353 \pm 0.002 -> 0.0333 \pm 0.007 | Helped |
| Use B-PE instead of SignNet | DrugOOD model · DrugOOD Size OOD-Test | AUC: 64.03\(\pm\)0.70 -> 66.58 \pm 0.67 | Helped |
| Use B-PE instead of BasisNet | DrugOOD model · DrugOOD Size OOD-Test | AUC: 60.79\(\pm\)3.19 -> 66.58 \pm 0.67 | Helped |
| Use B-PE instead of SignNet | DrugOOD model · DrugOOD Scaffold OOD-Test | AUC: 66.43\pm 1.06 -> 69.51 \pm 0.62 | Helped |
| Use B-PE instead of SPE | DrugOOD model · DrugOOD Size OOD-Test | AUC: 66.02 \pm 0.49 -> 66.58 \pm 0.67 | Helped |
| Use R-PE instead of No PE | RelBench user-post-comment model · RelBench user-post-comment Test | MAP: 12.47 -> 13.87 | Helped |
| Use R-PE instead of No PE | RelBench post-post-related model · RelBench post-post-related Test | MAP: 10.73 -> 10.86 | Helped |
| Use R-PE instead of SignNet-8L | RelBench post-post-related model · RelBench post-post-related Test | MAP: 10.39 -> 10.86 | Helped |
Surprising findings
- On DrugOOD Assay, the proposed B-PEARL and R-PEARL do not beat SPE or SignNet in OOD-Test AUC, with B-PEARL trailing SPE by about 1.3 points.
- On RelBench post-post-related, the R-PEARL validation MAP is best but the B-PEARL/R-PEARL test MAP differences are small, suggesting limited gains outside the molecular and social datasets.
Limitations
- B-PEARL complexity is quadratic in graph size, so it is less suited to large graphs.
- The sample complexity bound and stability result rely on assumptions (Lipschitz nonlinearities, bounded filters) and are stated for specific architectures.
- On several DrugOOD Assay and Scaffold metrics, the method does not outperform SPE or SignNet.
Experimental setup
Datasets: REDDIT-B REDDIT-M ZINC DrugOOD RelBench rel-stack
Benchmarks: REDDIT-B REDDIT-M ZINC DrugOOD RelBench rel-stack
Metrics: accuracy MAE generalization gap AUC MAP
Baselines: GCN GIN GIN + random IDs GSN SignNet BasisNet PEG SPE SPE-8S SignNet-8S SignNet-8L BasisNet-8S
Builds on: SignNet BasisNet SPE GIN GINE
Closest papers by meaning
- On the Stability of Expressive Positional Encodings for Graphs (ICLR 2024 · similarity 0.92)
- Positional Encoding meets Persistent Homology on Graphs (ICML 2025 · similarity 0.90)
- What Are Good Positional Encodings for Directed Graphs? (ICLR 2025 · similarity 0.90)
- Graph Positional and Structural Encoder (ICML 2024 · similarity 0.89)
- What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding (ICML 2024 · similarity 0.89)
- Towards Principled Graph Transformers (NeurIPS 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.