Higher-order positional encodings improve graph representation learning performance
Higher-Order Positional Encodings for Graph Representation Learning
Machine Learning
Summary
Many systems have complex interactions that involve groups, not just pairs, but current graph methods often miss these. The authors propose a way to add extra information describing these group interactions to graphs without changing the core algorithms. They prove mathematically that this extra information helps capture patterns existing beyond simple pairs. Their experiments show that using these higher-order signals improves prediction tasks on molecular and synthetic data. The approach connects two research areas, making it easier to use advanced topology ideas in standard graph learning.
What this means in practice
- •For machine learning engineers: Enhance graph-based models for molecular property prediction by incorporating higher-order interaction information via new positional encodings.
- •For network analysts: Improve network structure analysis by using these encodings to capture group relations without redesigning existing graph algorithms.
Authors
Caleb Stam, Aagrim Hoysal, Sanjukta Krishnagopal
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.