Topological Zigzag Spaghetti for Diffusion-based Generation and Prediction on Graphs

We appreciate very much your constructive comments on our paper. Please kindly find our response to your comments below, and all revisions made to the paper are highlighted in red.

$**Q1:**$ The soundness of the paper seems to need a bit of improvement. For instance, notations might need a little more description. ($\omega$ from section 3 and 3.1 seems to be referring to different object). Also, definition of mathematical object can help the understanding of the paper (union of two graphs mentioned). More detailed description of figures and tables can improve the readability.

$**A:**$ Thank you very much for careful reading! Yes, we used $\omega_{.,.}$ with 2 subscripts to denote an edge weight and $\omega_{.}$ with 1 subscript to denote a weight in zigzag spaghetti. We agree that it may be confusing so we have changed the edge weight to $\nu$ in the paper.

On the graph unions, we use the standard graph operation, where the union of graphs is defined by creating a single graph containing all the nodes and edges from both original graphs (Gross et al. (2018) “Graph Theory and Its Applications”, CRC Press; Shiu and Sun (2014) “A First Course in Graph Theory”, HKBU). We have added the respective explanation and the references to the paper.

$**Q2:**$ What is the difference between $G_t$ and $G^t$ in Sec. 3?

$**A:**$ This is an inconsistency on our part, thanks for noticing it! $G_t$ (with subscript) and $G^t$ (with superscript) is the graph observed at point $t$. We have updated the notation in the paper to $G^t$ to denote dependence of graphs on time.

$**Q3:**$ Can you describe how you obtained $w_i$ in Sec. 3.1?

$**A:**$We use here a standard approach of assigning $w_i=1/n$, that is, all time intervals contribute equally (which would correspond to flat priors in Bayesian terms). However, this raises interesting directions of either learning optimal $w_i$ with attention mechanisms or using more refined priors with the Bayesian framework. Thanks very much for initiating these ideas!

$**Q4:**$ How is Sec. 4.1 related to the methodology of your paper?

$**A:**$ The Sec. 4.1 is about the mixed-up graph construction (MGC) which is used to generate a mixed-up graph $\mathcal{G}^t$ based on a sample ${\bf X}_t$ (see Eq. 5) where ${\bf X}_t$ corrupted node feature matrix in the forward process at time step $t$. Then we apply our zigzag spaghetti approach to a mixed-up graph $\mathcal{G}^t$ at time step $t$ and obtain a corresponding zigzag spaghetti-based topological feature which will be used to integrate into the denoising decoder.

$**Q5:**$ Zigzag spaghetti is proposed as computation efficiency, which remains unclear from a theoretical perspective. Please justify this by comparing its time complexity with existing metrics.

$**A:**$ Zigzag spaghetti has two main advantages (not one): first, it allows for capturing essential topological characteristics of a dynamic object over time at $**all resolution scales simultaneously**$, and, second, it is easily tractable and computationally efficient (relative to other time-aware topological summaries). To justify the second point, we present the running time comparison among ZS, ZPI, and ZFC for graph classification on MUTAG. The obtained results suggest that ZS-DM achieves the best performance and also delivers competitive running time (in seconds), relative to other zigzag summaries.

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Data $\hspace{2ex}$ | ZS-DM (ours) $\hspace{8ex}$ | ZPI-DM $\hspace{13ex}$ | ZFC-DM

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

MUTAG | 0.21 sec (91.68$\pm$0.34) | 0.37 sec (90.52$\pm$0.63) | 0.18 sec (90.73$\pm$0.59)

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

In addition, the complexity of zigzag persistence on graphs can be improved for a subclass of graphs satisfying certain assumptions on the size of the unions in the filtration, i.e. of the size of the union of all graphs in the filtration is $\Omega{m^\epsilon}$ for any fixed $\epsilon$, i.e., $0< \epsilon<1$ [1]. However, this is not true for a general class of graphs, and some other more drastic approaches are needed to improve scalability of zigzag persistence on denser graphs. One such potential direction is to compute zigzag persistence based only on landmarks rather than on all nodes and then to use Dowker or witness complexes. This approach has not been yet investigated in computational topology and its theoretical guarantees are yet unknown. We believe though that it’s a very promising approach that can fundamentally shift the scalability problem for ZP.

[1] Dey, T.K. and Hou, T., 2023. Computing Zigzag Vineyard Efficiently Including Expansions and Contractions. arXiv preprint arXiv:2307.07462.

$**Q6:**$ Figure 1 is proposed to illustrate the proposed ZS. I suggest the authors provide the necessary explanations for better clarity.

$**A:**$ For Figure 1, we showcase the forward process of the zigzag spaghetti-aware diffusion model. In more detail, at each time step, we first add noise to the data, i.e., transitioning from ${\bf X}_0$ to ${\bf X}_1$ to ${\bf X}_2$ and so on (in this toy example, we suppose there are overall 5 time steps). After that, we use the mixed-up graph construction (MGC) approach to generate the corresponding new mixed-up graph, and then apply the zigzag spaghetti method over the mixed-up graphs within a specific sliding window (i.e., the dashed gray box) to obtain the corresponding zigzag spaghetti.

We sincerely thank the reviewer for providing valuable feedback. We detail our response below point by point and we also added the respective updates into the paper (see the parts highlighted in red and Appendix E).

$**Q1:**$ Some illustrations for zigzag persistence and zigzag filtration curves in Section 3 can benefit the convey of the content.

$**A:**$ Thank you very much! We agree that this is an important point for conveying the intuition behind zigzag persistence. We have added a new Figure 2 with a toy example on Page 18, Appendix E. We’ll integrate it to the main body of the final version when all other edits/additions/deletions are completed.

From the Figure 2 (c), we observe that although overall there are similarities in curves for all scales, we find that, starting from time 3, the time evolving graphs deliver consistency in terms of topological characteristics of order 1, while there is a notable variability among topological characteristics over the time period from time point 0 to time point 3. Furthermore, another notable topological feature is observed over the time period 1-2, but its lifespan is relatively short.

$**Q2:**$ Some sentences are not precise, e.g., “M is the number of the” in line 162. Actually, M is a set in the paper.

$**A:**$ Thank you! Yes, $\mathcal{M}$ is a set containing the observed $p$-dimensional topological features at a given scale. We have updated it in the paper.

$**Q3:**$ Proposition 3.2 seems to be a simple derivation from proposition 3.2 of Chen et al. (2022). Please further clarify the significance of this proposition. Meanwhile, there exist explicit notation errors in Proposition 3.2 between PDz_alpha_k and PDz’_alpha_k, which should be avoided in the submission.

$**A:**$ We advance the stability result of Chen et al. (2022) by lifting the key restriction of zigzag curve which considers only a $**single**$ user-predefined scale $\alpha_{k}$, to a general case, where we show stability for all scales $\alpha_{1}, \alpha_{2}, …, \alpha_{m}$ simultaneously. This involves moving derivations from a univariate zigzag curve in $\mathbb{R}$ to a multivariate zigzag spaghetti in $\mathbb{R}^m$. Practically, this stability result is of high importance to ensure robustness of zigzag spaghetti and the associated graph learning process with respect to uncertainties at $**all**$ resolution scales $**simultaneously**$. It also allows us to bypass the subjective selection of a single resolution scale $\alpha_{k}$, which is one of the major criticisms of the zigzag persistence for dynamic data (Xian et al, 2022).

Thanks very much for the careful reading! We have fixed the typos in Proposition 3.2, adding the missing $^{\prime}$.

$**Q4:**$ The bootstrap version of ZS is proposed. However, no theoretical analysis of accuracy is provided due to the inherent challenges. I would suggest the authors provide some empirical results or analyses at least.

$**A:**$ In the main body (Table 4 on Page 9), we provided the performance comparison under different bootstrap sample sizes on three graph datasets. We have also conducted additional experiments on COX2 data with bootstrap sample sizes $B \in {10, 20, 50, 100}$ (see Table below).

Similarly to the earlier obtained results (Table 4 on Page 9) and on par with the premise of the resampling methods in the inferential statistics (Efron and Tibshirani, 1993; Hall, 2013), we find that that as the bootstrap sample size increases, the performance of ZS-DM improves and the standard error decreases. This suggests that there likely shall be some theoretical result on asymptotics of bootstrap estimates for ZS-DM, but this is a fundamental question at the intersection of mathematical statistics and DL which we leave for future research.

++++++++++++++++++++++++++++++++++++++++++++++++++++++

# Sim $\hspace{0.2ex}$ | 10 $\hspace{8.5ex}$ | 20 $\hspace{8.2ex}$ | 50 $\hspace{8.2ex}$ | 100

++++++++++++++++++++++++++++++++++++++++++++++++++++++

ZS-DM | 80.35$\pm$1.10 | 80.39$\pm$0.95 | 81.20$\pm$0.90 | 81.73$\pm$0.86

++++++++++++++++++++++++++++++++++++++++++++++++++++++

Thanks very much for your time in reviewing and insightful comments, Reviewer HF5K! We sincerely understand you are busy. Since the discussion due is approaching, would you mind checking our response to confirm whether you have any further questions?

We are looking forward to your reply and happy to answer your further questions.

Thanks very much for the helpful feedback! Below our answers on the proposition and computational complexity.

$**Q7**$: Regarding Q3, this generation from single scale to all scales seems a direct result of the conclusion of Chen et al. (2022).

$**A**$: On the proposition comment, we respectfully disagree with it. The proposition in Chen et al. (2022) considers a univariate case, i.e. $\mathbb{R}$, and we prove the stability for all cells simultaneously, i.e., for a multivariate case of $\mathbb{R}^m$. While clearly our result relies on the univariate result of Chen et al. (2022), the proper mathematical derivation of stability for a multivariate case does not exist, and our proposition offers a formal treatment of the multivariate case under the corresponding norms. The step from a univariate case to a multivariate case, while not highly mathematically involved, requires proper mathematical apparatus from linear algebra and operator theory. Of course, we don't argue in any way that the proof is a breakthrough in pure mathematics but it is important to obtain such formal result, ensuring the stability guarantees of a multivariate case in practice.

$**Q8**$: In the provided experimental results in Q5, the proposed method ZS-DM does not demonstrate an efficiency advantage over baseline.

$**A**$: On computational efficiency vs. performance, to highlight our point, we have added another experiment on PTC_FM. We describe the conclusions based on MUTAG (presented earlier) and PTC_FM (the new experiment) below. The conclusions on the MUTAG and PTC_FM experiments are consistent.

Table 1: Computational efficiency and performance comparison on MUTAG.

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Data $\hspace{2ex}$ | ZS-DM (ours) $\hspace{8ex}$ | ZPI-DM $\hspace{13ex}$ | ZFC-DM

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

MUTAG | 0.21 sec (91.68$\pm$0.34) | 0.37 sec (90.52$\pm$0.63) | 0.18 sec (90.73$\pm$0.59)

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Table 2: Computational efficiency and performance comparison on PTC_FM.

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Data $\hspace{2ex}$ | ZS-DM (ours) $\hspace{8ex}$ | ZPI-DM $\hspace{13ex}$ | ZFC-DM

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

PTC_FM | 0.18 sec (66.76$\pm$0.24) | 0.25 sec (62.47$\pm$0.39) | 0.16 sec (61.86$\pm$0.40)

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

On ZS vs. ZFC, as ZS considers a multivariate case of filtration scales and ZFC considers only a univariate case of a single filtration scale, ZS and ZFC show overall similar costs, with ZFC costs being, as it can be expected, somewhat lower. However, ZS outperforms ZFC in accuracy (with gains of 7.92%) and also $**substantially**$ reduces variability, with gain in std of up to 42%. This phenomenon is not surprising as as ZS considers $**all**$ filtration scales simultaneously.

Now ZS vs. ZPI, ZS outperforms ZPI in computational efficiency up to 43%, in accuracy up to 6.87% and in variability up to 46%.

To summarize:

1. in accuracy ZS is better than ZFC and ZPI;
2. in variability ZS is much better than ZFC and ZPI,
3. in computational costs, ZS is a bit worse than ZFC and is much better than ZPI.

We hope that these experiments are sufficiently convincing to demonstrate the performance and computational advantages of ZS. Thanks a lot again for raising these questions which allow us to better highlight the ZS gains.

Thank you for the in-depth review and your encouraging comments! We have addressed your questions below and also added the respective updates into the paper (see the Appendix E).

$**Q1:**$ The proposed method is not scalable which is rather a limitation. Zigzag persistence introduces additional complexity due to the need for forward and backward inclusions in the filtration sequence, which can become costly for large or dense graphs.

$**A:**$ Yes, of course, we agree, in general, zigzag persistence is not computationally cheap. However, zigzag spaghetti has two main advantages: first, it allows for capturing essential topological characteristics of a dynamic object over time at $**all resolution scales simultaneously**$, and, second, it is easily tractable and computationally efficient (relative to other time-aware topological summaries). To justify the second point, we present the running time comparison among ZS, ZPI, and ZFC for graph classification on MUTAG. The obtained results suggest that ZS-DM achieves the best performance and also delivers competitive running time (in seconds):

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Data $\hspace{2ex}$ | ZS-DM (ours) $\hspace{8ex}$ | ZPI-DM $\hspace{13ex}$ | ZFC-DM

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

MUTAG | 0.21 sec (91.68$\pm$0.34) | 0.37 sec (90.52$\pm$0.63) | 0.18 sec (90.73$\pm$0.59)

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

In addition, the complexity of zigzag persistence on graphs can be improved for a subclass of graphs satisfying certain assumptions on the size of the unions in the filtration, i.e. of the size of the union of all graphs in the filtration is $\Omega{m^\epsilon}$ for any fixed $\epsilon$, i.e., $0< \epsilon<1$ [1]. However, this is not true for a general class of graphs, and some other more drastic approaches are needed to improve scalability of zigzag persistence on denser graphs. One such potential direction is to compute zigzag persistence based only on landmarks rather than on all nodes and then to use Dowker or witness complexes. This approach has not been yet investigated in computational topology and its theoretical guarantees are yet unknown. We believe though that it’s a very promising approach that can fundamentally shift the scalability problem for ZP.

[1] Dey, T.K. and Hou, T., 2023. Computing Zigzag Vineyard Efficiently Including Expansions and Contractions. arXiv preprint arXiv:2307.07462.

$**Q2:**$ I would like to ask the authors if recent efforts in scaling graph diffusion models could benefit also their approach as well. For instance, could techniques such as sparse attention or hierarchical modeling, commonly used in recent large-scale graph diffusion models, be adapted to improve the scalability of the zigzag spaghetti approach?

$**A:**$ We greatly appreciate this reviewer’s suggestion! Based on the paper [1], we incorporate its sparse denoising network (which contains a graph transformer architecture with a sparse attention mechanism) into our zigzag spaghetti approach and have conducted additional experiments on MUTAG and BZR datasets. We call the zigzag spaghetti model with sparse denoising network ZS-DM$_{new}$.

From the Table below, we observe that ZS-DM$_{new}$ always outperforms the previous version (i.e., ZS-DM$\_{old}$) on both MUTAG and BZR datasets. Thanks very much for this excellent suggestion for further improvement of the ZS approach! We’ve added it to the paper, Appendix E (Page 18) at this point, and we’ll integrate it to the main body of the final version when all other edits/additions/deletions are completed.

++++++++++++++++++++++++++++++++++++++++++++++

Model $\hspace{2.2ex}$ | MUTAG $\hspace{3.8ex}$ | BZR

++++++++++++++++++++++++++++++++++++++++++++++

ZS-DM$_{old}$ $\hspace{0.2ex}$ | 91.68$\pm$0.34 | 86.20$\pm$0.12

++++++++++++++++++++++++++++++++++++++++++++++

ZS-DM$_{new}$ | 92.15$\pm$0.32 | 86.39$\pm$0.10

++++++++++++++++++++++++++++++++++++++++++++++

[1] Qin, Y., Vignac, C. and Frossard, P., 2023. Sparse training of discrete diffusion models for graph generation. arXiv preprint arXiv:2311.02142.