# Shortest Path Between Two Nodes in a +10 Million Nodes Graph

I have my own knowledge graph representation, read from ConceptNet and NELL, containing tens of millions of nodes in which I want to calculate the nearest distance (if any) between two concept nodes. The application is to find out how two concepts are related in the simplest explainable way. Typical connectedness of the graph lie in the range 100-1000. Do I need some variant of Dijkstras in this case? I want the solution to require at most around 10 GBytes of RAM. My current memory usage is around 2 GB.

• For a completely arbitrary graph this is unrealistic to do with acceptable performance. Is there anything special about the graph? Is there any kind of locality? Any heuristics? Can the graph be separated into areas with few inter-area connections? Oct 28 '14 at 19:22
• I'm only aware about the connectedness, nothing more. My current application is to find the path(s) between two arbitrary concepts to answer a typical question: "How are these concepts related?" I believe the realistic solution to this problem is to make the search algorithm time-constained. What do you think? Oct 28 '14 at 19:27
• Have you tried A* just to see what the performance is like? Do you have no heuristic at all? Oct 28 '14 at 19:47
• Depending on the structure of the data, you might be able to pre-process it into clusters. These clusters then are a simplified representation of the whole graph. When searching for a path, you would first search for a path between the clusters, which could also yield precalculated lower and upper bounds on the actual path length. Then you could search for the actual path using only nodes in the clusters which are part of the cluster-path. Paths that exceed the upper path length determined from the clusters can be pruned.
– amon
Oct 28 '14 at 19:53
• Is it likely that the long paths usually use a limited subset of vertices ("key ideas")? If yes, then you could probably adapt some of the techniques used for road networks. This research group in Karlsruhe provides papers describing some methods and you can find more via their references. You don't have to identify the key vertices; the contraction hierarchy or highway hierarchy algorithms will do it themselves if the graph is sufficiently non-homogenous. Oct 29 '14 at 14:43

2 simple solutions that immediately arise:

Precompute everything via something like Johnson's algorithm, or use a standard search algorithm every time as you suggested - Dijkstra for example (which boils down to simple BFS, since the graph is unweighted).

The first requires way too much storage/RAM to do. The second is prohibitively slow. What you (likely) want is a hybrid solution that combines some precomputation (possibly a long one, but that doesn't require much storage), and a shorter per-query computation.

Clustering
One approach would be to somehow cluster your graph, and compute the distances between the exit vertices of the clusters. Then a search algorithm wouldn't even consider paths in clusters (or rather use the precomputed minimum paths between exits), unless that cluster contains the start or end point.

A-star
Another is to compute a heuristic and use A* (or any other heuristic-assisted search). You mentioned that you do not have any information about the graph, except the connectedness, so you may need to devise and precompute such a heuristic.

One such heuristic may be a minimal "order n spanning graph". There's likely a proper term for this, but it's been too long since my Uni days, so I'll explain what I mean. I call a "order n spanning graph" a collection of vertices, such that any vertex in your original graph is reachable from some vertex in this collection via a path of length at most n.

If you've got such a collection, along with a mapping of `Vertex -> closest vertex in spanning graph + distance to it`, and the distances between any 2 points in the spanning graph, then you have a heuristic:

The distance between two vertexes is at least the distance between their closest vertices in the spanning tree + distances to them - 2*n. (Why? Because the distance between the spanning vertices is at most the distance between A and B + distances to them).

This is an admissible heuristic, hence A* will do a good job using it.

The smaller the order of the collection, the better the heuristic and faster the search. But that also means that the spanning graph will be larger, and hence you will need a larger matrix of distances. I would probably start off with a graph of order 50 or so, but you can tweak it, depending on the exact shape/nature of the graph.

Optimize for the average use-case
Also worth noting that you can optimize not for the graph you have, but for the queries you answer. If they are typically to compute precise, but small distances, you may want to precompute some, but not all values (For example, distances from each node to anything reachable by 3 or less steps?). You'd need fallback to one of the methods above in this case, but that may be sufficient.

This also begs the question: Is full precision really necessary on longer paths for you? Maybe the specification can be relaxed in this sense?