Neural Reasoning for Robust Instance Retrieval in SHOIQ

A knowledge base (KB) is a pair $\mathcal {K} = \langle \mathcal {T}, \mathcal {A}\rangle$. The TBox $\mathcal {T}$ contains general concept inclusions (GCIs) of the form C⊑D, where C, D are concepts. The ABox $\mathcal {A}$ includes assertions having the form C(a) (concept assertion) or r(a, b) (role assertion) for individuals a, b, concepts C, and role r. The description logic $\mathcal {SHOIQ}$ additionally includes an RBox, which contains axioms pertaining to roles. A role inclusion axiom (RIA) has the form r⊑s. A transitivity axiom is denoted by Tra(r), and a functionality axiom by Fun(r), where r and s are roles. A role s is simple if there is neither a transitivity axiom Tra(r), nor Tra(r^{− 1}) for any role r subsumed by s. For simplicity of presentation, we assume that the TBox $\mathcal {T}$ includes both concept and role axioms. The syntax and semantics for concepts in $\mathcal {SHOIQ}$ [1, 18] are given in Table 1.

Let C⊑D be a GCI and $\mathcal {I}$ be an interpretation. Then, $\mathcal {I}$ satisfies C⊑D, denoted as $\mathcal {I}\models {C}\sqsubseteq D$ iff ${C}^\mathcal {I}\subseteq {D}^\mathcal {I}$. Similarly, $\mathcal {I}$ satisfies an assertion C(a) iff $a^\mathcal {I}\in {C}^\mathcal {I}$. The assertion r(a, b) is satisfied by $\mathcal {I}$ iff $(a^\mathcal {I}, b^\mathcal {I}) \in {r}^\mathcal {I}$. Finally, $\mathcal {I}$ satisfies an RIA r⊑s iff $r^{\mathcal {I}}\subseteq s^{\mathcal {I}}$ and axioms Tra(r), Fun(r) iff the interpretation $r^{\mathcal {I}}$ is a transitive and a functional role, respectively. We say that $\mathcal {I}$ is a model of the KB $\mathcal {K}$, denoted by $\mathcal {I} \models \mathcal {K}$, iff $\mathcal {I}$ satisfies every axiom in $\mathcal {K}$. Finally, let $\mathcal {K}$ be a DL KB and α be an axiom, then $\mathcal {K}\models \alpha$ iff $\mathcal {I}\models \alpha$ for every model $\mathcal {I}$ of $\mathcal {K}$.

Reasoning with expressive DL KBs is a computationally hard task. Specifically, the instance checking problem, which, given $\mathcal {K}$, a concept C, and an individual x, determines whether x is an instance of C in $\mathcal {K}$ (denoted as $\mathcal {K} \models C(x)$) is non-deterministic (resp., double) exponential time complete for $\mathcal {SHOIQ}$ [20]. Given such high complexity and the additional challenges posed by incomplete and inconsistent data in real-world scenarios, practical applications often require the use of approximation algorithms.

To the best of our knowledge, HermiT [15] is the only reasoner that fully supports the OWL 2 standard. HermiT is based on a “hypertableau” calculus that addresses performance problems due to nondeterminism and model size—the primary sources of complexity in state-of-the-art OWL reasoners. HermiT was shown to outperform the previous reasoners, including Pellet [30], and Fact++ [33]. OWL2Bench [29] compares different reasoners across datasets and OWL profiles. Pellet and its extension Openllet were found to perform best in terms of runtime. JFact, the Java implementation of Fact++, performed worst on all the reasoning tasks across all OWL 2 profiles. While OWL2Bench assessed the reasoner's performance to detect inconsistent ontologies, they did not assess the robustness of reasoners, i.e., how well they answer queries on incomplete or inconsistent data.

Let $\mathcal {E}$ be the set of all entities and $\mathcal {R}$ the set of all relations. A knowledge graph (KG) $\mathcal {K} \subseteq \mathcal {E} \times \mathcal {R} \times \mathcal {E}$ is a set of triples (also called assertions) of the form (x, r, y) where $x, y\in \mathcal {E}$ are called head and tail entities, respectively, and $r \in \mathcal {R}$ depict the relationship between them. A Knowledge Graph Embedding (KGE) model is defined as a parameterized scoring function over KGs, depicted as $\phi _\Theta : \mathcal {K}\rightarrow \mathbb {R}$. where Θ denotes parameters, which often comprise entity embeddings $\mathbf {E} \in \mathbb {R}^{|\mathcal {E}| \times d_e}$, relation embeddings $\mathbf {R} \in \mathbb {R}^{|\mathcal {R}| \times d_r}$, and additional parameters (e.g., affine transformations, batch normalizations, convolutions). Since d_e = d_r holds for many state-of-the-art models, we will use d to denote the number of embedding dimensions for both entities and relation types in a knowledge graph.

A plethora of KGE models have been developed over the last decade to address reasoning tasks over large symbolic knowledge graphs [9, 34]. These models aim to map entities and relations from the KG into continuous vector spaces, enabling efficient and scalable computation via algebraic operations. Most KGE approaches are primarily designed for the link prediction task, where the goal is to estimate the plausibility of a triple $(x, r, y) \in \mathcal {E} \times \mathcal {R} \times \mathcal {E}$. This is typically done via a scoring function $\phi _\Theta (x, r, y)$ parameterized by Θ, which produces a real-valued score $\hat{y}$ that reflects the likelihood (not necessarily calibrated) of the triple being valid [12].

Scoring functions vary across models: translational models like TransE [4] interpret relations as translations in vector space (i.e., $\vec{x} + \vec{r} \approx \vec{y}$), while bilinear models like DistMult [36] and ComplEx [32] employ multiplicative interactions, capturing symmetric and asymmetric patterns. Recent work has introduced more expressive representations based on Clifford algebras. Notably, Keci [12] generalizes models like DistMult and ComplEx by embedding entities and relations in Clifford spaces of the form Cl_{p, q}. DeCaL [31] extends this framework using degenerate Clifford algebras Cl_{p, q, r}, achieving state-of-the-art results on standard benchmarks.

Since most knowledge graphs encode only positive (i.e., true) facts, training KGE models necessitates the creation of negative samples typically via corrupting the head or tail entity in a triple. This is done using negative sampling techniques such as Bernoulli sampling [25], 1-vs-All, or K-vs-All strategies [27], which help the model differentiate between plausible and implausible triples. Learning is commonly performed using margin-based ranking losses or cross-entropy objectives, with regularization techniques to mitigate overfitting in large-scale settings.

KGEs have demonstrated remarkable versatility and effectiveness across a wide range of applications beyond link prediction. In drug discovery, embeddings assist in identifying novel drug-target interactions by modeling complex biomedical graphs [3]. In question answering, KGEs serve as soft reasoning engines that embed semantic relationships into the retrieval and inference pipeline [16]. In recommender systems, they enhance traditional collaborative filtering by leveraging multi-relational user-item graphs [8]. Moreover, recent trends explore explainable embeddings, temporal dynamics, and inductive generalization, pushing KGE techniques closer to deployment in real-world intelligent systems.

Mapping description logic syntax to our neural semantics (see in Section 3.3) solely requires an engine that can accurately predict whether an assertion (x, r, y) is true. We map this task to computing whether the score assigned to an assertion is greater than or equal to a preset threshold γ. A key to achieving high accuracy on this task lies in the construction of a knowledge graph that renders the key assertions for our input knowledge base in such a way that accurate predictions can be carried out. To construct this knowledge graph $\mathcal {K}\subseteq \mathcal {E} \times \mathcal {R}\times \mathcal {E}$, we extract taxonomic axioms of the form $C(a)\equiv (x, \texttt{rdf:type}, C),\ r(x,y)\equiv (x,r,y)$, $C\sqsubseteq D\equiv (C, \texttt{rdfs:subClassOf}, D)$ and $r \sqsubseteq s\equiv (r, \texttt{rdfs:subPropertyOf}, s)$. The graph $\mathcal {G}$ is then used as input to a KGE model to learn embeddings for entities and relation types. This yields a trained KGE model $\phi _\Theta : \mathcal {E} \times \mathcal {R}\times \mathcal {E} \rightarrow \mathbb {V}^d$— where $\mathbb {V}^d$ is a vector space.

Once the model $\phi _\Theta$ is trained, we construct a neural link predictor $\phi : \mathcal {E} \times \mathcal {R} \times \mathcal {E} \rightarrow [0,1]$ which can assign a truth probability to any triple (x, r, y) from its domain. Given that the scores computed by $\phi _\Theta$ are not bound, we chose to use the sigmoid trick used in neural networks to translate scores into a range that can be interpreted as a probability. Consequently, we set $\phi (x, r, y) = \sigma (\phi _\Theta (x, r, y))$, where σ stands for the sigmoid function. A triple is then considered true in our neural interpretation if ϕ(x, r, y) is larger than a preset threshold γ. This is a key difference to symbolic reasoning (see Table 2 for details on the neural semantics). In particular, triples (x, r, y) found in $\mathcal {K}$ might be predicted to be false and hence not included in the neural interpretation of the input knowledge graph.

The syntax and semantics for concepts in $\mathcal {SHOIQ}$ are provided in Table 1. We define a mapping from concept constructors in $\mathcal {SHOIQ}$ to their neural semantics in Table 2. For a given KB $ \mathcal {K}$, the domain $\Delta ^\mathcal {N} \subseteq \mathcal {E} \cup \mathcal {R}$ of the interpretation $\mathcal {N}$ computed by Ebr is the set of all class names, individual names and role names found in the axioms in $\mathcal {K}$.

These mappings allow us to handle not only atomic concepts and roles but also more expressive axioms involving complex concept expressions. For example, consider the TBox axiom A⊓∃r.B⊑C⊔∀r.D, which asserts that individuals belonging to both A and those related via r to instances of B must also belong to either C or to those whose r-successors are all in D. In the neural setting, this axiom is interpreted as a set inclusion constraint: $(A^{\mathcal {N}} \cap \lbrace x \mid \exists y.\ (x, y) \in r^{\mathcal {N}} \wedge y \in B^{\mathcal {N}} \rbrace) \subseteq (C^{\mathcal {N}} \cup \lbrace x \mid \forall y.\ (x, y) \in r^{\mathcal {N}} \Rightarrow y \in D^{\mathcal {N}} \rbrace)$.

While such axioms are not explicitly encoded as triples in the knowledge graph, their components, such as class memberships and role assertions, are grounded via basic triples like :a rdf:type :A, :a :r :b, and :b rdf:type :B. The embedding-based interpretation $\mathcal {N}$ reconstructs the semantics of the full axiom by composing the neural representations of these grounded components, thus enabling reasoning over complex concept expressions in a continuous space.

We evaluated our proposed approach on six benchmark datasets, including four large datasets (Carcinogenesis, Mutagenesis, Semantic Bible, and Vicodi) and two smaller datasets (Family and Father). These datasets cover a range of domains, from biological interactions to historical and familial relationships. Detailed statistics for each dataset are provided in Table 3.

We evaluate Ebr across three main tasks to assess its robustness and effectiveness under different knowledge base conditions.

Task 1: Instance Retrieval. In the first task, we evaluate Ebr on standard instance retrieval using complete and consistent knowledge bases. The goal is to measure how accurately our reasoner retrieves instances of given class expressions compared to symbolic reasoners. We quantify performance using the Jaccard similarity, which compares the set of instances $\hat{y}$ retrieved by our reasoner with the ground-truth set y obtained from symbolic reasoners.³ The Jaccard similarity $J(\hat{y}, y)$ is defined as:

Task 2: Robustness to Noise and Incompleteness. The second task examines the performance of Ebr under noisy and incomplete knowledge bases. Starting from a consistent and correct knowledge base $\mathcal {K}$, we simulate noise by injecting $\nu |\mathcal {K}|$ random false axioms, where ν denotes the predefined noise ratio. To simulate incompleteness, we randomly remove $\nu |\mathcal {K}|$ axioms from $\mathcal {K}$. For concept learning, we focus on the inconsistent scenario and compare Ebr, against baseline reasoners.

Evaluation Protocol. We first choose a KGE model and integrate it into EBR to perform instance retrieval and concept learning across the scenarios described above. For all instance retrieval experiments, we use the Fast Instance Checker (FIC) reasoner from the DL-Learner framework [6, 10], which can support reasoning under inconsistency, making it a suitable reference for evaluating embedding-based retrieval. Other symbolic reasoners used include Pellet, HermiT, Openllet, JFact, and the Structural reasoner, the latter being a lightweight variant of FIC. For concept learning, we evaluate four state-of-the-art learners: OCEL and CELOE [6, 23] from the DL-Learner framework, CLIP [22], and EvoLearner (EVO) [17] with baseline reasoners in the backend and compare their performances (using the traditional F1-score [11]). All concept learners rely on FIC as their default reasoning component, ensuring consistency and comparability across models. Their performances are assessed using the traditional F1-score [11].

All our experiments were carried out on a virtual machine with 2 NVIDIA H100-80C GPUs, each with 80 GB of memory. Note that the embedding computation only consumed approximately 16 GB of GPU memory on the biggest datasets (e.g., Vicodi).

We selected the KGE model and embedding dimensionality used throughout our experiments following a systematic protocol aimed at maximizing retrieval accuracy while maintaining a reasonable balance between model complexity and training cost. Each candidate KGE model was trained with embedding dimensions of 16, 32, 64, 128, and 256, and its instance retrieval performance within Ebr was assessed using the Jaccard similarity between the instances predicted by the Embedding-Based Reasoner (EBR) and those retrieved by the symbolic instance checker (FIC). The average Jaccard scores over all target expressions are summarized in Figure 1.

From the figure, it is evident that TransE and DistMult perform poorly–TransE never exceeds a Jaccard score of 0.2, while DistMult remains below 0.4–regardless of the embedding dimensionality. This suggests that the embeddings learned by these models are not sufficiently expressive to capture the relational and hierarchical semantics required for accurate instance retrieval within expressive ontologies. In contrast, other embedding models such as DeCaL, Keci, DualE [7], and ComplEx exhibit strong performance, with their Jaccard similarity steadily converging toward 1.0 as the embedding dimension increases. This indicates that Ebr can operate effectively with a wide range of expressive KGE models.

Based on these observations, we selected ComplEx with an embedding dimension of 128 as the default configuration for Ebr. This choice was motivated by three consistent findings from Figure 1: (i) ComplEx achieves the highest and most stable Jaccard scores across all datasets, (ii) performance improvements plateau beyond 128 dimensions, and (iii) the model remains computationally efficient at this size. As confirmed in Table 4, this configuration enables EBR to achieve perfect retrieval accuracy across all datasets and OWL concept types from dimension 128 onward.

Table 4 reports the instance retrieval performance of Ebr across four error-free benchmark datasets. Performance improves steadily with larger embedding dimensions, reaching perfect Jaccard scores (1.00) for all concept types at d = 128 and beyond. The largest gains occur between d = 32 and d = 64, indicating that a minimum embedding capacity is needed to capture the ontological structure of these datasets.

For instance, in the Carcinogenesis dataset, accuracy for conjunctions (C⊓D) rises from 0.37 at d = 32 to 0.99 at d = 64, achieving perfection at d = 128. Similar trends hold for other complex concepts such as C⊔D, ∃r.C, and ∀r.C. Increasing d beyond 128 yields no meaningful improvement, confirming that d = 128 strikes an effective balance between accuracy and computational efficiency. The consistent results across all datasets further support the generality of this configuration.

An important advantage of Ebr is its robustness to the choice of the parameter γ, which governs the selection of individuals (see Table 2). Across all datasets, we observed that varying γ had a negligible impact on the Jaccard similarity, hence, on the set of retrieved instances. This makes Ebr easier to tune in practice, as it consistently retrieves correct instances without requiring fine-grained threshold calibration.

Here, we present the results of $\rm E{\small BR}$ along with state-of-the-art reasoners on all datasets. In Figure 3, we present the average Jaccard similarity scores with margins of error for each dataset across varying levels of incompleteness. In general, Ebr exhibits higher or comparable Jaccard similarity scores relative to other reasoners in most cases, particularly at higher levels of incompleteness. However, as the level of incompleteness increases, the performance of all reasoners declines. This is expected, as higher incompleteness typically leads to poorer retrieval performance. In this phase, removed instances are not tracked; therefore, the threshold is determined through the experiments. Therefore, given queries may not be related to removed instances, which explains why we can have an increase or the same performance for an increased level of incompleteness.

Table 5 reports the average runtime of each reasoner across datasets for the concept retrieval task. Overall, Ebr exhibits strong runtime efficiency, achieving the affordable execution times on smaller datasets such as Family and Father, and competitive performance on larger ones like Carcinogenesis and Vicodi. While symbolic reasoners such as HermiT and JFact show significantly higher runtimes, particularly on complex ontologies Ebr maintains a consistent balance between speed and scalability.

The general performance of all reasoners on noisy knowledge bases is illustrated in Figure 2. In the Carcinogenesis, Mutagenesis, and Vicodi datasets, we injected $1\%$ and $2\%$ noise, corresponding to at least 1,000 corrupted axioms per dataset. For smaller datasets, the noise ratios ranged between $10\%$ and $80\%$.

As shown in Figure 2, symbolic reasoners do not operate on most noisy datasets. Symbolic reasoners often fail on noisy datasets due to contradictions introduced by injected noise, which make knowledge bases inconsistent. In contrast, Ebr, along with FIC and the Structural reasoner, can handle such inconsistencies. Ebr shows strong robustness, achieving consistently high Jaccard scores and outperforming other reasoners on most datasets, except for a slight drop against FIC on the Semantic_Bible dataset. It also performs best on datasets without contradictions, like Mutagenesis and Family.

We further assessed the effectiveness of Ebr when integrated into concept learning frameworks on inconsistent knowledge bases. The results in Table 6 report the average F1-scores (and standard deviations where applicable) for several concept learners combined with different reasoning backends. Ebr maintained stable and high predictive performance across all learners. On the Carcinogenesis dataset, EBR achieved perfect F1-scores (1.00) across all learners, surpassing both FIC and Structural. On the more complex Vicodi dataset, EBR remained competitive with FIC, consistently outperforming the Structural reasoner. These results highlight that Ebr not only supports reasoning under inconsistencies but also enables reliable concept learning in scenarios where classical symbolic reasoners cannot operate.