Learning Adaptive Propagation for Knowledge Graph Reasoning

Yongqi Zhang, Zhanke Zhou, Quanming Yao, Xiaowen Chu, Bo Han

Knowledge Graphs (KGs) serve as the foundation for modern AI applications, ranging from semantic search to drug discovery. However, reasoning over these vast networks—such as deducing that "LeBron James lives in Los Angeles" because he plays for the Lakers—presents a significant computational challenge. As reasoning paths extend, the number of potential connections grows exponentially, leading to what researchers call the "neighbor explosion" problem.

In their KDD '23 paper, AdaProp, Yongqi Zhang and colleagues introduce a novel framework to make Graph Neural Networks (GNNs) more selective. By filtering out noise and focusing on the most promising leads, AdaProp achieves state-of-the-art reasoning performance with high computational efficiency.

The Problem: Neighbor Explosion

Most GNN-based reasoning methods struggle with the sheer scale of KGs. To answer a multi-hop query, a model typically starts at a query entity and propagates information to all its neighbors, and then to their neighbors in subsequent steps.

Knowledge Graph reasoning example: inferring LeBron James's residence based on team affiliation and family ties.

Existing methods generally follow two paradigms:

  1. Full Propagation: These models consider every neighbor at every step. This is computationally expensive and often leads to "over-smoothing," where entity representations become indistinguishable.
  2. Progressive Propagation: These models expand outward hop-by-hop. While more structured, they still involve a massive number of irrelevant entities at larger steps (e.g., processing unrelated facts about a stadium when the query concerns a player's hometown).

The AdaProp Framework

AdaProp addresses these issues by learning an adaptive propagation path. Instead of following all edges, it identifies and samples only the most semantically relevant entities for a specific query.

Comparison of propagation strategies in KG reasoning. AdaProp (Adaptive propagation) selectively activates query-relevant entities.

Key Innovations

  • Incremental Sampling: Unlike standard sampling that might disconnect the reasoning path, AdaProp preserves entities from the previous step and adds a fixed number ($K$) of new neighbors. This ensures a continuous path from the query to the target while keeping the entity count growing linearly rather than exponentially.
  • Semantic-Aware Distribution: The model learns a sampling distribution conditioned on the query relation. For instance, if the query is about "place of birth," the model prioritizes geographic and familial relations over commercial sponsorships.
  • Differentiable Training: To train this discrete sampling end-to-end, the authors utilize the Gumbel top-k trick combined with a Straight-Through (ST) estimator. This allows the model to learn which paths are useful based on their eventual success in reaching the correct answer.

Experimental Results

The researchers evaluated AdaProp on six widely used benchmarks (including WN18RR, FB15k237, and NELL-995) across both transductive and inductive settings.

  • State-of-the-Art Accuracy: AdaProp outperformed strong baselines like NBFNet and RED-GNN, particularly on complex datasets like NELL-995.
  • Inductive Generalization: In settings where the model must reason on entirely unseen entities, AdaProp consistently ranked at the top, proving its learned sampling logic generalizes well.
  • Efficiency and Depth: By filtering noise, AdaProp achieves higher "Target over Entities" (ToE) ratios. It can successfully utilize deeper GNNs (up to 8 layers) without the performance degradation typically seen in deep GCNs.

Conclusion

AdaProp demonstrates that the key to efficient Knowledge Graph reasoning is not processing more data, but processing the right data. By pruning the KG into query-specific subgraphs, it avoids the memory wall of traditional GNNs while maintaining high accuracy. Future work may involve applying this adaptive propagation logic to other graph-heavy tasks like recommendation systems and large-scale node classification.

Summary updated

BibTeX
@inproceedings{zhang2023learning,
  author = {Yongqi Zhang and Zhanke Zhou and Quanming Yao and Xiaowen Chu and Bo Han},
  title = {{Learning Adaptive Propagation for Knowledge Graph Reasoning}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2023},
  doi = {10.1145/3580305.3599404},
}
Figure