DuetGraph: Coarse-to-Fine Knowledge Graph Reasoning with Dual-Pathway Global-Local Fusion

Jin Li, Zezhong Ding, Xike Xie

Knowledge Graphs (KGs) are massive networks of real-world facts (e.g., "Taylor Swift" → "Born in" → "Pennsylvania"), but they are almost always incomplete. Knowledge graph reasoning aims to predict these missing links, enabling advanced applications in search, recommendation, and question answering.

To perform this reasoning effectively, a model needs to understand two critical aspects of the graph:

  1. Local Neighborhoods: The immediate neighbors of an entity, typically captured via Message Passing Neural Networks (MPNNs).
  2. Global Structure: How distant parts of the graph relate to one another, usually captured via Transformers or Attention mechanisms.

Current state-of-the-art models typically "stack" these layers sequentially. However, this architectural choice introduces a critical flaw: score over-smoothing. As information propagates through many stacked layers, the representations of different entities become too similar. Consequently, the model assigns nearly identical scores to both the correct answer and thousands of incorrect candidates, making accurate inference nearly impossible.

Score gap comparison showing DuetGraph reducing over-smoothing

The DuetGraph Solution

To address this, researchers introduce DuetGraph, a novel architecture that prevents score over-smoothing by processing local and global information in parallel and employing a two-stage coarse-to-fine optimization. This approach achieves state-of-the-art performance with up to an 8.7% improvement in reasoning quality and a 1.8× boost in training speed.

DuetGraph tackles the over-smoothing challenge through two primary innovations:

1. Dual-Pathway Global-Local Fusion

Instead of stacking MPNN and Attention layers sequentially, DuetGraph processes them in two distinct, parallel pathways. One pathway focuses entirely on local message passing, while the other handles global attention. These parallel streams are then combined using an adaptive fusion mechanism with a learnable parameter. This segregation prevents the "mutual interference" that typically leads to over-smoothing, preserving the unique signal from both local and global contexts.

2. Coarse-to-Fine Reasoning Optimization

The model uses a two-stage approach for inference to narrow the search space and sharpen the score gap:

  • Stage 1 (Coarse): A lightweight "coarse" model quickly partitions the massive entity space into a high-score subset (the most likely candidates) and a low-score subset.
  • Stage 2 (Fine): The sophisticated DuetGraph "fine" model then focuses its reasoning power exclusively on these subsets. Using a predefined threshold, it sharpens the score gap between correct and incorrect candidates to finalize the prediction.
DuetGraph Architecture featuring Dual-Pathway Fusion and Coarse-to-Fine Reasoning

Key Insights and Performance

The authors evaluated DuetGraph across a comprehensive suite of benchmarks, including standard reasoning datasets (FB15k-237, WN18RR, NELL-995, YAGO3-10), large-scale KGs (Wikidata5M), and inductive reasoning tasks.

  • Parallelism Trumps Depth: A key takeaway is that for KGs, making a model "deeper" by stacking different types of layers actually degrades its discriminative power. Parallelizing the pathways is mathematically proven (via the paper's theoretical bounds) to provide a higher upper bound on the "score gap" compared to single-pathway stacked models.
  • Architectural Diversity: The coarse-to-fine strategy works best when the "coarse" model is architecturally different from the "fine" model (e.g., using a triplet-based model to filter for a transformer-based model). This maximizes the diversity of captured patterns.
  • Superior Accuracy and Efficiency: DuetGraph achieved SOTA results across almost all benchmarks, showing up to an 8.7% improvement in Hits@1 (the probability that the top-ranked answer is correct). Furthermore, because the dual-pathway design allows for parallel processing and the coarse-to-fine strategy narrows the search space, DuetGraph achieved a 1.8× acceleration in training efficiency and reduced inference time on massive datasets by over 20%.
  • Robustness: The model proved highly effective in inductive reasoning, suggesting it learns generalizable structural rules rather than just memorizing entity IDs.

Limitations and Future Work

While highly effective, the authors acknowledge that DuetGraph, like many deep learning models, remains somewhat of a "black box." In sensitive domains like biomedical research or clinical diagnosis, understanding why a model predicted a specific link is as important as the prediction itself.

Future work will focus on incorporating explainability modules and interactive visualization tools to help human experts trace the reasoning process, making the model more trustworthy for high-stakes applications.

Summary updated

Abstract

Knowledge graphs (KGs) are vital for enabling knowledge reasoning across various domains. Recent KG reasoning methods that integrate both global and local information have achieved promising results. However, existing methods often suffer from score over-smoothing, which blurs the distinction between correct and incorrect answers and hinders reasoning effectiveness. To address this, we propose DuetGraph, a **coarse-to-fine** KG reasoning mechanism with **dual-pathway** global-local fusion. DuetGraph tackles over-smoothing by segregating—rather than stacking—the processing of local (via message passing) and global (via attention) information into two distinct pathways, preventing mutual interference and preserving representational discrimination. In addition, DuetGraph introduces a **coarse-to-fine** optimization, which partitions entities into high- and low-score subsets. This strategy narrows the candidate space and sharpens the score gap between the two subsets, which alleviates over-smoothing and enhances inference quality. Extensive experiments on various datasets demonstrate that DuetGraph achieves state-of-the-art (SOTA) performance, with up to an **8.7\%** improvement in reasoning quality and a **1.8$\times$** acceleration in training efficiency.
BibTeX
@inproceedings{li2025duetgraph,
  author = {Jin Li and Zezhong Ding and Xike Xie},
  title = {{DuetGraph: Coarse-to-Fine Knowledge Graph Reasoning with Dual-Pathway Global-Local Fusion}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=r029oluPS7},
}
Figure