Laplacian Eigenvectors as Graph Positional Encodings
Published:
Intuition First
Imagine stretching a rubber graph flat on a table so that connected nodes end up close together and disconnected nodes end up far apart. The optimal 1D layout (minimising edge lengths) is exactly the Fiedler vector u₂. The optimal 2D layout is (u₂, u₃). These eigenvectors give the graph its natural coordinate system.
Nodes with similar graph positions get similar Laplacian PE vectors — not because we designed it that way, but because the eigenvectors mathematically encode the graph’s geometry.
The Graph Laplacian Eigen-Embedding
The graph Laplacian L = D − A (or its normalised form) has eigendecomposition:
The Laplacian Positional Encoding (LapPE) for node v is its row in the matrix U restricted to the first k eigenvectors:
(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:
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:
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.
Worked Numerical Example
Consider the path graph P₄: nodes {1, 2, 3, 4} with edges {1–2, 2–3, 3–4}.
The graph Laplacian is:
L = D - A =
[ 1 -1 0 0 ]
[-1 2 -1 0 ]
[ 0 -1 2 -1 ]
[ 0 0 -1 1 ]
Eigenvalues: λ₁=0, λ₂≈0.586, λ₃=2, λ₄≈3.414
Fiedler vector (u₂): approximately [−0.600, −0.371, +0.371, +0.600]
This assigns node 1 a negative value (one end), node 4 a positive value (other end), and nodes 2 and 3 intermediate values — perfectly encoding the linear order of the path. A 2-layer GCN with these PE values can now distinguish nodes 1 from 4, and 2 from 3.
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
| Property | LapPE | ||
|---|---|---|---|
| Basis | k smallest non-trivial Laplacian eigenvectors | ||
| Captures | Global position, community structure, graph geometry | ||
| Metric | Approximates commute time distance | ||
| Sign issue | ±1 ambiguity per eigenvector; requires SignNet or random flipping | ||
| Cost | O(k· | E | ·T) with sparse solver |
| Expressiveness | Strictly beyond 1-WL | ||
| Used by | SAN, 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
- Belkin, M., & Niyogi, P. (2003). Laplacian Eigenmaps for Dimensionality Reduction and Data Representation. Neural Computation.
- Dwivedi, V. P., Lim, A. T., Beaini, D., & Lió, P. (2021). Graph Neural Networks with Learnable Structural and Positional Representations. ICLR 2022.
- Kreuzer, D., Beaini, D., Hamilton, W. L., Létourneau, V., & Tossou, P. (2021). Rethinking Graph Transformers with Spectral Attention. NeurIPS 2021 (SAN).