# An Embedding-Based Approach to Repairing OWL Ontologies
## 4 Algorithm  
In this section, we design two concrete algorithms (i.e., a threshold-based algorithm and a signature-based algorithm) to repair an incoherent ontology based on the definitions of similarity degrees. Algorithm 1 provides the details about the threshold-based repair algorithm. It takes an incoherent ontology \(O\), all of its MIPS \(MIPS(O)\), axiom embeddings \((emb(\alpha)\) indicatesthe embedding of the axiom \(\alpha\)), and a threshold \(t\) ranging from 0 to 1 as inputs, and outputs a diagnosis. This algorithm assumes all MIPS of \(O\) have been computed and are denoted as \(MIPS(O)\). In this algorithm, the degree of each axiom in a MIPS needs to be computed first (see lines 4-13), which is the average similarity over those axiom pairs whose similarity values are greater than the threshold. According to these degrees, a subset \(M^{\prime}\) is extracted from each MIPS \(M\) such that only the axioms with the lowest degree are contained in \(M^{\prime}\) (see lines 15-18). Afterwards, a diagnosis can be generated over these subsets by applying the linear integer programming (abbreviated as ILP)-based approach [26] (see lines 20-30). We choose this approach to computing a minimal diagnosis instead of the traditional one (i.e., hitting set tree-based approach [22]) due to its high efficiency. ```
Data: An incoherent ontology \(O\), all MIPS in \(O\) (i.e., MIPS(O)), embeddings of axioms, and a threshold \(t\) (\(t\in(0,1)\)) Result: A diagnosis \(D\) begin \(\mathcal{M}\), \(\mathcal{C}=\emptyset\) // Compute a degree for each axiom in the union of all MIPS in \(O\) for\(ax\in\bigcup_{M\in MIPS(O)}M\)do \(s\), \(c=0\) for\(ax^{\prime}\in O\)do if\(sim(emb(ax),\;emb(ax^{\prime}))>t\)then \(s=s+sim(emb(ax),\;emb(ax^{\prime}))\) \(c=c+1\)  end if  end for \(d_{thr}(ax,O,t)=s/c\)  end for // Choose a subset from each MIPS such that the axioms in the subset have the lowest degree for\(M\in MIPS(O)\)do \(M^{\prime}=\{a\in M:\exists a^{\prime}\in M,\;d_{thr}(a,O,t)>d_{thr}(a^{\prime}, O,t)\}\) \(\mathcal{M}=\mathcal{M}\cup\{M^{\prime}\}\}\)  end for // Apply an ILP solver to compute a diagnosis for the extracted subsets \(S_{union}=\bigcup_{M^{\prime}\in\mathcal{M}}M^{\prime}\) \(X=\{x_{j}|ax_{j}\in S_{union},\;j=1,...,|S_{union}|\}\) \(z=\sum_{x_{j}\in X}x_{j}\) for\(M^{\prime}\in\mathcal{M}\)do \(X_{M^{\prime}}=\{x_{j}|ax_{j}\in M^{\prime},x_{j}\in X\}\) \(c_{i}=(\sum_{x_{j}\in X_{M^{\prime}}}x_{j})\geq 1\) \(\mathcal{C}=\mathcal{C}\cup\{c_{i}\}\)  end for \(S_{assi}=\textbf{ILP_Solver}(z,\mathcal{C},\min)\) // Translate the solution given by the ILP solver into a set of axioms \(D=\{ax_{j}|(x_{j}=1)\in S_{assi}\}\) return\(D\)  end for
```  
**Algorithm 1**A threshold-based algorithm to repair an incoherent ontology. The ILP-based approach first associates a binary variable to each axiom in the union of all MIPS (see lines 20-21). An objective function is then constructed over all binary variables by regarding them as the same important (see Line 22). For each set in \(\mathcal{M}\), a constraint \(c_{i}\) is constructed (see lines 23-27). Finally, the function ILP_Solver is invoked to generate an optimal assignment (see Line 28), and this can be achieved through invoking a traditional ILP solver such as the commercial linear programming tool Cplex. It is an optimization software developed by IBM ILOG ([[https://www.ibm.com/analytics/cplex-optimizer](https://www.ibm.com/analytics/cplex-optimizer)]([https://www.ibm.com/analytics/cplex-optimizer](https://www.ibm.com/analytics/cplex-optimizer)), accessed on 15 November 2022). For this function, one of its parameters \(min\) indicates minimizing the objective function. The returned assignment \(S_{assi}\) is the first one found by the ILP solver. Based on this assignment, we can find those axioms whose corresponding variables have the value 1 to form a final solution \(D\) (see Line 30). The signature-based repair algorithm can be obtained easily by modifying Algorithm 1 slightly.