Topological Zigzag Spaghetti for Diffusion-based Generation and Prediction on Graphs
Authors: Yuzhou Chen
Yulia Gel
Venue: ICLR 2025 Poster (2025)
Keywords: Graph learning
Topological Data Analysis
Geometric Deep Learning
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning

Abstract: Diffusion models have recently emerged as a new powerful machinery for generative artificial intelligence on graphs, with applications ranging from drug design to knowledge discovery. However, despite their high potential, most, if not all, existing graph diffusion models are limited in their ability to holistically describe the intrinsic higher-order topological graph properties, which obstructs model generalizability and adoption for downstream tasks. We address this fundamental challenge and extract the latent salient topological graph descriptors at different resolutions by leveraging zigzag persistence. We develop a new computationally efficient topological summary,
zigzag spaghetti (ZS), which delivers the most inherent topological properties simultaneously over a sequence of graphs at multiple resolutions. We derive theoretical stability guarantees of ZS and present the first attempt to integrate
dynamic topological information into graph diffusion models. Our extensive experiments on graph classification and prediction tasks suggest that ZS has a high promise not only to enhance performance of graph diffusion models, with gains up 10\%, but also to substantially booster model robustness.

Published as a conference paper at ICLR 2025
TOPOLOGICAL ZIGZAG SPAGHETTI FOR DIFFUSION- BASED GENERATION AND PREDICTION ON GRAPHS
Yuzhou Chen' Yulia R. Gel?
Department of Statistics, University of California, Riverside Department of Statisties, Virginia Tech yuzhou. chen@ucr. ygl@vt.edh
ABSTRACT
Diffusion models have recently emerged as a new powerful machinery for genera- tive artificial intelligence on graphs, with applications ranging from drug design knowledge discovery. However, despite their high potential, most, if not all, existing graph diffusion models are limited in their ability to holistically describe the intrinsic higher-order topological graph properties, which obstructs model generalizability and adoption for downstream tasks. We address this fundamental challenge and extract the latent salient topological graph descriptors different resolutions by leveraging zigzag persistence. We develop a new computationally efficient topological summary, zigzag spaghetti (ZS), which delivers the most in- herent topological properties simultaneously over sequence of graphs at multiple resolutions. We derive theoretical stability guarantees 7S and present the first attempt to integrate dynamic topological information into graph diffusion models. Our extensive experiments on graph classification and prediction tasks suggest that ZS has high promise not only to enhance performance of graph diffusion models, with gains up 10%, but also to substantially booster model robustness.
INTRODUCTION
Diffusion models on graphs. as a novel generative paradigm in artificial intelligence, with applications from drug design to material discovery, has invigorated interest of the deep learning (DL) community in developing more systematic, efficient, and reliable mechanisms for graph representation learn- ing (Yang et al. 2023 /Zhang et al., 2023 Liu et al.) (024). In turn, the emergence of probabilistic diffusion models has sparked attention diffusion- based graph generation, e.g., decomposition of the full diffusion into multiple simpler inter-related diffusion processes to model the dependencies among nodes and edges (Jo et al., 2022), which demands diffusion models to accurately capture intrinsic higher-order topological properties simultancously across multiple (sub)graphs. However, prevailing graph diffusion models tend to exhibit limited abilities to describe such key joint topologi- cal characteristics across multiple objects, which obstructs their generalizability and restricts their utility for downstream tasks (Kong et al.) [003) Yi et al., 2024a Cai et al. 2024). Addressing this barrier requires development of new mathematical approaches, enabling us simultaneously extract the most illustrative topological characteristics not of a single graph but of a sequence of graphs, with the problem being further exacerbated for diffusion models for time-evolving graphs.
We postulate that this fundamental challenge can be approached by blending the emerging ideas of graph diffusion models with the mathematical machinery of zigzag persistence (ZP). What is the premise? Persistent homology (PH) on graphs allows us to learn the key higher order shape descriptors, i.e., properties that are, broadly speaking. invariant under continuous transformations such as twisting, compressing, and stretching (Carlsson) 2009). Combination of PH with DL on graphs, usually in a form of a fully trainable topological layer, often results in superior graph learning performance and higher robustness to perturbations (for the recent overviews see, e.g., Yan et al. (2021); Horn et al. (2022) ;; Verma et al. (2024)). However, traditional PH focuses only on a single graph. In contrast, ZP is the powerful mathematical tool based the theory of quiver representations that allows us to advance the ideas of the traditional PH to a case simultaneous evaluation of
the key shape characteristics of sequence of graphs (Carlsson & Silva 2010 Tausz & Carlsson

---

Published as a conference paper at ICLR 2025
2011). The extracted zigzag topological information can be then conveniently summarized in form of zigzag persistence image or zigzag filtration curves (Chen et al., 2021] 2022). Such summaries satisfy the conditions of Lipschitz continuity and, such, are suitable imput fully trainable topological layers in DL on par with the traditional PH tools. However, these ZP summaries require some a-priori knowledge of the data and yield topological information extracted only for a single user-predefined resolution scale. To mitigate this problem. Xian et al.] developed a crocker plot. Crocker plot does not use the ZP notion per say, but is based on the traditional PH framework, recording the number of topological features at each resolution. Although being tractable and computationally efficient, crocker plots are not differentiable and cannot serve as an input to a fully trainable topological layer. Furthermore, crocker plots yield only local information on the graph topology, bypassing critical information on lifespans of topological features. These open questions on Zigzag topological summaries, along with computational costs of 7P on graphs have been obstructing broader applicability of ZP and keeping it largely as a theoretical concept in algebraic topology, albeit number of recent studies demonstrating the ZP potential in ecology, enginecring, and social
sciences (Mata et al. 2015) Myers et al. 2203bb McDonald et al. 2023 Chen et al.) (023) and albeit
the recent advances improving computational efficiency of ZP on graphs (Dey & Hou 2021 Dey
et al. 2023).
Here we propose bridge the rising research directions on graph diffusion representations and zigzag persistence. We develop a new computationally efficient time-aware topological summary, zigzag spaghetti (ZS), which simultaneously captures the key joint higher-order shape properties from sequence of graphs at all resolution scales. We show that ZS enjoys the important theoretical stability guarantees which in practice imply resistance of ZS uncertainties and, hence, is of particular significance for diffusion- based graph generation tasks, often involving noisy conditions and limited data scenarios. We also explore the applicability of ZP as a backbone tool for topological bootstrap and the associated topological uncertainty quantification, resulting in reducing variability up 5 times comparing to the competing models. Finally, we validate the ZS utility in diffusion-based prediction and classification tasks on graphs, illustrating the critical role the latent higher order topological information plays in performance and robustness of graph diffusion models.
Significance of our contributions can be summarized as follows:
To the best of our knowledge, this is the first attempt to bridge not only zigzag persistence but generally, tools from algebraic and computational topology with generative diffusion models on graphs
We develop new computationally efficient and easily tractable time-aware topological summary. zigzag spaghetti, for simultaneous assessment of the latent topological characteristics of multiple graphs at various resolution scales and derive its theoretical stability guarantees.
We show the utility ZS in application to extracting time-conditioned topological knowledge from time-evolving graphs and to topological uncertainty quantification.
With extensive experiments on a broad range of benchmark datasets, we demonstrate the superiority of our ZS-based tools over the strongest state-of-the-an thettrr graph-based models for both graph pre- diction and classification tasks, resulting not only in performance gains up to 10%, but prominent improvement in robustness.
2 RELATED WORK
Diffusion Models Inspired by non-equilibrium thermodynamics, diffusion models are proposed as a tool reconstruct data samples from noise by reversing the diffusion process of the Markov Chains (Sohl-Dickstein et al. 2015) Yang et al.) 2023). Recently, diffusion based tools have sprung up as new branch of generative models such as Stochastic Differential Equations (SDE) (Song et al.. 2020c), Denoising Diffusion Probabilistic Models (DDPM) (Ho et al. 2020), Denoising Diffusion Implicit Models (DDIM) (Song et al.) 2020b). Noise Conditional Score Networks (NCSN) (Song & Ermon 2019), and autoregressive diffusion model for graph generation (Kong et al. 2023). Additionally, DiGress of Vignac et al. (2023) consider a discrete diffusion process to progressively add discrete noise to graphs by either creating or removing edges and altering node categories for graph generation, while LGD Cai et al. (2024) applies a score-basee diffusion generative model in the latent space generate new graph representations. However, most graph diffusion approaches
2

---

Published as a conference paper at ICLR 2025
tend to overlook the richer set of topological and structural information in the input data. To address this barrier, TopoGAN model with a generative adversarial network (GAN) framework is used to bridge synthetic and real data distributions in the topologiaal feature space (Wang et al. 2020). while Niu et al. (220) develop a permutation invariant model to study the gradient of the distribution of input data. Nevertheless, these approaches still tend to suffer from the following limitations. First, they can only model spatial information, leading to the restricted capabilities of capturing (long-term) inter-dependencies and intra-dependencies. Second, they tend be limited in quantifying uncertainties, which hampers their applicability under scenarios with scarce records and unseen data.
Zigzag Persistence has recently emerged as new powerful machinery in computational topology. ZP has proven its utility in a wide range of domains, particularly, involving time-evolving and dynamic objects, such as neuronal images and brain functions (Mata et al.. 2015 [J1s/hhhyruryy et al., 2018), swarming phenomena in biology (Corcoran & Jones] 2017] Kim et al. (020), cryptocurrency analytics (Chen al., 202T; 2022), commuting trends in transportation networks (Myers et al.) 2023b coral reef resilience (McDonald et al. 2023), power distribution planing (Chen et al. |023 and cy byrrsecuurity (Myers et al. 2023a). Nevertheless, beyond a handful of recent studies (Chen et al. 2021 2022). the ZP utility in DL still remains largely unexplored (Carlsson & Gabrielsson| 2020).
One of the primary roadblocks on the way of ZP on graphs (arguably) remains computational costs, although recently there has been notable progress in this direction (Dey et al. 2014: Dey & Hou
2021: Dey et al. 2023). In addition, the existing ZP summaries, zigzag persistence image|Chen
Chen et al.
(2021) and zigzag filtration curves Chen et al.] (2022), can only deliver topological information for single a-priori user-selected resolution scale, which restricts their utility for the scenarios with the yet unseen data. Here we bypass this major limitation and develop a new computationally efficient time-aware topological summary, zigzag spaghetti, simultaneously quantifying the most essential tine-conditioned information for a sequence of graphs at all scales and opening a path for ZP in generative DL.
3
ZIGZAG SPAGHETTI: FROM TIME-AWARE KNOWLEDGE REPRESENTATION TO TOPOLOGICAL UNCERTAINTY QUANTIFICATION
Let G = (V,E, X) be an attributed graph, where is a set of nodes (V) N), & is a set of edges, and X E IRN is feature matrix of nodes (here F is the dimension of the node features). Let A NN be a symmetric adjacency matrix whose entries are a.j = Mij if nodes i and j are connected and 0 otherwise (here Vij is edge weight and Vi = 1 for unweighted graphs). In turn, D graph forecasting, a spatio-
denotes the degree matrix of A, that is du = Σ, Oij. For temporal graph is collection of snapshots at different time steps, denoted by g ( g ....... ,TT). where T is the maximum timestamp.
Zigzag Persistent Homology Given a sequence of time-evolving graphs gh,gs , .... gtm, we may be interested in such questions as:
Q1 What are the most characteristic topological signatures of these graph sequence over time?
Q2 How do these time-aware topological signatures vary over different resolution scales?
These questions are critical for forecasting, transfer learning, anomaly detection, and broad range of other unsupervised tasks involving time-evolving objects.
To address these questions, we can invoke the machinery of zigzag persistence (ZP) (Carlsson & Silva. 2010: Carlsson et al. 2019), which allows us to consider linear maps into both directions X )( X (Gorz) and X (G..) - XXG (Gaz+1). rather than into single direction traditional PH does (see Appendix A for background on PH). In a context of time-evolving graphs, we alternate left and right inclusions and interleave them with unions of neighboring graphs, where the union of graphs is defined as the standard graph operation by creating single graph which contains all the nodes and edges from both original graphs (Gross al. 2018 Shao & Sun 2014):
g
g
gla-1 U U
3

---

Published as a conference paper at ICLR 2025
Now, given a scale a, we say that topological feature & of dimension p (0 S p S dim(KC) is born time to, if is first recorded at X (g") ). and we say that ç is born at time t, + 2. if is is first recorded at XX(( U Similarly, we say that & dies at ta or ta + 1. if is last recorded at X (( or X (g U gl respectively. The extracted topological features at scale a can be represented in form of zigzag persistent diagram (ZPD) PDZzy h = 1.2..... m, which is a multiset in I.,, ie. PDz,, = { de) E beg < E E MM. where by and dg are the birth and death of the p-dimensional topological feature Ç. respectively, M is a set containing the observed p-dimensional topological features at scale Ogg, and m is a filtration length.
To quantify topologiaal features extracted over Chen et al. (2021) and Chen et al. (2022) propose
to use zigzag persistence images (ZPI) and zigzag filtration curves (ZFC), respectively. Both ZPI and ZFC are based on advancing the ideas of persistence images (Adams et al. 2017) and filtration curves (Johnson & Jung |021 O' Bray et al., 202I). developed for traditional PH to a zigzag case. While promising, the major limitation of ZPI and ZFC is that these summaries are limited only to a single pre-defined resolution scale a.. In turn, selecting such feasible scale a, may require some a-priori knowledge of the data. Furthermore, using ZPI and ZFC can help us answer only a part of Q1, that is, which topological features are the most characteristic over time for given resolution a,? To mitigate this restriction, Xian et al. (2022) propose to employ a crocker plot, which does not use the notion of ZP, but uses the traditional PH framewor,, recording the number of "holes" at each scale a; as function of time t and scales ar1 Q2...... While simple to compute, crocker plots do not satisfy the assumption of differentiability and, hence, cannot serve as an input to a fully trainable topological layer. In addition, crocker plots convey only local information on the graph topology, bypassing critical information on lifespans of topological features. Our goal is to address this major challenge and provide comprehensive answers both to Question I and 2 for general case.
3.1 NEW TIME-AWARE ZIGZAG SPAGHETTI
Inspired by the ZFC of Chen et al. (0222) and crocker plots of Xian et al. (2022). ) we propose a new time-aware topological summary zigzag spaghetti (ZS). The term spaghelli is motivated by the notion of a spaghetti diagram widely used in Earth sciences (Wilks) 201T). ZS leverages the strengths of both ZFC and crockers plots, while mitigating their key limitations.
Definition 3.1 (Zigzag Spaghetti). Let [t1. tn] be the time interval over which we observe time evolving graphs {G*) We represent [&1, ty] as UAt, where At, = (t--1+ + +2, i,,,,,;== 1, l....... ..... n are non-overlapping time intervals. Let a1 < a2 < Spaghetti (ZS) for p-dimensional topological information of (G'); (0 S p S dim(KC) is given by
am be a sequence of scales. Then, Zigzag
Σ/= Wini (to;, td;)as
M
ΣØ=1 wyn?
(tb;;tt))e )as
و Winhi (to tal )as
)S(19)))=
=
EyM Wn (bo Ldd Jam Here K, 2R2 + RR is suitable L Lipschitz continuous function with Lipschitz constant L,, associated with scale agg, A = 1, 2....... m. Following Johnson JollowingJohnnon & Jung (202I) and [Chen et al. (002). here as Ki, we use a Gaussian density f with mean (f,-1 + 1/2, t,) and identity covariance matrix Σ. In turn, (tog, td, )a, E R² is an interval containing the birth and death of a p-dimensional topological feature E, observed at scale ax. j studies we set Wi = 1/ n, i.c. a "flat prior".)
=== W2 WIng aetm (1og) la.)am.
Ee W2ng am (lo 1 Ja))a..
M) and w; are positive weights such that Σ, W/ 1. (In our
Being Lipschitz continuous, ZS is suitable as an input to fully trainable topological layer in DL. At the same time, ZS inherits tractability of crocker plots in terms of linear algebra, while providing critical information on both local and global time-aware topology, lifespans of the extracted time- aware topological features at all resolution scales. Furthermore, as Proposition 3.2 shows, ZS satisfies the important theoretical stability guarantees in terms of Wasserstein distance W1.
Proposition 3.2 (Stability of Zigzag Spaghetti). Let PDzoz be a zigzag persistence diagram cor- responding to scale agk, k = 1.2...., m. and let PD''a, be its perturbed counterpart such that (PD PDz <, Ek- Let ZS and ZS' be zigzag spaghetti summaries corresponding to zigzag persistence diagrams PDz., and PD respectively, over scales a1,, 02,, am. Then ZS is stable with respect to Wasserstein distance W1 and
||5 - ZS' S max Wi (PDEas, PDz..))
1<k5m
4

---

Published as a conference paper at ICLR 2025
where ||
|/oc is column norm of matrix, i.e. for matrix B, BBlcc max, E, bist
Proof of Proposition 3.2 is Appendix B
Proposition 3.2 essentially guarantees that smaller changes in the graphs are expected result in smaller changes in ZS. Practically, this stability result of high importance to ensure robustness of ZS and the associated graph learning process with respect to uncertainties. To illustrate this idea, conduct a robustness study under various noisy scenarios and varying sizes of training sets and find that 7S yields competitive resistance broad range of uncertainties (see Section | and Appendix [ for more details). Furthermore, these ideas can be advanced toward a multipersistence framework, as discussed by Coskumuzer et (2024).
3.2 ZIGZAG TOPOLOGICAL UNCERTAINTY QUANTIFICATION
The idea of zigzag persistence is very general and can unfold new approaches address broad range of open problems in graph learning and knowledge representation. Here we propose to employ ZP for topological uncertainty quantification (UQ). That is, from a formal statistical inferential point, we can add another question:
Q3 How certain are we that the extracted most characteristic topological signatures of the graph sequence over time and over different scales ag are indeed most characteristic and are not simply due to chance only?
To address this question, develop bootstrap ZS, which is rooted in the ideas of block bootstrap for time series Politis (2003). In particular, given a sequence of graphs {g' fhn associated ZS, we (sub) sample graphs {gr Fir without replacement out of t, graphs (g (Tm < (n)) and construct its associated ZS We can then repeat the (sub)sampling procedure B times, which results in an ensemble of bootstrapped ZS (BZS): BZS {ZSi, ZS5.... ZS Intuitively. we can expect that the most illustrative time-aware topological features persisting over {g*) Jú shall also manifest in many bootstrapped ZS. Armed with the BZS ensemble, we can then consider integrating BZS into DL models, quantifying the uncertainty associated with time-aware topological signatures. Alternatively, we can estimate mean, median and other quantiles of BZS and construct the associated confidence and prediction intervals. However, this route is more challenging, since given that BZS is collection of matrices, it involves the developments in terms of random matrix theory (Paul & Aue 2014). As such, we leave this route for further research and note that the concept of zigzag and ZS are not restricted to time-evolving or even other naturally ordered objects.
Jti and its
4 ZIGZAG SPAGHETTI-AWE NEURAL NETWORKS
In this section, we provide the technical details of the proposed zigzag spaghetti- aware models. Then detailed descriptions of each step are given.
4.1 MIXED-UP GRAPH CONSTRUCTION
To capture topological information from graph G and its node features, we construct a mixed-up graph G. (A.,, X) based on original input graph Go (Ao, X) and k-hop graph 9K (Ax, X).
Original Graph Representation Learning. We adopt the Graph Convolutional Layer (GCL) to perform message passing on the original graph Go = (Ao,X, X). It utilizes the original graph structure of Go with its node feature matrix X through the graph convolution operation and a multi-layer perceptron (MLP). Specifically, the designed graph convolution operation proceeds by multiplying the input of each layer with the r-th power of the normalized adjacency matrix. The 7-th power operator contains statistics from the 7-th step of a random walk on the graph (in this study, we set r to be 2), thus nodes can indirectly receive more information from farther nodes in the graph. Combined with a multi-laycr perceptron (MLP), the representation learned at the L-th layer is given by
z ((+1) 9o
-muplo(Ae o (()))
(1)
5

---

Published as a conference paper at ICLR 2025
Forward Process
X2
X
X
X;
Moc
Moc
MOC
MGC
MBC
MDC
9o
51
52
9
9.
25
25
25
25g
Z5g
Figure I: Forward process of the zigzag spaghetti-aware diffusion model. At each time step, we first add noise to the data, i.e., transitioning from X X to X2 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 specific sliding window (i.c., the dashed gray box) to obtain the corresponding zigzag spaghetti.
Here = A Ao = Ao + I, D the corresponding degree matrix of Ā, H H Go X,
H(()) is the output the 1)-th layer, SMUP is an MLP which has 2 layers with batch normalization, Go
a.) is the non-linear activation function, and e is trainable weight of f-th layer.
K-Nearest Neighbor Graph Representation Learning. First, to capture graph structural informa- tion, induced by the graph connectivity and node features, we build K-nnarest neighbor (KNNN) graph, i.e., GK = (Ax, X). In our study, we first define the similarity matrix Sx E R among N nodes and consider three different methods follows: (i) Cosine Similarity: It uses the cosine aE value of the angle be- tween two vectors to measure the similarity, i.c., Sue Te.. [..] (ii Gaussian Kernel: It is based on the idea of the heat equation, partial differential equation that describes how heat propagates over time I, which can be defined as follows S... exp(-Ilax, - æ..11 /t); and (ii) Node Embedding Similarity: Let ((+1)) be the node embedding of (f)-th layer of GNN. For any u. V, we can calculate the similarity score Sue between nodes u and as (i) Cosine Similarity: (ii) Gaussian Kernel: Sue exp (- (-
DE(++111/// (where t a free parameter). Then, the adjacency matrix Ax can be obtained through selecting top-K similar neighbouring nodes of each node. Similarly, we can use Eq. [ to learn the (f + 1)-th layer node
S uar || H H
H 11+ H((11)
embeddings of the above XNNN graph, which is denoted by Z (++1)
Mixup for Graph Construction. Here we adopt node-level attention mechanism to learn the hidden connectivity between nodes. Specifically, given node pair (u, v), the importance coefficient between
nodes u and can be formulated as (for the simplicity, we omit (2 + 1) for Zgo z(f+1) and 2 (f+1) )):
9x
Eur θ θ. Zgo Each
explo(( EvEy Dnvevexplot (x ee
Softmax e
where [ represents the concatenation operation, ___ and P. are training parameters, a(-) denotes the LeakyRel.U function with negative input slope 0. After the above calculation, we can get the mixup attention score a.d te
which represents the weight of the edge between nodes and
4.2 ZIGZAG SPAGHETTI REPRESENTATION LEARNING
The challenge of graph representation learning in generative diffusion is further aggravated, when the goal is model dynamic topological information between graphs. In light of this, we propose novel

---

Published as a conference paper at ICLR 2025
zigzag spaghetti- brggeeti--based encoder (ZS-ENC) explicitly capture the beneficial temporal topoloiial information. Formally, given ZS, we generate its latent representation as:
(MLP(OrZZS), Scenario (I) UMIP(O>sBBS)
Zzs =
Scenario (II)
where Ozs trainable weight. Note that, in this paper, we consider both graph classification and prediction on spatio-temporal graphs, and we describe two specific scenarios to learn ZS, i.e.,
Scenario (I): for spatio-temporal graph forecasting tasks, given a sequence of time-evolving graphs, we only generate one ZS;
Scenario (II) for graph classification tasks, to generate a ZS for the sample X, at time step in the forward process, we apply ZS over both time step and its adjacent yp (4p > time 2, ( 1,6, L 1, ... L 2....
steps (e.g., {t 9
(o} denoted as 7
To get efficient computation without sacrificing on performance, we use the bootstrapping mechanism to randomly select B subsamples from 7t- For instance, (where E [0.5, 1) time steps from Te- as [1 {1-3, 1-2, 1,1, (+1) (1-3 (1-3, 1-1, (+2, (+3), etc. Hence, can generate BZS with the size B (in our study, we B to be {20, 50, 100]: see more details in Table (4) during the forward process the diffusion model and each ZS, is generated based mixed-up graphs at w different time steps.
randomly select p(2 + 1)
4.3 ZIGZAG SPAGHETTI-AWARY DIFFUSION MODEL
We now elaborate on our two proposed frameworks. First, we start with zigzag spaghetti-aware diffusion model (ZS-DM) which involves forward and reverse processes for graph learning. Then, for spatio-temporal forecasting tasks, discuss IS-DM which combines the spatial and temporal learning capabilities of GNN, recurrent neural networks, and ZS representation learning module.
The forward process of the diffusion model is gradually add noise onto the real data. We first generate a sample X, from the input node feature X via Eq. 4 We then employ fMuc(.) which is the mixed-up graph construction (MGC) process to generate its corresponding mixed-up graph, i.e. Ge = fMGc( After that, in Eq. 5 we use the function of the ZS representation learning (zs(-) extract the corresponding 7S:
X, = Vo + VI acd' Zzs,1 (M)))))))))))
(4)
(5)
Inspired by incorporating directional noise in the forward diffusion process for graph learning of Yang et al. 2024), here corrupt input data (i.e., X) with directional noise instead of white noise, i.e.,
sgn X @ | and = f + a @ c where c ~ (0, I), where @ is the elementwise product. During the mini-batch training, μu and are calculated using graphs within the batch. The parameter
a - 3,) represents the variance schedule (o,, 1 BB), and we set {B1, 92, 3T as hyperparameters so that the forward diffusion process is not included in the training. The overview of the forward process illustrated in Figure
In the denoising process, we develop a denoising decoder fDEC(-) with graph convolution blocks (in UNet-inspired architecture) to learn the reverse Markov chain with zigzag spaghetti:
Xn fDEC( Xx, t, Zzs.t; : 1) [JNNN( X 1), fzs Zzs ENC. )) + SPE(t);
where we use sinusoidal position embeddings fPE(-) Vaswani et al. 2017) to encode the timestep t. For spatio-temporal graph prediction tasks, employ UGnet Wen al. (2023), i.e., Unet-based architecture to capture temporal dependencies and the GNN to model spatial correlations.
5 EXPERIMENTS
Datasets, Baselines, and Experimental Setup. We evaluate our ZS-based graph learning models on teatioltemporal prediction tasks 2 traffic datasets, i... PeMSD3 and PeMSD8 which are real-time traffic datasets from California (Guo et al.) 2019, Song et al. 2020a), where nodes denote sensors and edges represent the intersections between the nodes.
7

---

Published as a conference paper at ICLR 2025
Table 1: Prediction performance of probabilistic methods on the PeMSID3 and PeMSD8 datasets.
PeMSD3
PeMSD8
Probabilistic Models
MAE
RMSE
MAPE (%)
MAE
RMSE
MAPE (%)
Latent ODE Rubanova et al.
2019
17.25
28.33
17.71
26.05
39.50
17.20
DeepAR Salinas et al. 2020
17.44
28.51
18.02
21.56
33.37
14.15
CSDI Tashiro ( 2021
18.92
30.41
19.56
32.11
47.40
18.88
TimeCrad Rasul
2021
17.93
29.81
19.33
24.46
38.06
17.03
MC Dropout et al
2021
17.25
27.85
17.79
19.01
29.35
13.10
DiftSTG Wen et al. 22223
17.79
28.74
18.12
18.60
28.20
11.94
ZS-DM (ours)
16.57
26.46
16.25
17.59
26.09
10.29
Table 2: Performance comparison on molecular and chemical graphs.
Model
NCI
PROTEINS
DD
MUTAG
BZR
COX2
PTC MI
FTC FM
GI.
Shervashidze al.
2009
N/A
N/A
N/A
31.66:1..11
NIA
NIA
57.30 1.40
N/A
WL
Shervashidzee et al 2011
80.01
0..9
74.00=2.200
80.72:33000
NIA
N/A
58.00=#0.50
N/A
DGK
Yanarolgg
Wanthan
40.31:0046
03.30=0.82
87.44:12.72
60.10:22.60
mode2
Unuver & Leskoved 2016
54.89:11.61
37.4913.57
NAA
72.63=10.21
NIA
N/A
N/A
N/A
sub2vse
Adiikar of 2018
52.84+1.447
53.03=5.555
N/A
61.05=15.80
N/A
N/A
graph2
Naravanan
2017
73.22::1.81
73.30=22.05
NAA
83.15:19.25
NIA
NIA
NA
N/A
InfoGraph Sum al
20799
16.20.11.06
74.44.1.31
72,85
1.78
89.01
84.84.10.86
80.55 L0.51
61.70.L 1.40
61,55
GraphCI.
You
77.87:1441
74.39=0.45
78.62-1040
86.80-11.34
84 04
10
21,3012..10
65.26-10.59
AD-GCL Suresa e
73.91
73.28=00.66
75.79=0.87
88. 18.74
85.97:40.63
78.6
63 20:4
64,99-0777
RG
78.144:1.08
75.03-0.43
78.86-1048
64.29-10.32
GCL- SCL-TAGSS
2022
71.43:00.49
75.78=0.41
75,78=052
12:
NIA
N/A
N/A
N/A
GraphMAF Hou el
A122
00.40.10.30
05.30
N/A
18.1911..2
N/A
N/A
N/A
N/A
CWN Bodnal
00.35
0.774
86.32:20.91
N/A
N/A
N/A
TOGL Tiom el M1724
1..49
72.72
NIA
90.49
NIA
N/A
N/A
N/A
Yang al:
73.93100777
75.47.0..00
79.88
12..1 65.09-40.97
ZS-DM (Ours)
81.80:1.009 76.08-10.19" 78.93=00.22 91.68:1.34 86.20 81.73-186" (4.02:11000 66.76:00.24
In addition, we validate our ZS-DM on unsupervised graph representation learning classification tasks using the following 8 real-world chemical compounds and protein molecules: (i) 3 chemical compound datasets: MUTAG, BZR, and COX2, where the graphs are chemical compounds, the nodes different atoms, and the edges chemical bonds and (ii) molecular compound datasets: NCI1, D&D, PROTHINS, PTC_MR, and PTC_FM, where the nodes represent amino acids and edges represent relationships or interactions between the amino acids, e.g. physical bonds, spatial proximity, or functional interactions. For these 8 graphs, we follow the training principle (You et al. 2020) and use 10-fold cross validation accuracy as the classification performance (based on linelinear SVM model, i.e., conduct a one-sided two-sample /-test between the best result and the best performance achieved by the runner-up. where * denotes statistically significant results. We also adopt larger graph dataset ogbg-mm molhiv from Open Graph BenchMark (OGB) Hu et al. (2020). For ogbg-molhin data, the task to predict certain molecular property, measured in terms of Receiver Operating Characteristic Area Under Curve (ROC-AUC) scores, and we follow the official scaffold splitting where structurally different molecules separated into different subsets.
& Lin (2011)) and report the mean and standard deviation. We
Experimental Settings. We implement our proposed ZS-DM with Pytorch framework on two NVIDIA RTX A5000 GPUs with 24 GB RAM. We use the dionysus2 package in Python for ZP graphs. For graph classification, we follow a two-step process, i.e., we firstly pre-train a ZS-DM on the dataset in unsupervised manner, and then extract feature representations from diffusion steps 50, 100, and 200 using the pre-trained model. For PeMSD3 and PeMSD8, we consider window size
Table 3: Ablation study of different rigzag-based topological features.
Architecture
PROTEINS
MUTAG
MR
7S-DM
76.08-10.19
9134
64.02-1 1.00)
ZPL-DM
75.83+20:41
89.28-10.00
63.06 1.32
ZFC-DM
75.80=20.49
90.74::0.31
62.43::1.43
8

---

Published as a conference paper at ICLR 2025
Table 4: Performance comparison under different number of subsampling replications on PROTEINS, MUTAG, and PTC MR datasets.
PROTEINS
MUTAG
PTC_MR
Model
sim 20 sim
50 # sim
100
sim
20
sim
50
# sim
100
sim 20
sim 50 # sim 100
ZS-DM (ours) 75.98=0034 76.0220022 76.08=0.19 91.6 0.567 91.48=0.50 9..68=0.34 63,98=2.28
63.33+ 1.07 64.02=+1.00
of 12 and horizon h of 12. To measure the forecasting performance of predictive models, we use Mean Absolute Error (MAE), Root Mean Square Error (RMSE), and Mean Absolute Percentage Error (MAPE). The hyperparameter values is determined via grid search. For spatio-temporal traffic forecasting, we set the number of epochs trained, batch size, and weight decay ratio to be 200, 16, and 0.9 respectively. We search initial learning rate of model among {0.001, 0.003, 0.005, 0.01}. number of convolution layers among {1, 2, 3). dimension of hidden units among {16, 32, 64, 128, 512). For the mixed-up graph construction, we set number of steps of a random work to be = 2. Our code and data can be accessed under htte:::tt::::: / t.ub. cow z www.ggaggatttttteccc.. /ttiiiizizzz gzag_ spaghett adm.giit,. (Please refer to Appendix C for the detailed version of baselines.)
Findings. Table compares forecasting performance on spatio-temporal graphs between our ZS-DM and state-of-the-art baselines (6 probabilistic methods) on PeMSD3 and PeMSD8. We find that ZS-DM leads performance under all scenarios, with gains up 14% in MAPE and up to 7.5% in RMSE. The results suggest that ZS-DM can effectively capture spatial corre- lations, temporal dependencies. and time-aware topological information in a holistic manner. In turn, Table 2 presents accuracy for graph classification. The best results are in bold and the results with underline denote the runner-ups. We find that ZS-DM consistently outperforms 15 base- lines on all 8 graphs. To be specific, compared to GNN-based contrastive learning (i.e., InfoGraph, GraphCL, AD-DCL, RGCL, and GGCL-TAGS) ZS-DM improves upon runner-ups ups by a margin of 4.68%, 0.40% 0.09%, 2.87%. 0.27%, 0.90%. 1.30%, and 2.30% on NCI1, PROTEINS, DD, MUTAG, BZR, COX2, PTC_MR, and PTC_FM respectively. Moreover, compared to the two powerful graph generative models (i.e., GraphMAE and DDM), ZS-DM al- ways outperforms the runner-up by a large margin. For instance, for chemical compound datasets (except MUTAG), ZS-DM demonstrates competitive improvement, i.e., yielding relative gain from 2.32% to 3.06%. The results of ZS DM, GraphCL, and TOGL on ogbg-molhiv are shown in Table [ The findings are consistent with those in Table 2 that is, ZS-DM yields better performance than that of GraphCL and TOGL.
Table 5: Performance compar- ison ogbg-molhiv (ROC- AUC).
Model
ogbg-molhiy
18. ZS-DM (ours)
GraphCL TOGL
62.63 67.52.13.00
We also conduct robustness of 7S-DM under various noisy conditions. In particular, we add Gaussian noise with mean f and standard deviation a = 0.1 1% and 5% MUTAG data. As Table indicates, ZS-DM is more stable under noisy scenarios than DDM.
Robustness.
We perform the robustness analysis w.r.t. varying sizes of the training sets, reducing the training set from 90% to 80% and 70% (see Appendix D for further details). We find that the ZS-DM gains in performance increase as the training size decreases, while variability of ZE-DSND S--D tends to be noticeably lower than runner up SOTAs, i.c., up to 1.5-2 times lower. These phenomena suggest that ZS might be more helpful when the amount of training data is lower or the data are noisy, which intuitively is expected because 7S allows to gain additional insights into the latent topological structure of the underlying data generating process. (For additional experiments on the choice of filtration scales and sensitivity the dimensions of topological features see Appendix D also contains.)
Table 6: Robustness study under additive Gaussian noise.
Model
MUTAG
MUTAG with 1% moise
MUTAG with 5% noise
DDM
91.51-11445
89.6 09.68 91.02-0.83
86.41 -1.77
7S-DM (ours)
91.68-1..34
89.76-10.36
ZS vs. competing Zigzag Summaries and Traditional Persistence. To evaluate the ZS gains in capturing time-aware higher-order topological information, we compare 7S with 7PI Chen al.

---

Published as a conference paper at ICLR 2025
(2021 and ZFC Chen et al. (2022). Table 3 indicates that in all cases (both graph prediction and graph classification), ZS-DM outperforms ZPI-/ZFC-bass based models by a large margin. Also, compared with ZPI, computational cost of ZS is much lower, e.g., average rumning time of ZS and ZPI generation per epoch on MUTAG are 0.21 and 0.37 seconds, respectively. To summarize, our proposed approach achieves much better results than ZPI- and ZFC-based DM models without sacrificing efficiency.
Furthermore, Table 7 presents comparison of ZS vs. traditional PH. We observe that ZS-DM outperforms with highly statistically significant gains the diffusion model with traditional persistence on both MUTAG and BZR datasets. These phenomena illustrate the critical role that simultaneous assessment of the joint higher order topological features at all resolution scales plays for performance and robustness of graph diffusion models.
Table 7: Performance comparison between ZS and traditional persistence.
Data
ZS
Traditional Persistence
MUTAG
91.68:+0..3' BZR 86.20=+0.12
86.00=10.83 83.94+10.77
Impact of the Number of Subsampling Replications and Topological UQ As described in Section 4.2 in the forward process of ZS-DM model, we can generate a BZS of size B. To evaluate the ZS-DM performance with different bootstrap samples, we also report the mean accuracy with standard deviation of ZS-DM for for varying numbers of bootstrap replications (i.e., #sim) (see D. We observe that, when #sim increases (from 20 to 100), variability of ZS-DM substantially decreases, thereby suggesting the utility of this approach for topological UQ
Computational Costs. Currently, the best possible computational complexity for ZP for 0- dimensional and for I-dimensional features on graphs is O(m log"(N) + m log(m)) Dey & Hou (202T The ZP complexity 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 2(m²) for any fixed
< 1 Dey al. (202). Alternatively, we may compute ZP based only on landmarks rather than on all nodes and then to use Dowker or witness complexes (De Silva & Carlsson] 2004, [Cho et al.] 2024, Li et al.] (024). Table X also shows average time taken and performance comparison between ZS-DM and DDM. Although the average time taken by ZS-DM is a bit higher, ZS-DM consistently outperforms DDM and other competitors.
Table 8: Average time taken comparison between ZS-DM and baseline methods.
Data
MUTAG PTC MR
Data
PeMSD3 PeMSD8
DDM
1.73
3,41
DifITGG
3.98 s
4.73
ZS-DM (ours) 2.55
3.79
ZS-DM (ours) 3.27
5.25
6 DISCUSSION AND FUTURE DIRECTIONS
With the growing success of diffusion models on graphs, there is surge of interest in more accurate and reliable graph representation learning. Indeed, most currently prevailing techniques of generative diffusion on graphs tend to be limited their abilities to capture intrinsic topological features of multiple graphs simultaneously. This in turn severely obstructs the transferability and generalizability of such diffusion models. We tackle this fundamental challenge by invoking the mathematical machinery of zigzag persistence which allows us to systematically extract and summarize the inherent topological characteristics of multiple objects, including time-evolving graphs, simultaneously at multiple resolution scales in form of zigzag spaghetti. To the best of our knowledge, this is the first attempt to bridge diffusion models on graphs with the notions of topological data analysis and, zigzag persistent homology, in particular. In the future, armed with more scalable abstract simplicial complexes such as Dowker and witness complexes, we plan to push this envelop further by exploring zigzag persistence for diffusion models hypergraphs and dynamic multilayer networks.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was supported by the NSF grant DMS-2335844/23355847 and the ONR grant N00014-21- 1-2530. The views expressed in the article do not necessarily represent the views of NSF ONR. The authors would like to thank the AC and three ICLR reviewers as well Dr. Andrei Zagvozdkin for engaging into the interactive discussion and providing highly valuable feedback that allowed for improving the manuscript.
REFERENCES
Henry Adams, Tegan Emerson, Michael Kirby, Rachel Neville, Chris Peterson, Patrick Shipman, Sofya Chepushtanova, Eric Hanson, Francis Motta, and Lori Ziegelmeier. Persistence images: A stable vector representation of persistent homology. JMLR, 18, 2017.
Bijaya Adhikari, Yao Zhang, Naren Ramakrishnan, and B Aditya Prakash. Sub2vec: Feature learning for subgraphs. PAKDD, pp. 170-182. Springer, 2018.
Lei Bai, Lina Yao, Can Li, Xianzhi Wang, and Can Wang. Adaptive graph convolutional recurrent network for traffic forecasting, In NeurIPS, volume 33, pp. 17804-17815, 2020.
Ulrich Bauer. Ripser: efficient computation of vietoris-rips persistence barcodes. arXiv: 1908.025188 2019.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: CW networks. In NeurIPS, volume 34, pp. 2625-2640, 2021.
Zhou Cai, Xiyuan Wang, and Muhan Zhang. Latent graph diffusion: A unified framework for generation and prediction on graphs. arXiv preprint arXiv:2402.02518. 2024.
Defu Cao, Yujing Wang, Juanyong Duan, Ce Zhang, Xia Zhu, Congrui Huang, Yunhai Tong, Bixiong Xu, Jing Bai, Jie Tong, and Qi Zhang. Spectral temporal graph neural network for multivariate time-series forecasting. In NeurIPS, volume 33, pp. 17766-17778, 2020.
Gunnar Carlsson. Topology and data. Bulletin of the American Mathematical Society, 46(2), 2009.
Gunnar Carlsson and Rickard Brüel Gabrielsson. Topological approaches to deep learning. In Topological Data Analysis, pp. 119-146. Springer, 2020.
Gunnar Carlsson and Vin Silva. Zigzag persistence. Foundations of Computational Mathematics, 10 (4):367-405, August 2010. ISSN 1615-3375.
Gunnar Carlsson, Vin De Silva, Sara Kališnik, and Dmitriy Morozov. Parametrized homology via zigzag persistence. Algebraic & Geometric Topology, 19(2)6657-700, 2019.
Chih-Chung Chang and Chih-Jen Lin. LIBSVM: library for support vector machines. ACM TIST, 2(3):1-27,20) 2011.
Yuzhou Chen, Ignacio Segovia, and Yulia R Gel. Z-GCNETs: Time zigzags at graph convolutional networks for time series forecasting. In ICML, pp. 1684-1694 PMLR, 2021.
Yuzhou Chen, Yulia Gel, and H Vincent Poor. Time-conditioned dances with simplicial complexes: Zigzag filtration curve based supra-hodge convolution networks for time-series forecasting. In NeurlPS, volume 35, pp. 8940-8953, 2022.
Yuzhou Chen, Miguel Heleno, Alexandre Moreira, and Yulia R Gel. Topological graph convolutional networks solutions for power distribution grid planning. In PAKDD, pp. 123-134. Springer, 2023.
Jae Won Choi, Yuzhou Chen, José Frías, Joel Castillo, and Yulia Gel. Revisiting link prediction with the dowker complex. In PAKDD, pp. 418-430 2024.
Samir Chowdhury, Bowen Dai, and Facundo Mémoli. The importance of forgetting: Limiting memory improves recovery of topological characteristics from neural data. PloS One, 13(9): e0202561, 2018.
11

---

Published as a conference paper at ICLR 2025
Padraig Corcoran and Christopher B Jones. Modelling topological features of swarm behaviour in space and time with persistence landscapes. IEEE Access, 5: 5:18534- 18544, 2017.
Baris Coskunuzer, Ignacio Degovia-Dominguee Yuzhou Chen, and Yulia R Gel. Time-aware knowledge representations of dynamic objects with multidimensional persistence. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 11678-11688 2024.
Vin De Silva and Gunnar E Carlsson. Topological estimation using witness complexes. In PBG, pp. 157-166, 2004.
Tamal Dey and Tao Hou. Computing zigzag persistence on graphs in near-linear time. Leibniz International Proceedings in Informatics, 2021.
Tamal K Dey and Tao Hou. Computing zigzag vineyard efficiently including expansions and contractions. arXiv preprint arXiv:2307.0746. 2023.
Tamal K Dey, Fengtao Fan, and Yusu Wang. Computing topological persistence for simplicial maps.
In SoCG, pp. 345-354, 2014.
Tamal K Dey, Tao Hou, and Salman Parsa. Revisiting graph persistence for updates and efficiency. In WADS, pp. 371 2023.
Yarin Gal, Jiri Hron, and Alex Kendall, Concrete dropout. In NeurIPS, volume 30, 2017.
Jonathan L Gross, Jay Yellen, and Mark Anderson. Graph theory and its applications. Chapman and Hall/CRC, 2018.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. SIGKDD, pp. 855-864, 2016.
Shengnan Guo, Youfang Lin, Ning Feng, Chao Song, and Huaiyu Wan. Attention based spatial- temporal graph convolutional networks for traffic flow forecasting. In AAAI, volume 33, pp. 922-929, 2019.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. NeurlPS, 33: 6840-6851, 2020.
Christoph Hofer, Florian Graf, Bastian Rieck, Marc Niethammer, and Roland Kwitt. Graph filtration learning. ICML, pp.
2020.
Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Rieck, and Karsten Borgwardt. Topological graph neural networks. In ICLR, 2022.
Zhenyu Hou, Xiao Liu, Yukuo Cen, Yuxiao Dong, Hongxia Yang. Chunjie Wang, and Jie Tang. GraphMAE: Self-supervised masked graph autoencoders. In SIGKDD, pp. 594-604, 2022.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. In NeurIPS, volume 33, pp. 221 18-22333,, 2020.
Jachyeong Jo, Seul Lee, and Sung Ju Hwang. Score-based generative modeling of graphs via the system of stochastic differential equations. In ICML,, pp. 10362-10383, 2022.
Megan Johnson and Jae-Hun Jung. Instability of the betti sequence for persistent homology and stabilized version of the betti sequence. arXiv preprint arXiv:2109.092 2021.
Woojin Kim, Facundo Mémoli, and Zane Smith. Analysis of dynamic graphs and dynamic metric spaces via zigzag persistence. Topological Data Analysis, pp. 371-389. Springer, 2020.
Lingkai Kong, Jiaming Cui, Haotian Sun, Yuchen Zhuang, Aditya Prakash, and Chao Zhang. Autoregressive diffusion model for graph generation. In ICML, pp. 17391-17408. PMLR, 2023,
Hao Li, Hao Jiang, Fan Jiajun, Dongsheng Ye, and Liang Du. Dynamic neural Dowker network: Approximating persistent homology dynamic directed graphs. In SIGKDD, pp. 1564-1564, 2024.
12

---

Published as a conference paper at ICLR 2025
Sihang Li, Xiang Wang, An Zhang, Yingxin Wu, Xiangnan He, and Tat-Seng Chua. Let invariant rationale discovery inspire graph contrastive learning. In ICML. pp. 13052-13065, 2022.
Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. Diffusion convolutional recurrent neural network: Data-driven traffic forecasting. In ICLR, 2018.
Lu Lin, Jinghui Chen, and Hongning Wang. Spectrum guided topology augmentation for graph contrastive learning. In NeurlPS 2022 Workshop: New Frontiers in Graph Learning, 2022.
Gang Liu, Eric Inae, Tong Zhao, Jiaxin Xu, Tengfei Luo, and Meng Jiang. Data-centric learning from unlabeled graphs with diffusion model. In NeurIPS, volume 36, 2024.
Gadea Mata, Miguel Morales, Ana Romero, and Julio Rubio. Zigzag persistent homology for processing neuronal images. Pattern Recognition Letters, 62:55-60, 10355-0,220 2015.
Robert A McDonald, Rosanna Neuhausler, Martin Robinson, Laurel G Larsen, Heather A Harrington, and Maria Bruna. Zigzag persistence for coral reef resilience using stochastic spatial model. Journal of the Royal Society Interface, 20(205):20230280, 2023.
Audun Myers, Alyson Bittner, Sinan Aksoy, Dan Best, Gregory Venselman-Petrusee Helen Jenne, Cliff Joslyn, Bill Kay, Garret Seppala, Stephen Young, and Emilie Purvine. Malicious cyber activity detection using zigzag persistence. In IEEE DSC, pp. 1-8, 2023a.
Audun Myers, David Muñoz, Firas A Khasawneh, and Elizabeth Munch. Temporal network analysis using zigzag persistence. EPJ Data Science, 12(1):6, 2023b.
Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang Liu, and Shantanu Jaiswal. graph2vec: Learning distributed representations graphs. arXiv preprint arXiv:1707.05005. 2017.
Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permuta- tion invariant graph generation via score-based generative modeling. In AISTATS, pp. 4474-4484, 2020.
Leslie O'Bray, Bastian Rieck, and Karsten Borgwardt. Filtration curves for graph representation. In SIGKDD, pp. 1267-1275, 2021.
Debashis Paul and Alexander Aue. Random matrix theory in statisties: review. Journal of Statistical Planning and Inference, 150:1-29, 2014.
Dimitris N Politis. The impact of bootstrap methods on time series analysis. Statistical Science, pp. 219-230, 2003.
Yiming Qin, Clement Vignac, and Pascal Frossard. Sparse training of discrete diffusion models for graph generation. arXiv preprint arXiv:231 1..22311..214.. 2023.
Kashif Rasul, Calvin Seward, Ingmar Schuster, and Roland Vollgraf. Autoregressive denoising diffusion models for multivariate probabilistic time series forecasting. In ICML, pp. 8857-8868. PMLR, 2021.
Yulia Rubanova, Ricky TQ Chen, and David K Duvenaud. Latent ordinary differential equations for irreuulrlyysamppled time series. In NeurIPS, volume 32, 2019.
David Salinas, Valentin Flunkert, Jan Gasthaus, and Tim Januschowski. DeepAR: Probabilistic forecasting with autoregressive recurrent networks. International Journal of Forecasting. 36(3): 1181-1191, 2020.
Weici Shao and Pak Kiu Sun. A First Course in Graph Theory. Hong Kong Baptist University, 2014.
Zezhi Shao, Zhao Zhang, Fei Wang, Wei Wei, and Yongjun Xu. Spatial-temppral identity: A simple yet effective baseline for multivariate time series forecasting. CIKM, pp. 4454 4458, 2022.
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mchlhorn, and Karsten M Borgwardt. Efficient graphlet kernels for large graph comparison. In AISTATS, volume 5, pp. 888-495, 2009.
13

---

Published as a conference paper at ICLR 2025
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lchmar graph kemels. JMLR, 12(9), 2011.
Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In ICML, pp. 2256-2265, 2015.
Chao Song, Youfang Lin, Shengnan Guo, and Huaiyu Wan. Spatial-temporal synchronous graph convolutional networks: A new framework for spatial-temport network data forecasting. In AAAI volume 34, pp. 914-921, 2020a.
Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. In ICLR, 2020b.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. In NeurIPS, volume 32, 2019.
Yang Song. Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. ICLR, 2020c.
Fan- Sun, Jordan Hoffman, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi- supervised graph-level representation learning via mutual information maximization. In ICLR, 2019.
Susheel Suresh, Pan Li, Cong Hao, and Jennifer Neville. Adversarial graph augmentation to improve graph contrastive learning. NeurIPS, 34:15920 19933999--993,,, 2021.
Yusuke Tashiro, Jiaming Song, Yang Song, and Stefano Ermon. CSDI: Conditional score-based diffusion models for probabilistic time series imputation. In NeurIPS, volume 34, pp. 24804-24816, 2021.
Andrew Tausz and Gunnar Carlsson. Applications of zigzag persistence to topological data analysis. arXiv: 108.1003. 2011.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In NeurlPS, volume 30, 2017.
Yogesh Verma, Amauri H Souza, and Vikas Garg. Topological neural networks go persistent, equivariant, and continuous. ICML, 2024.
Clement Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard. DiGress: Discrete denoising diffusion for graph generation. In ICLR, 2023.
Fan Wang, Huidong Liu, Dimitris Samaras, and Chao Chen. TopoGAN: A topology-aware generative adversarial network. In ECCV, pp. 118-136, 2020.
Haomin Wen, Youfang Lin, Yutong Xia, Huaiyu Wan, Qingsong Wen, Roger Zimmermann, and Yuxuan Liang. DIFFSTG: Probabilistic spatio-temporal graph forecasting with denoising diffusion models. In SIGSPATIAL, pp. 1-12, 2023.
Daniel S Wilks. Statistical methods in the atmospheric sciences, volume 100. Academic press, 201 1.
Dongxia Wu, Liyao Gao, Matteo Chinazzi, Xinyue Xiong, Alessandro Vespignani, Yi-An Ma, and Rose Yu. Quantifying uncertainty in deep spatiotemporal forecasting. In SIGKDD, pp. 1841-1851, 2021.
Lu Xian, Henry Adams, Chad M Topaz, and Lori Ziegelmeier. Capturing dynamics of time-varying data via topology. Foundations of Data Science, 4(1):1-36, 2022.
Zuoyu Yan, Tengfei Ma, Liangeai Gao. Zhi Tang, and Chao Chen. Link prediction with persistent homology: An interactive view. In ICML, pp. 11659-11669. PMLR, 2021.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In SIGKDD, pp. 3365-1374 2015.
14

---

Published as a conference paper at ICLR 2025
Ling Yang. Zhilong Zhang, Yang Song. Shenda Hong, Runsheng Xu, Yue Zhao, Wentao Zhang, Bin Cui, and Ming-Hsuan Yang. Diffusion models: A comprehensive survey of methods and applications. ACM Computing Surveys, 56(4):1-39, 2023.
Run Yang. Yuling Yang, Fan Zhou, and Qiang Sun. Directional diffusion models for graph represen- tation learning. In NeurlPS, volume 36, 2024.
Kai Yi, Bingxin Zhou, Yiqing Shen, Pietro Liò, and Yuguang Wang. Graph denoising diffusion for inverse protein folding. In NeurlPS, volume 36, 2024a.
Kun Yi, Qi Zhang, Wei Fan, Hui He, Liang Hu, Pengyang Wang, Ning An, Longbing Cao, and Zhendong Niu. FourierGNN: Rethinking multivariate time series forecasting from a pure graph perspective. In NeurIPS, volume 36, 2024b.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph 2020.
contrastive learning with augmentations. In NeurlPS, volume 33, pp.
Bing Yu, Haoteng Yin, and Zhanxing Zhu. Spatio-temporal graph convolutional networks: a deep learning framework for traffic forecasting. In IJCAL, pp. 3634-3640, 2018.
Mengchun Zhang, Maryam Qamar, Taegoo Kang, Yuna Jung, Chenshuang Zhang, Sung-Ho Bae, and Chaoning Zhang. A survey graph diffusion models: Generative ai in science for molecule, protein and material. arXiv:230400156. 2023.
A BACKGROUND ON TRADITIONAL PERSISTENCE
Persistent homology (PH) is a mathematical machinery which allows us to quantify shape of an object along various dimension(s). By shape here, we broadly understand object properties that are preserved under continuous transformation,, i.e. the ones that do not change "holes" in the object. Such transformations include, for example, folding, bending, and twisting; while "holes" can be connected components (0-dim topological features), loops (I-dim topological features), voids (2-dim topological features), and their nigher-dimensiona, counterparts. PH monitors evolution of these topological features as we monotonically change certain user-defined parameters. The idea is to select some suitable monotonic sequence of scales a1 02 .... am, and then to study graph G not as a single object but as a parametrized sequence of nested graphs Gn, S Gn. S E....., S.... = G. recording which holes appear (born) and disappear (die) throughout this filtration. Holes that persist over the filtration (i.e., with longer lifespans) are likelier to contain some essential latent information about the structural organization of G, while holes with shorter lifespans are often referred to as topological noise. To systematize the process of selecting and recording holes, we build an abstract simplicial complex A (Ga.) on each Ga, which results a filtration of complexes X (Ga,) C X (9a.. S .... .. (Ga..) ) and counting the associated simplices in X. As an example of such scale parameter a, we can choose edge weight and then use an abstract simplicial complex X (G.) [g S G)diam (9) S a). that is, we keep only nodes (and the associated induced subgraphs) with a shortest weighted path of at most a. Such X is called Vietoris-Rips complex and the induced nested sequence is called power filtration. (For an overview of various filtration on graphs see AAdass et al. (2017): Bauer (2019; Hofer et al. 2020).) )) As such, this traditional PH framework considers a sequence of linear maps X (Ga,) + X (9...)) .) along the same direction, thereby assuming that each simplicial complex needs to be subset of the following one, allowing us only to add new simplices to the preceding complex. This limits applicability of PH to time-dependent
and dynamic graphs, where the goal is to extract time-aware topological signatures that persist over time.
B PROOF OF PROPOSITION 5.2
Proof. By definition of ZS, we get
| ZS = max 1sksm
ZFCa. (Ati) ZFC,, (Ati)
1=1
15

---

Published as a conference paper at ICLR 2025
where
ZFCan (Ati) Σ WIny" f (185 td,)as.
corresponding to zigzag persistence diagram PDzen and LFC (Ati)l is its counterpart correspond- ing to the perturbed PDz
From Proposition 3.2 of Chen et al. 2002 we have
ZFC (Ati) ZFC,, (Ati) S W, (PDzan PDznn) < Li
Hence,
n
||ZS 160 <
max 1sk
wi W, (PDz PDZoE)
1=1
L max Wi Wi (PDZaa PIZza 1sk5m
Σ
L max Wi (PDzay PDzaa) S Ie, 1sksm
where L = max 1 S nL, and maxiçksm Ck.
C BASELINES AND EXPERIMENTAL SETUP
Baselines. We use the following popular models for spatio-temporal graph forecasting as baselines:
(i) 6 probabilistic methods: (1) Latent Ordinary Differential Equations (ODE) Rubanova et al. (2019)
(2) DeepAR (which is a forecasting method based on autoregressive recurrent neural networks) Sali
al. (2020). (3) Conditional Score-based Diffusion models for Imputation (CSDI) Tashiro et al.
12021). (4) TimeGrad (which is an autoregressive model for multivariate probabilistic time series
forecasting) Rasul et al. (202T), (5) MC Dropout (which uses the MC Dropout Gal al. (2017) for probabilistic spatio-temporal forecasting) Gal et al. (2017);
71:7)):1))) Wu et al. (202I). and (6) DiffSTG (which a non-autoregressive framework) Wen et al. (2023); and (ii) GNN-based models: (1)
Spatio-Temporal Graph Convolutional Networks (STGCN) Yu et al. (2088) Diffusion Convolutional Recurrent Neural Network (DCRNN) Li et al. (2018). Adaptive Graph Convolutional Recurrent Network (AGCRN) Bai et al. (220)), Spectral Temporal Graph Neural Network (StemGNN) Cao et al.
(2020), STID Shao et al. (022), and Fourier Graph Neural Network (FourierGNN) Yi et al. (2024b).
compare our 7S-DM with 15 state-of-the-ard (SOTA) baselines includ- ing: (1) Graphlet Kernel (GL) Shervashidze et al. 20099), (2) Weisfeiler-Lehmee Sub-tree Kernel
For graph classification,
(WL) Shervashidze et (2011) (3) Deep Graph Kernels (DGK) Yanardag Vishwanathan (2015),
(4) node2vec Grover
Adhikari et al. (2018). (6) graph2ved Caaphh2ec(Narayanaaa al. (2017). (7) InfoGraph Sun al. 22199, (8) Graph Contrastive Learning (GraphCL) You et al.
Groverr & Leskoved (2016), (5) Aubkvec(Adhikar
Contrastive Learning (AD-GCL) Suresh et al. (2021), (10) Rationale- aware Graph Contrastive Learning (RGCL) Li et al. (2022), (11) Graph Contrastive Learning scheme with Topology Augmentation guided by the Graph Spectrum (GCL-TAGS)) Lin et (2022), (12) Masked Graph Autoencoder (GraphMAE) Hou et al. (2022). (13) CW Networks (CWN) Bodnar et al.
(2020). (9) Adversarial-Gras
(2021), (14) Topological Graph Neural Networks (TOGL) Horn et al. (2022). and (15) Directional
Diffusion Models (DDM) Yang et al. (024).
D ROBUSTNESS AND SENSITIVITY ANALYSIS
Robustness to Noise and Varying Sizes of Training Data We also perform experiments on reducing the training set from 90% to 80% and 70%. We find that the ZS-DM gains are higher for lower training sizes, i.e. on average for MUTAG and BZR 0.22% for 90% training size (Table main body), 1.58% for 80% training size (Table 9 below), and 1.94% for 70% training size (Table 10 below). Furthermore, variability of DS tends to be noticeably lower than runner up SOTAs, I.c., up to 1.5-2 times lower, suggesting that the ZP idea may be helpful for uncertainty quantification. More
16

---

Published as a conference paper at ICLR 2025
Table 9: Performance comparison of robustness study with 80% training
Model
MUTAG
BZR
AD-GCL
82.16=2.09
80.43=1.55
RGCL
82.77+2.34
81.35+2..00
DDM
83.38+22.85
81.21=1.855
ZS-DM (ours)
84.59=1.47
82.78=1.299
Table 10: Performance comparison of robustness study with 70% training set.
Model
MUTAG
BZR
AD-GCL
79.50=22.23
74.28-
RGCL
80.35=1.68
1.84
DDM
80.78:2.007
76.92+-2.88
ZS-DM (ours)
82.23+1.57
78.58=1004
generally, these findings suggest that the 7S approach is capable of capturing some fine-grained latent information on the graph structure that the more conventional approaches cannot, but the role such finer-grained information diminishes as the sample size increases.
Table 11: Sensitivity graph classification with different choices scales.
Data
degree
betweenness
closeness
MUTAG
91.68110.44
90.70-10.83 83.35=11.93
88 88.40-10.37
BZR 86.20=0.12
82.52-+0.82
Table 12: Performance comparison among 7S features with different dimensions.
Data
0-dim
1-dim
0- & 1-dim
MUTAG
91.68:10.34 BZR 86.20:10.12
88.91=0.47 84.34+0.90
90.17=0.12 85.3
Sensitivity Analysis to the Choice Filtration Scales. Table shows the sensitivity of graph classification results the choice of scales, i.e., using node-degree, node-betweenness, and node- closeness scores. In general, we find that the performance for more homogenous graphs is less sensitive filtrations. For sparser and more heterogeneous graphs, degree- or power filtrations are often the preferred choices. We have also conducted additional experiments to compare ZS and traditional persistence. From Table 7 we observe that our diffusion model with 7S always outperforms with highly statistically significant gains the diffusion model with traditional persistence on both MUTAG and BZR datasets. Additionally, in experiments of graph classification (see Table can incorporate O-dimensional feature, I-dimension feature, both () and I-dimensional features into the model. However, we found that our ZS-DM model with O-dimensional features always outperforms other scenarios. This phenomenon be potentially explained by stronger signal yielded by O-dimensional features and much higher representation of O-dimensional features.
E ADDITIONAL DETAILS OF ZIGZAG SPAGHETTI AND EXPERIMENTS
Zigzag spaghetti has two main advantages: first, allows for capturing essential topological char- acteristics of dynamic object over time at all resolution scales simultancously. and, second, it is easily tractable and computationally efficient (relative to other time-aware topological summaries). To justify the second point, 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):
17

---

Published as a conference paper at ICLR 2025
Table 13: Running time and performance comparison.
Data
ZS-DM (ours)
ZPI-DM
ZFC-DM
MUTAG
0.21 sec 03.4)
0.37 see (90.32+0.63)
0.18 see (90.73=0.59)
Go
5. US
(a)
Go
G1
5z
6 9:th gayy (lrnson Canner wth onteersioess
54
naw Docrn beobdene
Death
(b)
Figure 2: Visualization of zigzag persistence, zigzag persistence diagram and zigzag filtration curves.
In addition, the complexity of zigzag persistence graphs can be improved for subclass of graphs satisfying certain assumptions on the size the unions in the filtration, i.c. of the size of the union of all graphs in the filtration is Qm for any fixed i..., 0 < this is not true for a general class of graphs, and some other more drastic approaches are needed denser graphs. One such potential direction is to
Dey & Hou (2023). However,
to improve scalability of zigzag persistence compute zigzag persistence based only on landmarks rather than on all nodes and then to use Dowker witness complexes. This approach has been yet investigated in computational topology and its theoretical guarantees are yet unknown. We believe though that it is a very promising approach that can fundamentally shift the scalability problem for ZP.
Furthermore, based on Qin et al. (2023), we incorporate its sparse denoising network (which contains graph transformer architecture with 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 From the Table 14 we observe that ZS- ZS-DMnew always outperforms the previous version (i.e., ZS-DMata) on both MUTAG and BZR datasets. Thanks very much for this excellent suggestion for further improvement
ZS approach.
From the Figure (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 I, while there is notable variability among topological characteristics over the time period from time point 0 to time point 3. Furthermore, another notable topological feature observed over the time period 1-2, but its lifespan is relatively short.
Table 14: ZS-DM with sparse denoising network.
Model
MUTAG
BZR
ZS-DMate
90.38
86.20-0.11
ZS- ZS-DM
92.1510.32
86.39-0.10
18


Reviews:
[{"review_id": "aS6evtnFZW", "reviewer": "Reviewer_weuX", "summary": "This paper introduces zigzag spaghetti (ZS), a novel topological summary designed to enhance diffusion models for graph-based generative AI by capturing higher-order topological properties. Using zigzag persistence, ZS extracts key topological descriptors across multiple resolutions in dynamic graphs, addressing limitations in current models' generalizability. Theoretical stability guarantees for ZS are provided, and it represents the first integration of dynamic topological information in graph diffusion models. Experiments across nine benchmark datasets demonstrate that the proposed method improves performance even up to 10%.", "questions": "- 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?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1) The proposed method is very interesting and novel. The paper tackles an important topic introducing concepts from computational topology to generative diffusion models for graphs. The motivation behind the idea is clearly communicated and provided.\n\n2) The paper is well written providing a good introduction to the different concepts adopted in the study.\n\n3) The experimental set-up is very strong including multiple baselines with the method outperforming all of the them across all datasets. Furthermore, there are experiments validating the robustness of the method and the computational cost. The paper is very complete on the experimental set-up", "weaknesses": "1) 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "aumghUwcJH", "reviewer": "Reviewer_HF5K", "summary": "This paper investigates diffusion models on graph generation and prediction. To capture the high-order topological graph properties during diffusion, the authors propose to leverage the zigzag persistence. In particular, a computation-efficient topological summary metric zigzag spaghetti (ZS) is developed over a sequence of graphs at multiple resolutions with theoretical stability guarantees. Experimental results confirm the effectiveness of ZS as a plausible metric for graph diffusion models.", "questions": "Please refer to the weakness part.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper develops a practical method to capture the topological properties of generated graphs at various resolutions.\n\n2. Theoretical stability guarantees are provided.\n\n3. Extensive experimental results confirm the effectiveness of ZS as a plausible metric for graph diffusion models.", "weaknesses": "1. Some illustrations for zigzag persistence and zigzag filtration curves in Section 3 can benefit the convey of the content.\n\n2. Some sentences are not precise, e.g., “M is the number of the” in line 162. Actually, M is a set in the paper.\n\n3. 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.\n\n4. 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.\n\n5. 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.\n\n6. Figure 1 is proposed to illustrate the proposed ZS. I suggest the authors provide the necessary explanations for better clarity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "s25o1zg1B9", "reviewer": "Reviewer_MZ8J", "summary": "This paper addresses the a critical limitation in current graph diffusion models by introducing a novel approach to capture higher-order topological properties. Such higher-order topological properties can be captured using time-aware topological summary zigzag spaghetti (ZS), which leverages zigzag persistent homology. Stability of the obtained ZS has been guaranteed with respect to Wasserstein distance. The paper also introduces zigzag spaghetti-based encoder (ZS-ENC) to incorporate ZS into diffusion models. The applicability of ZS has been tested on various settings demonstrating improvements in different metrics.", "questions": "- What is the difference between $\\mathcal{G}_t$ and $\\mathcal{G}^t$ in Sec. 3?\n- Can you describe how you obtained $\\omega_i$ in Sec. 3.1\n- How is Sec. 4.1 related to the methodology of your paper?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper attempts to incorporate zigzag persistence homology into generative diffusion model.\n- Theoretical stability of zigzag spaghetti has been addressed\n- Applicability of zigzag spaghetti has been demonstrated in different settings", "weaknesses": "The soundness of the paper seems to need a bit of improvement. For instance, notations might need a little more description. ($\\\bomega$ 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (Poster)