TL;DR
This paper introduces a novel approach to knowledge base completion (KBC) that addresses the challenge of "out-of-knowledge-base" (OOKB) entities – entities not seen during training. By leveraging Graph Neural Networks (GNNs), the authors enable KBC models to infer missing information for these new entities without costly retraining, achieving state-of-the-art results on the WordNet dataset in both standard and OOKB settings.
What Problem Does This Paper Address?
Knowledge bases (KBs) are vast repositories of information structured as relation triplets (e.g., "Paris" - "is capital of" - "France"). A crucial task in KBC is to predict missing triplets to make these KBs more complete. Traditional KBC methods, particularly those based on entity and relation embeddings, assume that all entities encountered during testing were also present during training. This assumption breaks down when new entities emerge after the model has been trained. This "out-of-knowledge-base" (OOKB) entity problem means that models cannot generate embeddings for these new entities, hindering their ability to predict relationships involving them. While retraining is a solution, it's computationally expensive. This paper tackles the OOKB entity problem by developing a method that can infer relationships for unseen entities using existing knowledge and limited auxiliary information, avoiding retraining.
Methods
The core of the proposed solution lies in the application of Graph Neural Networks (GNNs). The authors adapt GNNs to the structure of knowledge graphs, where entities are nodes and triplets are edges. Their approach involves two main components:
- Propagation Model: This part of the GNN determines how information flows between nodes (entities) in the graph. Instead of simple summation of neighbor vectors (as in some prior GNN work), they introduce a pooling function to aggregate information from neighboring entities. This allows the model to compute an embedding for an OOKB entity by aggregating information from its known neighbors within the existing knowledge graph. They explore various transition functions (e.g., using tanh or ReLU activations with batch normalization) and pooling functions (sum, average, max).
- Output Model: This component defines the task-specific objective function. The authors adopt the TransE embedding model as their output model due to its simplicity and effectiveness. They propose an "absolute-margin objective function" which optimizes positive triplet scores towards zero and negative triplet scores to be at least a margin value, showing it converges faster and yields good results.
The GNN's propagation model is designed to compute embeddings for OOKB entities by leveraging their connections to entities already present in the training data, effectively transferring knowledge.
Datasets
The paper uses standard KBC datasets for evaluation:
- WordNet11: A subset of the WordNet knowledge graph.
- Freebase13: A subset of the Freebase knowledge graph.
For the OOKB entity problem, they construct nine new datasets by sampling triplets from the WordNet11 test set. These datasets vary in the number of sampled triplets (1,000, 3,000, 5,000) and the position of the OOKB entities (Head, Tail, or Both head and tail entities).
Key Insights and Ideas
- Knowledge Transfer via Graph Structure: The fundamental idea is that even if an entity is new, its relationships with existing entities within the knowledge graph provide valuable clues for inferring its properties. GNNs are well-suited to exploit this relational structure.
- Avoiding Costly Retraining: The primary motivation is to solve the OOKB problem without the computational burden of retraining the entire model, making KBC systems more adaptable to dynamic knowledge bases.
- Absolute-Margin Objective: The proposed absolute-margin objective function offers a more direct optimization strategy compared to pairwise-margin objectives, leading to faster convergence and competitive performance.
- Pooling Functions Matter: The choice of pooling function (sum, average, max) in the GNN's propagation model significantly impacts performance, with average pooling showing particular strength in the OOKB setting.
Key Results
- Standard KBC: The proposed model achieved state-of-the-art accuracy on the WordNet11 dataset in the standard KBC setting. On Freebase13, it performed competitively, slightly outperforming the baseline TransE model.
- OOKB Entity Problem: In the OOKB setting, the proposed GNN approach consistently outperformed baseline methods across all nine generated datasets. The Graph-NN with average pooling demonstrated the best performance.
- Stacking vs. Unrolling: Experiments on stacking and unrolling GNNs for standard KBC showed that these techniques did not improve performance, suggesting that the embedding models are already effective at capturing distant relationships.
Limitations and Future Work
- Computational Resources: The authors mention that due to limited computational resources, they sampled neighbor entities randomly when an entity had more than 64 neighbors. This sampling might affect performance.
- Stacking/Unrolling Not Beneficial: The study found that stacking and unrolling GNNs did not improve performance in the standard KBC setting. The authors hypothesize this is due to the inherent power of embedding models to capture distant information. Future work could explore if these techniques offer benefits in the OOKB setting or with different graph structures.
- Hyperparameter Sensitivity: While they found good hyperparameter settings through preliminary experiments, the sensitivity of the model to these choices (e.g., margin value, embedding dimension) could be further investigated.
Summary updated