Laplacian Canonization: A Minimalist Approach to Sign and Basis Invariant Spectral Embedding
Published in NeurIPS, 2023
Recommended citation: Jiangyan Ma, Yifei Wang, Yisen Wang (2023). Laplacian Canonization: A Minimalist Approach to Sign and Basis Invariant Spectral Embedding. In Thirty-seventh Conference on Neural Information Processing Systems. https://openreview.net/forum?id=1mAYtdoYw6
Laplacian eigenvectors offer universal expressive power as a graph positional encoding technique. However, they also suffer from ambiguities related to sign and basis. In our research, we uncovered that achieving permutation equivariance, sign/basis invariance, and universality simultaneously in Graph Neural Networks (GNNs) is not possible. To address this challenge, we developed the Laplacian Canonization algorithm that eliminates the sign and basis ambiguities of Laplacian eigenvectors. We further established the necessary and sufficient conditions for canonizing Laplacian eigenvectors into a canonical form. Our work on Laplacian Canonization was accepted as a poster at NeurIPS 2023.