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.
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.
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