CascadER: Cross-Modal Cascading for Knowledge Graph Link Prediction

Tara Safavi, Doug Downey, Tom Hope

Knowledge Graphs (KGs) serve as the backbone for numerous AI applications, from search engines to drug discovery. However, these graphs are often incomplete. Link prediction—the task of predicting missing relationships between entities—is therefore a critical area of research. In "CascadER: Cross-Modal Cascading for Knowledge Graph Link Prediction," presented at the 2022 Automated Knowledge Base Construction (AKBC) conference, researchers introduce a framework that bridges the gap between fast structural models and powerful textual models.

The Efficiency-Accuracy Trade-off

Traditionally, link prediction relies on two distinct paradigms:

  1. Knowledge Graph Embeddings (KGEs): Models like RotatE or ComplEx focus on the graph's topology. They are computationally efficient, allowing for the scoring of millions of candidates in seconds, but they ignore the rich semantic information contained in entity descriptions.
  2. Language Models (LMs): Cross-encoders (e.g., BERT) can process textual descriptions to capture deep semantic nuances. While highly accurate, they are computationally expensive; scoring every possible entity pair in a large KG using a cross-encoder is practically impossible for real-time or large-scale applications.

While ensembling these models provides superior accuracy, the "combinatorial explosion" of candidates makes full ensembling impractical. CascadER addresses this by introducing a tiered reranking architecture designed to maximize both accuracy and efficiency.

The CascadER Framework

CascadER operates as a progressive pipeline, filtering candidates through increasingly complex models in a tiered approach:

  • Tier 1 (The Filter): A fast KGE scores the entire entity set to identify a broad pool of potential candidates based on graph structure.
  • Tiers 2+ (The Refiners): Increasingly complex LMs—starting with Dual-encoders and ending with Cross-encoders—rerank only the most promising candidates passed from the previous tier.

Dynamic Pruning

The core innovation of CascadER is its Dynamic Pruning strategy. Instead of passing a fixed number of candidates (e.g., the top 100) to the next tier, CascadER uses a lightweight MLP regressor. This regressor analyzes the distribution of scores from the KGE to predict an optimal $k$—the number of candidates to pass forward—for each specific query. If the KGE is highly confident, $k$ is small; if the scores are ambiguous, $k$ increases to ensure the correct answer is not prematurely pruned.

Additive Reweighting

To combine the insights from different tiers, the authors use Additive Reweighting. This method utilizes a convex combination of scores, preserving the confidence signals of individual models and preventing a single model's noise from overwhelming the final prediction.

Experimental Results

The framework was evaluated on five diverse benchmarks: FB15K-237 (encyclopedic), WN18RR (lexical), CoDEx-S & CoDEx-M (Wikidata), and RepoDB (biomedical).

CascadER achieved state-of-the-art (SOTA) performance on four of the five datasets. Key highlights include:

  • Accuracy Gains: An improvement of up to 9 points in Mean Reciprocal Rank (MRR) over standard KGE baselines.
  • Massive Speedups: On the CoDEx-M dataset, CascadER matched the accuracy of a full cross-encoder ensemble while being orders of magnitude faster. Inference time was reduced from an estimated 11+ days to just a few hours.
  • Robustness: The system maintained high performance even when the computational budget was significantly restricted, validating the effectiveness of the adaptive pruning regressor.

Insights and Future Directions

The success of CascadER stems from the complementary strengths of its components. KGEs and LMs make different types of errors; KGEs might struggle with rare entities where structural data is sparse, while LMs can leverage text to fill those gaps. Qualitative analysis also showed that Cross-encoders are particularly "aggressive" filters, making them ideal for the final stage of a cascade.

While CascadER significantly reduces inference costs, it does require training multiple base models and a pruning regressor. Future work may explore hybrid architectures like ColBERT to further optimize the LM tiers or apply the cascading logic to inductive link prediction, where models must handle entities not seen during training.

Summary updated

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