Abstract
Semi-supervised and unsupervised machine learning methods often rely ongraphs to model data, prompting research on how theoretical properties ofoperators on graphs are leveraged in learning problems. While most of theexisting literature focuses on undirected graphs, directed graphs are veryimportant in practice, giving models for physical, biological, ortransportation networks, among many other applications. In this paper, wepropose a new framework for rigorously studying continuum limits of learningalgorithms on directed graphs. We use the new framework to study the PageRankalgorithm, and show how it can be interpreted as a numerical scheme on adirected graph involving a type of normalized graph Laplacian. We show that thecorresponding continuum limit problem, which is taken as the number of webpagesgrows to infinity, is a second-order, possibly degenerate, elliptic equationthat contains reaction, diffusion, and advection terms. We prove that thenumerical scheme is consistent and stable and compute explicit rates ofconvergence of the discrete solution to the solution of the continuum limitPDE. We give applications to proving stability and asymptotic regularity of thePageRank vector.