DELE: Deductive $\mathcal{EL}^{++}$ Embeddings for Knowledge Base Completion

Basic Information

• Paper ID: 2411.01574
• Title: DELE: Deductive $\mathcal{EL}^{++}$ Embeddings for Knowledge Base Completion
• Authors: Olga Mashkova, Fernando Zhapa-Camacho, Robert Hoehndorf
• Institution: King Abdullah University of Science and Technology (KAUST)
• Classification: cs.AI
• Conference: NeSy 2024 Special Issue
• Paper Link: https://arxiv.org/abs/2411.01574

Abstract

This paper addresses the limitations of ontology embedding methods for description logic $\mathcal{EL}^{++}$ in knowledge base completion tasks by proposing DELE (Deductive $\mathcal{EL}^{++}$ Embeddings). While existing geometric embedding methods can explicitly generate ontology models, they suffer from two critical issues: (1) inability to distinguish between unprovable and falsifiable statements, potentially treating entailed statements as negative samples; (2) insufficient utilization of the ontology's deductive closure to identify inferred but unasserted statements. This paper improves knowledge base completion performance by designing novel negative loss functions and evaluation methods that effectively leverage the deductive closure.

Research Background and Motivation

Problem Definition

Ontology embedding aims to map classes, roles, and individuals in an ontology to $\mathbb{R}^n$ space to compute entity similarity or infer new axioms. For $\mathcal{EL}^{++}$ description logic, several optimization-based geometric embedding methods exist, such as ELEmbeddings, ELBE, and Box2EL.

Limitations of Existing Methods

1. Negative Sample Selection Problem: When existing methods randomly select negative samples, they may mistakenly treat true statements entailed by the ontology as negative examples, affecting model training quality.
2. Insufficient Utilization of Deductive Closure: Inadequate consideration of the ontology's deductive closure—the set of all derivable statements—prevents effective distinction between inferred and unasserted knowledge.
3. Limited Evaluation Methods: Current evaluation methods primarily derive from knowledge graph completion tasks and do not account for the rich entailment relationships in ontologies.

Research Motivation

Knowledge base completion is an important task requiring prediction of axioms that should be added to the knowledge base but are not yet represented. For formalized knowledge bases, this includes both deductive reasoning (predicting entailed axioms) and inductive reasoning (predicting novel non-entailed axioms). This paper aims to improve geometric embedding methods by better leveraging the deductive closure.

Core Contributions

1. Proposed negative loss functions considering deductive closure: Designed new negative loss functions for all $\mathcal{EL}^{++}$ standard forms to avoid treating entailed statements as negative samples.
2. Developed fast approximate deductive closure computation algorithm: Proposed a sound algorithm for computing the deductive closure of $\mathcal{EL}^{++}$ theories to improve negative sample selection during training.
3. Formulated evaluation methods considering deductive closure: Designed new evaluation metrics for knowledge base completion tasks that can distinguish prediction performance between entailed and non-entailed axioms.
4. Extended multiple geometric embedding methods: Applied improvements to three representative methods—ELEmbeddings, ELBE, and Box2EL—demonstrating generalizability.

Methodology Details

Task Definition

Knowledge base completion is defined as: given an $\mathcal{EL}^{++}$ ontology $T$, predict new axioms that should be added to $T$. The task can be further subdivided into:

• Deductive Completion: Predicting axioms in the deductive closure $T^⊢$ but not explicitly asserted in $T$
• Inductive Completion: Predicting novel axioms not in the deductive closure

Deductive Closure Computation

Normalized Forms

$\mathcal{EL}^{++}$ axioms can be normalized into seven forms (see Table 1):

• GCI0: $A \sqsubseteq B$
• GCI1: $A \sqcap B \sqsubseteq E$
• GCI2: $A \sqsubseteq \exists r.B$
• GCI3: $\exists r.A \sqsubseteq B$
• GCI0-BOT: $A \sqsubseteq \perp$
• GCI1-BOT: $A \sqcap B \sqsubseteq \perp$
• GCI3-BOT: $\exists r.A \sqsubseteq \perp$

Deductive Closure Algorithm

The paper proposes two algorithms to compute approximations of the deductive closure:

Algorithm 1: Based on explicitly represented axioms in the ontology, uses inference rules to derive entailed axioms. For example:

A ⊓ B ⊑ E, A' ⊑ A, B' ⊑ B, E ⊑ E'
─────────────────────────────────────
         A' ⊓ B' ⊑ E'

Algorithm 2: Based on arbitrary concept and role names, adds logically necessary axioms, such as $A \sqcap \perp \sqsubseteq E$.

Negative Loss Function Design

ELEmbeddings Negative Loss

For spherical embeddings, six new negative loss functions were designed:

1. GCI0 Negative Loss (based on GCI1-BOT): $\text{loss}_{A \not\sqsubseteq B}(a,b) = \max(0, r_\eta(a) + r_\eta(b) - \|f_\eta(a) - f_\eta(b)\| + \gamma)$
2. GCI1 Negative Loss: $\text{loss}_{A \sqcap B \not\sqsubseteq E}(a,b,e) = \max(0, -r_\eta(a) - r_\eta(b) + \|f_\eta(a) - f_\eta(b)\| - \gamma) + \text{other terms}$

Corresponding negative loss functions were similarly designed for ELBE (box embeddings) and Box2EL.

Negative Sample Filtering

During training, randomly generated negative samples are filtered:

1. Compute the deductive closure of the training ontology
2. Check whether candidate negative samples are in the deductive closure
3. If in the closure, remove from negative samples

Experimental Setup

Datasets

1. Gene Ontology & STRING Data:
   • Protein-protein interaction prediction (PPI)
   • Protein function prediction
   • Based on yeast protein data
2. Food Ontology: Used for subclass relationship prediction
3. GALEN Ontology: Medical concept ontology for subclass relationship prediction

Evaluation Metrics

• Hits@n (n=10,100): Top-n accuracy
• Mean Rank (MR): Average ranking (macro and micro)
• AUC ROC: Area under ROC curve
• Filtered Metrics: Metrics after removing axioms in training set and deductive closure

Baseline Methods

• Baseline Methods: Original ELEmbeddings, ELBE, Box2EL
• Improved Versions:
  • +l: Add negative loss for all standard forms
  • +l+n: Add negative loss and negative sample filtering

Implementation Details

• Implemented using mOWL library
• Training epochs: 2000 for STRING & GO data, 800 for Food & GALEN data
• Batch size: 32,768
• Optimizer: Adam with ReduceLROnPlateau learning rate scheduler
• Hyperparameters determined through grid search

Experimental Results

Main Results

Protein-Protein Interaction Prediction (Table 4)

• ELEmbeddings+l+n: Hits@10 improved from 0.05 to 0.06, Hits@100 from 0.31 to 0.37
• Box2EL+l+n: Significantly reduced average ranking while maintaining Hits@100 performance

Protein Function Prediction (Table 3)

• Box2EL achieved best performance: Hits@10 of 0.28, AUC of 0.96
• After adding negative loss, AUC improved for ELEmbeddings and ELBE

Subclass Relationship Prediction

• Food Ontology (Table 5): ELBE+l improved Hits@10 from 0.01 to 0.04
• GALEN Ontology (Table 6): All methods showed improved Hits@n metrics after adding negative loss

Ablation Studies

Negative Sample Filtering Effects

Through bias experiments on Food Ontology (Figure 3):

• Reducing the proportion of entailed axioms in negative samples continuously improves performance
• Filtering effects are more pronounced when the proportion of entailed axioms in negative samples is higher

Visualization Analysis

2D embedding visualizations (Figures 1-2) show:

• After adding all negative losses, the model better preserves the logical structure of the ontology
• Negative sample filtering helps construct more faithful geometric models

Filtered Metrics Analysis

Comparing metrics before and after filtering (NF-F columns):

• Improved methods prioritize predicting entailed axioms
• This indicates the model constructs more accurate ontology models

Related Work

Graph-Based Ontology Embedding

• Projects ontologies into graph structures using Word2Vec or knowledge graph embedding methods
• Advantages: Can handle adjacency information
• Disadvantages: Difficult to handle logical operators, cannot approximate ontology models

Geometric Ontology Embedding

• ELEmbeddings: Uses hyperspheres to represent concepts
• ELBE/BoxEL: Uses axis-aligned boxes, supports intersection operations
• Box2EL: Uses two boxes to represent role domain and range
• EmEL++/EmELvar: Extended to handle role chains and role inclusions

Knowledge Base Completion Methods

• Large language model-based methods (HalTon, natural language reasoning, etc.)
• Graph structure-based link prediction methods
• Matrix-based ontology embedding methods

Conclusions and Discussion

Main Conclusions

1. Importance of Deductive Closure: Fully leveraging the deductive closure significantly improves the performance of geometric embedding methods.
2. Impact of Negative Sample Quality: Avoiding treating entailed statements as negative samples is crucial for model training.
3. Improved Evaluation Methods: Evaluation methods considering deductive closure more accurately reflect the model's knowledge base completion capability.
4. Method Generalizability: Improvement strategies apply to multiple geometric embedding methods.

Limitations

1. Computational Complexity: Deductive closure computation may face efficiency issues on large-scale ontologies.
2. Approximate Algorithm: The proposed deductive closure algorithm is sound but incomplete.
3. Evaluation Limitations: Current evaluation metrics still rely on individual axiom ranking without considering semantic similarity.
4. Scope of Applicability: Primarily targets $\mathcal{EL}^{++}$; extensibility to more expressive description logics is limited.

Future Directions

1. Develop more efficient deductive closure computation algorithms
2. Design evaluation metrics considering semantic similarity
3. Extend to more expressive description logics
4. Construct more knowledge base completion benchmark datasets

In-Depth Evaluation

Strengths

1. Accurate Problem Identification: Accurately identifies key issues in existing methods regarding negative sample selection and deductive closure utilization.
2. Reasonable Method Design: Proposed negative loss functions and filtering strategies are theoretically well-motivated.
3. Comprehensive Experiments: Validates method effectiveness across multiple datasets and tasks, including visualization analysis.
4. Theoretical Contribution: Provides a sound algorithm for deductive closure computation with theoretical value.
5. Strong Generalizability: Improvement strategies apply to multiple geometric embedding methods.

Weaknesses

1. Limited Performance Gains: Improvements are modest on some tasks, potentially insufficient to justify additional complexity.
2. Computational Overhead: Deductive closure computation and negative sample filtering increase training time, but the paper insufficiently analyzes this overhead.
3. Benchmark Scale: Datasets used are relatively small; effectiveness on large-scale applications remains to be verified.
4. Insufficient Comparisons: Lacks comparison with recent LLM-based knowledge base completion methods.

Impact

1. Academic Value: Provides important improvement insights for the geometric ontology embedding field.
2. Practical Value: Improved methods can be directly applied to knowledge base completion in biomedical and other domains.
3. Reproducibility: Code and data are publicly available, facilitating reproduction and extension.

Applicable Scenarios

1. Formalized Knowledge Bases: Particularly suitable for ontologies with rich logical structures.
2. Biomedical Domain: Shows good performance on tasks such as gene ontology and protein function prediction.
3. Applications Requiring Interpretability: Geometric embeddings provide interpretable model structures.

References

The paper cites 50 related references covering important works in description logic, ontology embedding, knowledge graph completion, and related fields, providing a solid theoretical foundation for the research.