Source-linked AI summary
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 Phung
TL;DR
Knowledge graph completion and search personalization require effective prediction over relationship triples, but prior models lacked a deep architecture for same-dimension triple entries. CapsE uses convolution and capsule-network routing to model triples, achieving state-of-the-art results across the reported benchmarks and search-personalization evaluation. Its scope includes a training assumption that query and document embeddings cannot be learned for generalization to new queries.
Problem
Existing triple-embedding models use simple operators, and prior models lacked a deep architecture for modeling entries at the same dimension.
Method
CapsE represents each triple's entity and relation embeddings as a matrix, applies convolutional filters, forms capsules, and uses routing to produce a plausibility score.
Results
CapsE outperforms state-of-the-art knowledge graph completion models on WN18RR and FB15k-237 and competitive search-personalization baselines on SEARCH17.
Takeaways & Limitations
CapsE provides one capsule-network embedding approach for both knowledge graph completion and search personalization, with reported gains across the evaluated datasets and tasks.
Takeaways & Limitations
Learning query and document embeddings during training would overfit and prevent the models from working for new queries.
Abstract
from arXiv · showhide
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.
1 Introduction
Knowledge graphs support applications such as semantic search and question answering but remain incomplete, motivating completion methods that predict missing triples. CapsE applies capsule-network modeling to triple embeddings and achieves strong results for both knowledge graph completion and search personalization.
- Motivation: Knowledge graphs contain relationship triples but can omit many valid triples, motivating knowledge graph completion.Completion predicts whether a triple absent from a graph is likely to be valid.
- Motivation: Search personalization can formulate query, user profile, and returned document as triples for document re-ranking.This extends triple-based prediction beyond knowledge graph completion.
- Research gap: Conventional embedding models mainly capture linear relationships, while existing models lacked a deep architecture for entries at the same triple dimension.This limitation motivates exploring capsule networks for triple-based prediction.
- Approach: CapsE feeds the three embeddings of a triple through convolutional feature extraction and capsule construction to model same-dimension entries.The model adapts capsule-network routing to relationship triples.
- Contribution: CapsE is proposed as a capsule-network embedding model for knowledge graph completion and search personalization.The paper presents this as the first exploration of capsule networks for these two tasks.
- Results: CapsE obtains the best mean rank on WN18RR, the highest mean reciprocal rank and Hits@10 on FB15k-237, and new state-of-the-art search-personalization results.The evaluations cover WN18RR, FB15k-237, and SEARCH17.
2 The proposed CapsE
CapsE scores relationship triples by transforming their embeddings into feature maps and capsules, then using the final capsule’s vector length as the triple score.
- Triple representation and convolution: CapsE represents each triple as a matrix of three entity and relation embedding columns, then applies shared 1×3 filters across its rows.The filters generate N feature maps, with each map capturing a characteristic among entries at the same embedding dimension.
- Capsule construction: The first capsule layer groups corresponding-dimension entries from all feature maps into k capsules that capture multiple characteristics of each dimension.This differs from traditional CapsNet construction, which splits feature maps to form capsules.
- Capsule routing: Outputs from the first capsule layer are transformed by weight matrices, summed, and passed through a squashing function to produce the second-layer vector e.The transformed vectors provide the input to the single capsule in the second layer.
- Capsule routing: Routing uses coupling coefficients and applies softmax from all capsules in the previous layer to the single capsule in the next layer.This is the stated difference from the original routing direction in Sabour et al. (2017).
- Scoring and training: The length of the output vector e is used as the score for the input triple, with valid triples intended to receive higher scores than invalid triples.The model is trained with Adam by minimizing a loss over valid triples G and corrupted invalid triples G′.
3 Knowledge graph completion evaluation
CapsE is evaluated for knowledge graph completion on WN18RR and FB15k-237 using filtered ranking metrics, dataset-specific settings, and comparisons with prior models. It achieves strongest overall results on several metrics, with especially large gains on FB15k-237 and advantages for many-to-many relation sides.
- Experimental setup: The evaluation uses WN18RR and FB15k-237, benchmark datasets designed to avoid reversible relations and provide more challenging prediction tasks.The datasets contain entities and relations summarized in Table 1.
- Experimental setup: Filtered ranking replaces each test triple’s subject or object with all other entities, measuring MR, MRR, and Hits@10.Lower MR and higher MRR or Hits@10 indicate better performance.
- Main results: CapsE outperforms ConvKB on both datasets except Hits@10 on WN18RR and MR on FB15k-237.The comparison uses the same evaluation protocol as the reported prior results.
- Main results: CapsE obtains the best MR on WN18RR and the highest MRR and Hits@10 on FB15k-237.Its Hits@1 scores are 33.7% on WN18RR and 48.9% on FB15k-237.
- Relation analysis: CapsE performs better than ConvKB on the many side of relation categories, while ConvKB performs better on the one side.On FB15k-237, many-to-many relations account for 72.3% of test triples, compared with 0.9% for one-to-one relations.
- Relation analysis: CapsE also outperforms ConvKB on four symmetric WN18RR relations, supporting its potential for applications containing many many-to-many relations.The paper identifies search personalization as an example of such an application.
- Parameter analysis: With N = 50 and learning rate 1e−5, the best WN18RR validation performance for each tested epoch setup uses one routing iteration.The paper contrasts this result with image classification, where more routing iterations can be useful.
4 Search personalization application
CapsE models search personalization as triple-based ranking, representing each query, user, and document as a relationship triple and re-ranking returned documents. On SEARCH17, it achieves the highest reported ranking performance, with statistically significant improvements over strong baselines.
- Task formulation: Search personalization is formulated as re-ranking documents for a user and query using triples of the form (query, user, document).The triple captures a user's interest in a document given a query.
- Dataset: SEARCH17 contains query logs from 106 users, including queries, returned top-10 documents, clicks, and dwell times.SAT clicks identify relevant documents using click and dwell-time criteria.
- Evaluation: MRR and Hits@1 are used for evaluation, with higher values indicating better ranking performance.Because only top-10 documents are re-ranked, Hits@10 is the same for all models.
- Baselines: CapsE is compared with SE, CI, SP, TransE, and ConvKB under the same experimental setup.The baselines include the original search-engine ranking, personalized navigation, session-based profiles, and embedding models.
- Results: 14.5% and 22% are CapsE's relative improvements over TransE in MRR and Hits@1, respectively.CapsE also outperforms the traditional learning-to-rank models CI and SP.
- Results: CapsE achieves the highest MRR and Hits@1 among the compared systems, with improvements over all five baselines statistically significant at p < 0.05.The paired t-test is used to assess significance.
- Training analysis: CapsE validation performance improves as the number of filters increases under the learning-curve experiment.The authors attribute this to capsules encoding more useful properties for a large embedding size.
5 Related work
Related work spans transition-based and multiplicative knowledge-graph embedding models, convolutional triple models, and classical personalized-search systems. CapsE is positioned closest to ConvKB while extending triple embedding to search personalization.
- Knowledge-graph embeddings: Transition-based models such as TransH, TransR, TransD, and STransE extend TransE with projection vectors or matrices.DISTMULT and ComplEx instead compute triple scores with a tri-linear dot product.
- Neural triple models: ConvKB applies convolutional neural networks to knowledge-graph completion and is the model most closely related to CapsE.CapsE also models relationship triples for knowledge-graph completion and search personalization.
- Search personalization: Personalized search systems use historical queries and clicked documents to tailor results to a user's needs.Common approaches separately build a user profile and learn a ranking function.
6 Conclusion
CapsE uses capsule networks to model relationship triples for knowledge-graph completion and search personalization. It outperforms state-of-the-art knowledge-graph models on WN18RR and FB15k-237 and competitive search-personalization baselines on SEARCH17.
- Conclusion: CapsE is a capsule-network embedding model for relationship triples in knowledge-graph completion and search personalization.The paper also reports that CapsE effectively models many-to-many relationships.
- Conclusion: CapsE outperforms other state-of-the-art models on WN18RR and FB15k-237 and competitive baselines on SEARCH17.SEARCH17 consists of web search query logs.