Calibrate and Boost Logical Expressiveness of GNN Over Multi-Relational and Temporal Graphs

As a powerful framework for graph representation learning, Graph Neural Networks (GNNs) have garnered significant attention in recent years. However, to the best of our knowledge, there has been no formal analysis of the logical expressiveness of GNNs as Boolean node classifiers over multi-relational graphs, where each edge carries a specific relation type. In this paper, we investigate \mathcal{FOC}_2, a fragment of first-order logic with two variables and counting quantifiers. On the negative side, we demonstrate that the R 2 -GNN architecture, which extends the local message passing GNN by incorporating global readout, fails to capture \mathcal{FOC}_2 classifiers in the general case. Nevertheless, on the positive side, we establish that R 2 -GNNs models are equivalent to \mathcal{FOC}_2 classifiers under certain restricted yet reasonable scenarios. To address the limitations of R 2 -GNNs regarding expressiveness, we propose a simple graph transformation technique, akin to a preprocessing step, which can be executed in linear time.