Faster Local Solvers for Graph Diffusion Equations
Authors: Jiahe Bai
Baojian Zhou
Deqing Yang
Yanghua Xiao
Venue: NeurIPS 2024 poster (2024)
Keywords: Graph Diffusion Equation
Personalized PageRank
Heat Kernel
Katz
Local Solvers
Graph Neural Networks
Primary area: graph_neural_networks
TL;DR: We propose a general local iterative framework to accelerate the computation of graph diffusion equations which can be applied to GNN models.

Abstract: Efficient computation of graph diffusion equations (GDEs), such as Personalized PageRank, Katz centrality, and the Heat kernel, is crucial for clustering, training neural networks, and many other graph-related problems. Standard iterative methods require accessing the whole graph per iteration, making them time-consuming for large-scale graphs. While existing local solvers approximate diffusion vectors through heuristic local updates, they often operate sequentially and are typically designed for specific diffusion types, limiting their applicability. Given that diffusion vectors are highly localizable, as measured by the participation ratio, this paper introduces a novel framework for approximately solving GDEs using a local diffusion process. This framework reveals the suboptimality of existing local solvers. Furthermore, our approach effectively localizes standard iterative solvers by designing simple and provably sublinear time algorithms. These new local solvers are highly parallelizable, making them well-suited for implementation on GPUs. We demonstrate the effectiveness of our framework in quickly obtaining approximate diffusion vectors, achieving up to a hundred-fold speed improvement, and its applicability to large-scale dynamic graphs. Our framework could also facilitate more efficient local message-passing mechanisms for GNNs.

Faster Local Solvers for Graph Diffusion Equations
Jiahe Bai
Baojian Zhou 1,2+ Deqing Yang 1,2 Yanghua Xiao
the School of Data Science, Fudan University, Shanghai Key Laboratory of Data Science, School of Computer Science, Fudan University jhbai20, bjzhou, yangdeqing shawyh@fudan, edu cn
Abstract
Efficient computation of graph diffusion equations (GDEs), such as Personalized PageRank, Katz centrality, and the Heat kernel, is crucial for clustering, training neural networks, and many other graph-related problems. Standard iterative meth- ods require accessing the whole graph per iteration, making them time-consuming for large-scale graphs. While existing local solvers approximate diffusson vectors through heuristic local updates, they often operate sequentially and are typically designed for specific diffusion types, limiting their applicability. Given that dif- fusion vectors are highly localizable, as measured by the participation ratio, this paper introduces novel framework for approximately solving GDEs using a lo- cal diffusion process. This framework reveals the suboptimality of existing local solvers. Furthermore, our approach effectively localizes standard iterative solvers by designing simple and provably sublinear time algorithms. These new local solvers are highly parallelizable, making them well-suited for implementation on GPUs. We demonstrate the effectiveness of our framework in quickly obtaining approximate diffusion vectors, achieving up to hundred-fold speed improvement, and its applicability to large-scale dynamic graphs. Our framework could also facilitate more efficient local message-passing mechanisms for GNNs.
1 Introduction
Katz centrality (Katz) [46]. Heat kernel (HK) (1 and Inverse PageRank (IPR) (1). fundamental tools for modeling graph data. These score vectors for nodes in graph capture various aspects of their impor- tance or influence. They have been successfully applied many graph learning tasks including local clustering 22] [8 detecting communities [49], semi-supen semi-supervised learning [78] 80), node embeddings
Graph diffusion equations (GDEs), such as Personalized PageRank (PPR)
41
62
63 67]. training graph neural networks (GNNs) [TO 16 19
BT] 75), and many other applications Specifically, given a propagation matrix M associated with an undirected graph G(V, &),
32
general graph diffusion equation is defined
Ck M s,
where ff is the diffusion vector computed from source vector s, and the sequence of coefficients Ck
satisfies eą 0. Equation (1) represents system of linear, constant-coefficient ordinary differential
equation, (t) = (t))), with an initial condition a=(0) and /. 2 0. Standard solvers 34 (7) for computing require access matrix-vector product operations M.. typically involving O (m)
operations, where m is the total number of edges in G. This could be time-consuming when dealing
with large-scale graphs [42]
*Corresponding author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

A key property of f is the high localization of its entry magnitudes, which reside in a small portion of this localization property of f on PPR, Katz, and HK. Leveraging this local- ity property allows for more efficient approximation using local ieeativv solvers, which heuristically avoid (m) operations. Local push-based methods 2 7 49 or their variants 4 12] are known to be closely related to Gauss-Seidel 449 [8]. However, current local push-based methods are fundamentally sequential iterative solvers and focused on specific types such PPR HK. These disadvantages limit their applicability to modern GPU architectures and their generalizability.
G. Figure[J
6.00
Participation Ratio pi.)
am
By leveraging the locality of f. we propose, for the first time, general local iterative framework for solv- ing GDEs using a local diffusion process. novel component of our framework is to model local diffu- sion as a locally evolving set process inspired by its stochastic counterpart [58]. We use this framework to localize commonly used standard solvers, demon- strating faster local methods for approximating f. For example, the local gradient descent simple, prov- ably sublinear, and highly parallelizable. It can be accelerated further by using local momentum. Our contributions are
Katz
Graph Index Figure 1: The maximal participation ra- tio r(f)=(Eit= (n Ei= (fd(*) of exam- ple diffusion vectors f over 18 graphs, or- dered from small (cora) to large (oghn- papers100M), The ratio p(f) is normalized by the number of nodes n.
By demonstrating that popular diffusion vectors, such as PPR, Katz, and HK, have strong localiza- tion properties using the participation ratio, we propose a novel graph diffusion framework via local diffusion process for efficiently approximating GDEs. This framework effectively tracks most energy during diffusion while maintaining local computation.
To demonstrate the power of our proposed framework, we prove that APPR [2, a widely used local push-based algorithm, can be treated special case. We provide better diffusion-basel bounds Ô (vol (S))) 7))) where vol(S.) is lower bound of 1/c. This bound is effective for both PPR and Katz and is empirically smaller than O ((1/(ac)), previously well-known for APPR.
We design simple and fast local methods based on standard gradient descent for APPR and Katz, which admit runtime bounds of min (ain(vo((S))))) (a- 7 1/(ac)) for both cases. These methods are F-r--riindly, and we demonstrate that this iterative solution significantly faster on GPU architecture compared to APPR. When the propagation matrix M is symmetric, we show that this local method can be accelerated further using the local Chebyshev method for PPR and Katz.
Experimental results on GDE approximation of PPR, HK, and Katz demonstrate that these local solvers significantly accelerate their standard counterparts. We further show that they can be naturally adopted to approximate dynamic diffusion vectors. Our experiments indicate that these local methods for training are twice fast standard PPR-bes based GNNs. These results may suggest novel local message-passing approach to train commonly used GNNs.
All proofs, detailed experimental settings, and related works postponed the appendix. Our code is publicly available at https://giihubbco geggiiuub.com/Jaae
2 GDEs, Localization, and Existing Local Solvers
Table 1: Example GDEs with their corresponding propagation matrix M, coefficients Ck, and source s.
Notations. We consider undirected graph g(V,E) where V = (1,2.....n) the set of nodes, and E is the edge set with |E] m. The degree matrix is D diag(d,, .2...., dn), and A is the adja- cency matrix of G. The volume subset nodes S is vol(S) neighbors of node is denoted by (V)). The standard basis for node s is e,- The support of æ is defined supp(æ) = {u F. # 0}.
Equ.
M
PPR 162
AD
a(1
a*
E,
Katz [46]
A
E
HK [21]
AD
T /k!
Eves de. The set of
IPR [51)
AD -1
(04400007
Es
APPNP 30
D D-1AD-
a(1 0

---

Many graph learning tools can be represented as diffusion vectors. Table I presents examples widely used as graph learning tools. The coefficient O₁ usually exhibits exponential decay, so most of the energy of f is related to only the first few Ok- We revisit these GDEs and existing local solvers.
Personalized PageRank. Given the weight decaying strategy c* = a(1 ax and predefined damping factor a E (0, 1) with M AD- the analytic solution for PPR is
SPPR ar - (1-a)AD-))
These vectors can be used to find local graph cut or train GNNs g approximate PPR (APPR) method (2 locally updates the estimate-residual pair (æ, r) as follows
10 25 79 The well-known
APPR:
x: イ- x + OTT
Cu:
<- r --rrr, Tu C. + (1 a)r, AD e..
Here, each active node has a large residual Tu 2 eadd, with initial values æ t- and r + ae.. The runtime bound for reaching Ta < eady for all nodes leveraging the monotonicity property. Previous analyses [49 18) suggest that APPR is a localized version of the
traph-independent and is (1/((e)))
(GS) iteration and thus has fundamental sequential limitations.
Katz centrality. Given the weight c = a s+1 with a E (0, A|1)) and a different propagation matrix M A. The solution for Katz centrality can then be rewritten
fKatz aA-
The goal is to approximate the Katz centrality ((I aA) - ne. Similar to APPR, local solver [ for Katz centrality, denoted as AKatz, can be designed as follows
AKatz
x + Tu
rtr Tu + ar, Ae..
AKatz is coordinate descent method [ЛI. Under the nonnegativity assumption of (i.e., S
1/ /ddmax), convergence bound for the residual || |[a is provided.
Heat Kernel. The heat kernel (HK) (21) is useful for finding smaller but more precise local graph
cuts. uses different weight decaying C - -/kk! and the vector then defined as
fHK = exp (- (I M)}es e.:
where 7 is the temperature parameter of the HK equation and M AD-1 Unlike the previous two, this equation does not admit an analytic solution. Following the technique developed in [48 49] given initial vector s and temperature r, the HK vector can be approximated using the first N terms
of the Taylor polynomial approximation: define NN = Σ Ue with egp = e, and uk++1 M uss /k for & ...... N. It is known that [[ EN 1 S (/NN).. This is equivalent to solving the linear system (IN+1 @ I, N M) e = e, & e.. where @ denotes the Kronecker product. Then, the push- push-based method, namely AHK, has the following updates
AHK + v (e& & e.),
r (IN+1 @ I, - SN+1 @ M) (ex & eew)
There many other types of GDEs, such Inverse PageRank [51]. which generalize PPR. Many GNN propagation layers, such as SGC 69 and APPNP B0), can be formulated as GDEs. For all
these f, the participation ratio [54]] to measure its localization ability, defined as
pff)
1A IAAP) /
1=1
When the entries in f are uniformly distributed, such that f; O(Inn), then pff) O(). However, in the extremely sparse case where ff is a standard basis vector, p(f) = 1/n indicates the sparsity effect. Figure I illustrates the participation ratios, showing that almost all vectors have ratios below 0.01. Additionally, larger graphs tend to have smaller participation ratios.
APPR, Aatzz, and AHK all have fundamental limitations due to their reliance sequential Gauss- Seidel-style updates, which limit their parallelization ability. the following sections, we will develop faster local methods using the local diffusion framework for solving PPR and Katz.

---

3 Faster Solvers via Local Diffusion Process
We introduce a local diffusion process framework, which allows standard iterative solvers to be effectively localized. By incorporating this framework, we show that the computation of PPR and Katz defined in 2 and 33 can be locally approximated sequentially in parallel on GPUs.
3.1 Local diffusion process
To compute fPPR and fKATZ, it is equivalent to solving the linear systems, which can be written as
(4) where Q is a (symmetric) positive definite matrix with eigenvalues bounded by j and L. i.e., (QQ < L. For PPR, we solve (I (1-a)AD-1)
Qx 8,
ae,, which is equivalent to solving (I - a)D 1/2 AD-AD-122 1 1/2 aD aD-1/ For Katz, we compute (I aA)x es- The vector s is sparse, with supp(s) < n. We define local diffusion process, a locally evolving set procedure inspired by its stochastic counterpart (58) as follows
Definition 3.1 (Local diffusion process). Given an input graph G. a source distribution 8, precision tolerance e, and local iterative method A with parameter for solving (4). the local diffusion process defined process of updates ((x:1) r(()),))) (Se))osisz Specifically, it follows the dynamic system
(((1)) (((+),,,+++)))) S++1 = (0) ((), S. S,
0 OS1ST.
where o is a mapping via some iterative solver Ag. For all three diffusion processes (PPR, Katz, and HK), set Su = {s). We say this process converges when S, 0 if there exists such T; the generated sequence of active nodes are St. The total number of operations of the local solver As is
T-1
TAo Σ
vol(S,) = T -vooS))
t=)
where we denote the average of active volume as vol(S = T ET= vol(S.).
Intuitively, we can treat this local diffusion process as random walk on a Markov Chain defined on the space of all subsets of V, where the transition probability represents the operation cost. More efficient local solvers try to find a shorter random walk from Sy to Sy. The following two subsections demonstrate the power of this process in designing local methods for PPR and Katz.
3.2 Sequential local updates via Successive Overrelaxation (SOR)
Given the estimate (²) at f-th iteration, we define residual (+) s Qa (1) and Q be the matrix induced by A and D. The typical local Gauss-Seidel with Successive Overrelaxation has the following online estimate-residual updates (See Section 11.2 of [34]): at each time = 0, .,....77 T-1, for each active node S. {ui, .2..... Mis, } with 1.2,..., |St). we update each u,-th entry of and corresponding residual r as the following
LocalSOR 2 (++f.+1) x (t++.) + a(t+e.) (++4+41) (t++:) Qeai-QQ@tttttt a(t+t.)
(6)
where - (i 1) S), is the current time, and update unit vector is eup Yu e /u
((++,) ((+t)
Note that each update of (6) is (dd,,). If S, V. it reduces to the standard GS- [34]. Therefore. APPR is special case of (6). local variant of GS-SOR with procedure. APPR updates æ at some entries and keeps track of large magnitudes of per iteration, while LocalSOR allows for better choice of w; hence, the total number of operations reduced. We establish the following fundamental property of LocalSOR.
Figure 2 illustrates this
Theorem 3.2 (Properties of local diffusion process via LocalSOR). Lei Q A 1-11-0 3P where P Z Onxn and Pue + 0 if (u, v) E E; 0 otherwise. Define maximal value Pmax = maxxEv P
Assume that (0) 2 0 is nonnegative and Pmaz. B are such that (3 Pmax < 1, given the updates of
(6, then the local diffusion process of (x(t) (p))) SS; S, G, Ag (LocalSOR, w)) with w (0, 1)
has the following properties
1. Nonnegativity. (t+ei) 2 for all and t, (i- 1)/(So) with i
... 1Sc).

---

So = (0)
Si (1,12)
S2 20, 13,
S3 (1,
S4 20, 18)
Sa (14)
So (0)
6, [0, 12) 8, 2,, 14)
Sg {6, 13]
$4 [4, 12)
Figure 2: The first row illustrates the local diffusion process of APPR over a toy network topology adopted from [4]]. It uses TAPPR 6 local iterations with TAPPR 42 operations and additive error 2 0.29241. The second row shows the process of LocalSOR (w = 1.19 ~ w*). uses local iterations with TLocaISOR
28 operations and additive error 0.21479. LocalSOR uses fewer local iterations, costs less total active volume, and obtains better approximate solutions. We choose the source node 0 with 0.02 and 0.25.
LoocaSOR
2. Monotonicity property.
||^(0)]| ... 1| 2 ||
If the local diffusion process converges (i.e., ST 0), then T is bounded by
(r(0)) 11
1
|s (e++-)))
Tu:
T
WT (1 3P max)
where Tr
T
Yt
(1( l|
t=
Based on Theorem 3.2 we establish the following sublinear time bounds of LocalSOR for PPR.
Theorem 3.3 (Sublinear runtime bound of LocalSOR for PPR). Let IT = su)p(r(T)) Given an undirected graph and a target source node with (0, 1), = and provided 0 < 1/dg. the run time of LocalSOR in Equ. (6) for solving (I (1 a AD " ) = ae, with the stop condition D 11-1((1))) 1100 S are and initials x:
and (U) ae, is bounded as the following
1 (ST CPPR
where vol(ST)
TLocsSOR S min
In
OTT
FT
where Crrn = 1/((1- a)(rr) The estimate (()) satisfies | (x - frrR) S.
The above theorem demonstrates the usefulness of our frame- work. It shows a new evolving bound where vol(S)) /r S L/e as long Q satisfying certain assumption (It true for PPR and Katz). Similarly, applying Theorem 3.2 following result for approximating fkau--
Opeatione (E (o0S))
Loca SOR
we have the
Corollary 3.4 (Runtime bound of LocalSOR for Katz). Let I-= = (r and CKotz = 1/((1 a)[Ir]). Given an undirected graph G and target source node with e 1/ 3 1, and provided O < c 1/dg. the run time of LocalSOR in Equ. (6) solving (I (I-aA) e, with the e, bounded the following
Figure 3: Parameter tuning of w.
stop condition | |D-1,(T) S and initials x and
1
(OT(
1 In CKazz where vol(ST)
TLocalSOR I min
(8)
e(1 admaxx) (1 ad Fi
TT
E
The estimate fkam: = x (T) e, satisfies I| fkarll2 S [1(I aA)--DDl
Accerlation when Q is Stieltjes matrix (w² 2/(1 11 (a 11-))) is well-known that when W E 2), GS-SOR has acceleration ability when Q Stieltjes. However, it is fundamentally
5

---

difficult to prove the runtime bound as the monotonicity property no longer holds. It has been conjectured that a runtime of (()((a)e) can be achieved [27]. Incorporating our bound, new conjecture could be O (ool(SS/((/Tr))) If Q is Stieltjes, then with the proper choice of w, one can achieve speedup convergence ((vol(Sr) ((Vo))))) We leave it as an open problem.
3.3 Parallelizable local updates via GD and Chebyshev
The fundamental limitation of LocalSOR is its reliance on essentially sequential online updates, which may be challenging utilize with GPU-type computing resources. Interestingly, we developed a local iterative method that is embarrassingly simpler, highly parallelizable, and provably sublinear for approximating PPR and Katz. First, one can reformulate the equation of PPR and Katz as
x = arg min f(x) A 20 Qu 8 ST
A natural idea for solving the above is to use standard GD. Hence, following a similar idea of local updates, we simultaneously update solutions for St. We propose the following local GD.
LocalGD:
(t) x: (t+1) (x) + rss.
(1+1) = -p( Qrrs.
(10)
Theorem 3.5 (Properties of local diffusion process via LocalGD). Let Q I 1-3P where P P> Onxn and Pue + 0 if (u, v) E E; otherwise. Define maximal value Pmax = maxs,gv Prs. l1r//lls, 111- Assume that (0) = 8 2 O and Pmaxo 3 are such that 33 < 1, given the updates of (10), then the local diffusion process of (St,z(()) x!()) r(0); 9, Ao (LocalGI), ,t, I.)) has the following properties
1. Nonnegativity. (() 2 for all 2 O.
2. Monotonicity property. (|r 2 ... 11r(0111 2 ||r(t111111
the local diffusion process converges (i.e., ST 0), then T is bounded by
1
(r 1 where FT
T-1
T
7r - 3Pmaax) maxx
T
Indeed, the above local updates have properties that are quite similar to those of SOR. Based on Theorem (355] we establish the sublinear runtime bounds of LocalGD for solving PPR and Katz.
Corollary 3.6 (Convergence of LocalGD for PPR and Katz). Let Ir = supp (r (T)) and C (I-a][r]- Use LocalGD to approximate PPR Katz by using iterative procedure (TO). Denote Trrr
and Karz as the total number of operations needed by using LocalGD, they can then be bounded by
1
vol(ST) In C) }
vol(ST)
TPpR S min
S
(11)
Ouppr . OXPRR -T
"T
for stop condition |D-1,(00) "xppr For solving KATZ, then the toal runtime is bounded by
Traz S min
{ (11 O'Kaiz (emax)e (1 O'Katz dunxx) TT
vol(Sr)
In
C
vol(Sr)
1
(12)
FTT
for a stop condition
(t)) S edg. The estimate of equality the same as that of LocalSOR.
Remark 3.7. Note that LocalGD quite different from iterative hard thresholding methods 43] where the time complexity of the thresholding operator is (n)) at best, hence not a sublinear algorithm.
Accerlerated local Chevbyshev. One can extend the Chebyshev method 39 an optimal iterative solver for (9) Following (24). Chebyshev polynomials T, are defined via following recursions
TT(x:) = 2r (I) T (ar), for k 2 2, with (1) (()
(13)
For the PPR equation, (I AD 1 x ae,, we can symmetrize this linear system by rewriting
(1 - D 1/2 e.. The solution is then recovered by /2 (t))

---

Given 51
L-- L+u
21 = 20 L+N
2 f (zo), the standard Chevyshev method is defined as
46x
vs (x + (1-20% 2d L +
3% = 24
-- (ax-2 Tk x
L
2 TT òk-1
where μ S (QQ) S L. For example, for approximating PPR, we propose the following local updates
LocalCH: π (1+1) = (1) + 26.41
T-o D1/2r (t) + d ( - π (t,-1))s. 0 = T 6c) -4)
(1/2,((44)) (1 ( (++1) 1)_ ()) + (1 - a1) AD (T((++) (2).
The sublinear runtime analysis for LocalCH is complicated since it does not follow the monotonicity property during the updates. Whether admits, an accelerated rate remains an open problem.
Applications to Dynamic GDEs and GNN Propagation
Our accelerated local solvers ready for many applications. We demonstrate here that they can be incorporated to approximate dynamic GDEs and GNN propagation. We consider the discrete- time dynamic graph (47 which contains sequence of snapshots of the underlying graphs, i.e., Go. .1....,.yy The transition from G--1 to G, consists of a list of events O₂ involving edge deletions
or insertions. The graph Gt is then represented as: Gu Ot G1 On, G2 On Gr-1 On, Gr. The goal is to caleulate an approximate fi for the PPR linear system Qift ae, at time t. That is,
(I-(1-a)A,); =es
ae..
(14)
The key advantage of updating the above equation (presented in Algorithm 3 is that the APPR algorithm is used as a primary component for updating, making it much cheaper than computing from scratch. Consequently, we apply our local solver LocalSOR to the above equation, and we found that it significantly sped up dynamic GDE calculations and dynamic PPR-based GNN training.
Experiments
Datasets. We conduct experiments on 18 graphs ranging from small-scale (cora) to large-scale (P0)ers100M), mainly collected from Stanford SNAP [45] and OGB [42] (see details in Table B}. We focus on the following tasks: 1) approximating diffusion vectors with fixed stop conditions using both CPU and GPU implementations; 2) approximating dynamic PPR using local methods and training dynamic GNN models based on InstantGNN models (75] F
Baselines and Experimental Setups. We consider four methods with their localized counter- parts: Gauss-Seidel (GS)/LocalGGS) Successive Overrelaxation (SOR)/LocalSORK Gradient De- scent (GD)/LocaIGD, and Chebyshev (CH)/LocalCH* Specifically, we use the stop condition [D-1,00) 0c I ca for PPR and | S c for Katz, while we follow the parameter settings the optimal parameter w' suggested in Section 3.2 We randomly sample 50 nodes uniformly from lower to higher-degree nodes for all experiments. All results averaged over these 50 nodes. We conduct experiments using Python 10 with CuPy and Numba on server with 80 cores, 256GB of memory, and two 28GB NVIDIA-4090 GPUs.
used in 49 for HK. For LocalSOR,
5.1 Results on efficiency of local GDE solvers
Local solvers are faster and use fewer operations. We first investigate the efficiency of the proposed
local solvers for computing PPR and Katz centrality. We set (APpr = 0.1, 1/n) for PPR and (OrKatz A/(1|A||2 e),e= 1/m) for Katz. We use temperature of 10 and 1/vn n for HK. All algorithms for HK estimate the number of iterations by considering the truncated error of Taylor approximation. Table presents the speedup ratio of four local methods over their standard counterparts. For five graph datasets, the speedup is more than 100 times in terms of the number of operations in most cases. This strongly demonstrates the efficiency of these local solvers. Figure
e Moor detailed experimental setups and additional results are in the appendix.
NNtt that the approximate local solvers of APPR, AHK, and AKatz will be referred to GS.
7

---

presents all such results. Key observations are: 1) All local methods significantly speed up their global counterparts on all datasets. This strongly indicates that when is within certain range. local solvers for GDEs are much cheaper than their global counterparts. 2) Among all local methods, LocalGS and LocalGD have the best overall performance. This may seem counterintuitive since LocalSOR and LocalCH are more efficient in convergence rate. However, the number of iterations needed for 1/n or = 1/m much smaller. Hence, their improvements are less significant.
Table 2: Speedup ratio of computing PPR vectors. Let TA and Locald be the number of operations of the standard algorithm A and the local solver LocalA, respectively. The speedup ratio TA/ Localal
Graph
SOR/LocalSOR
GS/LocalGS
GD/LocalGD
CH/LocalCH
Citeseer
86.21
114.89
157.41
5.86
ogbn-arxiv
183.43
392.26
528.03
101.88
ogbn-products
667.39
765.97
904.21
417.41
wiki-talk
169.67
172.95
336.53
30,45
ogbn-papers 100M
100M
243.68
809.47
1137.41
131.30
60B
Locatiin
Local:
LocaGD
LeaaCH
S3R
SDR
LocaSDR
65
# of Operations (C vol(5))
Operations DC vol(s.)
of Operations (C volss)))
Graph Index
Graph
PPR(a 0.1,6=
Katz
HK( 10, Vn
Figure 4: Number of operations required for four representative methods and their localized counter-
parts over 18 graphs. The graph index is sorted according to the performance of LocalGS.
Which local GDE solvers are the best un- der what settings? the lower precision set- ting, previous results suggest that LocalSOR and LocalGD perform best overall. To test the proposed LocalSOR efficiency, we use the ogbn-arxiv dataset to evaluate the local algo- rithm efficiency under a high precision setting. Figure SouueeJillusee illlsttrates the performance of Local- SOR and LocalGS for PPR and Katz. As becomes smaller, the speedup of LocalSOR over LocalGS becomes more significant.
of Oocuten OZ m
Com dase
PPR
Katz
Figure 5: The number of operations function of e for comparing LocalSOR and LocaIGS.
Huree (ne
Ratts
Speda aoe
PPR
PPR
Katz
HK
Figure 6: Running time (seconds) as function of e for HK, Katz, and PPR GDEs on the wiki-ralk dataset. We use OPpR = 0.1, Q'gaz = 1/(1|/]/2 + 1). and THK = 10 with 50 sampled source nodes.
When do local GDE solvers (not) work? The next critical question is when standard solvers can be effectively localized, meaning under which e conditions we see speedup over standard solvers. We conduct experiments to determine when local GDE solvers show speedup over their global counterparts for approximating Katz, HK, and PPR on the wiki-talk graph dataset for different values, ranging from lower precision (2-17) to high precision (2-32) As illustrated in Figure 6

---

when e is in the lower range. local methods are much more efficient than the standard counterparts. As expected, the speedup decreases and becomes worse than the standard counterparts when high precision is needed. This indicates the broad applicability of our framework; the required precisions many real-world graph applications are within a range where our framework is effective.
5.2 Local GDE solvers on GPU-architecture
We conducted experiments the efficiency of the GPU implementation of LocalGD and GD, specifically using LocalGD's GPU implementation to compare with other methods. presents the running time of global and local solvers function of the wiki-talk dataset. LocalGD is the fastest among wide range of This indicates that, when a GPU is available and within the effective range, LocalGD (GPU) can be much faster than standard GD (GPU) and other methods based on CPUs. We observed similar patterns for computing Katz in Figure II
Localdl
Bunnng Time (0)
4221/GP1
LoGESOO:
50B
GINGRU
Ciiocee
Figure 7: Comparison of running time (seconds) for CPU and GPU implementations.
5.3 Dynamic PPR approximating and training GNN models
IntenGGNiiuca5000
(S Traning (esoreChiooocaCS) lifeerce
bot 50R) Inferene
Raning Time C1)
Accuracy (3)
70
69
68
67
(nstamtGNN(LccaCG))
Snapshot
Figure 8: InstantGNN model using local iterative solver (LocalSOR) do propagation.
To test the applicability of the proposed local solvers, we ap- ply LocalSOR GNN propagation and test its efficiency ogbn-arxiv and ogbn- gebn-products. We use the InstantGNN (75) model (essentially APPNP [30), following the experimental settings in (75). Specifically, we set a = 0.1, 10-2 /n, and w w the optimal value for cases. For oghn- arxiv, we randomly partition the graph into 16 snapshots (each snapshot with 59.375 edges), where the initial graph Go contains 17.9% of the edges. With similar performance on testing accuracy, as illustrated in Figure 8 the Instant- GNN model with LocalSOR (Algo. 7 has significantly shorter training time than its local propagation counterpart (Algo. (). Figure 9 presents the accumulated operations over these 16 snapshots. The faster local solver is LocalSOR (Dynamic), which dynamically updates (x. r) for (14) according to Algo. A and Algo. 3 whereas LocalSOR (Static) updates all approximate PPR vectors from scratch at the start of each snapshot for (T4). We observed a similar pattern for LocalCH, where the number of operations is significantly reduced compared to static ones.
LambiOtt)yyonicc
Accomdaedd
Snapshot
Figure 9: Acculmulated total number of operations of local solvers the
ogbn-arxiv dataset.

---

Limitations and Conclusion
When is sufficiently small, the speedup is insignificant, and is unknown whether more efficient local solvers can be designed under this setting. Although we observed acceleration in practice, the accelerated bounds for LocalSOR and LocalCH have not been proven. Another limitation of local solvers is that they inherit the limitations of their standard counterparts. This paper mainly develops local solvers for PPR and Katz, and it remains interesting to consider other types GDEs.
We propose the local diffusion process, local iterative algorithm framework based on the locally evolving process. Our framework is powerful in capturing existing local iterative solvers such as APPR for GDEs. We then demonstrate that standard iterative solvers can be effectively localized, achieving sublinear runtime complexity when monotonicity properties hold in these local solvers. Extensive experiments show that local solvers consistently speed up standard solvers by hundredfold.
We also show that these local solvers could help build faster GNN models 31 expect many GNN models to benefit from these local solvers using local message passing strategy. which we are actively investigating. Several open problems are worth exploring, such whether these empirically accelerated local solvers admit accelerated sublinear runtime bounds without the monotonicity assumption.
I3
14 20
We
10

---

Acknowledgments and Disclosure of Funding
The authors would like to thank the anonymous reviewers for their helpful comments. The work of Baojian Zhou is sponsored by Shanghai Pujiang Program (No. 22PJ1401300) and the National Natural Science Foundation of China (No. KRH2305047). The work of Deqing Yang is supported by Chinese NSF Major Research Plan No.92270121. The computations in this research were performed using the CFFF platform Fudan University.
References
[1] Reid Andersen, Christian Borgs, Jennifer Chayes. John Hopcraft, Vahab S Mirrokni, and Shang- Hua Teng. Local computation of PageRank contributions. In Algorithms and Models for the Web-Graph: 5th International Workshop, WAW 2007, San Diego, CA, USA, December 11-12, 2007. Proceedings 5, pages 150-165. Springer, 2007.
[2] Reid Andersen, Fan Chung, and Kevin Lang. Local graph partitioning using PageRank vectors. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 066), pages 475-486. IEEE, 2006.
[3] Konstantin Avrachenkov, Paulo Gonçalves, and Marina Sokol. On the choice of kernel and labelled data in semi-supervised learning methods. In Algorithms and Models for the Web Graph: 10th International Workshop, WAW 2013, Cambridge, MA, USA, December 14-15, 2013, Proceedings 10, pages 56-67. Springer, 2013.
[4] Konstantin Avrachenkov, Nelly Litvak, Danil Nemirovsky, and Natalia Osipova. Monte carlo methods in PageRank computation: When one iteration is sufficient. SIAM Journal on Numerical Analysis, 45(2):890-900 2007.
[5] Siddhartha Banerjee and Peter Lofgren. Fast bidirectional probability estimation in markov models, Advances in Neural Information Processing Systems, 28, 2015.
[6] Michele Benzi and Paola Boito. Matrix functions in network analysis. GAMM- MAMMM-Miteillugen, 222000220000 2020.
[7] Pavel Berkhin. Bookmark-coloring algorithm for personalized PageRank computing. Internet Mathematics, 3(1):41-62, 2006.
[8] Aleksandar Bojchevski, Johannes Gasteiger, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberezki, Michal Lukasik, and Stephan Günnemann. Scaling graph neural networks with approximate PageRank. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2473, 2020.
[9] Aleksandar Bojchevski and Stephan Günnemann. Deep Gaussian embedding of graphs: Unsu- pervised inductive learning via ranking, arXiv preprint arXiv:1707.03815, 2017.
[10] Aleksandar Bojchevski, Johannes Klicpera, Bryan Perozzi, Martin Blais, Amol Kapoor, Michal Lukasik, and Stephan Günnemann. Is PageRank all you need for scalable graph neural networks. In ACM KDD, MLG Workshop, 2019.
[11] Francesco Bonchi, Pooya Esfandiar, David Gleich, Chen Greif, and Laks VS Lakshmanan. Fast matrix computations for pairwise and columnwise commute times and Katz scores. Internet Mathematics, 8(1-2):73-112, 2012.
[12] Christian Borgs, Michael Brautbar, Jennifer Chayes, and Shang-Hup Teng. A sublinear time algorithm for PageRank computations. In International Workshop on Algorithms and Models for the Web-Graph, pages 41-53. Springer, 2012.
[13] Ben Chamberlain, James Rowbottom, Maria I Gorinova, Michael Bronstein, Stefan Webb, and Emanuele Rossi. Grand: Graph neural diffusion. In International Conference on Machine Learning, pages 1407-1418. PMLR, 2021.

---

[14] Benjamin Chamberlain, James Rowbottom, Davide Eynard, Francesco Di Giovanni, Xiaowen Dong, and Michael Bronstein. Beltrami flow and neural diffusion on graphs. Advances in Neural Information Processing Systems, 34:1594-16000 2021.
[15] Deli Chen, Yankai Lin, Guangxiang Zhao, Xuancheng Ren, Peng Li, Jie Zhou, and Xu Sun. Topology-imbalane learning for semi-supervised node classification, Advances in Neural Information Processing Systems, 34:29885-298977 2021.
[16] Ming Chen, Zhewei Wei, Bolin Ding, Yaliang Li, Ye Yuan, Xiaoyong Du and Ji- Ji-Rong Wen. Scalable graph neural networks via bidirectional propagation. Advances in neural information processing systems, 33:1 14556-1456666 2020.
[17] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International conference on machine learning, pages 1725-1735. PMLR, 2020.
(18) Zhen Chen, Xingzhi Guo, Baojian Zhou, Deqing Yang, and Steven Skiena. Accelerating per- sonalized PageRank vector computation. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 262-273, 2023.
[19] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized PageRank graph neural network. In International Conference on Learning Representations (ICLR), 2021.
[20] Jeongwhan Choi, Seoyoung Hong, Noseong Park, and Sung-Bae Cho. GREAD: Graph neural pnactionddiffsiio networks. In International Conference on Machine Learning, pages 5722- 5747. PMLR, 2023.
[21] Fan Chung. The heat kernel as the PageRank of graph. Proceedings of the National Academy of Sciences, 104(5)):17355199444 2007.
[22] Timothy BP Clark and Adrian Del Maestro. Moments of the inverse participation ratio for the laplacian on finite regular graphs. Journal of Physics A: Mathematical and Theoretical, 4144):495003, 2018
[23] Haoran Deng, Yang Yang. Jiahe Li, Haoyang Cai, Shiliang Pu, and Weihao Jiang. Accelerating dynamic network embedding with billions of parameter updates to milliseconds. In Proceedings of the 29th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pages 414 425. 2023.
[24] Alexandre d' Aspremont, Damien Scieur, Adrien Taylor, et al. Acceleration methods. Founda- tions and Trends@ in Optimization, 5(1-2):1-245, 2021.
[25] Alessandro Epasto, Vahab Mirrokni, Bryan Perozzi, Anton Tsitsulin, and Peilin Zhong, Differ- entially private graph learning via sensitivity-boundee personalized PageRank. Advances in Neural Information Processing Systems, 35:22617-22627,, 2022.
[26] Illés Farkas, Imre Derényi, Albert-Lászlo Barabási, and Tamas Viesek. Spectra of "roal-world" graphs: Beyond the semicircle law. Physical Review E, 64(2):026704, 2001.
[27] Kimon Fountoulakis and Shenghao Yang. Open problem: Running time complexity of acceler- ated é ri-reuularized pagerank. In Conference on Learning Theory, pages 5630-5632. PMLR, 2022.
[28] Dongqi Fu. Zhigang Hua, Yan Xie, Jin Fang, Si Zhang, Kaan Sancak, Hao Wu, Andrey Malevich, Jingrui He, and Long. VCR- -CR-graphormer: mini-batch graph transformer via virtual connections. In The Twelfth International Conference on Learning Representations, 2024.
[29] Dongqi Fu, Dawei Zhou, and Jingrui He. Local motif clustering time-evolving graphs. In Proceedings of the 26th ACM SIGKDD International conference on knowledge discovery & data mining, pages 390-400. 2020.
12

---

[30] Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized PageRank. International Conference on Learning Representations (ICI.R), 2019.
[31] Johannes Gasteiger, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning, Advances in neural information prucessing systems, 32, 2019.
[32] David F Gleich. PageRank beyond the web. siam REVIEW, (7(3):331333)33 2015.
[33] David F Gleich, Kyle Kloster, and Huda Nassar. Localization in seeded PageRank. arXiv preprint Stt1:1509000006 2015.
[34] Gene H Golub and Charles F Van Loan. Matrix computations. JHU press, 2013.
[35] Thomas Guhr, Axel Müilerr-roellng, and Hans A Weidenmüllerr. Random-matte theories in quantum physics: common concepts. Physics Reports, 299(4-6):1894422 425, 1998.
[36] Wentian Guo, Yuchen Li, Mo Sha, and Kian-Lee Tan. Parallel personalized PageRank on dynamic graphs. Proceedings of the VLDB Endowment, 11(1):93-106 2017.
[37] Xingzhi Guo, Baojian Zhou, and Steven Skiena. Subset node representation learning over large dynamic graphs. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 516-526, 2021.
[38] Xingzhi Guo, Baojian Zhou, and Steven Skiena. Subset node anomaly tracking over large dynamic graphs. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 475 475-485, 2022.
[39] Martin H Gutknecht and Stefan Röllin. The chebyshev iteration revisited. Parallel Computing. 28(2):263 2002.
[40] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances neural information processing systems, 30, 2017.
[41] Taher H Haveliwala. Topic-sensitive PageRank. Proceedings of the 11th international conference on World Wide Web, pages 517-526, 2002.
[42] Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. Ogb- Isc: A large-scale challenge for machine learning on graphs. arXiv preprint arXiv:2103.09430, 2021.
[43] Prateek Jain, Ambuj Tewari, and Purushottam Kar. On iterative hard thresholding methods for high-dimensional m-estimation. Advances in neural information processing systems, 27, 2014.
[44] Glen Jeh and Jennifer Widom. Scaling personalized web search. In Proceedings of the 12th international conference World Wide Web, pages 271-279, 2003.
[45] Leskovec Jure. Snap datasets: Stanford large network dataset collection. Retrieved December 2021 from http://snap. stanford. edu/data, 2014.
[46] Leo Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1):39-43, 1953.
[47] Seyed Mehran Kazemi, Rishab Goel, Kshitij Jain, Ivan Kobyzev, Akshay Sethi, Peter Forsyth. and Pascal Poupart. Representation learning for dynamic graphs: a survey. The Journal of Machine Learning Research, 21(1):2648-2720) 2020.
[48] Kyle Kloster and David F Gleich. nearly-sublinear method for approximating column of the matrix exponential for matrices from large, sparse networks. In Algorithms and Models for the Web Graph: 10th International Workshop, WAW 2013, Cambridge, MA, USA, December 14-15, 2013, Proceedings 10, pages 68-79. Springer, 2013.
[49] Kyle Kloster and David F Gleich. Heat kernel based community detection. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1386-1395, 2014.
13

---

[50] Isabel M Kloumann, Johan Ugander, and Jon Kleinberg. Block models and personalized PageRank. Proceedings of the National Academy of Sciences, 114(1):33-38, 2017.
[51] Pan Li, Chien, and Olgica Milenkovic. Optimizing generalized pagerank methods for seed- expansion community detection. Advances in Neural Information Processing Systems, 32, 2019.
[52] Yiming Li, Yanyan Shen, Lei Chen, and Mingxuan Yuan. Zebra:
When temporal graph neural networks meet temporal personalized PageRank. Proceedings of the VLDB Endowment, 16(6):1332-1345, 2023.
[53] Peter Lofgren, Siddhartha Banerjee, and Ashish Goel. Bidirectional PageRank estimation: From average-case to worst-case. In Algorithms and Models for the Web Graph: 12th International Workshop, WAW 2015, Eindhoven, The Netherlands, December 10-11, 2015, Proceedings 12, pages 164-176. Springer, 2015.
[54] Travis Martin, Xiao Zhang, and Mark EJ Newman. Localization and centrality in networks. Physical review E, 90(5):052808, 2014.
[55] Frank McSherry. A uniform approach to accelerated PageRank computation. In Proceedings of the 14th international conference on World Wide Web, pages 575-582, 2005.
[56] Dingheng Mo and Siqiang Luo. Agenda: Robust personalized PageRanks evolving graphs.
In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 1315-1324, 2021.
[57] Cleve Moler and Charles Van Loan. Nineteen dubious ways to compute the exponential of matrix, twenty- five years later. SIAM review, 45(1):3-49 2003.
(58) Ben Morris and Yuval Peres. Evolving sets and mixing. In Proceedings of the Thirty-Fitth Annual ACM Symposium on Theory of Computing (STOC), page 279-286, New York, NY, USA, 2003. Association for Computing Machinery.
[59] Huda Nassar, Kyle Kloster, and David F Gleich. Strong localization in personalized PageRank vectors. In Algorithmss and Models for the Web Graph: 12th International Workshop. WAW 2015, Eindhoven, The Netherlands, December 10-11, 2015, Proceedings 12, pages 190-202. Springer, 2015.
[60] Huda Nassar, Kyle Kloster, and David F Gleich. Localization in seeded PageRank. Internet Mathematics, 2017.
[61] Lorenzo Orecchia, Sushant Sachdeva, and Nisheeth K Vishnoi. Approximating the exponential, the lanczos method and an o(m))time spectral algorithm for balanced separator. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1141-1160, 2012.
[62] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The PageRank Citation Ranking: Bringing Order to the Web. Technical report, Stanford Digital Library Technologies Project, 1998.
[63] Ştefan Postăvaru, Anton Tsitsulin, Filipe Miguel Gonçalves de Almeida, Yingtao Tian, Silvio Lattanzi, and Bryan Perozzi. Instantembedding: Efficient local node representations. arXiv preprint arXiv:2010.06999, 2020.
[64] Purnamrita Sarkar, Andrew W Moore, and Amit Prakash. Fast incremental proximity search in large graphs. In Proceedings of the 25th international conference on Machine learning, pages 896-903, 2008.
[65] Ingo Scholtes. When is a network network? multi-order graphical model selection in pathways and temporal networks. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1037-1046, 2017.
[66] Jieming Shi, Renchi Yang. Tianyuan Jin, Xiaokui Xiao, and Yin Yang. Realtime top-k personal- ized PageRank over large graphs on gpus. Proceedings of the VLDB Endowment, 13(1):15-28, 2019.
14

---

[67] Anton Tsitsulin, Marina Munkhoeva, Davide Mottin, Panagiotis Karras, Ivan Oseledets, and Emmanuel Müller. FREDE: anytime graph embeddings. Proceedings of the VLDB Endowment, 14(6): 102-1110, 2021.
[68] Hanzhi Wang, Mingguo He, Zhewei Wei, Sibo Wang, Ye Yuan, Xiaoyong Du, and Ji-Rong Wen. Approximate graph propagation. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 1686-1696, 2021.
[69] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference on machine learning, pages 6661-6871. PMLR, 2019.
[70] Hao Wu, Junhao Gan, Zhewei Wei, and Rui Zhang. Unifying the global and local approaches: an efficient power iteration with forward push. In Proceedings of the 2021 International Conference on Management of Data, pages 1996-2008 2021.
[71] Hao Yin, Austin Benson, Jure Leskovee, and David F Gleich. Local higher-order graph clustering. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pages 555-564, 2017.
[72] Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Andrey Malevich, Rajgopal Kannan, Viktor Prasanna, Long Jin, and Ren Chen. Decoupling the depth and scope of graph neural networks. Advances in Neural Information Processing Systems, 34:19665-19679 2021.
[73] Hongyang Zhang, Peter Lofgren, and Ashish Goel. Approximate personalized PageRank on dynamic graphs. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1315-1324, 2016.
[74] Jialin Zhao, Yuxiao Dong, Ming Ding, Evgeny Kharlamov, and Jie Tang. Adaptive diffusiion in graph neural networks. Advances neural information processing systems, 34:23321-23333, 2021.
[75] Yanping Zheng. Hanzhi Wang, Zhewei Wei, Jiajun Liu, and Sibo Wang. Instant graph neural networks for dynamic graphs. In Proceedings of the 28th ACM SIGKDD conference on knowledge discovery and data mining, pages 2605-2615, 2022.
[76] Baojian Zhou, Yifan Sun, and Reza Babanezhad Harikandeh. Fast online node labeling for very large graphs. In International Conference on Machine Learning, pages 42658-42697. PMLR, 2023.
[77] Baojian Zhou, Yifan Sun, Reza Babanezhad Harikandeh, Xingzhi Guo, Deqing Yang. and Yanghua Xiao. Iterative methods via locally evolving set process. arXiv preprint arXiv:2400.15020, 2024.
[78] Dengyong Zhou, Olivier Bousquet, Thomas Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency. Advances in neural information processing systems, 16, 2003,
[79] Qi Zhu, Natalia Ponomareva, Jiawei Han, and Bryan Perozzi, Shift-robust GNNs: Overcoming the limitations of localized graph training data. Advances in Neural Information Processing Systems, 01.27965--7977 2021.
[80] Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. Semi-supervised learning using Gaussian fields and harmonic functions. In Proceedings of the 20th International conference on Machine learning (ICML-03), pages 912-919, 2003.
[81] Zeyuan Allen Zhu, Silvio Lattanzi, and Vahab Mirrokni. A local algorithm for finding well- connected clusters. In International Conference on Machine Learning, pages 396 404. PMIR, 2013.
15

---

A Related Work
Disclaimer: The local diffusion process introduced in this paper shares a similar conceptual founda- tion with our concurrent work [77]. where we propose the locally evolving set process. However, these two approaches address distinct problems. In this work, our focus on investigating a different class of equations and exploring whether the local diffusion process can accelerate the training of Graph Neural Networks (GNNs)..
Graph diffusion equations (GDEs) and localization. Graph diffusion vectors can either be exactly represented as linear system be approximations of underlying linear system. The general form defined in Equation (T) has appeared in various literature [49] 51 (see more examples in 68 or
be found in the survey works of (2] The locality and localization properties of the diffusion vector f. including the PPR vector, have been explored in [64, 59
33 66]] Inspired by methods
for measuring the dynamic localization of quantum chaos [35 22 which also used for analyzing
graph eigenfunctions [1] 26 54). we use the inverse participation ratio to measure the localization ability of f. However, there is a lack of local framework for solving GDEs efficiently.
Standard solvers for GDEs. The computation of a graph diffusion equation approximates the exponential of propagation matrix, either through an inherently Neumann series as analytic system of linear equations. Well-established iterative methods, such as those approximating via the Neumann series Padé approximations, exist (see more details in the surveys [57 6 61 and (4) )
Each iteration requires computing the matrix-vector dot product, requiring (m)) operations for all the above methods. This is the computation aim to avoid.
Local methods for GDEs. The most well-known local solver for solving PPR was initially proposed in [2] for local clustering. PPR, fundamental tool for graph learning, has been applied to many core problems, including graph neural networks 8 17 69 15). graph diffusion S1 74, and its generalizations [5] [9] for GNNs clustering [50
Many variants have been proposed for solving such equations different forms using local methods that couple local methods with Monte Carlo sampling strategies, achieving sublinear time 53.. The work of [55] attempts to accelerate PPR computation via the Gauss-Southwal method, but does not work well in practice [48]. A notable finding from 77 is that the local computation of PPR is equivalent power iteration when the precision high. There are also works on temporal PPR vector computation [66] 36 [6 [22] and
our work can be immediately applied to these. Some local variants of APPR have been proposed for
Katz and HK [1] [4]] However, these local solvers are sequential and lack the ability to be easily implemented GPUs. Our local framework addresses this challenge.
PPR on dynamic graphs. Ranking on dynamic graphs has many applications [65], including motif clustering [71 (29), embedding large-scale graphs [63] 23 37 38 18), and designing graph neural networks [75] [72). The local computation via forward push (a.k.. APPR algorithm (2)
reverse push (a.k.a. reverse APPR (1] is widely used in GNN propagation and bidirectional Our framework helps to design more efficient dynamic GNNs.
propagation algorithms [66 28
B
Missing Proofs
B.1 Notations
We list all notations used in our proofs here.
eu: The indicator vector where the u-th entry is and 0 otherwise.
N(u): Set of neighbors of node u.
d,: The degree of node u.
G(V, E): The underlying graph with the set of nodes V and set of edges E.
A: Adjacency matrix of G.
D: Degree matrix of G when 9 is undirected.
II: Personalized PPR matrix, defined as II aa=aaa--aa (1-
appR: Damping factor oppRR (0, 1) for the PPR equation.
OKazz: Parameter OrKazz E (0. 1) for the Katz equation.
16

---

e: The enror tolerance.
D rlloo S oppre:: The stop condition for local solvers of PPR.
| S E: The stop condition for local solvers of Katz.
B.2 Formulation of PPR and Katz
In this section, restate all theorems and present all missing proofs. We first restate the two target linear systems we aim to solve, as introduced in Section 3 Recall PPR is defined as (I (1 aPpR) 1) fPPR appR It can be equivalently written
PPR:
Qx 8, Q
(1 OPpR ) D 1/2 AD 1/2 a oppp 1/2
(15)
where oppr E (0, 1) and x" aQ D eie Hence, SPPR D D1/2"". The Katz centrality be written as
Katz:
Qx =
OKKaz A ess
(16)
where O'Katz 10|1/||4||2) Then fkau xx C.. -es-
Proposition B.1 (3 53)). Ler G(V.E) E) be an undirected graph and and v be two vertices in V. Denote f. == a(I AD e, as the PPR vector of a source node s. Then
du fulu] = dy fulul.
Proof. We directly follow the proof strategy in [53] for completeness. For path P = {s, U1, ....... Uk. t in G, denote its length as ((P) (here E(P) h 1), and define its verse path to be P {t, Uk...., 12 V1,s) note that ((P) = (P). Moreover, we know that and thus, duy
random walk starting from traverses path P with probability P[P]
is easy to see that we have
P[P]- d, = P[P] de.
Now let Pss st. denote the paths in G starting at and terminating Then, can re-write fa((] as:
fall
Σ a(1 aa))))(P)p())
PEP
Σ a(1 a) de P[P] PEP.
d,
de de PEPa
Σ a(1 a(l-a)
de se(s),
d,
Algo 1 APPR (G. 6, 8)
adopted from g
1: x <- 0, r +- 0e,
2: while 3m, ru 2 ead,, do
3: r,æ t- PUSH(u,,,æ))
Return w
1: PUSH(U, r, w)::
2: Fu
Ia f- Iu + Tu
4: Tu + 0
5: for E (u) do
6: + + fl-a)f..
d.
7: Return (r, .z)
We adopt the typical implementation of APPR as presented in Algo.
We will arbitrarily write aryR and OrKaz when the context is clear.
17

---

B.3 Missing proofs of LocalSOR
(Properties of local diffusion process via LocalSOR). Lel Q - I 11--8 3P where P Owx and uu o Of v) E E; 0 otherwise. Define maximal value P maxx maxuEv || Assume that pl)) 0 is nonnegative and Pmax, 3 are such that max given the updates of (6. then the local diffusion process of & (=(()))(()) 8, A, = (LocalSOR, w)) with w E (0, has the following properties
Theorem 3.2
p(0)
1. Nonnegativity. r(t+ti) 2 for all t 2 0 and t; = (i 11/////l with = 1,2,...,,
... 2. Monotonicity property. ||r|0)]1 0 ||](((t+)))] (...((((tt))] 2 ||r(0+66+1)]1
the local diffusion process converges (i.e., ST 0), then T is bounded by
||-000/1 |r(2
T-1
|s. (e+t)
T T wT - B 3mpax)
In
where 7T
A
1i=1
T
|r(
t=
Proof. At each step and 1; = (i (i- 1)/11/ Sc] where = -..2...., |8:1 recall LocalSOR for solving Qu has the following updates
(1+4) Cue
((++.)
((ttuu)) =x (++t()) + ru;
r (++te+)) = ((+t))))
w Tuu
Q Cu--
Jusu
quau
Since we define as Q BP, where Pau for all E V, and using Jusu 1, we continue to have the updates of r as follows
(+++))
T 1) (1+t2)) w Tuu
Qee,
quru
(c+t.)
rus (++t,) e., + (wBr(tt))) Pe..
By using induction, show the nonnegativity of (())) First of all, (0)) 2 0 by our assumption. Let us assume (f++))) 2 O, then the above equation gives ((tttir)) 2 0 since S and P >> 0nxr by our assumption. Since we assume w I and P 2 Onxu: the above equation can be written as (e+t.) ((tt)1)) + w .Tu, Cu. ((++)) wwrr (1++2s) Peu. By taking
on both sides, have [ I|1 + wr = [|r((tt)))]] + wBr (t+t.) Pe..
To make an effective reduction, should be such that B Pe,, ll1 i = 1,2...... |S,| of the above equation, we then have the following
for all u, V. Summing over
Se (++e) aa
(1 3 (i)Peelll))
(1(t2))
||100]
||((0/1
$ -1-W
w/i (1 3Pmax)) ||,(
(17)
94 (1+*)) re 1- and (1 3 3Pmax < (1 -3P,)) for all us E S. The
Note that we defined To inequality of [17 leads the following bound
T-1
| 11 < II (1 who (1 - BPmaxx)) (0)
0=0
To further simply the above upper bound, since each term why (1 3 Pmax)) > 0 during the updates, it follows that why (1 Pmax)) E (0,1), 1). If there exists such that Sz = 0. then we can obtain upper bound of as
T
<
In - wiy (1 3Pmaa))
||
0=
T-1
Σ
why (1 - 3Pmax),
0
18

---

which leads to
In ||n(0] 112
T wTr(1 - PB ||r(T)
Theorem 3.3
(Sublinear runtime bound of LocalSOR for PPR). Let IT = supp(r(T)) Given an undirected graph G and a larget source node with E (0, 10,1), = and provided 0 < S 1/d.. the run time of LocalSOR in Equ. for solving (I - (1 a AD fPPPR = ae, with the stop QE and initials x0)) and (0) aes bounded as the following
condition || ( S
1
vol(ST)
CPrR
where vol(ST)
1
TLoclSOR < minn
In
(18)
EC
oTT
FT
where CPPR = a(\11a))Irl) The estimate x(T satisfies
|D (x:(T)
frrK)l Sc.
Proof. Recall St {ui, u2,.... 1 s.) be the set of active nodes processed in iteration. For convenience, we denote |St| = k. By LocalSOR defined in (6) for solving
II (1 AD ") fPPR ae.
We have the following online iteration updates for each active node u, E S (recall qu.u. 1).
(1++) = x (1+ (++
(1+)
+
Tuu
eui for = I,..., k and E S₁,
(1++) (1+ rw;
(2+ x+1)
Eu, w (1 a) ru;
AD-
(++ (1+'x))
Note for each active node ui, we have Tu:
2 eard. The total operations for LocSOR is
LocalSOR
vol(S:)
du.
((-(1)))
ca
||
(++
1
(++
2
w
|
||
wea?
||
wea?
eax
where the equality follows from w and [1)(() = a. Next, we focus on the proof of our
newly derived bound ((vol()))((a7T)) To check the upper bound of T, from Theorem 3.2 by noticing 3 = (1 - ax) and Pmax 1, this leads to the following
T
3 )
||>(0)
l11
In
a7T
19

---

Next, we try to give lower bound of r()) Note that after the last iteration T, for each nonzero residual (7) + O, u Zr, there is at least one possible update that happened node u: 1) Node has a neighbor E [N(,), which was active. This neighbor pushed some residual (1 a)ro. dv. where the time t' T. Hence, for all u E Ir, we have
|||
Σ
(T)
NEIr
(1
a)r
di
uEIn
(1
a)cad
dv
NEIT
Σ (1 a)Ea MEIr
2 aee( a [TT|
where the first equality due to the nonnegativity of guaranteeing by Theorem 3.2 and the second inequality is due to the fact that ra was active residuals before the push operation. Applying the above lower bound of (1) we obtain
|
|r:00)/ //1
ac
[T)
1
e(1- a Irl
CPPR
where OPPR = 1 and Ir = su)p(r(T)) Combine the above inequality and the upper bound T, we obtain our new local diffusion-based bounds. The rest is to show a lower bound of l/e. By using the active node condition, for u, E St, we have
S&
aE aov)((S)) S
((+4)
T-1 |Sd
aE
vol(S;)
5
Tus
(++4)
(19)
t=
1=0 1=1
We continue to have
(Sr)
Σ T-1
vol (S.)
1=0
FT
T-
1=0 Y
> 1=0 vol (S.)
T-1 E rws
(ctt:)
|
>T T-1 vol (S.)
a T St ((t1)
2im1 ru.
where the first inequality follows from the fact that E. (40) [r(9]]
[r[O]] 1i=11 Pe;
Pu;
for t
0. 1. due to the monotonicity property of ||r(() 112 The last inequality is from 19
Combining these, we finish the proof the sublinear runtime bound. The rest is to prove the estimation quality. Note ||>_)(()) S are directly implies || D (ar(( fPPR)lloo S e by using
Proposition B.I and the corresponding stop condition.
20

---

Remark B.2. The above theorem shares the proof strategy we provided in [77] Here, we use slightly different formulation of the linear system.
Corollary 3.4 (Runtime bound of LocalSOR for Katz). Let IT supp(r(2)) and CKatz - 1/((1 ZrI) Given an undirected graph 9 and target source node with a E (0, (0,1/dmax), provided O < e 1/d the run time of LocalSOR in Equ. for solving (I aA)x e, with the
1, and
stop condition
[D-rp(1) llo I
and initials x0)) and p. Es is bounded as the following
CKatz voT( In
where vol(ST)
TEocoSORR S min
(20)
c11 oddmax) )' (1 (--mmax))) TT
FT
The estimate fRom: (T) e, satisfies || |kka fkamll2 S I1(I aA)
Proof. The linear system (I - o.A)xr = s using LocalSOR updates can be written as x (1tt,-21) (1+h))
(++1.)
wru:
Eug
augu (t++))
ll4e, At) ((++e)) wry,
eu; + wr(l++)) aA Cas
Gazu:
Tu:us
where qu.u, 1. The updates of (t++e) can be simplified as the following
((++r++A)) = p((++))) wr!t eu, + wrrl+++)
(t+tt))
(1++(t+))))) Aeu.
The proof of nonnegativity of (t) follows the similar induction as in previous theorem by noticing the spectral radius of is [A(A)] < dmax- Hence, we have
S
|s,1
((+1) = -
(1+b) eu: + a A
((+b)
Move the negative term to left and take &, norm on both sides, we have
S.
[sel
(++++) = ||r(0/11 - (1+11)) + ww
(t++.) add. m
3
U2
|s (1+1)) أ-
16el (1++.) 1 ru:
addus ||2(1
ru:
||((t|] 1/
w(1 admax)
Diml rai
Σ |ccl (x++)))
||
(1](1)
It leads to the following
SS.
(t+t,)
(+++:) ad., (1 (1+
1=1
i=1
Since each ra,
(+++)
2 eduu, vol(S,) S >
| (++1i)
/e, we continue have
==
18c|
[&
(1++))
ad
(l+tc) (1 adde))
i=1
[S
(1+bi)
(1 addmax)
uz
1=
Finally, the above inequality gives the following upper runtime bound
[|r(()] ||
(++ [
vol(S,)
t=0 we(1
addaax)
[|~[0)]
| ||r ||
we(1 - axdmaax
1
we(1 -xdmax)
21

---

By letting 3 = and P = A with Piax= = dmax. we apply Theorem 3.2
to obtain the local
diffusion-basee bound
|
- (1 w(1 max ||
T
||
w(1 admaax B&) [|
(=0
T
(1 w(1 admax)
k=0
Using the similar technique provided in the previous case, and letting we can have
vol(ST)
CKatz
TRatz To check the estimate equality, we have
In
(1 ard
(() C, -aA)x
(1- -I- (T) (II - aA) - 1) es + te, -e,-r (T)
fknn te - (T)
Let fkaz :- x(3) This leads to
fkk
fkazzl2
= |1(I - DD DDD-1,(111 1/2
S |1(I aA) - | | 11:0
||(I aA) DDD|licc.
B.4 Missing proofs of LocalGD
Theorem 3.5 (Properties of local diffusion process via LocalGD), Les Q I --3P P 0 Onxn and Puo # if (u, v) E &; otherwise. Define maximal value P max = maxs, Prs, 1/ll////ss Il Assume that (0) s 2 and P Pmazz are such that 3Pmax 1, given the updates of {10,, then the local diffusion process of d (1), r:); G, Ag = (LocalGD, μ1, L)) has the following properties
1. Nonnegativity. (t) 0 for all 2 0.
... 2. Monotonicity property. ||r|0)||| ....//r1 ||r(1111 (|r(t)2)|11
the local diffusion process converges (i.e., ST 0), then T is bounded by
1
(r) |r(T)|ll'
T-1
T
In
where J T
Tr
3P max
1=0
Proof. each step I, recall LocalGD for solving Qx = (1 3P) s has the following updates
(1+1) = (t) T.
((++) = (1) Qr
Since Q = I B,, we continue to have the updates of r as the following
r ((+1) = (1) (I 3P) P)rss
(() rs. + 3P (t) (t)
(t)
By using induction, we show the nonnegativity of (1), First of all, (0) > 0 by our assumption. Let
us assume y(()) 2 0. Then, the above equation gives y (1+1)) since 3 0 and 2 Onxn by our assumption. The above equation can be written
(++1)
+ +rS.
(1) (() + P (t)
22

---

Taking ||
||| on both sides, we have
| ( 1n + Il lla = || + B|| PrS. 111
To make effective reduction, / should be such that [|| Pr. (1) |I we then have the following
||rs. (1)
for all S; S V. For this,
Irrs 11
311 Pr (0)
|r
||
||<(()) ||2
S 7t
m)])))) ||
(21)
where note we defined to T, it leads to the following bound
lh ml
and assumed Pr's. 000 S P lr Apply 21 from t = 0
|| S
II t=0
(1 71 (1 - 3Pmaa)) ||r 111
Note each of the term 1 - - (1 3Paa)) check the upper bound of we have
2 0 during the updates, then Te (1 3P Pmaxx) E (0, 1). To
|| 111 |r(0)]|
T
1
In 7/ (1 - 3Pmax))
0=
T-1
Te (1 PPmax)
1=0
which leads to
T <
7r 3P
[T(1)
Corollary 3.6
(Convergence of LocalGD for PPR and Katz). Let IT supp(r (T)) and C
[I-a:)rll Use LocalGD to approximate PPR or Katz by using iterative procedure (10). Denote TPPR and T Tan the total number of operations needed by using LocalGD, they can then be bounded by
1
vol(ST) In Cl J
vol(ST) S
TPPR S min
(22)
(ppPR e OPPR "I
E
for stop condition
|| 1n(000
11o0 CoppR For solving KATZ, then the toal runtime is bounded by
1
vol(Sr)
C2
vol(Sr)
1
Tkatz
< min
In
(23)
(1 OKKare dmax)ee" (1 OcKote dmmx) Frr
FT
for a stop condition |D S edgy The estimate equality is the same as of LocalSOR.
Proof. We first show graph-indepenie bound O(1((ac)) for PPR computation. Since (1+1)
(() Qr!!)) then rearrange it
(1+1)
T. + +1- (1-
(8)
Note that entries in (t) are nonnegative. It leads to
|| (++))|) + ||r (0) = (1 + (111-a))D +
To simplify the proof, here represents 1
23

---

where note [|(1 ( AD-1r 111 (1 -x) (1)
s. I11. then we have
|rs || (I](()) |||
|1)
At step f, LocalGD accesses the indices in St. By the active node condition codu, S Fug we have
(1)
vol(S,)
Σ du
k
(9)
Tug
||rs ||
(1()) 111
(f+11)
602
Then the total run time of LocalGD is
TPpR
vol(S.)
[|r(,)]] || - 11(tt2111)
ca
2
1=
||](0))
|11
|
(T)
where the last inequality is due to [1 = a. Therefore, the total run time is ((1/(ac)). Follow the similar technique, we have sublinear runtime bound for Katz, i.e., TKat [I-ax=dmmxx]] Next,
show the local diffusion bound for PPR. Recall LocalGD has the initial x: (0) 0, (0) ac2 and the following updates
x (1+1) = (1) + r.
r ((+1) = (()) Qr
S₁ = r( 2 eady, a v}.
Since = a and P AD by applying Theorem
3.5 we have the upper bound of T
T-1 1
| (0) 11
||r(()
II (1 an)) || 1=0
oJT
Note that each nonzero has at least part of the magnitude from the push operation of an active node. This means each nonzero of (T) satisfies
a)r! (
dp
(1 a)acdo (1 a)ae, for IT
dp
[|r(T) 1 2 (1 a)vee [rrl
where ī & T. Hence, we have
1
|
T <
In
47T
||((]]]
1
|| (
In
07
ac(1
- [T
1
C
In
071
24

---

where C' = (I-a)]zr1 To see the additive enror note that r()) = Qx = ae2
1
(I - (1-(1-1 (1- (1-o)AD w(T) It has the following equality
fa (T)) = (I - (1 a)AA 10)AD-1)-11 p(7)
To estimate the bound [ - vu (T) need to know (1-(1-a)AD r()),. Specifically, the u-th entry of the above is
fu[u] xu
(T)
Σ
fulu!r!
NEV
By Proposition B.1
we know du.uluu [u] dofulu.. then we continue to have
du
Sul(
Sa[u] (T)
(T)
dg
NEV
<
fufuu [u]ea
NEY
edu,
fulo]
VEV
cdus
where the first inequality is due to (2) eodyy, and the last equality follows from E Evev fu(e] = 1.
Combining all inequalities for u E V, we have the estimate ID= fPPR)]1 11 S e. We omit the proof of the sublinear runtime bound of LocalGD for Katz, it largely follows the proof technique in Corollary 3.4 For the two lower bounds of 1 1/c, i.e., vol(S.) /T S 1 it directly follows from the monotonicity and nonnegativity properties stated Theorem 3.2 and Theorem 3.5
Remark B.3. The part of the theorem shares the similar proof strategy we provided in 77 Here, use a slightly different formulation of the linear system.
B,5 Implementation Details
1/2 and b = aD- aD-1/22, Then f() (1) The eigenvalue of Q is in range [a, - a). So, we let L = 2 and a.
Chebyshev for PPR. Let Q
e/2e,
1. 81 1 a, (9) 0, 20) ae..
2. When have
11/2 (1) D 1/22 (0) DD 222
-ae
(1) ae, (I (1 - a)AAa)D--- -D
a(1 a) AD -ee. e..
3. When 2 1, have
8, 6,41 2 - 5.)) 5;)-
f(1) 26141 (12 1..0+11 (1/2
T-o
((++1) = f(1) + f(()
1/2pp(( (t+1)
-1) f(t)
For LocalCH, we change the update (()) to the update ((1) The final estimate f = 11/2
Chebyshev for Katz. We want solve (I AA) x e., We assume /4 admax (A), A) I
1 - --aAmin (A). Then, the updates of LocalCH for Katz centrality are
1. When 0, (0) O, (0) c.. To obtain initial value 81, have 81 ad
This is because (A(A)| S dmax.
25

---

2. When = 1, we have
(11 = (0) + 2 (())
L C,
L + H
r (1) b - (I - a A A)x(!!)
C, (I aA)
CsS (())
+ H
2a
= (1 L+p
es +
+ Ae..
3. When 2 updates the estimate-residual pair
6t+1 aadmax
5,
a()) 18,+1 (()) + 51d A
L-H
(1+1) 1) = (t) + (1))
((+1) = p(() (I aAA) a1()
For LocalCH, change the update a( to the update Tz.. (t) ((()) Cs.
The final estimate is then
We omit the details of LocalSOR and LocalGD) for PPR and Katz as they can directly follow from (6) and (10). respectively. We implement all our proposed local solvers via the FIFO Queue data structure.
B.6 FIFO-QUEUE and PRIORITY-QUEUE
We examine the different data structures of local methods and explore two types: the First-In-First- Out (FIFO) Queue, which requires constant time O(1) for updates, and the Priority Queue, which is used to implement the
algorithm as described in 48, 7). We test the number of operations needed using these two data structures on five small graphs, including CORA (n = 16316), CITESEER (n 4230, 10674), and
19793, m 126842), CORA-ML (n 2995, DBLP (n 17716, m = 105734), and PUBMED (n = 19717, m = 88648) as used downloaded from https://githutt com/ aboj hhevska/grapphgauss.
Figure 10 presents the ratio of the total number of operations needed by APPR-FIFO and APPR- Priority-Queue We tried four different settings; the performance of one does not dominate the other, and the Priority Queue suitable for some nodes but not all nodes.
=0.2,
1/m
0022
I/n
00111
I,
1/m
=0.1, 1/n
log Tarn--Quon
Logas Tricety Qproe
1.5
1.0-
Chrossase
Pussizo
Dur
1.3
Cura
Proszzo
Dare
Crnssax
1.5
1.0
Putono
Dur
1.5
10
Cinoeean
Tamr
0.5
Con
0.5
CousMM
Cons-it
0.5
ConA-ML
0.0-
0.0
-0.5
1.3
0.5
0.5
-1.0
1.0
1..0
1.0
0
20
10
60
80
100
20
41
50
50
100
20
40
60
80
100
0
20
40
60
80
100
Souree node
Scarce node
Source
mode
Smire node
Figure 10: The number of operations ratio between the APPR (FIFO-Queue) and Gauss- Southwell (Priority-Qeeue. The number of operations of APPR is defined TFIFO-Queue E S,, Trriority- = -K (du,, + logz supp(r(()))) where is the total number of push operations used in Gauss-Southwell iteration and supp(r(()) = {u r(()) 0,u V) and loga (R)) is the number of operations needed by the priority queue for maintaining all resid- uals in (k).
26

---

B.7 LocalGS(Dynamic) and LocalSOR(Dynamie
The dynamic PPR algorithm based LocalGS is presented in Algo. and initially proposed in [73] Specifically, Algo. and 3 are the components of LocalGSS(yynamic) for updating the edge event (u, u) while Algo. and are the components of LocagSOR for update the edge event (u, v). In practice, we follow the batch updates strategy proposed in InstantGNN [75], which call Algo. 3 aadd 5 for list of edge events then call Algo. 2 and 4 fonc after this batch update of edge events.
Algo 2 LocalGS(G, Ps. To, a, a)
Algo 3 LOCALLG Pa, Pa (,
1: while max, Ts [u] 2 edout [u] do Push(u)
1: Apply Insert/Delete of (u, v) to (p..
2:
2: return LocalGS Psy Tax a,
3: while min, r', ru[u] - cdout do
3: procedure Insert(u. v)
4: Push(u)
Ps [ f- Ps [u[u
* dout [2] (dout [u] 1)
5: return (p,,
5:
<- Ta (ulu -P pulu// dout [u]
6: procedure Push(u):
6:
Ts(u] < Ts +1 (1-a) Po [u] douu [u]
7: Palu] < pe[u] ru|u]
7: procedure Delete(u, v)
8: for v in Nou do
8:
Ps [u]
Ps Pa[u]
* dout [u] (dout [2]] 1)
9: re[u]] +
10:
[=[ + ra[v] +
(1-a)r.11 [w]
dans 14]
10:
9:
Ts (1)
t6
< Ts [
<- rx 1
+ Ps [u] dout (1)
(1 a)) Pa [u] doue (u]
Algo LocalSOR(G Ps: P,, G,,,
Algo LLCAA..S Ps. a, (u,
1: while max,, rs ru[u] 2 cdout [u] do
Apply Insert/Delete of (u, v) to (ps; r.).
2:
Push(u)
2: return LocalSOR Ps, Ta: at 8,
3: while min, ru[u]= S - -ddont do
3: procedure Insert(u,
4:
Push(u)
4:
Pa
[u]
+ ps [u[u]
* dout [u]] (dl/(dout//) - -)
5: return Ts)
5:
W +- Ts jul Ps [j]/douu [u]
6: procedure Push(u):
6:
[a(u] < T. [u] + (1 (1-60 a) Pe [u| /doe//o
7: Pa(u] < Ps + wr
7: procedure Delete(u, v)
8: ru(u]] < rr(u [u]
8: Pa[u] +- p. * dout [u] (dout [u] + 1)
9: for e in Nomt do
9:
u. +- Ta ju + Po [u] dout [u]
10: re[u] +- re[l] tw- (1-a))r.lv)
10: [s( <- Ts - (1 a) Po polul/ doue
doas M
B.8 InstantGNN(LocalGG)) and Instan(GNN(LcaaSORR)
We present InstantGNN(LocalGG)) and InstanGGNN(LcaJSOR) in Algo. and Algo. respectively. Additional parameter used; in practice, we choose B 11/2 for all our experiments.
Algo 6 inssnGGNNLLooaCCSSS(.........
Algo IIssannGNNNooocaoSRRii..........
1: while max, |r[u]] 2 cdg do
1: while max, |r[u]] 2 ed [u] do Push(u)
2: Push(u)
2:
3: return (p,r)
3:
return (p,r)
4: procedure Push(u):
4: procedure Push(u):
5: p(u] + p[u] a r([uj
5: plu] < plu + a a.ju
6: rfu] <-
6: r(u) r(u] -
7: for v in (u) do
7: for in Nam(u) do
8:
r=[u]] + r(u]
(1-0)-ffu 2 uldd (
8: r(e] r(w] +
(1 (1-a)-(11
z [u]d v
27

---

Table 3: Dataset Statistics sorted by + m
Dataset ID
Dataset Name
G
Citeseer
3279
9104
12383
G2
Cora
2708
10556
13264
G3
pubmed
19717
88648
108365
G4
ogbn-arxit -axxvv
169343
2315598
2484941
9s
nom-youtube
1134890
5975248
7110138
G6
wiki-talk
2388953
9313364
11702317
97
as-skitter
1694616
22188418
23883034
G8
cit-patent
3764117
33023480
36787597
9g
ogbl-ppa
576039
42463552
43039591
010
ogbn-mag
1939743
42182144
44121887
91
ogbn-proteins
132534
79122504
79255038
G12
soc-Ij1
4843953
85691368
90535321
913
reddit
232965
114615892
114848857
G14
egbn-producch
2385902
123612606
125998508
915
com-orkut
3072441
234370166
237442607
G16
wiki-en21
6216199
321647594
327863793
917
sebn-papers100m
111059433
3228123868
3339183301
918
nom-friendster
65608366
3612134270
3677742636
Datasets and More Experimental Results
C.1 Datasets Collected
We collected 18 graph datasets listed in Table To test LocalSOR on GNN propagation, we use three graphs with feature data from 75
C.2 Detailed experimental setups.
For all experiments, the maximum runtime limit is set 14,400 seconds. All methods will terminate when this time limit is reached. Specifically, we use the following parameter settings for drawing Figure I and Figure
Experimental settings for Figure 1 For computing PPR, we use a high precision parameter
of 10-10 /m and set OppR = 0.1. For calculating Katz centrality, we use O'aazz 1/(|A|2 1). The temperature for the Heat Kernel equation is set to r 10.
Experimental settings Figure caleulation.
We use the wiki-talk graph and a = 0.1 for PPR
Table 4: Parameters of InstantGNN
Dataset
Ir
batchsize
dropout
hidden size
layers
ogbn-arxiv
0.5
0.1
le-7
lc-4
8192
0.3
1024
ogbn-products
0.5
0.1
le-8
le-4
10000
0.5
1024
4
Table 4 presents parameter settings of InstantGNN model training in experiments. The GDE in InstamtGNN is defined as f = Zce a(1 - aa ( ADD is the same as APPNP 30) when we 3 0.5.
C.3 More experimental results
Figure [ presents the results of GPU-implementee methods for Katz. Table presents more details of participation ratios for PPR, Katz, and HK. The ratios in tables are without normalization. Figure 12 present more results of Figure 6 different datasets and settings. Figure and present dynamic PPR approximating and training GNN model results on different datasets.
28

---

GorGru) Lealce/orn
(PAGPU)
Rorning Time (+)
G3
Time
Figure 11: Comparison of running time (seconds) for CPU and GPU implementations for Katz.
Table Unnormalized participation ratios for PPR (a 0.1)
Participation Ratios
Graph
Vertices
Avg.Deg
Min
Mean
Median
Max
Cora
2708
3,90
1.11
2.57
2.60
5.68
Citeseer
3279
2.78
1.14
2.76
2.63
5.22
pubmed
19717
4.50
1.04
2.10
2.12
4.19
ogbn-proteins
132534
597.00
1.00
1.26
1.01
2.01
ogbn-arxiv
169343
13.67
1.03
1.84
1.65
4.12
reddit
232965
491.99
1.00
1.27
1.03
2.25
ogbl-ppa
576039
73.72
1.00
1.34
1.06
2.88
com-youtube
1134890
5.27
1.01
1.85
1.99
3.39
as-skitter
1694616
13.09
1.04
2.02
2.19
4.99
ogbn-mag
1939743
21.75
1.01
1.70
1.57
2.84
ogbn-products
2385902
51.81
1.00
1.46
1.19
2.84
wiki-talk
2388953
3.90
1.00
1.61
1.68
2.87
com-orkut
3072441
76.28
1.00
1.29
1.05
2.19
cit-patent
3764117
8.77
1.01
1.67
1.55
2.99
soc-ljl
4843953
17.69
1.00
1.68
1.73
3.73
wiki-en21
6216199
51.74
1.00
1.34
1.11
2.22
com-friendster
65608366
55.06
1.00
1.46
1.20
2.23
ogbn-papers 100M
111059433
29.10
1.00
1.45
1.19
2.15
Table Unnormalized participation ratios for Katz(o = 1/(1 + 2A
Participation Ratios
Graph
Vertices
Avg.Deg.
Min
Mean
Median
Max
Cora
2708
3,90
1.01
7.62
3.34
30.24
Citeseer
3279
2.78
1.01
7.03
2.09
40.77
pubmed
19717
4.50
1.01
25.71
2.23
173.21
ogbn-proteins
132534
597.00
1.00
2181.89
2997.35
3397.70
ogbn-arxiv
169343
13.67
1.00
18.06
6.04
47.12
reddit
232965
491.99
1.00
3364.93
4412.49
4757.13
ogbl-ppa
576039
73.72
1.00
507.92
43.88
2984.20
com-youtube
1134890
5.27
1.00
10.86
8.65
42.78
as-skitter
1694616
13.09
1.00
52.56
5.07
702.30
ogbn-mag
1939743
21.75
1.00
8.24
6.71
182.96
ogbn-products
2385902
51.81
1.00
100.53
27.33
649.78
wiki-talk
2388953
3.90
1.00
404.15
587.18
701.41
com-orkut
3072441
76.28
1.00
637.67
50.15
1824.24
cit-patent
3764117
8.77
1.00
37.49
6.01
315.39
soc-Ij1
4843953
17.69
1.00
358.72
5.00
2122.33
wiki-en21
6216199
51.74
1.00
110.88
156.60
189.79
com-friendster
65608366
55.06
1.00
8475.52
9.02
36776.54
ogbn-papers100M
111059433
29.10
1.00
97.53
7.93
726.71
29

---

Table 7: Unnormalized participation ratios for HK(7 10)
Participation Ratios
Graph
Vertices
Avg.Deg.
Min
Mean
Median
Max
2708
3.90
1.65
8.43
6.62
34.85
citeseer
3279
2.78
1.82
7.69
5,81
35.71
pubmed
19717
4.50
1.15
26.02
7.09
242.95
ogbn-proteins
132534
597.00
437.31
5743.38
5712.33
12874.41
ogbn-arxiv
169343
13.67
1.95
15.48
10.61
109.58
reddit
232965
491.99
30.26
2697.53
2468.45
5395.28
ogbl-ppa
576039
73.72
2.02
1052.49
766.77
3860.21
com-youtube
1134890
5.27
1.06
8.66
4.73
58.02
as-skitter
1694616
13.09
1,51
13.04
7.18
45.05
ogbn-mag
1939743
21.75
1,50
2.63
1.96
16.90
ogbn-products
2385902
51.81
2.16
124.51
72.87
775.54
wiki-talk
2388953
3,90
1.00
8.19
1.43
65.72
com-orkut
3072441
76.28
6.02
655.85
367.02
7942.79
cit-patent
3764117
8.77
1.76
30.51
21.03
273.80
soc-Ij1
4843953
17.69
2.29
59.08
24.23
573.48
wiki-en21
6216199
51.74
3.00
34.05
32.49
164.69
com-friendster
65608366
55.06
2.05
323.12
83.67
3092.69
ogbn-papers 100M
111059433
29.10
1.44
51.49
21.40
275.48
Spetto 1000
Citeseer
wiki-talk
ogbn-arxiv
com-youtube
Figure 12: Running time (seconds) as function of for PPR on several datasets with 0.1.
30

---

Tarnn The
Spaate tart
Spacn
Citeseer
wiki-talk
ogbn-arxiv
com-youtube
Figure 13: Running time (seconds) function of for Katz on several datasets with 1/[|| 2 + 1).
Speiio
Citeseer
wiki-talk
ogbn-arxiv
com-youtube
Figure 14: Running time (scconds) function of for HK on several datasets with 10.
a = 0.5
a = 0.2
a
0.1
a
0.05
a 0.01
Figure 15: Running time (seconds) of SOR and LocalSOR function of for PPR on the wiki-talk dataset with different a.
31

---

Dysanii
10:00
Snapshot
Snapsnot
Snapshot
ogbn-arxiv
ogbn-products
ogbn-papers 100
Figure 16: Accumulated number of operations on some dynamic graphs.
IetomGHti))) neo550t Propreiiinn
Intonicii (ealfS)
Propagaticn IntuntONb(Lacaaa Triiing
bean@HHk1ss1800) Traning
5000
botan(GWW(LoolBOR)) infonnce
Locas)) Inforenee
79
Runting Time (4)
Accuray (%)
IastantSMM/LocaBB0R)
Snapshot
Snapshet
Figure 17:
The performance of InstantGNN using SOR and GS propagation ogbn-products.
C.4 The efficiency of local methods on different types of graphs (tested grid graphs).
Our local algorithms do not depend on graph types. However, our key assumption is that diffusion vectors are highly localizable, measured by the participation ratio. As demonstrated in Figure [ almost all diffusion vectors have low participation ratios collected from 18 real-world graphs. These graphs are diverse, ranging from citation networks and social networks to gene structure graphs. To further illustrate this, we con- ducted experiments where the graphs are grid graphs, and the diffusion vectors have high participation ratios (about 3.56 x 10 with a grid size of 1000x 1000, i.e., 10c nodes and 1,998,000 edges). We set aPPR 0.1. The figure below presents the running time as a function of over grid graph with 50 sampled source nodes.
Running Time
LecalGD
LocalGS
SOR
LocalSOR
The results indicate that local solvers are more efficient than global ones even when is very small.
32

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims made in the abstract and introduction accurately reflect our contributions and scope. We introduced a novel framework for approximately solving graph diffusion equations (GDEs) using local diffusion process.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discussed several limitations of our proposed work in the last section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiitiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
33

---

Answer: [Yes]
Justification: The paper thoroughly presents theoretical results, including the full set of assumptions necessary for each theorem and lemma. Each proof is detailed and follows logically from the stated assumptions, ensuring correctness.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofss provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide comprehensive details on the experimental setup, including de- scriptions of the datasets used, parameter settings, and the specific algorithms applied. We also provided our code for review and will make it public upon publication.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should possible for other researchers to have some path reproducing verifying the results.
34

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We provide open access the data and code, along with instructions in the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
httpp/.cccpubllc/uuucccee Codeeubmii ssi crrionPPoiccy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We follow the existing experimental setup and provide detailed information on the training and testing settings used for InstantGNN with LocalSOR.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The paper reports error bars and other relevant information about the statistical significance of the experiments. We use 50 randomly sampled nodes and plot the mean and standard deviation of the results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
35

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
The experiments were conducted using Python 3.10 with CuPy and Numba libraries on server with 80 cores, 256GB of memory, and two NVIDIA-4090 GPUs with 28GB each.
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httppp/////eaaeppp.ccppppppiiiip
Answer: [Yes]
Justification:
The research adheres to all aspects of the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There are no broader societal impacts, as it focuses on technical contributions.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
36

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not involve data or models with a high risk for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not involve licenses for existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
37

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
batasets.papersstt
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out the asset's s creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not involve new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing and research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector:
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve institutional review board (IRB) approvals or equivalent for research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
38

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
39


Reviews:
[{"review_id": "VlEcV2WAvd", "reviewer": "Reviewer_kfsj", "summary": "This paper proposes a suite of fast methods to approximately compute graph diffusion vectors such as Personalized PageRank, Katz centrality and the heat kernel. A notable feature of the proposed methods is that they are easily parallelizable and hence can achieve further acceleration on GPU. The authors also provide a running time bound for each method that they introduce. Empirical results show that the new local methods can achieve up to a hundred-fold speedup when compared to their global counterpart.", "questions": "- Line 188: The open problem is recently solved by Martínez-Rubio et al, Accelerated and Sparse Algorithms for Approximate Personalized PageRank and Beyond, 2023.\n- When eps goes to 0, do the approximate solutions converge to the exact global solutions?", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written and easy to follow.\n- The local diffusion framework is applicable to computing several important graph diffusion vectors.\n- The experiments are reasonably comprehensive.", "weaknesses": "- When compared with APPR, the speedup is not really captured by Theorem 3.3 and Corollary 3.6. The authors only showed that $\\overline{\\mbox{vol}}(\\mathcal{S}_T)/\\bar\\gamma_T \\le 1/\\epsilon$, but it requires strict inequality to achieve nontrivial speedup in terms of worse-case running time. It is not clear how tight this bound is in general. If the bound is tight, then in the worst case there is no speedup. The authors should comment on if there are classes of graphs over which there will be a notable gap between the 2 quantities $\\overline{\\mbox{vol}}(\\mathcal{S}_T)/\\bar\\gamma_T$ and $1/\\epsilon$, so that the result provides a meaningful improvement.\n- Because the theorems concerning the worst-case running time do not seem to capture a clear improvement over simple baseline local methods, it is unclear where exactly the speedup reported in Table 2 comes from.\n- In LocalGD and LocalCH, the authors did not provide an update rule (or even a definition) for $\\mathcal{S}_t$. Since $\\mathcal{S}_t$ is part of the local diffusion process, the authors should specify how $\\mathcal{S}_t$ is updated or defined at each step. I guess that $\\mathcal{S}_t$ depends on the termination condition, but I could not find where the authors mention about it in the main paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time and effort to review our paper carefully. We appreciate your positive perspective on our paper. Your concerns and our responses are listed as follows.\n\n---\n\n**Q1.** The concern of two quantities $ \\overline{\\operatorname{vol}}\\left(\\mathcal{S}_T\\right) / \\overline{\\gamma}_T $ and $ 1 / \\epsilon$: It is unclear how tight this bound is in general.\n\n**A:** Thank you for this great point. Our bound is slightly rough. The actual inequality is $ \\overline{\\operatorname{vol}}\\left(\\mathcal{S}_T\\right) / \\overline{\\gamma} _T < 1 / \\epsilon$ as long as $T \\geq 1$.  The inequality used in Line 664 $(\\leq)$ is actually $(<)$, i.e., $\\sum _{i=1}^{ |\\mathcal S_t|} r _{u_i} / ||\\boldsymbol{r}^{(0)} ||_1 < \\sum _{i=1}^{ |\\mathcal S_t|} r _{u_i} / ||\\boldsymbol{r}^{(t)} ||_1$ as long as $t \\geq 1$. This strict inequality is achievable if the algorithm runs more than one iteration. The reason is that the monotonicity property of $|| \\boldsymbol r^{(t)} ||_1$ is actually $|| \\boldsymbol r^{(0)} ||_1 < || \\boldsymbol r^{(1)} ||_1 <\\cdots < ||  \\boldsymbol r^{(t)} ||_1 < \\cdots$ where there are at least some magnitudes that are moved from $\\boldsymbol r^{(t)}$ to $\\boldsymbol x^{(t)}$ per-iteration. Therefore, in the worst case, the improvement of our bound is significant if the factor $1/\\epsilon$ is the main concern. \n\nMore importantly, it is better to compare two local bounds presented in Theorem 3.3 instead of only considering two quantities. We conducted a simple experiment to compare these two quantities (please see our detailed experimental results in the attached file) and two local bounds. Our results indicate the effectiveness of our local bounds. The time-evolving bound is more suitable and mirrors the actual performance. \n\n---\n\n**Q2.** It is unclear where exactly the speedup reported in Table 2 comes from.\n\n**A:** Table 2 presents the speedup ratio of computing PPR vectors comparing the local and global solvers where we set $\\epsilon = 1/n$ and report the value $\\mathcal{T} _{\\mathcal A} / \\mathcal{T} _{ \\text{Local} \\mathcal A} $ where $\\mathcal{T} _{\\mathcal A}$ is the total number of operations needed for algorithm $\\mathcal{A}$. The results of different local solvers are in Figure 4. These results indicate that local solvers speed up significantly compared to their global counterparts.\n\n---\n\n**Q3.** The definition of $\\mathcal{S}_t$ in LocalGD and LocalCH is missing.\n\n**A:** Thank you for pointing out this. The active set $\\mathcal{S} _t$ indeed depends on the termination condition. We defined $\\mathcal{S}_t = \\\\{ u _1, u _2, \\ldots, u _{\\left| \\mathcal{S} _t \\right|} \\\\}$ be the set of active nodes processed in $t$ iteration in Section 3.1. Specifically, at any time $t$, $\\mathcal S _t$ maintains the set $\\\\{ u \\in \\mathcal{V} : |r_u| \\geq   \\alpha \\epsilon d_u \\\\}$ for calculating PPR. The definition of Katz's score is similar. We will clarify these $\\mathcal{S} _t$ for all local solvers in our manuscript.\n\n---\n\n**Q4.** For the PPR computation, the open problem was recently solved by Martínez-Rubio et al. (2023, COLT)\n\n**A:** Thank you for pointing out this latest work. We are also aware of Martínez-Rubio's work when we are submitting our manuscript. First of all, Algorithm 4 in Martínez-Rubio's work is proposed for solving PPR, not graph diffusion vectors (GDEs). But, the problem in our paper is solving GDEs which is more general than the open problem.\n\nWhen we empirically compared our work, LocalSOR, with ASPR, we found that ASPR is much slower than our proposed LocalSOR. **The main reason is that ASPR is based on a nested subspace pursuit strategy, and the corresponding iteration complexity is bounded by $\\mathcal O (|\\mathcal S^\\star| / \\sqrt{\\alpha} )$ where $\\mathcal S^\\star$ is the support of the optimal solution. This bound deteriorates to $\\tilde {\\mathcal {O}} (n / \\sqrt{ \\alpha})$ when the solution is dense, with $ n$ representing the number of nodes in $\\mathcal G$, which could be less favorable than that of standard solvers under similar conditions. Please see the detailed experimental results in our attached file.** Moreover, the nested computational structure provides a constant factor overhead, which could be significant in practice.\n\n---\n\n**Q5.** When $\\epsilon \\rightarrow 0$, do $\\boldsymbol{x}^{(t)}$ converge to $\\boldsymbol{x}^{*}$?\n\n**A:** Yes. For PPR using LocalSOR in Theorem 3.3, we proved that the estimate $\\boldsymbol{x}^{(T)}$ satisfies $\n||\\boldsymbol{D} ^{-1}(\\boldsymbol{x} ^{(T)}-\\boldsymbol{f} _{\\text{PPR}})|| _{\\infty} \\leq \\epsilon$.  This means $\\boldsymbol{x} ^{(T)} \\rightarrow \\boldsymbol{f} _{\\text{PPR}}$ when $\\epsilon \\rightarrow 0$.  For Katz using LocalSOR in Corollary 3.4, the estimate $\\hat{\\boldsymbol{f}} _{\\text {Katz }} =\\boldsymbol{x}^{(T)}-\\boldsymbol{e} _s$ satisfies $||\\hat{\\boldsymbol{f}} _{\\text {Katz }}-\\boldsymbol{f} _{\\text {Katz }} ||_2 \\leq ||(\\boldsymbol{I}-\\alpha \\boldsymbol{A})^{-1} \\boldsymbol{D} ||_1 \\cdot \\epsilon$. This means $\\hat{\\boldsymbol{f}} _{\\text {Katz }} \\rightarrow \\boldsymbol{f} _{\\text{Katz}}$ when $\\epsilon \\rightarrow 0$. One can obtain similar results for LocalGD.\n\n---\n\nWe hope that our clarifications can address your concerns. **We are happy to have further discussions if needed!**", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FsMJfEmbfv", "reviewer": "Reviewer_JA1M", "summary": "This paper proposes a new local iterative framework for solving graph diffusion equations (GDEs). Specifically, the framework approximates GDEs through a local diffusion process, leveraging the strong localization properties of diffusion vectors such as personalized PageRank, Katz centrality, and Heat Kernel. The proposed local solvers can achieve sublinear runtime complexity under certain monotonicity assumptions. Empirical results demonstrate that these solvers significantly accelerate their standard counterparts on several large-scale benchmark datasets.", "questions": "Please refer to Weaknesses.", "limitations": "NA", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-structured and clear.\n\n2. The theoretical analysis is rigorous and sound, providing runtime complexity bounds for some of the proposed local solvers, which are better than their standard counterparts.\n\n3. The effectiveness of the proposed methods is well-supported by experimental results on large-scale benchmark datasets.", "weaknesses": "1. It is not clear how graph structures, such as sparsity and spectral properties, impact the runtime complexity of the local solvers. A discussion on the potential influence of graph structures on runtime complexity would be helpful.\n\n2. The runtime complexity analysis assumes that the updates of local solvers satisfy monotonicity properties. However, LocalCH does not satisfy these properties during updates. Establishing runtime bounds for LocalCH may require different techniques.\n\n3. In Figure 7, when $\\epsilon \\geq 2^{-31}$, the running time of LocalGD is the same as GD, indicating that LocalGD may not speed up the standard counterparts when $\\epsilon$ is sufficiently small.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are happy that you like our work. We appreciate your time and effort in reviewing our submission. We addressed your concerns as follows:\n\n---\n\n**Q1.** It is unclear how graph structures, such as sparsity and spectral properties, impact the runtime complexity of the local solvers.\n\n**A:** In terms of graph structure, our local algorithms do not depend on graph types. A key assumption of our paper is that the computed diffusion vectors are highly localizable, measured by the participation ratio. It is worth studying whether high-participation ratio diffusion vectors exist in real-world graphs. To verify this further, we conducted a simple experiment where the graphs are grid graphs, and the diffusion vectors have low participation ratios. The results indicate that local solvers are more efficient than global ones, even with low participation ratios. **Please also check our general response and our attached PDF file to see the detailed experimental results.**\n\nIn terms of spectral properties, the performance of both local and global solvers is affected by the spectra of the underlying graph. For example, let $\\lambda_1,\\lambda_2, \\ldots, \\lambda_n$ be the eigenvalues of normalized Laplacian of the underlying matrix defined by the graph. Then, the condition number is determined by $\\lambda_1$ and $\\lambda_n$, which will dominate the convergence rate of all methods. Furthermore, when the eigenvalues are clustered together, all methods will be easier to converge due to the same reason. Thank you for this great point, and we will add discussions on this to our manuscript.\n\n---\n\n**Q2.** Comments on the difficulty of accelerated bound analysis for LocalCH.\n\n**A:** The sublinear runtime analysis for LocalCH is complicated since it does not follow the monotonicity property during the updates. One cannot directly follow existing techniques. One possible solution is that the diffusion process can be effectively characterized by the residuals of LocalCH, which is a type of second-order difference equation with parameterized coefficients. We then use this second-order difference equation to provide a bound. However, the core difficulty is that this difference equation is difficult to analyze when the coefficients are parameterized.  We are actively investigating this direction. \n\n---\n\n**Q3.** When $\\epsilon$ is sufficiently small, LocalGD may not speed up the standard counterparts.\n\n**A:** We admit that when $\\epsilon \\rightarrow 0$, it is hopeless to speedup the standard counterparts as the optimal first-order methods need run time $\\mathcal{O}(m/\\sqrt{\\alpha})$ for computing PPR vectors. In the high precision ( in Figure 7), when $\\epsilon \\geq 2^{-31}$, the running time of LocalGD is slightly less than that of GD. More importantly, the computation of high-precision diffusion vectors is not our main goal. We aim to develop faster local methods when high precision is not a strong requirement. Many applications of graph learning problems only need lower precisions, such as local clustering and training GNN models.\n\nTo summarize, for the first time, we propose a novel framework for designing efficient local solvers that could be applied to many graph diffusion equations (GDEs). These GDEs solvers can be applied to local clustering and training graph neural networks, improving the efficiency of these algorithms. We are happy to have further discussions if needed!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "staCuM1RYa", "reviewer": "Reviewer_X7w6", "summary": "This paper proposes a novel framework for approximately solving graph diffusion equations using a local diffusion process. In addition,  the proposed method can effectively localizes standard iterative solvers by designing simple and provably sublinear time algorithms.", "questions": "See comments in Weaknesses.", "limitations": "Not applicable.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "+ The problem is well motivated and the paper is well-written.\n+ Extensive experiments are conducted to showcase the efficiency of graph diffusion framework to approximating graph diffusion equations.\n+ The paper provides a good summary of existing graph diffusion equations.\n+ The authors provide code and details of implementations.", "weaknesses": "- In this paper, the authors explore 18 different graphs, can the authors show/provide which local GDE solver achieves better performance on which type(s) of graphs? \n- Computational complexity/cost is missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time and effort to review our paper. We believe there may have been some misunderstandings, and your two concerns can be effectively resolved as follows:\n\n---\n\n**Q1.** Can the authors show/provide which local GDE solver achieves better performance on which type(s) of graphs?\n\n**A:** **We answered this question in Section 5.1 (Line 272 to Line 282).** Our results in the lower precision setting suggest that LocalSOR and LocalGD perform best overall. Figure 6 illustrates the performance of LocalSOR and LocalGS for PPR and Katz. As $\\epsilon$ becomes smaller, the speedup of LocalSOR over LocalGS becomes more significant. In practice, when GPU resources are available, using LocalCH (corresponding to an accelerated convergence rate) is recommended instead of LocalGD in the high precision range. When GPU resources are unavailable, using LocalSOR (corresponding to an accelerated convergence rate with optimal $\\omega$) instead of APPR is recommended in the high precision range.\n\n**More importantly, our local algorithms do NOT depend on graph types.** A fundamental assumption of our paper is that the computed diffusion vectors are highly localizable, measured by the participation ratio. As demonstrated in Figure 1, almost all diffusion vectors have low participation ratios collected from 18 real-world graphs. It is worth studying whether high-participation ratio diffusion vectors exist in real-world graphs. Interestingly, when the participation ratio is high, local solvers still offer some level of speedup compared to global ones. To verify this, we conducted a simple experiment where the graphs are grid graphs, and the diffusion vectors have high participation ratios. The results indicate that local solvers are more efficient than global ones, even when the participation ratios are high. **Please check our attached PDF file to see the detailed experimental results on grid graphs.**\n\n---\n\n**Q2.** Computational complexity/cost is missing.\n\n**A:** **There seems to be some misunderstanding. The analysis of the computational complexity of local solvers is actually one of our core contributions.** The main contribution of our paper is to show the local runtime complexity of these two methods for different GDEs. Our framework is quite general and applicable to a broad range of GDEs. Specifically, these runtime complexities are stated in Theorem 3.3 (LocalSOR for PPR), Corollary 3.4 (LocalSOR for Katz), and Corollary 3.6 (LocalGD for PPR and Katz). Therefore, we are unsure whether you mean the runtime complexity of LocalSOR and LocalGD for Katz and PPR, or something else.\n\n**We are ready and happy to discuss any further concerns you may have.**", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gRx6VxI6N6", "reviewer": "Reviewer_X6sG", "summary": "The paper, \"Faster Local Solvers for Graph Diffusion Equations,\" addresses the efficiency of computing Graph Diffusion Equations (GDEs) such as Personalized PageRank (PPR), Katz centrality, and the Heat kernel, which are essential for various graph-related problems like clustering and training neural networks. Traditional methods for solving GDEs are computationally intensive for large-scale graphs. This paper introduces a novel framework for approximating GDEs using local diffusion processes, which significantly reduces computational time and improves scalability by leveraging the localization property of diffusion vectors. The proposed local solvers are highly parallelizable and suitable for GPU implementation, offering up to a hundred-fold speed improvement and applicability to large-scale dynamic graphs. The paper also discusses the potential for these methods to enhance local message-passing mechanisms in Graph Neural Networks (GNNs).", "questions": "What are the potential trade-offs between precision and computational efficiency, and how can practitioners balance these in practical applications?\n\nThe paper includes quite some datasets to test, with biggest of ogbn-papers100M. How does the proposed method handle very large-scale dynamic graphs in real-time applications, and what are the potential bottlenecks?", "limitations": "See above", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The introduction of a novel framework for localizing the computation of GDEs using local diffusion processes is a significant contribution. This approach reveals the suboptimality of existing local solvers and provides a more efficient solution.\n\n\nThe paper offers a solid theoretical foundation, proving that popular diffusion vectors have strong localization properties using the participation ratio. It demonstrates that Approximate Personalized PageRank (APPR) can be treated as a special case of the proposed framework, providing better diffusion-based bounds. The design of simple and fast local methods based on standard gradient descent and the local Chebyshev method for symmetric propagation matrices is well-founded.\n\n\nExperimental results on GDE approximation for PPR, HK, and Katz show significant acceleration over standard methods. The proposed local solvers demonstrate up to a hundred-fold speed improvement. The paper also shows that the new methods can be naturally adopted to approximate dynamic diffusion vectors, and they outperform standard PPR-based GNNs in training speed.", "weaknesses": "Precision Limitations: While the paper shows significant speedups for lower precision settings, the performance gain diminishes as higher precision is required. This limitation could affect the applicability of the methods in scenarios where high precision is crucial.\n\nSequential Nature: (Please correct if I am wrong.) Despite improvements, the reliance on sequential updates in some methods (like LocalSOR) still poses challenges for achieving maximal parallel efficiency.\n\nComplexity of Analysis: The runtime analysis for some of the proposed methods, such as the Local Chebyshev method, is noted as complex and remains an open problem. Maybe simplifying this analysis or providing more intuitive explanations could enhance the paper’s accessibility.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time and effort to review our paper. We appreciate your positive perspective. We resolve your concerns as follows.\n\n---\n\n**Q1.** What are the potential trade-offs between precision and computational efficiency, and how can practitioners balance these in practical applications? The performance gain diminishes as higher precision is required, which could affect the methods' applicability in scenarios where high precision is crucial.\n\n**A:** Please see our general response to this concern. Furthermore, it is true that when $\\epsilon$ is lower, the run time of our local methods is getting closer to global ones. In the large range of precision $\\epsilon \\leq 10^{-4}/n$, however, they are still competitive and use less time. Furthermore, high precision is not required in most empirical settings of graph learning problems, including local clustering, training GNN models, and learning graph embeddings. It is still an open problem that the minimal complexity is significant when $\\epsilon$ is lower ( proportional to $\\log 1/\\epsilon$). In terms of training dynamic GNNs, the precision is about $\\mathcal{O}(1/m)$. In terms of local graph clustering, the precision is about $1/n$. The essential question is whether or not our methods are optimal or close to the optimal local methods.  We believe this question is worth studying further in our future work.\n\n---\n\n**Q2.** Despite improvements, relying on sequential updates in some methods (like LocalSOR) still poses challenges for achieving maximal parallel efficiency.\n\n**A:** Yes, the sequential updates of LocalSOR are not suitable for parallelization. This is why we propose local gradient descent and the local Chebyshev method to speed up these methods further. However, we still think the local SOR is valuable when the GPU resources are not available and is more power efficient. In practice, when high precision is needed, we recommend using LocalSOR when GPUs are not available, as both LocalSOR and LocalCH have accelerated rates in the global setting.\n\n---\n\n**Q3.** Comments on the runtime analysis for some proposed methods, such as the Local Chebyshev method.\n\n**A:** Thank you for this great point. We are still investigating this strategy. Please also see a more detailed explanation in our general response. The sublinear runtime analysis for LocalCH is complicated since it does not follow the monotonicity property during the updates. One cannot directly follow existing techniques. One possible solution is that the diffusion process can be effectively characterized by the residuals of LocalCH, which is a type of second-order difference equation with parameterized coefficients. We then use this second-order difference equation to provide a bound. However, the core difficulty is that this difference equation is difficult to analyze when the coefficients are parameterized. We are actively investigating this direction.\n\n---\n\n**Q4.** How does the proposed method handle very large-scale dynamic graphs in real-time applications, and what are the potential bottlenecks?\n\n**A:** The potential bottleneck is memory usage when the precision is high. We tried to apply our local solvers to the ogbn-papers100M graph, but our GPU memory is limited to 24GB. It fails to train due to memory issues. One reason is that the graph size is too large. However, the other reason could be that memory usage is linear to $1/\\epsilon$. We will investigate this further and explore more efficient ways to reduce memory usage in this case. However, our paper shows that speedup is very significant when the participation ratio is low for middle-scale dynamic graphs where we tested these local solvers on training dynamic GNN models on the ogbn-arxiv and ogbn-products datasets. \n\n**We are happy to discuss any further concerns you may have.**", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
**Our General Responses**

We thank all reviewers for their time and effort in carefully reading our paper. To address some general concerns, we included experimental results in the attached PDF file. Furthermore, some general concerns are worth to response as follows:

---

**Q1. Potential trade-offs between precision and computational efficiency: When high precision is required, i.e., $\epsilon \rightarrow 0$, the efficiency of local solvers diminishes (Reviewer kfsj, JA1M, X6sG).**

**A:** To clarify, the effective speedup of local solvers over the standard ones is when $\epsilon \leq 10^{-4}/n$ empirically. This already covers many downstream applications, including local clustering (where $\epsilon = 10^{-6}$ and $n\approx 10^{-6}$ see Fountoulakis's work in [1]) and training graph neural networks (where $\epsilon = 10^{-4}$ but $n \geq 10^{5}$ see Bojchevski's work on the PPRGo model in [2]), as far as we know. It is a reasonable observation that the efficiency of local solvers diminishes when $\epsilon \rightarrow 0$, as the number of iterations needed for both local and global solvers is proportional to $\log(1/\epsilon)$. These local solvers are more like their global counterparts. Specifically, for the optimal first-order global solvers, they require $\mathcal{O}(m \sqrt{\kappa} \log(1/\epsilon))$, where $m$ is the number of edges in the graph and $\kappa$ is the condition number (e.g., $\kappa = 1/\alpha$ when the graph diffusion equation is PPR). Similarly, for the local solvers, as proved in our Theorem 3.3, the number of *local iterations* is also proportional to $\log(1/\epsilon)$. It is unknown, but it remains interesting to see whether the runtime of *optimal first-order local methods* is proportional to $\log(1/\epsilon)$. We will study this problem in future work.

---

**Q2. Comments on the difficulty of accelerated bound analysis for LocalCH (Reviewer JA1M, X6sG)**

**A:** We are actively investigating this direction and have some preliminary results. The sublinear runtime analysis for LocalCH is complicated since it does not follow the monotonicity property during the updates. One cannot directly follow existing techniques. One possible solution (we are investigating it) is that the diffusion process can be effectively characterized by the residuals of LocalCH, which is a type of second-order difference equation with parameterized coefficients. We then use this second-order difference equation to provide a bound. However, the core difficulty is that this difference equation is difficult to analyze when the coefficients are parameterized. Due to the space limit, we believe the convergence analysis of more advanced local solvers, such as LocalCH and LocalSOR with optimal parameters, can be treated as independent work.

---

**Q3. The effectiveness of local bounds compared with existing local bounds. (Reviewer kfsj)**

**A:** Our bound is effective. By a refined analysis, the actual inequality is $ \overline{ \operatorname {vol} } (\mathcal{S} _T ) / \overline \gamma _T < 1 / \epsilon$  as long as $T \geq 1$. The inequality used in Line 664 $(\leq)$ is actually $(<)$, i.e., $\sum _{i=1}^{ |\mathcal S_t|} r _{u_i} / ||\boldsymbol{r}^{(0)} ||_1 < \sum _{i=1}^{ |\mathcal S_t|} r _{u_i} / ||\boldsymbol{r}^{(t)} ||_1$ as long as $t \geq 1$. This strict inequality is achievable as long as the algorithm runs at least for two iterations. The reason is that the monotonicity property of $|| \boldsymbol r^{(t)} ||_1$ is actually $|| \boldsymbol r^{(0)} ||_1 < || \boldsymbol r^{(1)} ||_1 <\cdots < ||  \boldsymbol r^{(t)} ||_1 < \cdots$ where there are at least some magnitudes that are moved from $\boldsymbol r^{(t)}$ to $\boldsymbol x^{(t)}$ per-iteration. Therefore, in the worst case, the improvement of our bound is significant if the factor $1/\epsilon$ is the main concern. We conduct a simple experiment to compare these two quantities. **Please check our attached PDF file to see the experimental explanations.**

---

**Q4. Comments on the performance of local solvers over different graph structures. (Reviewer JA1M, X7w6)**

**A:** Our local algorithms do not depend on graph types. A fundamental assumption of our paper is that the computed diffusion vectors are highly localizable, measured by the participation ratio. As demonstrated in Figure 1, almost all diffusion vectors have low participation ratios collected from 18 real-world graphs. It is worth studying whether high-participation ratio diffusion vectors exist in real-world graphs. Interestingly, when the participation ratio is high, local solvers still offer some level of speedup compared to global ones. To verify this, we conducted a simple experiment where the graphs are grid graphs, and the diffusion vectors have high participation ratios. The results indicate that local solvers are more efficient than global ones, even when the participation ratios are high. **Please check our attached PDF file to see the detailed experimental results.**

To summarize,  for the first time, we propose a novel framework for designing efficient local solvers that could be applied to many graph diffusion equations (GDEs). These GDEs solvers can be applied to local clustering, training graph neural networks improving the efficiency of these algorithms.

---
**References**

- [1] Fountoulakis, K., Roosta-Khorasani, F., Shun, J., Cheng, X., & Mahoney, M. W. (2019). Variational perspective on local graph clustering. Mathematical Programming, 174, 553-573.

- [2] Bojchevski, Aleksandar, Johannes Gasteiger, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberczki, Michal Lukasik, and Stephan Günnemann. "Scaling graph neural networks with approximate PageRank." In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2464-2473. 2020.

Meta-review: This paper introduces a set of efficient methods for approximating graph diffusion vectors. Their approach achieves significant acceleration when implemented on GPUs. Empirical results demonstrate that these new methods can achieve speedups of up to one hundred times compared to their global counterparts.

Although the score is borderline, I find this contribution meaningful since it can potentially have an impact in speeding up computation which appears in the industry sector.
Decision: Accept (poster)