Learning Complete Topology-Aware Correlations Between Relations for Inductive Link Prediction

Jie Wang, Hanzhu Chen, Qitan Lv, Zhihao Shi, Jiajun Chen, Huarui He, Hongtao Xie, Yongdong Zhang, Feng Wu

Abstract

Inductive link prediction -- where entities during training and inference stages can be different -- has shown great potential for completing evolving knowledge graphs in an entity-independent manner. Many popular methods mainly focus on modeling graph-level features, while the edge-level interactions -- especially the semantic correlations between relations -- have been less explored. However, we notice a desirable property of semantic correlations between relations is that they are inherently edge-level and entity-independent. This implies the great potential of the semantic correlations for the entity-independent inductive link prediction task. Inspired by this observation, we propose a novel subgraph-based method, namely TACO, to model Topology-Aware COrrelations between relations that are highly correlated to their topological structures within subgraphs. Specifically, we prove that semantic correlations between any two relations can be categorized into seven topological patterns, and then proposes Relational Correlation Network (RCN) to learn the importance of each pattern. To further exploit the potential of RCN, we propose Complete Common Neighbor induced subgraph that can effectively preserve complete topological patterns within the subgraph. Extensive experiments demonstrate that TACO effectively unifies the graph-level information and edge-level interactions to jointly perform reasoning, leading to a superior performance over existing state-of-the-art methods for the inductive link prediction task.

Introduction

Knowledge Graphs (KGs) like Freebase or WordNet are massive networks of facts, but they are almost always incomplete. Inductive link prediction is the challenge of predicting missing facts involving entities that weren't even seen during training (e.g., a new user in a recommendation system or a newly discovered molecule).

While previous methods focused on the "shape" of the graph (graph-level features), they often ignored edge-level semantic correlations. For example, "nationality" and "languages spoken" are highly correlated regardless of which specific person you are talking about. This entity-independence makes semantic correlations a "gold mine" for inductive reasoning. However, existing methods either ignored these correlations or used "enclosing subgraphs" that accidentally deleted critical reasoning paths or added too much noise.

Methodology: The TACO Framework

The authors propose TACO (Topology-Aware COrrelations), which consists of two main innovations: the Relational Correlation Network and a new subgraph extraction method.

Relational Correlation Network (RCN)

The authors mathematically prove that any two relations can interact in exactly seven topological patterns (e.g., head-to-head, tail-to-tail, or parallel). They build a Relational Correlation Graph (RCG) where nodes are relations and edges represent these patterns. The RCN then learns "importance weights" for these interactions using an attention mechanism. This module captures the semantic conversation between different types of relationships.

The overall architecture of TACO, featuring the Relational Correlation Module (RCN) and the Sub-graph Reasoning Module (R-GCN).

Complete Common Neighbor (CCN) Subgraphs

Previous models like GraIL used simple $n$-hop enclosing subgraphs. However, standard extraction is often "broken": statistical analysis shows that in the WN18RR dataset, over 45% of standard 2-hop subgraphs fail to capture any reasoning path at all. A 2-hop subgraph often misses the "middle man" in a reasoning chain, while a 3-hop subgraph introduces too many irrelevant nodes.

TACO introduces CCN and CCN+, which use "equivalent relations" and a distilled traversal algorithm to preserve complete reasoning paths without the noise. These modules ensure that "isolated" but relevant nodes are preserved, allowing the model to reason effectively.

Comparison of subgraph extraction methods: standard 2-hop and 3-hop neighboring subgraphs vs. TACO's approach to preserving reasoning paths.

Key Results

TACO significantly outperforms previous state-of-the-art models like GraIL, CoMPILE, and NBFNet across several benchmarks including WN18RR, FB15k-237, and NELL-995.

  • Ranking (Hits@10): This is where TACO shines most. On WN18RR v3, it improved the Hits@10 score from GraIL's 58.43 to 82.02—a massive jump in accuracy.
  • Classification (AUC-PR): TACO achieved near-perfect scores (99%+) on many WN18RR and NELL-995 tasks, outperforming GraIL by up to 10% in some versions.
  • Efficiency: While more complex than basic models, TACO is significantly faster than path-based methods like NBFNet because it only needs to reason over small local subgraphs rather than the entire graph.

Conclusion

TACO demonstrates that semantic correlations are inherently inductive and can be structured into a discrete framework of seven topological patterns. By fixing flaws in subgraph extraction with the CCN method, TACO unifies graph-level information and edge-level interactions. Future work may extend this to higher-order correlations or dynamic graphs that change over time.

Summary updated

Abstract

Inductive link prediction -- where entities during training and inference stages can be different -- has shown great potential for completing evolving knowledge graphs in an entity-independent manner. Many popular methods mainly focus on modeling graph-level features, while the edge-level interactions -- especially the semantic correlations between relations -- have been less explored. However, we notice a desirable property of semantic correlations between relations is that they are inherently edge-level and entity-independent. This implies the great potential of the semantic correlations for the entity-independent inductive link prediction task. Inspired by this observation, we propose a novel subgraph-based method, namely TACO, to model Topology-Aware COrrelations between relations that are highly correlated to their topological structures within subgraphs. Specifically, we prove that semantic correlations between any two relations can be categorized into seven topological patterns, and then proposes Relational Correlation Network (RCN) to learn the importance of each pattern. To further exploit the potential of RCN, we propose Complete Common Neighbor induced subgraph that can effectively preserve complete topological patterns within the subgraph. Extensive experiments demonstrate that TACO effectively unifies the graph-level information and edge-level interactions to jointly perform reasoning, leading to a superior performance over existing state-of-the-art methods for the inductive link prediction task.
BibTeX
@misc{wang2023learning,
  author = {Jie Wang and Hanzhu Chen and Qitan Lv and Zhihao Shi and Jiajun Chen and Huarui He and Hongtao Xie and Yongdong Zhang and Feng Wu},
  title = {{Learning Complete Topology-Aware Correlations Between Relations for Inductive Link Prediction}},
  year = {2023},
  eprint = {2309.11528},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2309.11528},
}

Loading related content...

Figure