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

TL;DR

This paper introduces CapsE, a novel embedding model for knowledge graphs that leverages capsule networks to better model the complex relationships within triples. By treating triples as matrices and using capsule networks, CapsE achieves state-of-the-art results in both knowledge graph completion and search personalization tasks.

What Problem Does This Paper Address?

Knowledge graphs (KGs) are powerful resources for various NLP tasks, but they are often incomplete, meaning many valid relationships are missing. The task of knowledge graph completion aims to predict these missing relationships. Additionally, in applications like semantic search, personalizing results based on user interests is crucial. Traditional embedding models for KGs often struggle to capture the nuanced relationships within triples (subject, relation, object), especially complex many-to-many relationships. This paper addresses this by proposing a new embedding approach that can better model these intricate connections for both KG completion and search personalization.

Methods

The core innovation of this paper is the introduction of CapsE, an embedding model that utilizes capsule networks. Here's a breakdown of the approach:

  • Triple Representation: Each knowledge graph triple (s, r, o) is represented as a 3-column matrix, where each column is the embedding vector of the subject, relation, and object, respectively.
  • Convolutional Layer: This matrix is then fed into a convolutional layer. Multiple filters are applied to generate feature maps, capturing different aspects of the triple's structure.
  • Capsule Networks: These feature maps are then processed by capsule networks. The key idea is that capsules can encode more complex information and relationships than traditional neurons.
  • First Capsule Layer: Entries from the same dimension across all feature maps are grouped into a capsule. This allows each capsule to represent various characteristics of the corresponding dimension within the triple's embeddings.
  • Second Capsule Layer: These capsules are then routed to a final capsule, which outputs a single vector.
  • Plausibility Score: The length of this output vector is used as a "plausibility score" for the triple. A higher score indicates a more likely valid triple.
  • Routing Algorithm: The paper adapts the dynamic routing algorithm from capsule networks to effectively pass information between capsule layers.

Datasets

The paper evaluates CapsE on two benchmark datasets for knowledge graph completion and one for search personalization:

  • WN18RR: A subset of WordNet, known for avoiding reversible relation problems.
  • FB15k-237: A subset of Freebase, also designed to mitigate issues with reversible relations.
  • SEARCH17: A dataset of web search query logs, used for evaluating search personalization.

Key Insights and Ideas

  • Capsules for Triples: The paper's central hypothesis is that applying capsule networks, originally successful in image recognition, to knowledge graph triples can capture richer relational information than standard embedding models.
  • Modeling Many-to-Many Relationships: The authors suggest that CapsE is particularly well-suited for modeling many-to-many relationships, which are common in KGs and crucial for tasks like search personalization.
  • Matrix Representation of Triples: Representing triples as matrices and applying convolutional filters is a novel way to process the structured information within a triple.
  • Routing Iterations: Interestingly, the study found that for KG tasks, fewer routing iterations (specifically, 1) in the capsule network yielded better performance, contrasting with findings in image-based tasks. This suggests that the nature of KG relationships might not require the same level of hierarchical spatial reasoning as images.

Key Results

  • Knowledge Graph Completion: CapsE achieved state-of-the-art results on both WN18RR and FB15k-237 datasets, outperforming existing models like ConvKB, DISTMULT, and ComplEx.
  • On FB15k-237, CapsE showed significant improvements in Mean Reciprocal Rank (MRR) and Hits@10.
  • On WN18RR, CapsE achieved the best Mean Rank (MR).
  • Search Personalization: CapsE also outperformed strong baselines on the SEARCH17 dataset, demonstrating its effectiveness in re-ranking search results based on user context. It showed relative improvements of 14.5% in MRR and 22% in Hits@1 over the TransE baseline.

Limitations and Future Work

  • Computational Cost: While not explicitly detailed as a limitation, the use of capsule networks and dynamic routing can be computationally intensive.
  • Hyperparameter Sensitivity: The performance of CapsE, like many deep learning models, is dependent on careful hyperparameter tuning, as evidenced by the extensive search described in the paper.
  • Future Work: The authors suggest that their CapsE model is a promising direction for effectively modeling many-to-many relationships, which could be further explored in various applications. They also make their code publicly available, facilitating further research.

Summary updated

Abstract

In this paper, we introduce an embedding model, named CapsE, exploring a capsule network to model relationship triples (subject, relation, object). Our CapsE represents each triple as a 3-column matrix where each column vector represents the embedding of an element in the triple. This 3-column matrix is then fed to a convolution layer where multiple filters are operated to generate different feature maps. These feature maps are reconstructed into corresponding capsules which are then routed to another capsule to produce a continuous vector. The length of this vector is used to measure the plausibility score of the triple. Our proposed CapsE obtains better performance than previous state-of-the-art embedding models for knowledge graph completion on two benchmark datasets WN18RR and FB15k-237, and outperforms strong search personalization baselines on SEARCH17.
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