A Capsule Network-based Embedding Model for Knowledge Graph Completion and Search Personalization

Dai Quoc Nguyen, Thanh Vu, Tu Dinh Nguyen, Dat Quoc Nguyen, Dinh Q. Phung

Abstract: Dai Quoc Nguyen, Thanh Vu, Tu Dinh Nguyen, Dat Quoc Nguyen, Dinh Phung. Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers).

2019.

Introduction

Knowledge Graphs (KGs), such as Freebase and WordNet, serve as critical backbones for modern AI applications. However, these graphs are often incomplete, necessitating robust embedding models to predict missing links. Traditional embedding methods typically rely on linear operations that may fail to capture the complex, non-linear interactions within high-dimensional data. While Convolutional Neural Networks (CNNs) have been introduced to address this, they often overlook the internal "part-whole" relationships between embedding dimensions.

This paper introduces CapsE, a novel architecture that leverages Capsule Networks to model the interactions within KG triples. CapsE is designed to handle both knowledge graph completion and search personalization—a task that involves tailoring search results to user profiles—within a unified framework.

Methodology

CapsE represents a triple $(subject, relation, object)$ as a $k \times 3$ matrix, where each column corresponds to a $k$-dimensional embedding vector. The model processes this matrix through several distinct stages:

  1. Dimension-Wise Convolution: The model applies multiple $1 \times 3$ filters. This specific shape is critical; it forces the network to analyze how the $i$-th dimension of an entity interacts specifically with the $i$-th dimension of the relation and the object.
  2. Capsule Construction: The resulting feature maps are reorganized into a layer of capsules. Each capsule represents a group of neurons capturing specific "instantiation parameters" of the relationship at a given dimension.
  3. Dynamic Routing: Information is passed from the first capsule layer to a final capsule in the second layer using a simplified dynamic routing algorithm. Interestingly, the authors found that a single routing iteration ($m=1$) yielded the best results for symbolic data.
  4. Scoring: The plausibility of a triple is determined by the L2 norm (length) of the final capsule's vector, where a longer vector signifies a higher likelihood of a valid fact.
The CapsE architecture, illustrating the transition from a triple matrix to capsules via dimension-wise convolutions.

Experimental Evaluation

The model was evaluated on two primary tasks using standard benchmarks:

  • Knowledge Graph Completion: Tested on WN18RR and FB15k-237, datasets designed to be challenging by excluding simple inverse relation leaks.
  • Search Personalization: Evaluated using SEARCH17, a dataset of web search query logs where triples are defined as (query, user profile, document).

Results and Discussion

CapsE demonstrated state-of-the-art performance across all benchmarks, significantly outperforming previous models like ConvKB and TransE.

  • FB15k-237: CapsE achieved a Mean Reciprocal Rank (MRR) of 0.523, representing a ~25% relative improvement over ConvKB (0.418).
  • WN18RR: The model obtained a leading MRR of 0.415, proving its effectiveness in sparse, hierarchical environments.
  • Search Personalization: On SEARCH17, CapsE achieved an MRR of 0.766 and a Hits@1 of 62.1%, demonstrating its versatility beyond static KGs.

Performance on Complex Relations

A key strength of CapsE is its ability to handle Many-to-Many (M-M) relations. Unlike standard CNNs that pool features, capsules can encode the specific "state" of a feature, which is vital when a single entity relates to many others in varying ways. Qualitative analysis confirms that CapsE is particularly dominant in these complex scenarios.

Performance comparison between CapsE and ConvKB across different relation categories (1-1, 1-M, M-1, M-M) for head and tail prediction.

Conclusion

CapsE successfully adapts the principles of Capsule Networks to symbolic knowledge representation. By focusing on dimension-wise interactions and utilizing dynamic routing, it captures nuanced patterns that linear and standard convolutional models miss. While the optimal routing iteration count remains low for symbolic data compared to image data, the model's performance on M-M relations and search personalization highlights its potential for large-scale, complex knowledge representation tasks. Future work will explore deeper capsule architectures and the application of CapsE to billion-scale knowledge bases.

Summary updated

BibTeX
@inproceedings{nguyen2019capsule,
  author = {Dai Quoc Nguyen and Thanh Vu and Tu Dinh Nguyen and Dat Quoc Nguyen and Dinh Q. Phung},
  title = {{A Capsule Network-based Embedding Model for Knowledge Graph Completion and Search Personalization}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2019},
  url = {https://openreview.net/forum?id=rJELPX-_-r},
}
Figure