低维路径表示学习

Question

我有一个图(例如: map)和代表不同路径的多个ids序列。

• 顶点表示区域/区域
• 两个顶点之间的边缘:从一个区域到另一个区域的交叉
• 图路径(交叉序列)：轨迹

如下所示：

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

所有的路径都来自相同的图结构，它们可以有不同的大尺寸(~50)。然后，我想得到一个低维向量(每个路径一个)，以执行近似邻域搜索(这是一种搜索技术，用于查找最接近另一条路径的数据点)。

我发现了一些关于图表示学习的论文，但没有任何相关的内容。我应该探索NLP技术还是图形嵌入技术？

Answer 1

假设目标是在数据集中找到彼此相似的路径，我建议使用适当的相似/距离函数直接比较路径对。由于路径中的顺序是明确相关的，我认为像Levenshtein编辑距离这样的基于序列的度量是一个很好的候选。

这样做的目的是计算数据集中每一对路径之间的距离。一旦这样做，距离矩阵就可以用来将相似的路径聚在一起。

我认为这种方法的唯一潜在问题是计算复杂性:如果数据集中有许多路径，那么计算所有的距离可能会很昂贵。

Answer 2

图嵌入给出了每个节点的嵌入/向量。这类似于NLP中的字嵌入，它给出了每个单词的一个向量(通常是相关的方法，例如word2vec与node2vec、深度行走等)。

如果您想嵌入路径，这听起来类似于“句子嵌入”。你可以找到很多方法( its等)，但是人们经常发现它们没有比仅仅获得节点嵌入更好的方法，然后将路径中所有节点向量的平均值作为它的向量/嵌入。(例如，参见本论文和其他人的Wieting)