Pith. sign in

REVIEW 4 major objections 5 minor 49 references

Scaling Up Graph Propagation Computation on Large Graphs: A Local Chebyshev Approximation Approach

T0 review · 4 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims that swapping Taylor expansions for Chebyshev expansions speeds up graph propagation by a square-root factor and yields a local push algorithm with a proven error bound.

desk verdict ChebyPower is a clean, publishable acceleration; ChebyPush's headline local bound rests on an unproven stability assumption and a broken lemma, so the paper deserves a careful referee rather than a desk reject. read the letter →

arxiv 2412.10789 v1 pith:J76UBAYO submitted 2024-12-14 cs.LG cs.DS

Yichun Yang , Rong-Hua Li , Meihao Liao , Longlong Lin , Guoren Wang This is my paper · ORCID
classification cs.LGcs.DS
keywords graphpropagationChebyshevpolynomialspersonalizedPageRankheatkernelpushalgorithmpoweriterationlocalrandomwalkmatrix
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Graph propagation scores like personalized PageRank and heat kernel PageRank are infinite sums of random-walk matrix powers, and the usual way to approximate them is to truncate a Taylor series. This paper argues that the Taylor basis is the wrong basis: because Chebyshev polynomials are orthogonal and optimal in squared-error approximation, expanding the same propagation function in Chebyshev polynomials halves the needed number of terms, from roughly N to the square root of N for the two most studied examples. The paper gives closed-form Chebyshev coefficients for both PageRank variants and builds two algorithms on them. The global variant, ChebyPower, accelerates power iteration; the local variant, ChebyPush, uses a subset Chebyshev recurrence to push only important nodes and still carries a degree-normalized error guarantee. If the claims hold, high-precision PageRank and heat-kernel queries on billion-edge graphs become several times cheaper, and the same recipe applies to more general propagation functions used in graph learning.

What carries the argument

The central object is the Chebyshev expansion of the graph propagation function, f(P) = sum_k c_k T_k(P), with P = A $D^{{-1}}$ and the three-term recurrence T_{k+1}(P) = 2P T_k(P) - T_{k-1}(P). The coefficients for SSPPR and HKPR are explicit closed forms involving $\beta$^k and modified Bessel functions I_k(t). The additional mechanism that makes the method local is the subset Chebyshev recurrence, computed by pushing only nodes with |rhat_k(u)| > epsilon_k d_u; the deviation terms compensate truncation so that the exact recurrence can be recovered as r_k = rhat_k plus a sum of Chebyshev polynomials applied to deviation vectors.

What would settle it

Take a graph with a small bottleneck, such as two large cliques joined by a single edge, form the random-walk matrix P, and compute the induced $\ell^1$ norm of T_k(P) for k up to a few hundred; if the norm exceeds a small universal constant or grows with k, Assumption 1 fails and the paper's O($K^{2}$/epsilon_a) runtime bound for ChebyPush loses its proof.

Watch

Extended reading notes

Core claim

The paper's central claim is that graph propagation vectors y = f(P) e_s are better computed by expanding f in Chebyshev polynomials than in Taylor monomials. For single-source personalized PageRank it derives the exact expansion with coefficients gamma and beta, and for heat kernel PageRank the expansion with modified Bessel coefficients. Truncating these series at K on the order of one over the square root of alpha times a log factor for SSPPR, and at K on the order of the square root of t times a log factor for HKPR, gives squared-error below epsilon, whereas Taylor truncation needs N roughly equal to K squared. The paper then turns this expansion into two algorithms: ChebyPower, a global power iteration over the three-term Chebyshev recurrence, and ChebyPush, a local push-style algorithm built on a subset Chebyshev recurrence, and claims ChebyPush reaches degree-normalized error epsilon_a in time on the order of the minimum of K squared over epsilon_a and K times m.

Load-bearing premise

ChebyPush's per-iteration cost bound rests on Assumption 1, which says the $\ell^1$ norm of every Chebyshev polynomial T_k(P) stays below a universal constant; on graphs with strong degree heterogeneity that norm could grow with k, and then the advertised O($K^{2}$/epsilon_a) runtime does not follow.

Editorial extensions

If this is right

  • For single-source personalized PageRank, the Chebyshev truncation step K = O(alpha^{-1/2} times log(1/epsilon)) replaces the Taylor step N = O(alpha^{-1} times log(1/epsilon)), cutting global power-iteration cost from O(Nm) to O(Km).
  • For heat kernel PageRank with large t, Taylor expansion needs about 2t log(1/epsilon) terms while the Chebyshev expansion needs about the square root of t times log(1/epsilon) terms, giving roughly a square-root-of-t speedup.
  • ChebyPush is a local algorithm whose runtime is independent of the full graph size for fixed accuracy, and the experiments report that it is 3 to 8 times faster than state-of-the-art baselines on five large real-world graphs.
  • ChebyPush can replace the push phase inside bidirectional randomized algorithms for SSPPR, and the paper claims this reduces the push-phase cost by a factor of about 1 over the square root of alpha compared with prior bidirectional methods.
  • The expansion extends to general graph propagation matrices f(D^{-a} A D^{-b}), so the algorithms apply beyond PageRank and heat kernel to propagation schemes used in graph neural networks.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Extending the paper's recipe to other propagation functions, such as Katz centrality or regularized Laplacian filters, is natural if their Chebyshev coefficients can be written in closed form; the same square-root-like saving should transfer whenever the coefficients decay geometrically.
  • The subset Chebyshev recurrence is a generic local executor for three-term recurrences, and porting the deviation-compensation step to Lanczos-style iterations or graph signal filters would be a testable new use beyond graph propagation.
  • A direct numerical check of the stability assumption on degree-heterogeneous graphs would show whether the O(K^2/epsilon_a) worst-case bound holds beyond the graphs tested; if the assumption fails, replacing the l1 control by a weighted spectral bound would be a natural repair.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. This paper proposes two algorithms for graph propagation (GP) computation on undirected graphs: ChebyPower, a global power-iteration method based on a Chebyshev expansion of the GP function, and ChebyPush, a local push-style algorithm built on a newly introduced subset Chebyshev recurrence. The authors derive closed-form Chebyshev coefficients for personalized PageRank and heat kernel PageRank, prove an O(sqrt(N)) reduction in truncation degree for ChebyPower, and claim for ChebyPush a degree-normalized error guarantee with a graph-size-independent running time of O(min{K^2/epsilon_a, Km}). The paper also presents a bidirectional extension, a generalization to matrix propagation, and experiments on five large real-world graphs.

Significance. If the theoretical claims were valid, the paper would make a substantial contribution: ChebyPower's acceleration is practically useful, and ChebyPush would be the first local push-style algorithm with Chebyshev acceleration and a provable degree-normalized error guarantee for general GP functions. The closed-form Chebyshev coefficients in Lemmas 3.3 and 3.4 are original, and the subset Chebyshev recurrence idea is interesting. The ChebyPower analysis (Lemmas 3.2-3.5 and Theorems 3.6-3.7) appears sound, relying on standard spectral properties of the random-walk matrix. The experimental study is extensive and well-executed. However, the theoretical core of ChebyPush is not established: the proof of Lemma 4.4 contains an invalid inequality, the proof of Theorem 4.5 has a norm mismatch and an inconsistent use of the stability assumption, and Assumption 1 itself is only justified heuristically. Because the local-complexity claim is exactly what separates ChebyPush from a straightforward global method, the paper's central advertised contribution is currently unproven.

major comments (4)
  1. [Section 4.3, Lemma 4.4] The proof claims that sum_{u in S_k} epsilon_k d_u <= sum_{u in S_k} hat_r_k(u)^2 follows from the threshold condition |hat_r_k(u)| > epsilon_k d_u, but this implication is invalid: the threshold only gives epsilon_k d_u < |hat_r_k(u)|, which does not imply epsilon_k d_u <= hat_r_k(u)^2 when |hat_r_k(u)| < 1. Since the pushed residual values can be much smaller than 1 in magnitude, the inequality fails, and the conclusion vol(S_k) <= O(1/epsilon_k) is not established. This is the load-bearing step for the claimed O(K^2/epsilon_a) local running time of ChebyPush in Theorem 4.5.
  2. [Section 4.3, Assumption 1 and Lemma 4.4] Assumption 1, namely ||T_k(P^T)||_infinity = ||T_k(P)||_1 <= C for all k, is not proved; the heuristic explanation that a truncation step does not perturb the output much is not a mathematical argument, and the spectral bound ||T_k(P)||_2 <= 1 does not control the 1-norm (for example, on an n-node star graph, ||T_2(P)||_1 = (3n-7)/(n-1), which approaches 3, so the assumption is nontrivial). Even if Assumption 1 held, the inference in Lemma 4.4 that ||hat_r_k||_1 <= O(1) by taking epsilon_l < 1/K is unjustified: ||sum_l T_{k-l}(P) delta_l||_1 <= C sum_l ||delta_l||_1, and ||delta_l||_1 <= epsilon_l vol(V - S_l), which depends on the graph size m. The proof does not bound vol(V - S_l). Thus the l1 bound on hat_r_k is not derived, and the graph-size-independent time bound of ChebyPush is not proven.
  3. [Section 4.3, Theorem 4.5, Eq. (20)] There is a norm mismatch in the error proof: the derivation bounds ||D^{-1/2}(tilde_y - hat_y)||_infinity, but the theorem requires the degree-normalized error ||D^{-1}(y - hat_y)||_infinity. The text does not supply the step that connects these two norms. In addition, the proof states 'by the assumption that ||T_k(P^T)||_infinity <= 1', whereas Assumption 1 only gives <= C for a universal constant; if C is not 1, the claimed epsilon_a error bound does not follow as written. These are concrete gaps in the error analysis of ChebyPush.
  4. [Section 4.3, Theorem 4.5 proof] The justification of the O(Km) alternative in the min{...} complexity bound is incorrect: the sentence 'when we set epsilon_a = 0, ChebyPush is equivalent to ChebyPower' does not hold, because with threshold zero the subset recurrence still only pushes nonzeros of r_cur, while the exact Chebyshev recurrence can produce nonzero entries where the subset recurrence has zeros (due to the -r_{k-1} term). The O(Km) bound should instead be justified by the trivial per-iteration bound vol(S_k) <= m; as written, the min{...} complexity is not derived.
minor comments (5)
  1. [Section 3.2, Lemma 3.5 (HKPR)] The proof for HKPR only cites the asymptotic e^{-t} I_n(t) ~ 1/sqrt(2*pi*t) for n << t; the needed tail bound sum_{n>K} e^{-t} I_n(t) < epsilon is not derived, so the claimed truncation step K = O(sqrt(t) log(1/epsilon)) should be justified with a reference or a short argument.
  2. [Section 4.3, Theorem 4.5] The theorem proof uses 'the assumption that ||T_k(P^T)||_infinity <= 1', which is inconsistent with Assumption 1's statement ||T_k(P^T)||_infinity <= C; the constant should be carried through the bound or the assumption should be restated with C = 1.
  3. [Section 4.3, Algorithm 4] The threshold formula epsilon_k = (1 / sum_{l=k}^K |c_l|) * epsilon_a / (4K) appears only in the pseudocode; the main text of Section 4.3 should state it explicitly before Lemma 4.4, since Lemma 4.4 is written for a generic epsilon_k and the proof of Theorem 4.5 relies on the specific formula.
  4. [Section 5.2, Lemma 5.3] Lemma 5.3 states that ChebyPush is invoked with threshold epsilon_a^2, but Algorithm 4's threshold is named epsilon_a and its error bound refers to epsilon_a; this notational mismatch should be clarified.
  5. [Section 4.2, Algorithm 4] Line 10 of Algorithm 4 is missing a semicolon after r_cur(u) <- -r_cur(u); the pseudocode should be formatted consistently.

Circularity Check

0 steps flagged · score 1.0 of 10

No material circularity: Chebyshev coefficients are derived in closed form and the only self-citation (the authors' full version for the HKPR proof) is not load-bearing; the Assumption 1 / Lemma 4.4 issues are correctness concerns, not circularity.

full rationale

The paper's derivation chain is self-contained and not circular. The central objects are the Chebyshev expansion coefficients, which are obtained in closed form: Lemma 3.3 evaluates the PageRank coefficient integrals explicitly to obtain gamma and beta, and Lemma 3.4 reduces the HKPR coefficients to the standard integral representation of modified Bessel functions, with the integral form stated in the paper even though the full algebra is deferred to the authors' own full version [48]. That deferral is a minor self-citation but is not load-bearing: the claimed identity is a standard Bessel integral and is independently checkable. The convergence claims in Lemma 3.5 follow from Property 1 and the closed-form coefficient bounds, not from a fitted parameter or a renamed known result. ChebyPush's error and complexity analysis introduces Assumption 1, a stability assumption on ||T_k(P^T)||_infinity, and Lemma 4.4 contains an inequality that does not follow from the threshold condition; these are potential correctness gaps and are properly flagged as such, but they are not instances where a prediction reduces to its input by construction. No parameter is fitted to data and then reported as a prediction, and no load-bearing claim is justified solely by a self-citation chain. The paper is therefore essentially non-circular, with only the routine, non-load-bearing reliance on the authors' full version for a deferred proof.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central ChebyPush analysis assumes two things not established from standard theory: a universal l1 stability bound for Chebyshev polynomials of the random walk matrix, and the ability to bound residual l1 mass by choosing small thresholds. Neither is proven, and the proof of Lemma 4.4 contains an additional algebraic slip. No free parameters are fitted and no new entities are postulated.

assumptions (4)
  • ad hoc to paper Assumption 1 (stability): ||T_k(P^T)||_infinity = ||T_k(P)||_1 <= C for a universal constant C for all k.
    Introduced in Section 4.3 to bound vol(S_k); not derived from spectral properties and likely false for some graphs.
  • standard math The random walk matrix P of an undirected graph has eigenvalues in [-1,1] and is similar to the symmetric normalized adjacency matrix.
    Used in Lemma 3.2 and Property 1; standard spectral graph theory.
  • standard math Chebyshev expansion of f on [-1,1] converges and equals f for the GP functions considered.
    Uses Weierstrass approximation and analyticity of the SSPPR and HKPR functions; standard approximation theory.
  • ad hoc to paper Setting epsilon_l < 1/K implies ||hat_r_k||_1 <= O(1) in Lemma 4.4.
    No proof is given; the l1 mass of residual vectors in the subset recurrence is not obviously bounded by a constant independent of n and k.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Scaling Up Graph Propagation Computation on Large Graphs: A Local Chebyshev Approximation Approach." pith.science (2026). https://pith.science/paper/J76UBAYO

@misc{pith2026241210789,
  author       = {Pith},
  title        = {Pith review of: Scaling Up Graph Propagation Computation on Large Graphs: A Local Chebyshev Approximation Approach},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/J76UBAYO}},
  note         = {Machine review of arXiv:2412.10789}
}
abstract

Graph propagation (GP) computation plays a crucial role in graph data analysis, supporting various applications such as graph node similarity queries, graph node ranking, graph clustering, and graph neural networks. Existing methods, mainly relying on power iteration or push computation frameworks, often face challenges with slow convergence rates when applied to large-scale graphs. To address this issue, we propose a novel and powerful approach that accelerates power iteration and push methods using Chebyshev polynomials. Specifically, we first present a novel Chebyshev expansion formula for general GP functions, offering a new perspective on GP computation and achieving accelerated convergence. Building on these theoretical insights, we develop a novel Chebyshev power iteration method (\ltwocheb) and a novel Chebyshev push method (\chebpush). Our \ltwocheb method demonstrates an approximate acceleration of $O(\sqrt{N})$ compared to existing power iteration techniques for both personalized PageRank and heat kernel PageRank computations, which are well-studied GP problems. For \chebpush, we propose an innovative subset Chebyshev recurrence technique, enabling the design of a push-style local algorithm with provable error guarantee and reduced time complexity compared to existing push methods. We conduct extensive experiments using 5 large real-world datasets to evaluate our proposed algorithms, demonstrating their superior efficiency compared to state-of-the-art approaches.

Figures

Figures reproduced from arXiv: 2412.10789 by the authors.

Figure 1
Figure 1. Illustration of the deviation propagation [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Illustration of ChebyPush to compute 𝑇3 (P)e𝑣1 [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. The difference between Push v.s. ChebyPush after the push operation, we have r𝑐𝑢𝑟 = [0, − 1 3 , − 2 3 , − 2 3 ] and r𝑛𝑒𝑤 = [ 5 3 , 0, 0, 0]. Then, we swap r𝑐𝑢𝑟 and r𝑛𝑒𝑤, and turn to the next iteration 𝑘 = 3. Thus, r𝑐𝑢𝑟 = [ 5 3 , 0, 0, 0] is rˆ3 obtained by the subset Chebyshev recurrence, which is an approximation of r3 = 𝑇3 (P)e𝑣1 . Note that the exact value is 𝑇3 (P)e𝑣1 = [1, 0, 0, 0], suggesting that ChebyPush ob… view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: Query time of different SSPPR algorithms under 𝑙1-error. The lower (resp., upper) bar of each figure represents the query time of each algorithm to reach low-precision (resp., high-precision) 𝑙1-error. (a) Dblp (b) Youtube (c) LiveJournal (d) Orkut (e) Friendster [PIT…
Figure 5
Figure 5. Figure 5: Query time of different SSPPR algorithms under Normalized RelErr. The lower (resp., upper) bar of each figure represents the query time of each algorithm to reach low-precision (resp., high-precision) Normalized RelErr. (a) Dblp (b) LiveJournal [PITH_FULL_IMAGE:figure…
Figure 6
Figure 6. Figure 6: Comparison of various bidirectional methods [PITH_FULL_IMAGE:figures/full_fig_p012_6.png]
Figure 7
Figure 7. Figure 7: Query time of different HKPR algorithms under 𝑙1-error. The lower (resp., upper) bar of each figure represents the query time of each algorithm to reach low-precision (resp., high-precision) 𝑙1-error. (a) Dblp (b) Youtube (c) LiveJournal (d) Orkut (e) Friendster [PITH…
Figure 8
Figure 8. Figure 8: Query time of different HKPR algorithms under Normalized RelErr. The lower (resp., upper) bar of each figure represents the query time of each algorithm to reach low-precision (resp., high-precision) Normalized RelErr. (a) Dblp,𝛼 = 0.2,𝑡 = 5 (b) Dblp,𝛼 = 0.02,𝑡 = 20 (c…
Figure 9
Figure 9. Figure 9: Query time distribution for our ChebyPower and ChebyPush algorithms in computing SSPPR and HKPR vectors. Pw − PRU and Pw − HkU denote ChebyPower selecting source nodes uniformly for SSPPR and HKPR, respectively. Pw − PRH and Pw − HkH represent ChebyPower selecting sour…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

49 extracted references · 45 canonical work pages

  1. [1]

    Local graph partitioning using pagerank vectors

    Reid Andersen, Fan Chung, and Kevin Lang. Local graph partitioning using pagerank vectors. In FOCS, 2006

    work page 2006

  2. [2]

    A local updating algorithm for personal- ized pagerank via chebyshev polynomials

    Esteban Bautista and Matthieu Latapy. A local updating algorithm for personal- ized pagerank via chebyshev polynomials. Social Network Analysis and Mining , 12(1), 2022

    work page 2022

  3. [3]

    Scaling graph neural networks with approximate pagerank

    Aleksandar Bojchevski, 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 KDD, 2020

    work page 2020

  4. [4]

    Is pagerank all you need for scalable graph neural networks

    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 KDD, 2019

    work page 2019

  5. [5]

    Sublinear time spectral density estimation

    Vladimir Braverman, Aditya Krishnan, and Christopher Musco. Sublinear time spectral density estimation. In STOC, 2022

    work page 2022

  6. [6]

    Accel- erating personalized pagerank vector computation

    Zhen Chen, Xingzhi Guo, Baojian Zhou, Deqing Yang, and Steven Skiena. Accel- erating personalized pagerank vector computation. In KDD, 2023

    work page 2023

  7. [7]

    The heat kernel as the pagerank of a graph

    Fan Chung. The heat kernel as the pagerank of a graph. Proceedings of the National Academy of Sciences , 104(50), 2007

    work page 2007

  8. [8]

    Concentration inequalities and martingale inequali- ties: a survey

    Fan Chung and Linyuan Lu. Concentration inequalities and martingale inequali- ties: a survey. Internet mathematics, 3(1), 2006

    work page 2006

Show all 49 references
  1. [9]

    Computing heat kernel pagerank and a local clustering algorithm

    Fan Chung and Olivia Simpson. Computing heat kernel pagerank and a local clustering algorithm. European Journal of Combinatorics , 68, 2018

    2018

  2. [10]

    A note on the summation of chebyshev series.Mathematics of Computation, 9(51), 1955

    Charles W Clenshaw. A note on the summation of chebyshev series.Mathematics of Computation, 9(51), 1955

    1955

  3. [11]

    Efficient processing of network proximity queries via chebyshev acceleration

    Mustafa Coskun, Ananth Grama, and Mehmet Koyuturk. Efficient processing of network proximity queries via chebyshev acceleration. In KDD, 2016

    2016

  4. [12]

    Indexed fast network proximity querying

    Mustafa Coşkun, Ananth Grama, and Mehmet Koyutürk. Indexed fast network proximity querying. Proceedings of the VLDB Endowment , 11(8), 2018

    2018

  5. [13]

    Convolutional neural networks on graphs with fast localized spectral filtering

    Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems , 2016

    2016

  6. [14]

    Pagerank for ranking authors in co-citation networks

    Ying Ding, Erjia Yan, Arthur Frazho, and James Caverlee. Pagerank for ranking authors in co-citation networks. Journal of the American Society for Information Science and Technology, 60(11), 2009

    2009

  7. [15]

    Predict then propagate: Graph neural networks meet personalized pagerank

    Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05997, 2018

    2018 arXiv

  8. [16]

    Diffusion improves graph learning

    Johannes Gasteiger, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. NeurIPS, 2019

    2019

  9. [17]

    Golub and Charles F

    Gene H. Golub and Charles F. Van Loan. Matrix Computations, Third Edition . Johns Hopkins University Press, 1996

    1996

  10. [18]

    Subset node representation learning over large dynamic graphs

    Xingzhi Guo, Baojian Zhou, and Steven Skiena. Subset node representation learning over large dynamic graphs. In KDD, 2021

    2021

  11. [19]

    Convolutional neural networks on graphs with chebyshev approximation, revisited

    Mingguo He, Zhewei Wei, and Ji-Rong Wen. Convolutional neural networks on graphs with chebyshev approximation, revisited. Advances in neural information processing systems, 2022

    2022

  12. [20]

    CCSS: towards conductance-based community search with size constraints

    Yue He, Longlong Lin, Pingpeng Yuan, Ronghua Li, Tao Jia, and Zeli Wang. CCSS: towards conductance-based community search with size constraints. Expert Syst. Appl., 250, 2024

    2024

  13. [21]

    Heat kernel based community detection

    Kyle Kloster and David F Gleich. Heat kernel based community detection. In KDD, 2014

    2014

  14. [22]

    Efficient personalized pagerank computation: The power of variance-reduced monte carlo approaches

    Meihao Liao, Rong-Hua Li, Qiangqiang Dai, Hongyang Chen, Hongchao Qin, and Guoren Wang. Efficient personalized pagerank computation: The power of variance-reduced monte carlo approaches. Proc. ACM Manag. Data, 1(2):160:1– 160:26, 2023

    2023

  15. [23]

    Efficient person- alized pagerank computation: A spanning forests sampling based approach

    Meihao Liao, Rong-Hua Li, Qiangqiang Dai, and Guoren Wang. Efficient person- alized pagerank computation: A spanning forests sampling based approach. In SIGMOD, 2022

    2022

  16. [24]

    Index- free approach with theoretical guarantee for efficient random walk with restart query

    Dandan Lin, Raymond Chi-Wing Wong, Min Xie, and Victor Junqiu Wei. Index- free approach with theoretical guarantee for efficient random walk with restart query. In ICDE. IEEE, 2020

    2020

  17. [25]

    Scalable and effective conductance-based graph clustering

    Longlong Lin, Ronghua Li, and Tao Jia. Scalable and effective conductance-based graph clustering. In AAAI, 2023

    2023

  18. [26]

    QTCS: efficient query-centered temporal community search

    Longlong Lin, Pingpeng Yuan, Rong-Hua Li, Chun-Xue Zhu, Hongchao Qin, Hai Jin, and Tao Jia. QTCS: efficient query-centered temporal community search. Proc. VLDB Endow., 17(6), 2024

    2024

  19. [27]

    Personalized pagerank estimation and search: A bidirectional approach

    Peter Lofgren, Siddhartha Banerjee, and Ashish Goel. Personalized pagerank estimation and search: A bidirectional approach. In WSDM, 2016

    2016

  20. [28]

    Personalized pagerank to a target node

    Peter Lofgren and Ashish Goel. Personalized pagerank to a target node. arXiv preprint arXiv:1304.4658, 2013

    2013 arXiv

  21. [29]

    Chebyshev polynomials

    John C Mason and David C Handscomb. Chebyshev polynomials. Chapman and Hall/CRC, 2002

    2002

  22. [30]

    Stability of the lanczos method for matrix function approximation

    Cameron Musco, Christopher Musco, and Aaron Sidford. Stability of the lanczos method for matrix function approximation. In SODA. SIAM, 2018

    2018

  23. [31]

    Bessel functions., 2010

    Frank WJ Olver and Leonard C Maximon. Bessel functions., 2010

    2010

  24. [32]

    The pagerank citation ranking: Bringing order to the web

    Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford infolab, 1999

    1999

  25. [33]

    Faster algorithms via approximation theory

    Sushant Sachdeva, Nisheeth K Vishnoi, et al. Faster algorithms via approximation theory. Foundations and Trends® in Theoretical Computer Science , 9(2), 2014

    2014

  26. [34]

    Chebyshev polyno- mial approximation for distributed signal processing

    David I Shuman, Pierre Vandergheynst, and Pascal Frossard. Chebyshev polyno- mial approximation for distributed signal processing. In DCOSS. IEEE, 2011

    2011

  27. [35]

    Distributed signal processing via chebyshev polynomial approximation

    David I Shuman, Pierre Vandergheynst, Daniel Kressner, and Pascal Frossard. Distributed signal processing via chebyshev polynomial approximation. IEEE Transactions on Signal and Information Processing over Networks , 4(4), 2018

    2018

  28. [36]

    Verse: Versatile graph embeddings from similarity measures

    Anton Tsitsulin, Davide Mottin, Panagiotis Karras, and Emmanuel Müller. Verse: Versatile graph embeddings from similarity measures. In WWW, 2018

    2018

  29. [37]

    Approximate graph propagation

    Hanzhi Wang, Mingguo He, Zhewei Wei, Sibo Wang, Ye Yuan, Xiaoyong Du, and Ji-Rong Wen. Approximate graph propagation. In KDD, 2021

    2021

  30. [38]

    Estimating single-node pagerank in o (mindt,√𝑚) time

    Hanzhi Wang and Zhewei Wei. Estimating single-node pagerank in o (mindt,√𝑚) time. Proc. VLDB Endow., 2023

    2023

  31. [39]

    Per- sonalized pagerank to a target node, revisited

    Hanzhi Wang, Zhewei Wei, Junhao Gan, Sibo Wang, and Zengfeng Huang. Per- sonalized pagerank to a target node, revisited. In KDD, 2020

    2020

  32. [40]

    Edge-based local push for personalized pagerank

    Hanzhi Wang, Zhewei Wei, Junhao Gan, Ye Yuan, Xiaoyong Du, and Ji-Rong Wen. Edge-based local push for personalized pagerank. arXiv preprint arXiv:2203.07937, 2022

    2022 arXiv

  33. [41]

    Fora: simple and effective approximate single-source personalized pagerank

    Sibo Wang, Renchi Yang, Xiaokui Xiao, Zhewei Wei, and Yin Yang. Fora: simple and effective approximate single-source personalized pagerank. In KDD, pages 505–514, 2017

    2017

  34. [42]

    Topppr: top-k personalized pagerank queries with precision guarantees on large graphs

    Zhewei Wei, Xiaodong He, Xiaokui Xiao, Sibo Wang, Shuo Shang, and Ji-Rong Wen. Topppr: top-k personalized pagerank queries with precision guarantees on large graphs. In SIGMOD, 2018

    2018

  35. [43]

    Approximating single-source person- alized pagerank with absolute error guarantees

    Zhewei Wei, Ji-Rong Wen, and Mingji Yang. Approximating single-source person- alized pagerank with absolute error guarantees. arXiv preprint arXiv:2401.01019, 2024

    2024 arXiv

  36. [44]

    Simplifying graph convolutional networks

    Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In ICML, 2019

    2019

  37. [45]

    Unifying the global and local approaches: an efficient power iteration with forward push

    Hao Wu, Junhao Gan, Zhewei Wei, and Rui Zhang. Unifying the global and local approaches: an efficient power iteration with forward push. In SIGMOD, 2021

    2021

  38. [46]

    Efficient algorithms for personalized pagerank computation: A survey

    Mingji Yang, Hanzhi Wang, Zhewei Wei, Sibo Wang, and Ji-Rong Wen. Efficient algorithms for personalized pagerank computation: A survey. IEEE Transactions on Knowledge and Data Engineering , 2024

    2024

  39. [47]

    Efficient estimation of heat kernel pagerank for local clustering

    Renchi Yang, Xiaokui Xiao, Zhewei Wei, Sourav S Bhowmick, Jun Zhao, and Rong-Hua Li. Efficient estimation of heat kernel pagerank for local clustering. In SIGMOD, 2019

    2019

  40. [48]

    Chebyshev meets push: Efficient and provable graph propagation computation

    Yichun Yang, Rong-Hua Li, Meihao Liao, Longlong Lin, and Guoren Wang. Chebyshev meets push: Efficient and provable graph propagation computation. https://anonymous.4open.science/r/ChebyPush-2E94, 2024

    2024

  41. [49]

    GSD-GNN: generalizable and scalable algorithms for decoupled graph neural networks

    Yunfeng Yu, Longlong Lin, Qiyu Liu, Zeli Wang, Xi Ou, and Tao Jia. GSD-GNN: generalizable and scalable algorithms for decoupled graph neural networks. In ICMR, 2024

    2024

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.