Part I: Graphs

Welcome to this course!

This course is about a technology called 'conceptual graphs'. This technology can be used to represent knowledge and meaning in a computer. The technology consists of a "formal language" in which we can express knowledge and meaning. In this course, we will be learning about that language, but not much about any particular implementation. We will be drawing graphs with pencil and paper where necessary, and we will learn to read conceptual graphs.

Example

A simple conceptual graph could look like this:

It represents the phrase "Conceptual graphs". This is a very simple example, but conceptual graphs can scale to almost any size to express almost anything which we want to say.

Knowledge bases

A knowledge base, so far as conceptual graph-theory is concerned, consists of a number of things:

Knowledge bases are the means to representing knowledge and meaning. We will not be making reference to any particular knowledge base in this course. Instead, we will simply assume that all the graphs we draw are part of some larger knowledge-base which has the elements listed above.

Scope of conceptual graph-theory

Conceptual graphs as such are only a part of the overall theory of conceptual graphs: Other parts include:

We will get back to all of these in due course. For now, it is important to bear this goal in mind: That we will be able to represent knowledge and meaning in a computer.

Next

Next, we note some practical points before going on to the main material.


Practical points

Introduction

Noting a number of practical points will help you navigate through the pages of this course.

Document navigation

Firstly, at the bottom of each page, you will find a number of links to help you navigate the document-structure. For example, some pages will have links to "Prev"(ious), "Up", and "Next".

The "Prev" and "Next" links take you to the previous and following pages in the document flow respectively. The "Up" link takes you to the page once upwards in the hierarchy of pages.

For example, following the "Up" link from this page will take you to the table of contents. You will always be able to get to the table of contents if you follow "Up"-links far enough.

Optional material

Secondly, at a number of points through the course material, there will be optional parts. You can read these parts if you want to, or skip them if you like; they are not required reading. If you do decide to follow the links to the optional parts, there will be a "Back" link at the bottom of the page which will take you back to where you left the main flow of the material.

Reference materials

A number of reference materials are available in Part VI. They are:

Sample conceptual relations

The page with sample conceptual relations contains a list of some of the most commonly used relations (such as "Agnt" (Agent)). You will need to refer to this page often, so one suggestion would be to bookmark it. There will also be links to this page from the graphs that have relations defined on this page.

Glossary

This course is quite liberally interlinked with hyperlinks. One particular kind of hyperlink is to the glossary. You will be able to identify the glossary-hyperlinks by hovering the mouse over the link, then looking at the status line of the browser. If it says "Glossary", you know it is a link to the glossary. You can then decide whether you want to follow the link or not.

Glossary of symbols

The glossary of symbols defines some of the symbols used in the course, with links to the relevant parts of the material.

Hyperlinks within the course material

Another kind of hyperlink is to other parts of the course. You can identify these in the same way as for the glossary-definitions, except that the URL in the status-line will say "Module_I/XXXX.php3", where "XXXX" is a four- or five-digit number.

Quizzes

At the end of most chapters, there will be a short quiz to help you reflect on the main points of the chapter. The quizzes will be quite easy, and sometimes you may even think that the questions are insulting your intelligence. If this is the case, please be forgiving.

The quizzes will be multiple-choice. You will be given a question, and then you have to choose from a number of answers. Only one answer will be correct. When you have selected the right answer to all questions, simply press the "Check answers" button at the bottom of the page. This will take you to a new page that tells you how many you got right, as well as the answer to, and an explanation for, any question which you got wrong.

The answers given in the quizzes will be logged. However, no-one will be able to trace the link between you and the answers. Thus, even though the answers are logged, the answers given are anonymous.

Onward

But now, let us get going. We start by looking at conceptual graphs, the most central aspect of the overall theory of conceptual graphs.


Conceptual graphs

Definition

A conceptual graph is a graph or network of two kinds of nodes:

  1. Concepts and
  2. Relations.

The nodes have arcs between them. The arcs are always directed, i.e., they have a direction. This is indicated by an arrow head.

Now we will see some examples.


Example

An example of a conceptual graph could be:

  [Graph: {*}]->(Attr)->[Conceptual]

This is a graph representing the phrase "Conceptual graphs". The notation used is called the "linear notation" because it is drawn using linear text. There is another way to draw conceptual graphs, namely the graphical notation:

In the graphical notation, concepts are drawn as rectangles while relations are drawn as circles (or ovals). In the linear notation, concepts have [square brackets] around them, while relations have (parentheses).


A CG is a bipartite graph

A conceptual graph is a bipartite graph. This simply means that there are no arcs between a concept and another concept, and no arcs between a relation and another relation. All arcs either go from a concept to a relation or from a relation to a concept.

The term "bipartite" means "partitioned in two". The nodes of a bipartite graph can be divided into two nonempty sets A and B, with two different kinds of nodes. All arcs of a bipartite graph then connect exactly one node from A and one node from B. Therefore, all arcs cross the boundary between the two sets of the two kinds of nodes.

Conceptual graphs are bipartite in that it has two kinds of nodes, concepts and relations, and every arc "crosses the border" between the two sets of the two kinds of nodes. That is, any arc connects a concept with a relation.


Belongs to, attached to

An arc is said to belong to a relation but to be attached to a concept. This is useful terminology, and will be used throughout the remainder of these notes.

For example, in the graph

   [Say]->(Thme)->[Phrase: "Nightie-night"]
   "Say 'Nightie-night'" 
the two arcs belong to the relation "(Thme)", while they are attached to the two concepts "[Say]" and "[Phrase: "Nightie-night"]".


Stand-alone concepts

A conceptual graph may have concepts that are not linked to any relation. Thus concepts can stand alone without being linked to any relation.

For example, the following conceptual graph is well-formed:

   [God]

This conceptual graph means "There is a God". Of course, this may or may not be true.


Stand-alone relations

While it is possible for concepts not to have any arcs attached to themselves, this is not possible for relations. A relation must have at least one arc that belongs to it.

For example, the following is not a well-formed conceptual graph:

   (On)
   Ill-formed conceptual graph

However, the following is a well-formed conceptual graph, since the relation (In) has at least one arc that belongs to it (in fact, it has two):

   [Bird]->(In)->[SycamoreTree]
   Well-formed conceptual graph

It means "There is a bird in a sycamore tree".


Special names

Three kinds of conceptual graph are given distinguished names:

  1. A blank is an empty conceptual graph with no concepts, no relations, and no arcs. This is a blank:
    
         A blank
    
    The blank conceptual graph is the graph that says nothing about anything, and which therefore is true about everything.

  2. A singleton is a conceptual graph that consists of a single concept, but no conceptual relations or arcs. We have already seen an examle of a singleton:
         [God]
       A singleton
    

  3. A star is a conceptual graph that consists of a single relation and the concepts that are attached to its arcs. For example, these are both stars:
       [Bird]->(In)->[SycamoreTree]
       "A bird is in a sycamore tree"
    
       [Cat]->(On)->[Mat]
       "A cat is on a mat"
    


Reading arrows

The challenge

Reading arrows is not easy at first. There are eight combinations of various dimensions that one has to keep track of. However, reading arrows is essential to reading conceptual graphs. Therefore, this page has all of the information you need in order to be able to read arrows.

Equivalence of reading directions

The following two graphs are equivalent:

   [A]->(R)->[B]    and    [B]<-(R)<-[A]

Thus the direction of the arrows on the page is determined by the position of the concept types within the signature, and is otherwise immaterial.

Standard Language

There is also special standard language associated with the direction of an arrow. This language can be divided into two groups:

  1. When reading in the direction of the arrows,
  2. When reading against the direction of the arrows.

For each group, it also matters whether we are reading an arrow that points towards or away from a relation.

  1. When reading in the direction of the arrows:
    1. If the arrow points away from the relation, we often say "which is".
    2. If the arrow points towards the relation, we often say "has a".
  2. When reading against the direction of the arrows:
    1. If the arrow points away from the relation, we often say "is a".
    2. If the arrow points towards the relation, we often say "of".

This can be shown as in the following two tables. The first is when reading from left to right and the second is when reading from right to left:

[concept]<-(relation)
"is a"
[concept]->(relation)
"has a"
(relation)<-[Concept]
"of"
(relation)->[Concept]
"which is"
Example:
  [Fat]<-(Attr)<-[Cat]
Fat "is an" attribute "of" Cat
Example:
   [Cat]->(Attr)->[Fat]
Cat "has an" attribute "which is" Fat.
(Reading from ---> left to right)

(Reading from right to left <---)
[concept]<-(relation)
"which is"
[concept]->(relation)
"of"
(relation)<-[Concept]
"has a"
(relation)->[Concept]
"is a"
Example:
    [Fat]<-(Attr)<-[Cat]
Cat "has an" attribute "which is" Fat.
Example:
  [Cat]->(Attr)->[Fat]
Fat "is an" attribute "of" Cat.

Examples

First example

Now we need examples. Try to follow these examples in the two tables above. The following graph can be read in two ways:

   [Bird]<-(Agnt)<-[Sing]
   "A bird is singing"
  1. From left to right: "Bird is an agent of Sing".
  2. From right to left: "Sing has an agent which is a bird".

Second example

Another example:

   [Sing]->(Agnt)->[Bird]

can be read:

  1. From right to left: "Bird is an agent of Sing".
  2. From left to right: "Sing has an agent which is a bird".

It is important that you learn to read arrows. Thus it is recommended that you go back and try to match each arrow with each of the four expressions in the two ways of reading the graph.

Third example

Another example:

   [Person: John]<-(Agnt)<-[Go]->(Dest)->[City: Aalborg]
   "John is going to Aalborg"
  1. "Go has an agent which is a Person who is John. Also, Go has a destination which is a City which is Aalborg."
  2. "John is an agent of Go. Aalborg is a destination of Go."

Language about prepositional relations

This technique does not work very well with relations which are prepositions, such as On and In. In this case, it is better simply to say the preposition, preceded by a form of the verb 'to be', as in:

   [Book]->(On)->[Table]
   "A book is on a table"

Importance of reading arrows

This concludes our discussion of how to read arrows. It is important that you practice reading arrows until you master the technique.

If you wish, you can print out this page and have it lying beside you as a reference.


Concepts

Definition of a concept

On this page, we define what a concept is.

A concept is made up of two entities

A concept is always made up of two entities:

Concepts with both a type and a referent

The concept is drawn like this:

   [Type: Referent]

where the type and the referent are separated by a colon. For example:

   [Person: John]
   "There exists a person whose name is John"

Here, "Person" is the concept type, and "John" is the referent.

Concepts with only a type

If the referent is blank, the concept is drawn like this:

   [Type]

For example:

   [Bus]
   "There exists a bus"

The type can never be blank.

Next

We now discuss concept types in a little more detail.


Concept types

Introduction and sample ontology

The concept type of a concept says what kind of concept we are dealing with. For example, these could all be types in our ontology:

   Entity > Bus, Person, Tree, Location, Act, Animal.
   Person > Student, Employee.
   Employee > Professor.
   Tree > SycamoreTree.
   Location > City.
   Act > Go, Leave, Eat, Catch.
   Animal > Cat, Dog, Bird, Mouse.

What is a type?

A type is a label or name we give to a group of entities with similar traits. If we can categorize a number of individuals (e.g., "John", "Alfred", "Mary") in the same group (e.g., "Person"), then we can call the name of the group, together with the definition of the group, a "type".

Subtypes and supertypes

A type can be a subtype of another type. For example, in the above ontology, "Cat" is a subtype of "Animal", while "Student" is a subtype of "Person". In the list of examples above, subtypes are listed after their supertype and a '>'.

Lattice notation

The concepts "subtype" and "supertype" will become clearer if we look at the above examples of types in a diagram such as this:



"Some of the above types, drawn in a lattice"

Here, we see that the "subtypes" are below their "supertypes". The Entity and Absurdity types will be explained later.


Referents

Look at the lattice of types from the previous page:



"Types in a lattice"

An individual from any of the groups that these types define can be the referent of a concept. For example:

   [Person: John]

This concept says that "There exists a person whose name is John". "Person" is the type, while "John" is the referent. In other words, "John" is the particular individual (or referent) which we are referring to, and he is an instance of the type "Person".


Examples

Examples

These are also examples of types and referents:

   [Cat: Felix]
   [Mouse: Eeek]
   [Cat: Garfield]
   [Dog: Odie]
   [Animal: Odie] 
   [Employee: Jon]
   [Professor: Alfred]

For example, in the concept:

   [Professor: Alfred]

"Professor" is the type and "Alfred" is the referent.

Prolog+CG notation

In Module II of this series of courses on conceptual graphs, we will learn about a system called Prolog+CG. Later on in this course, we will learn what an ontology is. In Prolog+CG, the above individuals could be specified, as part of an ontology, like this:

   Cat = Felix, Garfield.
   Mouse = Eeek.
   Dog = Odie.
   Employee = Jon.
   Professor = Alfred.


Blank referents

The referent may be left blank, as in the following conceptual graph:

   [Bus]->(Dest)->[City: Aalborg]

Here, the concept "[Bus]" has no referent. The concept simply means "A bus" or "There is a bus".

Anytime the referent is left blank, it means "There is an X" or simply "An X", where "X" is the concept type.

The whole conceptual graph means

"There is a bus which has a destination (Dest) which is a City, the referent of which is Aalborg."


Relations

A conceptual graph is a bipartite graph

It will be remembered that a conceptual graph is a bipartite graph with two different kinds of nodes:

  1. Concept nodes
  2. Relation nodes

We have already discussed concept nodes. Now we discuss the other kind, relation nodes.

What are relations?

If concepts can be likened to bricks in a wall, then relations can be likened to the mortar that bonds the bricks together. Relations relate concepts to each other in all of the different ways that concepts can be related.

For example, in the following graph,

   [Cat]->(On)->[Mat]
   "A cat is on a mat"

the concepts "Cat" and "Mat" are related by the relation node "On". The concepts "Cat" and "Mat" are the "bricks" of the graph, while "On" is the "mortar" that binds the concepts together.

Next

With this informal introduction in mind, we now gives some definitions that are useful when thinking and talking about relations.


Definitions for relations

This page merely gives an overview of the three kinds of ideas associated with relations, namely:

In later sections, we treat each idea more fully.

All relations have a relation type. This tells us the kind of relation we are dealing with. While concepts have both a type and a referent, relations only have a type.

The valence of a relation is the number of arcs that belong to it. This number, or the valence of a relation, is always greater than or equal to 1.

A relation type also has a signature. The signature of a relation is a list of the concept types involved in the relation.

In the following, we discuss relation type first, then valence, and then signatures.


Relation type

Definition and examples of relations

A relation type is simply a name which we give to the relation. It tells us what kind of relation we are dealing with. The type also determines the valence of the relation and its signature. That is, the type of the relation determines the number of arcs that belong to it, and the types of the concepts that are attached to those arcs.

For example, all of these are relation types:

On        (on)
In(in)
Dest(destination)
Agnt(agent)
Thme(theme)
Ptnt(patient)
Rcpt(recipient)

A very important relation is "Agnt" or "agent". It is used again and again when we draw conceptual graphs. It relates an act (such as "Sing") and an animate being (such as "Bird") which performs the act. We will use this relation in the next example.

Example using a conceptual graph

Consider this conceptual graph:

   [Sing]->(Agnt)->[Bird]->(In)->[SycamoreTree]

This conceptual graph says:

"There is a bird which is the agent of Sing. This same bird is in a sycamore tree".

Or, put into better English:

"A bird is singing in a sycamore tree".

This graph has two relations, "Agnt" (agent) and "In" (in). The relation type of "Agnt" is "Agnt". Its valence is 2, and it relates an act with an animate being. The relation type of "In" is "In". Its valence is 2, and it relates two physical entities in a spatial relationship.

Note on tense and aspect information

The tense and aspect of the verbal concept "Sing" are unspecified in the graph. It is a generally accepted idea that graphs are atemporal -- i.e., they do not say anything about tense and aspect, unless explicitly specified. The default interpretation is to interpret a graph as active indicative present tense unless otherwise specified.

There are techniques for specifying both tense and aspect, but we will not be looking at them in this course. The only exception is that we will note that to specify past, we can use the "Past" relation:

   (Past)->[Situation: [Sing]->(Agnt)->[Bird]->(In)->[SycamoreTree] ]

This graph has a sub-graph that is embedded in a concept (the graph that is the referent of the concept "Situation"). This structure will be explained later.

Onward

To summarize: A relation is defined by its relation type. The relation type not only gives a name to the relation, it also determines the other two ideas associated with relations, valence and signature. We discuss valence next.


Valence

Definition

The valence n of a relation is the number of arcs that belong to it. For any relation type t, the valence n is always constant. That is, the number of arcs that belong to a relation is always the same.

Example

For example, the number of arcs that belong to the concept type "Dest" (destination) is always two, and the number of arcs that belong to the concept "Agnt" (agent) is also always two. This is because the valence of "Dest" is 2, and the valence of "Agnt" is also 2:

   [Person: John]<-(Agnt)<-[Go]->(Dest)->[City: Aalborg]

This conceptual graph can be paraphrased as:

"A Person, John, is the agent of 'Go', and the destination of Go is a City, which is Aalborg".

In better English:

"John is going to Aalborg".

n-adic, monadic, dyadic, triadic

A relation with valence n is said to be n-adic. For example, a relation with valence 5 is said to be 5-adic. The first three valences have special names:

  1. monadic is a synonym for 1-adic,
  2. dyadic is a synonym for 2-adic,
  3. triadic is a synonym for 3-adic.

Examples of the first three valences

Examples of monadic relations

Examples of monadic expressions include "Past" (past tense) and "Psbl" (possibility):

   (Past)->[Situation: [Bird]<-(Agnt)<-[Sing] ]
   "In the past, there was this situation: A bird was singing."

   (Psbl)->[Situation: [Bird]<-(Agnt)<-[Sing] ]
   "It is possible that a bird is singing."

Examples of dyadic relations

We have already seen numerous example of dyadic relations. For example, "Agnt" (agent), "Dest" (destination), and "On".

Example of a triadic relation

An example of a triadic relation could be "Betw" or 'between'.

   [Person: Julia]<-(Betw)-
                 <-1-[Person: Tom]
                 <-2-[Person: Brad]
   "Julia is between Tom and Brad"
   Example of a triadic relation.

Note the special multi-line notation. We will discuss this in detail later.

Summary

To summarize: the valence of a relation is determined by the relation type, is always constant, and signifies the number of arcs that belong to the relation.


Signature

Definition

An n-adic conceptual relation r is said to have a signature of n concept types. The signature is written as <t1, t2, ..., tn>, where t1, t2, t3, etc. are the types of the concepts that are attached to each of the arcs that belong to r.

Example

For example, the relation type

   Agnt

is said to have the signature

   <Act,Animate>.

This is because the first arc that belongs to Agnt must be attached to a concept whose concept type is either Act or a subtype of Act. The second arc must be attached to a concept whose concept type is either Animate or a subtype of Animate:

   [Sing]->(Agnt)->[Bird]

Here, "Sing" is a subtype of "Act", which is the first concept in the signature. "Bird" is a subtype of "Animate", which is the second concept in the signature.

Order significant

The order of the concept types in the signature of a relation is significant and is always constant. This is important for the direction of the arrows on the arcs, as we shall see next.


Direction of arrows

Definiton

There is a convention for the direction of the arrows that go to and from a conceptual relation. In fact, this convention is part of the definition of a conceptual relation. The convention is this: For a conceptual relation with n arcs, the first n-1 arcs point towards the relation, while the last, or n-th, arc points away.

Determining the last arc

How do we know which is the last arc? In other words, how do we know which arc should point away from the relation while all the rest should point towards the relation?

The answer is simple: We know from the signature of the relation. For example, the signature for the "Agnt" relation is:

   <Act,Animate>

Therefore, the arc that points away must be the one that points to the concept denoting the animate entity:

   [Sing]->(Agnt)->[Bird]

Thus when we say "first arc", "second arc", "third arc", etc., we are referring to their position within the signature.

Special cases: 1 and 2 arcs

It follows from the definition that in the special case where there is only one arc (a monadic relation), the arc must point away from the relation. In the case of two arcs, the first points towards the relation while the second points away. For example:

   (Past)->[Situation: [Sing]->(Agnt)->[Bird] ]
   "A bird sang"

Notice how for the monadic relation (Past), the arc points away, while for the dyadic relation (Agnt), the first points towards the relation while the other points away.

Next

Relations may have more than two arcs (have valence greater than 2). The next section discusses notation for dealing with this.


Notation for more than two arcs

Example

In the linear notation, if a relation has more than two arcs, the arcs may be represented as in this example:

   [Person: Julia]<-(Betw)-
                 <-1-[Person: Tom]
                 <-2-[Person: Brad]
   "Julia is between Tom and Brad"

If this were a Hollywood movie, we might imagine Julia Roberts walking gracefully between Tom Cruise and Brad Pitt.

The hyphen continues the arcs

The hyphen after the relation indicates that its arcs are continued on subsequent lines. Here is the example again, in a different form:

   [Person: Tom]-1->(Betw)-
                <-2-[Person: Brad]
                ->[Person: Julia]

Notice the hyphen after "(Betw)".

Graphical notation

In the graphical notation, the arcs are simply labelled with numbers:

The last arc is unlabeled

Notice how the arc that has no number is the arc that points away from the relation. Recall that all of the arcs except the last one must point towards the relation, while the last one must point away. Thus the last arc could be labelled with a "3" in this case, but we often simply leave it unlabelled, since it is uniquely identified by its pointing away from the relation.