Research map / Graph learning / GNN architectures
Positional Encoding meets Persistent Homology on 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.
Shows positional encodings (PE) and persistent homology (PH) are incomparable in expressivity and proposes PiPE, a learnable method that feeds PE-derived persistence diagram features into message-passing GNNs, provably more expressive than PE or PH alone.
Problem
Message-passing GNNs have limited expressivity due to local inductive bias; PE and PH each improve it, but their relative expressive power is unclear and they have not been combined theoretically.
Approach
Proves PE and PH are mutually incomparable in expressivity, then unifies them by computing vertex-color persistence diagrams (dims 0 and 1) from learnable positional encodings at each GNN layer and feeding the vectorized topological features back into message passing; the framework is agnostic to the base PE.
Key results
- On BREC unattributed graphs, PiPE reaches 0.72 accuracy on Basic (60 pairs) versus 0.03 for PH and 0.10 for PH+LPE.
- On the DrugOOD Scaffold OOD-Test AUC-ROC, PiPE with RePHINE achieves 68.03 vs 66.43 for SignNet and 67.85 for BasisNet-based baselines; the paper's main results tables are in the commented-out sections, so these figures are from the main text and tables as shown.
- On synthetic tree tasks, RoPE with RePHINE achieves the lowest perplexity (e.g., 1.59 on C3 breadth vs 1.84 without persistence).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add PiPE to PH+LPE | PH+LPE · BREC Basic | accuracy: 0.10 -> 0.72 | Helped |
| add PiPE to PH+LPE | PH+LPE · BREC Regular | accuracy: 0.15 -> 0.40 | Helped |
| add PiPE to PH+LPE | PH+LPE · BREC Extension | accuracy: 0.13 -> 0.67 | Helped |
| add PiPE to PH+LPE | PH+LPE · BREC CFI | accuracy: 0.03 -> 0.03 | No clear effect |
| add PiPE to PH+LPE | PH+LPE · BREC Distance | accuracy: 0.00 -> 0.05 | Helped |
| add identity filtration (VC-I) (ablation) | PEG · ZINC | MAE: 0.1878 $\pm$\textcolor{gray}{0.012} -> 0.1432 $\pm$\textcolor{gray}{0.023} | Helped |
| replace identity filtration with learned VC filtration (ablation) | PEG + VC-I · ZINC | MAE: 0.1432 $\pm$\textcolor{gray}{0.023} -> 0.1256 $\pm$\textcolor{gray}{0.017} | Helped |
| add RePHINE filtration (ablation) | PEG · ZINC | MAE: 0.1878 $\pm$\textcolor{gray}{0.012} -> 0.1082 $\pm$\textcolor{gray}{0.022} | Helped |
| add identity filtration (VC-I) (ablation) | SPE · ZINC | MAE: 0.0693 $\pm$\textcolor{gray}{0.004} -> 0.0608 $\pm$\textcolor{gray}{0.013} | Helped |
| replace identity filtration with learned VC filtration (ablation) | SPE + VC-I · ZINC | MAE: 0.0608 $\pm$\textcolor{gray}{0.013} -> 0.0599 $\pm$\textcolor{gray}{0.010} | Helped |
| add RePHINE filtration (ablation) | SPE · ZINC | MAE: 0.0693 $\pm$\textcolor{gray}{0.004} -> 0.0588 $\pm$\textcolor{gray}{0.007} | Helped |
| add PiPE with RePHINE | SignNet · DrugOOD Assay OOD-Test | AUC-ROC: 72.27_{\pm \textcolor{gray}{0.97}} -> 73.87_{\pm \textcolor{gray}{1.32}} | Helped |
Surprising findings
- Random-walk PE combined with PH cannot separate some graph pairs that 3-WL distinguishes, so PiPE with RW-PE is not universal.
- Identity filtration (using PEs directly as filtration values) already improves ZINC performance, and learned filtrations improve further.
Limitations
- PH computation adds computational cost.
- Restricted to 1-dimensional simplicial complexes (dims 0 and 1).
- Random-walk-based PiPE cannot distinguish some pairs separable by 3-WL.
Experimental setup
Datasets: ZINC Alchemy OGBG-MOLTOX21 OGBG-MOLHIV OGBG-MOLPCBA DrugOOD BREC synthetic tree tasks
Benchmarks: ZINC Alchemy OGBG-MOLTOX21 OGBG-MOLHIV OGBG-MOLPCBA DrugOOD BREC
Metrics: test MAE ROC-AUC AUC-ROC accuracy perplexity
Baselines: PEG SignNet BasisNet LapPE RWPE SPE DE VC RePHINE LSPE Sinusoidal Relative
Builds on: TOGL RePHINE LSPE GIN Laplacian PE random walk PE
Closest papers by meaning
- On the Stability of Expressive Positional Encodings for Graphs (ICLR 2024 · similarity 0.91)
- Learning Efficient Positional Encodings with Graph Neural Networks (ICLR 2025 · similarity 0.90)
- Homomorphism Counts as Structural Encodings for Graph Learning (ICLR 2025 · similarity 0.89)
- Graph Positional and Structural Encoder (ICML 2024 · similarity 0.89)
- Boosting Graph Pooling with Persistent Homology (NeurIPS 2024 · similarity 0.88)
- Learnable Spatial-Temporal Positional Encoding for Link Prediction (ICML 2025 · 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.