A Conceptual Graph Approach for the Generation of Referring Expressions

1 Introduction

Generation of Referring Expressions (GRE) is a key task in Natural Language Generation (Reiter and Dale 2000). Essentially, GRE models the human ability to verbally identify objects from amongst a set of distractors, as when we say 'the wooden bookcase', 'the cup on the table', and so on, to single out the object in question. A GRE program takes as input (1) a knowledge base (KB) of (usually atomic) facts concerning a set of domain objects, and (2) a designated domain object, called the target. The task is to find some combination of facts that singles out the target from amongst all the distractors in the domain. These facts should be true of the target and, if possible, false of all distractors (in which case we speak of a distinguishing description). Once expressed into words, the description should ideally be 'natural' (i.e., similar to human-generated descriptions), and effective (i.e., the target should be easy to identify by a hearer). Many of the main problems in GRE are summarized in Dale and Reiter (1995). (See also Dale and Haddock 1991 for GRE involving relations; Van Deemter 2002 and Horacek 2004 for reference to sets and for the use of negation and disjunction). Here, we focus on logical and computational aspects of the problem, leaving empirical questions about naturalness and effectiveness, as well as questions about the choice of words, aside. We do not argue for one particular flavour of GRE, but show how different flavours can be 'implemented' using CGs.

Recently, a graph-based framework was proposed (Krahmer et al. 2003), in which GRE was formalised using labelled di-graphs. A two-place relation R between domain objects x and y was represented by an arc labelled R between nodes x and y; a one-place predicate P true of x was represented by an

Kees van Deemter

Department of Computing Science, University of Aberdeen, UK

looping arc (labelled P ) from x to x itself. By encoding both the description and the KB in this same format (calling the first of these the description graph and the second the scene graph), these authors described the GRE problem in graphbased terms using subgraph isomorphisms. Their approach is elegant and has the advantage of a visual formalism for which efficient algorithms are available, but it has a number of drawbacks. Most of them stem from the fact that their graphs are not part of an expressively rich overarching semantic framework that allows the KB to tap into existing ontologies, and to perform automatic inference. It is these shortcomings that we address, while maintaining all the other advantages of the approach of Krahmer et al.

Conceptual Graphs are a visual, logic-based knowledge representation (KR) formalism. They encode ontological ('T Box') knowledge in a structure called support. The support consists of a number of taxonomies of the main concepts and relations used to describe the world. The world is described using a bipartite graph in which the two classes of the partition are the objects, and the relations respectively. The CG semantics translate information from the support in universally quantified formulae (e.g., 'all cups are vessels'); information from the bipartite graph is translated into the existential closure of the conjunction of formulae associated to the nodes (see section 3.2). A key element of CG is the logical notion of subsumption (as modelled by the notion of a projection), which will replace the graph-theoretical notion of a subgraph isomorphism used by Krahmer et al. (2003). CGs have been used in computational linguistics before (e.g. Nicolov et al. 1995) but, to the best of our knowledge, never to GRE.

2 Conceptual Graphs (CGs)

2.1 Syntax

Here we introduce the conceptual graph (CG) model and explain how it can be used to formalise the information in a domain (or 'scene') such as Figure 1. In section 3 we show how the resulting CG-based representations can be used by a GRE algorithm that refers uniquely to objects in the scene.

The CG model (Sowa (1984)) is a logic-based KR formalism. Conceptual Graphs make a distinction between ontological (background) knowledge and factual knowledge. The ontological knowledge is represented in the support, which is encoded in hierarchies. The factual knowledge is represented by a labelled bipartite graph whose nodes are taken from the support. The two classes of partitions consist of concept nodes and relation nodes. Essentially, a CG is composed of a support (the concept / relation hierarchies), an ordered bipartite graph and a labelling on this graph which allows connecting the graph nodes with the support.

We consider here a simplified version of a support S = (TC, TR, I), where: (TC,≤) is a finite partially ordered set of concept types; (TR, ≤) is a partially ordered set of relation types, with a specified arity; I is a set of individual markers.

Formally (Chein and Mugnier (1992)), a (simple) CG is a triple CG= [S, G, λ]:

• S is a support;
• G = (VC, VR,E) is an ordered bipartite graph ; V = VC ∪VR is the node set of G, VC is a finite nonempty set of concept nodes, VR is a finite set of relation nodes; E is the set of edges {vr, vc} where vr ∈ VR and vc ∈ VC;
• λ : V → S is a labelling function; if v ∈ VC then λ(v) = (typev, refv) where typev ∈ TC and refv ∈ I ∪ {∗}; if r ∈ VR then λ(r) ∈ TR.

For simplicity we denote a conceptual graph CG= [S, G, λ] by G, keeping support and labelling implicit. The order on λ preserves the (pair-wise extended) order on TC (TR) and considers I elements mutually incomparable.

Consider the following KB described in Figure 1. The CG scene graph description is given in Figure 2.

In Figure 2 the concept type hierarchy TC of the support is depicted on the left. The factual information provided by Figure 1 is given by the labelled bipartite graph on the right. There are two kinds of nodes: rectangle nodes representing concepts (objects) and oval nodes representing relations between concepts. The former are called concept nodes and the second relation nodes. The labels ri and vi outside rectangles and ovals are only used for discussing the structure of the graph, they have no meaning. {v0, . . . , v7} are the concept nodes and {r1, . . . , r7} are the relation nodes. Each edge of the graph links a relation node to a concept node. The edges incident to a specific relation node are ordered and this ordering is represented by a positive integer label attached to the edge. For example, the two edges incident to the relation node r1 are {r1, v0}, labelled 1 and {r1, v1}, labelled 2; we also say that v0 is neighbor 1 of r1 and v1 is neighbor 2 of r1.

In the graphs of Krahmer et al. (2003), relations with more than two places are difficult to handle, but CGs can represent these naturally, because relation instances are reified. Consider that x gives a car y to a person z, and a ring u to v. This is modelled by using two instances r1 and r2 of giving, each of which has a labelled arc to its three arguments.

The label of a concept node (inside the rectangle) has two components: a concept type and either an individual marker or ∗, the generic marker. The concept node designates an entity of the type indicated by the first component. If the second component is ∗, this entity is an arbitrary one; if it is an individual marker then the entity is a specific one. In Figure 2 all concepts have generic markers and the nodes v0, v3 and v7 designate three (different) arbitrary objects of type cup, v4 designates an arbitrary object of type floor, etc. For a relation node, the label inside the oval is a relation type from TR. The arity of this relation type is equal to the number of vertices incident to the relation node r (denoted by deg(r). The objects designated by its concept node neighbours are in the relation designated by the label. In Figure 2 the relation node r2 asserts that the bowl designated by v1 is on the table designated by v2.

Overall the conceptual graph in Figure 2 states that there is a floor on which there are a table, a cup and two bowls; on the table there is a a bowl and in this bowl there is a cup.

2.2 Formal Semantics of CGs

CGs are provided with a logical semantics via the function Φ, which associates to each CG a FOL formula (Sowa (1984)). If S is a support, a constant is associated to each individual marker, a unary predicate to each concept type and a nary predicate to each n-ary relation type. We assume that the name for each constant or predicate is the same as the corresponding element of the support. The partial orders specified in S are translated in a set of formulae Φ(S) by the following rules: if t1, t2 ∈ TC such that t1 ≤ t2, then ∀x(t2(x) → t1(x)) is added to Φ(S); if t1, t2 ∈ TR, have arity k and t1 ≤ t2, then ∀x1∀x2 . . . ∀xk(t2(x1, x2, . . . , xk) → t1(x1, x2, . . . , xk)) is added to Φ(S).

If CG= [S,G, λ] is a conceptual graph then a formula Φ(CG) is constructed as follows. To each concept vertex v ∈ VC a term av and a formula φ(v) are associated: if λ(v) = (typev, ∗) then av = xv (a logical variable) and if λ(v) = (typev, iv), then av = iv (a logical constant); in both cases, φ(v) = typev(av). To each concept vertex r ∈ VR, with λ(r) = typer and degG(r) = k, the formula associated is φ(r) = typer(aN 1G(r), . . . , aN kG(r)). The existential closure of the conjunction of all formulas associated to the vertices of G is Φ(CG). That is, if VC(∗) = {vi1 , . . . , vip } is the set of all concept vertices having generic markers, then Φ(CG)= ∃v1 . . . vp(∧v∈VC∪VR φ(v)).

If G is the graph in Figure 2, then (using only one quantifier) Φ(G) = ∃xv0 xv1 xv2 xv3 xv4 xv5 xv6 xv7 (cup(xv0 ) ∧ bowl(xv1 )∧table(xv2 )∧cup(xv3 )∧f loor(xv4 )∧bowl(xv5 )∧ bowl(xv6 ) ∧ cup(xv7 ) ∧ isin(xv0 , xv1 ) ∧ ison(xv1 , xv2 ) ∧ ison(xv1 , xv2 ) ∧ ison(xv3 , xv4 ) ∧ ison(xv2 , xv4 ) ∧ ison(xv5 , xv4 ) ∧ ison(xv6 , xv4 ) ∧ isin(xv7 , xv6 ).

If (G, λG) and (H, λH) are two CGs (defined on the same support S) then G ≥ H (G subsumes H) if there is a projection from G to H. A projection is a mapping π from the vertices set of G to the vertices set of H, which maps concept vertices of G into concept vertices of H, relation vertices of G into relation vertices of H, preserves adjacency (if the concept vertex v in V G C is the ith neighbour of relation vertex r ∈ V G R then π(v) is the ith neighbour of π(r)) and furthermore λG(x) ≥ λH(π(x)) for each vertex x of G. A projection is a morphism between the corresponding bipartite graphs with the property that labels of images are decreased. Informally G ≥ H means that if H holds then G holds too. Π(G, H) denotes the set of all projections from G to H.

For the GRE problem the following definitions are needed to rigorously identify a certain type of a subgraph. If G = (V G C , V G R ,E) is an ordered bipartite graph and A ⊆ V G R , then the subgraph spanned by A in G is the graph [A]G = (NG(A), A, E′ ) where NG(A) is the neighbour set of A in G, that is the set of all concept vertices with at least one neighbour in A, and E′ is the set of edges of G connecting vertices from A to vertices from NG(A). Clearly [A]G ≥ G since the identity is a trivial projection from [A]G to G.

3 CGs for Generation of Referring Expressions

3.1 Stating the problem

Let us see how the GRE problem can be stated in terms of CG. Given a CG G, a concept node v0 in G, a CG H and a concept node w in H, we define that the pair (w,H) refers to the pair (v0,G) if there is a projection π from H to G such that π(w) = v0. Furthermore, (w,H) uniquely refers to (v0,G) if (w, H) refers to (v0, G) and there is no concept node v in G different from v0 such that (w,H) refers to (v,G). The GRE problem may now be stated as follows: given a CG G and a concept node v0 in G, find a pair (w,H) such that (w,H) uniquely refers to (v0, G).

But (analogous to Krahmer et al. 2003), the GRE problem means that we are interested in referring graphs 'part of' the scene graph. By the above definition, if (w,H) uniquely refers to (v0,G), then there is a projection π from H to G such that π(w) = v0. If π(H) is the image of H, then π(H) is a spanned subgraph of G namely, [π(V H R )]G, containing v0 such that there is no projection π1 from π(H) to G such that π1(v0) ̸= v0. Therefore it is possible to formulate GRE using only the combinatorial structure CG G and the vertex v0.

More precisely, any spanned subgraph G′ = [A]G containing v0 (that is, if A ̸= ∅ then v0 ∈ NG(A), and if A = ∅ then G′ = ({v0}, ∅, ∅) ) is called a v0-referring subgraph of G. A v0-referring subgraph [A]G is called v0-distinguishing if v0 is a fixed point of each projection π from [A]G to G, that is π(v0) = v0 ∀π ∈ Π([A]G, G). The GRE problem is now:

Instance: CG= [S, G, λ] a conceptual graph representation of the scene; v0 a concept vertex of G.

Output: A ⊆ VR such that [A]G is a v0distinguishing subgraph in CG, or the answer that there is no v0-distinguishing subgraph in cg.

Example. Consider the scene described in Figure2. A = ∅ is not a solution for the GRE instance (CG, {v0}) since G1 = ({v0}, ∅, ∅) can be projected to ({v7}, ∅, ∅) or ({v3}, ∅, ∅). However, A = {r1, r2} is a valid output since G1 = [{r1, r2}]G is a v0-distinguishing subgraph (note that the intensional description of the entity (cup) represented by v0 in G1, ΦG1,v0 (x) = ∃xv1 ∃xv2 (bowl(xv1 ) ∧ table(xv2 ) ∧ isin(x, xv1 ) ∧ ison(xv1 , xv2 )) has the intuitive meaning the cup in the bowl on the table, which clearly individualizes this cup in the set of the three cups in the scene).

Note that if G1 = [A]G is a v0-distinguishing subgraph in CG then if we denote by A′ the relation node set of the connected component of G1 containing v0, then [A′ ]G is a v0-distinguishing subgraph in CG too. For brevity, we consider only connected v0-distinguishing subgraphs. On the other hand, intuitively the existence of a v0-distinguishing subgraph is assured only if the CG description of the scene has no ambiguities.

Theorem 1 Let (CG, {v0}) be a GRE instance. If [A]G is v0distinguishing then [A′ ]G is v0-distinguishing for each A′ ⊆ V G R such that A ⊆ A′ . (Proof omitted for reasons of space.) In particular, taking A′ = VR, we obtain:

Corollary 1 There is a v0 distinguishing subgraph in G iff there is no projection π from G to G such that π(v0) ̸= v0.

A concept vertex v0 which does not have a v0distinguishing subgraph is called an undistinguishable concept vertex in G. We say that a CG provides an well-defined scene representation if it contains no undistinguishable vertices. Testing if a given GRE instance defines such an ambiguous description is, by the above corollary, decidable.

3.2 Complexity results

Some of the main complexity results in GRE are presented in Dale and Reiter (1995). Among other things, these authors argue that the problem of finding a uniquely referring description that contains the minimum number of properties (henceforth, a Shortest Description) is NP-complete, although other versions of GRE can be solved in polynomial or even linear time. As we have argued, CG allows a substantial generalisation of the GRE problem. In what follows, we shall show that this generalisation does not affect the theoretical complexity of finding Shortest Descriptions. 1

Let v0 ∈ VC be an arbitrary concept vertex. The set of concept vertices of G different from v0, in which v0 could be projected, is (by projection definition) contained in the set

1 To the best of our knowledge this is the first formal proof of the NP- completeness of any GRE problem.

Clearly, if Distractors0 (v0) = ∅ then v0 is implicitly distinguished by its label (type + referent), that is ({v0}, ∅, ∅) is a v0-distinguishing subgraph.

Therefore we are interested in the existence of a v0-distinguishing subgraph for concept vertices v0 with Distractors0 (v0) ̸= ∅. In this case, if NG(v0) = ∅, clearly there is no v0-distinguishing subgraph (the connected component containing the vertex v0 of any spanned subgraph of G is the isolated vertex v0). Hence we assume NG(v0) ̸= ∅.

A simple case considering all relation vertices r ∈ V G R unary. This means that G is a disjoint union of stars centered in each concept vertex. Intuitively, this means that each object designated by a concept vertex in the scene represented by G is characterized by its label (type and reference) and by some other possible attributes (properties) and each r ∈ V G R designates an unary relation. This is the classical framework of the GRE problem, enhanced with the consideration of basic object properties (the types) and the existence of a hierarchy between attributes. Even with these enhancements we will show that the GRE problem complexity results remain similar.

Indeed, if NG(v0) = {r1, . . . , rp} (p ≥ 1) (the properties of the concept designated by v0) then for each ri ∈ NG(v0) let: Xi := {w|w ∈ Distractors0 (v0) such that there is no r ∈ NG(w) with λ(ri) ≥ λ(r)}.

In words, Xi is the set of v0-distractors which will be removed if ri would be included as a single relation vertex of a v0-distinguishing subgraph (since there is no r ∈ NG(w) such that λ(ri) ≥ λ(r) it follows that there is no projection π of the subgraph [ri]G to G such that π(v0) = w).

Lemma 1 There is a v0-distinguishing subgraph in G iff:

Proof. If there is a v0-distinguishing subgraph [A]G, then we can suppose that A ⊆ NG(v0) = {r1, . . . , rp} (because we can suppose that [A]G is connected). Suppose that there is w ∈ Distractors0 (v0)\∪pi=1Xi. By the definition of the sets Xi it follows that for each ri ∈ A there is r′i ∈ NG(w) such that λ(ri) ≥ λ(r′i ). If we take π(v0) = w and π(ri) = r′i for each ri ∈ A, then π is a projection of [A]G to G with π(v0) = w ̸= v0, contradicting the hypothesis that [A]G is a v0-distinguishing subgraph.

Conversely, if ∪pi=1Xi = Distractors0 (v0), then taking A = NG(v0) = {r1, . . . , rp} [A]G is a v0-distinguishing subgraph. Indeed, if there is π a projection of [A]G to G such that π(v0) = w ̸= v0, then for each ri ∈ A the edge v0ri is projected in some edge wr′i such that λ(v0) ≥ λ(w) and λ(ri) ≥ λ(r′i ). This means that w ∈ Distractors0 (v0) \ ∪pi=1Xi is a contradiction.

To summarize, if all relation vertices have degree 1, deciding if a vertex v0 admits a v0-distinguishing subgraph can be done in polynomial time. However, the above proof shows that [A]G is a v0-distinguishing subgraph if and only if A ⊆ NG(v0) and ∪ri∈AXi = Distractors0 (v0). Therefore the problem of finding a v0-distinguishing subgraph with a minimum number of vertices (e.g., Dale and Reiter 1995) is reduced to the problem of finding a minimum cover of the set Distractors0 (v0) with elements from X1, . . . , Xp, which is an NP -hard problem.

We now prove that the decision problem associated with minimum cover can be polynomially reduced to the problem of finding a concise distinguishing subgraph. Let us consider the following two decision problems:

Minimum Cover

Instance: O = {o1, . . . , on} a finite nonempty set; S = (S1, . . . , Sp) a finite family of subsets of O; q a positive integer. Question: Are there Si1 , . . . , Sit ∈ S such that

∪tj=1Sij = O and t ≤ q ?

Shortest Description

Instance: SCG= (G, S) a conceptual graph such that dG(r) = 1, for each relation node r ∈ VR; a vertex v0 ∈ VC;

s a positive integer.

Question:

Is there a v0-distinguishing subgraph [A]G such that |A| ≤ s ?

Theorem 2 Shortest Description is NP-complete.

Proof. We have shown that checking if a guessed A ⊆ VR such that [A]G is v0-distinguishing can be done in polynomial time (we need to test if v0 ∈ NG(A) and ∪ri∈AXi = Distractors0 (v0); all sets involved can be computed in polynomial time). Hence Shortest Description belongs to NP.

We outline a polynomial reduction of Minimum Cover to Shortest Description. Let O = {o1, . . . , on}, S = (S1, . . . , Sp) and q an instance of Minimum Cover. Let us consider the bipartite graph G with VC = {o0, o1, . . . , on}. The label of each concept vertex is (⊤, ∗). The relation vertices set of G is initialized as VC = {rij|i ∈ {0, . . . , n}, j ∈ {0, . . . , p} }, where each vertex rij is a neighbor of the vertex oi ( all edges oirij are added to G). The type of the vertex rij is ai. The final CG G is obtained by deleting some relation vertices using the following rule: for each i and j, if oi ∈ Sj then rij is deleted fromG (together with the edge oirij).

Clearly the graph G is constructed from the instance of the Minimum Cover problem in polynomial time. The desired instance of the Shortest Description problem is obtained by taking as input this graph, vertex o0 and s = q. An illustration of this construction for the instance O = {o1, o2, o3}, S = (S1 = {o1, o2}, S2 = {o1, o3}, S3 = {o2, o3}) and q = 1, of Minimum Cover is given in Figure 3:

It is easy to see that there is no o0-distinguishing subgraph with at most s = 1 relation vertices and also there is no cover of O with at most q = 1 members of S. If in the instance of the Minimum Cover problem we have q = 2 then the answer is yes since (S1, S2), (S1, S3) or (S2, S3) are all covering of O with 2 members of S. The corresponding instance of the Shortest Description problem (the same graph and s = 2) also returns "yes"; since [r01, r02]G, [r01, r03]G or [r02, r03]G are all o0-distinguishing subgraphs with 2 relation vertices.

Returning to the proof, we must show that in the constructed conceptual graph there is an o0-distinguishing subgraph with at most s relation vertices if and only if there is a covering of O with at most q = s members from S. But this is an easy consequence of the observation that the above construction is such that the sets Xi (destroying the distractors by the relation vertices r0i) are exactly the sets Si ∈ S.

3.3 A simple GRE algorithm

In the general case, each object in the scene represented by G is characterized by its label (type and reference), by some other possible attributes (properties) and also by its relations with other objects, expressed via relation nodes of arity ≥ 2. In this case, if v0 an arbitrary concept node, it is possible to have vertices in Distractors0 (v0) which cannot be distinguished from v0 using individual relation neighbors but which could be removed by collective relation neighbors. Let us consider the scene described in Figure 4 :

Note that relation labels are assumed to be incomparable. Clearly, NG(v0) = {r1, r2} and Distractors0 (v0) = {v2, v4}. The vertex v4 can be removed by r1 (v4 has no relation neighbor with a label at least know) and by r2 (despite of the existence of a relation neighbor r5 labelled is near, v4 is the second neighbor of r5; v0 is the first neighbor of r2). The vertex v2 cannot be removed by r1 ([r1]G ≥ [r3]G)) and by r2([r2]G ≥ [r4]G), but {r1, r2} destroys v2 ( there is no projection of [{r1, r2}]G mapping v0 to v2 and in the same time mapping v1 to a common neighbor of r3 and r4).

This example suggests an algorithm for constructing a v0distinguishing subgraph in general. For an arbitrary concept vertex v0, let us denote N 0 (v0) = ∅, N 1 (v0) := NG(v0) and for i ≥ 2, N i (v0) = NG(NG(N i-1 (v0))). Clearly, since G is finite, there is k ≥ 1 such that N i (v0) = N k (v0) for each i ≥ k. This parameter is called the eccentricity of v0

and is denoted ecc(v0). We can inductively construct distractors of higher order for a vertex v0, as follows: If we consider Distractors0 (v0) = {w|w ∈ VC - {v0}, λ(v0) ≥ λ(w)}, then for each i = 1, ecc(v0), Distractorsi (v0) = {w|w ∈ Distractorsi-1 (v0), [N i (v0)]G ≥ [N i (w)]G}.

Theorem 3 Let (CG, {v0}) be a GRE instance, and let i0 be the first i ∈ {0, . . . , ecc(v0)} such that Distractorsi (v0) = ∅. If i0 exists then [N i (v0)]G is a v0-distinguishing subgraph, otherwise v0 is an undistinguishable vertex.

Proof. The theorem clearly holds due to the definition of the Distractors sets.

This theorem basically defines a breadth-first search algorithm for finding a v0 distinguishing subgraph.

4 Generalisations and extensions

Apart from the benefits shown throughout the paper, using CGs for representing GRE means that a number of interesting and useful extensions can be developed. This section sketches two kinds of extensions: the addition of inferential rules (to increase reasoning power), and the addition of negation and full quantification (to increase expressive power).

4.1 Adding inferential Rules

An important further generalisation of the GRE problem can be obtained by bringing inferential rules to bear, as an integral part of CG (Baget and Mugnier 2002). If S is the support of the CG representing the scene, a rule defined on S is any CG, H, over the support S, and having specified a bipartition (Hyp,Conc) of its set of relation nodes V H R . The subgraph of H spanned by Hyp, [Hyp]H is called the hypothesis of the rule H, and the subgraph spanned by Conc, [Conc]H, is the conclusion of the rule H. Applying a rule H to a CG G means to find a projection π from [Hyp]H to G, to add a disjoint copy of [Conc]H to G, and finally to identify in this graph each concept node v ∈ V [Conc]H C ∩V [Hyp]H C to π(v), its image by π. The new CG obtained, G′ , is called an immediate derivation of G by the application of rule H following π. Let R a set of rules defined on S and G a CG over S. Then G, R derives a CG G′ if there exists a sequence of immediate derivations leading to G′ by applications of rules in R.

Let us consider again the scene represented in Figure 4. If we want to express that the conceptual relation near is symmetric, then we add the rule H described in Figure 5:

Here the Hyp set contains only the "gray" relation node s1 and the set Conc is the singleton set {s2}. Without this rule, the vertex in Figure 4 v4 ∈ Distractors0 (v0) can be removed by by adding r2 to a v0-referring subgraph (despite of the existence of a relation neighbor r5 labelled is near, v4 is the second neighbor of r5 while v0 is the first neighbor of r2). Considering the rule H, which intuitively asserts that "if a person a isnear a person b then b isnear a, too", v4 can not be removed by adding r2 to a v0-referring subgraph.

We have therefore an interesting extension of the basic GRE problem, which can be formally stated as follows. Let S, G and R a scene representation, and v0 a concept node in G. A derived v0-distinguishing subgraph is any v0distinguishing subgraph of some derived CG G′ from G and R. The extended GRE problem asks to find such a derived v0-distinguishing subgraph or the conclusion that it does not exists for a specified S, G and R scene representation.

4.2 Increasing expressive power

Like all other GRE algorithms that we are aware of, the CGs discussed so far are essentially limited to the expression of atomic facts. In the CG framework, however, various extensions are naturally forthcoming.

Negation. Explicit negation can be added to the KB, which is an interesting way to allow GRE to produce descriptions involving the absence of a property (cf. van Deemter and Krahmer (in press) for alternative approaches).

Let A, F ⊆ VR such that A∩F = ∅. The pair ([A]G, [F ]G) is called a v0-distinguishing pair of subgraphs if v0 ∈ NG(A) (that is, [A]G is a v0-referring subgraph), v0 ̸∈ NG(F) and each projection π from [A]G to G such that π(v0) ̸= v0 can be extended to a projection π′ from [A ∪ F]G to G (that is, π′ |[A]G = π|[A]G ) such that we have π′ (v0) ∈ NG(π′ (F)).

The set F ⊂ VR (of forbidden relation nodes) is used to kill each concept node from the set ConfusableA(v0), where ConfusableA(v0) = {w|w ∈ VC - {v0}, ∃π ∈ Π([A]G,G) such that π(v0) = w}.

In the example in Figure 4 ({r1}, {r5}) is a v0distinguishing pair of subgraphs, with the intuitive meaning the man knowing a person and which is not near Joe. Similarly, for the scene represented in figure (2), ({r5}, {r7}) is a v5-distinguishing pair of subgraphs, with the intuitive meaning: the bowl on the floor, not containing a cup.

Clearly, if [A]G is a v0-distinguishing subgraph, then ([A]G, [F]G) is a v0-distinguishing pair of subgraphs, for each F ⊆ VR such that A ∩ F = ∅. The basic GRE problem can be extended by replacing the output requirement with:

Output: A, F ⊆ VR such that ([A]G, [F ]G) is a v0-distingushing pair of subgraphs in SG, or the answer that there is no v0-distinguishing pair of subgraphs in SG.

Full quantification. Suppose our CG-based KB expressed the (non-atomic) proposition that every table has exactly one cup on it; this plus the fact that there is only one wooden table (for example) would be sufficient to justify a description like 'the cup on the wooden table', even if the KB does not say which table this is. Extensions of this kind would enable GRE programs to model human communication far more extensively than has so far been possible.

5 Conclusions

Using CG to formalise GRE means that we can benefit from:

• The existence of a support. CGs make possible the systematic use of a set of "ontological commitments" for the knowledge base. A support, of course, can be shared between many KBs.
• A properly-defined formal semantics, reflecting the precise meaning of the graphs and their support, and including a general treatment of n-place relations. Further extensions of the expressive power of the formalism are possible, as we have seen (section 4).
• Projection as an inferential mechanism. Projection replaces the purely graph-theoretical notion of a subgraph isomorphism by a proper logical concept (since projection is sound and complete with respect to subsumption). Optimized algorithms for CG projection have been studied in Croitoru and Compatangelo (2004). This inferential mechanism can be further enhanced by the addition of 'axiomatic' rules (section 4).

6 References

Baget and Mugnier (2002) Baget, J.-F., and Mugnier, M.-L. Extensions of Simple Conceptual Graphs: the Complexity of Rules and Constraints. Jour. of Artif. Intell. Res. 16:425 465.

Chein and Mugnier (1992) Chein, M., and Mugnier, M.-L. Conceptual graphs: Fundamental notions. Revue d'Intelligence Artificielle 6(4):365

Croitoru and Compatangelo (2004) Croitoru, M., and Compatangelo, E. A combinatorial approach to conceptual graph projection checking. In Proc. of the 24th International Conf. of the Brit. Comp. Soc. Spec. Group on Artif. Intell. (AI 2004), 130 143. Springer.

Dale and Haddock (1991) Robbert Dale and Nickolas Haddock. Generating referring expressions containing relations. Procs. of the 5th Conference of the European Chapter of the ACL, EACL-91.

Dale and Reiter (1995) Robbert Dale and Ehud Reiter. Computational Interpretations of the Gricean Maximes in the Generation of Referring Expressions. Cognitive Science 18: 233-263.

Horacek (2004) Horacek, H. On referring to Sets of Objects Naturally. Proc. of Third Int. Conf. on Natural Language Generation (INLG-2004), p.70-79, Brockenhurst, UK.

Krahmer et al (2003). Krahmer,E. van Erk,S. and Verleg,A. Graphbased Generation of Referring Expressions. To appear in Computational Linguistics 29 (1):53-72.

Nicolov et al. (1995) Nicolov, N., C.Mellish, and G.Ritchie. Sentence Generation from Conceptual Graphs. In Conceptual Structures: Applications, Implementation and Theory. (LNAI 954), p.7488. Berlin: Springer.

Sowa (1984) Sowa, J. F. Conceptual Structures: Information Processing in Mind and Machine. Addison-Wesley.

van Deemter (2002) Generating Referring Expressions: Boolean Extensions of the Incremental Algorithm. Computational Linguistics 28 (1), pp.37-52. March 2002.

van Deemter and Krahmer (IN PRESS). K. van Deemter and E.Krahmer. Graphs and Booleans: on the generation of referring expressions". To appear in "Computing Meaning, Volume 3", "Studies in Linguistics and Philosophy" series, Kluwer, Dordrecht.