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

arXiv: https://arxiv.org/abs/2311.01647 · HTML: https://mlsanity.com/paper/2311.01647/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 40 references that are in the map.
- First posted on arXiv 3 Nov 2023.

## Builds on (most cited first, 23 of 23)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Temporal Graph Networks for Deep Learning on Dynamic Graphs](https://mlsanity.com/paper/2006.10637/) (2020)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [Inductive Representation Learning on Temporal Graphs](https://mlsanity.com/paper/2002.07962/) (2020)
- [EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs](https://mlsanity.com/paper/1902.10191/) (2019)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [GemNet: Universal Directional Graph Neural Networks for Molecules](https://mlsanity.com/paper/2106.08903/) (2021)
- [Structured Sequence Modeling with Graph Convolutional Recurrent Networks](https://mlsanity.com/paper/1612.07659/) (2016)
- [On the equivalence between graph isomorphism testing and function approximation with GNNs](https://mlsanity.com/paper/1905.12560/) (2019)
- [Dynamic Graph Convolutional Networks](https://mlsanity.com/paper/1704.06199/) (2017)
- [Relational Graph Attention Networks](https://mlsanity.com/paper/1904.05811/) (2019)
- [Few-Shot Graph Learning for Molecular Property Prediction](https://mlsanity.com/paper/2102.07916/) (2021)
- [Expressiveness and Approximation Properties of Graph Neural Networks](https://mlsanity.com/paper/2204.04661/) (2022)
- [ASGN: An Active Semi-supervised Graph Neural Network for Molecular Property Prediction](https://mlsanity.com/paper/2007.03196/) (2020)
- [Predicting Path Failure In Time-Evolving Graphs](https://mlsanity.com/paper/1905.03994/) (2019)
- [Estimating Node Importance in Knowledge Graphs Using Graph Neural Networks](https://mlsanity.com/paper/1905.08865/) (2019)
- [Dynamic Graph Representation Learning via Self-Attention Networks](https://mlsanity.com/paper/1812.09430/) (2018)
- [Are Powerful Graph Neural Nets Necessary? A Dissection on Graph Classification](https://mlsanity.com/paper/1905.04579/) (2019)
- [A Theory of Link Prediction via Relational Weisfeiler-Leman on Knowledge Graphs](https://mlsanity.com/paper/2302.02209/) (2023)
- [EvoKG: Jointly Modeling Event Time and Network Structure for Reasoning over Temporal Knowledge Graphs](https://mlsanity.com/paper/2202.07648/) (2022)

## Built on by (most cited first, 2 of 2)

- [The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logics](https://mlsanity.com/paper/2505.11930/) (2025)
- [Reification as a Transferable Vocabulary: Zero-Shot Link Prediction with Vanilla GNNs](https://mlsanity.com/paper/2609.11347/) (2026)

## Abstract (arXiv)

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 FOC2, a fragment of first-order logic with two variables and counting quantifiers. On the negative side, we demonstrate that the R2-GNN architecture, which extends the local message passing GNN by incorporating global readout, fails to capture FOC2 classifiers in the general case. Nevertheless, on the positive side, we establish that R2-GNNs models are equivalent to FOC2 classifiers under certain restricted yet reasonable scenarios. To address the limitations of R2-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 R2-GNNs to effectively capture any FOC2 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 R2-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 R2-GNN with the graph transformation outperforms the baseline methods on both synthetic and real-world datasets