We propose a representation of simple conceptual graphs with binary conceptual relations, which is based on finite-state automata. The representation enables the calculation of injective projection as a two-stage process: off-line calculation of the computationally-intensive subsumption checks and encoding of the results as a minimal finite-state automaton, and run-time calculation by look-up in the minimal finite-state automaton using the projection query as a word belonging to the automaton language. This approach is feasible since a large part of the projection calculations does not depend on the run-time query but only on the relatively static statements in the knowledge base.
Conceptual Graphs (CGs) are based on logic and graph theory [
The most effective algorithms for computing CG projection rely on graph theory.
They search for structural similarity and subgraph mappings between the projection
query and the CGs in the Knowledge Base (KB). Given two CGs G and H, it is
NPcomplete to decide whether G≥H. However there are large classes of CGs for which
polynomial algorithms for projection exist when the underlying ordinary graphs are
trees [
Section 2 defines important notions. The FSA-based encoding of SCGs is presented in section 3. Section 4 sketches the idea of injective projection calculation in run-time. Experimental evaluations and the conclusion are given in section 5. Here we define the support for binary conceptual relations only: Definition 1. A support S is a 4-tuple (TC, TR, I, τ) where:
• TC is finite, partially ordered set of distinct concept types. For x,y∈TC, x≤y means that x is a subtype of y; we say that x is a specialisation of y;
• TR is finite, partially ordered set of distinct relation types. TC∩TR=∅. Each type R∈TR has arity 2 and holds either between two different concept types x,y∈TC or between two distinct instances of a concept type x∈TC. Pairs (c1maxR,c2maxR)∈TCxTC, called star graphs, are associated to each type R∈TR; they define the greatest concept types that might be linked by R. A type R∈TR holds between x,y∈TC iff x≤c1maxR and y≤c2maxR. For R1,R2∈TR and R1≤R2, it holds that c1maxR1≤c1maxR2 and c2maxR1≤c2maxR2; • I is a finite set of distinct individual markers (referents) denoting specified concept instances. TC∩I=∅ and TR∩I=∅. The generic marker ∗, ∗∉(TC∪TR∪I), refers to an unspecified individual of a specified concept type x. For all i∈I, i≤∗; • The mapping τ: I→TC defines correspondences between instances and concept types. So concept types have instances in contrast to the relations types. □ Definition 2. A simple conceptual graph with binary conceptual relations G, defined over a support S, is a connected, finite bipartite graph (V = VC∪VR, U, λ) where: • The nodes V are defined by VC – the set of concept nodes (c-nodes) and VR – the set of relation nodes (r-nodes). VC≠∅, i.e. each SCG contains at least one node; • The edges U are defined by ordered pairs (x,r) or (r,y), where x,y∈VC and r∈VR. The edges are directed either from a c-node to a r-node – like the incoming arc (x,r), or from a r-node to a c-node – like the outgoing arc (r,y). For every r∈VR, there is exactly one incoming and one outgoing arcs, incident with r;
• The mapping λ associates labels of S to the elements of VC∪VR. Each c∈VC is labeled by a pair (C, marker(C)), where C∈TC and marker(C)∈I∪{∗}. A c-node with generic marker is called a generic node, it refers to an unspecified individual of the specified concept type. A c-node with individual marker is called an individual node, it refers to a specified instance of the concept type. Each r∈VR is labeled by a type R∈TR. The 1st argument of R is mapped to the c-node linked to the incoming arc of r while its 2nd argument is mapped to the c-node linked to the outgoing arc of r. □
The SCGs introduced by definition 2 can contain cycles but no multi-edges and
loops. They may contain nodes with duplicating labels since λ associates repeating
labels to the elements of VC∪VR. Then all generic concept nodes of the same type are
treated as distinct c-nodes of the underlying graph. Such nodes represent distinct
instances, as we consider no coreference links between the c-nodes. We shall deal
with non-blank, simplified SCGs [
πG⊆H has the properties: (i) for each concept c in G, πc is a concept in πG where type(πc) ≤ type(c). If c is individual, then referent(c) = referent(πc); (ii) for each relation r(c1,c2) in G, it holds that πr(πc1,πc2) is in πG; (iii) πG is isomorphic to G. □
finite alphabet, Q is a finite set of states, q0∈Q is the initial state, F⊆Q is the set of final states, and Δ ⊆ Q x Σ x Q is the transition relation. The transition ‹q, a, p›∈Δ begins at state q, ends at state p and has the label a. □
Definition 5. Let A be a FSA. A path c in A is a finite sequence of k>0 transitions: c = ‹q0, a1, q1› ‹q1, a2, q2› … ‹qk-1, ak, qk›, where ‹qi-1, ai, qi›∈Δ for i = 1,…,k. The integer k is called the length of c. The state q0 is called beginning of c and qk is called the end of c. The string w = a1 a2 … ak is called the label of c. The null path of q∈Q begins and ends in q with label ε, where ε is the empty symbol. □
Definition 6. Let A = ‹Σ, Q, q0, F, Δ› be a FSA. Let Σ* be the set of all strings over the alphabet Σ, including the empty symbol ε. The generalised transition relation Δ* is the smallest subset of QxΣ*xQ with the following two closure properties: (i) For all q∈Q we have ‹q, ε, q›∈Δ*; (ii) For all q1, q2, q3∈Q and w∈Σ*, a∈Σ : if ‹q1, w, q2›∈Δ* and ‹q2, a, q3›∈Δ, then ‹q1, w·a, q3›∈Δ*. □
Definition 7. The formal language L(A) accepted by a FSA A = ‹Σ, Q, q0, F, Δ› is the set of all strings, which are labels of paths leading from the initial to a final state: L(A):= { w∈Σ* | ∃ q∈F : ‹q0, w, q›∈Δ* }. These strings are called words of L(A). □
The FSAs accept regular languages. Every finite list of words over a finite alphabet
of symbols is a regular language. Among the deterministic FSAs which accept a given
language, there is a unique automaton (excluding isomorphisms) which has a minimal
number of states [
Definition 8. Let A = ‹Σ, Q, q0, F, Δ› be a FSA. Let Σ+ be the set of all strings w over the alphabet Σ, where |w|≥1. The automaton A is called acyclic iff for all q∈Q there exist no string w∈Σ+ such that ‹q, w, q›∈Δ*. □
‹Σ,Q,q0,F,Δ,E,μ›, where Σ is finite alphabet, Q is finite set of states, q0∈Q is the initial state, F⊆Q is set of final states, Δ⊆QxΣxQ is the transition relation, E is finite set of markers, and μ: F→E is a function assigning a marker to each final state. □ 3
We are looking for an internal encoding of the SCGs with binary conceptual relations,
which maps the SCGs to words of symbols and provides a unified enumeration of: (i)
all SCGs, defined according to a support, (ii) all their subgraphs and (iii) all injective
generalisations of (i) and (ii). Actually we aim to interpret them as a a finite regular
language over certain finite alphabet. The encoding has to reflect the particular
topological structure of the SCGs but should not contain graph-dependent indices,
since we intend to further use this conceptual resource in run-time, when its symbols
have to be matched to the symbols of (all future) projection queries. Perhaps all the
subgraphs and their injective generalisations are too many and the brute-force
enumeration makes no sense even if it is calculated off-line. However, we can filter
only the subgraphs which have conceptual interpretation according to the support.
Definition 10. Let G be a SCG with binary conceptual relations. A conceptual
subgraph Gcs⊆G is a connected graph which is a SCG according to definition 2. □
Example 1. Figure 1 introduces a sample support, using examples from [
EGOISTIC, ANIMATE, ANIMAL, PERSON} with partial order shown at Fig. 1; TR = {ATTR, EXPR, OBJ } with partial order and star graphs shown at Fig. 1; I = {John, Mary} which are not ordered; τ(John) = PERSON, τ(Mary) = PERSON. Fig. 2 shows the SCGs G1 and G2, defined over the support given at Fig. 1. Figure 3A presents a conceptual subgraph of G2. Fig. 3B shows a connected subset of G2 nodes and edges, which has no conceptual interpretation according to the support. There exist connected bipartite graphs which cannot be interpreted as SCGs in any support, e.g. the one at Fig. 3B. Below by 'subgraphs' we shall mean 'conceptual subgraphs'.
The formula operator φ, defined in [
The symbols used in this encoding correspond directly to the support labels which are meaningful for all SCGs in the KB as well as for the potential run-time projection queries. However, some of the generic concept types' labels might be duplicated, due to two different reasons: (i) they represent equivalent instances whose configuration reflects the topological structure of the underlying connected bipartite graph; (ii) they represent different unspecified instances belonging to the same concept type. Therefore we have to distinguish the two kinds of duplication and to mark the duplicated labels of the generic concept types, which refer to equivalent concept instances. For instance G2 contains such duplications; the sequence of triple labels LOVE EXPR PERSON LOVE OBJ PERSON corresponds to three facts: (f1) “there exists a person who loves another person”, (f2) “there exists a person who loves himself” and (f3) “there exist a person who experiences one kind of love and he/she is object of another love”. A marker for the equivalences of the unspecified instances will ensure proper SCG encoding and, in addition, proper run-time treatment. Please note that a projection query with labels e.g. LOVE EXPR ANIMATE LOVE OBJ ANIMATE has to be projected in run-time to only one of (f1), (f2) and (f3) depending on its c-nodes identity. Therefore we need a unified approach to encode and recognise the c-nodes identity for all SCGs.
Describing all possible identities of n arguments is connected to the task of finding all ways to partition a set of n elements into nonempty, disjoint subsets. Each partition defines an equivalence relation of its members. The number of partitions is given by the so-called Bell numbers B1, B2, ... . We are interested in partitions of even number of elements, since the arguments of binary conjuncts are even numbers. Let us consider in more detail the similarity between the partition task for a set of four elements and our task to define structural patterns for argument identity of two binary predicates with four arguments. Let the four set elements be x1, y1, x2, y2 and the SCG with two binary predicates be correspondingly rel1(x1, y1) & rel2(x2, y2).
Table 1, column 1 lists the set partitions into disjoint equivalence classes. These classes are interpreted as encodings of the topological links in a SCG with two binary predicates. Each row of column 2 contains either a G1-G2 subgraph with arguments linked correspondingly to the class in column 1, or comments why there are no such subgraphs. There are 15 ways to partition a set of four elements into disjoint subsets: • Partition № 1 is irrelevant to our considerations as it corresponds to four distinct arguments of the two binary predicates – but the SCGs are to be connected; • Eight partitions (№ 2, 5, 8, 9, 10, 11, 14, 15) are irrelevant, as they correspond to loops in the underlying graph, which are not allowed by definition 2; and • Six patterns (corresponding to partitions № 3, 4, 6, 7, 12, 13) are relevant and provide a typology for the encoding of the links between two SCG binary predicates.
Thus the linearised SCG labels and the respective labels' identity annotations: LOVE EXPR PERSON LOVE OBJ PERSON 1=3 (i.e. x1=x2) (1) LOVE EXPR PERSON LOVE OBJ PERSON 1=3|2=4 (i.e. x1=x2 and y1=y2) (2) LOVE EXPR PERSON LOVE OBJ PERSON 2=4 (i.e. y1=y2) (3) uniquely encode the G2 subgraphs (f1), (f2) and (f3). Moreover, we can reconstruct the logical formulas of the corresponding SCGs, given (1), (2) or (3), by building monadic predicates and adding the variables and the respective existential quantifiers. Thus we have found the encoding we needed; it is based on insights stemming from both the logical and graphical CG nature. Now we can work with the linear sequences of support labels and the associated identity annotations, interpreting them as SCGs.
We present an algorithm for the construction of a minimal acyclic automaton with
markers at the final states, which builds a list of all KB subgraphs and their respective
injective generalisations. All language' words are constructed here; results from
automata theory build further the FSA itself [
Equivalence classes 1. {{x1},{y1},{x2},{y2}} 2. {{x1, y1}, {x2}, {y2}} 3. {{x1,x2}, {y1}, {y2}} 4. {{x1}, {y1, x2}, {y2}} 5. {{x1, y1, x2}, {y2}} 6. {{x1, y2}, {y1}, {x2}} 7. {{x1}, {y1, y2}, {x2}} 8. {{x1}, {y1}, {x2,y2}} 9. {{x1, y1, y2}, {x2}} 10. {{x1, y1}, {x2, y2}} 11. {{x1, x2, y2}, {y1}} 12. {{x1, x2}, {y1, y2}} 13. {{x1, y2}, {y1, x2}} 14. {{x1}, {y1, x2, y2}} 15. {{x1, y1, x2, y2}}
irrelevant: distinct arguments build disconnected SCGs
x1=y1 is impossible as no loops are allowed G1: LOVE EXPR PERSON:John LOVE OBJ PERSON:Mary
G2: LOVE EXPR PERSON PERSON ATTR NAIVE x1=y1 is impossible as no loops are allowed G2: PERSON ATTR EGOISTIC LOVE EXPR PERSON
(f3) LOVE EXPR PERSON LOVE OBJ PERSON Acyclic subgraph of G2 with distinct 1st arguments of the two conjuncts and equivalent 2nd arguments x2=y2 is impossible as no loops are allowed x1=y1 is impossible as no loops are allowed x1=y1, x2=y2 is impossible as no loops are allowed x2=y2 is impossible as no loops are allowed (f2) LOVE EXPR PERSON LOVE OBJ PERSON
Cyclic subgraph of G2 with equivalent 1st and equivalent 2nd arguments of the two conjuncts
no such example in the sample graphs x2=y2 is impossible as no loops are allowed x1=y1=x2=y2 is impossible as no loops are allowed CHAR-types: lin_labels, identity, new_lin_labels; Arrays of lists: list_subgraphs; list_gen_graphs; Arrays: words_markers(CHAR, <CHAR,CHAR,CHAR>) and sorted_words_markers(CHAR, {<CHAR,CHAR,CHAR>, ..., <CHAR,CHAR,CHAR>}); function <identity(G), lin_labels(G)> = GRAPH_LINEARISATION(G, Σ) where G is a SCG presented in logical/graphical format over an ordered alphabet Σ. Given G, this function returns the pair (i) identity(G) – a sorted marker for identity of concept instances and (ii) lin_labels(G) which contains the linear sequence of sorted G labels, where each binary predicate in G is presented as a triple concept1-relation-concept2. The function integrates interfaces between our encoding and the other CG formats; it simplifies and normalises the input graph G and translates it to the desired linearised form. The sorted identity-marker is a string enumerating the equivalent c-nodes; it contains digits, '=' and '|' as shown in the samples (1), (2) and (3) above.
function list_gen_graphs = COMPUTE_INJ_GEN(G, Σ1, Σ2, λ). This function returns the list of all injective generalisations written in alphabet Σ2, for a given graph G written in alphabet Σ1. The generalisations are calculated using the mapping λ, which defines how the symbols of Σ1 are to be generalised by symbols of Σ2. function new_lin_labels(Gsub) = ENSURE_PROJ_MAPPING(lin_labels(Gsub), identity(Gsub), Σ1, lin_labels(Ggen), identity(Ggen), Σ2, λ) Given a linearised subgraph Gsub, written in the ordered alphabet Σ1 and its injective generalisation Ggen, written in the ordered alphabet Σ2, this function checks whether the order of c-nodes in the sorted string lin_labels(Ggen) corresponds to the order of the respective specialised c-nodes in the sorted string lin_labels(Gsub). The check is done following the mapping λ, which defines how the symbols of Σ1 are to be generalised by symbols of Σ2. (Remember that Gsub and Ggen contain equal number of binary predicates, where the ones of Ggen generalise some respective predicates of Gsub). If the c-nodes order in lin_labels(Ggen) corresponds to the order of the respecttive specialised c-nodes in lin_labels(Gsub), new_lin_labels(Gsub) = lin_labels(Gsub). Otherwise, lin_labels(Gsub) is rearranged in such a way that the order of its nodes is aligned to the order of generalising nodes in Ggen. Let lin_labels(Ggen) be as follows: cgen11 relgen1 cgen12 cgen21 relgen2 cgen22 … cgenk1 relgenk cgenk2 where cgenij, 1≤i≤k, j=1,2 are labels of c-nodes and relgeni, 1≤i≤k, are labels of r-nodes. Then lin_labels(Gsub) is turned to the sequence of labels
csub11 relsub1 csub12 csub21 relsub2 csub22 … csubk1 relsubk csubk2 where cgenij≥csubij for 1≤i≤k, j=1,2 and relgeni≥ relsubi for 1≤i≤k. The re-arranged labels of Gsub nodes are returned in new_lin_labels(Gsub). The string new_lin_labels(Gsub) is no longer lexicographically sorted but its nodes' order is aligned to the order of the generalising nodes in Ggen. The c-nodes' topological links in new_lin_labels(Gsub) are given by identity(Ggen). Thus an injective projection π: Ggen→Gsub is encoded. Algorithm 1. Construction of a minimal acyclic FSA with markers at the final states AKB = ‹Σ, Q, q0, F, Δ, E, μ› which encodes all subgraphs' injective generalisations for a KB of SCGs with binary conceptual relations {G1, G2,…, Gn} over support S.
Step 1, defining the finite alphabet Σ: Let S = (TC, TR, I, τ) be the KB support according to definition 1. Define Σ={x | x∈TC or x∈TR}∪{ x:i | x∈TC, i∈I and τ(i)=x}. Order the m symbols of Σ using certain lexicographic order Ω = <a1,a2,…,am>.
Step 2, indexing all c-nodes: Juxtapose distinct integer indices to all KB c-nodes, to ensure their default treatment as distinct instances of the generic concept types. Then ΣKB = {aij | ai∈Σ, 1≤i≤m and j is an index assigned to the KB c-node ai, 1≤j≤pi or j='none' when no indices are assigned to ai}.
Order the symbols of ΣKB according to the lexicographic order ΩKB = <a1s1,…, a1su, a2p1,…, a2pv, ….., amq1,…, amqx> where s1,s2,…su are the indices assigned to a1; p1,…,pv are the indices assigned to a2; q1,…qx are the indices assigned to am and s1<s2<…<su, p1<p2<…<pv, ….. and q1<q2<…<qx . Define a mapping λ: ΣKB→Σ where λ(aij)=ai for each aij ∈ΣKB, 1≤i≤m and j is an index assigned in ΣKB to the symbol ai∈Σ.
/* Step 3, computation of all KB (conceptual) subgraphs: */ for i := 1 to n do begin list_subgraphs(i) := { Gsub-ji | Gsub-ji⊆Gi according to definition 10}; end; /* Step 4, computation and encoding of all injective generalisations: */ var gen_index := 1; for each i and Gsub-ji in list_subgraphs(i) do begin <identity(Gsub-ji), lin_labels(Gsub-ji)> := GRAPH_LINEARISATION(Gsub-ji , ΣKB); list_gen_graphs(i,j) := COMPUTE_INJ_GEN(Gsub-ji, ΣKB, Σ, λ); for each Ggen in list_gen_graphs(i,j) do begin <identity(Ggen), lin_labels(Ggen)> := GRAPH_LINEARISATION(Ggen, Σ); new_lin_labels(Gsub-ji) := ENSURE_PROJ_MAPPING(lin_labels(Gsub-ji), identity(Gsub-ji), ΣKB, lin_labels(Ggen), identity(Ggen), Σ, λ); words_markers(gen_index, 1) := lin_labels(Ggen); words_markers(gen_index, 2) := <identity(Ggen), new_lin_labels(Gsub-ji), Gi>; gen_index := gen_index+1; end; end; sorted_words_markers := SORT-BY-FIRST-COLUMN(words_markers) ; while sorted_words_markers(*,1) contains k>1 repeating words in column 1, starting at row p do begin sorted_words_markers(p, 2) := {sorted_words_markers(p,2),
sorted_words_markers(p+1,2),…, sorted_words_markers(p+k-1,2)}; for 1≤s≤k-1 do begin DELETE-ROW(sorted_words_markers(p+s,*) end; end; L = {w1, w2,…,wz | wi∈ sorted_words_markers(*,1), 1≤i≤z and wi≤wj according to Ω, for i≤j, 1≤i≤z and 1≤j≤z }.
/* Step 5, FSA construction: */
Consider L as a finite language over Σ, given as a list of words sorted according to Ω.
Apply results of [
M7: <1=3|2=5, LOVE EXPR PERSON LOVE OBJ PERSON PERSON ATTR NAIVE, G2> Fig. 4 shows the minimal FSA with markers at the final states, which encodes the 33 injective generalisations of the subgraphs in M1-M7. New markers M8-M11 were created at step 4 of algorithm 1, to properly encode all data.
The injective projection is calculated by a look-up in the minimal acyclic FSA, which encodes all the KB generalisations, with a word built by the query graph labels. There are two main on-line tasks, given a query G: (i) Presenting G as a sorted sequence of support symbols, and calculation of its identity-type for linear time O(n); (ii) Look-up in the FSA AKB by a word wG. Its complexity is clearly O(n), where n is the number of G symbols. No matter how large the KB is, all injective projections of G to the KB are found at once with complexity depending on the input length only.
Now we see the benefits of the suggested explicit off-line enumerations. Actually we enumerate all possible injective mappings from all injective projection queries to the KB subgraphs. It becomes trivial to check whether a SCG with binary conceptual relations is equivalent to certain SCG in the KB. Thus the lexicographic ordering of conceptual labels provides a convenient formal framework for SCGs comparison.
We have generated randomly type hierarchies of 600 concept types and 40 relation types. The experimental KB consists of 291 SCGs with binary conceptual relations in normal form, each with length of 3-10 conjuncts. These SCGs have 6753 (conceptual) subgraphs with 10436190 different injective generalisations. After the lexicographic sorting of all words (injective generalisations' labels) is done, they belong to 13885 identity-types- i.e. they are topologically structured in a relatively uniform way. The minimal acyclic FSA with markers at the final states, which recognises all injective generalisations, has 2751977 states and 3972096 transition arcs. The input text file of sorted words, prepared for the FSA construction, is 891,4 MB. The minimal FSA is 52,44 MB but the markers-subgraphs are encoded externally, i.e. markers contains only pointers. The input text file is compressed about 18 times when building the minimal FSA, which is only 2,4 times bigger than the zipped version of the input file.
The suggested approach implements off-line as much computations as possible and provides exclusive run-time efficiency. The implementation requires considerable offline preprocessing and large space since the off-line tasks operate on raw data. The star graphs impose strong constraints on the structural patterns while computing injective generalisations; this is intuitively clear but now we see experimental evidences about the ′uniformity′. Currently we plan an experiment with realistic data.