Inductive Link Prediction for Both New Nodes and New Relation Types via Double Equivariance

Despite recent advances in relational learning, the task of inductive link prediction in discrete attributed multigraphs with both new nodes and new relation types in test remains an open problem. In this work we tackle this task by defining the concept of double exchangeability and its associated double-permutation equivariant graph neural network that are equivariant to permutations of both node identities and edge relations. Our neural architecture imposes a structural representation of relations that can inductively generalize from training nodes and relations to arbitrarily new test nodes and relations, without the need for adaptation or retraining, thus enabling a new direction in relational learning. Finally, we introduce a general blueprint for such double equivariant representations and empirically showcase its capability on two proposed real-world benchmarks that no existing works can perform accurately.