Knowledge Graph Pathfinding and Traversal

Section 5.3 path finding and traversal shortest paths weighted traversal and the real world use cases where graph path finding outperforms every alternative. Finding the shortest path between two nodes is one of the most fundamental operations in graph analysis. Neo4jds gives you two production grade algorithms for weighted shortest paths. Dystra and AAR. The left block shows Dystra. You project a city graph with a road relationship type that carries a distance kilometers property. Then you find your source and target nodes by name. Call GDS.shortest path.dystra.stream and specify the weight property. The result includes the path itself and the total cost. You use nodes on the path to extract the city names in order. The right block shows AAR on the same graph. The difference is the additional latitude and longitude properties. AAR uses geographic coordinates as a heruristic to estimate how far each candidate node is from the target. This heristic lets it skip exploring nodes that are clearly moving in the wrong direction which makes it significantly faster than dystra on large spatial graphs. When to use which dystra is the right choice when you have no meaningful heristic non-geographic routing dependency resolution supply chain networks it guarantees the optimal path regardless of graph structure. AAR is the right choice when you have geographic coordinates or any other good estimate of distance to the target. It can be dramatically faster on large spatial graphs. Sometimes exploring only a fraction of the nodes Dystra would visit while still guaranteeing the optimal weighted path. Sometimes you don't want just one shortest path. You want all of them. Or you want the minimum cost spanning tree that connects an entire network. Let me show you both. The left block uses all shortest paths, a built-in cipher function, not a GDS call, to find all paths of equal minimum length between two drug nodes. Below that, a variable length match shows how to find all paths up to four hops ordered by length. This is useful for discovering indirect interaction chains, paths between entities that have no direct connection. The right block shows the minimum spanning tree algorithm. You provide a source node and a weight property and GDS writes a spanning tree back to the graph as a new relationship type. The spanning tree connects all nodes in the projection with the minimum total edge weight, the cheapest set of roads that still connects every city or the minimum set of communication links that still keeps a network fully connected. Three industry use cases. Drug interaction pathways. A drug may not directly interact with another, but both interact with a shared enzyme. All shortest paths reveals those indirect chains, which is exactly how pharmacco vigilance systems flag multi-drug regimens for review. Supply chain routing. Dystra on a logistics graph finds the minimum cost route from supplier to warehouse to distribution center accounting for transport costs and lead times as edge weights. Fraud network traversal money moves through networks of accounts sometimes through five or six intermediaries specifically to obscure the trail. All shortest paths between a known source account and a known beneficiary uncovers every viable route, giving investigators the full picture of how funds were moved.