Link Prediction on N-ary Relational Facts: A Graph-based Approach

Quan Wang, Haifeng Wang, Yajuan Lyu, Yong Zhu

TL;DR

The paper introduces GRAN (GRAph-based N-ary relational learning), a highly efficient approach for predicting missing links in knowledge graphs containing complex, multi-entity (n-ary) facts. By representing these facts as small heterogeneous graphs and utilizing a novel edge-biased attention mechanism, GRAN captures both global and local dependencies, outperforming existing state-of-the-art models while delivering up to a 10x training speedup.

What Problem Does This Paper Address?

Traditional knowledge graphs (KGs) store information as binary triples: (subject, relation, object), such as (Marie Curie, received-award, Nobel Prize in Physics). However, real-world facts are often more nuanced and involve multiple entities or attributes simultaneously (e.g., adding the year 1903 and co-recipients Pierre Curie and Henri Becquerel).

Predicting missing links within these complex n-ary relations is a significant challenge. Existing methods often treat all attributes as equally important, which ignores the core structure of the fact, or they model auxiliary attributes completely independently, missing the rich semantic interactions between them.

Methods

The authors propose GRAN, which tackles n-ary relational learning through two key innovations:

  1. Heterogeneous Graph Representation: Instead of treating an n-ary fact as a flat tuple, GRAN reformulates it as a small heterogeneous graph. Both entities/values and relations/attributes become vertices. The architecture connects them using four distinct, undirected edge types: subject-relation, object-relation, relation-attribute, and attribute-value. An n-ary fact represented as a heterogeneous graph with typed vertices and edges.
Figure 1: An n-ary fact as a heterogenous graph, with relations/attributes and entities/values as vertices, and four types of edges designed between the vertices.
  1. Edge-Biased Fully-Connected Attention: Rather than using a computationally heavy graph neural network (GNN) encoder followed by a separate decoder, GRAN uses a unified architecture based on the Transformer decoder. It employs a modified attention mechanism that allows every node to look at every other node (capturing global context), but injects learnable key and value biases ($e_{ij}^K, e_{ij}^V$) based on the explicit edge types connecting them. This effectively bakes the local graph topology directly into the attention calculation. Overview of GRAN's architecture and the edge-biased attention matrix.
Figure 2: Overview of the graph learning process, with edge-biased fully-connected attention illustrated.

For training, GRAN masks a target element (using a [MASK] token) and learns to predict the missing entity or relation directly using cross-entropy loss with label smoothing, completely avoiding the need for expensive negative sampling.

Datasets

The model was evaluated on several standard n-ary link prediction benchmarks:

  • JF17K: A dataset derived from Freebase containing facts with mixed arities ranging from 2 to 6.
  • WikiPeople & WikiPeople-: Datasets derived from Wikidata focusing on human entities, with arities up to 9. WikiPeople- is a filtered version that excludes literal values (like dates or strings), capping its arity at 7.
  • Single-Arity Subsets: Isolated 3-ary and 4-ary subsets (e.g., JF17K-3, WikiPeople-4) used specifically to compare GRAN against traditional tensor factorization methods.

Key Insights and Ideas

  • Lightweight Decoders Can Replace Heavy Encoders: Previous state-of-the-art models (like STARE) relied on complex message-passing graph encoders before passing embeddings to a decoder. GRAN demonstrates that a structurally aware decoder can do all the heavy lifting on its own, drastically reducing computational overhead.
  • The Power of Global + Local Context: By utilizing fully connected attention modified by edge biases, GRAN doesn't force a hard choice between local graph propagation and global sequence modeling—it achieves both simultaneously.
  • Graph Heterogeneity is Crucial: Through ablation studies, the authors showed that a variant ignoring edge types (GRAN-homo) or one ignoring graph structure entirely (GRAN-complete) performed worse. Explicitly distinguishing relationship types (e.g., knowing an entity is a primary subject vs. an auxiliary attribute value) is vital for accurate higher-arity reasoning.

Key Results

  • State-of-the-Art Accuracy: GRAN consistently outperformed all baselines across all datasets. On the JF17K dataset for predicting all entities, GRAN achieved a Mean Reciprocal Rank (MRR) of 0.656, substantially higher than the previous best model, RAM (0.539).
  • Dramatic Speedups: Because GRAN eliminates the heavy graph encoder, it trains significantly faster than its closest competitor, STARE. On JF17K, GRAN achieved superior results in just 3 hours compared to STARE's 10 hours. On the larger WikiPeople- dataset, GRAN finished training in 10 hours, whereas STARE required 4 days—representing a 9-10x speedup.

Limitations and Future Work

The authors identify a few areas for future exploration:

  • Broader Benchmarking: GRAN needs to be validated on newer, alternative datasets such as WD50K and FB-AUTO.
  • Feature Enhancements: The authors suggest investigating the utility of positional embeddings and alternative attention bias formulations within the network.
  • Multimodal Integration: Incorporating external data types, such as textual descriptions of entities and relations, could provide richer context and further improve link prediction performance.

Summary updated

Abstract

Link prediction on knowledge graphs (KGs) is a key research topic. Previous work mainly focused on binary relations, paying less attention to higher-arity relations although they are ubiquitous in real-world KGs. This paper considers link prediction upon n-ary relational facts and proposes a graph-based approach to this task. The key to our approach is to represent the n-ary structure of a fact as a small heterogeneous graph, and model this graph with edge-biased fully-connected attention. The fully-connected attention captures universal inter-vertex interactions, while with edge-aware attentive biases to particularly encode the graph structure and its heterogeneity. In this fashion, our approach fully models global and local dependencies in each n-ary fact, and hence can more effectively capture associations therein. Extensive evaluation verifies the effectiveness and superiority of our approach. It performs substantially and consistently better than current state-of-the-art across a variety of n-ary relational benchmarks. Our code is publicly available.
BibTeX
@inproceedings{wang2021link,
  author = {Quan Wang and Haifeng Wang and Yajuan Lyu and Yong Zhu},
  title = {{Link Prediction on N-ary Relational Facts: A Graph-based Approach}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2021},
  doi = {10.18653/v1/2021.findings-acl.35},
}
Figure