Sign Ambiguity in Laplacian Eigenvectors
Published:
Intuition First: The Two-Sided Mirror
Imagine a ruler used to measure positions on a graph. Laplacian eigenvectors are like that ruler โ but the ruler has no fixed orientation: it can point left or right arbitrarily. Two runs of the same eigendecomposition may return the ruler flipped. If you train a model to recognise โhub nodes are at position +0.4 on the rulerโ, it will fail on the next graph where the same hub appears at โ0.4, even though the structural meaning is identical.
The Sign Problem
Compute the k-th Laplacian eigenvector u_k for graph G. Now compute it again (different random seed in the numerical solver). You may get u_k one time and -u_k the next.
For a node v with u_k[v] = +0.4 in the first computation, it gets u_k[v] = -0.4 in the second. These are different PE vectors โ yet they represent the same structural position.
This is not a numerical bug. It is mathematically fundamental: the eigenvalue equation L u = ฮป u is satisfied by both u and -u.
Consequences for Learning
Within a single graph: all nodes flip sign simultaneously (u โ -u for all v). The relative relationships between nodes are preserved. GNNs that use differences u_k[v] - u_k[w] are fine.
Across training batches (different graphs): if graph Gโ uses +u and graph Gโ (isomorphic to Gโ) uses -u, the model sees different PE vectors for structurally identical positions in two different graphs. This creates an inconsistent training signal.
Generalisation: a model trained on graphs where u_k happens to be positive for hub nodes will fail on test graphs where u_k is negative for hub nodes โ even if the graphs are structurally identical.
Concrete Worked Example: Sign Flip Breaks Training
Suppose you have two isomorphic graphs Gโ and Gโ in the same training batch. Both are 4-node paths. The 2nd Laplacian eigenvector for a path graph is uโ = [0.65, 0.38, โ0.38, โ0.65] (roughly). The two eigendecomposition calls return:
- Gโ: uโ = [+0.65, +0.38, โ0.38, โ0.65]
- Gโ: uโ = [โ0.65, โ0.38, +0.38, +0.65] (sign flipped)
Node 1 (hub at one end) gets PE = +0.65 in Gโ but PE = โ0.65 in Gโ. The model sees contradictory training signals for the structurally identical position. After many such examples, the model learns to ignore the PE โ or worse, learns a noisy representation. SignNet resolves this: it computes ฯ(+0.65) + ฯ(โ0.65) for both runs, which is always identical by the symmetry of addition.
The Rotation Ambiguity
The sign problem is a special case of a more general rotation ambiguity. When eigenvalue ฮป_k has multiplicity m > 1 (the k-th eigenspace is m-dimensional), any rotation within that m-dimensional eigenspace is valid. There are infinitely many orthonormal bases for the eigenspace.
For simple eigenvalues (multiplicity 1), only the ยฑ1 sign flip exists. For degenerate eigenvalues (highly symmetric graphs โ regular graphs, bipartite graphs), the ambiguity is a full O(m) rotation.
Solutions
1. Random Sign Flipping During Training
At each training step, randomly flip the sign of each eigenvector independently:
This data augmentation teaches the model to be sign-invariant empirically. Simple but doesnโt solve the rotation ambiguity for multiplicity > 1.
2. SignNet (Lim et al., 2022)
SignNet processes each eigenvector through a sign-equivariant network:
Where ฯ is a node-wise MLP and ฯ is a permutation-invariant function over eigenvectors. The sum f(u) + f(-u) is sign-invariant by construction: ฯ(u) + ฯ(-u) = ฯ(-u) + ฯ(u).
SignNet is equivariant to sign flips: if you flip u_k โ -u_k, the output PE is unchanged.
3. BasisNet (Lim et al., 2023)
Extends SignNet to handle arbitrary rotation ambiguity in degenerate eigenspaces. Uses a rotation-equivariant network within each eigenspace.
4. Use RWPE Instead
If sign ambiguity is problematic for your use case, switch to RWPE โ random walk return probabilities are always non-negative, have no sign ambiguity, and are computationally cheaper.
Summary
| Problem | Cause | Fix |
|---|---|---|
| Sign flip (simple eigenvalue) | L u = ฮปu and L(-u) = ฮป(-u) | Sign aug., SignNet |
| Rotation (degenerate eigenvalue) | Any rotation in eigenspace valid | BasisNet |
| Cross-graph inconsistency | Different runs โ different sign | SignNet (deterministic output) |
| Implementation complexity | Requires special handling | Use RWPE (no ambiguity) |
Sign ambiguity is the main practical obstacle to using LapPE. For most graph learning applications, either random sign flipping during training (simple and effective) or switching to RWPE (no ambiguity) is sufficient.
References
- Lim, D., Robinson, J., Zhao, L., Smidt, T., Sra, S., Maron, H., & Jegelka, S. (2022). Sign and Basis Invariant Networks for Spectral Graph Neural Networks. ICLR 2023.
- Belkin, M., & Niyogi, P. (2003). Laplacian Eigenmaps for Dimensionality Reduction and Data Representation. Neural Computation.
- Kreuzer, D., Beaini, D., Hamilton, W. L., Lรฉtourneau, V., & Tossou, P. (2021). Rethinking Graph Transformers with Spectral Attention. NeurIPS 2021.