Shortest paths without supernovae in Neo4j

Question

I have a graph with 0.5 billion nodes and edges in Neo. I want to find the shortest path between two nodes that avoids supernovae (even if it is longer than the paths that have supernodes).

The following query works fine for smaller graphs, but never ends for the size graph I'm dealing with:

MATCH (n:Node { id:'123'}),(m:Node { id:'234' }), p = shortestPath((n)-[*..6]-(m)) WHERE NONE(x IN NODES(p) WHERE size((x)--())>1000) RETURN p 

If I delete the WHERE clause, it is very fast. Usually a subsecond.

How can I speed it up? Would predict node degrees and index their help? Should I resort to duplicating all edges except adjacent to the super-nodes, giving them a new label and using them for my shortest request without a WHERE clause? Any other suggestions?

Answer 1

As far as I can tell about Neo4j empty paths for shortest paths, when WHERE ALL contains only relationships (not nodes). Where it cannot trim requests, it finds all the paths and then filters them (slowly).

As Martin says, you can add a shortcut:

 MATCH (x:Node) WHERE size((x)--())>1000 SET n:Supernode 

And then query the node label through the edges:

 MATCH p = shortestPath((n:Node { id:'1'})-[*..6]-(m:Node { id:'2' })) WHERE ALL( rel IN relationships(p) WHERE not (startNode(rel):Supernode or endNode(rel):Supernode)) RETURN p 

This will allow Neo4j to use an optimized, bi-directional, fast (fast) request.

Read more here: https://neo4j.com/docs/developer-manual/current/cypher/execution-plans/shortestpath-planning/

Answer 2

You can also try adding a shortcut for supernovae:

 MATCH (x:Node) WHERE size((x)--())>1000 SET n:Supernode 

Is this running and ending your data? How many supernodes and normal nodes do you have?

Then try:

 MATCH (n:Node { id:'123'}),(m:Node { id:'234' }) WITH n, m MATCH p = shortestPath((n)-[*..6]-(m)) WHERE NONE(x IN NODES(p) WHERE (x:Supernode)) RETURN p 

I assume label verification is faster.