Laplacian Canonization: A Minimalist Approach to Sign and Basis Invariant Spectral Embedding

Spectral embedding is a powerful graph embedding technique that has receiveda lot of attention recently due to its effectiveness on Graph Transformers.However, from a theoretical perspective, the universal expressive power ofspectral embedding comes at the price of losing two important invarianceproperties of graphs, sign and basis invariance, which also limits itseffectiveness on graph data. To remedy this issue, many previous methodsdeveloped costly approaches to learn new invariants and suffer from highcomputation complexity. In this work, we explore a minimal approach thatresolves the ambiguity issues by directly finding canonical directions for theeigenvectors, named Laplacian Canonization (LC). As a pure pre-processingmethod, LC is light-weighted and can be applied to any existing GNNs. Weprovide a thorough investigation, from theory to algorithm, on this approach,and discover an efficient algorithm named Maximal Axis Projection (MAP) thatworks for both sign and basis invariance and successfully canonizes more than90% of all eigenvectors. Experiments on real-world benchmark datasets likeZINC, MOLTOX21, and MOLPCBA show that MAP consistently outperforms existingmethods while bringing minimal computation overhead. Code is available athttps://github.com/PKU-ML/LaplacianCanonization.