Papers › Calibrate and Boost Logical Expressiveness of GNN Over Multi-Relational and Temporal Graphs
Calibrate and Boost Logical Expressiveness of GNN Over Multi-Relational and Temporal Graphs
Yeyuan Chen, Dingmin Wang
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 ℱ𝒪𝒞₂, a fragment of first-order logic with two variables and counting quantifiers. On the negative side, we demonstrate that the R²-GNN architecture, which extends the local message passing GNN by incorporating global readout, fails to capture ℱ𝒪𝒞₂ classifiers in the general case. Nevertheless, on the positive side, we establish that R²-GNNs models are equivalent to ℱ𝒪𝒞₂ classifiers under certain restricted yet reasonable scenarios. To address the limitations of R²-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²-GNNs to effectively capture any ℱ𝒪𝒞₂ 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²-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²-GNN with the graph transformation outperforms the baseline methods on both synthetic and real-world datasets
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections