A Theory of Link Prediction via Relational Weisfeiler-Leman on Knowledge Graphs

Xingyue Huang, Miguel Romero, I. Ceylan, P. Barceló

Abstract

Graph neural networks are prominent models for representation learning over graph-structured data. While the capabilities and limitations of these models are well-understood for simple graphs, our understanding remains incomplete in the context of knowledge graphs. Our goal is to provide a systematic understanding of the landscape of graph neural networks for knowledge graphs pertaining to the prominent task of link prediction. Our analysis entails a unifying perspective on seemingly unrelated models and unlocks a series of other models. The expressive power of various models is characterized via a corresponding relational Weisfeiler-Leman algorithm. This analysis is extended to provide a precise logical characterization of the class of functions captured by a class of graph neural networks. The theoretical findings presented in this paper explain the benefits of some widely employed practical design choices, which are validated empirically.

Benchmark Results

Tested on 3 datasets 2 baseline values reported too low

Tables show presented results in global context (best 3 papers + GCN + MLP).

OGB

ogbl-biokg

Global leaderboard →

#	Model	MRR ↑	Paper
1	PairRE+LRE code ↗ Trad 501.0M global	0.8360	PIE: a Parameter and Inference Efficient Solution for Large Scale Knowledge Graph Embedding … code ↗
2	NBFnet code ↗ GNN 3.0M global	0.8317	Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction code ↗
3	AutoSF code ↗ Trad 500.0M global	0.8309 ±0.0008	TripleRE: Knowledge Graph Embeddings via Tripled Relation Vectors code ↗
10	C-MPNN GNN ★ proposed	0.7900	This paper
12	RGCN GNN baseline	0.6360	This paper

Knowledge Graphs

WN18RR

Global leaderboard →

Default metric is MRR. The paper reports 5 values on MRR and 15 values on Hits@10 .

#	Model	MRR ↑ default	Hits@10 ↑	Paper
1	C-MPNN (PNA, Msg_r^2, f(t)=t, Init^2, no readout) GNN baseline	—	0.9470	Hits@10 0.9470 This paper
1	C-MPNN (PNA, Msg_r^3, f(t)=0, Init^2, no readout) GNN baseline	—	0.9470	Hits@10 0.9470 This paper
1	C-MPNN (PNA, Msg_r^2, f(t)=0, Init^2, no readout) GNN baseline	—	0.9460	Hits@10 0.9460 This paper
1	C-MPNN (PNA, Msg_r^1, f(t)=t, Init^2, global readout) GNN baseline	—	0.9460	Hits@10 0.9460 This paper
1	C-MPNN (PNA, Msg_r^3, f(t)=t, Init^2, no readout) GNN baseline	—	0.9440	Hits@10 0.9440 This paper
1	C-MPNN (sum, Msg_r^3, f(t)=0, Init^2, no readout) GNN baseline	—	0.9430	Hits@10 0.9430 This paper
1	C-MPNN (PNA, Msg_r^1, f(t)=0, Init^2, no readout) GNN baseline	—	0.9430	Hits@10 0.9430 This paper
1	C-MPNN (PNA, Msg_r^1, f(t)=t, Init^2, no readout) GNN baseline	—	0.9410	Hits@10 0.9410 This paper
1	C-MPNN (sum, Msg_r^2, f(t)=0, Init^2, no readout) GNN baseline	—	0.9390	Hits@10 0.9390 This paper
1	C-MPNN (sum, Msg_r^2, f(t)=t, Init^2, no readout) GNN baseline	—	0.9370	Hits@10 0.9370 This paper
1	C-MPNN (sum, Msg_r^1, f(t)=0, Init^2, no readout) GNN baseline	—	0.9340	Hits@10 0.9340 This paper
1	C-MPNN (sum, Msg_r^3, f(t)=t, Init^2, no readout) GNN baseline	—	0.9340	Hits@10 0.9340 This paper
1	C-MPNN GNN ★ proposed	—	0.9320	Hits@10 0.9320 This paper
1	C-MPNN (sum, Msg_r^1, f(t)=t, Init^2, no readout) GNN baseline	—	0.9320	Hits@10 0.9320 This paper
1	C-MPNN (PNA, Msg_r^1, f(t)=t, Init^2, relation-specific readout) GNN baseline	—	0.9320	Hits@10 0.9320 This paper
1	FedSage GNN global	0.8426 ± 0.0026	—	Hits@10 — FedBook: A Unified Federated Graph Foundation Codebook with Intra-domain and Inter-domain …
2	FED-PUB GNN global	0.8348 ± 0.0025	—	Hits@10 — FedBook: A Unified Federated Graph Foundation Codebook with Intra-domain and Inter-domain …
3	FedAvg GNN global	0.8252 ± 0.0023	—	Hits@10 — FedBook: A Unified Federated Graph Foundation Codebook with Intra-domain and Inter-domain …
7	GCN GNN global	0.8171 ± 0.0030	—	Hits@10 — FedBook: A Unified Federated Graph Foundation Codebook with Intra-domain and Inter-domain …
11	NeuralLP Trad baseline	0.7440	—	Hits@10 — paper 0.7440 prev best: A Survey of Knowledge Graph Reasoning on Graph Types: Static, Dynamic, and Multi-Modal (2022) paper 0.7440 Δ at pub 0.2850
12	DRUM Trad baseline	0.7440	—	Hits@10 — paper 0.7440 prev best: Knowledge Graph Reasoning with Relational Digraph (WWW 2021) paper 0.7440 Δ at pub 0.0780
35	C-MPNN-basic GNN ★ proposed	0.5340	—	Hits@10 — This paper
60	CompGCN GNN baseline	0.4790 best reported	—	Hits@10 — paper 0.4330 best at pub: Composition-based Multi-Relational Graph Convolutional Networks (ICLR 2019) best today: KnowFormer: Revisiting Transformers for Knowledge Graph Reasoning (ICML 2024) paper 0.4330 Δ at pub 0.0460 Δ today 0.0460
92	RGCN GNN baseline	0.4270 best reported	—	Hits@10 — paper 0.3670 best at pub: Knowledge Graph Contrastive Learning based on Relation-Symmetrical Structure (2022) best today: A Survey of Knowledge Graph Reasoning on Graph Types: Static, Dynamic, and Multi-Modal (2022) paper 0.3670 Δ at pub 0.0600 Δ today 0.0600

FB15k-237

Global leaderboard →

Default metric is MRR. The paper reports 7 values on MRR and 9 values on Hits@10 .

#	Model	MRR ↑ default	Hits@10 ↑	Paper
1	sum, Msg_r^3, f(t)=0 GNN baseline	0.8500	—	Hits@10 — This paper
2	sum, Msg_r^3, f(t)=t GNN baseline	0.8440	—	Hits@10 — This paper
3	C-MPNN relation-specific readout (PNA, Msg_r^1, f(t)=t, Init^2) GNN baseline	—	0.8350	Hits@10 0.8350 This paper
3	C-MPNN (PNA, Msg_r^1, f(t)=t) GNN baseline	—	0.8040	Hits@10 0.8040 This paper
3	C-MPNN no readout (PNA, Msg_r^1, f(t)=t, Init^2) GNN baseline	—	0.8040	Hits@10 0.8040 This paper
3	PNA, Msg_r^1, f(t)=0 GNN baseline	0.8010	—	Hits@10 — This paper
4	C-MPNN global readout (PNA, Msg_r^1, f(t)=t, Init^2) GNN baseline	—	0.7990	Hits@10 0.7990 This paper
4	C-MPNN (PNA, Msg_r^3, f(t)=t) GNN baseline	—	0.7950	Hits@10 0.7950 This paper
5	C-MPNN (basic, sum, Msg_r^1, f(t)=t, Init^2, no readout) GNN ★ proposed	—	0.7940	Hits@10 0.7940 This paper
4	sum, Msg_r^1, f(t)=t GNN baseline	0.7940	—	Hits@10 — This paper
5	C-MPNN (PNA, Msg_r^3, f(t)=0) GNN baseline	—	0.7880	Hits@10 0.7880 This paper
5	sum, Msg_r^1, f(t)=0 GNN baseline	0.7840	—	Hits@10 — This paper
6	sum, Msg_r^2, f(t)=0 GNN baseline	0.7340	—	Hits@10 — This paper
7	sum, Msg_r^2, f(t)=t GNN baseline	0.7280	—	Hits@10 — This paper
8	C-MPNN (PNA, Msg_r^2, f(t)=0) GNN baseline	—	0.7150	Hits@10 0.7150 This paper
8	C-MPNN (PNA, Msg_r^2, f(t)=t) GNN baseline	—	0.7090	Hits@10 0.7090 This paper

SOTA performance (not significantly different from the best) Proposed method (this paper) Baseline / comparison (this paper) Global context (other papers) Best at pub — reported result worse than the best known when published (best reported in green) Best at pub — reported value improved over the best known when published