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

Question

我在 Neo 中有一个包含 5 亿个节点和边的图。我想找到避免超节点的 2 个节点之间的最短路径（即使它比上面有超节点的路径长）。

下面的查询适用于较小的图形，但对于我正在处理的大小的图形永远不会完成：

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 子句？还有其他建议吗？

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

我想标签检查会更快。

Answer 2

据我所知，当 WHERE ALL 仅包含关系（不包含节点）时，Neo4j 最短路径实现会修剪路径。在它无法修剪查询的地方，它会找到所有路径然后过滤它们（慢）。

正如 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/

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

Shortest paths without supernodes in Neo4j

graph

shortest-path

neo4j

cypher