Alessio Borgi

Alessio Borgi

PhD in Graph Neural Networks and Generative AI 👨🏻‍💻🤖

Laplacian Eigenvectors as Graph Positional Encodings

4 minute read

Published:

TL;DR: The k smallest eigenvectors of the graph Laplacian form a k-dimensional coordinate system where distance in embedding space approximates graph distance. Nodes with similar structural positions get similar Laplacian PE vectors. This is the most theoretically grounded graph PE — but sign ambiguity requires careful handling.

The Graph Laplacian Eigen-Embedding

The graph Laplacian L = D − A (or its normalised form) has eigendecomposition:

L = U Λ Uᵀ, λ₁ ≤ λ₂ ≤ ... ≤ λₙ

The Laplacian Positional Encoding (LapPE) for node v is its row in the matrix U restricted to the first k eigenvectors:

pe_v = [u₂(v), u₃(v), ..., u_{k+1}(v)] ∈ ℝᵏ

(We skip u₁ = 1/√N, the constant eigenvector, as it carries no positional information.)

Why Eigenvectors Encode Position

The key property: eigenvectors minimise the Laplacian quadratic form subject to orthogonality. The first non-trivial eigenvector u₂ (the Fiedler vector) is the smoothest non-constant signal on the graph — it varies as slowly as possible across edges.

Concretely:

  • u₂ splits the graph at the largest “gap” — values are negative on one side, positive on the other. It approximates a 1D embedding of the graph along its longest axis.
  • u₃ gives the second most orthogonal smooth direction
  • Together, u₂ and u₃ embed the graph in 2D, capturing its global shape

Nodes close in the graph (short geodesic distance) tend to have similar eigenvector values. The k-dimensional LapPE approximates the metric structure of the graph.

Algebraic and Spectral Graph Theory Connection

The commute time distance between nodes i and j (expected random walk steps to travel from i to j and back) is:

CT(i,j) = Vol(G) · ||e_i − e_j||²_L⁺ ≈ Σₖ (uₖ(i) − uₖ(j))² / λₖ

Where L⁺ is the pseudoinverse of L. This is essentially the squared distance in the space spanned by eigenvectors weighted by 1/λₖ.

LapPE (without the 1/λₖ weighting) approximates this — nearby nodes in the graph get similar PE vectors.

Sign Ambiguity

A critical problem: if u is an eigenvector of L, so is -u. Eigenvectors are only defined up to sign (and up to rotation within eigenspaces of multiplicity > 1).

This means: if you run the eigenvector computation on the same graph twice, you may get u₂ one time and -u₂ the next. For nodes in two different graphs, the sign convention is arbitrary — you cannot compare PEs across graphs.

Solutions:

  • Random sign flipping during training: at each training step, randomly flip the sign of each eigenvector. This teaches the model to be sign-invariant.
  • SignNet (Lim et al., 2022): use a sign-invariant function (e.g., f(u) + f(-u)) to process eigenvectors before using them as PEs.
  • BasisNet: handles rotation ambiguity in higher-dimensional eigenspaces.

LapPE in Graph Transformers

LapPE is used in:

  • SAN (2021): full Laplacian spectrum as PE
  • Graphormer: adds degree centrality (not LapPE, but related)
  • GPS (2022): LapPE or RWPE as PE, fed into Transformer attention

Typical usage: concatenate pe_v to node features x_v, or add them as a separate encoding:

h_v = Linear(x_v) + Linear(pe_v)

Computational Cost

Computing k eigenvectors of an N×N Laplacian:

  • Dense: O(N³) — infeasible for large graphs
  • Sparse Lanczos/LOBPCG: O(k ·E) per iteration, O(k ·E· T) total — feasible for moderate N

For large graphs (N > 100,000), LapPE becomes expensive. Random walk PEs (next post) are a cheaper alternative.

What LapPE Can Distinguish

LapPE can distinguish nodes that 1-WL cannot: two nodes in the same regular graph (all same neighbourhood multisets) will have different eigenvector values if their global positions differ.

LapPE makes GNNs strictly more expressive than 1-WL — at the cost of a precomputation step and sign ambiguity handling.

Summary

PropertyLapPE  
Basisk smallest non-trivial Laplacian eigenvectors  
CapturesGlobal position, community structure, graph geometry  
MetricApproximates commute time distance  
Sign issue±1 ambiguity per eigenvector; requires SignNet or random flipping  
CostO(k·E·T) with sparse solver
ExpressivenessStrictly beyond 1-WL  
Used bySAN, GPS, many Graph Transformer papers  

LapPE is the gold standard for graph positional encodings when global structural position matters and computational cost is manageable.

References

You May Also Enjoy

Open Problems and Future Directions in Sheaf Neural Networks

5 minute read

Published:

Sheaf Neural Networks are a young field with many open research problems. This post surveys the most important unsolved questions: scalability to million-node graphs, stochastic sheaves for uncertainty quantification, sheaf autoencoders for generative models, connections to persistent homology, and unification with other topological deep learning frameworks.

Sheaf GNNs for Molecular Property Prediction

7 minute read

Published:

Molecular graphs are naturally heterophilic — atoms of different types bonded together — and have rich geometric structure (bond angles, torsion angles). Sheaf GNNs can encode this structure via restriction maps that represent the relational geometry between bonded atoms. This post explores how sheaf theory applies to molecular property prediction.

Sheaf GNNs for Heterophilic Node Classification: Benchmarks and Results

6 minute read

Published:

A systematic comparison of sheaf GNNs against baselines on standard heterophilic node classification benchmarks. Which datasets benefit most from sheaf structure? How does stalk dimension d affect performance? When do sheaves win — and when don’t they?

Sheaves Meet Attention: Transformer-Inspired Sheaf Models

6 minute read

Published:

Graph Transformers use global attention to capture long-range dependencies that local message passing misses. Sheaf Transformers combine sheaf-based local aggregation (with learnable relational geometry) with global attention (for long-range dependencies). This post surveys the design space of sheaf-augmented attention models.