As a measure of vertex importance according to the graph structure, PageRank has been widely applied in various fields. While many PageRank algorithms have been proposed in the past decades, few of them take into account whether the graph under investigation is directed or not. Thus, some important properties of undirected graph\textemdash symmetry on edges, for example\textemdash is ignored. In this paper, we propose a parallel PageRank algorithm specifically designed for undirected graphs that can fully leverage their symmetry. Formally, our algorithm extends the Chebyshev Polynomial approximation from the field of real function to the field of matrix function. Essentially, it reflects the symmetry on edges of undirected graph and the density of diagonalizable matrix. Theoretical analysis indicates that our algorithm has a higher convergence rate and requires less computation than the Power method, with the convergence rate being up to 50\% higher with a damping factor of $c=0.85$. Experiments on six datasets illustrate that our algorithm with 38 parallelism can be up to 39 times faster than the Power method.


翻译:根据图表结构,PageRank在多个领域广泛应用了顶点重要性的测量方法,PageRank在过去几十年中提出了许多PageRank算法,但其中很少考虑调查中的图表是否定向。因此,边缘非定向图形/textemdash对称性的某些重要属性被忽略,例如\ textemdash。在本文中,我们建议为非定向图形专门设计一个平行的PageRank算法,可以充分利用其对称性。形式上,我们的算法将Chebyshev多边近似法从实际功能领域扩大到矩阵功能领域。基本上,它反映了非定向图形边缘的对称性和可变矩阵的密度。理论分析表明,我们的算法的趋同率更高,需要比电力方法少的计算,而趋同率则提高到50<unk> 以上,而缩放系数为$c=0.85。在六个数据集上进行的实验表明,我们具有38个平行参数的算法可以比动力方法快39倍。</s>

0
下载
关闭预览

相关内容

【图与几何深度学习】Graph and geometric deep learning,49页ppt
神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
71+阅读 · 2020年8月2日
一份简单《图神经网络》教程,28页ppt
专知会员服务
123+阅读 · 2020年8月2日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
代码推荐 | 轻松实现各种图匹配 Graph matching.
图与推荐
2+阅读 · 2022年10月22日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
ICLR2019最佳论文出炉
专知
12+阅读 · 2019年5月6日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
【推荐】ResNet, AlexNet, VGG, Inception:各种卷积网络架构的理解
机器学习研究会
20+阅读 · 2017年12月17日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
3+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
23+阅读 · 2022年2月24日
Arxiv
19+阅读 · 2021年2月4日
Attentive Graph Neural Networks for Few-Shot Learning
Arxiv
40+阅读 · 2020年7月14日
Arxiv
14+阅读 · 2019年9月11日
Arxiv
24+阅读 · 2018年10月24日
VIP会员
相关VIP内容
相关资讯
代码推荐 | 轻松实现各种图匹配 Graph matching.
图与推荐
2+阅读 · 2022年10月22日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
ICLR2019最佳论文出炉
专知
12+阅读 · 2019年5月6日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
【推荐】ResNet, AlexNet, VGG, Inception:各种卷积网络架构的理解
机器学习研究会
20+阅读 · 2017年12月17日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
3+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员