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
this https URL

我们提出了一种轻量级的预处理方法，叫做 Laplacian Canonization (LC)，通过直接找到特征向量的规范方向来解决问题，该方法适用于任何现有的 GNNs，并且发现了一种高效的算法，称为 Maximal Axis Projection (MAP)，这两者可以成功使超过 90% 的特征向量规范化。在实际数据集上的实验证明 MAP 方法在带来最小计算负荷的同时，持续优于现有方法。