Research map / Graph learning / Graph self-supervised learning
Simple Path Structural Encoding for Graph Transformers
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 Simple Path Structural Encoding (SPSE), which uses approximate simple-path counts between node pairs as edge encodings in graph transformers in place of random walk structural encoding (RWSE), with a DAG-decomposition approximate counting algorithm.
Problem
RWSE edge encodings in graph transformers cannot distinguish certain local structures (e.g., even cycles vs. paths, cyclic patterns), limiting expressivity; exact simple path counting is combinatorially expensive.
Approach
Replace random-walk landing probabilities with simple-path counts as edge encodings, and compute approximate counts efficiently by decomposing the graph into many DAGs via combined DFS/partial-BFS/BFS node orderings and taking maximum counts across DAGs.
Key results
- CSA-SPSE and GRIT-SPSE improve over RWSE counterparts in 21 of 24 model-dataset cases; GRIT-SPSE reaches 0.059 MAE on ZINC vs 0.065 for GRIT-RWSE.
- On molecular datasets, CSA and GRIT with SPSE show statistically significant gains in 5 of 6 cases (p<=0.05, t-test over 10 seeds).
- GRIT-SPSE attains 77.022% on CIFAR10 vs 76.246% for GRIT-RWSE, a significant gain; no significant gain on CLUSTER where SPSE does not help pure graph transformers.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace RWSE with SPSE in GRIT | GRIT · Molecular benchmarks (ZINC, Peptides-func, Peptides-struct, PCQM4Mv2) | benchmark performance: improves in all four reported settings | Helped |
| Replace RWSE with SPSE in GRIT | GRIT · CLUSTER | Accuracy: 79.730 ± 0.189 -> 79.571 ± 0.122 | Hurt |
| Replace RWSE with SPSE in CSA | CSA · Molecular benchmarks (ZINC, Peptides-func, Peptides-struct, PCQM4Mv2) | benchmark performance: improves in all four reported settings | Helped |
| Replace RWSE with SPSE in CSA | CSA · CLUSTER | Accuracy: 79.071 ± 0.120 -> 78.940 ± 0.132 | Hurt |
| Replace RWSE with SPSE in graph transformers | CSA and GRIT · Real-world benchmarks | performance: 21 out of 24 cases | Mixed |
| Add SPSE to GPS node representations | GPS · PATTERN and CLUSTER | Accuracy: 86.688 ± 0.073 -> 86.834 ± 0.025; 77.969 ± 0.161 -> 78.440 ± 0.177 | Helped |
| Increase the root-node proportion R (ablation) | SPSE path counting · ZINC and other molecular datasets | proportion of discovered paths | Helped |
| Increase DFS depth or trial count (ablation) | SPSE path counting · ZINC and other molecular datasets | proportion of discovered paths | No clear effect |
| Increase root-node proportion, DFS depth, or trial count (ablation) | SPSE path counting · MNIST | proportion of discovered paths | Helped |
| Use N=2 instead of N=8 (ablation) | SPSE path counting · MNIST | discovered paths: approximately 40% fewer discovered paths | Hurt |
| Increase the number of trials N (ablation) | SPSE path counting · PATTERN | proportion of discovered paths | Helped |
| Use approximate path counts from DAG decompositions instead of exact counts (ablation) | SPSE · CLUSTER | performance | Hurt |
Surprising findings
- SPSE gives no significant improvement on the dense CLUSTER dataset for pure graph transformers, attributed to underestimated path counts in dense SBM graphs.
- Under the deepest synthetic configuration, all models count cycles almost perfectly regardless of edge encoding, suggesting depth compensates for encoding expressivity limits.
Limitations
- Approximate counts are lower bounds; dense graphs (e.g., CLUSTER) lead to underestimated counts and no gain.
- Path counting preprocessing is expensive relative to RWSE, scaling with hyperparameter choices (R, D_DFS, N).
- Expressivity comparison between SPSE and RWSE in general remains an open question.
Experimental setup
Datasets: ZINC Peptides-func Peptides-struct PCQM4Mv2 PATTERN CLUSTER MNIST CIFAR10
Benchmarks: ZINC Peptides-func Peptides-struct PCQM4Mv2 PATTERN CLUSTER MNIST CIFAR10 synthetic cycle counting
Metrics: MAE AP accuracy
Baselines: GRIT-RWSE CSA-RWSE GPS GPSE Exphormer GraphViT EGT Graphormer SAN GIN-AK+
Builds on: GRIT CSA GraphGPS Path-WL RWSE
Closest papers by meaning
- Homomorphism Counts as Structural Encodings for Graph Learning (ICLR 2025 · similarity 0.90)
- From Theory to Practice: Rethinking Green and Martin Kernels for Unleashing Graph Transformers (ICML 2025 · similarity 0.90)
- Enhancing Graph Transformers with Hierarchical Distance Structural Encoding (NeurIPS 2024 · similarity 0.88)
- Generalizable Insights for Graph Transformers in Theory and Practice (NeurIPS 2025 · similarity 0.87)
- Effective Structural Encodings via Local Curvature Profiles (ICLR 2024 · similarity 0.87)
- Graph Positional and Structural Encoder (ICML 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.