Low-dimensional path representation learning

Question

I have a graph (ex: map) and multiple sequences of ids representing different paths.

• A vertex represents a region/area
• An edge between 2 vertices : a crossing from a region to another
• A graph path (sequences of crossings) : a trajectory

Like the examples below:

path1 = [15,1,2,3]
path2 = [1,2,9]
path3 = [15,3]

All the paths come from the same graph structure and they could have various high sizes (~50). Then I would like to get a low-dimensional vector (one for each path) in order to perform an Approximate Neighbors Search (it's a kind of search technique to find out the closest data points to another).

I have found some papers about graph representation learning but nothing relevant. Should I explore an NLP technique or a graph embeddings technique?

Answer 1

Assuming that the goal is to find paths which are similar with each other in the dataset, I would suggest trying to directly compare pairs of paths with an appropriate similarity/distance function. Since the order in the path is clearly relevant, I think a sequence-based measure like the Levenshtein edit distance is a good candidate.

The idea would be to calculate the distance between every pair of paths in the dataset. Once this is done the matrix of distances can be used to cluster similar paths together.

I think that the only potential issue with this approach is computational complexity: in case there are many paths in the dataset, computing all the pairs of distances could be costly.

Answer 2

Graph embedding gives an embedding/vector per node. That is analogous to word embedding in NLP, which gives one vector per word (often methods are quite related, e.g. word2vec vs node2vec, deepwalk etc).

If you want to embed paths, that sound analogous to "sentence embedding". There are a bunch of methods you could find for that (inc RNNs etc), but it is often found they don't do that much better than just obtaining node embeddings and then take the average of all node vectors in a path as its vector/embedding. (e.g. see this paper and others by Wieting)