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

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 2011). The extracted zigzag topological information can be then conveniently summarized in a form of zigzag persistence image or zigzag filtration curves (Chen et al., 2021; 2022). Such summaries satisfy the conditions of Lipschitz continuity and, as such, are suitable as input to a 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. (2022) 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 ZP on graphs have been obstructing broader applicability of ZP and keeping it largely as a theoretical concept in algebraic topology, albeit a number of recent studies demonstrating the ZP potential in ecology, engineering, and social sciences (