2.1 Conceptual vocabulary

The vocabulary is composed of two partially ordered sets: a set of concepts and a set of relations of any arity (the arity is the number of arguments of the relation). The partial order represents a specialization relation: t′ ≤ t is read as ‘t′ is a specialization of t’. If t and t′ are concepts, t′ ≤ t means that ‘every instance of the concept t′ is also an instance of the concept t’. If t and t′ are relations, then these relations have the same arity, say k, and t′ ≤ t means that ‘if t′ holds between k entities, then t also holds between these k entities’). Figures 1 and 2 show parts of these hierarchies visualized by their Hasse diagram (t′ ≤ t if there is a path from t′ up to t). For instance, the concept TeddyBear is a specialization of the concept Object, because of the path (TeddyBear, Toy, Object); the relation siblingOf is a specialization of the relation link₂ (which stands for any binary relation) because of the path (siblingOf, relativeOf, link₂). Note that a hierarchy is not necessarily a tree: for instance, there are two paths from Woman to Person, namely (Woman, Female, Person) and (Woman, Adult, Person).

Names of specific individuals can also be included in the vocabulary. The vocabulary can be further enriched by signatures for relations indicating the maximal concept that can be assigned to each of the relation arguments (e.g. the first argument of the relation motherOf is of maximal type Woman and its second argument is of maximal type Person). It can also contain statements of disjointness between concepts (e.g. the two types Object and Person are disjoint).

2.2 Basic graphs

A basic conceptual graph (BG) is a bipartite graph: one class of nodes, called concept nodes, represents entities and the other, called relation nodes, represents relationships between these entities or properties of them. For example, the BG in Figure 3 graphically represents the following situation: ‘The boy John is a sibling of the girl Eva. John is giving a sweet to Eva, who is holding a red teddy bear belonging to John’.

A concept node is labeled by a couple t : m where t is a concept (and more generally, a list of concepts) called the type of the node, and m is called the marker of this node: this marker is either the generic marker, denoted by *, if the node refers to an unspecified entity, otherwise this marker is a specific individual name. For example, in Figure 3 the node [Sweet:*] refers to ‘a’ sweet, while the node [Boy : John] refers to ‘the’ boy John. A relation node is labeled by a relation r called its type, and, if k is the arity of r, this node is incidental to k totally ordered edges. For example, in Figure 3 the relation node of ternary type give has three incidental edges and the order on these edges allows to distinguish between the agent of the gift act [Boy : John], its recipient [Girl : Eva] and its object [Sweet:*]. Classically, concept nodes are drawn as rectangles and relation nodes as ovals and the order on edges incidental to a k-ary relation node are numbered from 1 to k.

BGs are used to represent assertions called facts. They are also building blocks for more complex kinds of knowledge, as outlined in the next section.

2.3 More complex graphs

In the following we present two examples of BG extensions: nested graphs, which allow to structure facts by level of detail; and inference rules, which enrich the basic ontology with general knowledge about a domain.

Nested graphs. In a nested graph, a concept node may itself contain a (nested) graph, whose role is to further describe the entity represented by the node. This allows to distinguish between internal and external information about an object, to represent zooming into an object or to contextualize the description of an object. For instance, let us consider the nested graph in Figure 4. At the outermost level, this graph says that ‘Eva is giving a picture that she did to John’ (note, however, that time is not represented here) and the graph nested in the node referring to the picture further describes this picture: ‘this picture shows a boy holding a teddy bear’. The dotted line is a coreference link: it links two nodes that refer to the same entity (in this example the boy called John). The information that the picture has been done by Eva can be seen as an external information about the picture, while the detail of what is in the picture can be seen as an internal information, that can be obtained by zooming into the picture. It can also be said that the piece of information nested in a node is relevant within the context represented by this node (here, John is holding a teddy bear in the context of the picture, but it may not be true in the outermost context).

Figure 4

A nested graph

Rules. A rule expresses implicit knowledge of the form ‘if hypothesis then conclusion’, where hypothesis and conclusion are both basic graphs. This knowledge can be made explicit by applying the rule to a specific fact: intuitively, when the hypothesis graph is found in a fact, then the conclusion graph can be added to this fact (see Section 3.4 for more details). There is a one to one correspondence between some concept nodes in the hypothesis with concept nodes in the conclusion. Two nodes in correspondence refer to the same entity. These nodes are said to be connection nodes. For instance, Figures 5 and 6 present two rules, with the hypothesis on the left hand side and the conclusion on the right, separated by a vertical line. In Figure 5, rule R ₁ says that ‘if a person is a sibling of a person, then the inverse relation holds between these persons’. More formally: ‘for all persons x and y, if x is a sibling of y then y is a sibling of x’ (all concept nodes are connection nodes). In Figure 6, rule R ₂ says that ‘for all persons x and y, if x is a sibling of y, then they have a common parent, that is, there is a person who is a parent of x and of y’ (the node representing this person is not a connection node, since it is not in correspondence with a node in the hypothesis). Let us add that rules can also be defined as pairs of nested graphs instead of basic graphs.

Figure 5

A rule (R ₁)

Figure 6

Another rule (R ₂)

All these graphical objects, that is, the vocabulary as well as basic graphs, nested graphs and rules, are provided with a semantics in FOL. This semantics specifies the meaning of knowledge constructs and allows to show the correctness of the associated graph mechanisms with respect to logical deduction (see Section 3.3).

3.1 Generalization and specialization operations

There are five elementary generalization operations and five inverse operations, called elementary specialization operations. The terms generalization and specialization are used here with the following intuitive meaning: let I be a piece of information; whenever a piece of information is added to I, the obtained information is a specialization of I (it contains more specific knowledge) and, conversely, deleting a piece of information from I yields a final piece of information that is more general than I (it contains less precise knowledge).

3.1.1 Elementary generalization operations for BGs

Any generalization operation is a ‘unary’ operation, that is, it transforms a BG into another BG. It can be pictured by a drawing representing the transition from the input BG to the output BG. Generalization has to be taken in a broad sense, that is, the BG obtained may contain a strictly more general information than the initial BG or the same information.

The elementary generalization operations can be graphically defined as follows:

• • Substract (Figure 8). The substract operation consists of deleting some connected components of a BG. The BG obtained is clearly more general than (or equivalent to) the original BG, since a piece of information is deleted.

  Figure 8

  Substract

  

• • Detach (Figure 9). The Detach operation consists of splitting a concept node c into two concept nodes c ₁ and c ₂, the edges incident to c being shared between c ₁ and c ₂. For instance, let us consider the detachment of the generic concept node c in Figure 9. In the initial BG it is said that ‘there is a boy who possesses something and is giving something to a person’, and in the resulting BG it is said that ‘there is a boy who possesses something and there is a boy giving something to a person’. In the resulting BG, the two boys may be different, while in the initial BG it is necessarily the same boy. Therefore, the final situation is more general than the initial situation.

  Figure 9

  Detach

  

• • Increase (Figure 10). The Increase operation consists of increasing the label of a concept or relation node. In the case of a concept node, it means that one can increase its type, for example, replacing ‘the girl Eva’ by ‘the person Eva’ and/or replace an individual marker by the generic marker, for example, transforming ‘the person Eva’ into ‘a person’. Formally, the generic marker is considered as greater than all individual markers, which are pairwise non-comparable. Thus, increasing a concept node label consists of increasing its type and/or its marker. Clearly, ‘a person’ is more general (in an intuitive sense) than ‘the girl Eva’. In the same way, replacing a relation type by a greater type is also clearly a generalization operation, for example, ‘John is a relative of Eva’ is more general than ‘John is a sibling of Eva’.

  Figure 10

  Increase

  

  Let us remark that checking if a type t is greater than another type t′ is the most frequent operation in hierarchies. It is a basic operation (t is >t′ if and only if there is a path from t′ to t) for which efficient algorithms have been developed (cf. Chein & Mugnier, Reference Chein and Mugnier2009). In Figure 11, the bold paths contain all types greater than the type Boy.

  Figure 11

  Types greater than or equal to the type Boy

  

• • Relation duplicate (Figure 12). The Relation duplicate operation consists of duplicating a relation node, that is, adding a new relation node r′ having the same type and the same list of arguments as a relation node r. r and r′ are said to be twin relation nodes.

  Figure 12

  Duplicate

  

• • Copy (Figure 13). The Copy operation consists of duplicating a whole BG, that is, adding to it an isomorphic and disjoint copy of it.

  Figure 13

  Copy

  

In the last two operations, the structure of the obtained BG contains the structure of the initial BG (one adds something), thus, at first glance, one can think that they are specialization operations. Nevertheless, as these operations duplicate already existing information, the BG obtained is semantically equivalent to the initial one, thus they are also generalization operations (in a broad sense).

We can now precisely define what ‘G is a generalization of H’ means: G is a generalization of H if there is a sequence of elementary generalization operations leading from H to G, that is, there is a sequence of BGs $$\[--><$> {{H}_0}\, = \,(H),\,{{H}_1},\, \ldots, \,{{H}_n}\, = \,(G) <$><!--$$ , such that for all i = 1, …, n, H_i is obtained from H_{i − 1} by an elementary generalization operation.

Figures 14–18 present some of the graphs occurring in a generalization sequence from H, the BG in Figure 3 to G, the BG in Figure 7. H ₁ is obtained from H by splitting both nodes [Girl : Eva] and [Boy : John] (two Detach operations). H ₂ is obtained from H ₁ by deleting the connected component containing the give relation node (Substract operation). H ₃ is obtained from H ₂ by duplicating the relation node color (Relation duplicate operation). H ₄ is obtained from H ₃ by a Detach operation on the node [TeddyBear:*]. G is obtained from H ₄ by a sequence of seven Increase operations: the relation siblindOf is replaced by relativeOf, the relations possess and hold are replaced by link2; the individual concept nodes [Boy : John] and [Girl : Eva] are made generic, and the teddy bears become toys.

Figure 14

Generalization from H to G—step I (H ₁)

Figure 15

Generalization from H to G—step II (H ₂)

Figure 16

Generalization from H to G—step III (H ₃)

Figure 17

Generalization from H to G—step IV (H ₄)

Figure 18

Generalization from H to G—step V (G)

3.2 Homomorphism

We have seen specialization operations, which are more convenient than generalization operations when considering the query-answering problem. Now, the problem is how to find a sequence of specialization operations from a BG to another BG.

In this section, we introduce the homomorphism notion between BGs. A homomorphism from G to H is a mapping from the node set of G to the node set of H, which preserves the adjacency between nodes of G and can decrease the node labels. If there is a homomorphism (say π) from G to H, we say that G maps to H (by π).

Let us consider again the query G in Figure 7 and the fact H in Figure 3. There is a homomorphism from G to H, which is pictured by the dashed lines in Figure 23. The concept node a = [Boy:*] in G is mapped to [Boy : John] in H, the concept node b = [Girl:*] in G is mapped to [Girl : Eva] in H, both concept nodes c = [Toy:*] and d = [Toy:*] in G are mapped to the same node [TeddyBear:*] in H, the concept node e = [Color : Red] in G is mapped to [Color : Red] in H, the relation node (relativeOf) is mapped to the relation node (siblingOf), the relation node (link2) from a to c is mapped to the relation node (possess) and the other relation node (link2) from b to d is mapped to the relation node (hold); finally, both relation nodes (color) are mapped to the same node (color).

Figure 23

A homomorphism from G to H

A BG homomorphism can be more precisely defined as follows. A homomorphism π from G to H is a mapping from the concept node set of G to the concept node set of H and from the relation node set of G to the relation node set of H, which preserves edges and may decrease concept and relation labels, that is:

• • for any edge labeled i between nodes c and r in G, there is an edge labeled i between nodes π(c) and π(r) in H; in other words, if a relation r has neighbors c ₁ … c_k (in this order) then its image π(r) has neighbors $$\[--><$> \pi ({{c}_1})\, \ldots \,\pi ({{c}_k}) <$><!--$$ (in this order).

• • for any (concept or relation) node x in G, the label of its image π (r) in H is less than or equal to the label of x.

Let us consider again the homomorphism in Figure 23. Figure 24 highlights the subgraph of H induced by the nodes that are images of nodes in G. This subgraph is called the ‘image graph’ of G by this homomorphism.

Figure 24

Image of G by the homomorphism in Figure 23

The following theorem holds. Given two BGs G and H, the three following propositions are equivalent:

1. 1. G is a generalization of H

2. 2. H is a specialization of G

3. 3. There is a homomorphism from G to H

Even though it is easy to visualize a homomorphism and to check if a mapping between two BGs is a homomorphism (cf. Figure 23), this global graph matching can be replaced, if needed, for more detailed explanation purposes, by a sequence of elementary operations (cf. Figures 14–18). Assume for instance that the answer to the query G is visualized as in Figure 24 and the user wants to understand why the image graph of G is indeed a specialization of G. The homomorphism can be decomposed into a sequence of elementary specialization operations, starting from G, as follows:

• • First, a sequence of Restrict showing how the label of each node of G is specialized (cf. the transformation from G to H ₄);

• • Second, a sequence of Join showing which concept nodes are merged into the same node (these are the nodes in G with the same image by the homomorphism, cf. the transformation from H ₄ to H ₃);

• • Third, a sequence of Relation simplify removing relation nodes that have become redundant (cf. the transformation from H ₃ to H ₂).

After these three steps, the image graph of G is obtained, which is sufficient to show that the fact contains a specialization of G. To build the fact graph itself from the image graph of G, one would need a disjoint sum (cf. the transformation from H ₂ to H ₁) and some joins (cf. the transformation from H ₁ to H).

3.3 Logical correctness

Until now, we have introduced the reasoning operations (generalization, specialization and subsumption) using simple graphical operations. It remains to relate these notions to usual reasoning notions, that is, essentially, to relate BG subsumption to logical deduction. This can be done using the logical semantics of the knowledge constructs. This semantics is defined by a mapping from graphical objects to logical formulas. It is classically denoted by Φ in conceptual graphs (Sowa, Reference Sowa1984). The fundamental theorem states that given two BGs G and H built on a vocabulary $$\[--><$> {\cal V} <$><!--$$ , there is a homomorphism from G to H if and only if Φ(G) is a semantic consequence of Φ(H) and $$\[--><$> \rPhi ({\cal V}) <$><!--$$ (this is a soundness and completeness theorem of BG homomorphism w.r.t. FOL entailment, cf. Chein and Mugnier (Reference Chein and Mugnier1992)). Let us point out that BGs are in fact equivalent to the positive, conjunctive and existential fragment of FOL.

Once again, logic is used to give a semantics to BGs, but not to reason with them. As detailed before, one motivation for preferring graph-based reasoning is its visual aspects permitting to understand (logically based) reasoning without doing logic. Another motivation is that BGs have good computational properties. Efficient graph-based deduction algorithms have been built, which are not the translations of logical procedures (see f.i. Chein & Mugnier, Reference Chein and Mugnier2009).

3.4 Overview of reasoning on more complex pieces of knowledge

Previous generalization and specialization elementary operations, as well as the corresponding homomorphism notion, can be extended to nested graphs, while preserving soundness and completeness with respect to deduction in the associated fragment of FOL.

Let us now consider the graph rules presented in Section 2. A rule R can be applied to a BG H, if there is a homomorphism from its hypothesis to H. Applying R to H according to such a homomorphism π consists of ‘attaching’ to H the conclusion of R by merging each connection node in the conclusion with the image by π of the corresponding connection node in the hypothesis. See for instance the graph H in Figure 3 and the rules R ₁ and R ₂ in Figures 5 and 6. There is a homomorphism from the hypothesis of R ₁ to H, thus R ₁ can be applied to H, which yields the graph K (Figure 25). Similarly, R ₂ can be applied to H, or to K. Let us apply R ₂ to K: we obtain L (Figure 25). R ₂ can be applied another time with a new homomorphism to L: however, this application would be redundant, since the part to be added is already present in L.

Figure 25

Applying rules

When a KB contains a set of facts and a set of rules, the query mechanism has to take implicit knowledge coded in rules into account. The KB answers a query Q if a BG F′ can be derived from the facts using the rules, such that Q maps to F′. Let us consider again the fact H in Figure 3 and the rules R ₁ and R ₂ in Figures 5 and 6 and let Q be the query in Figure 26 asking if there is someone who is parent of a boy and a girl: there is no homomorphism from Q to H; however, the KB containing H and the rules R ₁ and R ₂ answers Q: indeed Q maps to L (Figure 25), which is derived from H by applying the rules. This reasoning can be explained by visualizing a homomorphism from Q to L, as well as a sequence of rule applications allowing to add the knowledge involved in this homomorphism (for instance, the application of R ₁ is not needed in our example).

Figure 26

Another query example

Finally, let us point out that this rule application mechanism is sound and complete, that is, given a KB $$\[--><$> {\cal K} <$><!--$$ and a BG Q, Q maps to a graph derived from $$\[--><$> {\cal K} <$><!--$$ if and only if $$\[--><$> \rPhi ({\cal K})\, \models \,\rPhi (Q) <$><!--$$ , where $$\[--><$> \Phi ({\cal K}) <$><!--$$ is the set of formulas assigned to the vocabulary, the set of facts and the set of rules composing $$\[--><$> {\cal K} <$><!--$$ .