Graph Data Science Breadth-first-search doesn't give desired results

Neo4j Graph Platform Graph Algorithms/Graph Data Science
1

I have the following Graph Data Science BFS call. In this call, When I gave both 'Apple Inc.' and 'Microsoft' as target nodes, it only returns results with 'Steve Jobs' and 'Apple' which are directly linked. When I only give 'Microsoft' as target node, it returns a lot of nodes including source and target and many irrelevant.

I'd expect it to return only the PATH although it returns a lot of nodes(about 300) that are not in the path. I also would expect it that when I give both 'Apple' and 'Microsoft' as target nodes to return a union of these two although it now only returns a very small graph with only 'Steve Jobs' and 'Apple' (and a one common node linked by both)

These are some unexpected output I have encountered. Can you explain why are these happening and is there any way to get correct output?

Thanks.

My query:

MATCH (a:Entity{name:'Steve Jobs'}), (d:Entity{name:'Apple Inc.'}), (e:Entity{name:'Microsoft'})
WITH id(a) AS source, [id(d),id(e)] AS targetNodes
CALL gds.bfs.stream('myGraph', {
sourceNode: source,
targetNodes: targetNodes,
maxDepth: 4
})
YIELD path
RETURN path
2

Hi @cuneyttyler: what version of the GDS library are you using here?

3

It's 2.0.4. Although I found that dijkstra's shortest path is more suitable for my purpose and I'm also considering writing a multiple-pairs shortest path using pregel. But this question remains though as it has some points.

4

Hi @cuneyttyler,

Your questions likely have to do with the fact that BFS returns not a source--target path, but instead a list of all nodes examined until a target is hit (when one is specified).

That is why the 'Steve Jobs' -'Microsoft' query has a lot of seemingly unrelated nodes: they were all examined at some point prior to the 'Microsoft' node.

Note also that BFS quits as soon as any target node is reached, hence why putting 'Apple' in your target-list returns so few nodes.

Indeed, as you have figured out, Djikstra's output is probably better suited towards your application.

I hope the above answer your questions.

Best regards.

5

Thanks I'm using Dijkstra now.