Subgraph isomorphism between stored graphs

[Ivan Ševčík]

I was wondering if Neo4j supports subgraph isomorphism (finding pattern in a target), if both graphs come from the database. I'm quite new to Neo4j but to me it seems that the pattern is only described by Cypher language. However, what if I have some interesting and decently sized graph, and I would like to find all graphs in database that contain this graph. I think that theoretically, the "query" graph could be transformed to Cypher, although it screams at me "ineffective". Also building the Cypher query from graph might not be as easy as it seems until I attempt it. So my 2 questions would be:

1) Is there some built-in algorithm, that could perform this operation efficiently?
2) If not, is it possible to build GENERIC Cypher query that, given 2 graphs, would tell if one is subgraph of the other? And by generic I mean that it's not uniquely constructed for each queried graph.

Note that in this example, there would be a lot of disconnected graphs in DB. The way I was considering to distinguish graphs was by having a property like ".graphId" on each vertex, or possibly by having "partOf" relationship from all vertices to a single node representing the graph as whole.

Regarding the first question, I found some hints here and here, but I'm not sure what these are for or how to use them. On the other side, I've found a webinar followup from 2012 that answers:

Is subgraph isomorphism possible?

• Subgraph matching is not directly supported, just path pattern-matching. So the match would have to be expressed as a path pattern.

I wonder if there was some development in this area in the last 5 years. I will be glad for any piece of information, although direct yes+how / no+why would earn you my eternal gratitude.

[Michael Hunger]

What is your concrete use-case?

What do your graph structures look like? DAG / Cycles  ...

How would you limit the subgraphs to match on, just them being disconnected / via the mentioned graphId / ...?

Today it would make most sense to provide a user defined procedure that, being provided two nodes (of two disconnected graphs) to provide the information if one is a subgraph of the other, or compute a similarity (SimRank)

Cheers, Michael

--
You received this message because you are subscribed to the Google Groups "Neo4j" group.
To unsubscribe from this group and stop receiving emails from it, send an email to neo4j+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Jim Salmons]

Hi Michael & OP Ivan,

Upon seeing this thread pop up I could not help but dig out a homework assignment I did in the early 1980's while in the doctoral program in mathematical social sciences (now commonly called "social networks") at UC Irvine. I blew my prof's mind with this presentation that described a graph algorithm to compute self-complementary graphs. This was an optional extra-credit item on a daily graph theory homework assignment. Noone else in the class even tried to answer the specific question of the SC graph of 8 nodes much less provide an algorithm to compute all SC graphs of an arbitrary number of nodes. Here is an image from a page of that assignment:

And I have attached a PDF of my self-complementary graph homework from UC Irvine, ~1984.

Mac computers were very new at the time and I was an Apple 3rd party developer. I used the brilliant FileVision graphical database program to programmatically define and render the complete set of images of the self-complementary graphs of 8 nodes. I printed the assignment on an ImageWriter. :-) This seriously blew my prof and classmates minds as they had never seen anything like it and had no idea how I did it. :D

While this is a nostalgic item from my distant past, I believe it might be interesting and helpful to Ivan. And perhaps some energetic Neo4j graph algorithm developer might find it a fun challenge to include it in the forthcoming Neo4j Graph Platform. ;-)

Happy-Healthy Vibes,

-: Jim :-  

To unsubscribe from this group and stop receiving emails from it, send an email to neo4j+un...@googlegroups.com.