Positional Encoding meets Persistent Homology on Graphs

Conference: ICML 2025
arXiv: 2506.05814
Code: https://github.com/Aalto-QuML/PIPE
Area: Graph Learning / Graph Expressiveness
Keywords: Positional Encoding, Persistent Homology, Graph Expressiveness, GNN, PiPE

TL;DR

Theoretically proves that positional encoding (PE) and persistent homology (PH) on graphs are mutually incomparable in terms of distinguishing non-isomorphic graphs. This paper proposes PiPE (Persistence-informed Positional Encoding), which unifies both via message-passing networks and is provably more expressive than either method alone, consistently outperforming pure PE and pure PH baselines on multiple benchmarks including ZINC, Alchemy, DrugOOD, and BREC.

Background & Motivation

Expressiveness Bottleneck of Message Passing GNNs: Standard message-passing GNNs are at most as powerful as the 1-WL test, failing to capture critical structural information such as connectivity and cycles. To resolve this, the community has developed two mainstream approaches: first, Positional Encoding (PE), which assigns position-aware features using Laplacian eigenvectors or random walk distances; second, Persistent Homology (PH), which captures multi-scale topological features (e.g., the birth/death of connected components, persistence of independent cycles) via topological data analysis.

Key Challenge: While both paradigms enhance GNN expressiveness, their comparative advantages remain unclear—can PE encompass PH? Is PH strictly more powerful than PE? Can they be unified for further gains? These questions lack rigorous theoretical characterization.

Key Insight: Through constructive proofs, this work establishes the incomparability of PE and PH (by identifying pairs of graphs where each method succeeds while the other fails). Leveraging this insight, the authors design PiPE, theoretically and experimentally demonstrating that the unified method is strictly more expressive than either individual approach. Core Idea: Use PE features to drive the filtration function of PH, and then feed back the topological embeddings from PH to enhance PE updates, forming a closed loop.

Method

Overall Architecture

The pipeline of PiPE consists of three parallel update streams: (1) Positional Encoding Stream \(\{p_v^\ell\}\): initialized from basic PE (e.g., LapPE) and iteratively updated via message passing; (2) Topological Feature Stream \(\{r_v^{\ell,0}, r_v^{\ell,1}\}\): at each layer, a filtration function \(f_\ell\) is calculated using the current positional encoding to generate 0-dimensional and 1-dimensional persistence diagrams \(\mathcal{D}_\ell^0, \mathcal{D}_\ell^1\), which are then vectorized to obtain node-level topological embeddings; (3) Backbone GNN Stream \(\{x_v^\ell\}\): concatenates node features, positional embeddings, and topological embeddings for standard message passing. Finally, in the readout phase, the three streams are fused for graph-level/node-level predictions.

Key Designs

1. PE-Driven Persistent Homology Computation:

   • Function: Utilizes learnable positional encodings as node colors to construct vertex-color filtration functions for computing persistence diagrams.
   • Mechanism: At each layer \(\ell\), an MLP \(f_\ell\) maps the positional encoding \(p_v^\ell\) to filtration values. These values are used to construct a sequence of subgraphs \(G_\alpha\) that track the birth and death of connected components (0D) and independent cycles (1D), yielding persistence diagrams \(\mathcal{D}_\ell^0, \mathcal{D}_\ell^1\).
   • Design Motivation: Lemma 3.3 proves that a 0D persistence diagram generated by a PE-based filtration function is at least as expressive as the PE itself (retaining all information). Meanwhile, Proposition 3.4 demonstrates that PH can distinguish certain graph pairs that PE cannot. Therefore, their combination is strictly more expressive.

2. Node-Level Vectorization of Topological Embeddings:

   • Function: Converts persistence diagrams into fixed-dimensional embedding vectors for each node.
   • Mechanism: Since the size of the 0D persistence diagram \(|\mathcal{D}_0| = n\) matches the number of nodes, a bijection can be established. Each \((birth, death)\) tuple is processed by an MLP \(\Psi_0^\ell\) to obtain \(r_v^{\ell,0}\). For 1D persistence diagrams corresponding to independent cycles, edge-level features are vectorized via \(\Psi_1^\ell\) and then aggregated over edges incident to each node to obtain \(r_v^{\ell,1}\).
   • Design Motivation: Maintains node-level representations compatible with message-passing frameworks, allowing topological information to directly participate in the update of subsequent layers.

3. Joint Positional-Topological Message Passing Updates:

   • Function: Feeds back topological embeddings into positional encoding updates, creating a closed loop.
   • Mechanism: The positional encoding is updated via \(p_v^{\ell+1} = \text{Upd}_\ell^p(r_v^{\ell,0}, r_v^{\ell,1}, p_v^\ell, \text{Agg}_\ell(\{(r_u^{\ell,0}, r_u^{\ell,1}, p_u^\ell) : u \in \mathcal{N}(v)\}))\), which aggregates neighbors' topological and positional information simultaneously.
   • Design Motivation: Unlike LSPE which only uses positional information to update position embeddings, PiPE involves topological information in positional updates. Theoretically, this allows filtration functions in subsequent layers to encode richer structural details, generating more discriminative persistence diagrams.

Theoretical Analysis

• Proposition 4.1: LPE-based PiPE is strictly more powerful than LPE-based LSPE (on unattributed graph spaces).
• Proposition 4.2: LPE-based PiPE is strictly more powerful than PH + LPE (combining them without message passing unification).
• Proposition 4.3: RW-based PiPE has pairs of graphs it cannot distinguish (which are distinguishable by 3-WL), pointing out its limitations.
• Proposition 4.4: If \(k\)-FWL can distinguish two graphs, then a filtration function can be constructed such that the 0D persistence diagrams are different (strengthening existing results).

Key Experimental Results

Main Results: BREC Expressiveness Benchmark

Dataset	PH	PH+LPE	PiPE
Basic (60 pairs)	0.03	0.10	0.72
Regular (50 pairs)	0.00	0.15	0.40
Extension (100 pairs)	0.07	0.13	0.67
CFI (100 pairs)	0.03	0.03	0.03

PiPE leads by a large margin on Basic, Regular, and Extension, validating the expressiveness gains of the unified approach. CFI graph pairs remain difficult to distinguish for all methods (requiring higher-order WL).

Synthetic Tree Tasks (Perplexity ↓)

PE Scheme	PH	C₃-B	C₃-D	Reorder-B	Reorder-D	Copy-B	Copy-D
RoPE	None	1.84	2.52	4.93	6.63	1.85	3.17
RoPE	VC	1.65	1.94	4.76	5.24	1.14	2.35
RoPE	RePHINE	1.59	1.77	4.49	4.70	1.00	2.05

On all three tree tasks, PiPE (PE+PH) consistently outperforms pure PE baselines, reducing PPL by 13%–35%.

Ablation Study

Configuration	Key Metric	Description
Pure PE (No PH)	Baseline	Positional encoding only
Pure PH (No PE)	Lower than PiPE	Topological features only
PH + PE (Non-learned combination)	Medium	Simple concatenation
PiPE (Learned unification)	Optimal	Closed-loop message passing
Identity filtration vs. learned filtration	Learned filtration is better	Learnable \(f_\ell\) enhances expressiveness

Computational Overhead: Compared to base PE methods, PiPE only introduces a small time overhead (per-epoch time on Alchemy is close to the base method), with the primary overhead originating from the PH embedding calculation.

Key Findings

• Combining PiPE with PEG achieves the largest MAE reduction on the ZINC dataset.
• On the OOD-Test of DrugOOD, PiPE demonstrates the best generalization (all methods perform similarly on ID-Test, while gap widens on OOD-Test).
• Achieves significant improvements on OGBG-MOLPCBA (437.9k graphs), validating large-scale applicability.
• Consistent improvements across various PE base methods (LapPE/RWPE/PEG/SPE/SignNet), showcasing the generality of the framework.

Highlights & Insights

• First rigorous proof of the incomparability between PE and PH: Provides a complete theoretical characterization through meticulously constructed graph pairs (such as anthracene-like graphs and shared-ring graph pairs).
• The design of PiPE is theoretically elegant and practical, with its core mechanism (PE-driven PH, PH-informed PE) naturally unifying the two paradigms.
• Plug-and-play framework: can be built on top of any existing PE method and is compatible with multiple PH vectorization schemes (e.g., VC, RePHINE).
• Establishes a deep theoretical connection between topological data analysis and graph representation learning.

Limitations & Future Work

• The PH computation (especially 1D persistent homology) is computationally heavy, and its scalability to large-scale graphs (>10K nodes) remains to be validated.
• Currently, only 0D and 1D topological features (connected components and independent cycles) are considered; higher-dimensional persistent homology (e.g., cavities) remains unexplored.
• CFI-type graph pairs remain indistinguishable, indicating limitations on certain highly symmetric structures.
• Computations are restricted to 1D simplicial complexes; higher-dimensional Rips complexes library may yield further gains.

Related Work & Insights

• Horn et al. (2022) TOGL: The first framework integrating PH into GNN layers; PiPE builds on this by introducing PE-driven filtration functions.
• Dwivedi et al. (2022) LSPE: A learnable positional encoding framework; PiPE directly extends its position update formulation.
• Lim et al. (2023) SignNet/BasisNet: Resolves the sign ambiguity of Laplacian eigenvectors, serving as optional base PEs for PiPE.
• Immonen et al. (2023): Characterizes the expressiveness of VC filtrations; Lemma 3.3 of PiPE directly generalizes their results.
• Insight: The complementary nature of different enhancement paradigms is worth exploring in broader fields (such as geometric learning and molecular design).

Rating

• Novelty: ⭐⭐⭐⭐⭐ First to rigorously characterize the relationship between PE and PH theoretically; the unified PiPE framework is elegantly designed.
• Experimental Thoroughness: ⭐⭐⭐⭐ Covers expressiveness benchmarks, molecular prediction, graph classification, OOD, and synthetic tasks with comprehensive ablations.
• Writing Quality: ⭐⭐⭐⭐⭐ Seamless connection between theory and experiments, clear illustrations, and intuitive construction of incomparability.
• Value: ⭐⭐⭐⭐ Profound impact on the study of graph representation learning expressiveness, with a highly practical plug-and-play design.

Related Papers

• [ICML 2025] L-STEP: Learnable Spatial-Temporal Positional Encoding for Link Prediction
• [ICML 2025] TopInG: Topologically Interpretable Graph Learning via Persistent Rationale Filtration
• [ICLR 2026] LEAP: Local ECT-Based Learnable Positional Encodings for Graphs
• [ICML 2025] CoDy: Counterfactual Explainers for Dynamic Graphs
• [ICML 2026] Understanding Truncated Positional Encodings for Graph Neural Networks