Limitations of Graph Query Languages
Where graph query languages fall short on natural language.
My first PhD project: where graph query languages run out when the data is natural language. It reads sentences as dependency graphs, uses generalised semistructured models to compare statements and check them against a fact-checked knowledge base, and maps out what the query languages can't express. Presented as a poster at the SAgE PGR Conference.
Click on the various sections to take you to the corresponding section for more detailed description.
Research Papers
If you would like to read more on this, please read the papers below authored by myself and Giacomo Bergami.
Generalised Graph Grammars for Natural Language Processing [Paper]
This seminal paper proposes a new query language for graph matching and rewriting overcoming the declarative limitation of Cypher while outperforming Neo4j on graph matching and rewriting by at least one order of magnitude. We exploited columnar databases (KnoBAB) to represent graphs using the Generalised Semistructured Model.
Poster Sections
My first PhD project: where graph query languages run out when the data is natural language. It reads sentences as dependency graphs, uses generalised semistructured models to compare statements and check them against a fact-checked knowledge base, and maps out what the query languages can't express. Presented as a poster at the SAgE PGR Conference.1. What is "hallucination" in AI?
AI hallucination is a phenomenon wherein a large language model (LLM), often a generative AI chatbot or computer vision tool, perceives patterns or objects that are nonexistent or imperceptible to human observers, creating outputs that are nonsensical or altogether inaccurate [1].
The output from the screenshot above can be seen here.
The output from the screenshot above can be seen here.
2. What is the difference between these sentences?
These graphs were generated using the DependenSee project [2], making use of English Dependency Relations [3].
This was useful as a preliminary step of the investigation, however it is not completely foolproof. As shown in sentence C, there should be a dependency where not is, but it has failed to identify it.
This was useful as a preliminary step of the investigation, however it is not completely foolproof. As shown in sentence C, there should be a dependency where not is, but it has failed to identify it.
3. How are we tackling the problem?
Noam Chomsky et. al argued that a lack of an upper bound on the number of grammatical sentences and sentence length can be explained as recursion in language, given if the structure of a sentence in which what follows the verb in a given sentence is another sentence [4].
This is demonstrated by the constructed sentence above, suggesting that this could continue indefinitely as long as we continue this structure of extending the sentence.
This is demonstrated by the constructed sentence above, suggesting that this could continue indefinitely as long as we continue this structure of extending the sentence.
4. What does an example look like?
The first investigation for this research was analysing the sentence "Alice and Bob play cricket", simple in structure as a good starting point to understand the semantics of Cypher and with it Graph Query Languages (GQLs). Using the output from DependenSee [2], this was adapted into a starting graph seen in 2 in the image above.
Then, an investigation was carried out to find a single query that could be executed to rewrite this graph to achieve what is shown in 3. The code below shows the exact query that was constructed to get this output, raising limitations of the language along the way.
The use of the WITH clause is not ideal for our assumption of the language being declarative. Furthermore, the use of User-Defined Functions (UDFs) further dispels how expressive the language is. For example, in order to concatenate the names within the graph, we must use the APOC library [5].
Then, an investigation was carried out to find a single query that could be executed to rewrite this graph to achieve what is shown in 3. The code below shows the exact query that was constructed to get this output, raising limitations of the language along the way.
The use of the WITH clause is not ideal for our assumption of the language being declarative. Furthermore, the use of User-Defined Functions (UDFs) further dispels how expressive the language is. For example, in order to concatenate the names within the graph, we must use the APOC library [5].
MATCH (a)-[b:cc]->(c)
WITH Collect(a.name) as names, Collect(DISTINCT a) as nameNodes, c
CREATE (x {name: apoc.text.join(names, ' '), cc: c.name})
FOREACH (p IN nameNodes | CREATE (y {name: p.name})<-[:orig]-(x))
WITH x
MATCH (a)-[:dobj]->(b)
CREATE (y {name: b.name})
WITH a, x, y
CALL apoc.create.relationship(x, a.name, {}, y) YIELD rel
WITH y
MATCH q=()-[]->()
RETURN q
5. What have we found so far?
The query and sentence length in the table above refers to the character length of each respectively. This demonstrates that with a ~4.8x increase in sentence length ~8.7x increase in query length, highlighting the insufficiency of Cypher when dealing with complex sentences with multiple nested disjunctions between words.
The final query for rewriting the sentence: "Matt and Tray believe that either Alice and Bob and Carl play cricket or Carl and Dan will not have a way to amuse themselves" resulted in the code below.
The final query for rewriting the sentence: "Matt and Tray believe that either Alice and Bob and Carl play cricket or Carl and Dan will not have a way to amuse themselves" resulted in the code below.
// Create the grouped nodes
MATCH (a)-[:subj]->(b)-[:cc]->(c)
WHERE (b)<-[:conj]-() OR (b)-[:conj]->()
WITH a, Collect(b.name) as names, c
WHERE size(names) > 1 // To make sure it is only grouping nodes with multiple names
OPTIONAL MATCH (a)-[:neg]->(d)
CREATE (x {name: apoc.text.join(names, ' '), cc: c.name, dobjRel: a.name})
WITH a, c, d, x, names
CALL apoc.create.addLabels(x, names) YIELD node
CALL apoc.do.when(
d IS NOT NULL,
"SET x.neg = d.name",
'',
{c:c, d:d, a:a, x:x})
YIELD value as neg
// Create the origins
WITH neg
MATCH (n) // Match only nodes with no relationships
WITH LABELS(n) as nameLabels, Collect(DISTINCT n) as nameNodes
WHERE size(nameLabels) > 0
FOREACH (nNode IN nameNodes |
FOREACH (nLabel IN nameLabels |
CREATE (y {name: nLabel})<-[:orig]-(nNode)))
// Create dobj node
WITH *
MATCH (d)<-[:dobj]-(a)
WITH Collect(DISTINCT d.name) as objects, a
FOREACH (obj IN objects |
CREATE (y {name: obj, dobjRel: a.name}))
// Check for 'det'
WITH *
MATCH (n) WHERE NOT (n)-[]->() AND NOT (n)<-[]-()
WITH n
MATCH (d)<-[:dobj]-(a)
MATCH (e)-[:orig]->()
WHERE e.dobjRel = a.name AND d.name = n.name
OPTIONAL MATCH (d)-[:det]->(f)
CALL apoc.do.when(
f IS NOT NULL,
'SET n.det = f.name',
'',
{n:n, f:f})
YIELD value as det
// Create relationships
WITH det
MATCH (m) WHERE NOT (m)-[]->() AND NOT (m)<-[]-()
WITH m
MATCH (d)<-[:dobj]-()
MATCH (e)-[:orig]->()
WHERE e.dobjRel = m.dobjRel
WITH DISTINCT e, m
CALL apoc.do.when(
e.neg IS NOT NULL,
CALL apoc.create.relationship(e, e.neg + " " + e.dobjRel, {}, m) YIELD rel RETURN rel, // ''
CALL apoc.create.relationship(e, e.dobjRel, {}, m) YIELD rel RETURN rel, // ''
{e:e, m:m})
YIELD value as dobjRel
// Create ? acl node
WITH dobjRel
MATCH (p) WHERE NOT (p)-[]->() AND NOT (p)<-[]-()
WITH p
MATCH (a)-[:acl]->(b)
MATCH (c)<-[:orig]-(d)-[]->(e)
WITH DISTINCT p, a, e
WHERE e.name = a.name
CREATE (y {name: '?'})<-[:acl]-(e)
WITH p, y
CALL apoc.create.relationship(y, p.dobjRel, {}, p) YIELD rel as aclRel
// Group the groups
WITH aclRel
MATCH (a)-[:conj]->(b)-[:cc]->(c)<-[:cc]-(a)
MATCH ()<-[:orig]-(d)-[r]->()
WHERE type(r) CONTAINS a.name OR type(r) CONTAINS b.name
WITH a, b, c, d, r
ORDER BY d.name ASC
WITH Collect(DISTINCT d.name) as names, c
CREATE (x {name: apoc.text.join(names, ' ' + c.name + ' ')})
WITH x, names
CALL apoc.create.addLabels(x, names) YIELD node as groupedGroup
// Add properties to rels
// mark
WITH groupedGroup
MATCH (c)<-[:mark]-(a)-[:dobj]->(b)
MATCH (d)-[r]->(e)
WHERE type(r) CONTAINS a.name AND b.name = e.name
CALL apoc.create.setRelProperty(r, 'mark', c.name) YIELD rel as markRel
// aux
WITH markRel
MATCH (d)<-[:aux]-(a)-[:subj]->()-[:cc]->()
MATCH ()<-[:orig]-(f)-[r]->()
WHERE type(r) CONTAINS a.name
CALL apoc.create.setRelProperty(r, 'aux', d.name) YIELD rel as auxRel
// Create rels to orig groups
WITH auxRel
MATCH (a)-[:orig]->(b)
MATCH (x) WHERE NOT (x)-[]->() AND NOT (x)<-[]-()
WITH DISTINCT a, x
WHERE apoc.text.join(LABELS(a), ' ') IN LABELS(x)
CALL apoc.create.relationship(x, 'orig', {}, a) YIELD rel as origRel
// Rel from M+T to A+B+C|C+D
WITH x
MATCH (d)<-[:subj]-(a)-[:ccomp]->(b)-[:subj]->(c)
MATCH (e)-[:orig]->(f)
WITH a, b, c, d, e, f, x
ORDER BY d.name ASC, c.name ASC
WITH Collect(DISTINCT c.name) as endNames, x, Collect(DISTINCT d.name) as startNames, e, a
WHERE apoc.text.join(startNames, ' ') = e.name AND apoc.text.join(endNames, ' ') IN LABELS(x)
CALL apoc.create.relationship(e, a.name, {}, x) YIELD rel as finalRel
WITH finalRel
MATCH q=()-[]->()
MATCH (z)
CALL apoc.create.removeLabels(z, LABELS(z)) YIELD node // Remove all labels from nodes
WITH q, z
RETURN q, z
6. What does the future look like?
After researching and identifying the limitations of GQLs, we will account for these in our newly proposed Generalised Semistructured (Data) Model (GSM) to provide a uniform representation of three data representations, where objects and values are represented by their reference identifier, to be used to insert into collections. Through this, we can express relational tables or graphs with a uniform language, running graph grammars on top of this GSM, with the goal of tackling the issue of negation aforementioned in query answering.
?. Questions you might want to ask?
- What is a graph grammar? A graph grammar, also known as graph rewriting, is a set of graph rewrite rules of the form L → R, with L being called the pattern graph and R being the replacement graph [6].
- What is a graph query language (GQL)? Graph Query Languages (GQLs) are similar to a standard query language (a language used for the retrieval of information from a database), with the difference being it is used for graph data management, whereby extracting and defining data that has been modelled as a graph.
- Why is this important? If we are to continue to use AI as heavily as companies and individuals are right now, then we need to do it right. Relying on "half-baked" intelligences still hallucinating at simple questions like what the last digits of Pi are is not acceptable. This research aims to bring to light the limitations of current query answering technologies and aim to help, if not, fix the problem and give people more intelligent efficient AI capabilities.
- Is AI going to take over the world? No, not in the Terminator sense. At the end of the day, we can always just turn it off.
There exists some current implementations of GQLs, namely the most widely adopted are: Cypher and SPARQL. Both these languages are ideal for pattern matching on graphs. Cypher was used in this investigation and SPARQL will be investigated in the full paper.
Built with
- Graph Query Languages
- Graph Rewriting
- Neo4j
- SPARQL
- C++