Pattern Matching in Neo4j

Question

Assume that in an application, the user gives us a graph and we want to consider it as a pattern and find all occurrences of the pattern in the neo4j database. If we knew what the pattern is, we could write the pattern as a Cypher query and run it against our database. However, now we do not know what the pattern is beforehand and receive it from the user in the form of a graph. How can we perform a pattern matching on the database based on the given graph (pattern)? Is there any apoc for that? Any external library?

Answer 1

I have used patterns in genealogy queries.

The X-chromosome is not transmitted from father to son. As you traverse a family tree you can use the reduce function to create a concatenated string of the sex of the ancestor. You can then accept results that lack MM (father-son). This query gives all the descendants inheriting the ancestor's (RN=32) X-chromosome.

match p=(n:Person{RN:32})<-[:father|mother*..99]-(m) 
with m, reduce(status ='', q IN nodes(p)| status + q.sex) AS c 
where c=replace(c,'MM','') 
return distinct m.fullname as Fullname

I am developing other pattern specific queries as part of a Neo4j PlugIn for genealogy. These will include patterns of triangulation groups.

GitHub repository for Neo4j Genealogy PlugIn

Answer 2

One way of doing this is to decompose your input graph into edges and create a dynamic cypher from it. I have worked on this quite some time ago, and the solution below is not perfect but indicates a possible direction. For example, if you feed this graph:

and you take the id(node) from the graph, (i am not taking the rel ids, this is one of the imperfections)

this query

WITH $nodeids AS selection
UNWIND selection AS s
WITH COLLECT (DISTINCT s) AS selection
WITH selection,
     SPLIT(left('a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z',SIZE(selection)*2-1),",") AS nodeletters
WITH selection, 
     nodeletters, 
     REDUCE (acc="", nl in nodeletters | 
       CASE acc 
         WHEN "" THEN acc+nl 
         ELSE acc+','+nl 
       END) AS rtnnodes
MATCH (n) WHERE id(n) IN selection
WITH COLLECT(n) AS nodes,selection,nodeletters,rtnnodes
UNWIND nodes AS n
UNWIND nodes AS m
MATCH (n)-[r]->(m)
WITH DISTINCT "("
    +nodeletters[REDUCE(x=[-1,0], i IN selection | CASE WHEN i = id(n) THEN [x[1], x[1]+1] ELSE [x[0], x[1]+1] END)[0]]
    +TRIM(REDUCE(acc = '', p IN labels(n)| acc + ':'+ p))+")-[:"+type(r)+"]->("
    + nodeletters[REDUCE(x=[-1,0], i IN selection | CASE WHEN i = id(m) THEN [x[1], x[1]+1] ELSE [x[0], x[1]+1] END)[0]]
    +TRIM(REDUCE(acc = '', p IN labels(m)| acc + ':'+ p))+")" as z,rtnnodes
WITH COLLECT(z) AS parts,rtnnodes
WITH REDUCE(y=[], x in range(0, size(parts)-1) | y + replace(parts[x],"[","[r" + (x+1))) AS parts2,
     REDUCE (acc="", x in range(0, size(parts)-1)  | CASE acc WHEN "" THEN acc+"r"+(x+1) ELSE acc+",r"+(x+1) END) AS rtnrels,
rtnnodes
RETURN 
    REDUCE (acc="MATCH ",p in parts2 | 
      CASE acc 
        WHEN "MATCH " THEN acc+p 
        ELSE acc+','+p 
      END)+
      " RETURN  "+
      rtnnodes+","+rtnrels+ 
      " LIMIT "+{limit} 
      AS cypher

returns something like

cypher: "MATCH (a:Person)-[r1:DRIVES]->(b:Car),(a:Person)-[r2:KNOWS]->(c:Person) RETURN a,b,c,r1,r2 LIMIT 50"

which you can feed to the next query.

In Graphileon, you can just select the nodes, and the result will be visualized as well.

Disclosure : I work for Graphileon