Abstract
Traditional Knowledge Graph Embedding (KGE) models focus almost exclusively on explicit relational links between entities. This paper introduces the proximity pattern—a latent semantic closeness derived from entities that frequently appear as "co-answers" to the same queries. By integrating this pattern via a novel Chained couPle-GNN (CP-GNN) architecture, the authors achieve state-of-the-art results in Knowledge Graph Completion, particularly for complex, many-to-many queries.
Introduction
Knowledge Graphs (KGs) store facts as triples like $(head, relation, tail)$. Most KGE research focuses on modeling the relation pattern: how one entity relates to another through an explicit link (e.g., Robert Downey Jr. $\xrightarrow{act}$ The Avengers).
However, a more intuitive "proximity pattern" is often ignored. For instance, The Avengers and Avengers: Age of Ultron are semantically close because they share the same director, studio, and genre. Even if a direct "is_sequel_to" link is missing, their frequent appearance as answers to the same queries (e.g., "Which movies did Joss Whedon direct?") signals a deep semantic bond. Existing models struggle to capture this latent closeness, especially when the graph is sparse.
Methodology
The authors propose a two-step approach to capture and fuse these patterns using a Chained couPle-GNN (CP-GNN) architecture:
- Proximity Extraction: A Proximity Measure (PM) is defined based on statistical "co-answers." If two entities frequently satisfy the same query $(h, r, ?)$, they are assigned a high proximity score, forming a derived Proximity Graph.
- Chained Encoder: To merge the original KG with this proximity data, the model uses a dual-GNN structure. First, a Relation-aware GNN ($G_r$) processes the original KG. Its output is then fed into a Homogeneous GNN ($G_p$) that operates on the Proximity Graph. This "chains" the two patterns, allowing the model to refine entity embeddings based on their semantic neighbors.
- Decoding: The fused embeddings are passed to a ConvE decoder (a 2D convolutional neural network) to predict the likelihood of missing triples.
Experimental Setup
The model was evaluated on two standard benchmarks:
- FB15k-237: A subset of Freebase containing 14,541 entities and 237 relations, characterized by complex, many-to-many relations.
- WN18RR: A subset of WordNet with 40,943 entities and 11 relations, primarily containing hierarchical, one-to-one relations.
Key Results and Discussion
CP-GNN achieved state-of-the-art performance across both datasets, significantly outperforming strong baselines like RotatE, ConvE, and CompGCN. On FB15k-237, it achieved a Mean Reciprocal Rank (MRR) of 0.365, a notable improvement over previous GNN-based models.
Solving Complex Queries
The model showed its greatest strength in "N-type" queries (queries with multiple answers). In scenarios where a query had more than 10 answers, CP-GNN significantly outperformed versions of the model that only used the standard knowledge graph. This supports the "Co-answer Hypothesis": entities sharing a query context are semantically related, providing a statistical bridge to fill gaps where explicit relations are missing.
Ablation Study
Removing the proximity GNN ($G_p$) led to a consistent drop in performance across all metrics. This confirms that the proximity pattern provides unique, beneficial evidence that relational patterns alone cannot capture.
Conclusion
By formalizing and integrating proximity patterns, CP-GNN addresses the limitations of relation-only KGE models. While the approach introduces some computational overhead and requires hyper-parameter tuning for proximity thresholds, the gains in handling complex, many-to-many relations are substantial. Future work may explore dynamic proximity extraction to further enhance the model's flexibility during training.
Summary updated