Path Laplacian Encodings for Directed Graphs

Lydia Mezrag; Semih Cantürk; Michael Perlmutter; Bastian Rieck; Guy Wolf

cs.LGOct 3, 2026

Path Laplacian Encodings for Directed Graphs

Authors: Lydia Mezrag, Semih Cantürk, Michael Perlmutter, Bastian Rieck, Guy Wolf

Organizations: Université de Montréal · Mila – Quebec AI Institute · Boise State University · Université de Fribourg

Abstract

Directed graphs naturally model many real-world systems in which interactions are asymmetric, such as citation networks, web graphs, and information-flow networks. However, graph learning methods commonly rely on message passing with symmetrized graph representations or positional encodings that only partially exploit edge directionality. We introduce PathLapPE, a novel spectral positional encoding (PE) derived from the path Laplacian on directed graphs. PathLapPE provides node- and edge-level features that encode directional higher-order structure and can be incorporated into standard graph learning architectures. Empirical results on node- and graph-level benchmark tasks show that PathLapPE yields consistent improvements across several architectures, especially when combined with direction-aware message passing. Compared with magnetic Laplacian positional encodings, a widely studied spectral positional encoding for directed graphs, PathLapPE does not require additional fine-tuning of directionality hyperparameters while offering competitive runtime and performance.

Figures & tables

Panel of Figure 1 — Figure 1: Basis elements of $\Omega_{2}$ : invariant elementary $2$ -paths in (a) and (c), and the difference of the solid and dashed $2$ -paths in (b).

Panel of Figure 2 — Figure 2: Overview of PathLapPE construction and feature extraction pipeline.

Figure 3: FlowGraph experiments, mean + std for five runs. Only directional PEs (PathLapPE and Multi-

q

-MagLapPE) perform above random.

Model	PE	Cornell	Wisconsin	Texas	Avg. Rank $\downarrow$
GAT	No PE	$48.37\pm 7.59$	$52.55\pm 4.11$	$59.73\pm 4.12$	5.17
	RWPE	$54.05\pm 7.96$	$53.72\pm 6.55$	$60.00\pm 4.38$	3.17
	LapPE	$54.05\pm 7.75$	$52.35\pm 8.82$	$59.73\pm 4.84$	4.67
	Multi- $q$ -MagLapPE, $q\in\{0.01,0.05,0.10\}$	$\underline{55.68\pm 7.67}$	$53.14\pm 7.01$	$\underline{60.27\pm 4.24}$	2.67
	PathLapPE (ours)	$53.78\pm 6.17$	$\mathbf{56.28\pm 5.31}$	$59.46\pm 4.59$	4.00
	PathLapPE (ours, w/ EdgeSPE)	$\mathbf{55.95\pm 8.55}$	$\underline{55.88\pm 7.69}$	$\mathbf{61.35\pm 4.04}$	$\mathbf{1.33}$

Table 1: Node classification accuracy (mean test accuracy

\%

) on the WebKB datasets. The best result within each model family is in bold and the second best is underlined.

PE	BiGINE	BiGINE-shared	GAT	BiGAT	BiGCNE
Base (No PE)	$89.48\pm 0.40$	$83.03\pm 0.63$	$83.01\pm 0.35$	$90.36\pm 0.30$	$87.79\pm 0.47$
LaplacianPE	$90.97\pm 0.42$	$87.68\pm 0.42$	$84.19\pm 0.48$	$\mathbf{91.15\pm 0.40}$	$89.58\pm 0.57$
Multi- $q$ -MagLapPE, $q=0.05$	$90.95\pm 0.36$	$87.66\pm 0.24$	$83.93\pm 0.56$	$91.13\pm 0.44$	$89.63\pm 0.36$
Multi- $q$ -MagLapPE, $\#q=3,q\in\{0.05,0.1,0.15\}$	$90.95\pm 0.33$	$87.28\pm 0.39$	$84.32\pm 0.39$	$91.10\pm 0.45$	$89.82\pm 0.35$
PathLapPE (ours)	$91.33\pm 0.23$	$\mathbf{89.50\pm 0.36}$	$\mathbf{84.39\pm 0.39}$	$91.10\pm 0.46$	$\mathbf{90.29\pm 0.32}$
PathLapPE (ours, w/ EdgeSPE)	$\mathbf{91.37\pm 0.32}$	$89.17\pm 0.56$	$83.90\pm 0.42$	$91.14\pm 0.27$	$90.06\pm 0.45$

Table 2: Node classification results (mean test acc.

\%

) on Roman-Empire . Best result is bolded , second best is underlined . Best

k

(num. eigenpairs) reported, Table 6 lists results for all

k

values.

		OCB (RMSE $\downarrow$ )			HLS (MSE $\downarrow$ )			Avg.
	PE	Gain	BW	PM	DSP	LUT	CP	Rank $\downarrow$
BiGINE	No PE	$0.394$ $\pm 0.007$	$4.497$ $\pm 0.111$	$1.123$ $\pm 0.011$	$\mathbf{2.254}$ $\bm{\pm 0.068}$	$1.793$ $\pm 0.174$	$1.152$ $\pm 0.077$	$4.08$
	LapPE	$0.394$ $\pm 0.014$	$4.223$ $\pm 0.077$	$1.114$ $\pm 0.022$	$2.445$ $\pm 0.216$	$\mathbf{1.767}$ $\bm{\pm 0.030}$	$1.158$ $\pm 0.132$	$3.75$
	Multi- $q$ -MagLapPE, $\#q=\{5,10\},q=0.01$	$0.393$ $\pm 0.010$	$4.156$ $\pm 0.143$	$1.112$ $\pm 0.015$	$2.325$ $\pm 0.103$	$1.783$ $\pm 0.052$	$1.186$ $\pm 0.107$	$3.17$
	Multi- $q$ -MagLapPE, $\#q=\{5,10\},q\in\{0.05,0.1\}$	$0.388$ $\pm 0.015$	$4.215$ $\pm 0.128$	$1.121$ $\pm 0.018$	$2.335$ $\pm 0.137$	$1.856$ $\pm 0.134$	$1.383$ $\pm 0.348$	$4.17$
	PathLapPE (ours)	$0.384$ $\pm 0.014$	$4.236$ $\pm 0.102$	$1.147$ $\pm 0.005$	$2.625$ $\pm 0.121$	$2.096$ $\pm 0.083$	$\mathbf{1.113}$ $\bm{\pm 0.093}$	$4.33$

Table 3: Test set results for Open Circuit Benchmark and High-level Synthesis . Mean

\pm

std reported across five seeds. Best result is bolded , second best is underlined . Multi-

q

-MagLapPE uses

\#q=10

for OCB, and

\#q=5

for HLS.

Figure 4: Time (left pair) and memory (right pair) cost of PE computation on directed ER graphs on an NVIDIA L40S GPU. Dense solver on GPU,

k=8

, three repeats for each experiment.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

J_{r}=\{j_{1},\ldots,j_{s}\}:=\{j:(\mathbf{B}_{2}^{\mathcal{D}})_{rj}\neq 0\}.

Appendix

Algorithm 1 Construction of a basis for

\Omega_{2}

Dataset	Cornell	Wisconsin	Texas	Roman-Empire
# Nodes	183	251	183	22,662
# Edges	295	499	325	44,363
# Features	1,703	1,703	1,703	300
# Classes	5	5	5	18
License	CC-BY 4.0	CC-BY 4.0	CC-BY 4.0	MIT

Appendix

Table 4: Dataset statistics for transductive node-level tasks

Dataset	FlowGraph2	FlowGraph3	FlowGraph6	OCB	HLS
# Graphs	2,000	3,000	6,000	8,026 a	18,570
Avg. # Nodes	114.46	111.66	111.40	9.89	94.70
Avg. # Edges	150.30	150.70	149.93	15.02	122.12
# Node Features	0	0	0	3	7
# Edge Features	0	0	0	0	2
Task	Binary class.	3-way class.	6-way class.	Regression	Regression

Appendix

Table 5: Dataset statistics for inductive graph-level tasks

Encoder	PE Variant	$k{=}8$	$k{=}16$	$k{=}32$	$k{=}64$	Best
BiGINE-shared	Base (No PE)	$83.03\pm 0.63$	$83.03\pm 0.63$	$83.03\pm 0.63$	$83.03\pm 0.63$	$83.03\pm 0.63$
	LaplacianPE	$\mathbf{87.68\pm 0.42}$	$87.44\pm 0.23$	$87.60\pm 0.31$	$87.53\pm 0.42$	$87.68\pm 0.42$
	Multi- $q$ -MagLapPE, $q=0.05$	$\mathbf{87.66\pm 0.24}$	$87.47\pm 0.36$	$87.52\pm 0.42$	$87.64\pm 0.40$	$87.66\pm 0.24$
	Multi- $q$ -MagLapPE, $q\in\{0.05,0.1,0.15\}$	$87.10\pm 0.68$	$\mathbf{87.28\pm 0.39}$	$87.17\pm 0.52$	$87.16\pm 0.53$	$87.28\pm 0.39$
	PathLapPE (256 $\times$ 2)	$89.31\pm 0.44$	$\mathbf{89.43\pm 0.42}$	$89.36\pm 0.41$	$89.25\pm 0.37$	${\color[rgb]{0.38,0.43,0.77}\mathbf{89.43\pm 0.42}}$
	PathLapPE	$\mathbf{89.50\pm 0.36}$	$89.15\pm 0.29$	$89.12\pm 0.41$	$89.25\pm 0.41$	${\color[rgb]{1,0.58,0}\mathbf{89.50\pm 0.36}}$

Appendix

Table 6: Results across encoder architectures and positional encodings on Roman-Empire . Bold indicates the best

k

for each variant. In the last column, the top three PEs for each encoder are denoted with gold , silver and bronze .

Data
	FlowGraph	WebKB	Roman-Empire
Task	graph cls.	node cls.	node cls.
Graphs	2,000 / 3,000 / 6,000	1	1
Classes	2 / 3 / 6	5	18
Input feature dim.	1 a	1,703	300
Batching	batch size 32	full graph	full graph

Appendix

Table 7: Key model and training hyperparameters for the FlowGraph , WebKB and Roman-Empire datasets. All FlowGraph and WebKB datasets share the same configs.

	Gain	BW	PM
Data
Input node features	3
Input edge features	–
Graphs	8,026	8,026	8,026
Splits	$90/5/5$ %	$90/5/5$ %	$90/5/5$ %
Batch size	128	64	64

Appendix

Table 8: Key model and training hyperparameters for the Open Circuit Benchmark experiments. All backbones (both uni- and bidirectional GINE) share a single configuration per target.

	DSP		LUT		CP
	Uni-GNN	Bi-GNN	Uni-GNN	Bi-GNN	Uni-GNN	Bi-GNN
Data
Categorical node features	7
Categorical edge features	2
Graphs (CDFG)	18,570
Splits	16,570 / 1,000 / 1,000

Appendix

Table 9: Key model and training hyperparameters for the High-Level Synthesis experiments. Unlike OCB , the tuned configuration depends on whether the backbone is unidirectional (GINE) or bidirectional (BiGINE), so both are reported per target. A single value in a row indicates the parameter applies to all configurations.

	Roman-Empire		FlowGraph		OCB
	shift-invert, heap mem.		CPU dense, heap mem.		GPU dense, GPU mem.
PE	Time (s)	Mem (MB)	Time (ms)	Mem (MB)	Time (ms)	Mem (MB)
LapPE	0.154 $\pm$ 0.007	4.49	3.00 $\pm$ 0.23	0.24	2.20 $\pm$ 0.13	0.56
Multi- $q$ -MagLapPE, $\#q=1$	0.257 $\pm$ 0.001	8.50	2.96 $\pm$ 0.17	0.25	2.21 $\pm$ 0.10	1.12
Multi- $q$ -MagLapPE, $\#q=3$	0.704 $\pm$ 0.001	11.3	6.59 $\pm$ 0.44	0.27	4.23 $\pm$ 0.24	1.12
Multi- $q$ -MagLapPE, $\#q=5$	1.074 $\pm$ 0.016	14.1	10.15 $\pm$ 0.67	0.30	6.23 $\pm$ 0.38	1.12

Appendix

Table 10: Positional encoding precompute cost per graph. Each dataset is denoted with the optimal eigensolver strategy used for decomposition and the type of memory measured.

Explore similar work

Eigenbasis-Independent Learnable Spectral Positional Encodings for Directed Graphs via Hermitian Block Krylov Subspaces
Jul 8, 2026Jiaqing Xie, Yuxin WangPositional Encoding Spectral Methods
Fudan University
Higher-Order Positional Encodings for Graph Representation Learning
Oct 1, 2026Caleb Stam, Aagrim Hoysal, Sanjukta KrishnagopalGraph Representation Learning Positional Encoding
University of California, Santa Barbara
Rotary Position Encodings for Graphs
Sep 26, 2025Isaac Reid, Arijit Sehanobish, Cederik Höfs +7Rotary Positional Embeddings Graph Representation Learning
University of Cambridge · Google DeepMind · Independent Researcher +3

Jul 8, 2026J/K move · Enter open · S save

Eigenbasis-Independent Learnable Spectral Positional Encodings for Directed Graphs via Hermitian Block Krylov Subspaces

Jiaqing Xie, Yuxin Wang

Fudan University

Positional Encoding Spectral Methods Invariant Representation Learning Krylov Subspace Methods

Open paper AskPDF arXiv

Spectral positional encodings (PEs) for directed graphs face two obstacles: magnetic Laplacians require an

O(n^3)

Hermitian eigendecomposition per potential, and their complex eigenvectors are defined only up to unitary gauge, which prior work handles with basis-invariant architectures. We propose learnable spectral PEs of the form

h_θ(A_q)\,R

, where

A_q

is a normalized magnetic operator,

h_θ

a learnable scalar spectral response, and

R

a block of random probes. Because the PE is a matrix function of the operator, it is gauge-invariant by construction. We compute it in a Hermitian block Krylov subspace from sparse matrix--vector products only, prove that

k = O(\log(1/\varepsilon))

block steps suffice uniformly over heat--resolvent response families, and give a covering-number argument for why low-dimensional structured families generalize where free per-eigenvalue weights overfit. On a directed SBM whose symmetrization is uninformative by construction, direction-blind PEs stay at chance while magnetic Krylov PEs converge to the exact-eigendecomposition oracle as the depth grows. The same probes yield gauge-invariant pairwise features with

1/\sqrt{s}

Monte-Carlo error, and the undirected

q{=}0

case improves heterophilous benchmarks over no-PE and polynomial baselines.

Abstract

Explore similar work

Eigenbasis-Independent Learnable Spectral Positional Encodings for Directed Graphs via Hermitian Block Krylov Subspaces

Higher-Order Positional Encodings for Graph Representation Learning

Rotary Position Encodings for Graphs