OPERATIONS ON GRAPHS

CHAPTER 1 - GENERALISATION AND SPECIALISATION

Basic Ideas

Conceptual Graphs is a typed logic which means that the individuals represented by markers have an associated type and appropriate type label. These two components, the type label and marker, are what form the concepts of Conceptual Graphs. The same typing applies to relations between concepts and relations of certain types are appropriate between concepts of certain types.

In addition to types in concept and relation nodes there are the type hierarchy and relation hierarchy which are introduced here. These allow certain kinds of operation to be performed on single conceptual graphs or between pairs of graphs. In this chapter we discuss two of these operations.

Conformity Relations

Every individual marker is stated to conform to some type by a conformity relation. This is represented as type :: marker, which allows us to say that marker conforms to type and allows us to write the concept [ TYPE : marker ]. For the conformity relation type is the most specific type that accurately describes marker. For a type hierarchy in which some type T1 < T2 < T3 < ... and T1 :: marker the following can also be written: T2 : marker, T3 : marker, ..., giving us the concepts: [ T2 : marker ], [ T3 : marker ], .... Note the use of the single colon in the conformity relations to show that the type is not the most specific.

Since T2 and T3 are not the most specific types to which marker conforms we call relations such as type : marker "conformity relations" and relations such as type :: marker "specific conformity relations". Sowa, however, does not make this distinction and so he uses the term "conformity relation" where we use "specific conformity relation" and he uses :: where we use :.

Generalisation

The operation of generalisation can be carried out on single graphs or between pairs of graphs. Where only one graph is involved the result is a generalisation of that graph whereas where two graphs are involved the result is a common generalisation of the two graphs. In each case the resulting graph contains less information than the starting graphs and as a result could apply to or refer to more individuals.

Generalisation Of A Single graph

Any graph can be generalised in one or more of three ways: any type label may be replaced with a supertype label or the generic marker, any relation label may be replaced with a superrelation label or the generic marker, any individual referent may be replaced with a generic referent or a coreference marker can be removed.

The generalisation by these means of any evenly enclosed graph follows from Peirce's rule of erasure and so is truth preserving. The generalisation of oddly enclosed graphs is not truth preserving and so is meaningless.

Common Generalisation

Given two relations it is possible to find a generalisation of one which is also a generalisation of the other. Such a generalisation is called a common generalisation. The following example illustrates this:

Fig. 1.1

The graph at the bottom of the diagram, graph A, is a common generalisation of each graph at the top. We could take the process further and generalise the bottom graph to, say, [ LIVING_THING : * ]->( OWNER )->[ LIVING_THING : * ], graph B. This is also a common generalisation but there is a difference between graph A and graph B: if we assume that ANIMAL is the immediate supertype of DOG and CAT and OWNER is the immediate superrelation of MASTER and PETOWNER then graph A is the most specialised graph that can be a common generalisation in this case. We call such a graph a minimal common generalisation or supremum.

Generalisation of a simple graph in this way, or of any evenly enclosed graph, is truth preserving. In the example above the graph at the bottom is certainly true if either top graph is true. This has a clear relationship with Peirce's rules in that information in an evenly enclosed context can be erased. Generalisation of evenly enclosed graphs is part of the rule of erasure.

Specialisation

The operation of specialisation can be carried out on single graphs or between pairs of graphs. Where only one graph is involved the result is a specialisation of that graph whereas where two graphs are involved the result is a common specialisation of the two graphs. In each case the resulting graph contains more information than the starting graphs and as a result could apply to or refer to fewer individuals.

Specialisation Of A Single graph

Any graph can be specialised in one or more of three ways: any type label may be replaced with a subtype label or (if the generic marker) a type label, any relation label may be replaced with a subrelation label or (if the generic marker) a relation label, any generic referent may be replaced with a coreference marker or an individual marker.

The specialisation by these means of any oddly enclosed graph follows from Peirce's rule of insertion and so is truth preserving. The specialisation of evenly enclosed graphs is not truth preserving and so is meaningless.

Common Specialisation

Given two relations it is possible to find a specialisation of one which is also a specialisation of the other. Such a specialisation is called a common specialisation. The following example illustrates this:

Fig. 1.2

The graph at the bottom of the diagram, graph A, is a common specialisation of each graph at the top. We could take the process further and specialise the bottom graph to, say, [ BABY_BOY : peter ]->( SISTER )->[ BABY_GIRL : mary ], graph B. This is also a common specialisation but there is a difference between graph A and graph B: if we assume that BOY is an immediate subtype of MALE and SISTER is an immediate subrelation of SIBLING then graph A is the least specialised graph that can be a common specialisation in this case. We call such a graph a maximal common specialisation or infimum.

Specialisation of a simple graph in this way is only truth preserving in oddly enclosed contexts. In the example above the graph at the bottom is certainly false if either top graph is false. This has a clear relationship with Peirce's rules in that information in an oddly enclosed context can be inserted. Specialisation of oddly enclosed graphs is part of the rule of insertion.

Canonical Graphs

Relations hold between concepts of particular types or, more accurately, between concepts on particular lines of inheritance. For the relation [ P ]->( R )->[ Q ] we could also write [ P1 ]->( R )->[ Q1 ] where P1 and Q1 are supertypes or subtypes of P and Q. We will illustrate this with an example: The relation [ MAN : john ]->( NEPHEW )->[ MALE : chris ] is a plausible relation and as long as MAN :: john and MALE : chris are true then the relation is true. Assuming the normal type hierarchy we can also write [ MAN : john ]->( NEPHEW )->[ BOY : chris ] as long as BOY :: chris is true. In this case the relation may be false but the graph is nevertheless well formed. On the other hand we could also write [ MAN : john ]->( NEPHEW )->[ PERSON : chris ]. This is only true if MALE : chris is true since PERSON : chris could be a female.

Thus there are limits to the generality of the concepts attached to a relation such that all instantiations remain plausible. Whilst, in the example above, the graph [ MAN : john ]->( NEPHEW )->[ PERSON : chris ] is true it is not the case that [ MAN : john ]->( NEPHEW )->[ PERSON : * ] is plausible for all instances of PERSON even though it is for all instances of MAN. The [ PERSON : * ] concept is too general to be always plausible. However, the relation [ PERSON : * ]->( NEPHEW )->[ MALE : * ] is always plausible even if it is not true in some cases. We call this last graph an upper bound canonical graph since it expresses a combination of a relation and attached types that are always plausible even if not always true. Similarly the graph [ MAN : john ]->( NEPHEW )->[ MALE : * ] is a canonical graph since if an unrestricted person can have a nephew then a man can have a nephew.

It is not always the case that any canonical graph may be specialised to every degree and remain canonical. For instance we might have the canonical graph [ MAN : john ]->( SON )->[ BOY : chris ] and yet it might be that John is a eunuch in which case it is implausible that John has a child. Thus the graph [ EUNUCH : * ]->( CHILD )->[ PERSON : * ] is not plausible and is uncanonical. To rule out such graphs we must write the lower bound canonical graph ~( [ EUNUCH : * ]->( CHILD )->[ PERSON : * ] ). This graph says that it is false that any eunuch has a child.

The collection of all upper bound and lower bound canonical graphs is called the canonical basis. Its main use is in the detection of ill formed relations.

Semantic Units

Natural language sentences are all formed around verbs and consist of verbs with associated participants. Each verb belongs to a class of verbs with a particular set of participants that contribute to its meaning. In some cases the sentence may not contain references to all possible participants but the meaning of the verb may require their assumed presence. We call a verb with its associated participants and relations a semantic unit. Semantic units were not described by Sowa and indeed the term is ours. The idea for them arose from practical experience of the processing of graphs which contained concepts of acts where each relation was proved in turn when it would have been more efficient to prove the whole semantic unit in one go. Where a system encounters a graph which contains a concept for an act which requires more relations than those given it must provide the missing ones so that the semantic unit is complete.

Verbs fall into two main categories: intransitive and transitive. An intransitive verb is done by something but is not done to anything, except that it might be done with something. A transitive verb is one where the action is done by something to something, and again maybe with something. Sometimes a verb describes an action in which the performer is accompanied by somebody else. Since different classes of verb take different combinations of "parameters" we can for each class specify which parameters must either be present or assumed. We can do this with something equivalent to the canonical graph for a relation.

When we express the relations which are attached to a concept represented by a verb we use the following:

PART OF SPEECH	CONCEPTUAL RELATION
Subject	AGENT
Direct Object	PATIENT
Indirect Object	INSTRUMENT

This is obviously not an exhaustive list but it illustrates the connection between the grammatical part of speech and the semantic roles, and hence relations, played by individuals. As an example we give a graph that describes the act represented by an intransitive verb with an indirect object: [ PERSON ]<-( AGENT )<-[ INTRANS_ACT ]->( INSTRUMENT )->[ OBJECT ]. There is an interesting link between this graph and the graph which describes the phrase in which the action is represented: [ NOUN ]<-( OBJECT )<-[ INTRANS_VERB ]->( INDIRECT_OBJECT )->[ NOUN ]. There is a mapping between this graph and the previous graph which can be used to convert the parse of a sentence into a graph representing the semantic content of the sentence. This mapping is the subject of further work.

It may also be useful to define necessary relations to be attached to concepts that represent nouns. However, the possible relations that could be attached to any individual are huge in number and it may be that none of them are required as part of the semantics of individuals of that type. This is an area for further work.

Updated 24^th January, 2007