Laplacian Eigenvectors as Graph Positional Encodings

Intuition First

Imagine stretching a rubber graph flat on a table so that connected nodes end up close together. The 1D layout that minimises total squared edge length, subject to being centred and unit-norm so the layout cannot collapse to a point, is exactly the Fiedler vector \(u_2\). Adding a second coordinate orthogonal to the first gives \(u_3\). 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 combinatorial graph Laplacian \(L = D - A\) is symmetric and positive semi-definite, so it has an orthonormal eigendecomposition:

The Laplacian Positional Encoding (LapPE) for node \(v\) is that node’s entry in each of the first \(k\) non-trivial eigenvectors:

We skip \(u_1\), which spans the kernel of \(L\). For a connected graph and \(L = D - A\) this is the constant vector \(\mathbf{1}/\sqrt{N}\), carrying no positional information. Two caveats: if the graph has \(c\) connected components then \(\lambda_1 = \dots = \lambda_c = 0\) and the whole kernel is \(c\)-dimensional, so more than one eigenvector must be discarded (or, better, the components handled separately); and if you use \(L_{\mathrm{sym}} = I - D^{-1/2}AD^{-1/2}\) instead, the trivial eigenvector is \(D^{1/2}\mathbf{1}\) normalised, which is not constant, it encodes degree.

Why Eigenvectors Encode Position

The key property is a variational one. For any vector \(x\),

so minimising \(x^{\top}Lx\) means making the signal vary as little as possible across edges. Subject to \(\lVert x \rVert = 1\) and \(x \perp u_1\), the minimiser is exactly \(u_2\), the smoothest non-constant signal the graph admits. Each subsequent \(u_i\) is the smoothest signal orthogonal to all the previous ones.

Concretely:

• \(u_2\) (the Fiedler vector) splits the graph across its sparsest cut, negative on one side, positive on the other. Its relation to the true minimum-conductance cut is a relaxation, made rigorous by Cheeger’s inequality rather than an exact correspondence.
• \(u_3\) gives the smoothest direction orthogonal to \(u_2\)
• Together \(u_2\) and \(u_3\) embed the graph in 2D, capturing its coarse global shape

Nodes close in the graph tend to have similar eigenvector values, though “close in the graph” here means well connected, not necessarily short geodesic distance; two nodes joined by a single bridge can be one hop apart yet land far apart in \(u_2\).

Algebraic and Spectral Graph Theory Connection

The commute-time distance between \(i\) and \(j\), the expected number of random-walk steps to go from \(i\) to \(j\) and back, has an exact spectral expression:

where \(L^{+}\) is the Moore–Penrose pseudoinverse of \(L\) and \(\mathrm{vol}(G) = \sum_v d_v = 2\lvert E\rvert\). Note this is an identity, not an approximation, and the sum starts at \(m = 2\) because the kernel direction contributes nothing.

Truncating to \(k\) terms and dropping the \(1/\lambda_m\) weights, which is what plain LapPE does, is therefore not the commute-time metric. It is a related coordinate system: the truncation keeps the terms with the smallest \(\lambda_m\), which are precisely the ones commute time weights most heavily, so the low-frequency structure survives; but the reweighting is discarded, so Euclidean distance between LapPE vectors should be read as a heuristic proxy for graph proximity, not as \(\mathrm{CT}\).

Sign and Basis Ambiguity

A critical problem: if \(u\) is an eigenvector of \(L\), so is \(-u\). Eigenvectors come with two distinct ambiguities:

• Sign. Each eigenvector of a simple (multiplicity-one) eigenvalue is determined only up to \(\pm 1\). Taking \(k\) eigenvectors, that is \(2^{k}\) equally valid encodings of the same graph.
• Basis. If an eigenvalue has multiplicity \(m > 1\), any orthonormal basis of its \(m\)-dimensional eigenspace is equally valid, the ambiguity is the full orthogonal group \(O(m)\), not a finite set. This is common: cycles have doubly degenerate eigenvalues, and \(K_N\) has one eigenvalue of multiplicity \(N-1\).

So two runs of the same solver on the same graph can return \(u_2\) and \(-u_2\), and PE vectors are not directly comparable across graphs.

Solutions:

• Random sign flipping during training: sample a fresh \(s_i \in \{-1,+1\}\) per eigenvector each step. Cheap data augmentation that pushes the model toward sign invariance without guaranteeing it, and it does nothing about basis ambiguity.
• SignNet (Lim et al., 2022): build the encoding from \(\phi(u_i) + \phi(-u_i)\), which is sign-invariant by construction rather than by training.
• BasisNet (same work): extends this to invariance under \(O(m)\) within each eigenspace, by acting on the eigenspace projectors \(U_m U_m^{\top}\), which are basis-independent.

Neither fixes the deeper limit: any such invariant encoding is a function of the graph, so automorphic nodes still receive identical values.

LapPE in Graph Transformers

LapPE is used in:

• SAN (2021): learns its PE by running a Transformer over the \((\lambda_i, u_i(v))\) pairs, so the encoding is a function of the spectrum rather than of raw eigenvector entries
• Graphormer: uses degree centrality and shortest-path biases instead, related in spirit, but not spectral
• GPS (2022): LapPE or RWPE, fed in alongside node features

Typical usage: project the PE and add it to the projected node features, so the two live in the same space:

Computational Cost

Computing the \(k\) smallest non-trivial eigenvectors of an \(N \times N\) Laplacian:

• Dense (full eigendecomposition): \(O(N^3)\) time, \(O(N^2)\) memory, fine for a 30-atom molecule, infeasible beyond a few thousand nodes
• Sparse iterative (Lanczos / LOBPCG): each iteration costs \(O(k\lvert E\rvert)\), giving \(O(k\lvert E\rvert T)\) for \(T\) iterations

The iterative bound deserves a caveat: \(T\) is not a constant you control. It depends on the spectral gap separating the eigenvalues you want from the rest. On a graph with well-separated low eigenvalues convergence is fast; on one with a cluster of near-equal eigenvalues, exactly the degenerate case that also causes basis ambiguity, it can be slow, and the returned basis within the cluster is numerically unstable into the bargain. So the honest statement is that LapPE is cheap on small or well-separated graphs and unreliable in cost on large or highly symmetric ones. Random-walk PEs (next post) sidestep this entirely.

Worked Numerical Example

Consider the path graph \(P_4\): 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 ]

For a path \(P_n\) the eigenvalues are \(\lambda_m = 2 - 2\cos\!\big(\pi (m-1)/n\big)\) and the eigenvectors are \(u_m(i) \propto \cos\!\big(\pi (m-1)(i - \tfrac12)/n\big)\). For \(n = 4\):

\(\lambda_1 = 0\), \(\lambda_2 = 2-\sqrt{2} \approx 0.586\), \(\lambda_3 = 2\), \(\lambda_4 = 2+\sqrt{2} \approx 3.414\).

Fiedler vector, normalised to unit length:

Node 1 sits at one extreme, node 4 at the other, and nodes 2 and 3 in between, recovering the linear order of the path. A GNN given these values as extra features can now separate node 1 from node 4 and node 2 from node 3, which no amount of message passing would achieve on its own.

But read the “or its negation” seriously. All four values flip together, and \(P_4\)’s reversal automorphism means node 1 and node 4 are automorphic: the encoding tells them apart only by sign, and a sign-invariant read-out puts them back together. What LapPE genuinely adds here is the relative geometry, that 1 and 4 are at opposite extremes while 2 and 3 are central.

What LapPE Can Distinguish

Adding any graph-derived feature to node inputs can only increase what an MPNN separates, so LapPE-augmented GNNs are at least as expressive as 1-WL, and there exist pairs they separate that 1-WL cannot, for example two nodes in a regular graph, where 1-WL assigns a single colour but the eigenvectors vary.

Three conditions temper that:

• Cospectral graphs. Two non-isomorphic graphs can share an identical Laplacian spectrum. Where the eigenvalues also fail to distinguish the relevant nodes, LapPE adds nothing that 1-WL did not already have.
• Automorphism. Nodes in the same automorphism orbit cannot be separated by any equivariant encoding.
• Invariance costs power. The sign- and basis-invariant treatments needed to make LapPE usable discard information. What you can actually exploit is what survives the invariantisation, not the raw eigenvector.

So: strictly more expressive than 1-WL on some inputs, not uniformly, and the gain depends on how the ambiguity is handled.

Summary

LapPE is the reference choice for graph positional encodings when low-frequency global position is what the task needs, the graph is small enough for a reliable eigensolve, and you are willing to handle sign and basis ambiguity properly.

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).