Higher-Order Positional Encodings for Graph Representation Learning

Caleb Stam; Aagrim Hoysal; Sanjukta Krishnagopal

cs.LGOct 1, 2026

Higher-Order Positional Encodings for Graph Representation Learning

Authors: Caleb Stam, Aagrim Hoysal, Sanjukta Krishnagopal

Organizations: University of California, Santa Barbara

Abstract

Many real-world systems exhibit higher-order interactions among groups of entities that cannot be captured by pairwise relationships alone. Graph Transformers and Graph Neural Networks increasingly rely on positional encodings to enrich graph representations, yet existing positional encodings are computed solely from the original graph and therefore cannot directly capture observed higher-order interactions. Topological Deep Learning addresses this limitation by lifting graphs to simplicial complexes, but typically requires performing message passing or attention on higher-order neural network representations. We introduce a representation learning paradigm that enriches graph representations with higher-order topology through positional encodings, enabling standard graph learning models to exploit lifted incidence structure without modifying the backbone. We derive a theoretical characterization of the expressivity of higher-order positional encodings, proving that node-level operators induced by higher-order lifts can mix graph Laplacian frequencies in ways that scalar graph spectral filters cannot. Guided by this theory, we instantiate higher-order positional encodings using Hodge Laplacians derived from clique complexes. Experiments with Graph Transformers on ZINC and controlled synthetic benchmarks demonstrate improvements in predictive performance, while a fixed-1-skeleton experiment shows that the pipeline can transmit higher-order information when cells are supplied independently of the graph. Together, our results establish higher-order positional encodings as a principled bridge between graph positional encodings and topological deep learning.

Figures & tables

Figure 1: (a) An example graph corresponding to Corollary 2 : filled triangle $\tau=\{0,1,2\}$ , with node 0 adjacent to an external vertex. (b) $\widehat{M}=U^{\top}M_{\triangle}U$ , the lifted operator in the Laplacian eigenbasis; off-diagonal entries are the frequency-mixing terms no scalar filter can reproduce. (c) The closest achievable scalar filter, $g(L)=\operatorname{diag}(\widehat{M}_{ii})$ , in the same eigenbasis, sharing (b)’s color scale. The operator is diagonal; it recovers none of (b)’s off-diagonal mass.

Figure 2: Overview of the proposed architecture. Positional and structural encodings are computed in the higher-order domain before being projected to the node level and passed to a standard GNN or Graph Transformer.

Encoding	4-clique count MAE
LapPE	$6.274\pm 0.001$
RWPE	$6.271\pm 0.008$
HOPSE-M-C	$5.813\pm 0.136$
Hodge	$\mathbf{3.906\pm 0.053}$

Table 1: Validation MAE (mean

\pm

std over 5 trials) for four-clique counting under degree-sequence control,

n\in[18,22]

Encoding	MAE
No PSE	$0.115\pm 0.001$
LapPE	$0.128\pm 0.001$
RWPE	$0.086\pm 0.025$
HOPSE-M-C	$0.111\pm 0.003$
HodgeRandom	$0.094\pm 0.018$
Hodge	$\mathbf{0.066\pm 0.001}$

Table 2: Validation MAE (mean

\pm

std over 5 trials) for the single-triangle-edge fraction task,

n\in[18,22]

Encoding	No bond features	Bond features
No PSE	$0.694\pm 0.002$	$0.556\pm 0.041$
LapPE	$0.683\pm 0.010$	$0.637\pm 0.016$
RWPE	$0.686\pm 0.003$	$0.585\pm 0.014$
Full Hodge	$0.534\pm 0.014$	$0.473\pm 0.024$
Lower Hodge	$0.523\pm 0.018$	$\mathbf{0.405\pm 0.030}$

Table 3: ZINC test MAE (mean

\pm

standard deviation) with and without standard bond features.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Task	$n$	$p$	Train / eval graphs
Four-clique counting	$[18,22]$	$[0.3,0.4]$	5,000 / 1,000
Hodge ablation (single-triangle-edge fraction)	$[18,22]$	$[0.3,0.4]$	5,000 / 1,000

Appendix

Table 4: Synthetic dataset generation parameters by task.

Encoding	Num. components	Largest-comp. fraction
No PSE	$1.037\pm 0.0003$	$0.131\pm 0.0002$
RWPE	$1.036\pm 0.0003$	$0.130\pm 0.0002$
LapPE	$1.036\pm 0.0003$	$0.131\pm 0.0002$
Hodge	$\mathbf{0.307\pm 0.013}$	$\mathbf{0.057\pm 0.010}$

Appendix

Table 5: Fixed-skeleton validation MAE (mean

\pm

std over 5 trials) on both targets. All examples share one 1-skeleton; only

B_{2}

varies. The first block uses graph-only information and the second uses the supplied filled faces.

Explore similar work

Jul 30, 2026cs.LG

TopoFormer: Topology Meets Attention for Graph Learning

We introduce Topoformer, a lightweight and scalable framework for graph representation learning that encodes topological structure into attention-friendly sequences. At the core of our method is Topo-Scan, a novel module that decomposes a graph into a short, ordered sequence of topological tokens by slicing over node or edge filtrations. These sequences capture multi-scale structural patterns, from local motifs to global organization, and are processed by a Transformer to produce expressive graph-level embeddings. Unlike traditional persistent homology pipelines, Topo-Scan is parallelizable, avoids costly diagram computations, and integrates seamlessly with standard deep learning architectures. We provide theoretical guarantees on the stability of our topological encodings and demonstrate state-of-the-art performance across graph classification and molecular property prediction benchmarks. Our results show that Topoformer matches or exceeds strong GNN and topology-based baselines while offering predictable and efficient compute. This work opens a new path for parallelizable and unifying approaches to graph representation learning that integrate topological inductive biases into attention frameworks.

Md Joshem Uddin, Astrit Tola, Cuneyt Gurcan Akcora +1

Department of Mathematical Science The University of Texas at Dallas Richardson, TX 75080, USA · Department of Mathematics Florida State University Tallahassee, FL 32306, USA · AI Initiative University of Central Florida Orlando, FL 32816, USA

Graph Representation Learning Topology Graph Representations Persistent Homology Inductive Bias

Ask PDF

Jun 11, 2026cs.LG

Understanding Truncated Positional Encodings for Graph Neural Networks

Positional encodings (PEs) enhance the power of graph neural networks (GNNs), both theoretically and empirically. Two of the most popular families of PEs - spectral (e.g., Laplacian eigenspaces, effective resistance) and walk-based (polynomials of the adjacency matrix) - are theoretically equivalent in expressive power, with expressivity between the 1-WL and 3-WL tests. However, this equivalence assumes the GNN uses the "complete" version of these PEs, which requires

O(n^3)

time and space complexity. Instead, practitioners commonly use truncated variants of these encodings, such as the first

k

eigenspaces or powers of the adjacency matrix. However, the theoretical properties of these truncated PEs are unknown. In this work, we initiate the study of these truncated PEs. Theoretically, we show that, under truncation, several families of PEs are fundamentally different in expressive power. As a corollary, we show that truncated spectral PEs are no longer stronger than the 1-WL test. We also study a family of spectral PEs, the

k

-harmonic distances, to highlight the differences in expressive power of even closely related truncated PEs. Finally, we experimentally show that a mix of truncated PEs is preferable to any single family on real-world datasets.

James Flora, Mitchell Black, Weng-Keen Wong +1

School of Electrical Engineering and Computer Science, Oregon State University, Corvallis, Oregon, USA · Halıcıoğlu Data Science Institute, University of California San Diego, San Diego, California, USA.

Graph Neural Networks Positional Encoding Graph Laplacians Expressivity

Ask PDF

Sep 26, 2025cs.LG

Rotary Position Encodings for Graphs

We study the extent to which rotary position encodings (RoPE), a recent transformer position encoding algorithm broadly adopted in large language models (LLMs) and vision transformers (ViTs), can be applied to graph-structured data. We find that rotating tokens depending on the spectrum of the graph Laplacian efficiently injects structural information into the attention mechanism, boosting performance in synthetic and real-world graph learning tasks. This approach, coined Wave-Induced Rotary Encodings (WIRE), enjoys intriguing theoretical properties: it recovers regular RoPE on grids, and depends asymptotically on the graph effective resistance. Unlike bias-based relative position encodings, WIRE is compatible with linear attention.

Isaac Reid, Arijit Sehanobish, Cederik Höfs +7

University of Cambridge · Google DeepMind · Independent Researcher +3

Positional Encoding Transformer Architectures Graph Laplacians

Ask PDF