Galois Theory Challenges Weisfeiler Leman: Invariant Features for Symmetric Matrices and Point Clouds

Blum-Smith et al. [2024] proposed a machine learning model on symmetric matrices that is invariant under the group action of permutation by conjugation. This model provides a new way to test whether two graphs are isomorphic. In this work, we investigate the expressive power of this new method. Our theoretical results show that on undirected graphs, the method is strictly worse than graph neural networks (GNNs). To improve expressivity, we propose a modified method which we test empirically against GNNs and the method of Blum-Smith et al. [2024].