Researchers have designed many algorithms to measure the distances between graph nodes, such as average hitting times of random walks, cosine distances from DeepWalk, personalized PageRank, etc. Successful although these algorithms are, still they are either underperforming or too time-consuming to be applicable to huge graphs that we encounter daily in this big data era. To address these issues, here we propose a faster algorithm based on an improved version of random walks that can beat DeepWalk results with more than ten times acceleration. The reason for this significant acceleration is that we can derive an analytical formula to calculate the expected hitting times of this random walk quickly. There is only one parameter (the power expansion order) in our algorithm, and the results are robust with respect to its changes. Therefore, we can directly find the optimal solution without fine-tuning of model parameters. Our method can be widely used for fraud detection, targeted ads, recommendation systems, topic-sensitive search, etc.


翻译:研究人员设计了许多算法,以测量图形节点之间的距离,例如随机行走的平均点击时间、与深电站的焦距距离、个性化的PageRank等。 成功虽然这些算法是成功的, 但仍表现不佳或过于耗时, 无法适用于我们在这个大数据时代每天遇到的巨型图表。 为了解决这些问题, 我们在此建议一个基于改进版随机行走速度的快速算法, 可以以10倍以上的加速率击败深海行走结果。 如此显著加速的原因是我们可以得出一个分析公式, 以快速计算这种随机行走的预期点击时间。 我们的算法中只有一个参数( 权力扩展顺序), 其结果在变化方面是稳健的。 因此, 我们可以直接找到最佳的解决方案, 不微调模型参数。 我们的方法可以被广泛用于欺诈检测、 定向广告、 建议系统、 专题敏感搜索等 。

0
下载
关闭预览

相关内容

最新《Transformers模型》教程,64页ppt
专知会员服务
305+阅读 · 2020年11月26日
【清华大学】图随机神经网络,Graph Random Neural Networks
专知会员服务
154+阅读 · 2020年5月26日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
图表示学习Graph Embedding综述
图与推荐
10+阅读 · 2020年3月23日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
已删除
将门创投
5+阅读 · 2017年11月22日
【论文】图上的表示学习综述
机器学习研究会
14+阅读 · 2017年9月24日
Random and quasi-random designs in group testing
Arxiv
0+阅读 · 2021年1月15日
Pointer Graph Networks
Arxiv
7+阅读 · 2020年6月11日
Arxiv
6+阅读 · 2018年4月24日
VIP会员
相关资讯
图表示学习Graph Embedding综述
图与推荐
10+阅读 · 2020年3月23日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
已删除
将门创投
5+阅读 · 2017年11月22日
【论文】图上的表示学习综述
机器学习研究会
14+阅读 · 2017年9月24日
Top
微信扫码咨询专知VIP会员