The Tractability of Path-Based Inheritance

1 Introduction

Since the early semantic networks of Quillian (1968), in­ heritance hierarchies have been used to provide a com­ pact representation and efficient reasoning mechanism for certain kinds of taxonomic information. One prob­ lem that has plagued these systems is that of exceptions (or cancellation) in non-tree hierarchies. Early attempts to systematically deal with this issue, such as that of NETL (Fahlman 1979), were later shown to be unsound in the presence of redundant links and ambiguities (Re­ iter and Criscuolo 1983; Touretzky 1984). The first com­ prehensive definition that appeared to solve these prob­ lems was that of Touretzky (1984). Since then, other equally sound schemes have been proposed (Sandewall 1986; Horty et a/. 1987). But despite a decade of study, with increasingly subtle examples and counter-examples being considered, consensus has yet to emerge regarding the proper treatment of multiple inheritance with can­ cellations.

*Fellow of The Canadian Institute for Advanced Research.

From a knowledge representation standpoint, part of the problem is that there are tremendous subtleties in reasoning with propositions that admit exceptions, such as "Birds fly" (Brachman 1985). Not surprisingly, the research on inheritance systems mentioned above has not attempted to settle the larger logical and semanti­ cal issues associated with defeasible reasoning. Rather, the argument has been that inheritance systems need to conform to a set of special intuitions involving paths through hierarchies. We therefore call such systems path­ based inheritance systems and contrast them with the more general nonmonotonic reasoning systems (Reiter 1987). The latter approach attempts to establish a log­ ical account of defeasible reasoning (using, for example, autoepistemic, circumscriptive, conditional, or default logic), and somehow absorb hierarchies and inheritance as a special case. While the nonmonotoni<: systems tend to be more principled and semantically motivated on the whole, they have yet to be applied successfully to prob­ lems as intricate as those considered by the path-based approaches.

But if there are indeed irreducible intuitions about in­ heritance and paths through hierarchies, these intuitions are sometimes in conflict and can give rise to different inheritance systems (Touretzky et a/. 1987). How then to choose among the competing systems, especially since there is no independent semantic characterization that adequately covers the phenomena in question? While we do not claim to have an answer to this question, we do propose here a criterion that should be taken into account when comparing systems. What we will show is that there can be a significant difference in the com­ putational tractability of inheritance depending on fine points of the definition used. In other words, two ac­ counts of inheritance that cover by and large the same territory, differing only in certain complex cases, may nonetheless be quite different in their overall computa­ tional demands.

The main technical result of this paper is that the def­ inition of inheritance proposed by Touretzky 1 is inher­ ently NP-hard, and remains so even for totally acyclic unambiguous networks. Thus there cannot be an algo­ rithm that correctly determines if one node is inheritable from another that runs in time that is polynomial in the size of the network. 2 An immediate consequence of this is that the conditioning of a network, which Touretzky proposes to allow for fast parallel inference, is itself com­ putationally intractable. This suggests that a Touretzky inheritance procedure cannot run unsupervised, unless the network can be restricted in form or in size.

1 When speaking of "Touretzky's definition of inheritance" or "Touretzky's inheritance system," we are referring to the system defined in Touretzky (1984).

But the news is not all bad. We also show that there are plausible variants of the Touretzky definition that are indeed tractable. Among these is the definition proposed by Horty et al. (1987), who first exhibited a polynomial algorithm for computing inheritance. We extend this work and demonstrate which parts of the definition are responsible for making inheritance tractable.

Again, we do not wish to claim that the tractability of inheritance implies the correctness of the definition; but it is certainly one issue among many that needs to be taken into account in resolving differences among com­ peting accounts.

In the next section, we consider the precise definition of several forms of path-based inheritance. In the subse­ quent section, we examine the complexity of inheritance, and which combination of features in the definition affect the tractability of the associated reasoning. In the final section, we summarize our results and discuss directions for future research.

2 Path-Based Inheritance Systems

For our purposes, an inheritance network consists of a fi­ nite set N of objects called nodes denoted with lower-case letters x, y, z, and a set r of edges, defined as follows:

Definition: Edge

An edge is an element of N x {0, 1} x N, that is, any ordered pair of nodes and a 0-1 value called its polarity. Edges with a 0 are called negative and those with a 1 are called positive. We draw positive edges as x-+y and negative edges as x+y.

Intuitively, the nodes of a network are intended to stand for concepts or properties such as "bird," "pen­ guin," "Tweety," or "flies." Edges, on the other hand, stand for statements: A positive edge x-+y stands for the statement "an x is normally a y," while the corre­ sponding negative edge represents the statement "an x is normally not a y." 3 Path-based inheritance is concerned with the logic of statements of this type only. 4 The goal is to define what it means for a new edge x-+y to be inferrable from a given set of edges r. To do so, we use the notion of a path.

2 For the purpose of this paper, and to keep the provisos to a minimum, we assume that P;CNP.

3 ln the case where x is a property, instead of "an x," this should read "something with property x." This also applies to y as a property. When x denotes an individual concept, instead of "an x is normally," the phrase "x is" should be used. The case with y as an individual concept never arises.

4 Touretzky also defines "no-conclusion" edges. Such edges are not often used in practice, and therefore we will ignore them here in order to simplify our definitions. Note that these edges cannot decrease the complexity of the inheritance reasoning.

Definition: Path

A path is a sequence of edges from nodes x0 to x1 to ... to Xn-1 to Xn where n ~ 1 and the first n- 1 edges are positive. 5 The polarity of a path is the polarity of the final edge. The nodes xo and Xn are called the start point and end point of the path. The edge formed by taking the start and end points and the polarity of a path we call the conclusion supported by the path. We will let lower-case Greek letters stand for paths and draw them Xo-+X1-+ ... Xn·

It is tempting to define the set of edges that are in­ ferrable from a network r directly as the set of all con­ clusions supported by at least one path formed by edges in r . The complication is that a path may be invali­ dated in one of two ways: it may be contradicted by other paths (in which case neither path wins) or it may be preempted by a more specific path (in which case the more specific path wins).

For the following definitions, we will let ~ be any set of paths, u be any path xo-+X1-+ . . . Xn, and x be any node.

Definition: Contradiction

u is contradicted in ~ iff there is path in ~ with the same start and end points as u, but of opposite polarity.

So for example, the path xo-+x1-+x2 is contradicted by the path xo-+X3-+X4-+xs+x2 since the start and end points are the same but the final edge is of opposite polarity.

For preemption, the idea is that a path is preempted by an edge of opposite polarity from an intermediate of the path. We will consider two definitions of intermedi­ ate.

Definition: On-path intermediate

x is an on-path intermediate of u in ~ iff for some i ~ n, either x = x; or ~ contains a positive path 1 = xo-+ .. . --+Xi-1--+Yo--+ .. . -+ym-+X; with x = Yi for some j ~ m. (Note that u and 1 must be identical up to node x;_l-)

Definition: Off-path intermediate

x is an off-path intermediate of u in ~ iff there is a posi­ tive path 1 in~ from xo to Xn- 1 that contains x. (Note that u and 1 can be completely disjoint except for the nodes Xo and Xn-1·)

Definition: Preemption (off-path or on-path) u is preempted in ~ iff there is a node x that is an in­ termediate of u in ~' and an edge in ~ of the opposite polarity of u from x to Xn .

For example, consider the set of paths ~ {C-+re-+e, e-+g, re+g}, where C, re, e, and g respec­ tively denote "Clyde," "royal elephant," "elephant," and "gray." Figure 1(a) gives the underlying inheritance net­ work. (The figure contains an additional node Ae, which will be discussed below.) The path C-+re-+e-+g would be on-path preempted in ~ by the edge re+g, since re is an on-path intermediate of the path. 6 It would also be off-path preempted by the same edge. On the other hand, the path C___.Ae___.e___.g, where Ae denotes "African elephant," would only be off-path preempted in cl>.

5 So every edge in a network is a path.

Contradiction and preemption tell us how a path in a network may be invalidated. But once a path is inval­ idated, other paths that contain it may be invalidated also. So in determining inheritable paths, we must be sure to concatenate only those paths that have not been ruled out. As it turns out, there are two ways to con­ catenate paths.

Definition: Upward concatenation

u is an upward concatenation of paths in cl> iff the last edge of u is in cl> and the path consisting of all but the last edge of u is also in cl>.

Definition: Downward concatenation

u is a downward concatenation of paths in cl> iff the path consisting of all but the first edge of u is in cl> and the path consisting of all but the last edge of u is also in cl>.

The latter form of concatenation was originally called double chaining in Touretzky (1984). Here we opt for the more recent terminology used in Touretzky et al. (1987). The definition of inheritance based on upward concate­ nation that we will consider leads to so-called decoupled inheritance, as opposed to the coupled inheritance when using downward path concatenation.

To illustrate the difference between the two forms of concatenation, consider the following set of paths cl> = {J___.as___.a,as___.s+e,a___.e}, where J,as,s,a, and e respectively denote "Jill," "adult student," "student," "adult," and "employed." The underlying inheritance network is given in figure 1(b ). The path J ___.as___.a___.e can now be formed by upward path concatenation. This path supports the conclusion J ___.e, while as___.s+e in cl> supports as___.e. So, in this case, Jill and the class of adult students differ w.r.t. the property "employed." In general, when there is no coupling between the proper­ ties of a class and the properties of its superclasses, one speaks of decoupled inheritance. But with downward path concatenation the path J ___.as___.a___.e cannot be ob­ tained from the paths in cl>. To do so, one would also need as___.a___.e which, in fact, is contradicted in cl> by as___.s+e. So, in this case, there is a coupling between the properties that Jill can inherit and those inherited by the class of adult students.

6 Royal elephant is a subclass of elephant; therefore, in­ formation associated with it should override information as­ sociated with the elephant class. This is precisely what is captured by preemption.

We now define the inheritable paths.

Definition: Inheritable path (on-path and off-path, downward and upward) u is inheritable in cl> iff

• (a) u is a concatenation of paths in cl>;
• (b) u is not contradicted in cl>;
• (c) u is not preempted in cl>.

Intuitively, the paths that are inheritable in cl> are those that are inferrable from but not invalidated by cl>. But where does this set cl> come from? There are different ways of choosing a set cl>. We first consider Touretzky's definition of so called credulous inheritance reasoning. In this approach, cl> is chosen to be the least set of paths whose edges are those of r and closed under inheritance. We call such sets credulous grounded extensions. 7

Definition: Credulous grounded extension

cl> is a credulous grounded extension of a set of edges r iff

• (a) r ~ cl>;
• (b) For all u, u E cl> - r iff u is inheritable in cl>.

Unfortunately, there need not be a unique credulous grounded extension for a given set r' that is a network can be ambiguous. Inheritance reasoners allowing for multiple extensions, such as Touretzky's, are called cred­ ulous reasoners because they explore the various alter­ natives in different extensions. Instead of allowing for multiple extensions, Horty et a/. (1987) propose a form of skeptical inheritance in which at most one grounded extensiOn IS generated. In this form of inheritance a unique extension is inductively constructed by including paths that are inheritable only if a path with the same start and end point but of opposite polarity could not be inherited. The induction is based on the degree of a path:

Definition: Degree

Given a set of edges r, the degree of a path with start point x and end point y is the length of the longest path in f from X to y (ignoring the polarity of the edges).

Horty et al. restrict their definition of skeptical inher­ itance to acyclic networks:

Definition: Acyclic

A set of edges r is acyclic iff the graph formed by the elements of r is acyclic. 8

We can now state the definition of skeptical inheri­ tance as follows:

7 These were called grounded expansions in Touretzky (1984).

8 Touretzky (1984) speaks of totally acyclic, as distin­ guished from IS-A acyclic networks in which the graph formed by only the positive edges is required to be acyclic.

Definition: Skeptical grounded extension 4> is a skeptical grounded extension of a set of edges r iff 4> = u:l <jJ, where <jJ, is defined as follows:

• (a) </J1 = f;
• (b) <PHl contains the paths in <jJ, and each path u of degree i + 1 with the following properties:
• u can be obtained by concatenation of two paths in <jJ,; 9
• there neither exists an edge in <jJ, nor a path inheritable in <Pi with the same start and end point as u but of opposite polarity.

What we ultimately care about is the conclusions (that is, the edges defined by the start and end points) sup­ ported by the paths in a grounded extension of a net­ work. So, we define:

Definition: Conclusion set

A set of edges is a conclusion set for r iff for some grounded extension 4>, the edges are all the conclusions supported by the elements of <1> .

The inheritance problem, then, is this:

Definition: Inheritance problem

Given an acyclic network r, find a conclusion set of r .

Note that we are really talking about 8 inheritance problems here according to whether we consider off­ path or on-path preemption, upward or downward path concatenation, and skeptical or credulous reasoning. Touretzky's definition, for example, would be classified as on-path, downward, and credulous, while Horty's ver­ sion is off-path, upward, and skeptical.

We now consider the computational difficulty of the inheritance problem.

3 Computational Complexity

The following theorem shows that for Touretzky's inheri­ tance notion there is no polynomial algorithm that takes as input an acyclic network r and finds a conclusion set off.

Theorem 1 The inheritance problem for on-path, downward, credulous inheritance (Touretzky 1984) is NP-hard.

The proof of this theorem is based on a reduction from the NP-complete decision problem "path with forbidden pairs" (or PWFP) defined by Gabow, Maheshwari, and Osterweil (1976). An instance of PWFP consists of a directed gr.aph G = (V, E), specified vertices s, t E V, and a collection C = {(a1, b1), ... ,(an, bn)} of pairs of vertices from V . The question is: does there exist a path from s to t in G that contains at most one vertex from each pair inC? This problem remains NP-complete even if we only consider acyclic graphs and all pairs in C are disjoint . Consider an instance of this restricted version of PWFP. Without loss of generality, we may assume that each forbidden pair (a,, b,) is such that there does not exist a path from b, to a, in C.

9 The perhaps more natural condition "u is inheritable in 1/J;" leads to a different notion of skeptical inheritance. We use the condition given above for compatibility with Horty et al. (1987). Under this definition, the credulous grounded extension of an unambiguous inheritance network need not be identical to its skeptical grounded extension. (Selman and Levesque 1989).

We now construct an acyclic network r from this in­ stance of PWFP. First, we include every edge of G as a positive edge of f. Then for every node a that is the first element of a forbidden pair in c, we replace a in r by the network shown in figure 2. Figure 2(a) shows a node a from the forbidden pair (a, b) with all of its its neighbors in G, and 2(b) shows the structure in r that replaces a : two additional nodes (for a total of three) and n + 4 additional edges must be included, where n is the number of edges pointing to a in G. Note that of the three new nodes, the middle one a* is linked to b by a negative edge. Since G is acyclic and the forbidden pairs are such that there is no path from b, to a, for any pair inC, it follows that f is an acyclic network. Moreover, f is such that given an arbitrary on-path, downward, cred­ ulous conclusion set C of r, there is a path in G from s to t containing at most one vertex from each forbidden pair iff the conclusion s-+t is in C . 10

Now, consider an algorithm that takes as input an instance of PWFP, constructs (in polynomial time) an acyclic network r as outlined above, then finds an on­ path, downward, credulous conclusion set C of r, and, finally, returns "yes" if s-+t E C, and and "no" other­ wise. Such an algorithm returns "yes" iff there exists a path from s to t in G containing at most one. node from each forbidden pair; but if finding a conclusion set can be done in polynomial time, the overall algorithm will run in polynomial time. Since PWFP is NP-hard, the inheritance problem for on-path, downward, credulous reasoning must be NP-hard too.

The construction shown in figure 2 exploits vari­ ous properties of inheritance reasoning in general, and Touretzky's notion specifically. Firstly, we rely on pre­ emption since preemption prevents inheritance of a path from s to t going through a" and b (corresponding to a path through a and b in G) because of the negative edge between a* and b. 11 Secondly, we use quasi-redundant edges (Touretzky 1984, p. 10; Horty et al. 1987, Techn. Report, p. 21). The edge a 1 -+a 11 is an example of a quasi­ redundant edge, since this edge is strictly redundant for concluding a' -+a 11 ; however, to be able to conclude, for example, p1-+a 11 , the edge is essential (so it allows us to have a path from s to t through p1 and a" in a grounded extension, corresponding to a path from s to t via Pl and a in G) . Thirdly, the reduction relies on coupled inheritance; we will see below that decoupled (upward) reasoning allows for polynomial time inheritance.

10 We prove this property of f in Selman and Levesque (1989).

A direct consequence of theorem 1 is that the condi­ tioning of a network as proposed in Touretzky (1984), to enable fast parallel inference, is also intractable. Con­ ditioning is a process of adding edges to an inheritance network in such a way that a parallel marker-passing procedure can subsequently be used to draw conclusions in time proportional to the height of the inheritance net­ work.

We show in Selman and Levesque (1989) that the in­ heritance network r used in the above reduction is unam­ biguous. Thus, it follows that even when we restrict our­ selves to unambiguous acyclic networks the inheritance problem based on Touretzky's notion of inheritance is intractable. Note that it also follows that determining whether an unambiguous acyclic network supports a par­ ticular conclusion is NP-hard.

Recently, Geffner and Verma (1989) used a variation of our reduction to show that reasoning based on their definition of defeasible inheritance is NP-hard. Thus, the technique given above may prove to be useful in deter­ mining the complexity of future proposals for path-based inheritance reasoners.

We will now consider the influence of the various de­ sign choices made in Touretzky (1984; Horty et al. 1987) on the computational complexity of the inheritance rea­ soning. Our results are summarized in the following the­ orem:

Theorem 2 The computational complexity of the inher­ itance problem for the various choices between off-path or on-path, upward or downward path concatenation, and skeptical or credulous reasoning is given in the following table {P stands for doable in polynomial time):

Clearly the choice between off-path or on-path pre­ emption and between skeptical or credulous inheritance does not change the complexity of inheritance reason­ ing. However, when we consider upward (decoupled) in­ heritance, we do obtain tractability. The latter finding generalizes the tractability result obtained by Horty et al. (1987) for their off-path, upward, skeptical inheri­ tance reasoner. The NP-hardness results are proved by showing that the various design choices do not affect the correctness of the above reduction when dealing with downward path concatenation. Details are given in Sel­ man and Levesque (1989) which also contains polyno­ mial algorithms for the tractable cases.

11 Downward concatenation is also relevant here.

To summarize, theorem 2 clearly shows that the type of path concatenation (upward or downward) is the de­ termining factor in the complexity of the reasoning. This distinction corresponds to the difference between decou­ pled and coupled reasoning. It should be noted though, that in formalisms with substantially different definitions of preemption or grounded extension, other factors may also influence the complexity of the reasoning.

A further understanding of the complexity issues un­ derlying inheritance reasoning can be obtained by con­ sidering the polynomial algorithms for upward inheri­ tance. These algorithms iteratively construct a conclu­ sion set. The main difficulty in adding a new conclusion to the set arises from having to determine whether the path that supports this conclusion is preempted or not. So, we have to search for intermediates, which requires access to the set of paths in the underlying grounded ex­ tension. At worst, one would have to keep track of the full extension obtained so far (which can be of exponen­ tial size). But for upward inheritance it is sufficient to keep track of the current conclusion set, since one can rederive in polynomial time any particular path in the underlying extension, and thus, search for intermediates efficiently.

As a final topic, we will consider goal-directed inheri­ tance. Note that so far we have considered the complex­ ity of finding any arbitrary conclusion set given an inher­ itance hierarchy. In some situations, however, it might be wasteful to generate the entire conclusion set, and moreover, one might be interested in an extension that supports some particular conclusion (or set of conclu­ sions). We therefore define the problem of goal-directed inheritance reasoning: given an inheritance network r and a conclusion x-+y (or x+y), does there exists an extension of r supporting x-+y (or x+y)?

When a network is unambiguous or when skeptical rea­ soning is desired, the computational complexity of this inference task is essentially the same as that of search­ ing for a conclusion set, since, on the one hand, after finding the unique conclusion set, it a trivial to deter­ mine whether it contains a certain conclusion, and, on the other hand, after at most a polynomial number of queries, one can determine the conclusion set (for a net­ work containing n concepts one has to consider at most 2n(n- 1) possible conclusions). Moreover, our reduc­ tion from PWFP shows that goal-directed inheritance for on-path and off-path, credulous, downward inheri­ tance is NP-hard, just like the problem of finding an extension. (Consider the query: does the constructed network have an extension that supports the conclusion s-+t?) The following theorem, however, shows that goal­ directed reasoning is strictly more difficult than search­ ing for an arbitrary conclusion set: 12

12 Kautz and Selman {1989) show that goal-directed rea­ soning for default logic is also strictly harder than generating an arbitrary extension.

Theorem 3 Goal-directed, on-path, upward, credulous inheritance is NP-hard.

The proof of this theorem is again based on a reduc­ tion from PWFP (Selman and Levesque 1989). For this reduction, it is essential for the constructed network to be ambiguous. This theorem reveals some of the extra difficulties in inheritance reasoning due to ambiguities, although these difficulties do not arise when searching for an arbitrary conclusion set, as shown by theorem 2. The complexity of goal-directed, off-path, upward, credulous inheritance remains an open problem.

4 Conclusions

We have shown that path-based inheritance reasoning as defined in Touretzky (1984) is NP-hard, even when restricted to acyclic unambiguous networks. Moreover, the versions of this form of inheritance that use skeptical reasoning and off-path preemption are also intractable. Thus, while Touretzky (1984) showed that inheritance networks can be conditioned to allow for correct and efficient retrieval of information (time 0(/og(n)) for n concepts) such as in NETL (Fahlman 1979), our results demonstrate that this conditioning procedure itself is intractable when based on downward (coupled) inher­ itance. However, our other complexity results, gener­ alizing the tractability result obtained by Horty et a/. (1987), also suggest that the various forms of upward ( decoupled) inheritance can be used to achieve tractabil­ ity.

One possible direction for future research is to consider further restrictions on the form of inheritance networks that would allow for a polynomial inference mechanism based on downward inheritance. One candidate we have already begun to explore is inheritance restricted to com­ pletely balanced hierarchies. Such hierarchies have a maximum depth of 0(/og(n)), where n is the total num­ ber of concepts in the hierarchy. Such a restriction seems quite reasonable, given that taxonomic hierarchies will often be "shallow." However, we have found a reduc­ tion from the small-clique problem 13 to downward in­ heritance reasoning with such networks. This result in­ dicates that Touretzky's inheritance notion restricted to balanced hierarchies is most likely still intractable (i.e., not polynomial) . See Selman and Levesque (1989) for a more detailed discussion of these issues.

Acknowledgments

This work was supported in part by a Government of Ontario Scholarship to the first author, and a grant to the second from the Nat ural Sciences and Engineering Research Council of Canada. We would like to thank David Etherington for point­ ing out to us that the complexity of inferential distance was unknown. We also would like to thank Sue Becker, Jim des Rivieres, Russ Greiner, Jeff Horty, Gerhard Lakemeyer, Peter Patel-Schneider, Rich Thomason, David Touretzky, Wlodek Zadrozny, and . the anonymous referees for providing useful comments.

13 Given a graph G with n vertices, does G contain a clique of size log(n)? (Karchmer 1989; Megiddo and Vishkin 1988)