CascadER: Cross-Modal Cascading for Knowledge Graph Link Prediction

Tara Safavi, Doug Downey, Tom Hope

TL;DR

CascadER is a tiered ranking framework that solves the efficiency-accuracy trade-off in Knowledge Graph (KG) link prediction. By using fast graph embeddings to filter candidates and powerful language models to rerank only the most promising ones, it achieves state-of-the-art accuracy while running orders of magnitude faster than traditional cross-modal ensembles.

What Problem Does This Paper Address?

Knowledge Graph link prediction—predicting missing facts like (aspirin, treats, ?)—is essential for building complete databases in fields like biomedicine and search. Currently, researchers use two main tools:

  1. Knowledge Graph Embeddings (KGEs): These are fast and great at capturing graph structure but ignore the rich text descriptions of entities.
  2. Language Models (LMs): These (like BERT) are excellent at understanding text but are computationally ruinous.

The "combinatorial explosion" is the real killer: to predict a link using a high-performing "cross-encoder" LM, you might have to score a query against every single entity in the graph. On a medium-sized dataset, this can turn a task that takes minutes for a KGE into a task that takes over a month for an LM. Existing ensembles that try to combine both are either too slow to be useful or fail to provide significant accuracy gains.

Methods

The authors introduce CascadER, a progressive reranking architecture that balances the "structural" signal of KGEs with the "textual" signal of LMs.

CascadER sequential reranking architecture.

The core idea is a cascade:

  • Tier 1: A fast KGE scores all possible candidates.
  • Pruning: The system selects a small subset of top-ranked candidates to move to the next tier.
  • Tiers 2 to $n$: Increasingly complex LMs (first "Siamese" dual-encoders, then heavy cross-encoders) rerank only the candidates passed up from the previous tier.

A key innovation is Dynamic Pruning. Instead of just picking the top 100 candidates for every query, CascadER uses a lightweight MLP to look at the KGE's score distribution. If the KGE is "uncertain" about a query, the model adaptively increases the number of candidates passed to the LMs. This ensures compute is spent only where it’s needed most.

Datasets

The authors evaluated CascadER on five diverse benchmarks:

  • FB15K-237 & CoDEx (S and M): General encyclopedic knowledge from Freebase and Wikidata.
  • WN18RR: Lexical relationships from WordNet.
  • RepoDB: A biomedical dataset focused on drug repurposing.
Statistics of the KG link prediction datasets.

Key Insights and Ideas

  • Diversity is Key: The authors found that KGEs and cross-encoder LMs have very low rank correlation. This means they "fail" in different ways, making them perfect partners for an ensemble.
  • Preserving Confidence: Simply summing scores from different models doesn't work well. CascadER uses additive reweighting (a convex combination of scores), which helps preserve the "confidence signals" (the margin between the correct answer and the noise) of the individual models.
  • Efficiency via Uncertainty: The score distribution of a KGE actually encodes how "difficult" a query is. Dynamic pruning leverages this to maintain high "coverage" (keeping the right answer in the top-k) while minimizing the number of times expensive LMs are called.

Key Results

CascadER sets a new state-of-the-art (SOTA) on four out of five benchmarks.

  • Accuracy: It improves Mean Reciprocal Rank (MRR) by up to 9 points over KGE baselines.
  • Speed: On the CoDEx-M dataset, a full cross-encoder ensemble would take over 11 days to run. CascadER achieves better accuracy in just a few hours—a 100x+ speedup.
CascadER maintains accuracy while improving efficiency by 1+ orders of magnitude.

As shown in the table below, CascadER consistently outperforms both standalone models and simpler ensembles across different metrics.

Test performance on CoDEx-M and RepoDB.

Limitations and Future Work

While CascadER is a major step forward, the authors note a few areas for growth:

  • Inductive Settings: The current KGEs are transductive (they can't handle entities not seen during training). While LMs are naturally inductive, the KGE-first cascade might still struggle with entirely new entities.
  • Hybrid Architectures: Future work could explore "late-interaction" models (like ColBERT) that sit between dual-encoders and cross-encoders in terms of the efficiency-accuracy trade-off.
  • Advanced Pruning: There is room to develop even more sophisticated reinforcement learning or meta-learning strategies for the pruning step to further squeeze out efficiency.

Summary updated

Abstract

Knowledge graph (KG) link prediction is a fundamental task in artificial intelligence, with applications in natural language processing, information retrieval, and biomedicine. Recently, promising results have been achieved by leveraging cross-modal information in KGs, using ensembles that combine knowledge graph embeddings (KGEs) and contextual language models (LMs). However, existing ensembles are either (1) not consistently effective in terms of ranking accuracy gains or (2) impractically inefficient on larger datasets due to the combinatorial explosion problem of pairwise ranking with deep language models. In this paper, we propose a novel tiered ranking architecture CascadER to maintain the ranking accuracy of full ensembling while improving efficiency considerably. CascadER uses LMs to rerank the outputs of more efficient base KGEs, relying on an adaptive subset selection scheme aimed at invoking the LMs minimally while maximizing accuracy gain over the KGE. Extensive experiments demonstrate that CascadER improves MRR by up to 9 points over KGE baselines, setting new state-of-the-art performance on four benchmarks while improving efficiency by one or more orders of magnitude over competitive cross-modal baselines. Our empirical analyses reveal that diversity of models across modalities and preservation of individual models' confidence signals help explain the effectiveness of CascadER, and suggest promising directions for cross-modal cascaded architectures. Code and pretrained models are available at https://github.com/tsafavi/cascader.
BibTeX
@inproceedings{safavi2022cascader,
  author = {Tara Safavi and Doug Downey and Tom Hope},
  title = {{CascadER: Cross-Modal Cascading for Knowledge Graph Link Prediction}},
  booktitle = {Akbc},
  year = {2022},
}
Figure