Laplacian Canonization: A Minimalist Approach to Sign and Basis Invariant Spectral Embedding
This addresses a theoretical limitation in graph neural networks for researchers and practitioners, offering a lightweight pre-processing solution, though it is incremental as it builds on prior spectral embedding methods.
The paper tackles the loss of sign and basis invariance in spectral embedding for graphs, which limits effectiveness, by proposing Laplacian Canonization (LC) with an efficient Maximal Axis Projection (MAP) algorithm that canonizes over 90% of eigenvectors and outperforms existing methods on benchmarks like ZINC, MOLTOX21, and MOLPCBA with minimal computation overhead.
Spectral embedding is a powerful graph embedding technique that has received a lot of attention recently due to its effectiveness on Graph Transformers. However, from a theoretical perspective, the universal expressive power of spectral embedding comes at the price of losing two important invariance properties of graphs, sign and basis invariance, which also limits its effectiveness on graph data. To remedy this issue, many previous methods developed costly approaches to learn new invariants and suffer from high computation complexity. In this work, we explore a minimal approach that resolves the ambiguity issues by directly finding canonical directions for the eigenvectors, named Laplacian Canonization (LC). As a pure pre-processing method, LC is light-weighted and can be applied to any existing GNNs. We provide a thorough investigation, from theory to algorithm, on this approach, and discover an efficient algorithm named Maximal Axis Projection (MAP) that works for both sign and basis invariance and successfully canonizes more than 90% of all eigenvectors. Experiments on real-world benchmark datasets like ZINC, MOLTOX21, and MOLPCBA show that MAP consistently outperforms existing methods while bringing minimal computation overhead. Code is available at https://github.com/PKU-ML/LaplacianCanonization.