🤖 machine learning

Understanding Truncated Positional Encodings for Graph Neural Networks

This paper investigates the theoretical and empirical implications of using truncated positional encodings in graph neural networks, revealing that such truncation fundamentally alters the expressive power of different encoding families—rendering spectral variants no stronger than the 1-WL test—and demonstrating that combining multiple truncated encodings outperforms using any single family on real-world datasets.

Original authors: James Flora, Mitchell Black, Weng-Keen Wong, Amir Nayyeri

Published 2026-06-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: James Flora, Mitchell Black, Weng-Keen Wong, Amir Nayyeri

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to understand the layout of a city. The robot is a Graph Neural Network (GNN), and the city is a graph made of intersections (nodes) and streets (edges).

To do a good job, the robot needs more than just a list of which streets connect to which. It needs Positional Encodings (PEs). Think of PEs as a "map" or a "compass" that tells the robot where every intersection is relative to every other one. Without this map, the robot is like a person walking through a city with their eyes closed, only knowing who is standing right next to them, but having no idea if they are near the center of town or stuck in a dead-end alley.

The Problem: The "Perfect" Map is Too Heavy

There are two main ways to create this perfect map:

The Spectral Map: This uses complex math (eigenvalues and eigenvectors) to see the "vibrations" or global shape of the city.
The Walk Map: This counts how many ways you can walk from one point to another in 1 step, 2 steps, 3 steps, and so on.

Mathematically, if you use the entire map (all steps, all vibrations), these two methods are equally powerful. They can distinguish between almost any two different city layouts.

However, there's a catch: Creating this "complete" map for a large city takes a massive amount of computer power and memory (specifically, it gets exponentially harder as the city grows). It's like trying to carry a library of every possible map of the world in your backpack. It's too heavy to use in real life.

So, engineers use Truncated Positional Encodings. Instead of the whole library, they just take the first few chapters.

Truncated Spectral: Just the first few "vibrations" (eigenvectors).
Truncated Walk: Just the first few walking steps (powers of the adjacency matrix).

The big question the paper asks is: If we chop off the end of these maps, do they still work the same way?

The Big Discovery: "Cutting" Changes Everything

The authors found a surprising answer: No, they don't work the same way anymore.

When you have the complete map, Spectral and Walk methods are twins. But when you truncate (cut) them, they become very different siblings with different strengths and weaknesses.

The "Truncated Spectral" Trap: Sometimes, using just the first few vibrations actually makes the robot worse at understanding the city than if it had no map at all! In some cases, a truncated spectral map is so weak that it can't even tell the difference between two cities that a very simple "neighbor-checking" test (called the 1-WL test) can easily spot.
The "Truncated Walk" Trap: Conversely, there are city layouts that a truncated walk map (counting just a few steps) completely misses, but a truncated spectral map catches immediately.

The Analogy: Imagine trying to identify a person.

The Complete Spectral Map is like knowing their entire DNA and life history.
The Truncated Spectral Map is like only knowing their height.
The Truncated Walk Map is like only knowing how many steps it takes to walk from their house to the grocery store.

If you only know their height (Truncated Spectral), you might confuse two people of the same height. If you only know their walking distance (Truncated Walk), you might confuse two people who live the same distance from the store. But if you use both, you get a much better picture.

The New Hero: "Harmonic Distances"

The paper introduces a new family of maps called k-harmonic distances.

Think of Effective Resistance (a type of 1-harmonic distance) as measuring how "connected" two points are, like how much electricity flows between them.
The paper shows that Biharmonic distance (2-harmonic) measures something different: how "central" or important a street is to the whole city.

The authors prove that while these new maps are powerful, they also have limits. If you only use the "resistance" map, you might miss details that the "biharmonic" map catches, and vice versa. However, if you use enough of these harmonic maps, you can recreate the power of the complete, heavy maps.

The Practical Advice: "Mix and Match"

Since no single "cut" map is perfect, the authors suggest a simple rule of thumb for engineers: Don't rely on just one type of truncated map.

Instead, mix them together.

Combine a few steps of the "Walk" map.
Combine a few "vibrations" of the "Spectral" map.
Throw in a "Harmonic" distance or two.

The Experiment:
The authors tested this on real-world datasets (like predicting chemical properties of molecules).

Using just one type of truncated map was okay.
Using a mixture of different truncated maps was significantly better.

It's like trying to navigate a city: having a compass (Spectral), a pedometer (Walk), and a measure of traffic flow (Harmonic) all at once is much better than relying on just one of them.

Summary

Full maps are too heavy for real-world use, so we use "truncated" (cut) versions.
Cutting breaks the equality: Truncated Spectral and Truncated Walk maps are no longer equal; they have different blind spots.
Some cuts are worse than no map: In some cases, a truncated spectral map is weaker than a very basic test.
The Solution: Don't pick one. Mix different types of truncated maps to get the best performance without the heavy computational cost.

Technical Summary: Understanding Truncated Positional Encodings for Graph Neural Networks

Problem Statement

Graph Neural Networks (GNNs), particularly Message Passing Neural Networks (MPNNs), are fundamentally limited in their ability to capture global structural information, a constraint formalized by their equivalence to the 1-Weisfeiler-Lehman (1-WL) test. To overcome this, Graph Transformers (GTs) and enhanced GNNs utilize Positional Encodings (PEs) to inject structural information. Two dominant families of PEs are spectral encodings (derived from Laplacian eigenspaces) and walk-based encodings (derived from powers of the adjacency matrix).

Theoretically, complete versions of these encodings (using $\Omega(n)$ eigenvectors or matrix powers) are equivalent in expressive power, lying between the 1-WL and 3-WL tests. However, computing these complete encodings requires $O(n^3)$ time and space complexity, which is prohibitive for real-world applications. Consequently, practitioners rely on truncated variants (e.g., the first $k$ eigenvectors or first $k$ powers of the adjacency matrix). The theoretical properties, expressive power, and comparative strengths of these truncated PEs remain largely unexplored, creating a gap between theoretical guarantees and practical implementation.

Methodology

The authors initiate a systematic study of truncated PEs through both theoretical analysis and empirical validation.

Theoretical Framework

The paper utilizes the WL hierarchy and its variants to characterize the expressive power of different PEs:

$\psi$ -WL Test: A variant of the WL test where node colors are updated using a relative positional encoding (RPE) $\psi$ .
Sparse- $\psi$ -WL Test: An extension for MPNNs where $\psi$ is used as edge features.
Key Families Analyzed:
1. Truncated Eigenspace Projections ( $k$ -EP-WL): Using the first $k$ eigenspace projections of the Laplacian.
2. Truncated Walk Encodings ( $k$ -Walk-WL): Using the first $k$ powers of the adjacency matrix.
3. Effective Resistance (Resistance-WL): A specific spectral distance (1-harmonic distance).
4. $k$ -Harmonic Distances: A generalization of effective resistance defined as $H_k(u, v) = \sqrt{(1_u - 1_v)^T (L^+)^k (1_u - 1_v)}$ .

The authors construct specific graph pairs (e.g., products of path graphs and complete graphs, or cycles vs. disjoint unions of cycles) to prove separability or indistinguishability under different truncated PEs and WL tests.

Empirical Evaluation

Experiments were conducted on three benchmarks:

BREC: A dataset designed to measure the "realized expressivity" of GNNs by testing their ability to distinguish non-isomorphic graphs ranging from 1-WL to 4-WL indistinguishable.
ZINC-12k: A graph regression benchmark for molecular solubility, used to test the hypothesis that mixing truncated PEs improves performance.
ogbg-molhiv: A binary classification benchmark for HIV inhibition.

The authors evaluated Graphormer-GD architectures and MPNNs (GINE) using various combinations of truncated PEs, including single families and mixtures of spectral, walk, and $k$ -harmonic encodings.

Key Contributions and Results

1. Divergence of Expressive Power in Truncated Forms

The paper proves that while complete spectral and walk encodings are equivalent, their truncated forms are fundamentally different:

Truncated Spectral vs. 1-WL: The authors show that truncated eigenspace projections ( $k$ -EP-WL) can be weaker than the 1-WL test. Specifically, there exist graph pairs distinguishable by 1-WL but indistinguishable by $k$ -EP-WL for $k \in \Omega(n)$ (Theorem 4.1).
Truncated Walk vs. Spectral: Conversely, there exist graph pairs distinguishable by a single eigenspace projection (1-EP-WL) but indistinguishable by $\Omega(n)$ -size walk encodings (Theorem 4.2).
Implication: No single truncated PE family is strictly superior; they capture different structural aspects and can be incomparable to the standard WL hierarchy.

2. Limitations of Effective Resistance

The paper analyzes Effective Resistance (1-harmonic distance) and finds it to be a weaker PE than full eigenspace projections or walk encodings on weighted graphs.

Theorem 4.3: There exist weighted graphs indistinguishable by Resistance-WL but distinguishable by Adjacency-WL (and thus 1-WL on unweighted graphs).
Corollary 4.1: Resistance-WL does not encode the entire spectrum of the graph, disproving a previous conjecture.

3. $k$ -Harmonic Distances as a Bridge

The authors introduce $k$ -harmonic distances as a natural bridge between spectral and polynomial encodings.

Completeness: Concatenating $\Theta(n)$ $k$ -harmonic distances yields an encoding equivalent in power to complete spectral or walk encodings (Theorem 4.6).
Differential Power: Even within the $k$ -harmonic family, fixed-size encodings differ. For example, the biharmonic distance (2-harmonic) can distinguish certain tree pairs in a constant number of iterations, whereas effective resistance (1-harmonic) requires $O(n)$ iterations (Theorem 4.7).
Robustness: However, if one $k$ -harmonic distance distinguishes a pair of graphs, most other $k$ -harmonic distances will also distinguish them (Theorem 4.8).

4. Empirical Findings: The Power of Mixing

BREC Results: $k$ -harmonic distances achieved competitive results with single-channel, low-overhead encodings, often matching the theoretical ceiling for graphs between 1-WL and 3-WL.
ZINC Results: The most significant finding is that mixing PEs from different families (e.g., combining truncated walks and $k$ -harmonics) outperforms any single family. A mixture of truncated walks and $k$ -harmonics achieved the lowest Mean Absolute Error (MAE) on ZINC-12k, surpassing single-family baselines.
Efficiency: The paper notes that $k$ -harmonic distances can be approximated in $O(mk \cdot \text{poly}(\log n))$ time using fast Laplacian solvers and Johnson-Lindenstrauss projections, avoiding the $O(n^3)$ cost of exact computation.

Significance and Claims

The paper claims to initiate the theoretical study of truncated positional encodings, shifting the perspective from viewing them merely as approximations of complete encodings to viewing them as a distinct design space with unique expressive properties.

Theoretical Insight: The work demonstrates that truncation fundamentally alters the information captured by PEs, making them incomparable to the standard WL hierarchy in specific cases.
Practical Guidance: The authors propose a rule-of-thumb: mix PEs from different families when using truncated encodings. This approach captures complementary structural cues while controlling computational costs.
Modest Scope: The authors acknowledge that while graph isomorphism is a principled proxy, real-world tasks involve downstream signals (centrality, motifs) that may not strictly align with isomorphism testing. Thus, the primary contribution is establishing a theoretical foundation and a starting point for systematic empirical study, rather than claiming a universal solution for all graph learning tasks.