Conceptual Graphs


Conceptual Graphs (CGs) - or Conceptual Structures - are a Knowledge Representation Language.
Click here to go to the official CG site and here for John Sowa's Conceptual Graph site.
Below is an informal description of my own.


Informal description

Conceptual Graphs (CGs) are labelled graphs where "concept" nodes are connected by "relation" nodes.

Simple CGs and the specialization relationship between them

In "simple CGs", each node label is composed of a type and a generic/individual referent (the generic referent is noted '*' and may be implicit in the CG graphical or linear notation).

A simple CG may be translated in an existential conjunctive and positive formula of first order logic. Here is an example of a CG in a linear form, followed by its first order logic interpretation:

  [Repair]-
        { (Agent)->[Person: John];
          (Object)->[Car: *]->(Owner)->[Person: John];
        }.
  Exists x, Exists y, Repair(x) and Person(John) and Car(y) and
                      Agent(x,John) and Object(x,y) and Owner(y,John).

The type used for concepts (like Person or Person) and relations (such as Owner and Agent) must be declared or defined in an "ontology", i.e. a formal vocabulary where the terms may be have associated contraints (e.g. signatures for the relation types) and definitions (e.g. definitions by necessary and/or sufficient conditions) and thus may be linked to other terms by different relations (e.g. given or calculated subsumption relations).

The two sets of usable concept types and relation types may be ordered in a partial order (subsumption) relation, thus implying a partial order (specialization or implication) relation between CGs. For example, the above CG is a specialization of each of following ones:

  [Repair]->(Agent)->[Person: John].
  [Repair]->(Binary_Relation)->[Physical_entity: *x].

More complex CGs

More expressive CGs may be built using more labels in the nodes, e.g. for representing sets, context, and incertaincy, but these "complex CGs" cannot be compared using the specialization relation between simple CGs. Other matching or ordering relations have to be defined. Here is a CG which may be built to represent the sentence "John has not repaired two cars today":

  (Not)<-[Proposition: p12
              [Time:today]<-(PTIM)<-[Proposition: p13
                                          [Repair]-
                                                { (Agent)->[Person: John];
                                                  (Object)->[Car: {*}@2];
                                                }
                                    ] 
         ].

WebKB can store and retrieve simple CGs but also contextualised (i.e. embedded) simple CGs: the query has to be a simple CG but when a simple CG is retrieved, it is presented with its contextualisation. For example, the CG above would be retrieved with any of the following queries.

  spec [Repairing].
  spec [Repairing]->(Agent)->[Person].
  spec [Situation]->(Time)->[Time: today].

Type definitions

Definitions with necessary and/or sufficient conditions or typical conditions, may also be associated with types. For example, the sentences "A car mechanic is someone who often repairs cars" and "Repairing a car often soils and involves a spanner and a jack". could respectively be represented in the following ways:

  NSC for Car-mechanic (x) are [Repair]-
                                    { (Agent)->[Person: *x];
                                      (Object)->[Car: {*}];
                                      (Frequency)->[Frequency: often];
                                    }.

  TC for Repair (x) is
     [Repair: *x]-
            { (Succ)<-[Situation]->(Descr)->[Proposition: p13
                           (Not)<-[Proposition: p14 [Car: *c]->(Attr)->[Functionning] ]
                                              ];
              (Succ)->[Situation]->(Descr)->[Proposition: p15
                                                    [Car: *c]->(Attr)->[Functionning]
                                                    [Person: *p]->(Attr)->[Dirty]
                                              ];
              (Agent)->[Person: *p];
              (Object)->[Car: *c];
              (Instrument)->[Spanner];
              (Instrument)->[Jack];
            }.

  Notes: a) in these definitions, the concepts which use the x variables are
            universally quantified;
b) the variables c and p are used for linking identical concepts.

WebKB accepts such definitions but does not use the definitions by necessary and sufficient conditions for automatically structuring the type hierarchies.


Examples of Applications

The graph-based structure of CGs recommends them for Information Retrieval (IR) and data discovery. For example, when a part of a CG specializes another CG, the two CGs can be joined to form a derived CG specializing both. There are many ways to define graph merging. For example, we define a "maximal join" as a join which "maximises" the number of matched nodes and then select a derived CG with a "minimal" number of concept and relation nodes. WebKB provide a command for such a join. For example, from the CGs: [Person:John]<-(Owner)<-[Car] and [Car]<-(Object)<-[Repair]->(Agent)->[Person:John], our maximal join would produce the CG:

[Repair]-
      { (Agent)->[Person: John];
        (Object)->[Car: *]->(Owner)->[Person: John];
      }.

Users of relational database query languages must understand the database structure, i.e. the exact names of the tables and their relations. The CG formalism can be used to exploit "search by content". For example, the specialization relation between CGs allows them, and the DEs they index, to be retrieved by specifying parts of their content with any supertype of the types they use. Additionally, if the calculation of the specialization relation takes into account type definitions, CGs may be retrieved even if their structure differs from the query structure --- provided there exists a specialization relation between the query and the CGs when type definitions have been fully expanded.

When a document element (DE) "d" is composed of other DEs, some of which have been represented by CGs, these CGs may be merged using a maximal join to produce a default representation for the DE "d". This technique is a key component of the method used by the IR system RIME. This technique can be used by the WebKB users for easing their representation of the content of a document.

Knowledge retrieval and merging may also guide knowledge modeling and DE indexation. As an example in the legal domain, CGs including concepts of types (or specializing the types) "Legally-separated" or "Bankrupt-parterships" could be automatically retrieved and merged. The result may then serve as a guide to define the concept type "bankrupt partnerships between legally separated individuals". Then the CGs specializing this type definition could be automatically updated to use this new type. If these CGs indexed DEs, these DEs are now also accessible via queries using this new type.

When no results can be found for a query -- there is no exact match -- queries could be generalized to provide approximate results, e.g. by using only a part of the query or by using CGs which are supertypes of the query. This technique is used in ROCK but not in WebKB.



Philippe A. MARTIN, Griffith University, School of Information Technology, Australia
E-mail: pm .@. phmartin dot info

Last modified: Fri Jul 9 12:43:06 EST 1999