Network embedding has attracted considerable research attention recently. However, the existing methods are incapable of handling billion-scale networks, because they are computationally expensive and, at the same time, difficult to be accelerated by distributed computing schemes. To address these problems, we propose RandNE, a novel and simple billion-scale network embedding method. Specifically, we propose a Gaussian random projection approach to map the network into a low-dimensional embedding space while preserving the high-order proximities between nodes. To reduce the time complexity, we design an iterative projection procedure to avoid the explicit calculation of the high-order proximities. Theoretical analysis shows that our method is extremely efficient, and friendly to distributed computing schemes without any communication cost in the calculation. We demonstrate the efficacy of RandNE over state-of-the-art methods in network reconstruction and link prediction tasks on multiple datasets with different scales, ranging from thousands to billions of nodes and edges.


翻译:最近,网络嵌入引起了相当大的研究关注。然而,现有方法无法处理10亿规模的网络,因为它们计算费用昂贵,同时难以通过分布式计算计划加速。为了解决这些问题,我们提议采用新型和简单的10亿规模的网络嵌入方法RandNE。具体地说,我们提议采用高斯随机投影法,将网络绘制成一个低维嵌入空间,同时保持节点之间的高度一致性。为减少时间复杂性,我们设计了一个迭代投影程序,以避免明确计算高阶近似。理论分析表明,我们的方法非常高效,在计算过程中,在没有任何通信成本的情况下,对分布式计算计划十分友好。我们展示了兰德尼在网络重建中相对于最新技术方法的功效,并将多个数据集的预测任务与不同尺度联系起来,范围从数千至数十亿个节点和边缘不等。

4
下载
关闭预览

相关内容

网络嵌入旨在学习网络中节点的低维度潜在表示,所学习到的特征表示可以用作基于图的各种任务的特征,例如分类,聚类,链路预测和可视化。
【ICLR 2019】双曲注意力网络,Hyperbolic  Attention Network
专知会员服务
82+阅读 · 2020年6月21日
【清华大学】图随机神经网络,Graph Random Neural Networks
专知会员服务
152+阅读 · 2020年5月26日
必读的7篇IJCAI 2019【图神经网络(GNN)】相关论文-Part2
专知会员服务
58+阅读 · 2020年1月10日
内涵网络嵌入:Content-rich Network Embedding
我爱读PAMI
4+阅读 · 2019年11月5日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
14+阅读 · 2019年4月13日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
机器学习(33)之局部线性嵌入(LLE)【降维】总结
机器学习算法与Python学习
7+阅读 · 2017年12月21日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
4+阅读 · 2018年5月21日
Arxiv
3+阅读 · 2018年2月19日
VIP会员
相关VIP内容
相关资讯
内涵网络嵌入:Content-rich Network Embedding
我爱读PAMI
4+阅读 · 2019年11月5日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
14+阅读 · 2019年4月13日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
机器学习(33)之局部线性嵌入(LLE)【降维】总结
机器学习算法与Python学习
7+阅读 · 2017年12月21日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员