Higher-Order Positional Encodings for Graph Representation Learning
Graph positional encodings (PSEs) are computed from pairwise edges and inherently miss higher-order interactions such as triangles and cliques. The paper proposes to enrich standard graph models by computing positional encodings on lifted higher-order domains (e.g., clique complexes) and projecting them back to nodes, without altering the backbone. Its core theoretical insight is that lift-induced symmetric node operators can mix the eigenmodes of the original graph Laplacian $L$, placing them outside the class of scalar spectral filters $g(L)$. This yields a principled design rule---the commutator $[L,M] \neq 0$---and an experimental pipeline using Hodge-Laplacian encodings.
The paper offers a clean operator-theoretic perspective on when higher-order lifts fundamentally expand the space of graph positional representations. The commutator criterion and exact projection formula provide a quantitative, architecture-independent design principle. However, the implemented Hodge encoding is a nonlinear finite PSE that is not covered by the linear theory, and the only real-world benchmark (ZINC) shows gains driven by edge-space spectral bias rather than by higher-order triangles. The work is a solid proof of concept but stops short of demonstrating that the full higher-order pipeline consistently improves practical graph learning.
Theorem 1 gives a crisp spectral characterization: a symmetric node-level operator $M$ lies outside the scalar filter class $\mathcal{S}(L)$ iff it mixes Laplacian eigenmodes, and the Frobenius distance to the nearest scalar filter is exactly $\sum_{i\neq j}|u_i^{\top} M u_j|^2$. This reframes expressivity in terms of representational geometry rather than graph discrimination. The synthetic experiments are well-controlled: under identical degree sequences, Hodge encoding cuts the 4-clique counting MAE from $6.27$ to $3.91$, and the HodgeRandom ablation confirms that real triangle incidence structure matters. These results support the practical value of lifted incidence information.
The central gap is between theory and implementation. The theory analyzes linear node operators such as $M_{\triangle}=C_1C_2C_2^{\top}C_1^{\top}$, whereas the actual encoding uses absolute-valued eigenvectors of the edge Hodge Laplacian $L_1$ aggregated over node neighborhoods---a nonlinear pipeline the theory does not cover. On ZINC the strongest variant is Lower Hodge ($B_1^{\top}B_1$), which contains no triangle term $B_2B_2^{\top}$, so the benchmark does not test the paper's higher-order claim. The fixed-1-skeleton experiment highlighted in the abstract is buried in Appendix A.4 and never analyzed in the main text. Finally, Theorem 1 itself is essentially a diagonal-approximation bound in a fixed eigenbasis: useful, but not a deep new algebraic result.
The synthetic benchmarks are carefully designed: degree-preserving swaps isolate higher-order structure, and the randomized $B_2$ control isolates structural signal from dimensionality artifacts. Comparisons to LapPE, RWPE, and HOPSE-M-C are fair on these tasks. However, the claim that prior higher-order PSEs "are often constrained to particular types of higher-order structures, or require the neural architecture to process the higher-order structure itself" is inaccurate for HOPSE, which is explicitly a preprocessing-based, architecture-independent encoder. The real-world evidence is narrow: only ZINC is tested, and the main driver of improvement there is the edge-space lower Hodge component, not the triangle-mediated higher-order component that motivates the theory.
The authors provide a public repository and detailed hyperparameters in Appendix A, making the synthetic and ZINC experiments reproducible in principle. Preprocessing times are reported transparently: Hodge encoding takes $452.2$s for $5{,}000$ graphs versus $6.0$s for LapPE, a roughly $75\times$ overhead that grows sharply with graph size ($1{,}135.8$s at $n=70$). Without sparse or partial eigensolvers, scaling beyond small molecules will be difficult. The paper reports means and standard deviations over five independent trials but does not specify the random seed protocol. Backbone details are complete for Graph Transformers, though the authors' claim of backbone-agnostic benefits is not tested on standard GNNs.
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.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.