Is There More Pattern in Knowledge Graph? Exploring Proximity Pattern for Knowledge Graph Embedding

Ren Li, Yanan Cao, Qiannan Zhu, Xiaoxue Li, Fang FangarXiv 2021 · arXiv

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:

  1. 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.
  2. 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.
  3. Decoding: The fused embeddings are passed to a ConvE decoder (a 2D convolutional neural network) to predict the likelihood of missing triples.
The Chained couPle-GNN (CP-GNN) architecture, illustrating the flow from Knowledge Graph to Proximity Graph and the chained GNN encoder.

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.

Comparison of CP-GNN against baseline models on FB15k-237 and WN18RR datasets.

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

Abstract

Modeling of relation pattern is the core focus of previous Knowledge Graph Embedding works, which represents how one entity is related to another semantically by some explicit relation. However, there is a more natural and intuitive relevancy among entities being always ignored, which is that how one entity is close to another semantically, without the consideration of any explicit relation. We name such semantic phenomenon in knowledge graph as proximity pattern. In this work, we explore the problem of how to define and represent proximity pattern, and how it can be utilized to help knowledge graph embedding. Firstly, we define the proximity of any two entities according to their statistically shared queries, then we construct a derived graph structure and represent the proximity pattern from global view. Moreover, with the original knowledge graph, we design a Chained couPle-GNN (CP-GNN) architecture to deeply merge the two patterns (graphs) together, which can encode a more comprehensive knowledge embedding. Being evaluated on FB15k-237 and WN18RR datasets, CP-GNN achieves state-of-the-art results for Knowledge Graph Completion task, and can especially boost the modeling capacity for complex queries that contain multiple answer entities, proving the effectiveness of introduced proximity pattern.
BibTeX
@misc{li2021is,
  author = {Ren Li and Yanan Cao and Qiannan Zhu and Xiaoxue Li and Fang Fang},
  title = {{Is There More Pattern in Knowledge Graph? Exploring Proximity Pattern for Knowledge Graph Embedding}},
  year = {2021},
  eprint = {2110.00720},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2110.00720},
}
Figure