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. This
transformation enables R$^2$-GNNs to effectively capture any $\mathcal{FOC}_2$
classifiers when applied to the "transformed" input graph. Moreover, we extend
our analysis of expressiveness and graph transformation to temporal graphs,
exploring several temporal GNN architectures and providing an expressiveness
hierarchy for them. To validate our findings, we implement R$^2$-GNNs and the
graph transformation technique and conduct empirical tests in node
classification tasks against various well-known GNN architectures that support
multi-relational or temporal graphs. Our experimental results consistently
demonstrate that R$^2$-GNN with the graph transformation outperforms the
baseline methods on both synthetic and real-world datasets

在这篇论文中，我们研究了图神经网络的逻辑表达能力，特别是其作为多关系图上的布尔节点分类器的能力，并提出了一种简单的图转换技术来增强图神经网络的表达能力。我们还将研究扩展到了时间图上，并通过实验证明了我们的发现。