THEORY OF CONCEPTUAL GRAPHS

CHAPTER 4 - GRAPHS

Basic Ideas

So far we have described the basic building blocks of our knowledge representation language. In this short chapter we will see how these blocks are built up into more complex structures called conceptual graphs. There are three main considerations: Logically, each entity only has one marker and therefore only one concept box, although the need to reduce crossing lines may make it necessary to duplicate some concepts, in which case duplicate generic concepts are linked by coreference links. Relations only exist between concepts and not other relations. Concepts, on the other hand, can have as many attached relations as necessary.

From the above it follows that graphs can be either neat linear structures of alternating concepts and relations, starting and ending with concepts, or they can be tangled webs of boxes, ovals and arrows. From this it also follows that the linear notation must be carefully written in order to ensure that the correct links are made. Sowa's notation, as suggested previously, is not adequate for >2-ary relations or relations with more than one outward pointing arrow. To overcome these points we extend the notation so that branch points in the linear form can be indicated..

Some Simple Graphs

In general conceptual graphs can be any shape or size whatever. This means that they can be very complex and care is required over their layout in display form. Their equivalent display form will probably require, and certainly require if there are loops, the use of copious coreference links on the generic variables. We illustrate with a small selection of graphs which describe simple scenes and situations, similar to those found in Sowa.

The above graph is a simple graph which illustrates some useful points:

1. The drawing of the graph need not be as shown but can start with any node, as illustrated by the different starting place of the linear form,

2. The graph can be read by starting from virtually anywhere, although some starting points may be cumbersome,

3. The logical connective between each of the three relations is AND.

The linear form above contains an extension to that previously encountered. That is, each relation that is attached to the [ TRAVEL ] concept is terminated with a comma. All branches must be terminated with one comma for every concept in the branch directly between the comma and the concept at the the start of the branch. The final branch is terminated with a full stop. The following graphs illustrate this:

Notice from these two examples that every concept that is a branch point, shown by [ ... ]- in linear form, contributes one comma at the end of its branch. The final branch is terminated by the final full stop and the full stop would still be present if there had not been any branches.

The next graph contains a loop which is shown in the linear form by the addition of a coreference link:

The linear form lists the relations attached to each concept. That used to list the relations attached to each concept is that of Sowa where the assumption is that the arrows to the left of each relation node point the same way as those to the right. We will later see a more general way of listing attached relations that does not make this assumption.

The graph shows that in order to break the cycle, which is necessary in linear form, a concept node must be repeated and where there is an unnamed generic marker, either in the type or relation field, it must be provided with a unique coreference marker. The addition of a coreference marker is not an indication that the logical status or the referent of the generic marker are changed.

Extensions To Linear Form

Since the Sowa linear form cannot deal with relations such as []<-()->[] or []->()<-[] and is severely limited with n-adic relations, extensions to the notation are needed. These take the form of a requirement to include full arrows immediately after each concept and an operator which places the immediately preceding node onto a stack.

Arrows

In order to resolve the ambiguity that results from Sowa's linear form when a relation such as

[ Concept1 ]<-( Rel )->[ Concept2 ]

or

[ Concept1 ]->( Rel )->[ Concept2 ]

is written in Sowa's linear form, both giving

[ Concept1 ]-

( Rel )->[ Concept2 ].

the required change to the linear form is simply to remove the hyphen and replace it with an appropriate arrow. However, since we wish to remain as close to Sowa's original notation as possible, we retain the hyphen notation for those situations where the assumption about the direction of the arrow at that point is correct.

Branching Operator

Consider the following graph:

[ C5 ]<-( R4 )<-[ C1 ]->( R1 )->[ C2 ]->( R2 )->[ C3 ]->( R3 )->[ C4 ]

In Sowa's linear form, starting from [ C1 ], this would become:

[ C1 ]-

( R1 )->[ C2 ]-

( R2 )->[ C3 ]-

( R3 )->[ C4 ],,

( R4 )->[ C5 ].

Since Sowa's linear form always starts with a concept there is no ambiguity. The commas always terminate branches that are assumed to come from concept nodes. However, we allow linear form to start at relations as well, since in that way a graph might be more conveniently written and we want the whole system to be as general and flexible as possible. In this case the linear form above might suggest that ( R4 ) is attached to ( R2 ), which it clearly cannot be.

We use a branching operator, “;”, appended to a concept or relation node to show that that node is to be taken as the branch point terminating at the next comma. Take the following example:

[ MAN ] ;->( WIFE )->[ WOMAN ];->( BROTHER )->[ MAN ], (1)

->( SISTER )->[ WOMAN ],, (2)

->( BROTHER )->[ MAN ]. (3)

Since we are including the complete arrows it is not clear in line 1 which of the concepts is the branch point of the branch terminated by the comma. In fact line one has two branch points. The comma in line 1 terminates the branch starting at [ WOMAN ]. Without the explicit inclusion of the branching operator this would be ambiguous. Similarly, the two commas in line 2 terminate the branches starting at [ WOMAN ] and [ MAN ] and there is no doubt about who's brother the [ MAN ] in line 3 is.

Relations As Branch Points

The situation is slightly different when a relation node is indicated to be a branch point because relation nodes do not have referents. The following will work:

( Rel1 );  - >[ Concept1 ],

 ->[ Concept2 ],

...

->[ Conceptn ].

( Rel2 );  <-[ Concept1 ]

->[ Concept2 ],

<-[ Concept3 ]

->[ Concept4 ],

...

<-[ Conceptn-1 ]

->[ Conceptn ].

These will produce separate relations for each comma delimited set of concepts. In the first case each relation is of the form ( Rel1 )->[ Conceptx ] and in the second case each relation is of the form [ Conceptx ]->( Rel )->[ Concepty ].

The following will not work:

( Rel1 );   <-[ Concept1 ]->( Rel2 )->[ Concept2 ],

->[ Concept3 ].

The result of this would be the three relations:

( Rel1 )<-[ Concept1 ]

( Rel2 )<-[ Concept1 ]->[ Concept2 ]

( Rel1 )->[ Concept3 ]

In other words, all the concepts for any branch point relation must be contiguous.

The BETWEEN Relation Revisited

In the previous chapter we saw the triadic BETWEEN relation and stated that, instead of numbering the arcs, relevant semantic information about the roles of each attached concept should be part of the graph. We can now give this graph and its associated linear form as a final example in the chapter.

Notice that in this example it is easiest to start the linear form from the [ BRICK : *x ] concept and the branching operator has been used. The Sowa notation would look like:

[ BRICK : *x ]-

( TOLEFTOF )->[ BRICK : *y ],

( TORIGHTOF )->[ BRICK : *z ],

( BETWEEN )<-[ BRICK : *y ]<-[ BRICK : *z ].

and would be easier in this case but it is only completely unambiguous because the BETWEEN relation has been written with both inward pointing arrows on the same side of the relation node as each other.

Updated 14^th December, 2006