A Broader Picture of Random-walk Based Graph Embedding
A Broader Picture of Random-walk Based Graph Embedding
复制标题
DOI：
10.1145/3447548.3467300
复制
发表时间：
2021-08
期刊：
影响因子：
--
通讯作者：
Zexi Huang;A. Silva;Ambuj K. Singh
中科院分区：
文献类型：
--
作者：
Zexi Huang;A. Silva;Ambuj K. Singh
基于随机游走的图嵌入为许多与图相关的下游任务提供了有效的解决方案。然而，丰富的嵌入文献已经越来越难以比较现有的方法，并确定机会，以推进国家的最先进的。同时，现有的工作留下了几个基本的问题-如嵌入如何捕捉不同的结构尺度，以及如何将它们应用于有效的链接预测-未回答。本文解决了这些挑战与分析框架的随机游走为基础的图形嵌入，由三个组成部分：一个随机游走过程，一个相似性函数，和嵌入算法。我们的框架不仅对许多现有的方法进行了分类，而且还自然地激发了新的方法。有了它，我们说明了在多个尺度上结合嵌入以提高下游任务性能的新方法。我们还表明，基于自协方差相似性的嵌入，当与链接预测的点积排名配对时，优于基于逐点互信息相似性的最先进方法高达100%。
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%.