Structure Is All You Need: Structural Representation Learning on Hyper-Relational Knowledge Graphs

Overview

Hyper-relational knowledge graphs (HKGs) capture complex, real-world facts by enriching standard triplets with auxiliary qualifiers. While powerful, most representation learning methods fail to fully exploit the underlying structure of these graphs. This paper introduces MAYPL, a purely structure-driven message-passing framework that learns to compute representations based solely on how entities and relations are connected. By doing so, MAYPL achieves state-of-the-art performance and uniquely enables inductive reasoning on entirely new, unseen entities and relations.

The Challenge of Hyper-Relational Reasoning

Standard Knowledge Graphs (KGs) represent information as simple triplets (e.g., [Finding Nemo, set in, Sydney]). HKGs enrich this by adding "qualifiers" to provide necessary context, such as adding [country, Australia] to the previous triplet.

Reasoning over these complex graphs requires understanding intricate relationships. However, existing models struggle in two main ways:

1. Ignoring Structure: Many models process each hyper-relational fact in isolation or convert the HKG into simpler, lossy formats (like n-ary relational representations or hypergraphs). This conversion destroys valuable topological information, such as shared qualifiers across different facts.
2. The Inductive Bottleneck: Most models learn fixed, specific embeddings for every entity and relation in the training set. If a completely new entity or relation appears at inference time (an "inductive" setting), these models break down because they lack pre-learned vectors to rely on.

Expand

Source, p. 2

MAYPL: A Structure-Driven Approach

To overcome these limitations, the authors propose MAYPL (Message pAssing framework for hYper-relational knowledge graph rePresentation Learning). MAYPL is entirely structure-based, abandoning fixed node identities in favor of learning the rules of connection.

The framework consists of two main components:

1. Structure-Driven Initializer

Instead of assigning a unique random vector to every entity and relation, MAYPL starts every node with the same shared learnable vector. It then initializes representations by passing messages among co-occurring entities and relations. This creates a unique "structural signature" for each node based purely on its local neighborhood and its specific role (e.g., head, tail, or qualifier).

2. Attentive Neural Message Passing

MAYPL computes "fact-level" messages by combining the representations of the entities and relations involved in a specific fact. It then uses an attention mechanism to update entity and relation representations by aggregating these fact-level messages, strictly respecting the positional roles of each component.

Expand

Source, p. 4

Because MAYPL learns how to route and aggregate messages rather than memorizing specific node identities, the trained weights can be seamlessly applied to a completely new graph.

Key Insights and Results

The authors evaluated MAYPL across a massive suite of benchmarks, including transductive HKGs (WD50K, WikiPeople), inductive KGs, and inductive HKGs (WD20K, WP-IND). It was compared against 40 baseline methods across 10 main datasets.

• Structure is All You Need: The graph's topology, combined with the positional roles of its components, contains enough signal to achieve state-of-the-art link prediction without needing fixed entity/relation embeddings or external text features.
• True Inductive Capability: By learning the rules of aggregation rather than node identities, MAYPL is the first HKG method capable of handling completely unseen entities and unseen relations at test time. In inductive settings, MAYPL crushes baselines: on the WD20K(100)v1 dataset, it achieved an MRR of 0.486, compared to the next best baseline (StarE) at just 0.113.
• Transductive Dominance: MAYPL also outperforms state-of-the-art models on standard transductive benchmarks. On the WikiPeople- dataset, it achieved an MRR of 0.519 (compared to the next best at 0.509).
• Qualitative Success: The structure-driven initializer alone naturally groups semantically similar entities. For instance, before any attention is applied, it groups "Vancouver" with "Venice" and "Budapest" based purely on their graph connectivity.

Limitations and Future Work

While powerful, MAYPL's complex message computation and attention-based aggregation are computationally heavy, requiring significant GPU memory and runtime (e.g., 21 hours and ~43GB of VRAM for the WD50K dataset).

To address this computational bottleneck, future work will focus on optimizing the implementation by swapping the current Bahdanau-style attention for more cost-effective Luong-style attention. The authors also suggest applying MAYPL to Question Answering (QA) tasks to serve as a grounding knowledge source for Large Language Models (LLMs) and extending the framework to build broad foundation models for KG reasoning.

@inproceedings{lee2025structure,
  author = {Jaejun Lee and Joyce Jiyoung Whang},
  title = {{Structure Is All You Need: Structural Representation Learning on Hyper-Relational Knowledge Graphs}},
  booktitle = {International Conference on Machine Learning},
  year = {2025},
  url = {https://openreview.net/forum?id=2tH2vexW1Z},
}