Compiling Conceptual Graphs.
AbstractThis paper addresses problems in conceptual graph implementation: subsumption and classification in a taxonomy. Conceptual graphs are typically stored using a directed acyclic graph data structure based on the partial order over conceptual graphs.We give an improved algorithm for classifying conceptual graphs into this hierarchy. It prunes the search space in the database using the information gathered while searching.We show how conceptual graphs in this hierarchy can be compiled into instructions which represent specialized cases of the canonical formation rules. This compiles subsumption of conceptual graphs and compresses knowledge in a knowledge base. Conceptual graphs are compiled as differences between adjacent graphs in the hierarchy. The differences represent the rules used in deriving the graph from the adjacent graphs. We illustrate how the method compresses knowledge bases in some experiments.Compilation is effected in three ways: removal of redundant data, use of simple instructions which ignore redundant checks when performing matching, and by sharing common processing between graphs.
Introduction
A central element of many natural language processing,
information retrieval, and knowledge based systems is a
large collection of information. This information may be
viewed as a large set of sentences. This paper concentrates
on the problem of answering queries on this set of sentences.
A query is a sentence. The question is whether the sentence
is implied by the set of sentences. Sentences that imply the
query sentence may be extracted as answers. This paper
discusses methods which seek answers which are explicit
sentences in the collection, rather than answers that can be
deduced from more than one sentence in the collection. The
method has been designed with the intention of extending
to handle the latter case in the future.
For example the query "Is there a person eating pie?" on
a set of sentences may extract the answers "A girl is eating
pie fast" and "A girl, Sue, is eating pie in the kitchen".
This example illustrates that there is typing information
embedded in the sentences. When searching for sentences
that imply something about people, sentences containing
information about the subtype girls were considered.
The research of G. Ellis was supported by a University of Queensland
Postgraduate Scholarship while enrolled in the PhD programme at Key
Centre for Software Technology, University of Queensland, QLD, 4072,
Australia. He is currently with the Dept. of Computer Science, Royal
Melbourne University of Technology, Victoria 3001, Australia. This work
was also supported by the Baskin Center at the University of California,
Santa Cruz, USA, during a visit there.
This paper is not concerned with the natural language
front-end of this system, rather, it concentrates on work at
the internal level where sentences are encoded in the conceptual
graph knowledge representation [14]. The knowledge
base is a set of conceptual graphs, each graph representing
a sentence. Queries are conceptual graphs which
are checked for subsumption against graphs in the knowledge
base.
The method outlined here constructs a directed acyclic
graph representing the partial order over conceptual graphs.
Nodes of the hierarchy are conceptual graphs. Querying
the set of graphs is achieved by selecting paths through
the hierarchy. By using the ordering information in the
hierarchy many of the graphs in the knowledge base are
eliminated from consideration in the search. The hierarchy
is a content addressable memory. The content of the
query determine its position in the hierarchy. The solutions
are ordered in the subhierarchies of the immediate
specializations of the query.
Levinson [5] developed a method for chemical graphs on
which the method in this paper is based. In more recent
work [6], Levinson has adapted his method to conceptual
graphs and developed hybrid indexing mechanisms.
Garner and Tsui [4] added the idea of storing graphs as
the differences between adjacent graphs in the hierarchy.
This has the potential to save store.
The method described here takes the differences idea
further. In [4], a graph is reconstructed from the differences
when traversing the hierarchy. This graph is then
compared to the query by using a general subsumption
algorithm. Our method differs from this in a number of
ways. We use different differences, rather than the incident
arcs being labelled with the differences, we only label
the node representing the conceptual graph. The differences
are between a graph and all of its adjacent graphs,
rather than a single adjacent graph. This method is especially
suited to the topological search method proposed
by Levinson [6]. Another difference is the interpretation of
the differences. The differences between graphs represent
instructions which are specialized cases of the canonical
formation rules of conceptual graph theory. An instruction
performs part of the matching of the database graph
with the query graph. The canonical formation rules are
the basis of the partial ordering defined over conceptual
graphs. Rather than just reconstructing the graphs, the
differences are applied to the query graph using the mappings
of the adjacent graphs into the query graph. In many
cases if the adjacent graphs have already been compared
to the query, the differences need only be mapped into the
query graph to implement the comparison.
Our method achieves compilation of conceptual graphs
in three ways: removal of redundant data, use of simple
instructions which ignore redundant checks when performing
matching, and by sharing common processing between
graphs.
Section II introduces basic conceptual graph theory. Section
III outlines algorithms and data structures used to
store and retrieve conceptual graphs. Section IV explains
what we mean by compilation of conceptual graphs in the
generalization hierarchy. Section V gives descriptions of
instructions which are specialized cases of the canonical
formation rules. A small example database is compiled. A
query on the compiled database is then examined. Section
VI details some experiments on compressing some
knowledge bases, and discusses ramifications for compilation

II. What are Conceptual Graphs
Conceptual Graphs [14] is a system of logic based on
Charles Sanders Peirce's Existential Graphs [12]. Conceptual
graphs have the full power of first-order logic, can
represent modal and higher-order logic, and have simple
and elegant inference rules. Conceptual graphs also have a
direct translation into natural language. The following is
a short introduction to the basic formalism. The reader is
advised to read [14] for a more thorough understanding.
A conceptual graph is a finite, connected, bipartite graph.
The two kinds of nodes are concepts and conceptual rela-
tions. Every conceptual relation has one or more arcs, each
of which must be linked to some concept. A single concept
by itself may form a conceptual graph, but every conceptual
relation must be linked to some concept.
The function type maps concepts into a set T whose elements
are type labels. The function referent maps concepts
into a set I = f#1; #2; of individual markers
or the generic marker *. An individual marker is a surrogate
for some individual in the real world, a perceived
world, or a hypothetical world. The label of concept c,
lab(c), is the
and referent(c) = r. A concept may be displayed in the
linear form as For example, the concept [Person: *]
or more simply [Person] represents an unspecified person,
and may be read A person. A box replaces the square
brackets in the graphical form.
The partial order - over the type labels in T , known
as the type hierarchy, forms a lattice, called the type lat-
tice. The type hierarchy makes analytic statements about
types: they must be true by intension. The statement
Person is true, because the properties of a person
are also associated with a girl.
The minimal common supertype of a pair of type labels
s and t is written s [ t. The maximal common subtype
is t. There are two primitive type labels: the
universal type ? and the absurd type ?. For any type label
t, ?. The minimal common supertype of Cat
and Dog could possibly be Carnivore depending on the
hierarchy. The maximal common subtype of Pet and Cat
is PetCat. The maximal common subtype of Cat and Dog
is ? (absurd), which means that it is logically impossible
for an entity to be both a dog and a cat.
The denotation of type t, written ffi t, is the set of all
entities that are instances of any concept of type t. For
extensions, the union is the set of all cats and
dogs in the world and nothing else. For intensional type
labels, Cat [ Dog is their minimal common supertype Car-
nivore, which also has subtypes Bear, Weasel, Skunk, etc.
The type lattice represents categories of thought, and the
lattice of sets and subsets represents collections of existing
things. The two lattices are not isomorphic, and the denotation
operator that maps one into the other is neither
one-to-one nor onto.
The function type also maps conceptual relations to type
labels. A relation r with may be written (t) in
the linear form. A ellipse replaces the parenthesis in the
graphical form. For two relations to have the same type
they must have the same number of arcs. Concepts and
conceptual relations have no type in common.
The conformity relation :: relates type labels to individual
markers: if t :: i is true, then i is said to conform to type
t. The conformity relation obeys the following conditions:
ffl The referent of a concept must conform to its type
label: if c is a concept, type(c) :: referent(c). For
example the concept [Integer: 1] is well-formed, but
[Integer: 3.14] is not.
ffl If an individual marker conforms to type s, it must
also conform to all supertypes of s: if s - t and s :: i,
then t :: i. For example the number 3 conforms to the
type Prime, Prime::3. Hence it also conforms to the
supertype Integer, Integer::3.
ffl If an individual marker conforms to type s and t, it
must also conform to their maximal common subtype:
For example since 3
conforms to types Odd and Prime: Odd::3; Prime::3,
then 3 also conforms to their maximal common sub-type
OddPrime, OddPrime::3.
ffl Every individual marker conforms to the universal type
?; no individual marker conforms to the absurd type
?: for all i in I, ? :: i, but not ? :: i.
ffl The generic marker * conforms to all type labels: for
all type labels t, t ::  .
The operator OE maps conceptual graphs into formulas in
first order predicate calculus. For the conceptual graph
the translation is
Generic concepts map to variables, individual concepts map
to constants. Alternatively, conceptual graphs could also
be mapped into a modern typed logic
c
Girl Agent Eat Manner Fast
Person: Sue Agent Eat Object Pie
Fig. 1: Two canonical graphs
A. Canonical Graphs
To distinguish the meaningful graphs that represent real
or possible situations in the external world, certain graphs
are declared to be canonical. One source is the derivation
of new canonical graphs from other canonical graphs by
formation rules.
There are five canonical formation rules for deriving a
conceptual graph w from conceptual graphs u and v [14,11]:
copy(u). w is an exact copy of u.
ffl restrict(u; c; l). For any concept c in u, type(c) may
be replaced by a subtype t; if c is generic, its referent
may be changed to an individual marker i where
These changes are permitted only if referent(c)
conforms to type(c) before and after the change, that
is t :: i.
relations r and s in
the graph u are duplicates, then one of them may be
deleted from u together with all its arcs.
ffl Join(u; c; d). If a concept c in u is identical to a concept
d in u, then Join(u; c; d) is the graph obtained
by deleting d and linking to c all arcs of conceptual
relations that had been linked to d.
ffl Fuse(u; v; c; d). Let u and v be two disjoint conceptual
graphs. If a concept c in u is identical to a concept d in
v, then Fuse(u; v; c; d) is the graph obtained by deleting
d and linking to c all arcs of conceptual relations
that had been linked to d.
To illustrate the formation rules, Fig. 1 shows two canonical
graphs. Each concept and relation is identified with ci
and rj, respectively, and each graph is also labelled for
reference in the text. The graph b may be read A girl
is eating fast; and the graph c, A person, Sue, is eating
pie. These are not formal translations of the graphs, but
informal verbalizations for discussion of the graphs here.
The graph d in Fig. 2 shows the result of restricting the
concept c3 [Girl] in the graph b in Fig. 1 to [Girl: Sue].
The graph e is the result of restricting the type Person
in the concept c7 in graph c to type Girl. Before doing
the restrictions, the conformity relation must be checked
to ensure that Girl :: Sue is true.
The identical concepts c3 and c7 [Girl: Sue] in d and e
in Fig. 2 can be fused together to form a single graph x9 in
Fig. 3. Then the identical concepts c1, c5 [Eat] in x9 can
be joined together to produce x10.
In Fig. 3, the graph x10 can be simplified by removing
one of the duplicate relations r2 and r4 (Agent) resulting in
graph f in Fig. 4. Two conceptual relations of the same type
are duplicates if for each i, the ith arc of one is linked to the
Girl: Sue
Girl: Sue
d
e Agent Eat Object Pie
Fast
Manner
Eat
Agent
Fig. 2: Restriction of two graphs in Fig. 1
Girl: Sue
Girl: Sue
Agent Eat Manner Fast
Agent Eat Object Pie
Agent Eat Manner Fast
Pie
Object
Agent
Fig. 3: Join of the two graphs in Fig. 2
same concept as the ith arc of the other. The graph f may
be read A girl, Sue, is eating pie fast. The simplification
rule corresponds to the rule of logic that R(x; y) - R(x; y)
is equivalent to just R(x; y).
The formation rules are a kind of graph grammar for
canonical graphs. Besides defining syntax, they also enforce
certain semantic constraints. The formation rules
make no guarantee about truth or falsity. However, the
formation rules are refutation rules. If we assert that the
graph
is false (No person is eating a pie), then we can use the
formation rules to show that
is false (Sue is not eating a pie). That is if a graph can be
derived from a false graph, then it must in turn be false.
The formation rules are falsity preserving.
The canon contains the information necessary for deriving
a set of canonical graphs. It has four components: a
type hierarchy T , broken into a concept hierarchy T c and
relation hierarchy T r ; a set of individual markers I; a conformity
relation :: that relates labels in T to markers in I;
f Girl: Sue Agent Eat Manner Fast
Pie
Object
Fig. 4: Simplification of Fig. 3
Place
Location
Act
Entity
Act Object
Event
Act PhysicalObject
Animate
Entity
Give Animal
Pie
Girl
Person
Attribute
Eat
Fast
Place
Kitchen Food
Girl::Sue
Manner Agent Object Location
Act
Act
Agent
Manner Attribute
Animate
Fig. 5: A sample canon
and a finite set of conceptual graphs B, called the canonical
basis, with all type labels in T and all referents either
or markers in I. The canonical graphs are the closure of
B under the canonical formation rules. Fig. 5 shows the
canon used in this paper.
B. The Relationship between the Canonical Formation Rules
and Subsumption of Conceptual Graphs
If a conceptual graph u is canonically derivable from a
conceptual graph v (possibly with the join of other conceptual
wn ), then u is called a specialization of
v, written u - v, and v is called a generalization of u.
Generalization defines a partial ordering of conceptual
graphs called the generalization hierarchy. The ordering is
reflexive, transitive, and antisymmetric. For any conceptual
graphs u, and v, the following properties are true:
ffl Subgraph. If v is a subgraph of u, then u - v.
ffl Subtypes. If u is identical to v except that one or more
type labels of v are restricted to subtypes in u, then
ffl Individuals. If u is identical to v except that one or
more generic concepts of v are restricted to individual
concepts of the same type, then u - v.
ffl Top. The graph [?] is a generalization of all other
conceptual graphs.
The graphs in Figs. 1, 2, and 3 are all generalizations
of the graph in Fig. 4. We call the graphs defined so far
atomic conceptual graphs (ACGs). They do not contain
logical connectives and hence neither quantification other
than the default existential quantification, nor have we consider
definition of concepts and relations. A subsumption
test for ACGs can be implemented as subgraph morphism
modulo subtyping and individuation.
The generalization hierarchy is not a partial order over
conceptual graphs as stated in [14], rather it is a partial order
over equivalence classes of conceptual graphs. Consider
the graphs
The graph v is a proper subgraph of u. The graph u can be
derived from v by joining a copy of v on the concept [Eat],
Girl: Sue Agent Eat Manner Fast
Object
Pie
q3
d3
d1 q1 d4 q2 d2
Query u
Fig. query graph u
thus u - v. However, v can be derived from u by joining
the two identical concepts [Person], then simplifying the
duplicate (Agent) relations, thus v - u. Hence according
to the generalization hierarchy. This property of
the generalization hierarchy has also been noted independently
in [15].
If u - v, a canonical derivation of u from v corresponds
to the reverse of a proof of the formula OEv from the formula
conceptual graphs u and v, if u - v, then
OEu oe OEv. The result that the two graphs given in the
paragraph above are equivalent should not be surprising
considering their translations into sorted logic
This is a subtle point that doesn't affect any of the subsequent
theory of conceptual graphs. In practice, graphs
with redundant branches can always be simplified to derive
the smallest one in each equivalence class. Conceptual
graphs from now on are assumed to be the minimal element
of their class.
For any conceptual graphs u and v where u - v, there
must exist a mapping is a subgraph
of u called a projection of v in u. The projection operator
- has the following properties:
ffl For each concept c in v, -c is a concept in -v where
referent(-c).
ffl For each conceptual relation r in v, -r is a conceptual
relation in -v where If the ith arc
of r is linked to a concept c in v, the ith arc of -r must
be linked to -c in -v.
For example, the projection of graph c in Fig. 1 into the
graph u in Fig. 6 is
Person ? Girl and Act ? Eat.
A graph v can be represented by the set of instances of
the canonical formation rules used to construct the graph
v from the graphs w wn . To test if the graph v subsumes
a graph u, these rule instances can be applied to
the projections of u in w wn . The rule instances will
only succeed if v subsumes u. We use this technique to
compile conceptual graphs in a data structure representing
the generalization hierarchy partial ordering.
Now that we have the theory of atomic conceptual graphs
we will consider how to store large sets of conceptual graphs
and how to retrieve conceptual graphs once stored.
Animate Act
Agent Act Object Entity
Manner
Act Attribute
Girl: Sue Eat Manner Fast
AgentB
a
Manner Fast
Girl Eat
Agent Eat Object Pie
Girl: Sue Manner Fast
Eat
Pie
Object
Eat Object Pie
Girl: Sue Agent
c
c3 r2 c4
e
d
Agent
Person: Sue
Agent
f
Fig. 7: The generalization hierarchy of the graphs in Figs
III. Storing and Retrieving Conceptual Graphs
The common data structure used to store conceptual
graphs is a hierarchy; a directed acyclic graph representing
the non-transitive links of the partial ordering, generalization
hierarchy, over conceptual graphs [10,6,2,3]. Levin-
son's earlier work used a similar data structure for organizing
chemical graphs [5]. The taxonomy over KL-ONE
concept descriptions [13] is a hierarchy.
A. The Generalization Hierarchy as a Data Structure for
Storing Conceptual Graphs
The nodes in the generalization hierarchy are conceptual
graphs and the arcs represent the non-transitive ordering
between the graphs. In Fig. 7 the hierarchy is given for
the graphs from the previous section. The canonical basis
in this example consists of the set of graphs g.
The arc (b; d) indicates each of the following:
1. A girl, Sue, is eating fast is canonically derivable from
A girl is eating fast.
2. A girl, Sue, is eating fast implies A girl is eating fast.
3. A girl is eating fast is a generalization of A girl, Sue,
is eating fast.
4. A girl, Sue, is eating fast is a specialization of A girl
is eating fast.
In the following sections we examine how to use the hierarchy
for searching a set of conceptual graphs and how
to construct the hierarchy.
B. Searching for a Conceptual Graph in the Generalization
Hierarchy
The generalization hierarchy indexes the knowledge base.
When we apply a conceptual graph query u to the knowledge
base we search for u in the hierarchy. The hierarchy
is a content addressable memory.
Fig. 8 illustrates the search space for a query u in a
hierarchy. Atoms or Primitives are the graphs closest to
objects unifiable with u
coatoms
(bottom object)
atoms (primitives)
(top object)
objects more general than u
objects more specific than u
objects non-unifiable with u
Fig. 8: The search space for the graph u in a generalization
hierarchy
the concept [?], which are not derivable from any other
graphs. Coatoms are the leaf nodes of the knowledge base.
The generalization space contains all the generalizations
of u in the hierarchy. The specialization space or solution
space contains all the specializations of u in the hierar-
chy. Immediate generalizations (Parents) and immediate
specializations (Children) of u are adjacent generalizations
and specializations of u respectively.
In Fig. 8, u is explicitly stored in the hierarchy. How-
ever, in many cases u will not be stored in the hierarchy
explicitly. The search for u can proceed in two directions:
top-down, from the graph [?] to u or bottom-up, from the
coatoms to u. The methods we examine here search top-down

Consider a depth-first search of the generalization space.
Any path in the generalization space can be taken as they
all lead to u in the hierarchy. Consider searching for the
query u
[Girl: Sue]/(Agent)/[Eat]!(Object)![Fast]?
Is the girl, Sue, eating fast, in the hierarchy in Fig. 7. The
query u matches the graph d in the hierarchy. The search
starts at the graph [?]. To find the graph search from the
children of [?] for a generalization of u. The children of v
is the set of immediate specializations of v. The children
of a, B1, B2, B3, b, c, d, e, and f are fB1, B2, B3g, fbg,
fb, cg, fcg, fdg, feg, ffg, ffg, and fg respectively.
In a depth-first search we could select the first graph in
the children which is a generalization of the query u as a
continuation in the path to u. The basis graph B1 is a generalization
in the first children set, so we select it. So are
B2 and B3, so they could equally be chosen. There is only
one child of B1, b, which is also a generalization, so we select
it. We now search the children of b for a generalization.
The graph d is the only child and it is a generalization of u.
In fact d is isomorphic to u. The query graph is matched
so the search terminates successfully. In this case there are
two solutions fd, fg. The English answers to the question
Agent Eat
Person Eat Object Pie
Location Kitchen
Agent Eat
Person
Object Food
Object
Location Kitchen
Agent Eat
Girl: Sue
Pie Object
Agent Eat
Pie
Girl Manner Fast
f
e
c
a
d
Fig. 9: A generalization hierarchy
Is the girl, Sue, eating fast? are d - yes; and f - yes, Sue is
eating pie fast.
The search does not necessarily start from the graph [?].
Indexing techniques can be used to start further down the
generalization space. The ultimate goal of indexing techniques
is to index directly to the top of the specialization
space which includes u (see [8] for indexing techniques).
C. Inserting a Conceptual Graph into the Generalization
Hierarchy: Classification
To insert a graph u into the hierarchy we need to compute
the set of immediate generalizations and the set of
immediate specializations of u in the hierarchy. This information
gives us the virtual location for inserting u.
Consider inserting the graph
read A person is eating pie, into the hierarchy in Fig. 9.
The immediate generalizations in this case are b, A person
is eating, and c, A pie is being eaten. The immediate specializations
are f, A girl, Sue, is eating pie in the kitchen,
and e, A girl is eating pie fast. Notice that d, A person
is eating food in the kitchen, and u are incomparable. To
insert u we remove the arcs (b, e), (c, e), and (c, f), then
add (b, u), (c, u), (u, f) and (u, e) to get the new hierarchy
in Fig. 10.
D. Searching the Generalization Space
Woods [16] describes the standard two phase breadth-first
search used for classification of KL-ONE like terms in
a taxonomy. The first phase calculates the set of immediate
predecessors, IP (generalizations), of the query by
breadth-first search of the generalization space. The second
phase breadth-first searches the subhierarchies of the
immediate predecessors calculated from the first phase, the
first specializations encountered in the hierarchies are the
immediate successors, IS, of the query.
Woods [16] in summarizing research on classification says
"More sophisticated algorithms can and should be devel-
oped."
Agent Eat
Person Eat Object Pie
Location Kitchen
Agent Eat
Person
Object Food
Object
Location Kitchen
Agent Eat
Girl: Sue
Pie Object
Agent Eat
Pie
Girl Manner Fast
Agent Eat
Person Object Pie
e
c
a
d
Fig. 10: The generalization hierarchy in Fig. 9 after inserting
In [6], Levinson describes algorithms which show deeper
insights into the problem. Subsumption can in general be
an expensive operation. Hence methods of classification
that avoid as many subsumption tests as possible are de-
sirable. The algorithm given here for inserting an object
into a hierarchy improves the implementation of Levinson's
method, but does the same number of graph comparisons
in each phase.
procedure insert(u)
begin
IP := immediate predecessors(u);
if IP 6= fug then
begin
IS := immediate successors(IP , u);
insert(u, IP , IS)
Fig. 11: Insert u in a partial order
Consider the algorithm for insert in Fig. 11. The first
phase of computing the immediate predecessors, IP , is
done by the function immediate predecessors(u) in Fig. 13.
If u is already stored in the hierarchy, u is returned rather
than u's immediate predecessors and the second phase is
avoided. Otherwise the subhierarchies of the members of
IP are searched using immediate successors(IP , u) in
Fig. 14. Once the sets IP , and IS are found then the
procedure insert(u, IP , IS) in Fig. 12 does the necessary
housekeeping linking u to immediate predecessors and immediate
successors. The procedure also maintains levels
of graphs in the hierarchy. This information is used to
traverse the hierarchy in topological order.
Levinson [6] pruned the search space using the fact that
a graph is only in the generalization space (generalizations
of the query u) if all of its immediate predecessors are also
in the generalization space. Levinson does this by sorting
the hierarchy by size of the graphs and traversing the hierarchy
in this order. Size was a necessary requirement for
procedure insert(u, IP , IS)
begin
for each v 2 IP do
for each w 2 IS do remove (v; w) if present;
for each v 2 IP do add (v; u);
for each w 2 IS do add (u; w);
u.level :=
propagate level(IS)
Fig. 12: Insert u in the partial order, given its neighbourhood
IS).
ordering the kinds of graphs that Levinson was working
with. However, for conceptual graphs size is not a necessary
requirement.
Topological order is the level order of a hierarchy. This
is reflected for each node by the distance the node is from
the top. For example, in Fig. 9 the graph a is on level 0,
graphs b and c are on level 1, graphs d and e are on level
2, and graph f is on level 3.
To see why topological order is a more efficient search
method than depth-first or breadth-first search in terms of
avoiding comparing objects in the hierarchy consider the
hierarchy in Fig. 9. Remember that all immediate predecessors
of a graph must be compared before that graph.
The immediate predecessors of the graph must be generalizations
of the query if the graph is also a generalization.
Assume the query is u in Fig. 10, and hence the generalizations
of u are a, b, and c. A breadth-first traversal of
the hierarchy in Fig. 9 (reading right to left): a, c, b, e,
f, d; would compare f. A depth-first traversal (from right
to left) would be fa, c, e, f, b, dg, also comparing f. A
topological traversal (also reading right to left): a, c, b, e,
d, f; would not compare f, since d is encountered beforehand
and is noted as being incomparable to u. Topological
search ensures that all predecessors of an element v are
seen before v.
In the algorithm in Fig. 13, the level information associated
with each graph in the hierarchy is used traverse
the hierarchy in topological order. The queue used for this
modified breadth-first search is a minimum priority queue.
Priority is given to elements with the smallest level num-
ber. Using an array of FIFO queues we can enqueue and
dequeue from this priority queue in constant time. Enqueuing
the weighted element (i; u) involves adding u to
the front of the ith queue. Dequeuing involves removing
the first element on the current minimum weighted queue.
Whenever the current minimum queue j becomes empty
the (weight) index is incremented. Traversing the hierarchy
by level order maintains the property that the j
FIFO is necessarily non-empty at this point.
The sets IP (v) and IS(v) correspond to the stored sets
of immediate predecessors of v and immediate successors
of v, respectively, where v is already stored in the hierar-
function immediate predecessors(u)
begin
Q.enqueue(level(?), ?)
while not Q.empty() do
begin
predecessors match(v) -u - v) then
begin
for each w 2 IP (v) do
IP
IP
for each w 2 IS(v) do
return IP
Fig. 13: Find the immediate predecessors of u
chy. In the algorithm the call to subsumption u - v is
guarded by the test predecessors match(v). The topological
traversal guarantees that all v's predecessors are seen
before v. The predicate predecessors match(v) is true if
all of vs predecessors are predecessors of the query u. In
depth-first search the object v is compared if v is has an
immediate predecessor which is a predecessor of the query
u. In breadth-first search an object v is compared to u
if one or more (but not necessarily all) of v's immediate
predecessors are predecessors of u. Thus the precondition
for checking if v is a predecessor of the query u is stronger
in a topological search. If v is a predecessor, add it to the
set IP , and remove all of v's immediate predecessors from
IP , then search the successors of v for closer predecessors
of the query.
E. Searching the Specialization or Solution Space
In the second phase Woods [16] searches one of the sub-hierarchies
of the immediate predecessors from the first
phase. Only one of the hierarchies needs to be traversed,
since any specialization of the query must also be a specialization
of a generalization of the query. When a specialization
is found it is added to the set IS and its subhierarchy
is removed from consideration. However, if a graph is incomparable
its subhierarchy must be traversed.
Levinson [6] devised a method of avoiding many of the
comparisons that are inherent in traversing a particular
subhierarchy in the second phase. Notice Wood's method
does not use any of the information about the other members
of IP . Levinson [6] noted that in the second phase for
any database graph to be a successor of the query graph it
must be in the intersection of the subhierarchies of the immediate
predecessors from the first phase. If subsumption
tests are relatively expensive compared to pointer traversal
involved in walking the subhierarchy, this is particularly
useful. The intersection is computed by traversing each of
the subhierarchies incrementing a counter for each graph.
For any graph to be in the intersection it must have a count
equal to the number of elements of IP . This intersection is
then traversed in the breadth-first manner used by Woods
above.
In the algorithm for immediate successors in Fig. 14 we
avoid this multiple traversal by computing the intersection
incrementally in one constrained topological search. The
algorithm uses the insight that for a graph to be in the intersection
of the subhierarchies of IP the graph must have
a path to each of those elements of IP . If each element of
the set IP is represented with a bit, the immediate successors
of elements of IP which have paths to all elements can
be determined by ORing the bit strings of their immediate
predecessors. By propagating this information we can restrict
subsumption testing to graphs that have all bits set
(in the intersection space). This algorithm also relies on
the level (topological) traversal implemented by the minimum
priority queue. The predicate IP reachable(v) ORs
the bit strings of vs immediate predecessors and is true if
all bits are set.
function immediate successors(IP , u)
begin
for each v 2 IP do
begin
for each w 2 IS(v) do
while not Q.empty() do
begin
if not seen(v) then
begin
if (IP reachable(v) -v - u) then
begin
see successors(v);
IS
else
for each w 2 IS(v) do
return IS
Fig. 14: Find the immediate successors of u given the immediate
predecessors
Notice that for each insert the "seen" information must
be reinitialised. This would mean the algorithm would perform
linearly in the size of the database in every case. This
can be avoided by using a token for each query. For a graph
to be seen it must have the same token as the current query.
If we consider the query graph u in the classification
problem as a query on the database of graphs in the hi-
erarchy, then solutions to the query would be everything
that implied the query: the specialization space. These
solutions can be listed by walking the subhierarchies of elements
of IS. The same support algorithms used in insert
for finding the immediate predecessors and immediate successors
can also be used for querying.
In the worst case these algorithms perform no better
than comparison of the query to each of the graphs in
the database. These methods are not suited to databases
where: there is little ordering information; or for total or-
ders, where the hierarchy is a chain. The methods are
suited for wide shallow hierarchies of data. We believe that
many of the domains that conceptual graphs are intended
to be used in do have this property. Woods [16] argues
that the typical-case complexity is logarithmic in the size
of the database, and Levinson [6] gives empirical evidence
to support this argument.
Levinson proved that his topological methods do less
comparison of graphs than previous known methods [6].
Levinson [6] also describes an indexing scheme which is a
hybrid of the above method. The method is particularly
useful for graphs with high degree of symmetry. Also see
[8] for its application to conceptual graphs.
We have shown how to prune the search within the
database down to the generalization and specialization space.
In the following section we show how to share matching
information gained from subsumption testing between related
graphs.
IV. Compilation of Conceptual Graphs
in the Generalization Hierarchy
How can the efficiency of querying the database be im-
proved? In the previous sections we saw a method for minimizing
the number of database graphs compared to the
query graph. In the following sections we look at minimizing
the cost of each of these comparisons. We examine how
to represent conceptual graphs in a generalization hierarchy
to improve individual subsumption tests.
Woods [16] states about his algorithm "No deep insights
have been exploited to gain efficiency. For example, in clas-
sification, no advantage is taken of what might be learned
in the course of one subsumption test that might be redundant
with part of another subsumption test."
Garner and Tsui [4] proposed representing graphs as differences
between adjacent graphs in the generalization hier-
archy. Fig. 15 illustrates how they stored the graph
girl, Sue, eating pie fast" as the difference from the adjacent
generalization "A girl eating food". The difference
means replace the referent of the concept c1
in u with Sue. The difference c2 ! "!(Manner)![Fast]"
means to connect a new binary relation (Manner) to the
concept c1 in u and a new concept [Fast]. The difference
means replace the type of the concept c3 in u
with the type Pie.
A difference between Garner and Tsui's method and the
Girl Eat Object
Agent
Fast
Eat
Manner
Object
Girl: Sue Pie
Agent
Girl Eat Object
Agent Food
c3 -> "Pie:"
Food
Transformed to:
Fig. 15: Representing graphs as differences from a generalization
method outlined below is that the former method places
the difference between adjacent graphs on the incident arc,
whereas the latter places differences between a graph and
all its immediate generalizations in the node representing
the graph. The graph differences in Garner and Tsui's
method are the nodes, arcs, and restrictions in the specialization
that are not in the generalization. The graph
differences are treated as data, reconstructing graphs by
traversing the arcs, and hence adding the graph differences.
Reconstructed graphs are then compared with the query
using a general matching algorithm. This method does not
compile the graphs into matching instructions, nor does it
share common computation in queries.
Storing graphs as differences fulfills our aim of removing
redundant data from the database. Another aim of
our method is to share common computation. This can be
achieved by storing mappings between the adjacent graphs,
in conjunction with the differences. As we will see the mappings
do not have to be stored explicitly, but can be com-
posed. This allows us to fulfill another aim: to represent the
differences in such a way that they may be used as instructions
for a future conceptual graph unification machine. A
graph may be compared to a query using the mappings of
generalizations into the query, and instructions which perform
small parts of the general matching operation relative
to these mappings. The following details this alternative
to Garner and Tsui's method.
Consider the query u in Fig. 6 on the generalization hierarchy
in Fig. 7. In the discussion below the notation
- v!u represents the mapping -
are graphs. Let us assume that a subgraph morphism
- b!u of the graph b in Fig. 7 has been found in the query
u. In the search for solutions to the query u, the search
method, outlined in previous sections, takes paths through
the generalization hierarchy that contain more specialized
generalizations of the query at each step. The graph d is
the only choice in paths from b. To traverse this path d
must be compared to u to see if it is a generalization of
u. Can a full subsumption test be avoided? Notice that
the only difference between d and b is that the concept c3
with type Girl is restricted from the generic form to the
individual Sue.
To compute a match the mapping - d!u must be com-
puted. Assume that the mapping - b!d is stored in the
database and the generalization b has been mapped into
the query u, - b!u . For every concept and relation x in d:
x is in b then
x) is in - d!u ,
otherwise find a match for x in u, y, that does not violate
the rest of the match. Insert
The mapping - d!u is equal to the mapping - b!u , since
and the mapping - b!d is the identity mapping.
The difference could then be represented as
referent(- d!u
Sue, d is a generalization of u. In general, this is only
possible if there is no symmetry in the graphs involved, that
is, there are unique mappings between the graphs involved.
If this is not the case, then the differences must be applied
to each of the possible mappings. For many of the domains
in which conceptual graphs are used the graphs contain
unique morphisms.
Thus differences between graphs can be used, if mappings
between adjacent graphs (- b!d in the previous ex-
ample) and the current generalization b and the query u
are kept. It is not necessary to store the mapping
between each adjacent graph explicitly. The mappings
are composed when traversing the generalization hierarchy.
The canonical formation rules construct the mapping when
constructing the graphs. The copy rule sets up a mapping
of the whole graph that was copied. The restrict rule does
not affect the mapping. The join rule computes the union
of the mappings of the two graphs being joined, it then
maps one of the identical concepts to the other. The simplify
rule maps a duplicate relation onto another.
Conceptual graphs in a generalization hierarchy can be
replaced with sets of applications of the canonical formation
rules. The instances of the rules apply to the immediate
generalizations of the graph being represented. Fig.
illustrates this method for the generalization hierarchy in
Fig. 7.
This method has the potential to reduce the cost of graph
comparison by sharing computation already done through
mappings between adjacent conceptual graphs, and also
has the potential to save space in storing conceptual graphs.
V. Instructions
We examine how to use the canonical formation rules
in differences between adjacent graphs in the generalization
hierarchy. Here we will concentrate on the first phase
of topological search: searching the generalization space.
The following discussion assumes that only graphs in their
canonical form are compared and stored.
restrict(B3, c5, Eat)
Act Manner Attribute
restrict(B1, c1, Eat)
restrict(x1, c2, Fast)
restrict(x2, c4, Eat)
fuse(x5, x6, c1, c4)
d
restrictRef(b, c3, Sue)
Animate
a
Act Object Entity
restrict(B2, c3, Girl)
x3
c3 r2 c4
Agent Act
copy(B2, ({c8, c7}, {r4}))
restrict(x4, c6, Pie)
restrict(B2, c7, Person)
restrict(x3, c8, Eat)
c
e
x9 fuse(d, e, c3, c7)
join(x9, c1, c5)
simplify(x10, r2, r4)
restrict(c, c7, Girl)
fuse(x7, x8, c5, c8)
Fig. 16: Encoding conceptual graphs in a generalization
hierarchy with canonical formation instructions
In the first phase the aim is to find subgraph morphisms
of database graphs in the query. In the second phase the
aim is to find subgraph morphisms of the query in the
database graphs. In the first phase the database graphs
could be thought of as reading from the query graph. In
the second phase the database graphs write to the query
graph constructing specialized solutions. These modes correspond
to the modes of reading and writing in Prolog compiler
unification instructions [1].
Here we give a specialized interpretation of the canonical
formation rules based on the mode of operation: read
or write. We only examine the read mode here. The
graphs are reconstructed by the instructions, however we
only show the operations that construct the mapping between
the database graphs and the query q.
ffl copy(u; w) - Find some subgraph morphism - w!q .
Where w is an exact copy of u, which has been recon-
structed. The general matcher is used to find -w!q .
ffl restrict(u; c; t; w) - if type(- u!q c) - t then - w!q :=
For the database graph w to be a generalization of the
query graph q, q must have a subtype of the type of
the corresponding concept in u.
ffl restrictRef(u; c;
This instruction only handles restriction to individual
markers, rather than more complex referents, such as
nested graphs, and sets. For q - u to be true the query
must have the same individual marker i as the one
in the corresponding concept in the database graph u.
Joining concepts c and d of database graphs u and v
respectively in read mode means that c and d must already
pointing at the same concept in the query graph
q.
ffl simplify(u;
Simplifying two duplicate relations in a database graph
in read mode means that the two relations must be
mapped to the same relation in the query, since the
query graph cannot contain duplicates as it is a minimal
graph.
These instructions can be separated into more specialized
cases. For example, if the input and output graph
are the same, then a new mapping is not constructed,
rather modifications to particular entries in the mapping
are made.
In Fig. 16, conceptual graphs have been replaced with
instructions. Compare this representation with the generalization
hierarchy in Fig. 7. Fig. 6 contains the query
graph u and the generalization hierarchy in Fig. 7 contains
the solution f. Let us consider what happens in each stage
of the topological search of the generalization hierarchy for
the query u. We will examine the process in the middle of
the search where subgraph morphisms of b and c in u have
been found: -
q1g.
Now we look at b and c's adjacent graphs for generalizations
of u. The adjacent graphs are d and e. The graph d is
represented by restrictRef(b, c3, Sue, d). This instruction
translates into "if referent(- b!u
Sue, d is a generalization of u and - d!u := - b!u .
The graph e is represented by restrict(c, c7, Girl, e). This
instruction is implemented as: if type(- c!u c7) - Girl then
Girl, e is a generalization of u, and - e!u := - c!u .
Now we examine the adjacent graphs of d and e. The
only one in this case is f. The graph f is represented by
three instructions. The first instruction, fuse(d, e, c3, c7,
x9), means if - d!u
we calculate -
q1g.
The second instruction is join(x9, c1, c5, x10). Since
The third instruction in f is simplify(x10, r2, r4, f). Since
q3g. Thus f is a generalization of u. In
u. Compare this result with the graphs u and f in
Fig. 6 and Fig. 7, respectively.
Fig. 17 shows an alternative compilation based on canonical
derivations applied to a single parent and joining simple
basis relations. This approach follows a new formalization
of conceptual graph theory by Mugnier and Chein
[11]. This approach has some similarities with Garner and
Tsui's method of representation as differences [4].
VI. Experiments
The compilation methods above are still in the design
phase. To examine the usefulness of such methods in conceptual
graph databases we wrote some programs which
Animate
f
a
x3
d
c3 r2 r3 c6
e
c
Act Manner Attribute Agent Act Act Object Entity
restrict(x3, c7, Girl)
restrict(B2, c3, Person: Sue)
restrict(x5, c4, EAT)
fuse(x6, B3, c4, c5, {c5, c8})
restrict(x7, c8, Pie)
restrict(c, c3, Girl)
fuse(d, B3, c5, {c5 c8})
restrict(x4, c8, Pie)
restrict(b, c7, Sue)
fuse(x2, B2, c1, c4, {c4, c7})
restrict(B1, c1, Eat)
restrict(x1, c2, Fast)
Fig. 17: Some linear derivations of graphs in the hierarchy
in Fig. 7
Animate Act
Agent Act Object Entity
Manner
Act Attribute
a
Manner Fast
Girl Eat
Agent Eat Object Pie
c3
Girl: Sue
Girl: Sue
Eat
Pie
Object
c
c3 r2 c4
Agent
Person: Sue
f
e
d
Fig. 18: The generalization hierarchy Fig.7 compressed using
differences from Largest Parent
Animate Act
Agent Act Object Entity
Manner
Act Attribute
a
Manner Fast
Girl Eat
Agent Eat Object Pie
Girl: Sue
c3
Girl: Sue
c
c3 r2 c4
Agent
Person: Sue
e
d
f
Fig. 19: The generalization hierarchy Fig.7 compressed using
differences from All Parents
Original
File
Compressed
Largest
Parent
All
Parents
All
Parents
Parents
Compressed
All Parents
Database
with basis18245220854918644189369374412901247493477971882616823 1222111923A
A
with basis
Fig. 20: Results of compressing chess files
Piece Piece
Piece Piece
Piece Piece
Piece Piece Piece
Piece
Piece
Piece
Fig. 21: Schemas from the Morph chess seed database
compressed conceptual graph databases by representing a
graph u as the differences between u and (i) u's largest
parent, (ii) all u's parents. Method (i), which we shall call
the Largest Parent method, is a best case in Garner and
Tsui's method. Method (ii) corresponds to the compilation
method shown in Fig. 16 which we will call All Parents
method. The main problem with All Parents method is
that a join of all parents may need to be stored. In the
tests below we did not store such joins.
The files that were tested in Fig. 20 were from the Morph
adaptive chess playing system [9]. The file B is a seed
database of 3104 patterns of the form shown in the schemas
in Fig. 21, where a Piece could be a WhitePawn, Black-
Here an arc between
concepts represents support or attack depending on colour
of the piece. The file B contains 1778 chess patterns learnt
by Morph similar to Fig. 22. The files "A with basis" and
"B with basis" include 42 basis graphs in addition to the
graphs in files A and B, respectively.
The column "Database" of Fig. 20 lists the names of
the files. The column "Original File" lists the size of each
ascii file containing the conceptual graphs in a conceptual
graph linear notation [14]. The column "Lempel Ziv Com-
pressed" column gives the size of the files when compressed
using a UNIX compression utility. The column "Largest
WhiteRook(Rank=>0, File=>0)
WhitePawn(Rank=>1, File=>1)
Fig. 22: A conceptual graph of a chess pattern
Parent" shows the size of each file when compressed using
the Largest Parent method of representing conceptual
graphs. The column "All Parents" shows the size of each
file when compressed using the All Parents method of representing
conceptual graphs. The column "All Parents
without Parents" stores the same differences as the All
Parents method, but leaves out the list of parents which
the differences refer to. The column "Lempel Ziv Compressed
All Parents" shows the size of the file generated by
the All Parents method after compression using a UNIX
compression utility.
The main columns to compare are "Largest Parent" and
"All Parents". The "All Parents" method results in smaller
files, even though more parents are referred to. The cost of
referring to the parents is the difference between "All Par-
ents" and "All Parents without Parents" columns. For ex-
ample, for database A listing parents cost 30534 bytes. In
all cases, the "All Parents" method resulted in smaller files
than the files using the "Largest Parent" method. The All
Parents method resulted in a compression ratio of between
2.56:1 and 3.84:1 in the four knowledge bases we tested.
Potentially a similar reduction could also be achieved in
information retrieval times.
VII.

Summary

Compilation of conceptual graphs can be achieved by
storing them as derivations from immediate generalizations
in a directed acyclic graph representing the generalization
hierarchy partial order over conceptual graphs. A graph
can be inserted into the generalization hierarchy by computing
its immediate neighbourhood in the hierarchy, then
attaching the newly inserted graph to graphs in the neigh-
bourhood. The neighbourhood is computed by a two phase
topological search.
The canonical formation rules distinguish conceptual
graphs from other semantic network formalisms. They enforce
semantic constraints on the canonical graphs. Algorithms
to process them must be developed.
Conceptual graphs are compiled into instructions which
are special cases of the formation rules. The instructions
operate on immediate generalizations, and construct a mapping
between the immediate generalizations and the graph,
and hence the query graph during search. Common computation
involved in matching database graphs to the query
graph is shared through these mappings. Further, there
is a potential for store to be saved by storing these dif-
ferences. Compression of knowledge using differences has
been illustrated on some sample databases.
Compilation is effected in three ways: removal of redundant
data, use of simple instructions which ignore redundant
checks when performing matching, and by sharing
common processing between graphs.
In future work, we will examine methods for handling
complex conceptual graphs for use in such domains as chem-
istry. Levinson [7] has recently developed a new tuple and
skeleton-based compression technique called UDS. UDS is
based on a new compact representation of conceptual graphs
which make storage and retrieval more efficient. UDS can
be extended so that processing in a hierarchical search can
shared. Early work suggests that storing possible mappings
in matrix form between parents and children in the
database and combining mappings between parents and a
query and children using matrix multiplication to get first
approximations in more specific matches to queries may
more adequately propagate binding information gathered
in search within a conceptual graph database.

Acknowledgements

I thank my supervisors Peter Robinson and Robert Levin-
son. I thank Fritz Lehmann, Guy Mineau, and John Staples
for comments on earlier drafts of this paper. Fritz
Lehmann inspired me to revise an earlier version of this
paper.



--R


"Compiling conceptual graphs,"
"Sorting conceptual graphs."
"A self-organizing dictionary for conceptual structures,"

"Pattern associativity and the retrieval of semantic networks,"
"UDS: A Universal Data Structure,"
"Multi-Level Hierarchical Re- trieval,"
"Adaptive Pattern Oriented Chess,"
"Induction on conceptual graphs: Finding common generalizations and compatible projections,"
"Characterization and Algorithmic Recognition of Canonical Conceptual Graphs,"
The Existential Graphs of Charles S.
"Classification in the KL-ONE knowledge representation system,"
Conceptual Structures: Information Processing in Mind and Machine.
"Knowledge graphs versus conceptual graphs,"
"Understanding subsumption and taxonomy: A framework for progress,"
--TR

--CTR
Ahmad Kayed , Robert M. Colomb, Extracting ontological concepts for tendering conceptual structures, Data & Knowledge Engineering, v.40 n.1, p.71-89, January 2002
Vilas Wuwongse , Ekawit Nantajeewarawat, Declarative Programs with Implicit Implications, IEEE Transactions on Knowledge and Data Engineering, v.14 n.4, p.836-849, July 2002
Gian Piero Zarri, Ontologies and reasoning techniques for (legal) intelligent information retrieval systems, Artificial Intelligence and Law, v.15 n.3, p.251-279, September 2007
Ahmad Kayed , Robert M. Colomb, Using BWW model to evaluate building ontologies in CGs formalism, Information Systems, v.30 n.5, p.379-398, July 2005
associative retrieval;partial orders;conceptual graphs;compilation;hierarchical knowledge bases