Accelerated Evolving Set Processes for Local PageRank Computation

Q1. If one compares with $O(1/(\alpha\epsilon))$ from APPR where are the wins and losses? How does the $\epsilon^2$ in the proposed method here affect performance compared to APPR and other methods with just $\epsilon$ involved?

A1. Thank you for raising this important question regarding the trade-offs in our theoretical guarantees.

1. Practical Impact of $\epsilon$: In PPR approximation, the precision parameter $\epsilon$ is typically not set too small, as an excessively tight tolerance would cause local push-based methods (e.g., APPR) to degenerate into global algorithms due to an overgrown active set. Thus, in practice, optimizing the dependence on $\alpha$ is often more critical than the $\epsilon$-dependence.

2. Trade-off Between $\alpha$ and $\epsilon$: As discussed in Martínez-Rubio et al. [1], our bound reflects a fundamental trade-off: while we improve the condition number dependence to $O(1/\sqrt{\alpha})$, this comes at the cost of a looser $O(1/\epsilon^2)$ dependence on sparsity. This aligns with existing conjectures about such trade-offs in iterative methods. Whether a tighter $\epsilon$-dependence (e.g., $O(1/\epsilon)$) can be achieved without sacrificing the gains in $\alpha$ remains an open question, and we intend to explore this direction in future work.

[1] Martínez-Rubio, David, Elias Wirth, and Sebastian Pokutta. "Accelerated and sparse algorithms for approximate personalized PageRank and beyond." The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.

Q2. How does the $R$ in the complexity scale with dumping factor $\alpha$?

A2. We sincerely appreciate the reviewer's insightful comments regarding the scaling behavior of $R$ with respect to the damping factor $\alpha$. To address these concerns, we have conducted additional experiments (see table below) examining $R$ across both small $\alpha$ values and values approaching 0.5, using the com-dblp graph (with $\epsilon=1e-8$; results are similar for other graphs). Our findings demonstrate that: (1) for $0.01 \leq \alpha < 0.5$, $R$ remains consistently at 1, indicating our algorithm's robustness for larger $\alpha$ values; (2) when $\alpha < 0.01$, $R$ exhibits a gradual increase with decreasing $\alpha$, but crucially this growth follows a logarithmic scaling of $\log(1/\alpha)$ - substantially milder than the $1/\alpha$ dependence. These empirical results validate the reasonableness of our treatment of $R$ in the complexity analysis while providing a more comprehensive characterization of its behavior across the full range of $\alpha$ values.

Q3. How does the method perform against other methods from the literature e.g. Ref.[37] ?

A3. Thank you for this important question regarding comparative performance. Regarding the comparison with Ref.[37]'s ASPR algorithm, we have included experimental comparisons in Appendix C.3 (Figure 6) due to space constraints in the main text. It should be noted that while ASPR maintains the desirable property of guaranteed monotonic decrease in the gradient's $\ell_1$-norm, this advantage comes at the cost of requiring progressively more iterative points, which ultimately leads to reduced computational efficiency compared to our proposed method. The detailed comparative results demonstrate this trade-off between theoretical guarantees and practical performance.

Thank you for the detailed response. The authors have made a good effort in answering my main concerns, especially the scaling of R with respect to a, and the effect of epsilon^2. I will keep my score 4, for the following reasons.

Given the dependence of R on alpha<0.01 this should somehow be visible in the complexity expression. Strictly speaking R is not a global constant but a function of alpha, and this behavior is not sufficient to be shown empirically on some datasets. How do we know how the R will behave in other datasets? Also, why is the change of monotonicity from 0.01 and lower? Where does this come from? Why not 0.012 or 0.005?

Furthermore, the authors answer about the tradeoff in complexity that "while we improve the condition number dependence to O(1/sqrt(alpha)), this comes at the cost of a looser dependence on sparsity O(1/epsilon^2), following existing conjectures from the literature. However, this is exactly the point that leaves questions about the importance of the paper and the current method, because aiming to improve the complexity over the alpha parameter, another aspect of the algorithm gets worse. The paper does not answer the question, can we get better without worsening another aspect or have we reached the limits?

Finally, regarding comparison with Ref.[37] I appreciate the inclusion of the experimental comparison in the Appendix, but this algorithm has already guaranteed the monotonic decrease in the gradient's norm, something that you have also claimed in your paper. I would have expected a more direct comparison against this algorithm in the main body of the paper, something which should also justify the importance of your own contribution in performance, i.e. what is actually new in the performance of the method you propose. These comments do not mean that I have not appreciated the contribution of the paper, this is why I keep the Borderline accept.

Q1. The concern about the clarity of proposed AESP Framework

A1. We appreciate this constructive suggestion and will add an illustrative figure to enhance the clarity of the AESP framework. The figure will demonstrate: (1) a simple graph with several nodes including the source node; (2) the first inner loop's local method (locGD or APPR) iterations, where the initial active set $\mathcal{S}_1^{(0)}$ contains only the source node, with subsequent iterations showing $\mathcal{S}_1^{(t)}$ first expanding then contracting; (3) the second inner loop recomputing the initial active set $\mathcal{S}_2^{(0)}$ based on the previous solution, where the shrinking tolerance $\epsilon_k$ leads to progressively larger active sets. Hope this will effectively demonstrate the dynamic evolution of active sets throughout the iterative process.

Q2. On the Robustness of the experimental evaluation

A2. We appreciate the reviewer's valuable feedback regarding baseline selection. Our choice of baseline methods was motivated by several key considerations: (1) Since AESP's inner loop employs either locGD or APPR, we directly compared against these fundamental methods to demonstrate the acceleration benefits; (2) We have indeed included comparisons with recent methods ASPR[1] (2023), LocCH[2] (2024) and maintained FISTA[3] (2009) as it remains a relevant benchmark, with these results presented in Appendix C.3 (Figures 6-7) due to space constraints; (3) The results clearly show AESP's superior early-stage convergence with rapid error reduction;

[1] Martínez-Rubio, David, Elias Wirth, and Sebastian Pokutta. "Accelerated and sparse algorithms for approximate personalized PageRank and beyond." The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.

[2] Zhou, Baojian, et al. "Iterative methods via locally evolving set process." Advances in Neural Information Processing Systems 37 (2024): 141528-141586.

[3] Beck, Amir, and Marc Teboulle. "A fast iterative shrinkage-thresholding algorithm for linear inverse problems." SIAM journal on imaging sciences 2.1 (2009): 183-202.

Q3. On the characterization of early-stage convergence

A3. We sincerely appreciate this insightful question regarding AESP's convergence behavior. Our analysis reveals that while AESP demonstrates significant early-stage convergence advantages, its time complexity does increase during updates as $\epsilon_t$ decreases. We conducted new experiments on the ogbn-arxiv dataset ($\alpha=0.1$, a random source node, different $\epsilon$ values range from $10^{-6}$ to $10^{-10}$). We found that, when AESP maintains a constant condition number for subproblems, its convergence rate in later stages becomes less pronounced compared to non-accelerated methods like APPR-Opt. This occurs because the subproblem precision $\epsilon_t$ eventually becomes smaller than the original problem's precision requirement. However, we emphasize that our outer loop incorporates an early-stopping mechanism (Algorithm 1, Line 7), which ensures comparable total operations between methods. Thus, while AESP's advantage becomes less pronounced at extremely small $\epsilon$ (the locality is not significant, so all local methods do not have any advantages) values, it maintains overall operational efficiency comparable to baseline methods throughout the convergence process. Whether one can optimize/accelerate the convergence of the later stage is an interesting problem to explore.

W1. Concern about the tradeoff between the sparsity (related with $\epsilon$) and the condition number (related with $\alpha$)

A1. We appreciate the reviewer’s insightful comment regarding the tradeoff between $\epsilon$ and the condition number $\alpha$. As discussed in Martínez-Rubio's work (see [1]), the final bound indeed represents a tradeoff between the dependence on the condition number, i.e., $1/\alpha$, and the sparsity, i.e., $1/\epsilon$. Specifically, while the condition number dependence scales as $1/\sqrt{\alpha}$, the sparsity dependence increases to $1/\epsilon^2$, which aligns with the conjecture and discussion in their work. Exploring whether a tighter dependence on $\epsilon$ can be achieved remains an interesting direction for future research, and we plan to investigate this further in our subsequent work.

[1] Martínez-Rubio, David, Elias Wirth, and Sebastian Pokutta. "Accelerated and sparse algorithms for approximate personalized PageRank and beyond." The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.

W2. The concern of the presentation in our abstract and introduction.

A2. We appreciate the reviewer's valuable suggestions for improving the clarity of our presentation. We acknowledge these points (e.g., approximation error definition, $\epsilon$-approximation, etc.) and will revise the paper to more intuitively and clearly present our results before introducing the problem formulation.

W1. The concern of the assumption on a constant $R$ may not hold.

A1. We appreciate the reviewer's insightful observation regarding the assumption of a constant $R$. As we discussed in line 248, we have provided explanations concerning this assumption. Overall, our experimental results demonstrate that: 1). $R$ does not exhibit any significant trend with respect to variations in graph size; 2). The increase of $R$ with decreasing $\alpha$ shows a relatively gradual trend. Based on our comprehensive experiments, we found that $R$ generally maintains a magnitude on the order of $\log(1/\alpha)$. These observations support the constant $R$ is a relatively small constant parameter in our analysis.

Q1. How do the proposed methods compare to the sampling-based PPR estimation algorithms (e.g., FORA [KDD'2017]) in empirical efficiency?

A1. Thank you for your question. We appreciate the opportunity to clarify the comparison with FORA [KDD'2017]. 1) Implementation Differences: FORA is implemented in C++, while our method is implemented in Python with Numba acceleration. This difference in implementation languages and frameworks makes direct runtime comparisons less equitable. 2) Algorithmic Frameworks: FORA combines an approximate PPR (APPR, i.e., Forward Push) step with Monte Carlo random walks to refine the estimation. In contrast, our method (AESP) focuses on computing the full PPR vector for a given source node, rather than pairwise node-to-node probabilities. Thus, the two methods address distinct problem formulations, making operational comparisons less meaningful. 3) Potential Synergy: Empirically, our method demonstrates strong early-stage acceleration, which could potentially improve the Forward Push phase in FORA. This represents a promising direction for future work.

Q2. What is the intuition underlying the proposed methods for the lower time complexity?

A2. We sincerely thank the reviewer for raising this important question about the intuition behind our method's improved time complexity. Our proposed framework is based on the following fact: at each time, we use a faster algorithm for solving a simpler version of the original problem, which has a constant condition number. Combine these solutions together to obtain the approximation of the original problem. These techniques are in the same vein as those in [1]. In optimization, this is the Catalyist framework.

[1] Peng, Richard, and Daniel A. Spielman. "An efficient parallel solver for SDD linear systems." Proceedings of the forty-sixth annual ACM Symposium on Theory of Computing (STOC). 2014.