Alessio Borgi

Alessio Borgi

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

Sign Ambiguity in Laplacian Eigenvectors

4 minute read

Published:

TL;DR: If Lu = λu, then L(-u) = λ(-u) also. Eigenvectors are only defined up to a ±1 sign flip (and up to rotation within multiplicity > 1 eigenspaces). Two runs of the same eigenvector computation can produce u and -u — giving nodes opposite PE vectors. SignNet handles this by using a sign-invariant neural network: f(u) + f(-u).

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.

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:

u_k → s_k · u_k, s_k ∈ {+1, -1} sampled uniformly

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:

pe_v = ρ( [φ(u_k[v]) + φ(-u_k[v])]_{k=1}^K )

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

ProblemCauseFix
Sign flip (simple eigenvalue)L u = λu and L(-u) = λ(-u)Sign aug., SignNet
Rotation (degenerate eigenvalue)Any rotation in eigenspace validBasisNet
Cross-graph inconsistencyDifferent runs → different signSignNet (deterministic output)
Implementation complexityRequires special handlingUse 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

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.