A continuum limit for the PageRank algorithm
A continuum limit for the PageRank algorithm
复制标题
DOI：
10.1017/s0956792521000097
复制
发表时间：
2020-01
期刊：
影响因子：
--
通讯作者：
Amber Yuan;J. Calder;B. Osting
中科院分区：
文献类型：
--
作者：
Amber Yuan;J. Calder;B. Osting
半监督和非监督机器学习方法通常依赖于图来建模数据，这促使人们研究如何利用图上算子的理论性质来解决学习问题。虽然现有的大多数文献都集中在无向图上，但有向图在实践中非常重要，它给出了物理、生物或交通网络的模型，以及许多其他应用。在本文中，我们提出了一个新的框架，用于严格研究有向图上的学习算法的连续统极限。我们使用新的框架来研究PageRank算法，并展示了它如何被解释为涉及一类归一化图拉普拉斯的有向图上的数值方案。我们证明了相应的连续体极限问题是一个包含反应项、扩散项和平流项的二阶可能退化的椭圆型方程。我们证明了数值格式的一致性和稳定性，并计算了连续介质极限偏微分方程解的离散解的显式收敛速度。我们给出了证明PageRank向量的稳定性和渐近正则性的应用。最后，我们用数值实验说明了我们的结果，并探索了它在数据深度方面的应用。
Semi-supervised and unsupervised machine learning methods often rely on graphs to model data, prompting research on how theoretical properties of operators on graphs are leveraged in learning problems. While most of the existing literature focuses on undirected graphs, directed graphs are very important in practice, giving models for physical, biological or transportation networks, among many other applications. In this paper, we propose a new framework for rigorously studying continuum limits of learning algorithms on directed graphs. We use the new framework to study the PageRank algorithm and show how it can be interpreted as a numerical scheme on a directed graph involving a type of normalised graph Laplacian. We show that the corresponding continuum limit problem, which is taken as the number of webpages grows to infinity, is a second-order, possibly degenerate, elliptic equation that contains reaction, diffusion and advection terms. We prove that the numerical scheme is consistent and stable and compute explicit rates of convergence of the discrete solution to the solution of the continuum limit partial differential equation. We give applications to proving stability and asymptotic regularity of the PageRank vector. Finally, we illustrate our results with numerical experiments and explore an application to data depth.