An Abduction-based Method for Explaining Non-entailments of Semantic Matching

This submission discusses an approach to generating "explanations" for non-entailments in ontologies, where an "explanation" is understood as a set of axioms that would suffice for generating the entailment in question if added to the ontology.

I am not convinced that this notion matches particularly well with what is commonly understood as an "explanation" - it seems to me that even a simple counterexample to the failed entailment would have better explanatory power - but nonetheless, the question of what needs to be added to an ontology to recover failed entailments in semantic matchings between ontologies is interesting and important.

The approach proposed by the authors consists, in brief, in comparing the semantic trees of the two terms appearing in the desired entailment and trying to find a subtree isomorphism between them by matching nodes between the two trees, as far from the roots as possible; and, afterwards, in generating axioms between the corresponding subterms. This makes intuitive sense, since it is equivalent to trying to add axioms involving sub-concepts that are as simple as possible. The authors also implement their algorithm and provide a brief analysis of its performance.

I think that the overall idea discussed in this paper is sound and interesting enough to warrant publication. However, I also think that some of the technical details could be better explained and that the presentation could also be substantially improved.

More detailed comments follow:

* The definition of "Rooted Trees" at the begining of Section 3.2 at page 5 lacks the tree condition: it must be stated that the graph is connected and acyclic.
* The phrasing of the conditions for lambda_V and lambda_E at Page 8, lines 1-2 is incorrect. If I understand it correctly, it's not that for any v in V and any I_V in L_V, lambda_V(v) = I_V and I_V is a subset of N_C (this would be impossible unless L_V is a singleton), but rather that for any v in V, lambda_V(v) is a subset of N_C. likewise for lambda_E in the next line.
* In Definition 10, at the end of page 8/beginning of page 9, saying that "one of the following holds" and that listing the three conditions is unclear: it's not that an arbitrary one of them must be satisfied, it really depends on what kind of entailment/equivalence we are trying to get. Why not talk instead of three *types* of T-isomorphism (for exampe type \sqsubseteq, \sqsupseteq, \equiv) corresponding to thre three conditions?
* The proof by induction of Theorem 1 is by structural induction on what? On the depth of T_C, on the depth of T_D, on the maximum between the two? Also, it should be stated at the beginning of the proof - not at the end - that we are examining the case of C \equiv D, and that the other two are analogous.
* How, precisely, is the hypothesis H at the end of Example 1 (line 51 at page 9) found given the isomorphism \phi? Intuitively I see it, but I don't find a formal definition on how to go from \phi to H.
* Definition 12 at page 11: same issue as for Definition 10 above - wouldn't it be better to talk about three classes of weak isomorphism?
* Page 12, line 17: The reference to "Point 3" is not clear here, since it's quite a few pages after it was mentioned in Page 7. I would suggest rephrasing it for clarity.
* Page 13, in the statement of Theorem 2 (line 35): don't the condition " \in E, \in E" follow at once from the assumption that x,y \in N(v)?
* Page 14, equation (18) on line 35: I don't think that this definition quite works. When |[x]| <= |[y]| we pick the set of the injections from [y] to [x], otherwise we pick the set of the injections from [x] to [y], and we let I(v,w) be the set of all these injections (for <[x], [y]> \in \mu(v,w)); and M(u,v) be the union of all the components of I(v,w). Then M(u,v) will contain some tuples in which the first component is in [x] and the second is in [y], where <[x],[y]> \in \mu, and some other tuples in which the first component was in [y'] and the second was in [x'] for some other <[x'], [y']> \in \mu; but later on, for example on line 38 of page 15, we seem to assume that every m in M is of the form where x is in [x] and y is in [y] for <[x], [y]> \in \mu…
* Page 14, line 48, equation (20): I think it was meant lambda(\phi) \subseteq {\langle v, w\rangle | v \in V_1, w \in V_2}: with the equality sign as written, we would label every node with *all* the pairs of nodes from V1 and nodes from V2, and I don't think that's what is intended.
* Page 15, lines 7-12: I understand the intended meaning, but rule B1 as stated would fixes entirely T_\Phi (and contradicts rule R1 afterwards). One should could simply say that \phi_0 is a node of T_\Phi and \lambda(\phi_0) is as given.
* Page 15, Claim 1: Both the statement and the proof are a little messy. P(\phi) is the statement that we are trying to prove by structural induction, and says that \phi is a weak isomorphism between T1[S1] to T2[S2], where S1 and S2 are what? From the context and from reading the proof I can understand it, but it should be stated more clearly, i.e. with something like "For all \phi \in \Phi, the following proposition P(\phi) is true: "there exist S1 and S2 such that \phi is a weak isomorphism between T1[S1] and T2[S2], …" The proof is by structural induction, but on what precisely? The induction step starts assumeing that P(\phi) is true for T1[S1] and T2[S2], picks some m \in M(v,w) (what are v and w here? is it the same as v0 in T1[S1] and T2[S2]?) and concludes that P(\phi \cup \{\m\}) is true, so it would seem that we are proving that P is true starting from the root \phi_0 and going towards the Leaves of the tree; but this entire proof should be rewritten in a more systematic and readable way.
* Regarding the implementation as a whole, can you say something about scalability? One gets the impression that the size of the M(v,w) can increase pretty badly for complex concepts…
* Page 18, line 23: the brakets are misplaced in the expressions for \mu(v0, w0)
* Page 21, line 7: "Concept descriptions were generated randomly" - randomly how?
* Page 21, line 31: "discription tree" - "description tree"
* Page 22, Fig. 4: some more discussion of these results in the text could be useful, in particular for the middle graphs (the ones plotting b1/b2 against the number of hypotheses). Also, the Jaccard index is defined in Equation (29) before, and from the graph labels it would seem that the bottom line of plots shows how this relates to the number of hypotheses; but the caption does not state that outright.
* More in general, I think that this submission would greatly benefit from a more rigorous statistical analysis of the performance of the algorithm.

The paper proposes a new approach for finding explanations for non-entailments with the help of subtree-isomorphisms.
The paper is mostly well written, the approach seems to be novel and an interesting extension of given approaches, the theoretical results are proven, and the approach is implemented and tested, and the implementation is provided in a long-term accessible and well-structured format.
1) However, the experiments are not totally convincing: As mentioned in the introduction, the explanation of non-entailment is an actual problem, therefore, it would have been nice to see the approach applied to real world datasets, as randomly generated concepts not necessarily resemble actual non-entailment problems. Even if there isn't any large dataset available, a qualitative analysis of some examples would have been interesting. Additionally, a comparison to the other approaches would have been helpful. Of course, they are restricted in their expressivity, however, e.g., [16] can also consider roles but only on predefined patterns. Does the variability of the proposed approach actually lead to an advantage over the predefined patterns of [16]?
2) In the experiments, the Tbox is considered to be empty, however, normally, there is some Tbox information given. How is this information incorporated into the process? Especially, what happens if the concepts considered are enhanced with the Tbox information beforehand? (e.g. when $C \sqsubseteq \exists R.D$ is considered as entailment problem, however, the Tbox contains the information that $C=\exists R.A$?) This should considerably change the outcome of the hypothesis generation process.
3) The theoretical part needs more explanations on an intuitive level, particularly regarding the definitions and theorems, e.g., the T-isomorphism or the role of mu (16), (17) and the creation of M(v,w).
4) As subtree-isomorphisms are a fundamental problem, there should be more comparison to other approaches and a thorough explanation of what this approach differentiates from other subtree-isomorphism approaches.

Minor comments:
- Definition 9: epsilon_D instead of epsilon_2
- Definiton 10: v_D(w) instead of v_C(w)
- (17): What does Xi mean?
- p.19, l.6: "abductive"
- the introduction is mainly focused on semantic matching, only a small part considers non-entailment. Here, the focus should be changed to the non-entailment.
- p.7: Points 1-3 should be explained in more detail directly after mentioning them. Though it will get clear during the section, it would be helpful to have an explanation beforehand.
- in (9): is it really meant v_i in V, and not v_j in N(v_i)?
- Definition 10 and Definition 12: v and w are two times quantified, one time in the text and another time in the formula.
- p. 10, l.34: what is meant with "consist mainly of role restrictions"?
- Observation 2 should be formalized

The paper presents a method for explaining missing subsumption relationships,
with a proposed application for semantic matching.

The problem that the paper is concerned about is following:
we are given an ontology (in the context of the
paper: a TBox) and some desired subsumption
relationship between concepts which
is not derivable through logical reasoning, and we want to compute a
set of concept inclusions that, when added to the TBox, would make
the subsumption relationship entailed.
The authors solve this problem via a new notion of abduction,
which is based on previous notions, but extended to deal with
more complex expressions in the solutions. The authors
motivate their work with semantic matching, and present also a
practical algorithm for computing their
abduction results in practice, which has been implemented and
evaluated on randomly generated data.

I think this is a relevant problem which might indeed find use cases
in matching, and I also like the new idea for abduction. However,
the paper is not good enough for a publication
at an international journal. There are issues in the presentation that
are below the standards of the journal. The contribution of the paper
is limited, and the setup of the experiments can be
improved. Finally, the whole story of the paper as supporting semantic
matching is not really convincing - from the view point of the paper,
semantic matching is essentially made equivalent to subsumption.

** The main contribution

The specific type of abduction the authors investigate is based on
the notion of "connection-minimal abduction" introduced in [15].
The idea can be roughly described as follows: we want to find out how
to establish a subsumption relationships between two concepts C1 and
C2. For this, we construct description trees for these concepts that
capture respectively a concept that subsumes C1, and one that is
subsumed by C2. Such a description tree shows the (tree-)structure of the
concepts, where nodes represent elements with concept names as labels,
and edges represent the role-relations. If C1 is not subsumed by C2,
the two trees must be necessarily different, but we might be able to
find a partial match that links the nodes of one tree to the other.
Based on this match, we can determine what is missing to make one tree
subsume the other, and construct the axioms that need to be added to
the ontology in order to make the desired subsumption hold. In [15],
the description trees have to be essentially identical except for the
node labeling, which leads to solutions which always relate
intersections of concept names, but never involve role
restrictions. The present paper extends the approach by also allowing for
situations where role-successors would need to be added, which means
that also solutions are produced in which role restrictions are used,
essentially allowing the full expressivity of EL in the solutions.
This makes this approach strictly more powerful than the original
approach in [15]. The authors do not only introduce this new
type of abduction, they also describe how to compute abductive
solutions in this setting, and evaluate an implementation.

** Semantic Matching

The title indicates that this is also a paper about semantic matching. Yet
the paper is quite late at explaining what the authors
actually understand as semantic matching. The introduction
provides pointers to the literature to semantic matching (Page 2,
Line 18), but without explaining what the problem is, and why it is
relevant. In fact this list of literature references comes quite
unexpected and is a bit confusing at this point. On Page 6, one then
finally gets a formal definition, but it is a bit strange:

"semantic matching determines whether two concepts are semantically
similar (or compatible) w.r.t. some background knowledge, if their
intersection is satisfiable."

Indeed this is how the first type of matches are defined
(Definition 5 on the same page): two concepts match if their
intersection is satisfiable. This is not particularly strong,
since then almost everything in an ontology will be
"similar" in that sense. Luckily, Definition 6 then provides different
types of semantic matches (those of "higher degree"), but these types
just correspond to the different subsumption relationships that can
hold between two concepts.

(A side-note on Definition 6: since these 3
types of (positive and negative) have different names in your paper
("exact", "plugin", "subsume"), it would be good to put these names
next to the corresponding cases, so that one directly understands what
they mean.)

It seems to me that the crux of semantic matching is that one wants
to find candidates for semantic matches: given a concept C1,
give me concepts that match C1 according to some of the notions. The
setting in the paper is quite different: here we are given C1 and C2
that do not match, and we want to understand how to make them match.
But since the only relevant type of matching just corresponds to
classical subsumption, I do not see a reason for talking about
semantic matching at all.

** Experimental Setup

Experiments are called "simulations" by the authors. As
experimental data, the authors use empty TBoxes and
randomly created concept expressions. There are two issues with
this setup:

1) it does not give any idea on how the method would perform on real
data,
2) it limits reproducability, since the authors remain vague in the
paper on how they exactly create the concepts,
3) since the authors create the data themselves, some readers might
worry that the data has been tailored to make the experiment
succeed.

There is a range of realistic ontologies and ontology-benchmarks that
are freely available on the web, already packaged ready to use on
Zenodo: BioPortal, MOWLCorp or the ORE competition benchmarks, to give
some popular examples. Moreover, I had a look and the paper in [15],
which forms the basis of the present method, actually provides their
evaluation data also on Zenodo - it would therefore have been easy to
just use it as well, to at least get an idea on how the two method
compare. Interesting questions would for instance have been: how often
does the present approach find a solution where the original approach
in [15] doesn't? Do solutions look more reasonable, or are they more
concise? How do the approaches compare in terms of efficiency?
Finally, the benchmark used in [15] is based on realistic ontologies,
and not on randomly generated concepts.

As a result, the evaluation does not really give that useful insights.

** Presentation

The presentation is sometimes sloppy. To give some examples:
- symbolic AI is sometimes written capitalized (e.g. Page 1, Line 46) and sometimes in
lower case (e.g. Page 1, Line 41),
- "TBox" is sometimes written "Tbox" (e.g. Page 1, Line 19)
- The graphs in Fig. 1+2 are pixel graphics with low resolution and
look fuzzy, when they should clearly be vector graphics (in latex
one can for instance include pictures in eps format)
- The caption of Algorithm 1 (page 20), has a weird layout and is hard
to read - apparently the authors put text into a math environment

There are definitions that often incomplete or do not work well: when
trees are introduced (Page 5, Lines 24-28), they are just introduced
as graphs - the basic propery of being a tree (e.g. no cycles, one
root, no node with two incoming edges) are not mentioned. On Page 6,
Definitions 2 and 3 then define edge-labeled and node-labeled trees
separately (as 4-tuples, where labeling functions that have a disjoint
domain), when later, trees that are both edge and node labeled are used,
now as 5-tuples that have two labeling functions (Page 7, Definition 8).
This is not how it works: you should have one definition where you
directly define labeled trees with the complete labeling function,
exactly in the way you use it later.

In general, the authors do not know well how definitions are written.
Take for example Definition 3 (Page 6):

"A rooted tree T = is called node labeled if
there exists a labeling lambda_V:V\mapsto L_V"

- "there exists" is not needed here - lambda_V is part of the tree!
- "\mapsto" should be "\rightarrow"

"[..] which maps all nodes to labels in a set of node labels L_V, such
that for any v_i\in V and l_v\in L_V, if v_i is mapped to l_V, then
lambda_V(v_i)=l_V"

- what follows after "such that" is just the usual mathematical
notions for functions - there is no need to mention that in a
paper, especially not in a definition.

The description of the algorithms (there are seven algorithm
environments in total in the paper, the appendix just consists of six
of them) is too low-level and detailed - some of it is pretty
straight-forward or standard and does not need to be described at this
level of detail, others could be more clearly and concisely described
using mathematical notations (see for example Algorithm 2 an 3).

To conclude, even if the paper was better in terms of motivation,
contribution and evaluation, the presentation would make it hard to
access the quality of the results, and is in anyway not up to the
standards of an international journal paper.

* Long-term Stable Link to Resources

The authors provide a link to a github repository, which contains a
zip-file with the code needed to run the implementation and
reproduce the experiments. Using a zip-file is not really optimal
(better and more convenient would be to put the source code directly).
It is good to see that maven is used for dependency management, which
facilitates compiling the projects on different machines.

The readme reads a bit strange:
"To run the experiments open the workbench folder in a new Maven Project.
Next, open the Experiments.java class. Build the project. Provided that
all the necessary dependencies are installed, the algorithm will ask for [..]"

Usually one would assume which dependencies need to be installed on a machine
and how to compile and run everything from command line. The present description
seems to assume some IDE to be used, which is unusual and less convenient for
reproducing experiments. Class name would be "Experiments" not "Experiments.java",
and necessary dependencies should be automatically installed by maven (that is
the whole point of using maven). I did not try to compile and run the code myself,
as it was already clear at this point to me that the paper cannot be excepted.