在Neo4j中没有超级节点的最短路径

Question

我有一个包含5亿个节点和边的Neo图。我想找到避开超级节点的两个节点之间的最短路径（即使这条路径比经过超级节点的路径要长）。

以下查询在较小的图形上运行良好，但对于我所处理的图形大小永远无法完成：

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

如果我删除WHERE子句，它会非常快，通常是亚秒级别。

如何加速？预计算节点度数并对其进行索引是否有帮助？是否应该复制除超级节点相邻边以外的所有边，给它们一个新标签，并将它们用于我的shortestPath查询，而不使用WHERE子句？还有其他建议吗？

- Tom

---

如果您删除标签会发生什么？ WHERE NONE(x IN NODES(p) WHERE size((x)--()) > 1000) - Nicole White

好的，非常有道理。抱歉，我实际上是在没有标签的WHERE子句中进行测试的。第一个标签会出错。第二个标签似乎没有任何影响。让我更新我的问题以删除这些标签。原始代码如下： WHERE NONE(x:Node IN NODES(p) WHERE size((x:Node)--())>1000) - Tom

Answer 1

您可以尝试为超级节点添加标签：

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

这段代码是否在你的数据上运行并完成了？你有多少个超级节点和普通节点？

那么请尝试：

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

我想检查标签会更快。

- Martin Preusse

---

谢谢。虽然这并没有解决问题，但它还是很有用的。我有将近0.5G个节点。我能够在9分钟内运行您的第一个查询来标记超级节点。其中有525个（即度数>1k的节点）。 不幸的是，如果n和m之间有超级节点，第二个查询仍然需要很长时间。据我所见，如果这些节点附近没有超级节点，它会非常快。 - Tom

Answer 2

据我所知，Neo4j最短路径实现在WHERE ALL仅包含关系（而非节点）时会剪枝路径。如果无法剪枝查询，则会找到所有路径然后过滤它们（速度较慢）。

正如Martin所说，您可以添加一个标签：

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

然后通过边来查询节点的标签：

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

这将使Neo4j使用优化的双向广度优先（快速）查询。更多信息请参阅：https://neo4j.com/docs/developer-manual/current/cypher/execution-plans/shortestpath-planning/

- Adam