Topology-aware Graph Diffusion Model with Persistent Homology

Authors: Joonhyuk Park, Donghyun Lee, Yujee Song, Guorong Wu, Won Hwa Kim
Primary area: learning on graphs and other geometries & topologies
Keywords: Graph Generation, Diffusion, Topology, Brain Network

Abstract:
Generating realistic graphs presents challenges in estimating accurate distribution of graphs in an embedding space while preserving structural characteristics such as topology. However, existing graph generation methods primarily focus on approximating the joint distribution of graph nodes and edges, overlooking topology-wise similarity hindering accurate representation of global graph structures such as connected components and loops. To address this issue, we propose a topology-aware diffusion-based graph generation method that aims to closely resemble the structural characteristics of the original graph by leveraging persistent homology from topological data analysis (TDA). Specifically, we suggest a novel loss function, Persistence Diagram Matching (PDM) loss, which ensures the generated graphs to closely match the topology of the original graphs, enhancing their fidelity and preserving essential homological properties. Also, we introduce a novel topology-aware attention to enhance the self-attention module in the denoising network. Through comprehensive experiments, we demonstrate the effectiveness of our approach not only by exhibiting high generation performance across various metrics, but also by demonstrating a closer alignment with the distribution of topological features observed in the original graphs. In addition, application to real brain network data showcases its versatility and potential for complex and real graph application.

Decision: reject
Reviewer scores: 5, 5, 6, 3

Reviews and discussion:
<thread>
creation date:
1730709006140

thread_type:
official_review

<thread_object>
creator: reviewer_6rdp

<content>
summary:
The paper introduces a topology-aware graph generation method called TAGG that incorporates persistent homology into diffusion models to preserve structural characteristics of graphs. The authors propose two main technical contributions: a persistence diagram matching (PDM) loss that ensures generated graphs match the topology of original graphs, and a topology-aware attention mechanism that enhances the self-attention module by incorporating homological features. The method is evaluated on various datasets, with a particular emphasis on brain network generation.

strengths:
The technical execution of the work is solid and thorough. The empirical evaluation is comprehensive, with extensive comparisons against baselines and multiple visualizations. The application to brain network generation is interesting, as it addresses a real-world problem where topological features are crucial. The authors also provide detailed ablation studies.

weaknesses:
The paper's primary limitation lies in its incremental nature and lack of theoretical depth. The core diffusion framework is heavily based on existing work (Vignac et al., 2023), and the integration of persistent homology, while useful, represents an incremental advance rather than a fundamental breakthrough. The topology-aware attention mechanism is essentially a straightforward modification of standard attention by incorporating topological features. And it is not clear why such topological based representations or vectorizations are differentiable and can be trained in an end-to-end generative model. The paper lacks theoretical analysis of why topology-awareness improves generation and provides no theoretical guarantees about topological preservation. The computational overhead of computing persistent homology is not adequately addressed, which could be significant for larger graphs. Additionally, the novelty is limited as the use of persistent homology in graph analysis has been explored in previous works (e.g., Hofer et al., 2020), and the paper doesn't clearly articulate how their approach fundamentally differs from these previous applications.

questions:
- How does the computational complexity scale with graph size, particularly considering the overhead of computing persistent homology? How does the method perform on very large graphs, and what are the main scalability challenges?
- The topology-aware attention mechanism uses pre-computed homological features during training, but how sensitive is the performance to the choice of filtration function used to compute these features?
- Are these topology-aware attention and persistence diagram matching loss differentiable or able to be trained end-to-end?
- What new features are learned through proposed methods? Is there any way to illustrate related hidden representations?
- Could this approach be extended to dynamic graphs where topology evolves over time?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730906629202

thread_type:
official_review

<thread_object>
creator: reviewer_m97e

<content>
summary:
This work introduces a persistence diagram matching loss, which aligns the generated graphs’ topology with that of the target, and a topology-aware attention mechanism within the denoising network. By capturing homological structures, this work aims to better replicate global structural characteristics like connectivity and loops, making it suitable for complex applications.

strengths:
1. The proposed idea is interesting.
2. Demonstrated application in real-world brain networks illustrates TAGG’s adaptability to complex, topologically rich datasets.

weaknesses:
1. A thorough complexity analysis of the graph generation process, including the persistent homology component, is essential. Given that this approach may be computationally intensive, providing a comparative analysis with existing baselines would be highly beneficial. This analysis should include a discussion on both time complexity and resource requirements, considering its practical feasibility for large datasets and real-world applications.
2. The paper’s introduction of the topology-aware diffusion approach is distinct. However, a clearer differentiation from [1] is necessary. The authors should emphasize the conceptual advancements over DiGress in terms of preserving global topological features through persistent homology. It would also strengthen the paper to discuss how this method aligns or contrasts with other homology-based approaches in TDA applications for graphs, which are briefly mentioned in the related work section.
3.  Table 3 provides a quantitative comparison between TAGG and baseline models across multiple datasets using MMD metrics. However, the analysis could benefit from a more detailed interpretation. For instance, while TAGG shows improved performance on various datasets, the significance of the metric differences, especially on small-scale graphs, could be expanded upon. Additionally, a discussion on how TAGG’s improvements in clustering and orbit metrics correlate with enhanced topological fidelity would offer a deeper understanding of the model’s strengths.

[1] Vignac, Clement, et al. "Digress: Discrete denoising diffusion for graph generation." arXiv preprint arXiv:2209.14734 (2022).

questions:
See Weakness.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731240142036

thread_type:
official_review

<thread_object>
creator: reviewer_aeeb

<content>
summary:
This paper introduces a novel graph generation method that utilizes persistent homology within a diffusion model, enhancing structural characteristics. The proposed Persistence Diagram Matching (PDM) loss, in conjunction with the 1-Wasserstein distance, significantly improves the model's topological awareness. The approach extends its application to complex brain network data, demonstrating its effectiveness in real-world scenarios.

strengths:
Pros

1. The proposed method differs from traditional self-attention models by incorporating persistent homology encoding and the use of Q in the forward process, addressing the structural characteristics of graphs.
2. The denoising model integrates the 1-Wasserstein distance to introduce a new loss function (PDM), which is highly versatile and effectively enhances the model's structural awareness.
3. The application range is extended from traditional graphs to brain data with structural features, demonstrating the method's effectiveness on complex real-world datasets.

weaknesses:
Cons

1. As a self-attention model, the paper does not clarify the costs associated with introducing attention mechanisms with mu and training multiple models.
2. The evaluation lacks diverse metrics for comparing graph properties, limiting a comprehensive assessment of model performance.
3. As a generative model, it should generate similar graphs without prior conditions. Here, mu and Q are given to generate the graph, this would naturally make the graph tend to have those similar mu and Q? If so, how to obtain the mu and Q for the graph to be generated? If mu and Q of the test graph themselves are used during the test process, this will make the generated result naturally close to the original graph. If use training ones this would lead to bias? 
4. While the loss function emphasizes degree distribution, this leads to the model showing the most significant improvements in degree metrics, while performance on other indicators is less pronounced.

questions:
Please refer to Cons.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731303003198

thread_type:
official_review

<thread_object>
creator: reviewer_znwp

<content>
summary:
This paper introduces a topology-aware diffusion-based method for realistic graph generation, aiming to preserve structural characteristics similar to the original graphs. The authors propose a novel approach that integrates topological data analysis (TDA), specifically using persistent homology, to guide the generation process. They introduce a new loss function Persistence Diagram Matching (PDM) loss that ensures the generated graphs closely align with the topology of the original graphs, thereby improving fidelity and preserving essential homological properties. Additionally, a topology-aware attention mechanism is developed to enhance the self-attention module in the denoising network.

strengths:
1. This paper addresses the challenge of existing graph generation methods failing to preserve topological information by proposing  a novel topology-aware graph generation method that yields homologically similar graphs with high fidelity.
2. This paper demonstrates the effectiveness of the proposed approach through comprehensive experiments, exhibiting high generation performance across various metrics and aligning better with the distribution of topological features observed in the original graphs.

weaknesses:
1. The paper does not adequately address the relationship between the Preliminaries and the Methodology, making it challenging to follow. Section 3 introduces many topological concepts, which can be frustrating if understanding them is required to proceed with reading. However, Section 4 did not specifically clarify how to apply these topological concepts. This gives me the feeling that there is no need to understand the various topological concepts mentioned in Section 3.
2. Motivation is not convincing enough. The main contribution of this paper is to maintain the topological features of the original graph during the graph generation process. However, it does not analyze the existing methods' capability in capturing topological invariance characteristics.
3. The paper focuses on graph structure information and proposes a topology-aware diffusion-based graph generation method. However, the generalization ability to small graph data: the performance improvement of the model on small graph datasets (e.g., Ego-small) is not obvious, which may indicate that the generalization ability of the model on small graph data needs to be improved. Although the model aims to recover the original graph structure from noisy graphs, how sensitive and robust it is to noise is not detailed in the text. In practice, different noise types and intensities may have an impact on model performance.

questions:
Please refer to weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732173810202

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Comments to all reviewers

comment:
Dear Reviewers,

We would like to express our sincere gratitude for your thorough and constructive reviews. We appreciate the recognition of our contributions, practical applicability, and the validation provided through comprehensive experiments highlighted by the reviewers as:

- **Novel approach :**
  - This paper addresses the challenge of existing graph generation methods … by proposing a *novel topology-aware graph generation method* that yields homologically similar graphs with high fidelity.” (Reviewer zNwP)
  - The proposed method *differs from traditional self-attention models* by incorporating persistent homology encoding and …  a *new loss function (PDM), which is highly versatile and effectively enhances* the model's structural awareness. (Reviewer aEEb)
  - The technical execution of the work is *solid and thorough*. (Reviewer 6rDp)

- **Application on the complex real-world dataset :**
  - Demonstrated application in real-world brain networks illustrates *TAGG’s adaptability to complex, topologically rich datasets*. (Reviewer m97e)
  - The application range is extended from traditional graphs to brain data with structural features, demonstrating the method's *effectiveness on complex real-world datasets*. (Reviewer aEEb)
  - The application to brain network generation is interesting, as *it addresses a real-world problem where topological features are crucial*. (Reviewer 6rDp)

- **Comprehensive experiments :**
  - This paper demonstrates the effectiveness of the proposed approach through *comprehensive experiments*, exhibiting *high generation performance across various metrics* and aligning better with *the distribution of topological features* observed in the original graphs. (Reviewer zNwP)
  - The empirical *evaluation is comprehensive*, with extensive comparisons against baselines and multiple visualizations. (Reviewer 6rDp)
  - The authors also provide *detailed ablation studies*. (Reviewer 6rDp)

---

We also take the reviewers’ concerns seriously, and we will try to fully address all the concerns. We truly hope that our rebuttal clarifies critical issues and helps the reviewers gain a better understanding of our work, possibly leading to a more favorable consideration for the acceptance of this paper. We welcome further discussion during the rebuttal period, so please feel free to leave any comments. We address some common concerns below:


**1. Contribution**

**A)** In our humble opinion, our contributions with respect to the core idea and concept are non-trivial although technical modification may be incremental. The main contribution of our work lies on graph generation with topological fidelity, which is crucial in real-world applications e.g., brain network modeling. To the best of our knowledge, this is the first work to examine graph generation tasks through the lens of persistent homology, validated by comprehensive experiments conducted both qualitatively and quantitatively (which the reviewer pointed as a strength).  

Specifically, unlike the existing approaches, our method uniquely captures the homological features across the entire filtration of a graph, rather than focusing solely on the final subgraph, i.e., the original graph. Moreover, our approach incorporates these homological features to ensure topological preservation during the generation process.  

As shown in Table. 1 and Figure. 5 and 6, our model generates high-fidelity graphs, with quantitative results (Table. 1) and qualitative results (Figure. 5 and 6). While some baselines perform competitively on MMD metrics, TAGG empirically demonstrates a clear advantage on topology-based metrics, i.e., ATOL and Mean Landscape, highlighting our ability to perverse the topological characteristics.

**2. Experimental analysis**

**A)** We have included additional experimental analyses in Appendix D. Specifically, Appendix D.1, D.2, and D.3 provide a detailed discussion of the ablation studies on the homological feature $\mu$ and PDM loss, the impact of different filter functions, and the generalizability of our method to small and large graph datasets, respectively.
</content>
</thread_object>

</thread>


Metareview: