Research map / Graph learning / GNN architectures
What Are Good Positional Encodings for Directed Graphs?
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 walk profiles for directed graphs, shows existing directed PEs (Mag-PE, SVD-PE, symmetrized Laplacian) cannot express them, and proposes Multi-q Magnetic Laplacian PE with a stable complex-domain SPE architecture.
Problem
Positional encodings for directed graphs are underexplored; existing PEs (symmetrized Laplacian, SVD-PE, Magnetic Laplacian PE) cannot express bidirectional walk relations such as walk profiles, shortest/longest path distances, and common successors/predecessors.
Approach
Define walk profiles counting bidirectional walks with exact forward/backward edge counts, prove a single magnetic-Laplacian potential q is ill-posed for recovering them, and show that concatenating eigenvectors of ceil(L/2)+1 distinct potentials q recovers walk profiles up to length L via a Fourier-type linear system; extend stable basis-invariant PE (SPE) to complex eigenvectors.
Key results
- On directed acyclic graphs, Multi-q MagLap with SPE reduces spd test RMSE to 0.016 versus 0.124 for single-q MagLap (q=0.1) and 0.355 for Lap-PE with SPE.
- Multi-q Mag-PE with SPE achieves the best results on most circuit targets, e.g., Bidirected-GIN BW 4.051 and LUT 1.735 versus 4.153 and 1.786 for Lap-PE with SPE.
- On average the test RMSE of Multi-q Magnetic Laplacian is reduced by 66% compared to naive concatenation, and sorting network satisfiability achieves the best F1 with Multi-q SPE.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use multiple magnetic potentials instead of the best single potential (ablation) | Magnetic Laplacian PE with SPE · Directed acyclic graphs | spd RMSE: 0.124_{\pm 0.002} -> 0.016_{\pm 0.000} | Helped |
| Use multiple magnetic potentials instead of the best single potential (ablation) | Magnetic Laplacian PE with SPE · Directed acyclic graphs | lpd RMSE: 0.432_{\pm 0.004} -> 0.185_{\pm 0.036} | Helped |
| Use multiple magnetic potentials instead of the best single potential (ablation) | Magnetic Laplacian PE with SPE · Directed acyclic graphs | wp(4, ·) RMSE: 0.040_{\pm 0.001} -> 0.002_{\pm 0.000} | Helped |
| Use multiple magnetic potentials instead of the best single potential (ablation) | Magnetic Laplacian PE with SPE · Regular directed graphs | spd RMSE: 1.533_{\pm 0.007} -> 0.546_{\pm 0.068} | Helped |
| Use multiple magnetic potentials instead of the best single potential (ablation) | Magnetic Laplacian PE with SPE · Regular directed graphs | lpd RMSE: 1.493_{\pm 0.003} -> 1.100_{\pm 0.007} | Helped |
| Use multiple magnetic potentials instead of the best single potential (ablation) | Magnetic Laplacian PE with SPE · Regular directed graphs | wp(4, ·) RMSE: 0.132_{\pm 0.000} -> 0.074_{\pm 0.001} | Helped |
| Use stable SPE processing instead of naïve concatenation (ablation) | MagLap-Multi-q · Directed acyclic graphs | spd RMSE: 0.353_{\pm 0.003} -> 0.016_{\pm 0.000} | Helped |
| Use stable SPE processing instead of naïve concatenation (ablation) | MagLap-Multi-q · Regular directed graphs | spd RMSE: 1.708_{\pm 0.012} -> 0.546_{\pm 0.068} | Helped |
| Use randomly sampled potential values rather than evenly spaced values (ablation) | MagLap-Multi-q · Distance prediction | test RMSE | Mixed |
| Use multiple potentials rather than a single potential (ablation) | Magnetic Laplacian PE · Sorting network satisfiability | test F1 | Helped |
| Use multiple magnetic potentials instead of the best single potential (ablation) | Magnetic Laplacian PE with SPE · Open Circuit Benchmark | Gain RMSE | Helped |
Surprising findings
- Naive concatenation and SignNet can perform worse than naive use of PEs; SignNet suffers from node ambiguity that loses pairwise distance information.
- Single-q Magnetic Laplacian PE, even with its best q, cannot express walk profiles, and the proof shows Mag-PE cannot express shortest path distance either.
Limitations
- Multi-q PE increases preprocessing cost and PE input dimension, requiring multiple eigendecompositions; training time with 10 q is about 1.5 to 3 times that of one q.
- Expressivity guarantee assumes no multi-edges and exact walk profile recovery; results for real tasks show gains that are often within standard deviation.
Experimental setup
Datasets: Synthetic Erdos-Renyi directed graphs (distance prediction) Sorting network satisfiability dataset Open Circuit Benchmark High-level Synthesis (HLS) dataset
Benchmarks: Synthetic directed graph distance prediction (spd, lpd, walk profile) Sorting network satisfiability Open Circuit Benchmark (Gain, BW, PM) High-level Synthesis (DSP, LUT)
Metrics: RMSE F1 MSE
Baselines: Lap-PE naive Lap-PE SignNet SVD-PE MagLap-1q SAT SignNet
Builds on: Magnetic Laplacian SignNet SPE (stable and expressive positional encodings) GIN SAT
Closest papers by meaning
- Learning Efficient Positional Encodings with Graph Neural Networks (ICLR 2025 · similarity 0.90)
- On the Stability of Expressive Positional Encodings for Graphs (ICLR 2024 · similarity 0.89)
- Positional Encoding meets Persistent Homology on Graphs (ICML 2025 · similarity 0.87)
- Simple Path Structural Encoding for Graph Transformers (ICML 2025 · similarity 0.87)
- From Theory to Practice: Rethinking Green and Martin Kernels for Unleashing Graph Transformers (ICML 2025 · similarity 0.86)
- Learnable Spatial-Temporal Positional Encoding for Link Prediction (ICML 2025 · similarity 0.85)
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.