Information-based Invariance, Equivariance, and Expressivity for Graph Neural Networks

Graph Neural Networks (GNNs) leverage the topology of graphs to learn informative representations. Since isomorphic graphs represent the same information, there has been a significant effort to develop GNNs that return the same results over isomorphic graphs (invariance/equivariance) and different results over non-isomorphic graphs (expressivity). However, it is known that the same information is often represented in nonisomorphic forms. In this paper, we postulate that GNNs should be invariant/equivariant and expressive with respect to these variations. We introduce the notions of invariance/equivariance of GNNs with respect to these variations and prove that current GNN architectures are not invariant/equivariant to these variations. We propose a general approach to modify a GNN to make it invariant/equivariant to these variations. We also generalize the current notion of expressivity to consider these variations and investigate the expressivity of the invariant/equivariant GNNs. Our empirical studies using multiple GNN architectures over real-world graphs indicate that our approach achieves perfect invariance/equivariance and improves the accuracy of current GNNs on average without imposing significant time overhead.