Conceptual Graphs

A graphical representation for logic.
Full first-order logic plus metalanguage capabilities.
Same model-theoretic semantics as the Knowledge Interchange Format (KIF).
Same expressive power: Anything represented in CGs or KIF can be translated to a logically equivalent form in the other.

Example: A cat is on a mat.

Display form for CGs:
Conceptual graph interchange form (CGIF):
```
[Cat: *x] [Mat: *y] (On ?x ?y)
```

KIF: Formally equivalent to CGIF.

(exists ((?x Cat) (?y Mat)) (On ?x ?y))

Boxes are called concepts, and circles are called conceptual relations. The default quantifier for each concept is the existential, which says that something of the specified type exists.

Each conceptual relation has one or more arcs. In KIF and CGIF the arcs are represented sequentially by a list of variables (KIF) or coreference labels (CGIF), prefixed with a question mark. In KIF, the quantifier ("exists" or "forall") and its associated "sort", such as Cat or Mat, corresponds to a declaration in a programming langage. In CGIF, an asterisk in front of a coreference label declares the concept in which the quantifier and type are associated with the correference label.

In the display form, the arcs are numbered from 1 to some upper limit n, which depends on the relation type. Alternatively, the first arc may be shown as an arrow pointing toward the circle, and the n-th arc may be shown as an arrow pointing away from the circle.

Example: Every cat is on a mat.

CG display form:
CGIF:
```
[Cat: @every*x] [Mat: *y] (On ?x ?y)
```

KIF:

(forall ((?x Cat)) (exists ((?y Mat)) (On ?x ?y)))

The universal quantifier is indicated by a symbol, such as an upside-down A in the display form or by @every in CGIF. By default, universal quantifiers have precedence over the existential quantifiers. If necessary, special concept boxes called contexts may be used to delimit the scope of quantifiers.

Example: A person is between a rock and a hard place.

CG display form:

CGIF:

[Person *x] [Rock *y] [Place *z] [Hard *w]
     (betw ?y ?z ?x) (attr ?z ?w)

KIF:

(exists ((?x person) (?y rock) (?z place) (?w hard))
        (and (betw ?y ?z ?x) (attr ?z ?w)))

The first two arcs of the Betw relation are numbered to distinguish them, and the last (third) arc is distinguished by the arrow pointing away from the circle. The arrow on the third arc may be replaced by the number 3.

Example: John is going to Boston by bus.

CG display form:

CGIF:

[Person: 'John' *x]  [City: 'Boston' *y]  [Bus: *z]  (GoR3 ?x ?y ?z)

KIF:

(exists ((?x Person) (?y City) (?x Bus))
        (and (Name ?x 'John) (Name ?y 'Boston) (GoR3 ?x ?y ?z)))

In logic, many different conventions are used for representing the concepts expressed by verbs. For some purposes, the simplest choice is to represent a verb by a relation with one arc or argument for each participant. Unfortunately, this solution cannot be easily generalized to handle all the options that may occur. For example, the sentence John is going would require a monadic relation, John is going to Boston would require a dyadic relation, and John is going to Boston by bus at noon would require a tetradic relation.

Example: John is going to Boston by bus.

CG display form:

CGIF:

[Go: *x] [Person: 'John' *y] [City: 'Boston' *z] [Bus: *w]
   (Agnt ?x ?y) (Dest ?x ?z) (Inst ?x ?w)

KIF:

(exists ((?x Go) (?y Person) (?z City) (?w Bus))
        (and (Name ?y John) (Name ?z Boston)
             (Agnt ?x ?y) (Dest ?x ?z) (Inst ?x ?w)))

This representation treats verbs and nouns on an equal footing: the verb go is represented by a concept type Go, which is treated in the same way as the concept types for representing nouns. The relations named Agnt, Dest, and Inst represent the thematic roles of agent, destination, and instrument, which are commonly used in linguistics. With such relations, arbitrarily many participants and qualifiers can be linked to the same concept.

Defining Relations by Lambda Expressions

The relation GoR3 is defined by a lambda expression.

A definition is a metalevel statement that associates a name with a definition of the entity it names. In this example, the Def relation associates the relation name GoR3 with a triadic lambda expression, which defines the corresponding relation. The concept of type LambdaExpression contains a nested conceptual graph, in which the Greek letter lambda is used to mark three of the concepts as formal parameters. The rule of lambda expansion allows any graph that contains a relation of type GoR3 to be expanded to a graph with a concept of type Go linked to relations of types Agnt, Dest, and Inst. The inverse rule of lambda contraction allows any graph with a concept of type Go linked to three relations of type Agnt, Dest, and Inst to be contracted to a graph with a relation of type GoR3. Equivalent definition techniques and rules for expansion and contraction are available in CGIF and KIF.

Example: Tom believes Mary wants to marry a sailor.

CG display form:

CGIF:

[Person: *x1 'Tom'] [Believe *x2] (Expr ?x2 ?x1)
   (Thme ?x2 [Proposition:
      [Person: *x3 'Mary'] [Want *x4] (Expr ?x4 ?x3)
         (Thme ?x4 [Situation:
            [Marry *x5] (Agnt ?x5 ?x3) (Thme ?x5 [Sailor]) ]) ])

KIF:

(exists ((?x1 person) (?x2 believe))
   (and (name ?x1 'Tom) (expr ?x2 ?x1)
        (thme ?x2
           (exists ((?x3 person) (?x4 want) (?x8 situation))
              (and (name ?x3 'Mary) (expr ?x4 ?x3) (thme ?x4 ?x8)
                   (dscr ?x8 (exists ((?x5 marry) (?x6 sailor))
                                (and (Agnt ?x5 ?x3) (Thme ?x5 ?x6)))))))))

In this example, the concepts of type Proposition and Situation represent contexts that contain nested conceptual graphs. The context boxes delimit the scope of quantifiers and other logical operators. The sailor, whose existential quantifier occurs inside the context of Mary's desire, which itself is nested inside the context of Tom's belief, might not exist in reality.

The dotted line from the concept [Person: Mary] to the concept [T], which is called a coreference link, shows that the inner concept [T] has the same referent as concept to which it is linked. In CGIF, the coreference link corresponds to a pair of coreference labels that associate the defining node [Person: Mary *x] with a bound node [T: ?x]. The type T, which represents the most general type at the top if the type hierarchy, is true of everything; therefore, a node such as [T: ?x] can be simplified to [?x] or just ?x in the CGIF notation.

Example: There is a sailor that Tom believes Mary wants to marry.

CG display form:

CGIF:

[Person: *x1 'Tom'] [Sailor: *x6] [Believe *x2] (Expr ?x2 ?x1)
   (Thme ?x2 [Proposition:
      [Person: *x3 'Mary'] [Want *x4] (Expr ?x4 ?x3)
         (Thme ?x4 [Situation:
            [Marry *x5] (Agnt ?x5 ?x3) (Thme ?x5 ?x6) ]) ])

KIF:

(exists ((?x1 person) (?x6 sailor) (?x2 believe))
   (and (name ?x1 'Tom) (expr ?x2 ?x1)
        (thme ?x2
           (exists ((?x3 person) (?x4 want) (?x8 situation))
              (and (name ?x3 'Mary) (expr ?x4 ?x3) (thme ?x4 ?x8)
                   (dscr ?x8 (exists ((?x5 marry)
                                (and (agnt ?x5 ?x3) (thme ?x5 ?x6)))))))))

In this example, the sailor is mentioned outside of any nested clauses. In the corresponding logic, the concept [Sailor] or the existential quantifier for ?x6 has also been moved outside the nested contexts. Therefore, a particular sailor is presumed to exist in the actual world.

Another possibility, represented by the sentence Tom believes there is a sailor that Mary wants to marry, could be represented by moving the concept [Sailor] or the corresponding quantifier into the middle context, which represents Tom's belief.

Why Graphs?

Readability: Graphs reduce the number of variables by showing connections directly.
Different algorithms:
Some algorithms are more efficient on graphs.
Some algorithms are more efficient on linear forms.
Ability to mix and match tools that take advantage of different structural properties.
More natural for certain applications:
Map cities to nodes and highways to arcs.
Show flow through programs, electrical wiring, and plumbing.
Direct mapping to computer networks.

International User Community

International Conferences on Conceptual Structures (ICCS)
Held annually since 1993 in Canada, United States, Australia, France, and Germany.
ICCS 2001 at Stanford from July 30 to August 3:
http://www.ksl.stanford.edu/iccs2001/
ICCS 2002 will be held in Bulgaria.

Bibliography

Chein, Michel, ed. (1996) Revue d'Intelligence artificielle, Special Issue on Conceptual Graphs, vol. 10, no. 1.
Eklund, Peter W., Gerard Ellis, & Graham Mann, eds. (1996) Conceptual Structures: Knowledge Representation as Interlingua, Lecture Notes in AI 1115, Springer-Verlag, Berlin.
Ellis, Gerard, Robert A. Levinson, William Rich, & John F. Sowa, eds. (1995) Conceptual Structures: Applications, Implementation, and Theory, Lecture Notes in AI 954, Springer-Verlag, Berlin.
Ganter, Bernhard, & Guy W. Mineau, eds. (2000) Conceptual Structures: Logical, Linguistic, and Computational Issues, Lecture Notes in AI 1867, Springer-Verlag, Berlin.
Hansen, Hans Robert, Robert Mühlbacher, & Gustaf Neumann (1992) Begriffsbasierte Integration von Systemanalysemethoden, Physica-Verlag, Heidelberg. Distributed by Springer-Verlag.
Lukose, Dickson, Harry Delugach, Mary Keeler, Leroy Searle, & John Sowa, eds. (1997) Conceptual Structures: Fulfilling Peirce's Dream, Lecture Notes in AI 1257, Springer-Verlag, Berlin.
Nagle, T. E., J. A. Nagle, L. L. Gerholz, & P. W. Eklund, eds. (1992) Conceptual Structures: Current Research and Practice, Ellis Horwood, New York.
Nogier, Jean-François (1991) Génération automatique de langage et graphes conceptuels, Hermès, Paris.
Mineau, Guy W., Bernard Moulin, & John F. Sowa, eds. (1993) Conceptual Graphs for Knowledge Representation, Lecture Notes in AI 699, Springer-Verlag, Berlin.
Mugnier, Marie-Laure, & Michel Chein, eds. (1998) Conceptual Structures: Theory, Tools, and Applications, Lecture Notes in AI 1453, Springer-Verlag, Berlin.
Pfeiffer, Heather D., & Timothy E. Nagle, eds. (1993) Conceptual Structures: Theory and Implementation, Lecture Notes in AI 754, Springer-Verlag, Berlin.
Rassinoux, Anne-Marie (1994) Extraction et Représentation de la Connaissance tirée de Textes Médicaux, Éditions Systèmes et Information, Geneva.
Schröder, Martin (1994) Erwartungsgestützte Analyse medizinischer Befundungstexte: Ein wissensbasiertes Modell zur Sprachverarbeitung, Infix-Verlag, Sankt Augustin.
Sowa, John F. (1976) "Conceptual graphs for a database interface," IBM Journal of Research and Development, vol. 20, no. 4, pp. 336-357.
Sowa, John F. (1984) Conceptual Structures: Information Processing in Mind and Machine, Addison-Wesley, Reading, MA.
Sowa, John F., ed. (1992) Knowledge-Based Systems, Special Issue on Conceptual Graphs, vol. 5, no. 3, September 1992.
Sowa, John F. (2000) Knowledge Representation: Logical, Philosophical, and Computational Foundations, Brooks Cole Publishing Co., Pacific Grove, CA.
Stumme, Gerd, ed. (2000) Working with Conceptual Structures: Contributions to ICCS'2000, Shaker-Verlag, Aachen.
Tepfenhart, William, and Walling Cyre, eds. (1999) Conceptual Structures: Standards and Practices, Lecture Notes in AI 1640, Springer-Verlag, Berlin.
Tepfenhart, William M., Judith P. Dick, and John F. Sowa, eds. (1994) Conceptual Structures: Current Practice, Lecture Notes in AI 835, Springer-Verlag, Berlin.
Way, Eileen C. (1991) Knowledge Representation and Metaphor, Kluwer Academic Publishers, Dordrecht.
Way, Eileen C., ed. (1992) Journal of Experimental and Theoretical Artificial Intelligence (JETAI), Special Issue on Conceptual Graphs, vol. 4, no. 2.

This is a revised version of a presentation by John F. Sowa at the meeting of ISO SC32 WG2 on 3 April 2001.

Last Modified: