Faster Local Solvers for Graph Diffusion Equations

Thank you for taking the time and effort to review our paper. We appreciate your positive perspective. We resolve your concerns as follows.

---

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.

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.

---

Q2. Despite improvements, relying on sequential updates in some methods (like LocalSOR) still poses challenges for achieving maximal parallel efficiency.

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.

---

Q3. Comments on the runtime analysis for some proposed methods, such as the Local Chebyshev method.

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.

---

Q4. How does the proposed method handle very large-scale dynamic graphs in real-time applications, and what are the potential bottlenecks?

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.

We are happy to discuss any further concerns you may have.

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:

---

Q1. Can the authors show/provide which local GDE solver achieves better performance on which type(s) of graphs?

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.

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.

---

Q2. Computational complexity/cost is missing.

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.

We are ready and happy to discuss any further concerns you may have.

We are happy that you like our work. We appreciate your time and effort in reviewing our submission. We addressed your concerns as follows:

---

Q1. It is unclear how graph structures, such as sparsity and spectral properties, impact the runtime complexity of the local solvers.

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.

In 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.

---

Q2. Comments on the difficulty of accelerated bound analysis for LocalCH.

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.

---

Q3. When $\epsilon$ is sufficiently small, LocalGD may not speed up the standard counterparts.

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.

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 and training graph neural networks, improving the efficiency of these algorithms. We are happy to have further discussions if needed!

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.

---

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.

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.

More 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.

---

Q2. It is unclear where exactly the speedup reported in Table 2 comes from.

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.

---

Q3. The definition of $\mathcal{S}_t$ in LocalGD and LocalCH is missing.

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.

---

Q4. For the PPR computation, the open problem was recently solved by Martínez-Rubio et al. (2023, COLT)

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.

When 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.

---

Q5. When $\epsilon \rightarrow 0$, do $\boldsymbol{x}^{(t)}$ converge to $\boldsymbol{x}^{*}$?

A: Yes. For PPR using LocalSOR in Theorem 3.3, we proved that the estimate $\boldsymbol{x}^{(T)}$ satisfies $||\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.

---

We hope that our clarifications can address your concerns. We are happy to have further discussions if needed!