Lecture 5. Conceptual Graphs

The canonical formation rules are specialisation rules.
Restriction specialises a concept [ANIMAL] to [DOG].

Join

Copy

simplification

Specialisation does not preserve truth.
Example: If the girl Sue is eating pie fast, then it must be true that some girl is eating fast and that the person Sue is eating pie.
Unfortunately, generalisation does not necessarily preserve selectional constraints.
If the girl Sue is eating pie, it follows that some entity is eating some entity, but the graph

[ENTITY] <- (AGNT) <-[EAT] -> (OBJ) -> [ENTITY]

does not include the constraints expected for the concept [EAT].

Thus, generalisation are not canonical.
3.5.1 Definition If a conceptual graph u is canonically derivable from a conceptual graph v (possibly with the join of other conceptual graphs w₁,...,w_n), then u is called a specialisation of v, written u £ v, and v is called a generalisation of u.
3.5.2 Theorem generalisation defined a partial ordering of conceptual graphs called the generalisation hierarch. For any conceptual graphs u, v, and w, the following properties are true:

Reflexive u £ u
Transitive if u £ v and v £ w, then u £ w
Antisymmetric if u £ v and v £ u, then u = v
Subgraph if v is a subgraph of u, then u £ v.
Subtypes if u is identical to v except that one or more type labels of v are restricted to subtypes in u, then u £ v.
Individuals if u is identical to v except that one or more generic concepts of v are restricted to individual concepts of the same type, then u £ v.
Top the graph [T] is a generalisation of all other conceptual graphs.

Proof.

Since u is canonically derivable from itself by the copy rule u £ u.
If u is canonically derivable from v and v is canonically derivable from w, then u must be canonically derivable from w; therefore u £ w.
If u is canonically derivable form v and v is canonically derivable from u, the only way they could have been derived is by copy; therefore, they must be identical.
If v is a subgraph of u, then u must be canonically derivable from v by joining the other parts of u that are not included in v; therefore, u £ v.
If u is derived from v by restricting type labels to subtypes or generic concepts to individual, then u is canonically derivable from v; therefore, u £ v.
Any graph u can be canonically derived from [T] (plus some other graph) simply by letting the other graph be u itself; then restrict [T] to the type and referent of any concept c in u and join it to c.

If the graph u is a specialisation of v, whenever u represents a true situation, v must also represent a true situation.

inferences on conceptual graphs (Chapter 4); or
by the use of the operator f; if u £ v, a canonical derivation of u from v corresponds to the reverse of a proof of the formula fv from the formula fu. The proof depends on the fact that the formation rules add properties to a graph. But if A and B are any properties, then (A ^ B)->A. Hence the graph u with more properties implies the simpler graph v.

3.5.3 Theorem. For any conceptual graphs u and v, if u £ v, then fu -> fv.
Proof. Consider a canonical derivation of u from v with intermediate graphs v₁, v₂, ..., v_n where v = v₁ and u = v_n. To prove that fu implies fv, show that at each step fv_i+1 implies fv_i. Then the sequence of formulas fv_n, ..., fv₁ would constitute a proof of fv under the hypothesis of fu. The rule for deriving the graph v_i+1 from v_i must be either copy, simplify, restrict, or join.

If copy, v_i+1 is identical to v_i. Therefore, fv_i+1 implies fv_i.
If simplify, fv_i contains a duplicate predicate that is omitted in fv_i+1. Since any formula A implies the conjunction A^A, fv_i+1 implies fv_i.
If a type label T is restricted to a subtype S, fv_i had a predicate T(x) that is replaced by a predicate S(x) in fv_i+1. By Assumption 3.2.4, dS dT Hence for any x, S(x) implies T(x). If a generic marker is restricted to an individual i, then S(i) implies the generic $x S(x). In either case fv_i+1 implies fv_i.
If join, fv_i+1 is equivalent to a formula of the form $x_i...$x_k (P ^ Q ^ x = y) where P is the body of fv_i, Q is a conjunction of predicates derived from some other graph w that was joined to v_i, and the equation x=y equates the two identifiers of the concepts that were joined. But the conjunction P^Q^x=y implies P. Therefore fv_i+1 implies fv_i.

If u is a specialisation of v, there must be a subgraph u' embedded in u that represents the original v to which additional graphs were joined during the canonical derivation.
The subgraph u' is called a projection of v in u. p is used for a projection operator: u' = pv.
Every conceptual relation in pv must be identical to the corresponding relation in v, but some of the concepts in v may have been restricted to subtypes or may have been converted from generic to individual.
In the derivation of u from v, some concepts of v may have been joined to each other, and some conceptual relations may have been eliminated as duplicates, therefore, the projection pv must contain a basic core of v, but its shape and concept types may be different.
3.5.4 Theorem. For any conceptual graphs u and v where u £ v, there must exist a mapping p: v -> u, where pv is a subgraph of u called a projection of v in u. The projection operator p has the following properties:

For each concept c in v, pc is a concept in pv where type(pc) £ type (c). If c is individual, then referent(c) = referent(pc).
For each conceptual relation in v, pr is a conceptual relation in pv where type(pr) = type (r). If the ith arc of r is linked to a concept c in v, the ith arc of pr must be linked to pc in pv.

The mapping p is not necessarily one-to-one: if x₁ and x₂ are two concepts of conceptual relations where x₁ ð x₂, it may happen that px₁ = px₂.
The mapping p is not necessarily unique: the graph v may also have another projection p'v in u where p'v ¹ pv.
Projections map graphs at higher levels of the generalisation hierarchy into ones at lower levels.
The hierarchy is not a lattice because two graphs may not have a unique minimal common generalisation/specialisation. But any two graphs have at least one common generalisation, since the graph [T] is a common generalisation of all. There is no guarantee that they must have a common specialisation, but many of them do.
Consider the following four graphs:

v: [PERSON] <- (AGNT) <- [EAT]

u₁: [GIRL] <- (AGNT) <- [EAT] -> (MANR) -> [FAST]

u₂: [PERSON:sue] <- (AGNT) <- [EAT] -> (OBJ) -> [PIE]

w: [GIRL:sue] <- (AGNT) <- [EAT] - 
                                 -> (MANR) ->[FAST] 
                                 -> (OBJ) -> [PIE]

3.5.5 Definition. Let u₁, u₂, v and w be conceptual graphs. If u₁ £ v and u₂ £ v, then v is called a common generalisation of u₁ and u₂. If w £ u₁ and w £ u₂, then w is called a common specialisation of u₁ and u₂.
Whenever two graphs u₁ and u₂ are joined on one or more concepts, the resulting graph w is a common specialisation of both.
Whenever two graphs are joined in such a way, the parts that were merged must be projections of some common generalisation.
In this example, the merged part is [GIRL:sue]<-(AGNT)<-[EAT]. This merged part is the projection of the common generalisation graph v.
Conversely, if two graphs u₁ and u₂ have a common generalisation v, then the corresponding projections p₁v in u₁ and p₂v in u₂ are candidates for being merged by a series of joins. Such a merger might be blocked, however, by incompatible type labels or referents. If there are no incompatibilities, then the two projections are said to be compatible.
3.5.6 Definition. Let conceptual graphs u₁ and u₂ have a common generalisation v with projections p₁: v->u₁ and p₂: v ->u₂. The two projections are said to be compatible if for each concept c in v, the following conditions are true.

type (p₁c) Ç type (p₂c) > ^.
The referents of p₁c and p₂c conform to type(p₁c) Ç type(p₂c).
If referent(p₁c) is the individual marker i, then referent(p₂c) is either i or *.

The common specialisation w may be derived by joining the graphs u₁ and u₂ on compatible projections of the more general graph v.
If all the conditions of 3.5.6 are satisfied, the two graphs can be merged by a join on compatible projections.
3.5.7 Theorem. If conceptual graphs u₁ and u₂ have a common generalisation v with compatible projections p₁: v -> u₁ and p₂: v -> u₂, then there exists a unique conceptual graph w with the following properties:

w is a common specialisation of u₁ and u₂.
There exist projections p₁':u₁ -> w and p₂':u₂ ->w where p₁'p₁v= p₂'p₂v.
If w' is any other conceptual graphs with the above two properties, then w' < w.

The graph w is called a join on compatible projections of u₁ and u₂. If both u₁ and u₂ are canonical graphs, then so is w.
Since two conceptual graphs may have many different common generalisations, they may also have many different pairs of compatible projections.
3.5.8 Theorem. Let conceptual graphs u₁ and u₂ have a common generalisation v with compatible projections p₁: v->u₁ and p₂: v->u₂, and let v' be a proper subgraph of v. Then v' is also a common generalisation of u₁ and u₂ with compatible projections p₁: v' -> u₁ and p₂: v' ->u₂. The compatible projections p₁v and p₂v are said to be extensions of p₁v' and p₂v'.
If two graphs contain compatible projections of a common generalisation v, those projections might be extended by finding a larger common generalisation that includes v as a subgraph. Since all conceptual graphs are finite, the process of extension must eventually stop. When it stops, the resulting compatible projections are called maximally extended. A join on those projections is then called a maximal join.
3.5.9 Definition. Two compatible projections are said to be maximally extended if they have no extensions. A join on maximally extended compatible projections is called a maximal join.

Dickson Lukose &

Rob Kremer . KNOWLEDGE ENGINEERING, PART A: Knowledge Representation. July 1996.

index