Graph embedding based on random-walks supports effective solutions for many graph-related downstream tasks. However, the abundance of embedding literature has made it increasingly difficult to compare existing methods and to identify opportunities to advance the state-of-the-art. Meanwhile, existing work has left several fundamental questions -- such as how embeddings capture different structural scales and how they should be applied for effective link prediction -- unanswered. This paper addresses these challenges with an analytical framework for random-walk based graph embedding that consists of three components: a random-walk process, a similarity function, and an embedding algorithm. Our framework not only categorizes many existing approaches but naturally motivates new ones. With it, we illustrate novel ways to incorporate embeddings at multiple scales to improve downstream task performance. We also show that embeddings based on autocovariance similarity, when paired with dot product ranking for link prediction, outperform state-of-the-art methods based on Pointwise Mutual Information similarity by up to 100%.

该论文提出了一个基于随机游走的图嵌入分析框架，包括三个组件：随机游走过程、相似性函数和嵌入算法，该框架不仅可以分类许多现有方法，而且自然地激发新方法，通过它，我们演示了改进下游任务性能的多个尺度嵌入的新方法。此外，我们还发现，基于自协方差相似性的嵌入，在与点积排名进行链路预测时，比基于点互信息相似性的最先进方法表现提高了多达100％。

随机游走图嵌入的更广泛视角