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:
- 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.
- 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.
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