
==== Front
Heliyon
Heliyon
Heliyon
2405-8440
Elsevier

S2405-8440(24)11994-9
10.1016/j.heliyon.2024.e35963
e35963
Research Article
Eliminating ontology contradictions based on the Myerson value
Wu Juanyong a
Peng Wei gs.wpeng22@gzu.edu.cn
bc⁎
a School of Mathematics and Statistics, Guizhou University of Finance and Economics, Huayan Road, Guiyang, 550025, Guizhou, China
b Department of Computer Science, Guizhou University, Jiaxiu South Road, Guiyang, 550025, Guizhou, China
c Institute for Artificial Intelligence, Guizhou University, Jiaxiu South Road, Guiyang, 550025, Guizhou, China
⁎ Corresponding author. gs.wpeng22@gzu.edu.cn
12 8 2024
30 8 2024
12 8 2024
10 16 e3596319 10 2023
5 8 2024
6 8 2024
© 2024 The Authors
2024
https://creativecommons.org/licenses/by-nc-nd/4.0/ This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).
Ontologies play a pivotal role in knowledge representation across various artificial intelligence domains, serving as foundational frameworks for organizing data and concepts. However, the construction and evolution of ontologies frequently lead to logical contradictions that undermine their utility and accuracy. Typically, these contradictions are addressed using an Integer Linear Programming (ILP) model, which traditionally treats all formulas with equal importance, thereby neglecting the distinct impacts of individual formulas within minimal conflict sets. To advance this method, we integrate cooperative game theory to compute the Shapley value for each formula, reflecting its marginal contribution towards resolving logical contradictions. We further construct a graph-based representation of the ontology, enabling the extension of Shapley values to Myerson values. Subsequently, we introduce a Myerson-weighted ILP model that employs a lexicographic approach to eliminate logical contradictions in ontologies. The model ensures the minimum number of formula deletions, subsequently applying Myerson values to guide the prioritization of deletions. Our comparative analysis across 18 ontologies confirms that our approach not only preserves more graph edges than traditional ILP models but also quantifies formula contributions and establishes deletion priorities, presenting a novel approach to ILP-based contradiction resolution.

Keywords

Ontology contradictions
Cooperative game theory
Lexicographic approach
Myerson value
Shapley value
==== Body
pmc1 Introduction

Ontologies are indispensable in artificial intelligence, providing a structured approach to knowledge representation. They provide a set of representational primitives that can model a domain of knowledge or discourse, including the definition of concepts, interconnections between them, and axioms [1]. In computer science, ontologies enhance resource sharing and foster mutual understanding across diverse systems and applications, thereby underpinning semantic web services [2]. Additionally, the application of ontologies extends to various other fields such as natural language processing, intelligent search, and recommendation systems [3], [4].

Logical contradictions frequently arise during the construction, revision, and mapping of ontologies [5], [6], [7]. These contradictions typically manifest as inconsistencies and incoherences within the ontology: inconsistency implies the absence of a viable model for the ontology, while incoherence pertains to the presence of unsatisfiable concepts, which are deemed to represent empty sets. Given that ontologies with such contradictions yield invalid conclusions when subjected to standard reasoning processes, resolving these contradictions is both crucial and challenging [8].

The resolution of logical contradictions in ontologies hinges on the concept of minimal conflict sets, which offer a precise representation of these contradictions [9], [10], [11], [12]. To address these contradictions, one can compute minimal conflict sets through debugging methods and subsequently remove at least one formula from each set. This approach aims to retain as many formulas as possible to preserve the ontology's semantic integrity. One approach involves Reiter's Hitting Set Tree (HST) algorithm [13]. Schlobach et al. proposed determining the minimal hitting set among all minimal incoherence-preserving subsets of an incoherent ontology, where the removal of each hitting set could reinstate the coherence of ontologies [14]. Kalyanpur et al. proposed a method to acquire the rank of axioms in minimal unsatisfiability-preserving subsets and calculating a hitting set with minimal path rank [15]. Qi et al. introduced algorithms that employ scoring functions or weighted approaches to expedite the hitting set search and reduce the search space [6]. Recently, another significant method involves using integer linear programming (ILP), as proposed by Ji et al. [16], which treats the formulas in a minimal conflict set as decision variables and linear constraints, aiming to remove the fewest formulas possible. Notably, this ILP model can process a large ontology in 500 milliseconds, a task at which the HST method may fail, provided a time limit of 1000 seconds is set. The focus of this paper is on this ILP-based strategy for eliminating logical contradictions in ontologies.

The ILP model efficiently eliminates logical contradictions but treats all formulas as equally important. This does not fully exploit the varying contributions of formulas in resolving contradictions and often overlooks the potential for more optimal solutions that include the fewest formulas. To enhance this methodology, this paper introduces an inconsistency measure based on the Shapley value, as proposed by Hunter et al. [17]. This measure quantifies the inconsistency within minimal inconsistent subsets and correlates these inconsistencies with specific Shapley values, integrating the principles of cooperative game theory [18].

Drawing on the work of Hunter et al. [17], we initially define the ontology's structure as a transferable utility game (TU game) from a cooperative game perspective, and then apply the Shapley value to assign a specific value to each formula within minimal conflict sets. To deepen our analysis of the interactions among formulas, we incorporate commonsense reasoning, constructing a commonsense reasoning graph for the ontology. This allows us to extend the Shapley value to the Myerson value based on the graph structure. To minimize deletions and preserve ontology semantics, we employ a lexicographic method [19] in our Myerson value-weighted ILP model. This model prioritizes minimizing the number of formula deletions and then preferentially removes formulas with higher Myerson values. We conducted experiments on 18 ontology datasets, generating random graphs (repeatedly) to model commonsense reasoning and comparing the ILP model against our Myerson-weighted model. Our findings indicate that the Myerson-weighted model generally retains more edges within the ontology graph compared to the standard ILP model. Our contributions are as follows:• We enhance the process of resolving logical contradictions in ontologies by introducing a cooperative game approach to measure the value of formulas within minimal conflict sets, and augmenting the standard ILP model with deletion preferences based on these values.

• We introduce a Myerson-weighted linear programming model utilizing the lexicographic method to systematically address logical contradictions in ontologies. The model prioritizes semantic preservation and then selectively targets formulas for deletion based on Myerson value.

• Our extensive testing on 18 ontologies demonstrates that, on average, our proposed Myerson-weighted ILP model retains approximately 4% more edges in the ontology graph compared to the standard ILP model.

The paper is structured as follows: Section 2 provides preliminaries to aid comprehension. Section 3 outlines our primary theories and methodologies. Section 4 presents experimental evidence validating the efficacy of our approach. Finally, Section 5 concludes the article and discusses directions for future research.

2 Preliminary

2.1 Cooperative game

Cooperative games, which are a branch of game theory, explore how groups can collaborate to achieve mutually beneficial outcomes [20]. These games have diverse applications in a wide range of fields, including economics, political science, computer science, and social psychology [21], [22]. A cooperative game with transferable utility is mathematically represented as a tuple (N,v) [23], where N denotes the set of players, and v is the characteristic function that assigns a value to each subset of players, indicative of the coalition's worth.

The Shapley value is a significant solution concept in cooperative game theory that allocates the total worth of a coalition among its members [18]. It was first introduced in 1953 and has become one of the most widely studied and applied concepts in cooperative game theory. Specifically, the Shapley value assigns a unique payoff to each player i in a cooperative game (N,v), representing the average marginal contribution of player i over all possible orders of coalition formation. The formal definition of the Shapley value for player i is given by Eq. (1):(1) Shi(N,v)=∑S⊆N∖{i}s!(n−s−1)!n!(v(S∪{i})−v(S)),for alli∈N.

Furthermore, the Shapley value satisfies the following properties: Efficiency: Ensures the sum of the Shapley values equals the total worth of the grand coalition.

Linearity: Guarantees the Shapley value is a linear function of the coalition's worth.

Symmetry: Two players contributing equally across all coalitions receive identical Shapley values.

Null-player: A player who adds no value to any coalition receives a zero payoff.

2.2 Graph theory

Graph theory is a branch of mathematics focused on the study of graphs, which are structured as collections of vertices (or nodes) connected by edges. [24]. This field has wide-ranging applications in disciplines such as computer science, engineering, and social sciences, among others.

In graph theory, a graph is represented as G=(V,E), where V={v1,...,vn} is the set of vertices, and E⊆V×V is the set of edges connecting these vertices. Vertices are commonly denoted by v, u, or w, and vi or vj for specific instances. The neighbors of a vertex v are denoted as N(v), representing vertices directly connected to v. A path in a graph is defined as a sequence of distinct nodes connected consecutively by edges. A graph is considered connected if there exists a path between every pair of nodes in that graph. A cut vertex, denoted as v∈V, in a connected graph (V,E), as a vertex that, upon its removal along with all its edges, divides the graph into disconnected components. In other words, the graph (V∖{v},E∖{{v,w}∈E:w∈V}) is disconnected.

2.3 Description logic ontology and logical contradiction

A Description Logic Ontology (DLO) comprises a set of concepts, roles, and axioms. Concepts are used to represent sets of individuals in a domain, while roles represent binary relations between individuals [25]. Axioms are statements that define the meanings of concepts and roles in the ontology. In DLO, concepts are defined with constructors, such as negation, conjunction, disjunction, existential restriction, and universal restriction. Roles in DLO are defined with properties, such as transitivity, reflexivity, and symmetry. Axioms in DLO define the relationships between concepts and roles in the ontology, and they can be classified as TBox and ABox axioms. TBox axioms define the terminology of the ontology, including the hierarchy of concepts and the properties of roles, whereas ABox axioms define the instances of the ontology, including the individuals and their relationships.

The presence of logical contradictions in DLOs poses a significant challenge, arising when two or more statements within the ontology conflict with each other [26]. Such contradictions often lead to inconsistencies, necessitating the computation and removal of minimal sets of axioms, a process known as axiom pinpointing [27]. To aid in understanding and resolving these contradictions, several key definitions are crucial:

Definition 1 Unsatisfiable concept

[28] A concept name C in an ontology O, is unsatisfiable iff, for each interpretation I of O, CI=∅.

Definition 2 Incoherent ontology

[28] An ontology O is incoherent iff there exists an unsatisfiable concept name in O.

Definition 3 Inconsistent ontology

[28] An ontology O is inconsistent iff it has no model.

Definition 4 Minimal unsatisfiability-preserving sub-ontology

[29] Let C be an unsatisfiable concept in an ontology O. An ontology O′⊆O is a minimal unsatisfiability-preserving sub-ontology (MUPS) of O w.r.t. C if C is unsatisfiable in O′ and satisfiable in every sub-ontology O″⊂O′.

Definition 5 Minimal incoherence-preserving sub-ontology

[29] Let O be an incoherent ontology. An ontology O′⊆O is a minimal incoherence-preserving sub-ontology (MIPS) of O if O′ is incoherent and every sub-ontology O″⊂O′ is coherent.

Definition 6 Minimal inconsistent sub-ontology

[30] An ontology O′⊆O is a minimal inconsistent sub-ontology (MIS) of O, if O′⊆O is inconsistent and every sub-ontology O″⊂O′ is consistent.

These definitions express that a MUPS, MIPS, or MIS is a minimal subset of an ontology that retains a specific property, namely, unsatisfiability, incoherence, or inconsistency, respectively. The removal of such subsets can effectively resolve the corresponding issues within the ontology. Since our approach does not require specification of the particular type of conflict, we employ the term minimal conflict set to refer to these subsets.

In order to clearly explain how logical contradictions can be eliminated based on the ILP approach, we use Algorithm 1 for illustration. Initially, the algorithm requires an ontology and a set of minimal conflict sets CONF(O), as input. Line 1 initializes C, an empty set of constraints. Line 2 constructs F, aggregating all formulas across the minimal conflict sets from CONF(O). In Line 3, X is defined, a set of decision variables where each variable xi corresponds to a formula ϕi in F. An iteration starts from Line 4 to Line 7 for each minimal conflict set confj. Line 5 creates Xconfj, a subset of X comprising variables linked to the formulas in confj. Line 6 enforces a constraint ensuring that the sum of decision variables in Xconfj is at least one, signifying that at least one formula from each conflict set is selected. This constraint is then added to C in Line 7. After processing all conflict sets, Line 9 applies binary constraints to each decision variable, mandating that each xi can only take values 0 or 1. Line 10 establishes the objective function Z, which sums all xi in X and aims to minimize this sum, reflecting the goal to select the minimal number of formulas. Line 11 involves the ILP solver optimizing Z subject to the constraints C, and Line 12 assembles the solution set S from the formulas corresponding to decision variables set to 1 in the results R from the solver. Finally, Line 13 returns S, representing the minimal subset of formulas necessary to eliminate the identified logical contradictions.Algorithm 1 An ILP model for eliminating ontology contradictions.

Algorithm 1

3 Method

The traditional ILP method treats all formulas involved in logical contradictions with equal importance, solving the programming model to derive a solution set aimed at resolving these contradictions within an ontology. However, this approach fails to consider the inherent variability in the significance of formulas within minimal conflict sets, thus inadequately refining the contradiction elimination process. To address this limitation, we incorporate insights from inconsistency measure theory, as introduced by Hunter et al., which quantitatively measures the inconsistency within minimal inconsistent subsets of an inconsistent belief base K, defined as MI(K)={K′⊆K|K′⊢⊥and∀K″⊂K′,K″⊬⊥}, as illustrated in Eq. (2) [17].(2) IMI(K)=|MI(K)|

where |MI(K)| represents the size of MI(K). Leveraging this theoretical foundation, our method adapts the ILP model to more finely eliminate logical contradictions by considering the differential significance of formulas within ontologies. Subsequently, Section 3.1 defines the ontology in the context of cooperative games and presents the computation of the Shapley value for formulas in minimal conflict sets; Section 3.2 defines the graph of the ontology on the basis of common-sense reasoning and proposes the computation of the Myerson value for formulas in minimal conflict sets; Section 3.3 propose the Myerson weighted model for eliminating logical contradictions in ontologies.

3.1 The Shapley value in the minimal conflict set

Let (N,v) represent a TU game, where N is the set of players, and v is the characteristic function that assigns a value to each subset S⊆2N. In cooperative game theory, the characteristic function is used to measure the value of different player coalitions. Within the realm of ontology contradiction resolution, this theoretical framework is particularly applicable to minimal conflict sets comprised of distinct formulas. Assume O={ϕi} represents an ontology that contains logical contradictions, with each ϕi acting as a formula player. The coalition formed to eliminate these contradictions comprises various ϕi, defined as the set of minimal conflict sets CONF(O)={confj}. The solution set for resolving these contradictions, denoted by λ, includes one or more formulas selected from each confj, with λ∩confj≠∅ for confj∈CONF(O). Definition 7 formalizes the TU game for an ontology with logical contradictions. Definition 7 The TU game for an ontology

Let O be an ontology contains logical contradictions. The set CONF(O)={confj} represents the set of minimal conflict sets of O. The TU game for the ontology is defined by the tuple (NO,v), where NO is the set of players corresponding to the formulas in CONF(O), defined as NO=⋃confj∈CONF(O)confj. The characteristic function v assigns a worth v(S) to each coalition S∈2NO.

For the purpose of resolving logical contradictions in ontologies, for any coalition S∈2NO, the characteristic function v(S) is defined as follows:(3) v(S)={1,ifS∈CONF(O)0,otherwise

According to Eq. (3), only the formulas that belong to the minimal conflict set are considered eligible for forming coalitions S to eliminate logical contradictions within the ontology. It is crucial to note that every formula within a given confj holds equal importance in resolving the contradictions; the removal of any formula would breakdown the conflict. Therefore, with reference to Eq. (2) [17], the value assigned to each formula within confj can be equal and determined according to the cardinality of confj. Definition 8 defines the Shapley value in the minimal conflict set.

Definition 8 The Shapley value in the minimal conflict set

Given the TU game (NO,v) for an ontology O, let CONF(O)={confj} be the set of minimal conflict sets based on O, and NO=⋃confj∈CONF(O)confj. The Shapley value of ϕi∈NO is defined as Eq. (4):(4) Shϕi(NO,v)=∑S∈2NO(∑ϕi∈Sv(S)|S|)=∑confj∈CONF(O)(∑ϕi∈confj1|confj|)

where S represents the minimal conflict set containing ϕi in CONF(O), |S| denotes the cardinality of S, and v(S) denotes the value of S.

The Shapley value of ϕi is derived by summing its marginal contributions across all minimal conflict sets to which it belongs. The marginal contribution is equal to v(confj) divided by the cardinality of confj, since the formulas in confj are equally important for breaking conflict and should be assigned the same value. To elucidate this process, consider the Example 1:

Example 1 Given an ontology O consisting of seven formulas, denoted as O={ϕ1, ϕ2, ϕ3, ϕ4, ϕ5, ϕ6, ϕ7}. Let CONF(O)={{ϕ1,ϕ2,ϕ3},{ϕ1,ϕ4,ϕ6},

{ϕ3,ϕ4,ϕ5,ϕ6}} be the set of minimal conflict sets based on O. The Shapley value of each formula is then calculated as follows:Sh(ϕ1)(NO,v)=13+13=23	Sh(ϕ2)(NO,v)=13	Sh(ϕ3)(NO,v)=13+14=712	
Sh(ϕ4)(NO,v)=13+14=712	Sh(ϕ5)(NO,v)=14	Sh(ϕ6)(NO,v)=13+14=712	

For further clarification, consider ϕ1, which is a member of the minimal conflict sets conf1={ϕ1,ϕ2,ϕ3} and conf2={ϕ1,ϕ4,ϕ6}, but not to conf3={ϕ3,ϕ4,ϕ5,ϕ6}. The value of each conflict set is v(conf1)=1, v(conf2)=1, and v(conf3)=1. The contribution of ϕ1 is evenly distributed based on the cardinality of the sets to which it belongs, resulting in Sh(ϕ1,S=conf1)(NO,v)=13 and Sh(ϕ1,S=conf2)(NO,v)=13. Consequently, the overall Shapley value for ϕ1 is computed as 13+13=23.

3.2 The Myerson value in the minimal conflict set

3.2.1 Commonsense reasoning graph of an ontology

The Myerson value incorporates cooperative relationships among players by utilizing graph structures to allocate values among players in a TU game, where the values are assigned based on the connected components each player belongs to [31]. To elucidate the collaborative among the formulas, we define commonsense reasoning within the context of ontologies:

Definition 9 Commonsense reasoning

Given an ontology O and the commonsense knowledge ∑ be a set of formulas in O. For any formulas ϕ1 and ϕ2 in O, commonsense reasoning defined as ϕ1⊢∑ϕ2 iff ϕ1,∑⊢ϕ2.

Definition 9 establishes a relationship for understanding interactions among formulas based on shared knowledge. Notably, ⊢∑ represents a weaker form of reasoning compared to classical logical reasoning (⊢), as it incorporates a broader array of formulas into the reasoning process. To quantitatively assess the value of formulas based on their relationships in commonsense reasoning, we introduce the concept of a commonsense reasoning graph for an ontology.

Definition 10 The commonsense reasoning graph of an ontology

Given an ontology O and CONF(O)={confj} denotes the set of all minimal conflict sets based on O, and NO=⋃confj∈CONF(O)confj. Let ∑ be a set of formulas within O that constitutes the commonsense knowledge. The commonsense reasoning graph, GO=(V,E), is a directed graph where V={ϕi|ϕi∈NO}=NO comprises nodes corresponding to all formulas in NO, and E={<ϕi,ϕj>|ϕi,ϕj∈Vandϕi⊢∑ϕj} represents the relationships of commonsense reasoning with ∑ between the formulas.

The TU game of an ontology with commonsense reasoning is represented as a triple (NO,v,E), where (NO,v) defines the TU game of the ontology O, while (NO,E) is portrayed as the directed graph GO. This graph illustrates the commonsense reasoning relationships between the formulas, which correspond to the players in the game.

3.2.2 Benefit distribution for the elimination of logical contradictions

In the distribution of the Myerson value, the value assigned to each player is determined by the strongly connected component of the graph to which the player belongs. Building upon the Myerson value, we analyze subgraphs that correspond to coalitions within the commonsense reasoning graph GO. For each minimal conflict set confj within CONF(O), we define G(confj) as the subgraph of GO induced by the nodes corresponding to the formulas in confj. The Myerson value for formula players in a graph-restricted TU game is then calculated as shown in Eq. (5):(5) Myϕi(NO,v,E)=∑confj∈CONF(O)ϵ∈τ(G(confj))(∑ϕi∈ϵ1|τ(G(confj))|⋅|ϵ|)

where τ(G(confj)) denotes the set of strongly connected components of G(confj), and ϵ denotes the strongly connected component in τ(G(confj)) that contains ϕi.

To elucidate the computation of the Myerson value for formulas within minimal conflict sets, we detail Algorithm 2. The algorithm begins by taking as inputs the ontology O and a set of minimal conflict sets, CONF(O), along with commonsense reasoning relationships that establish connections between the formulas. Initially, line 1 constructs NO by aggregating all formulas from each minimal conflict set in CONF(O). Line 2 then creates a set of edges E from the reasoning relationships that involve formulas within NO. Line 3 constructs GO as the graph consisting of nodes NO and edges E. Line 4 initializes the Myerson values of all formulas in NO to zero. The algorithm proceeds to iteratively process each conflict set, designated by lines 5 to 14. Within this loop, line 6 extracts the relevant edges Ej for each confj, and line 7 constructs the subgraph G(confj) using the nodes in confj and edges Ej. Line 8 identifies the set of strongly connected components τ(G(confj)) in G(confj), which are crucial for computing the Myerson values. Lines 9 to 13 involve iterating through each component ϵ within τ(G(confj)), updating the Myerson value mi for each formula ϕi based on the cardinality of the component ϵ and the total number of components in τ(G(confj)). Finally, line 15 returns the dictionary M containing the Myerson values for all formulas.Algorithm 2 The Myerson value of Formulas in the Minimal Conflict Set.

Algorithm 2

The Myerson value provides a graph-based extension to the concept of the Shapley value by taking into account the strongly connected component of the graph to allocate values to each coalition. To accommodate the existence of strongly connected components, the value v(confj) is initially distributed equally among these components. The value is then equitably distributed among the formulas within these components. Particularly, in scenarios where GO be a directed complete graph, with |τ(G(confj))|=1, and |ϵ|=|confj|, the Myerson value Myϕi(NO,v,EO) aligns directly with the Shapley value Shϕi(NO,v). This equivalence is illustrated in Example 2.

Example 2 Consider the ontology O={ϕ1, ϕ2, ϕ3, ϕ4, ϕ5, ϕ6, ϕ7} in Example 1, and CONF(O)={{ϕ1, ϕ2, ϕ3}, {ϕ1, ϕ4, ϕ6}, {ϕ3, ϕ4, ϕ5, ϕ6}}. Calculated Shapley values are as follows:Sh(ϕ1)(NO,v)=23	Sh(ϕ2)(NO,v)=13	Sh(ϕ3)(NO,v)=712	
Sh(ϕ4)(NO,v)=712	Sh(ϕ5)(NO,v)=14	Sh(ϕ6)(NO,v)=712	

The directed graph GO=(V,E), with V={ϕ1, ϕ2, ϕ3, ϕ4, ϕ5, ϕ6}, and E= {<ϕ1,ϕ2>, <ϕ1,ϕ6>, <ϕ2,ϕ1>, <ϕ3,ϕ6>, <ϕ5,ϕ3>, <ϕ6,ϕ5>, <ϕ6,ϕ1>}, as shown in Fig. 1. We then calculate the Myerson value of each formula as follows:Figure 1 Illustration of the directed graphs utilized in Example 2, comprising GO (a) and its subgraphs (b).

Figure 1

My(ϕ1)(NO,v,EO)=12×2+12×2=12	My(ϕ2)(NO,v,EO)=12×2=14	
My(ϕ3)(NO,v,EO)=12×1+12×3=23	My(ϕ4)(NO,v,EO)=12×1+12×1=1	
My(ϕ5)(NO,v,EO)=12×3=16	My(ϕ6)(NO,v,EO)=12×2+12×3=512	

In a scenario where GO is a directed complete graph, each subgraph G(confj) also becomes complete. For instance, considering ϕ2 within conf1, which contains a strongly connected component of size three, Thus, My(ϕ2)(NO,v,E)=11×3=13, and which is equivalent to Sh(ϕ2)(NO,v).

3.3 Eliminating ontology contradiction based on the Myerson value

Classical methods for resolving logical contradictions in ontologies typically strive to minimize the number of formula deletions. Once the Myerson values for the formulas are computed, it is intuitive to eliminate those with the lowest values from the ontology's commonsense reasoning graph using a weighted ILP model. However, this direct approach does not guarantee that the resulting solution set contains the minimal number of formulas. Thus, we introduce a Myerson-weighted model that employs the lexicographic method, as outlined in Algorithm 3. To minimize redundancy, the results of Algorithm 2 serve as inputs for Algorithm 3.Algorithm 3 The Myerson Weighted Model based on Lexicographic Method.

Algorithm 3

Algorithm 3 constructs an ILP model to resolve ontological contradictions using a lexicographic method. Its primary objective is to minimize the number of formulas removed from the ontology, while its secondary objective focuses on removing formulas with the highest Myerson values. Lines 1 to 11 of Algorithm 3 mirror the process of Algorithm 1, constructing the ILP model to compute the solution set SILP with the goal of minimizing formula removal. Line 12 defines n as the count of elements in SILP that are assigned a value of 1, indicating the minimal number of formulas that need to be removed. Line 13 ensures that the cardinality of the final solution set does not exceed n. Line 14 integrates the Myerson values into the objective function as negative coefficients, aligning with the minimization goal. Lines 15 to 17 involve solving the ILP model to derive the final solution set S, where the formulas corresponding to decision variables set to 1 are selected as the resolution.

This method effectively addresses ontological contradictions by prioritizing minimal impact on the semantics of the ontology and leveraging the calculated Myerson values to guide the removal of less crucial formulas, thereby preserving the integrity and utility of the ontology.

4 Experiments

4.1 Experimental setting

The experiment was performed on a Windows 11 operating system, powered by an Intel(R) Core(TM) i7-13700K CPU. The development of the experimental software was conducted using Python 3.8. To construct the linear programming model for solving the ultimate solution set, we employed the Python library provided by CPLEX 20.1.0. NetworkX 2.8.4 was utilized to handle the graph-related operations. The ontology processing and computation of minimal conflict sets were facilitated using the OWL API,1 and computed the set using the ontology debugging algorithm based on correlation, as documented in [32]. The experimental code and datasets are publicly accessible via the website2 to ensure complete reproducibility.

4.2 Datasets and metrics

For empirical validation, we employed a collection of ontology datasets from [16], [33], [34]. Eighteen ontologies were selected for this study, chosen based on the dimensions of their formula sets and the complexity of their conflict sets, as detailed in Table 1. This selection was made without the deep semantic analysis of the ontologies. The column labeled Cardinality of Solution Set in Table 1 specifies the count of elements within the solution sets, reflecting our objective to minimize the number of deletions required for resolving contradictions.Table 1 Details of ontologies used in the experiments, the Formulas and Minimal Conflict Sets columns denote the corresponding quantities, and the Cardinality of Solution Set denotes the least number of formulas contained in the solution set of the ILP model.

Table 1Ontology	Formulas	Minimal	Cardinality of	
Conflict Sets	Solution Set	
Lily-cmt-conference	20	42	1	
Lily-edas-ekaw	35	28	4	
miniTambis	38	28	3	
Geography	41	31	9	
Wiktionary-cmt-confof	49	52	3	
proton	61	41	8	
VeeAlign-edas-iasted	36	91	2	
ALOD2Vec-confof-edas	26	118	1	
Economy	110	66	8	
Transportation	119	135	13	
LogMapLt-cocus-crs_dr	50	225	2	
Wiktionary-confof-edas	26	274	1	
MaasMatch-cmt-sigkdd	72	309	3	
MGED	131	334	3	
CHEM-A	57	412	1	
AROMA-cmt-cocus	94	535	4	
km1500-5000	99	1620	8	
km1500_i500-3500	811	17947	19	

The construction of relationships (edges) as elaborated in Section 3.2 relies on extensive prior knowledge of the specific tasks under investigation. In our experiments, we employed thirty random seeds for each ontology to produce directed graphs. Subsequently, we calculated averages to demonstrate the findings. Fig. 2 showcases an instance of a randomly generated graph that derives from the ontology. The left side of the figure portrays the entirety of the ontology, while the right side depicts subgraphs of the 9 minimal conflict sets.Figure 2 Illustration of the directed graph of an ontology used in the experiment. The edges of the graph represent the relationships of commonsense reasoning between formulas.

Figure 2

To demonstrate the advantages of the proposed Myerson weighted model, we use the ILP model by Ji et al. [16] (referred to as Algorithm 1) as a baseline for comparison. For clarity in presentation, we use the term CILP to denote the classical ILP model [16] and MILP for the Myerson weighted model in subsequent sections of the remaining part.

To quantitatively assess the impact of formula deletion on the structural integrity of the ontology graph, we introduce Eq. (6) to calculate the edge loss rate:(6) Edge Loss Rates=|EO|−|EO′||EO|

where |EO| denotes the total number of edges in the original ontology graph, while |EO′| indicates the number of edges remaining after formulas have been removed.

4.3 Results analysis

Table 2 illustrates the outcomes of logical contradiction elimination efforts using the CILP and MILP models across eighteen ontology datasets. To contextualize the size of each ontology, we include a column (NF/NMCS) that lists the number of ontology formulas alongside the count of minimal conflict sets. Additionally, the table incorporates an evaluation metric that measures the percentage of edge loss within the ontology graph, thereby quantifying the impacts of formula deletions from the solution sets. This metric is reported independently for both CILP and MILP. A lower percentage reflects better model performance in terms of preserving the integrity of the graph. The differential impact, expressed as the edge loss rate difference between CILP and MILP, is tabulated in the CILP-MILP column. Variations exceeding 3% are highlighted in bold to underscore significant performance discrepancies between the models.Table 2 Comparison of edge loss rates (%) after elimination of logical contradictions. Bold indicates a significant impact on the ontology, where the loss rate decreases by 3% or more. NF/NMCS correspond to the Number of Formulas and Minimal Conflict in the ontology, respectively.

Table 2Ontology	NF/NMCS	CILP (%)	MILP (%)	CILP - MILP	
Lily-cmt-conference	20/42	10.93	8.08	2.85	
Lily-edas-ekaw	35/28	29.47	22.86	6.61	
miniTambis	38/28	16.27	12.53	3.74	
Geography	41/31	50.97	40.60	10.37	
Wiktionary-cmt-confof	49/52	24.33	20.34	3.99	
proton	61/41	28.16	23.40	4.76	
VeeAlign-edas-iasted	36/91	15.32	13.08	2.24	
ALOD2Vec-confof-edas	26/118	8.63	8.63	0	
Economy	110/66	46.62	45.26	1.36	
Transportation	119/135	34.16	31.61	2.55	
LogMapLt-cocus-crs_dr	50/225	11.13	9.17	1.96	
Wiktionary-confof-edas	26/274	8.05	8.05	0	
MaasMatch-cmt-sigkdd	72/309	10.43	7.18	3.25	
MGED	131/334	19.16	18.99	0.17	
CHEM-A	57/412	9.28	8.46	0.82	
AROMA-cmt-cocus	94/535	13.23	8.28	4.95	
km1500-5000	99/1620	16.90	15.12	1.78	
km1500_i500-3500	811/17947	36.03	29.25	6.78	

In the experimental setup, to control for variability, we generated the ontology graph using 30 random seeds. The findings indicate that the MILP model outperforms CILP in terms of retaining more edges within the ontology graph following formula deletions, particularly noted in the cases of the Geography, Lily-edas-ekaw, and AROMA-cmt-cocus ontologies. The Myerson value computation, pivotal in this analysis, ensures equitable distribution of benefits across each strongly connected component of the graph. This process extends to individual formulas within those components, wherein formulas situated in parts of a minimal conflict set devoid of edges are assigned higher Myerson values. This characteristic of the Myerson value supports the preservation of more edges, substantiating the efficacy of this approach in maintaining the structural integrity of the ontology graph.

To effectively integrate the Myerson value into the objective function, the MILP model must initially identify the solution set of CILP and then impose additional constraints to optimize the minimization of the final solution set, a process known as the lexicographic method. Consequently, the computational duration for MILP typically doubles that of CILP. However, given the substantial advancements in efficiency CILP has demonstrated over tree-based methods in resolving logical contradictions, where solution sets for most ontologies are computed in milliseconds, the increased processing time required for MILP remains within a permissible range. Table 3 details the time consumed by both CILP and MILP, utilizing the same CPLex solver configuration.Table 3 Computational time consumption for CILP and MILP.

Table 3Ontology	CILP (ms)	MILP (ms)	
Lily-cmt-conference	8	13	
Lily-edas-ekaw	7	14	
miniTambis	6	9	
Geography	7	11	
Wiktionary-cmt-confof	10	18	
proton	9	14	
VeeAlign-edas-iasted	8	13	
ALOD2Vec-confof-edas	10	18	
Economy	7	16	
Transportation	9	18	
LogMapLt-cocus-crs_dr	15	33	
Wiktionary-confof-edas	16	28	
MaasMatch-cmt-sigkdd	16	39	
MGED	16	31	
CHEM-A	16	32	
AROMA-cmt-cocus	17	32	
km1500-5000	69	170	
km1500_i500-3500	615	1428	

5 Conclusion and discussion

This research advances the classical ILP model, which historically treated all formulas within ontologies as equally significant, by differentiating their contributions using theory from cooperative game theory. Specifically, we calculated the Shapley value for each formula based on its marginal contribution within minimal conflict sets. Furthermore, we employed commonsense reasoning to construct an ontology graph, extending our theoretical framework from Shapley values to Myerson values based on graph structures. Our proposed Myerson-weighted ILP model adheres to a lexicographic method, which prioritizes minimizing the removal of formulas and strategically utilizes Myerson values to guide the selection process. Our evaluation across 18 ontology datasets demonstrates that this enhanced approach enables the model to retain more structural edges of the ontology graph compared to traditional ILP methods.

There are limitations to this work. The computational process for deriving Shapley and Myerson values, while streamlined, does not simplify the inherently complex construction of formula-based graphs. This aspect of ontology engineering continues to require significant expertise to manage the intricacies involved in graph construction and to adhere to established graph construction standards. Additionally, while our model shows promise on medium-sized datasets, scaling this approach to larger ontologies typical in enterprise or internet environments presents considerable challenges. The complexity and dynamic nature of such large-scale ontologies frequently necessitate more sophisticated algorithms or parallel processing techniques to maintain practicality.

Future research should explore several promising directions. First, the development of automated tools could simplify the process of graph construction in large-scale ontologies, reducing the need for expert intervention. Second, the application of distributed computing frameworks for the computation of Myerson and Shapley values could improve the scalability of our methods. These frameworks would facilitate the handling of larger datasets by distributing computational loads across multiple nodes, potentially accommodating real-time updates and dynamic changes within ontology structures. Lastly, enhancing our model with adaptive algorithms that dynamically adjust parameters in response to changes in the ontology could provide a robust solution for maintaining logical consistency in dynamic environments.

CRediT authorship contribution statement

Juanyong Wu: Writing – review & editing, Writing – original draft, Methodology, Formal analysis, Data curation. Wei Peng: Writing – review & editing, Writing – original draft, Validation, Methodology, Investigation, Formal analysis, Data curation.

Declaration of Competing Interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Data availability

The code used to reproduce the results of the paper and the logs are accessed at this link:

https://github.com/Peng-weil/Eliminating_Contradictions_Myerson.

We declared data access and reproduction methods in ReadMe file.

1 http://owlapi.sourceforge.net/.

2 https://github.com/Peng-weil/Eliminating_Contradictions_Myerson.
==== Refs
References

1 Gruber T. Ontology Liu L. Özsu M.T. Encyclopedia of Database Systems 2009 Springer US New York 1963 1965
2 Antoniou G. van Harmelen F. Web ontology language: OWL Staab S. Studer R. Handbook on Ontologies 2009 Springer Berilin 91 110
3 Nilashi M. Ibrahim O. Bagherifard K. A recommender system based on collaborative filtering using ontology and dimensionality reduction techniques Expert Syst. Appl. 92 2018 507 520
4 Horridge M. Gonçalves R.S. Nyulas C.I. Tudorache T. Webprotégé M.A. Musen A cloud-based ontology editor Liu L. White R. World Wide Web Conference 2019 ACM New York 686 689
5 Gartina Husein I. Sitohang B. Akbar S. Azizah F.N. Comparisons of Diagnosis in Mapping Repair Systems, in: International Conference on Data and Software Engineering 2016 IEEE Piscataway 1 6
6 Qi G. Haase P. Huang Z. Ji Q. Pan J.Z. Völker J. A kernel revision operator for terminologies-algorithms and evaluation Sheth A.P. Staab S. Dean M. Paolucci M. Maynard D. Finin T.W. Thirunarayan K. International Semantic Web Conference vol. 5318 2008 Springer Berlin 419 434
7 Du J. Ranking diagnoses for inconsistent knowledge graphs by representation learning Ichise R. Lécué F. Kawamura T. Zhao D. Muggleton S.H. Kozaki K. Semantic Technology - 8th Joint International Conference vol. 11341 2018 Springer Berlin
8 Teymourlouie M. Zaeri A. Nematbakhsh M. Thimm M. Staab S. Detecting hidden errors in an ontology using contextual knowledge Expert Syst. Appl. 95 2018 312 323
9 de la Banda M.J.G. Stuckey P.J. Wazny J. Finding all minimal unsatisfiable subsets International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming 2003 ACM New York 32 43
10 Schlobach S. Cornet R. Non-standard reasoning services for the debugging of description logic terminologies Gottlob G. Walsh T. International Joint Conference on Artificial Intelligence vol. 3 2003 Morgan Kaufmann San Francisco 355 362
11 Kalyanpur A. Parsia B. Sirin E. Hendler J. Debugging unsatisfiable classes in owl ontologies J. Web Semant. 3 4 2005 268 293
12 Kalyanpur A. Parsia B. Horridge M. Sirin E. Finding all justifications of owl dl entailments Aberer K. Choi K. Noy N.F. Allemang D. Lee K. Nixon L.J.B. Golbeck J. Mika P. Maynard D. Mizoguchi R. Schreiber G. Cudré-Mauroux P. International Semantic Web Conference vol. 4825 2007 Springer Berlin 267 280
13 Reiter R. A theory of diagnosis from first principles Artif. Intell. 32 1 1987 57 95
14 Schlobach S. Diagnosing terminologies Veloso M.M. Kambhampati S. AAAI Conference on Artificial Intelligence 2005 AAAI Press Menlo Park 670 675
15 Kalyanpur A. Parsia B. Sirin E. Grau B.C. Repairing unsatisfiable concepts in OWL ontologies Sure Y. Domingue J. European Semantic Web Conference vol. 4011 2006 Springer Berlin 170 184
16 Ji Q. Boutouhami K. Qi G. Resolving logical contradictions in description logic ontologies based on integer linear programming IEEE Access 7 2019 71500 71510
17 Hunter A. Konieczny S. On the measure of conflicts: Shapley inconsistency values Artif. Intell. 174 14 2010 1007 1026
18 Shapley L.S. A value for n-person games Kuhn H. Tucker A. Contributions to the Theory of Games (AM-28) vol. II 1953 Princeton University Press Princeton 307 318
19 Deb K. Sindhya K. Hakanen J. Multi-Objective Optimization, in: Decision Sciences 2016 CRC Press 161 200
20 Jr J.N. Two-person cooperative games Essays on Game Theory 1996 Edward Elgar Publishing Massachusetts, United States 34 46
21 Zolezzi J.M. Rudnick H. Transmission cost allocation by cooperative games and coalition formation IEEE Trans. Power Syst. 17 4 2002 1008 1015
22 Ghorbani A. Zou J.Y. Data Shapley: equitable valuation of data for machine learning Chaudhuri K. Salakhutdinov R. International Conference on Machine Learning vol. 97 2019 PMLR New York 2242 2251
23 Peleg B. Sudhölter P. Introduction to the Theory of Cooperative Games 2007 Springer Science & Business Media Berlin, Heidelberg
24 West D.B. Introduction to Graph Theory 2001 Prentice Hall Upper Saddle River, Upper Saddle River, NJ
25 Horrocks I. Sattler U. Ontology reasoning in the SSHOQ (D) description logic Nebel B. International Joint Conference on Artificial Intelligence vol. 1 2001 Morgan Kaufmann San Francisco 199 204
26 Haase P. Völker J. Ontology learning and reasoning - dealing with uncertainty and inconsistency da Costa P.C.G. d'Amato C. Fanizzi N. Laskey K.B. Laskey K.J. Lukasiewicz T. Nickles M. Pool M. Uncertainty Reasoning for the Semantic Web I ISWC International Workshops vol. 5327 2008 Springer Berlin 366 384
27 Peñaloza R. Axiom pinpointing Cota G. Daquino M. Pozzato G.L. Applications and Practices in Ontology Design, Extraction, and Reasoning 2020 IOS Press Amsterdam 162 177
28 Qi G. Hunter A. Measuring incoherence in description logic-based ontologies Aberer K. Choi K. Noy N.F. Allemang D. Lee K. Nixon L.J.B. Golbeck J. Mika P. Maynard D. Mizoguchi R. Schreiber G. Cudré-Mauroux P. International Semantic Web Conference vol. 4825 2007 Springer Berlin 381 394
29 Schlobach S. Huang Z. Cornet R. Van Harmelen F. Debugging incoherent terminologies J. Autom. Reason. 39 2007 317 349
30 Haase P. van Harmelen F. Huang Z. Stuckenschmidt H. Sure Y. A framework for handling inconsistency in changing ontologies Gil Y. Motta E. Benjamins V.R. Musen M.A. International Semantic Web Conference vol. 3729 2005 Springer Berlin 353 367
31 Myerson R.B. Conference structures and fair allocation rules Int. J. Game Theory 9 1980 169 182
32 Ji Q. Qi G. Haase P. A relevance-directed algorithm for finding justifications of DL entailments Gómez-Pérez A. Yu Y. Ding Y. The Semantic Web vol. 5926 2009 Springer Berlin 306 320
33 Ji Q. Li W. Zhou S. Qi G. Li Y. Benchmark construction and experimental evaluations for incoherent ontologies Knowl.-Based Syst. 239 2022 108090
34 Ji Q. Qi G. Yang Y. Li W. Huang S. Huang Y. An embedding-based approach to repairing OWL ontologies Appl. Sci. 12 24 2022 12655
