HIERARCHICAL EQUIVARIANT GRAPH GENERATION

Authors: Yoann Boget, Pablo Strasser, Alexandros Kalousis
Primary area: learning on graphs and other geometries & topologies
Keywords: graph, generative model, graph generation, hierarchical, coarsening, pooling, lifting, gnn, mpnn, spanning supergraph

Abstract:
Deep learning, and more specifically denoising models, have significantly improved graph generative modeling. However, challenges remain in capturing global graph properties from local interactions, ensuring scalability, and maintaining node permutation equivariance. While existing equivariant models address node permutation issues, they struggle with scalability, often requiring dense graph representations that scale with $\mathcal{O}(n^2)$.

To overcome these challenges, we introduce a novel coarsening-lifting method that generates sparse spanning supergraphs, preserving global graph properties. These supergraphs serve as both conditioning structures and sparse message-passing layouts for generative models. Leveraging this method with discrete diffusion, we model graphs hierarchically, enabling efficient generation of large graphs.

Our approach, to the best of our knowledge, is the first hierarchical equivariant generative model for graphs. We demonstrate its performance introducing new evaluation datasets with larger graphs and more instances than traditional benchmarks.

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

Reviews and discussion:
<thread>
creation date:
1729810178284

thread_type:
official_review

<thread_object>
creator: reviewer_f6xy

<content>
summary:
The manuscript outlines a new approach to graph generative modeling by addressing challenges such as scalability and maintaining node permutation equivariance. Specifically, current denoising models for graph generation face issues in capturing global graph properties from local interactions. Additionally, while existing equivariant models manage node permutation issues, they often struggle with scalability, particularly when dense graph representations with O(n^2) complexity are involved. To overcome these shortcomings, the authors introduce a novel coarsening-lifting method that generates sparse spanning supergraphs. These supergraphs help in preserving global graph properties and are used as both conditioning structures and sparse layouts for MPNN in generative models. By combining this method with discrete diffusion, the model handles graphs hierarchically, improving the efficiency of generating large graphs.

strengths:
This manuscript proposed a novel hierarchical graph generation method. Firstly, it proposes the gamma-min partitioning method to generate the coarse supergraph G, and then spann the G to a spanning-garph H. With the guidance from G and H, the authors employed the diffusion model for generation. In the experiment, this work was comprehensively evaluated on multiple synthetic and real datasets.

weaknesses:
1. This manuscript proposes a hierarchical equivariant graph generation model. Specifically, the generated object is a 2D graph, and the equivariance is guaranteed on the permutation group by using MPNN as the basic building block. However, equivariance is not a major contribution of this work, so it is somewhat overemphasized in the title of the manuscript. Moreover, it is suggested to illustrate the generated object at first.
2. The manuscript is lengthy, and the experiments are comprehensive. However, some sections do not have a critical correlation with the proposed method, such as the invariance and equivariance (which are not the main contributions and stem from the properties of MPNN itself) and the spectral properties (a long analysis with proof but not directly applied to the generation).
3. In contrast to the equivariant property, the generation model lacks sufficient detail. The authors should describe the generation model more clearly, including how the graph is encoded, how the constraints of $G$ and $H$ are applied to the diffusion layer, and what the loss function is.

questions:
1. In this manuscript, the proposed method focuses only on 2D graphs, and the equivariance correspondingly pertains only to permutations. It is confusing when reading the introduction without a clear definition of the graph category.
2. The graph coarsening process, in some ways, appears similar to node clustering. If I cluster the nodes with their neighbors first (or just combined with some neighbors as the supernode), would that lead to similar results compared to the proposed coarsening method? Maybe some ablation experiments will prove that.
3. In Equation (2), the definition of $W$ should be clarified.
4. It is recommended to adjust the content of the manuscript, delete some unnecessary sections amd introduce more details about the generation model, such as how the guidance of the coarsened and spanned graph is employed, and how the model is supervised.
5. It is suggested to present the related work first before introducing your method.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730590963559

thread_type:
official_review

<thread_object>
creator: reviewer_ujpl

<content>
summary:
The paper presents a new approach to graph generation based on discrete diffusion. The method addresses two challenges in graph generative modeling, (1) scalability (2) equivariance. To address these challenges, the authors propose an equivariant coarsening-lifting technique to create sparse spanning supergraphs, which they claim maintain global graph properties. This hierarchical model enables efficient generation of large graphs, and the authors validate their approach by comparing it to existing models across multiple datasets, showing improvements in both performance and speed.

strengths:
1. The usage of a coarsening/lifting technique combined with the hierarchical generation process (in an equivariant manner) is innovative in my opinion.
2. The proposed technique demonstrates competitive results compared to baseline methods.
3. The authors introduce new datasets for larger graphs.
4. The authors provide code to reproduce their results.

weaknesses:
1. The presentation lacks clarity, making it difficult to understand how the model operates -- see questions below.
2. The method requires training a series of generative models, one per coarsen level. This is a weakness in my opinion, since there might be graphs that require a lot of coarsen levels.
3. Although the model shows good results on large graphs, the comparisons with baseline models are somewhat limited by generation speed constraints, leading to fewer generated samples. 
4. The authors use a specific coarsening/lifting technique in their method, which might be a bottleneck in generating certain graphs. See question 2.

questions:
1. Do the authors have any insights on how graph size affects the performance of generation? Specifically, is it more challenging to approximate the probability distribution for larger graphs compared to smaller ones?
2. Do the authors know how to quantify the bottleneck that comes from the fact that a particular coarsening/lifting procedure is used?
3. Does the number of nodes remain fixed throughout the entire training/sampling process? From my understanding, the diffusion process is trained independently at each coarsening level. At what point during training/generation does the number of nodes change?
4. What is the number of coarse levels (L) used in the experiments, and how does it affect performance?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730684548036

thread_type:
official_review

<thread_object>
creator: reviewer_nqur

<content>
summary:
The paper propose a hierachical graph generation models. The idea is to train a partition model to partition graphs into a multiple components, where each component corresponds to a super node. The partition model helps identify components that edges mostly reside within. Then a diffusion model is applied on the components individually to avoid considering all N^2 node pair when formulating the generative models. The method claims to improve sampling speed since the number of variables to be modeled decreases.

strengths:
1. The propose method has great intuition and the methods used to address graph shrinking are reasonable and convincing

2. The derivation is rigorous and I didn't spot any obvious error.

3. Experiment result seems to be superior over baselines.

weaknesses:
1. The illustrative figures are a little confusing, I am not sure how the graph is lifted during the generation. Clarity need to be improved.

2. Followup question on 1. In the paper it mentions the modeling only happens intra-cluster edges, are you not considering inter-cluster edges? If so, what's the limitation of the assumption.

3. Typo in line 456: DGSS -> GDSS. 

4. Metrics used in experiments are outdated, for example, MMD from GraphRNN are still used in here. I suggest using more metrics that better reflects the generated graph statistics.

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

</thread>
<thread>
creation date:
1730695550275

thread_type:
official_review

<thread_object>
creator: reviewer_nwtl

<content>
summary:
The paper introduces a hierarchical equivariant generative model for graphs using a graph coarsening-lifting method and discrete diffusion. This approach aims to address challenges including scalability and node permutation equivariance. The authors claim significant improvements in generating large-scale graphs with efficient training and inference. Empirical validation is provided through experiments on standard benchmarks and newly proposed large datasets.

strengths:
The proposed coarsening-lifting method preserves global graph properties, enabling efficient generation of large graphs while maintaining node permutation equivariance. The empirical results demonstrate the method’s strong performance on various datasets, including newly introduced large-scale graph datasets.

weaknesses:
1. While the hierarchical framework is compelling, training separate generative models at multiple levels increases overall complexity and may pose challenges in terms of training and hyperparameter tuning. The partitioning method also relies on training a GNN and there are no experiments verifying if this is more effective than simpler partitioning methods.
2. The descriptions of the proposed method seem quite vague and informal, which make the paper generally hard to follow. For example, how to formally define global graph information, why equivariant models can not capture that, what is the formal definition of spanning supergraph (definition in proposition 1 looks like a tautology, i.e. for any graphs $G$ and $G'$ we have $G = G' + (G\backslash G')$), etc.
3. There is no ablation study on individual components of the proposed method (such as the architectural choices, the partitioning method) or discussion about hyperparameters (such as how $L$ and diffusion steps affect the performance and efficiency).
4. The novelty seems limited given existing permutation equivariant discrete generative models for graphs [1,2]. The authors might want to provide more detailed comparisons.

[1] Efficient and degree-guided graph generation via discrete diffusion modeling, 2023

[12 Sparse training of discrete diffusion models for graph generation, 2024

questions:
See above
</content>
</thread_object>

</thread>
<thread>
creation date:
1730739306285

thread_type:
official_review

<thread_object>
creator: reviewer_zmrk

<content>
summary:
The authors of this paper introduce a hierarchical approach for graph generation using graph coarsening and discrete diffusion. The authors introduce a novel "coarsening-lifting" method that creates spanning supergraphs to model global graph properties at each hierarchical level, improving scalability and capturing global structure. They evaluate their method against other graph generative models and achieve promising results on multiple datasets.

strengths:
- One of the strongest points of the paper is the scalability of the proposed methods. Usually, graph generators struggle with large graphs, as they have quadratic complexity. By leveraging sparse supergraphs for message-passing, the model reduces this complexity, achieving lower generation time for the graphs.

-   The experimental results are strong, outperforming previous several state-of-the-art methods. The model demonstrates better performance, faster graph generation, and lower memory consumption, which is especially apparent with larger datasets.

- Hierarchical graph generation is an interesting and important research direction, as it can better capture the hierarchical patterns in various graph datasets.

weaknesses:
- A weak point of the paper is that it doesn’t sufficiently motivate the hierarchical generation approach beyond its computational efficiency. While reducing computation costs is a valuable advantage, hierarchical generation could offer additional benefits, such as enhanced model interpretability or improved capture of multi-scale graph structures. The paper would be stronger if it discussed these potential benefits in more detail, especially how hierarchical modeling might help in applications with hierarchical graph patterns.

- Even if the paper acknowledges the lack of conditional generation, I think it is important to include some preliminary results or ideas on how to extend the current method with conditioning. In practical applications, generating graphs conditioned on specific properties (e.g., molecule properties) is often necessary.

- Another weak point is the lack of visualizations for the generated graphs. Visual comparisons between generated and real graphs would further improve the evaluation process. Graph visualizations could also help illustrate how well the hierarchical coarsening-lifting process preserves essential features at each level.

- The training time is missing for the results, and only the generation time is included.

questions:
- Could the authors elaborate on the use for hierarchical generation, aside from computational cost reduction? Specifically, how the proposed method can better model and generate graph structures with hierarchical patterns? 

- How the authors would extend their method to conditional graph generation?

-  Could the authors provide visual comparisons between generated and real graphs?

-  Could the authors provide training time for their method and the baselines across different datasets?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732533385988

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
Dear Reviewers,

We sincerely appreciate your constructive suggestions and would like to thank you warmly for your thorough and insightful comments and questions. We strongly believe your feedback has significantly improved our article.

**We have now updated our article** and kindly encourage you to take a look at the revised version.

Below is a summary of the changes we have made:

- **Paper Presentation and Clarity**:
  - Extended and clarified the explanation of the generative process.
  - Added detailed explanations on the graph lifting process during generation.
  - Clarified the link between the Propositions and our generative model.
  - Further motivated the hierarchical approach.
  - Reorganized the *Related Work* section to appear before the model presentation.
  - Enhanced the motivation for our coarsening algorithm and positioned it with respect to other coarsening methods.

- **Additions Following Your Suggestions**:
  - An ablation study on the number of levels.
  - An experimental comparison between our clustering method and two baseline models.
  - An explanation of how to use our model for conditional generation.
  - Visualizations of preprocessed and generated graphs.
  - Training times for our experiments.
  - A detailed comparison with two other sparse equivariant models, SparseDiff and EDGE.
  - Minor corrections, including typos and clarification of Equation 2.

We are also working on further improving the paper with the following planned updates:

- Adding an experiment on conditional graph generation.
- Enhancing the readability of Figure 1.

Once again, we thank you for your valuable feedback, which helped us in improving the quality of our work.

Best regards,  
The authors
</content>
</thread_object>

</thread>
<thread>
creation date:
1732789749166

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
Dear Reviewers,

**We have updated our article** and kindly encourage you to review the revised version.

In addition to the previous updates, we have:

- Included a new experiment on conditional graph generation.
- Improved Figure 1.
- Added additional visualizations, including those for the conditional model.
- Clarified the type of graphs we generate (2D) and provided additional details on the generation of graph attributes, such as bond types and atom types.

We take this opportunity to highlight the key contributions of our paper:

- We propose a new hierarchical generative model that scales to large graphs and, to the best of our knowledge, is the first graph generative approach that is both hierarchical and equivariant.
- Our model is faster in both training and generation while achieving better performance in capturing graph distributions compared to baselines.
- Our method inherently provides a conditional generative framework for structure-guided graph generation, enabling effective spectrum-conditioned generation.
- We introduce a novel graph coarsening method to produce minimal spanning supergraphs, which serve as conditioning structures and as sparse frameworks for generation.
- We prove that our coarsening method maximizes the sparsity of the conditioned structure while preserving important spectral properties. Experimentally, we demonstrate that our approach outperforms existing coarsening baseline methods.
- We present new datasets with more instances and larger graphs, enabling more comprehensive evaluation of graph generative models.

Although the revision period has ended, we would greatly appreciate your feedback on the revised version if you have not yet provided it.

Once again, thank you for your thorough and insightful comments and questions. We firmly believe your feedback has significantly improved our article.

**Best regards,**  
The authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
1, This paper presents a hierarchical graph generation model for (2D) graph generation, addressing two issues, scalability and equivariance. An equivariant coarsening-lifting technique is developed to create sparse spanning supergraphs,  to model global graph properties at each hierarchical level. Although the idea of hierarchical generation is not new enough, combining the sparse-spanning supergraphs delivers some value to the community. However, many concerns remain, including the weak motivation of the hierarchical fashion especially considering the efficiency issue, limited novelty (especially the permutation equivariance has been extensively studied, and the used MPNN seems to naturally achieve this, the lack of technical details, the lack of necessary condition generation results, independent training of each hierarchical level, etc. Also, the authors failed to revise the manuscript in a timely manner, and many suggested comments are not reflected in the current version. Given these considerations, I feel the paper is not ready to publish in its current state.