Sign and Basis Invariant Networks for Spectral Graph Representation Learning

We introduce SignNet and BasisNet---new neural architectures that are invariant to two key symmetries displayed by eigenvectors: (i) sign flips, since if v is an eigenvector then so is -v; and (ii) more general basis symmetries, which occur in higher dimensional eigenspaces with infinitely many choices of basis eigenvectors. We prove that our networks are universal, i.e., they can approximate any continuous function of eigenvectors with proper invariances. When used with Laplacian eigenvectors, our architectures are also theoretically expressive for graph representation learning, in that they can approximate any spectral graph convolution, can compute spectral invariants that go beyond message passing neural networks, and can provably simulate previously proposed graph positional encodings. Experiments show the strength of our networks for processing geometric data, in tasks including: molecular graph regression, learning expressive graph representations, and learning neural fields on triangle meshes.