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

arXiv: https://arxiv.org/abs/2310.18716 · HTML: https://mlsanity.com/paper/2310.18716/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 63 references that are in the map.
- First posted on arXiv 28 Oct 2023.

## Builds on (most cited first, 30 of 42)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Optuna: A Next-generation Hyperparameter Optimization Framework](https://mlsanity.com/paper/1907.10902/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [Graph Transformer Networks](https://mlsanity.com/paper/1911.06455/) (2019)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Residual Gated Graph ConvNets](https://mlsanity.com/paper/1711.07553/) (2017)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks](https://mlsanity.com/paper/1909.01315/) (2019)
- [Position-aware Graph Neural Networks](https://mlsanity.com/paper/1906.04817/) (2019)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [Universal Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/1905.04943/) (2019)
- [Sign and Basis Invariant Networks for Spectral Graph Representation Learning](https://mlsanity.com/paper/2202.13013/) (2022)
- [On the equivalence between graph isomorphism testing and function approximation with GNNs](https://mlsanity.com/paper/1905.12560/) (2019)
- [Equivariant Subgraph Aggregation Networks](https://mlsanity.com/paper/2110.02910/) (2021)

## Built on by (most cited first, 21 of 21)

- [A Canonicalization Perspective on Invariant and Equivariant Learning](https://mlsanity.com/paper/2405.18378/) (2024)
- [Scale Equivariant Graph Metanetworks](https://mlsanity.com/paper/2406.10685/) (2024)
- [Equivariance via Minimal Frame Averaging for More Symmetries and Efficiency](https://mlsanity.com/paper/2406.07598/) (2024)
- [On the Expressive Power of Spectral Invariant Graph Neural Networks](https://mlsanity.com/paper/2406.04336/) (2024)
- [Denoising Functional Maps: Diffusion Models for Shape Correspondence](https://mlsanity.com/paper/2503.01845/) (2025)
- [ELECTRA: A Cartesian Network for 3D Charge Density Prediction with Floating Orbitals](https://mlsanity.com/paper/2503.08305/) (2025)
- [On the Theoretical Expressive Power and the Design Space of Higher-Order Graph Transformers](https://mlsanity.com/paper/2404.03380/) (2024)
- [Baking Symmetry into GFlowNets](https://mlsanity.com/paper/2406.05426/) (2024)
- [Rethinking Diffusion Models with Symmetries through Canonicalization with Applications to Molecular Graph Generation](https://mlsanity.com/paper/2602.15022/) (2026)
- [Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum](https://mlsanity.com/paper/2506.05530/) (2025)
- [Adaptive Canonicalization with Application to Invariant Anisotropic Geometric Networks](https://mlsanity.com/paper/2509.24886/) (2025)
- [Using Random Noise Equivariantly to Boost Graph Neural Networks Universally](https://mlsanity.com/paper/2502.02479/) (2025)
- [Rotary Position Encodings for Graphs](https://mlsanity.com/paper/2509.22259/) (2025)
- [Generalizable Spectral Embedding with an Application to UMAP](https://mlsanity.com/paper/2501.11305/) (2025)
- [Sketch-Augmented Features Improve Learning Long-Range Dependencies in Graph Neural Networks](https://mlsanity.com/paper/2511.03824/) (2025)
- [A Graph Laplacian Eigenvector-based Pre-training Method for Graph Neural Networks](https://mlsanity.com/paper/2509.02803/) (2025)
- [Simultaneous Monitoring of Shape and Surface Color via 4D Point Clouds: A Registration-free Approach](https://mlsanity.com/paper/2605.08753/) (2026)
- [When and How to Canonize: A Generalization Perspective](https://mlsanity.com/paper/2605.11008/) (2026)
- [Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them](https://mlsanity.com/paper/2605.23446/) (2026)
- [CLEARMIND: Closed-Form Laplacian Embeddings of Arakelov-Green Resistance for Morphological Intrinsic Neuronal Distances](https://mlsanity.com/paper/2608.04460/) (2026)
- [Converse and Collision-Based Achievability for Node Localization with Hybrid Distance-Spectral Graph Positional Encodings](https://mlsanity.com/paper/2608.30152/) (2026)

## Abstract (arXiv)

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.