Message Passing for Hyper-Relational Knowledge Graphs

Mikhail Galkin, Priyansh Trivedi, Gaurav Maheshwari, Ricardo Usbeck, Jens Lehmann

Introduction

Knowledge Graphs (KGs) are typically represented as collections of binary triples $(s, r, o)$, where a relation $r$ connects a subject $s$ to an object $o$. While this format is standard, it fails to capture the complexity of real-world information. In platforms like Wikidata, facts are "hyper-relational," meaning they include additional qualifiers that provide context or specify the validity of a statement. For instance, the fact that Albert Einstein was educated at ETH Zurich is incomplete without qualifiers specifying his degree (Bachelor's vs. Doctorate) and major (Mathematics vs. Physics).

Comparison of triple-based facts and hyper-relational facts with qualifiers.

Traditional approaches often "flatten" these $n$-ary relations into triples, which can obscure the semantic distinction between the primary fact and its modifiers. This paper introduces STARE (StarE), a message-passing framework designed to treat qualifiers as first-class citizens, enabling more accurate link prediction by leveraging this rich contextual information.

Methodology: The STARE Framework

STARE is a Graph Neural Network (GNN) encoder that explicitly models hyper-relational data during the message-passing phase. The architecture consists of several key components:

  1. Qualifier Encoding and Aggregation: For each fact, qualifier pairs—consisting of a qualifier relation ($q_r$) and a qualifier value ($q_v$)—are processed through a composition function. These individual representations are then aggregated (e.g., via summation) into a single qualifier vector ($h_q$). This approach allows the model to handle an arbitrary number of qualifiers per fact.
  2. Hyper-Relational Integration: The qualifier vector is merged with the main relation's representation ($h_r$) using an integration function $\gamma$. This combined representation captures the full context of the hyper-relational statement.
  3. Message Passing: The updated hyper-relational representations are used to refine entity embeddings across the graph, propagating contextual information through the network.
The STARE message-passing architecture for hyper-relational facts.

To perform link prediction, STARE employs a Transformer-based decoder. The hyper-relational fact is linearized into a sequence, allowing the Transformer's attention mechanism to weigh the importance of specific qualifiers when predicting missing subjects or objects.

Datasets and Benchmarking

The authors evaluate STARE on standard benchmarks like WikiPeople and JF17K, but also identify significant flaws in these datasets, such as "data leakage" where test facts are present in the training set. To address this, they introduce WD50K, a new dataset extracted from Wikidata. WD50K is specifically curated to eliminate leakage and provide a robust testbed for hyper-relational modeling with varying numbers of qualifiers.

Results and Discussion

STARE achieves state-of-the-art performance across multiple benchmarks, significantly outperforming existing models like HINGE and NaLP. Key findings include:

  • The Qualifier Boost: On the WD50K dataset, incorporating qualifiers led to a 16% to 23% relative improvement in Mean Reciprocal Rank (MRR) compared to triple-only baselines. This demonstrates that qualifiers provide critical signal for resolving ambiguities.
  • Performance Saturation: Interestingly, the benefit of adding qualifiers tends to saturate after approximately two pairs. While initial context is vital, current architectures may face diminishing returns with very long sequences of metadata.
  • Benchmark Integrity: By "cleaning" JF17K, the authors showed that previous high scores were often inflated by memorizing leaked patterns, highlighting the importance of rigorous dataset curation.

Conclusion

STARE demonstrates that treating qualifiers as integral components of the knowledge graph structure, rather than auxiliary metadata, leads to substantial gains in link prediction. By preserving semantic integrity through specialized message passing and transformer-based decoding, STARE sets a new standard for hyper-relational KG modeling. Future work will explore applying these hyper-relational embeddings to complex query answering and node classification tasks.

Summary updated

Abstract

Hyper-relational knowledge graphs (KGs) (e.g., Wikidata) enable associating additional key-value pairs along with the main triple to disambiguate, or restrict the validity of a fact. In this work, we propose a message passing based graph encoder - StarE capable of modeling such hyper-relational KGs. Unlike existing approaches, StarE can encode an arbitrary number of additional information (qualifiers) along with the main triple while keeping the semantic roles of qualifiers and triples intact. We also demonstrate that existing benchmarks for evaluating link prediction (LP) performance on hyper-relational KGs suffer from fundamental flaws and thus develop a new Wikidata-based dataset - WD50K. Our experiments demonstrate that StarE based LP model outperforms existing approaches across multiple benchmarks. We also confirm that leveraging qualifiers is vital for link prediction with gains up to 25 MRR points compared to triple-based representations.
BibTeX
@inproceedings{galkin2020message,
  author = {Mikhail Galkin and Priyansh Trivedi and Gaurav Maheshwari and Ricardo Usbeck and Jens Lehmann},
  title = {{Message Passing for Hyper-Relational Knowledge Graphs}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2020},
  doi = {10.18653/v1/2020.emnlp-main.596},
}
Figure