A Local Updating Algorithm for Personalized

PageRank via Chebyshev Polynomials E. Bautista 1 , M. Latapy 1 , (1) Sorbonne Université, CNRS, LIP6, F-75005 Paris, France

Abstract-The personalized PageRank algorithm is one of the most versatile tools for the analysis of networks. In spite of its ubiquity, maintaining personalized PageRank vectors when the underlying network constantly evolves is still a challenging task. To address this limitation, this work proposes a novel distributed algorithm to locally update personalized PageRank vectors when the graph topology changes. The proposed algorithm is based on the use of Chebyshev polynomials and a novel update equation that encompasses a large family of PageRank-based methods. In particular, the algorithm has the following advantages: (i) it has faster convergence speed than state-of-the-art alternatives for local PageRank updating; and (ii) it can update the solution of recent generalizations of PageRank for which no updating algorithms have been developed. Experiments in a real-world temporal network of an autonomous system validate the effectiveness of the proposed algorithm.

I. INTRODUCTION

A. Context

The personalized PageRank algorithm is one of the great successes in network science. It has been used in a wide amount of applications that include ranking of websites [START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF], [START_REF] Ding | Pagerank, hits and a unified framework for link analysis[END_REF], [START_REF] Haveliwala | Topic-sensitive pagerank: A context-sensitive ranking algorithm for web search[END_REF], clustering data [START_REF] Chung | A local graph partitioning algorithm using heat kernel pagerank[END_REF], [START_REF] Andersen | Local graph partitioning using pagerank vectors[END_REF], [START_REF] Tabrizi | Personalized pagerank clustering: A graph clustering algorithm based on random walks[END_REF], classifying objects [START_REF] Avrachenkov | Classification of content and users in bittorrent by semi-supervised learning methods[END_REF], [START_REF] Merkurjev | A semi-supervised heat kernel pagerank mbo algorithm for data classification[END_REF], [START_REF] Dostal | Exploration of document classification with linked data and pagerank[END_REF], [START_REF] Avrachenkov | Generalized optimization framework for graph-based semi-supervised learning[END_REF], detection of anomalous events [START_REF] Fontugne | Bgp zombies: An analysis of beacons stuck routes[END_REF], [START_REF] Yoon | Fast and accurate anomaly detection in dynamic graphs with a two-pronged approach[END_REF], [START_REF] Yao | Anomaly detection using proximity graph and pagerank algorithm[END_REF], or recommender systems [START_REF] Janabi | Recommendation system of big data based on pagerank clustering algorithm[END_REF], [START_REF] Zhang | A collaborative filtering tag recommendation system based on graph[END_REF], [START_REF] Nguyen | An evaluation of simrank and personalized pagerank to build a recommender system for the web of data[END_REF], to name a few. Additionally, the numerous theoretical properties of personalized PageRank [START_REF] Langville | Deeper inside pagerank[END_REF], [START_REF] Ipsen | Mathematical properties and analysis of google's pagerank[END_REF], [START_REF] Brezinski | The pagerank vector: properties, computation, approximation, and acceleration[END_REF], [START_REF] Pretto | A theoretical analysis of google's pagerank[END_REF] have recently been leveraged to propose a large family of PageRank extensions used in the semi-supervised learning setting, allowing to tackle challenging settings such as signed graphs [START_REF] Bautista | L γ -pagerank for semisupervised learning[END_REF], anomalous diffusion processes [START_REF] De Nigris | Fractional graph-based semi-supervised learning[END_REF], infinite dimensional spaces [START_REF] Mai | The counterintuitive mechanism of graphbased semi-supervised learning in the big data regime[END_REF], Sobolev spaces [START_REF] Zhou | Semi-supervised learning by higher order regularization[END_REF], or time-graph dual spaces [START_REF] Girault | Semi-supervised learning for graph to signal mapping: A graph signal wiener filter interpretation[END_REF]. However, despite the success of all these PageRank-based algorithms, they still pose problems from the algorithmic point of view. In particular, they do not adapt well to networks that evolve over time, a situation that we aim to address in this work.

B. Related Works

In its simplest form, personalized PageRank can be interpreted as the stationary distribution of a random walk [START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF]. This interpretation has been exploited by numerous works to develop efficient algorithms for computing PageRank [START_REF] Haveliwala | Efficient computation of pagerank[END_REF], [START_REF] Kamvar | Adaptive methods for the computation of pagerank[END_REF], [START_REF] Fujiwara | Efficient personalized pagerank with accuracy assurance[END_REF], [START_REF] Bahmani | Fast personalized pagerank on mapreduce[END_REF], [START_REF] Maehara | Computing personalized pagerank quickly by exploiting graph structures[END_REF], [START_REF] Avrachenkov | Monte carlo methods in pagerank computation: When one iteration is sufficient[END_REF], [START_REF] Andersen | Local graph partitioning using pagerank vectors[END_REF], [START_REF] Berkhin | Bookmark-coloring algorithm for personalized pagerank computing[END_REF]. However, in cases where the graph evolves over time, such stationary distribution drifts and needs to be updated. While the algorithms above allow to efficiently recompute a personalized PageRank vector, proceeding in this way becomes impractical for very large networks that constantly evolve, such as the web graph that has been reported to have 60 × 10 12 nodes and evolve at a rate of 600 × 10 3 new pages created every second [START_REF] Ohsaka | Efficient pagerank tracking in evolving networks[END_REF]. Additionally, several works [START_REF] Ipsen | Mathematical properties and analysis of google's pagerank[END_REF], [START_REF] Brezinski | The pagerank vector: properties, computation, approximation, and acceleration[END_REF], [START_REF] Pretto | A theoretical analysis of google's pagerank[END_REF] have studied the impact of graph perturbations to PageRank vectors, showing that (i) the magnitude of the change to a PageRank vector is upper bounded by the size of the perturbation (magnitude of the change to the graph transition matrix); and (ii) the PageRank vector mostly changes in the entries associated to nodes close to the perturbed area. This implies that if a perturbation is small, then it is wasteful to recompute the PageRank vector from scratch. A better alternative consists in only updating the scores of nodes close to the perturbation. In the literature, this challenge is commonly referred to as local PageRank updating. There are three reference methods. Firstly, [START_REF] Bahmani | Fast incremental and personalized pagerank[END_REF] proposes a Monte-Carlo approach where multiple random walkers are run to estimate the entries of the PageRank vector based on how frequently walkers visit nodes. Secondly, the work of [START_REF] Yoon | Fast and accurate random walk with restart on dynamic graphs with guarantees[END_REF] exploits the random walk with restart interpretation of personalized PageRank to show that the stationary distribution of this walk can be updated by running a local diffusion process in the affected area. Then, [START_REF] Yoon | Fast and accurate random walk with restart on dynamic graphs with guarantees[END_REF] runs this local process in a distributed fashion via the power method. Thirdly, the work of [START_REF] Ohsaka | Efficient pagerank tracking in evolving networks[END_REF] proposes a centralized updating algorithm based on the use of a residual and an approximation vector, sequentially pushing mass from the residual vector into the approximation vector using Gauss-Southwell update rules. While these works have been subject of deep theoretical studies [START_REF] Zhang | Approximate personalized pagerank on dynamic graphs[END_REF] and successfully applied in practice [START_REF] Yoon | Autonomous graph mining algorithm search with best speed/accuracy trade-off[END_REF], they still suffer from two main limitations: (i) they have slow convergence rates, particularly when trying to attain very small approximation errors; and (ii) they fully rely on the random walk interpretation of PageRank and thus cannot be used to update the novel generalizations of PageRank used in semisupervised learning [START_REF] Bautista | L γ -pagerank for semisupervised learning[END_REF], [START_REF] De Nigris | Fractional graph-based semi-supervised learning[END_REF], [START_REF] Mai | The counterintuitive mechanism of graphbased semi-supervised learning in the big data regime[END_REF], [START_REF] Zhou | Semi-supervised learning by higher order regularization[END_REF], [START_REF] Girault | Semi-supervised learning for graph to signal mapping: A graph signal wiener filter interpretation[END_REF] which rely on more complex dynamical processes.

C. Goals, Contributions and Outline

In this work, we address the two limitations listed above. We propose a novel local updating algorithm based on Chebyshev polynomials. These polynomials have already been used to efficiently approximate personalized PageRank vectors from scratch [START_REF] Ruiz | Laplacian Powers for Graph-Based Semi-Supervised Learning[END_REF], showing faster convergence than Gauss-Southwell and power iteration based methods (the building blocks of [START_REF] Ohsaka | Efficient pagerank tracking in evolving networks[END_REF] and [START_REF] Yoon | Fast and accurate random walk with restart on dynamic graphs with guarantees[END_REF], respectively). However, Chebyshev polynomials have not yet been considered in the updating setting because they lack the ability to set an initial guess, which all the updating algorithms described above rely upon. Thus, the core of our proposal relies on a novel updating equation that is tailored for the large family of PageRank methods mentioned above. Concretely, it allows us to (i) use a previous personalized PageRank vector as an initial guess in the Chebyshev context; (ii) cast the updating challenge as the task of running a local diffusion process that we efficiently compute via the Chebyshev polynomials; (iii) update any of the recent generalized formulations of PageRank [START_REF] Bautista | L γ -pagerank for semisupervised learning[END_REF], [START_REF] De Nigris | Fractional graph-based semi-supervised learning[END_REF], [START_REF] Mai | The counterintuitive mechanism of graphbased semi-supervised learning in the big data regime[END_REF], [START_REF] Zhou | Semi-supervised learning by higher order regularization[END_REF], [START_REF] Girault | Semi-supervised learning for graph to signal mapping: A graph signal wiener filter interpretation[END_REF] among which classical personalized PageRank arises as a special case.

The paper is organized as follows: Section II sets definitions and reviews local updating methods. Section III presents Chebyshev polynomials and introduces the proposed algorithm. Section IV numerically evaluates the algorithm. Section V concludes the work.

II. DEFINITIONS AND STATE-OF-THE-ART

A. Definitions

Let G(V, E, W ) be an undirected weighted graph where W refers to the adjacency matrix, E is the set of edges and V is the set of vertices. By D = diag(d 1 , ⋯, d N ) we denote the diagonal matrix of degrees, where

d i = ∑ j W ij .
The combinatorial Laplacian and the random walk transition matrices are denoted by L = D -W and P = D -1 W , respectively. We refer by u ∼ v that u is adjacent to v. Additionally, let pr α (y) denote the personalized PageRank vector of G with restarting probability α and initial condition y. Personalized PageRank is defined as the solution to the fixed point equation pr α (y) = (1 -α)y + αP T pr α (y).

(

) 1
Let G( Ṽ, Ẽ, W ) denote an undirected weighted graph which is an evolved or perturbed version of G. In analogy to G, the matrices D, L and P refer to the degree, Laplacian and random walk transition matrices of G, respectively. Additionally, we let pr α (y) be the personalized PageRank vector of G with restarting probability α and initial condition y. The updating challenge refers to the problem of estimating pr α (y) from pr α (y). To have consistent sized matrices, we model nodes joining/leaving the network as isolated nodes that get connected/disconnected. By definition, isolated nodes correspond to zero rows and columns in the graph matrices and their degree and inverse degree are zero.

B. State-of-the-art Approaches for Local PageRank Updating

In this section, we briefly review the state-of-the-art methods of [START_REF] Yoon | Fast and accurate random walk with restart on dynamic graphs with guarantees[END_REF] and [START_REF] Ohsaka | Efficient pagerank tracking in evolving networks[END_REF] for local PageRank updating. We focus on these two approaches because they are deterministic methods that can update a PageRank vector up to any desired accuracy, hence they directly compare to our proposed algorithm that we describe in Section III.

Random Walk with Restart (RWR) [START_REF] Yoon | Fast and accurate random walk with restart on dynamic graphs with guarantees[END_REF]. This work is rooted in the power iteration method, which guarantees that the recursive formula

p(t) = (1 -α)y + α P T p(t-1) (2)
converges to pr α (y) when t → ∞. The authors take benefit of the possibility to set an initial guess p(0) , also known as warm restart. They set p(0) = pr α (y). Since it is guaranteed that a PageRank vector does not substantially change under small perturbations, this warm restart sets the trajectory of the recursive equation ( 2) very close to the fixed point, which helps to drastically reduce the number of iterations needed to obtain a good approximation. Notice however that, even though this reduces the number of iterations, the initial guess p(0) is a dense vector (most entries are non-zero). Thus, computations are needed for all vertices in the graph albeit the update only occurs locally. The authors of [START_REF] Yoon | Fast and accurate random walk with restart on dynamic graphs with guarantees[END_REF] address this issue by showing that (2), under a warm restart, can be rewritten as:

pr α (y) = pr α (y) + 1 (1 -α) pr α (r), (3)
where r = α[ P T -P T ]pr α (y). Eq. ( 3) shows that updating an existing PageRank vector amounts to computing another PageRank vector with an initial seed r that is completely localized (only non-zero) in the 1-hop vicinity of the perturbed nodes. Clearly, pr α (r) can be computed by setting y = r and p(0) = r in (2), showing that running the recursion for a few iterations is essentially equivalent to locally diffusing r to the affected nodes and updating their values.

Push method [START_REF] Ohsaka | Efficient pagerank tracking in evolving networks[END_REF]. This work is rooted in the Gauss-Southwell recursive formula which uses two vectors to approximate pr α (y): an approximation vector p and a residual vector r coding the difference between pr α (y) and p. The method starts with an initial guess p(0) and then, at iteration t, transfers mass from r(t-1) into p(t) such that the following invariant is preserved

pr α (y) = p(t) + 1 1 -α pr α (r (t) ). (4)
Clearly, minimizing the entries of r imply that p converges to pr α (y). To attain this, if at iteration t the largest entry of r(t) corresponds to vertex u, then the state of the algorithm at iteration t + 1 is determined by the following set of update equations:

p(t+1) = p(t) + r(t) u δ u . (5)
r(t+1) = r(t) -r(t) u δ u + α P T r(t) u δ u . ( 6
)
This procedure is repeated until all entries from the residual diminish below some user-defined threshold. The authors of [START_REF] Ohsaka | Efficient pagerank tracking in evolving networks[END_REF] show that setting p(0) = pr α (y) and r(0) = α[ P T -P T ]pr α (y) preserve the invariant (4). While r(0) is similar to the residual of the RWR method, in the push method it is used differently: the locality of r(0) implies that only a few entries can surpass the tolerance threshold, meaning that only a few push operations are needed to drive them below the threshold again and obtain a good approximation of the evolved PageRank vector.

III. PROPOSED METHOD

Algorithm 1 [START_REF] Shuman | Chebyshev polynomial approximation for distributed signal processing[END_REF] Distributed application of a matrix function to a vector via Chebyshev polynomials Input at node u: λ max , y u , µ, R uv ∀ v ∼ u, K, and {c t ∶ t = 0, . . . , K}.

Output at node u:

f (K) u ( T0 (R)y) u = y u Transmit y u to all neighbours v ∼ u Receive y v from all neighbours v ∼ u ( T1 (R)y) u = ∑ v={v∼u}∪u 1 φ R uv y v -y u for t = 2 ∶ K do Transmit ( Tt-1 (R)y) u to all neighbours v ∼ u Receive ( Tt-1 (R)y) v from all neighbors v ∼ u ( Tt (R)y) u = ∑ v={v∼u}∪u 2 φ ( Tt-1 (R)y) v - 2( Tt-1 (R)y) u -( Tt-2 (R)y) v end for Return f (K) u = 1 2 c 0 y u + ∑ K t=1 c t ( Tt (R)y) u

A. PageRank Computation via Chebyshev Polynomials

In this subsection, we present the Chebyshev polynomials, which are a general technique to approximate matrix functions and form the basis of our algorithm derived in Section III-B. As discussed in the introduction, the two main drawbacks of current local PageRank updating algorithms are that (i) they are slow to converge; and (ii) they cannot address the novel generalizations of personalized PageRank that no longer rely on random walk processes. Notably, the Chebyshev polynomials carry the potential to address these limitations because (i) they can account for general operators, thus covering the recent generalization of PageRank in the literature; and (ii) they converge faster than methods based on power-iteration and Gauss-Southwell rules when computing PageRank vectors from scratch [START_REF] Ruiz | Laplacian Powers for Graph-Based Semi-Supervised Learning[END_REF].

In the context of signal processing on graphs, the Chebyshev polynomials were introduced in [START_REF] Shuman | Chebyshev polynomial approximation for distributed signal processing[END_REF] as a mean to approximate functions of a graph matrix, achieving considerable success in the contexts of graph signal filtering [START_REF] Cheng | Iterative chebyshev polynomial algorithm for signal denoising on graphs[END_REF], [START_REF] Tseng | Minimax design of graph filter using chebyshev polynomial approximation[END_REF], [START_REF] Tian | Chebyshev and conjugate gradient filters for graph image denoising[END_REF] and graph neural networks [START_REF] Defferrard | Convolutional neural networks on graphs with fast localized spectral filtering[END_REF], [START_REF] Yan | Spatial-temporal chebyshev graph neural network for traffic flow prediction in iot-based its[END_REF]. They operate as follows: let R denote a graph matrix and h(R) be a function of it. Then, [START_REF] Shuman | Chebyshev polynomial approximation for distributed signal processing[END_REF] shows that h(R) can be approximated by means of the truncated series:

h(R) ≈ 1 2 c 0 + K t=1 c t Tt (R), (7)
where

Tt (R) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ 1, t = 0 R-φ φ , t = 1 2 R-φ φ Tt-1 -Tt-2 , t ≥ 2 (8) φ = λ max 2, c t = 2 π ∫ π 0 cos(tθ)h(φ(cos(θ) + 1)
)dθ, and λ max is the spectral radius bound of R. Eq. ( 8) is known as the Chebyshev polynomial approximation of h(R). One of its assets is that it allows to approximate the result of multiplying h(R) with a vector y in a distributed fashion. To see this, let us recall that y can be interpreted as a signal that lives on the vertices of the graph encoded by R. Thus, if nodes are given communication and computation capabilities, each node can compute its own value of h(R)y by transmitting and receiving messages to and from their neighbors. This distributed algorithm is detailed in Algorithm 1. While [START_REF] Ruiz | Laplacian Powers for Graph-Based Semi-Supervised Learning[END_REF] shows that Chebyshev polynomials can converge to personalized PageRank vectors significantly faster than power iteration and Gauss-Southwell methods from scratch, they have not been considered in the updating setting because they do not offer the possibility to set an initial guess.

B. Local PageRank updating via Chebyshev polynomials

In this subsection, we detail our main contribution: a Chebyshev polynomial-based local updating algorithm tailored for a large family of PageRank methods. We start by noticing that standard personalized PageRank and the novel generalizations used in semi-supervised learning [START_REF] Bautista | L γ -pagerank for semisupervised learning[END_REF], [START_REF] De Nigris | Fractional graph-based semi-supervised learning[END_REF], [START_REF] Mai | The counterintuitive mechanism of graphbased semi-supervised learning in the big data regime[END_REF], [START_REF] Zhou | Semi-supervised learning by higher order regularization[END_REF], [START_REF] Girault | Semi-supervised learning for graph to signal mapping: A graph signal wiener filter interpretation[END_REF] can all be framed under one same formalism in terms of matrix functions. To show this, let us introduce the change of variable α = 1 µ+1 . It is easy to see that the PageRank fixed point equation ( 1) can be rewritten as the partial differential equation: LD -1 pr µ (y) + µpr µ (y) = µy, where LD -1 = (I -P T ) is the so-called random walk Laplacian. This expression implies that PageRank can alternatively be interpreted as the equilibrium state of a dynamical process driven by a discrete Helmholtz equation in which the dynamics are ruled by the operator LD -1 . Notably, several of the novel generalizations of personalized PageRank admit the same interpretation, allowing their solutions to be expressed in the following general form:

Rpr µ (y) + µpr µ (y) = µy, (9)
where R denotes a generalized reference operator associated to graph G. Thus, the only difference among several personalized PageRank generalizations is the choice of the operator R. In Table I, we list some of the possible choices of R and the methods associated to them.

Clearly, the advantage of Eq. ( 9) is that any algorithm that we derive based on it automatically covers a large family of PageRank methods. Therefore, the updating algorithm we propose in this work is an algorithm to update the solution of Eq. ( 9). To derive our updating algorithm, we start by noticing that the solution of Eq. ( 9), for an evolved graph G, can be expressed as a matrix function of R in the following way

pr µ (y) = µ( R + µI) -1 y. ( 10
)
While Eq. ( 10) can be leveraged to efficiently compute pr µ (y) from scratch (for instance via the Chebyshev polynomials), it is not useful in an updating scenario because it does not allow to set an initial guess. Therefore, our first goal is to derive a recursive equation that converges to [START_REF] Dostal | Exploration of document classification with linked data and pagerank[END_REF], which we can then use to set pr µ (y) as an initial guess. A natural way to proceed is by developing Eq. ( 10) in its geometric series. However, we stress that this approach results in a recursive expression p(t) =

Method

Std. PageRank [1]

L γ -PageRank [START_REF] Bautista | L γ -pagerank for semisupervised learning[END_REF] Iter. PageRank [START_REF] Zhou | Semi-supervised learning by higher order regularization[END_REF] Recentered kernel [START_REF] Mai | The counterintuitive mechanism of graphbased semi-supervised learning in the big data regime[END_REF] Time-graph dual [START_REF] Girault | Semi-supervised learning for graph to signal mapping: A graph signal wiener filter interpretation[END_REF] Anom. Diffusion

[22] R LD -1 L γ D -1 γ (LD -1 ) m -P W P , P = I -1 N 11 T D -σ LD σ-1 D -σ γ L γ D σ-1 γ TABLE I:
Possible choices of the reference operator R reported in the literature.

y+ 1 µ Rp (t-1) that only converges to pr µ (y) when µ > λ max . To obtain a recursive equation that converges for all µ > 0 (hence for all α ∈ (0, 1]), we perform the following transformations: (i) we normalize the spectrum (eigenvalues) of R to the range [-1, 1]; and (ii) we map the spectral domain of the matrix function h( R) = µ( R+µI) -1 to the range [-1, 1]. By applying transformation (i), we obtain the new operator:

S = (2 λ max ) R -I. ( 11
)
We refer to the diagonal matrices of eigenvalues of R and S by Λ and s, respectively. Then, by applying transformation (ii) we obtain a new matrix function now depending on s:

h(Λ) = µ Λ + µ (12) = µ (λ max 2)(s + 1) + µ (13) = 2µ λ max s + 1 + (2µ λ max ) = h(s), (14)
where, for the sake of clarity, we have expressed matrix inversion in the form of division. Now, if we develop the geometric series of h( S), we obtain the following recursive expression that converges for all µ > 0:

h( S) = 2µ 2µ + max ∞ t=0 - λ max 2µ + λ max t St (15)
Eq. ( 15) highlights our restriction to undirected graphs: if the spectrum is complex, then the recursion is not guaranteed to converge. We thus leave the extension of (15) to directed graphs as future work. Finally, by setting

ρ = 2µ 2µ + λ max , (16)
ψ = - λ max 2µ + λ max , (17)
and applying [START_REF] Zhang | A collaborative filtering tag recommendation system based on graph[END_REF] to y, we obtain the following recursive equation

p(t) = ρy + ψ S p(t-1) (18)
that converges to pr µ (y) as t → ∞. Clearly, Eq. ( 18) allows us to set p(0) = pr µ (y) and drive the trajectory of the recursion close to the fixed point, reducing the number of iterations towards convergence. However, Eq. ( 18) is not fully satisfactory. Firstly, using it to update a PageRank vector involves sending messages across the entire network due to the fact that p(0) = pr µ (y) is dense, even though the update mostly takes place in the perturbed graph region. Secondly, it follows power-iteration convergence speed, which is slow. To amend these issues, we extend the result of [START_REF] Yoon | Fast and accurate random walk with restart on dynamic graphs with guarantees[END_REF] in Eq. ( 3) to a large family of PageRank methods

Algorithm 2 Distributed local updating of general PageRank methods via Chebyshev polynomials

Input: µ, pr ρ,ψ (y), R, R and ρ, ψ, φ. Output: pr ρ,ψ (y). r = ψφ[ R -R]pr ρ,ψ (y) Compute pr ρ,ψ (r) via Algorithm 1 Return pr ρ,ψ (y) = pr ρ,ψ (y) + pr ρ,ψ (r) ρ by means of the following Lemma. For the sake of notation clarity, we refer to the convergent state of ( 18) by pr ρ,ψ (y) = p(∞) .

Lemma 1. Given a fixed set of coefficients ρ, ψ, and initial condition y, we have that pr ρ,ψ (y) = pr ρ,ψ (y) +

1 ρ pr ρ,ψ (r) (19)
where r = ψ S -S pr ρ,ψ (y)

Proof. We start with a warm restart in recursion [START_REF] Ipsen | Mathematical properties and analysis of google's pagerank[END_REF] as follows

p(1) = ρy + ψ S p(0) (21)
= ρy + ψ Spr ρ,ψ (y)

= pr ρ,ψ (y) -ψSpr ρ,ψ (y) + ψ Spr ρ,ψ (y)

= pr ρ,ψ (y) + ψ S -S pr ρ,ψ (y)

= pr ρ,ψ (y) + r

Then, for the second iteration we have

p(2) = ρy + ψ S p(1) (26)
= ρy + ψ S pr ρ,ψ (y) + r

= pr ρ,ψ (y) -ψSpr ρ,ψ (y) + ψ S pr ρ,ψ (y) + r

= pr ρ,ψ (y) + ψ S -S pr ρ,ψ (y) + ψ Sr (29)

= ρy + ψ Spr ρ,ψ (y) + ψ Sr (30)
= pr ρ,ψ (y) + ψr + ψ Sr [START_REF] Avrachenkov | Monte carlo methods in pagerank computation: When one iteration is sufficient[END_REF] By successive applications of this procedure, we have that

p(∞) = pr ρ,ψ (y) + ∞ t=0 ψ t St r (32)
= pr ρ,ψ (y) +

1 ρ pr ρ,ψ (r) (33)
Lemma 1 has several implications. Firstly, it states that updating a PageRank vector amounts to computing another PageRank vector with an initial distribution r that is completely localized (non-zero) in the 1-hop vicinity of the nodes that changed between G and G. Secondly, since computing pr ρ,ψ (r) involves diffusing r through the graph, then the locality of r implies that only a few messages are enough to make the information necessary for an update reach the affected nodes. Thirdly, it makes it obvious that it is not necessary to use the slow recursive equation ( 18) to perform the update. Instead, pr ρ,ψ (r) can be more efficiently computed by means of the Chebyshev polynomials. Therefore, our proposed algorithm consists in leveraging Eq. ( 19) and in approximating pr ρ,ψ (r) by means of Chebyshev polynomials. It is summarized in Algorithm 2.

IV. NUMERICAL EVALUATION

Goals. In this section, we evaluate the performance of the proposed algorithm 1 . In particular, our goals are: (i) to assess the performance gains obtained by the algorithm with respect to computing PageRank from scratch using the Chebyshev polynomials; (ii) to demonstrate that the proposed algorithm can be used to update both standard and generalized PageRank vectors; (iii) to assess how the performance of the algorithm degrades as perturbations grow in size; (iv) to compare the proposed algorithm with the state-of-the-art alternatives; and (v) to evaluate the performance of the algorithm in a tracking scenario where a PageRank vector needs to be updated during a long period of time.

Metrics. We assess performance in terms of the number of messages that need be exchanged in order to approximate the evolved PageRank vector within a specified relative error ( 2 -norm sense). We use the number of messages rather than the routine's running time because we consider this metric to better capture the complexity of a local and distributed algorithm.

Data. We perform our experiments in the Tech-AS-Topology temporal network [START_REF] Rossi | The network data repository with interactive graph analytics and visualization[END_REF], which is a real-world network from an autonomous system with 34.8K nodes and 171.4K edges organized in 32.8K graph snapshots. This network contains both sparse and dense regions, meaning that perturbations can affect small or large regions. For the experiments, we pre-process the data by turning the snapshots into undirected graphs, resulting in a total of 215.4K timestamped edges. The first graph snapshot in the sequence contains 32K nodes and 111.6K edges. Then, in successive snapshots, new edges adhere into the network branching nodes already present or new nodes joining the graph. The dataset only contains edge additions, therefore we simulate an edge deletion setting (see experiment 4) by reversing the time axis: we consider the originally last snapshot as the new first one and the originally first snapshot as the new last one. From this perspective, a new snapshot causes edges to disappear or nodes to leave.

A. Experiment 1

In our first experiment, we address goals (i) and (ii). For this, we fix a small graph perturbation. Then, as we vary the allowed number of messages, we measure how well Algorithm 2 approximates the true PageRank of the evolved graph. For comparison purposes, we apply the same test to a computation from scratch using Algorithm 1. To show that the proposed algorithm can update generalized PageRank propositions as well as standard PageRank, we employ it to update standard PageRank vectors and the recently proposed L γ -PageRank vectors from [START_REF] Bautista | L γ -pagerank for semisupervised learning[END_REF]. For this experiment, we use the first snapshot from the Tech-AS-Topology network as initial graph. Then, we use the second snapshot of the network as the perturbation: it contains 120 new edges and 1 new node joining the graph. We choose a vertex at random and use its indicator function as the initial distribution y (a common setting in local graph clustering). We use α = 0.5, measure relative error in the 2 sense, and repeat the experiment for 20 realizations of y.

Results of Experiment 1 are displayed in Figure 1. The left panel shows the result of updating standard PageRank, while the right panel depicts the result of updating the generalized L γ -PageRank [START_REF] Bautista | L γ -pagerank for semisupervised learning[END_REF]. They show that the proposed algorithm successfully updates both standard and generalized PageRank vectors. In both cases, the proposed algorithm offers significant approximation improvements compared to computing from scratch. We additionally verify that our updating algorithm converges at the same rate than the Chebyshev polynomials from scratch. This amends a tradeoff that needs to be made with current updating algorithms: they are a good option if only few iterations are allowed but their slow convergence makes them worse than Chebyshev polynomials from scratch if several iterations are needed [START_REF] Ruiz | Laplacian Powers for Graph-Based Semi-Supervised Learning[END_REF]. Lastly, we notice that the error bars (standard error) are negligible, indicating that the performance of the algorithm is irrespective of the choice of initial seed y and, consequently, of a particular PageRank vector to update.

B. Experiment 2

In our second experiment, we address goal (iii). For this, we fix a target approximation error. Then, as we vary the perturbation size, we measure the number of messages required by Algorithm 2 to approximate the true PageRank of the evolved graph within the specified error. For comparison purposes, we apply the same test to a computation from scratch using Algorithm 1. Since larger perturbations imply larger updates, our proposed algorithm should be highly sensitive to the size of perturbations. On the other hand, a computation from scratch should only augment messages proportionally to Ẽ -E . Therefore, we aim to empirically spot the point where the update needed is so large that our updating algorithm offers no benefit over a computation from scratch. For this experiment, we use the first snapshot from the Tech-AS-Topology network as initial graph. Then, we control the size of the perturbation by aggregating an increasingly larger number of subsequent snapshots. We set y as the indicator function of a random vertex and update its associated standard PageRank vector. We use α = 0.5 and set the error at 1 × 10 -13 .

Results of Experiment 2 are displayed in Figure 2. For small perturbations, the number of messages needed by our algorithm to attain the desired error is small. This number increases as the perturbation grows in size, reaching a point where the updating algorithm does not provide any advantage with respect to a computation from scratch. For the Tech-AS-Topology network, this operational limit occurs for a perturbation of around 4000 new edges, which corresponds to roughly 3% of the edges from the initial graph. This confirms that our updating algorithm should preferably be used when the changes in the graph are small.

C. Experiment 3

In our next third experiment, we address goal (iv). For this, we fix a graph perturbation. Then, as we vary the target approximation error, we measure the number of message exchanges our proposed Algorithm 2 and the state-of-theart alternatives [START_REF] Yoon | Fast and accurate random walk with restart on dynamic graphs with guarantees[END_REF], [START_REF] Ohsaka | Efficient pagerank tracking in evolving networks[END_REF] require to approximate the true PageRank of the evolved graph within the specified error. We stress that our algorithm and the RWR one [START_REF] Yoon | Fast and accurate random walk with restart on dynamic graphs with guarantees[END_REF] are distributed and can thus be assessed in terms of transmitted messages. Yet, the push algorithm [START_REF] Ohsaka | Efficient pagerank tracking in evolving networks[END_REF] is centralized and normally studied in terms of push operations rather than messages. We notice that the complexity of each push operation is dominated by a matrix-vector multiplication that can be interpreted as transmitted messages, thus we track this quantity for the Push method. For this experiment, we use the first snapshot from the Tech-AS-Topology network as initial graph. Then, we use the second snapshot of the network as the perturbation. We set y as the indicator function of a random vertex and update its associated standard PageRank vector. We use α = 0.5.

Results of Experiment 3 are displayed in Figure 3. The proposed algorithm outperforms state-of-the-art alternatives for local PageRank updating, being able to attain any desired relative approximation error with significantly less messages. Indeed, for approximation errors in the order of 10 -14 , which are the best approximations we can obtain using Python's float64 data types, the proposed Algorithm requires roughly 35% less messages than the second best method of RWR. We notice that the push algorithm is not competitive for very precise approximations, as the number of message operations it requires quickly becomes large.

D. Experiment 4

In our fourth experiment, we address goal (v). For this, we fix a number of communication rounds (K). Then, as new graph snapshots arrive, we estimate the PageRank vector of the current snapshot by updating the PageRank vector estimated for the previous snapshot using Algorithm 2. To demonstrate that our algorithm addresses equally edge additions and deletions, we run the experiment in both settings. Since the data only contains edge additions, we simulate deletions by reversing the time axis, meaning that we start from the evolved network and run backwards to the primitive one. For comparison purposes, we estimate the exact PageRank of the current snapshot via a computation from scratch using Algorithm 1 under the same number of communication rounds (K). We stress that this is an extremely challenging task for the updating algorithm because the vector to update is no longer the exact PageRank vector of the previous snapshot but an approximation of it, thus meaning that errors accumulate over time. Therefore, we aim to empirically spot if our method can maintain a PageRank vector for a long time or if it soon becomes worse than the approximation obtained by the method from scratch. For this experiment, we use the aggregated first 100 snapshots from the Tech-AS-Topology network as initial graph. Then, we track the standard PageRank vector during the following 1000 snapshots (reverse for edge removals). The only exact PageRank vector is given to the initial graph. We set y as the indicator function of a random vertex, K = 15 and α = 0.5.

Results of Experiment 4 are displayed in Figure 4. The upper panel shows the relative error between the tracked vectors and the true PageRank of each snapshot when edge additions are considered, while the bottom panel depicts the same quantities for the case of edge deletions. The size of the perturbation in each new snapshot is shown as additional information in both panels. In both cases, the proposed algorithm is able to effectively track the PageRank vector during the entire time horizon. For early times, the updating algorithm returns extremely precise approximations: up to five orders of magnitude improvement with respect to a computation from scratch with the same computational budget. Then, we notice that errors steadily accumulate. However, it is at a sufficiently slow rate that, during the 1000 snapshots, the tracked vector is at least two orders of magnitude closer to the exact PageRank than the alternative from scratch.

V. CONCLUSION

We proposed a Chebyshev polynomial-based distributed algorithm for local PageRank updating. We showed that the proposed algorithm has faster convergence than state-of-theart alternatives, bringing us closer to the goal of effortlessly maintaining PageRank vectors in real world networks. Additionally, the algorithm can be used to update more general formulations of PageRank. These improvements were possible due to a novel updating equation that encompasses a family of PageRank formulations and that makes it direct to employ Chebyshev polynomials to locally solve the updating challenge. Numerical evaluations showed that the proposed algorithm is an effective tool for tracking PageRank vectors for a long period of time when changes in the graph are small. An interesting prospective work would be to extend these results to undirected graphs that have non-real eigenvalues and to the case in which PageRank parameters also change over time.

Fig. 1 :

 1 Fig. 1: Experiment 1. Performance of proposed algorithm vs a computation from scratch. We assess approximation error as larger computational budgets are given to the algorithms. Left: updating standard PageRank. Right: updating a generalized PageRank.

Fig. 2 :

 2 Fig.2: Experiment 2. Sensitivity of proposed algorithm to perturbations. We assess the number of messages required to update within an error of 1 × 10 -13 as the number of added edges grows. The alternative from scratch (same conditions) is used as reference.

Fig. 3 :

 3 Fig. 3: Experiment 3. Comparison of proposed algorithm with state-of-the-art alternatives. We assess the number of messages required to update a PageRank vector within an increasingly smaller approximation error.

Fig. 4 :

 4 Fig. 4: Experiment 4. Performance of proposed algorithm in a tracking setting. We update a PageRank vector during a long period of time using K = 15 fixed communication rounds. We measure error with respect to the exact PageRank of each snapshot. The alternative from scratch (same conditions) is used as reference. Top: Edge arrival setting. Bottom: Edge removal setting.

Code available at https://github.com/estbautista/PageRank Updating Chebyshev Paper

VI. ACKNOWLEDGEMENTS

This work is funded in part by the ANR (French National Agency of Research) under the Limass (ANR-19-CE23-0010) and FiT LabCom grants. The authors would also like to thank P. Abry and P. Gonc ¸alves for helpful discussions.


Esteban Bautista

Matthieu Latapy

A logical approach for temporal and multiplex networks analysis

Concept Proposition in graphs Extension

Disconnected network

and γ ⊆ C are a cover of D if it is satisfied: No α c are β c and γ c No β c are α c and β c No γ c are α c and β c

Introduction

Many systems generate data as a set of triplets (a,b,c): they may represent that user a called b at time c or that customer a purchased product b in store c. These datasets are traditionally studied as networks with an extra dimension (time or layer), for which the fields of temporal and multiplex networks have extended graph theory to account for the new dimension [START_REF] Kivelä | Multilayer networks[END_REF]. However, such frameworks detach one variable from the others and allow to extend one same concept in many ways, making it hard to capture patterns across all dimensions and to identify the best definitions for a given dataset. This work overrides this vision and proposes a direct processing of the set of triplets. While [START_REF] Cerf | Closed patterns meet n-ary relations[END_REF] also approaches triplets directly, it focuses on specific patterns and applications. Our work shows that a more general analysis is possible by partitioning the data and building categorical propositions (CPs) that encode informative patterns. We show that several concepts from graph theory can be framed under this formalism and leverage such insights to extend the concepts to data triplets. Lastly, we propose an algorithm to list CPs satisfying specific constraints and apply it to a real world dataset.

Results

Analysis via propositions. We consider the most general case where all the triplet entries come from arbitrary sets A,B,C. We thus define a triplet space as S = {(a,b,c) a ∈ A,b ∈ B,c ∈ C} and a dataset as D ⊆ S. We also define the sub-dataset induced by α ⊆ A, β ⊆ B, γ ⊆ C as D (α,β ,γ) = {(a,b,c) ∈ D a ∈ α,b ∈ β ,c ∈ γ}. Our main observation is that given α ⊆ A, β ⊆ B, γ ⊆ C, we can partition D into eight disjoint regions (or bins) according to whether a triplet has its entries in α, β and γ. Then, we can capture how triplets in D distribute across these bins via CPs. This process is illustrated in the Fig 1-Left: the large square depicts the eight possible partition bins, while the smaller squares illustrate how the triplets (crosses) may distribute and CPs be constructed to capture the distribution pattern. In a nutshell, a CP asserts or denies that all or some of the members of one group (the subject) possess the attributes of another group (the predicate), using an expression of the form: 'Q S are P', where S refers to the subject, P to the predicate, and Q to a quantification word which can be 'All', 'Some', or 'No' [START_REF] Copi | Introduction to Logic[END_REF]. The expression 'All S are P' is a typical example. In our case, we form CPs using α, β , or γ as S and the other two as P, such that the following expression holds: 'Q (triplets with elements in) S are (in relation with at least one element from) P'. For simplicity, we omit the words in parenthesis. In Fig. 1-Left we notice that all the triplets with elements in α also have elements in β and γ, thus forming: 'All α are β and γ'. These are informative patterns: if α represents customers, β products and γ stores, then 'All α are β and γ' indicates that customers in α buy only products from β and only in stores from γ. It is thus of interest to list informative CPs. We notice that (i) universal quantifiers (All, No) are more informative than particular ones (Some), yet particular propositions may be close to a universal one; and (ii) propositions above do not express how dense are the relations between S and P. We therefore extend propositions to: x% S are y% P, where x is the fraction of triplets in S in relation to P and y is the density of relationships between S and P. This allows us to state the algorithmic challenge of listing all propositions satisfying constraints on x and y without needing to explore the full space. Relation to graph theory and extensions. Our formalism can also be used to study tuples (a,b). By setting A = B = V we address the particular case of graphs, where V is to the vertex set of graph G. Several concepts from graph theory may be re-formulated in terms of propositions satisfying specific constraints. An illustration is given in Fig. 1-Right. Going further, we use this re-formulation to generalize the concepts to data triplets. Our results are listed in Table 1. It can be seen that some patterns, like XOR predicates, may not be easily derived from pure graph extensions. Listing propositions. We propose Algorithm 1 to list propositions of type x ≥ x min % α are y ≥ y min % β and γ, where x min and y min are user-defined parameters. It uses the fact that disjoint subjects satisfying a predicate also satisfy it when merged. Thus, the algorithm searches valid predicates for singleton subjects and merges all those sharing predicates. We find predicates via a constructive approach where each triplet forms a region iteratively grown until the constraints are no longer satisfied. While this approach does not in general retrieve all propositions, it identifies a significant number of nontrivial patterns, and it may be improved in further work. Application to real-world data. We apply Algorithm 1 to a contact network in a hospital [START_REF] Vanhems | Estimating Potential Infection Transmission Routes in Hospital Wards Using Wearable Proximity Sensors[END_REF]. Sets A = B consist of 29 patients and 46 healthcare workers (27 nurses, 11 doctors, 8 admin), set C represents time (1890 minutes of data). We use time as subject set and x min = 0.7,y min = 0.5. The algorithm finds 1456 predicates from which it forms patterns like: (i) group of 7 minutes where 85% activity corresponds to 3 nurses and 1 admin interacting with 64% density; (ii) group of 3 minutes where 84% activity corresponds to 4 doctors interacting with 66% density; (iii) group of 7 minutes where 80% activity corresponds to 3 nurses interacting with 66% density. Clearly, the patterns found are representative of the typical activity in a hospital.

Dominating set

α ⊆ V is a dominating set of G if it is satisfied: Some ai are α, ∀ai ∈ α c α ⊆ A, β ⊆ B, and γ ⊆ C are dominating sets of D if it is satisfied: Some ai are β or γ, ∀ai ∈ α c Some bi are α or γ, ∀bi ∈ β c Some ci are α or β , ∀ci ∈ γ c Separating set α ⊆ V is a separating set of G if it is satisfied that: G (α c ) is disconnected α ⊆ A, β ⊆ B, and γ ⊆ C are separating sets of D if it is satisfied that: D (α c ,β c ,γ c ) is disconnected Vertex k-coloring A disjoint partitioning V = ⋃ k i=1 αi is a k-coloring of G if it is satisfied: No αi are αi, ∀i The disjoint partitionings A = ⋃ k i=1 αi, B = ⋃ k i=1 βi, C = ⋃ k i=1 γi are a k-coloring of D if it

Fig. 1 :

 1 Fig. 1: Left: Partition bins (big square) and distribution of D (crosses) into the bins with associated categorical propositions (small squares). Right: Framework applied to a graph composed of two clique components.

Table 1 :

 1 is satisfied: No αi are βi and γi, ∀i No βi are αi and γi, ∀i No γi are αi and βi, ∀i Clique α ⊆ V is a clique of G if it satisfies: Some α are 100% α α ⊆ A, β ⊆ B, and γ ⊆ C are a clique of D if they satisfy: Some α are 100% β and γ Re-formulation of graph concepts in terms of categorical propositions and extension to data triplets. It can be seen that graph concepts relying on partitioning V easily carry over to arbitrary data triplets. end procedure ( return propositionList ) 12: procedure GET PREDICATES(D (a i ,B,C) , xmin, ymin) 13: regionList = D (a i ,B,C) ▷ Each triplet (ai, b j , c k ) becomes a region (b j = β , c k = γ) These predicates satisfy x ≥ x min ai are y ≥ y min P

	Cluster	α ⊆ V is a cluster of G if it satisfies: Large x % α are α
	Algorithm 1
	1: procedure GET PROPOSITIONS(D, xmin, ymin)
	2:	predicateList = [ ]
	3:	propositionList = [ ]
	4:	for ai ∈ A do
	5:	predicateList.append ( get predicates( D (a i ,B,C) , xmin, ymin ) )
	6:	end for
	7:	for P ∈ predicateList do
	8:	S ← merge subjects( P, predicateList )	▷ Combine all subjects (ai) with predicate P
	9:	propositionList.append( (S, P) )
	10:	end for
	11: 14:	predicates = [ ]
	15:	while regionList do
	16:	grownRegionList ← grow regions( regionList )	▷ For each region, grow β or γ in dir. of max. density
	17:	regionList ← filter y( grownRegionList )	▷ Remove regions with density less than ymin
	18:	predicates.append( filter x( regionList ) )	▷ Store regions if at least xmin fraction of triplets fall within
	19:	end while
	20: end procedure ( return predicates )	▷

α ⊆ A, β ⊆ B, and γ ⊆ C are a cluster of D if they satisfy: Large x% α are β and γ Large x% β are α and γ Large x% γ are α and β

Acknowledgements. This work is funded in part by the ANR (French National Agency of Research) under the Limass (ANR-19-CE23-0010) and FiT LabCom grants.