Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes an autoregressive diffusion model (ARM) that leverages the absorbing discrete diffusion as the diffusion process on graphs. Since node ordering is involved in the diffusion process, the generative process needs to learn the reversed node ordering for the graph generation. The paper exploits the objective function in the KL divergence and uses a reinforcement learning procedure to bypass the inference complexity. Empirical results demonstrate superior performance compared with baseline methods.
strength_and_weaknesses: 1. This paper introduces a discrete autoregressive diffusion process on graphs that is exchangeable in node ordering. The number of steps required is proportional to the number of nodes, thus improving sampling efficiency over previous graph sampling methods.

2. The paper resolves the node ordering inference problem involved in the inference process by exploiting the variational lower bound property. The method is similar to "Order matters: probabilistic modeling of node sequence for graph generation." by (Chen et al. 2021). 

3. Empirical results demonstrate superior performance in generation quality and time complexity.

Weaknesses:
1. The paper does not clearly explain the "optimal node generation ordering" learned from the posterior. An example demonstrated in Figure 3 in the appendix shows that GraphRAM tends to generate one community and then generate the other community. But more insight is required to check why that ordering is preferred in GraphRAM.
clarity,_quality,_novelty_and_reproducibility: This paper is clearly written. The proposed autoregressive diffusion model is new, but the inference algorithm, especially the node ordering inference part, is similar to Chen et al. 2021.
summary_of_the_review: This paper proposes a diffusion process on discrete graphs that derives an autoregressive generative process with inferred node ordering. Empirical results are good, but my concern is its similarity with previous node ordering inference algorithms.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: - This paper proposed an autoregressive diffusion-based graph generation model. 
- Its performance outperforms SOTAs. 
- GRAPHARM also has low complexity.
strength_and_weaknesses: ### Strength 
- This paper gives a new method for the graph generation.
- The well-designed model obtains better performance.

### Weaknesses
- It does not well explain what autoregressive diffusion is.
- Theoretical analysis is not sufficient
clarity,_quality,_novelty_and_reproducibility: Clarity, Quality, Novelty And Reproducibility are good.
summary_of_the_review: - This paper gives a new method for the graph generation.
- The well-designed model obtains better performance.
review_title: null

final_score: rating: 1: strong reject
review_content: summary_of_the_paper: The paper proposes a new graph generative model based on an autoregressive diffusion model. It shows good performances in a list of tasks. 
strength_and_weaknesses: Strength: 

+ the new model has a formulation of autoregressive diffusion model. 
+ the model is very efficient
+ the model shows good generation performances in a list of tasks. 

Weaknesses

- Though the formulation is motivated differently, it has a large overlap with (Chen et al., 2021). The diffusion ordering network is roughly the same as the variational distribution of node orders in (Chen et al., 2021). The variational lower bound is also very similar to (Chen et al. 2021). The difference is actually because this work neglects the difference between graph sequences and node orders: a graph sequence is not equivalent to a node ordering, which is analyzed by (Chen et al., 2021). 
- The generative procedure is also similar to the standard autoregressive generative procedure: every time adding a new node and the edges connecting to this new node. I don't see the benefit of describing this procedure using the diffusion process. 
- There are several flaws in the analysis. The first one is the difference mentioned above, then the variational lower bound is not exactly correct. The second one is the complexity of generation: the complexity of this model should still be O(n^2) (the analysis below equation 2). Anyhow the model needs to make a decision for each node pair. The running time is saved by reducing the number of calls of neural networks (from O(n^2) to O(n)). 

[After a careful study of the submission and a discussion with authors], I find a critical derivation error in the submission. In particular, the submission bases its derivation on equation 8, which is from (Chen et al., 2021), but the term $p(G_{1:n}, \sigma_{1:n})$ in this submission is different from that in the previous work, so the derivation is incorrect.   
clarity,_quality,_novelty_and_reproducibility: 
The description of the diffusion process can be clearer. For example, the definition of "Absorbing Node State" seems to indicate that a node enters the absorbing state after/because it is masked and connected to other nodes with masked edges. But actually, the diffusion process puts the node to an "absorbing node state" -- as a consequence, it is masked and connected to other nodes with masked edges. 

[After discussion], the notation system in this submission is not well defined. It should follow previous work and use adjacency matrices to derive probabilities. 
summary_of_the_review: The work devises a new graph generative model from the perspective of autoregressive diffusion models. However, it does not seem to add much to the original formulation. The model design is a contribution: it is efficient and shows good performance in several tasks. 

[After discussion:] the notation system of the submission is not well defined, and the derivation is problematic.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors proposed an autoregressive diffusion model for the graph generation. A node-absorbing diffusion process was introduced. For the forward diffusion a diffusion ordering network was suggested, and for the reverse diffusion a denoising network was designed. These two networks can be trained jointly with a simplified log-likelihood loss. Experiments have shown the competitive results of the proposed method when compared to several existing methods. 
strength_and_weaknesses: Strength:

A new node-absorbing diffusion process has been introduced, and a data-dependent ordering can be learned via the optimization. The proposed method has been compared with several SOTA methods and shown its competitive results including the generation time.



######################

Weaknesses:

. Section 2: The authors mentioned that the absorbing diffusion is the most promising generation method. Can you add some explanation on that?

. Section 3.1: The diffusion ordering network produces the probability of the node at time t via equation (1). Can you explain why such an ordering would reflect the topology/regularities of the graph?

. Section 3.3: The proposed training objective has ignored the KL-divergence term in equation (3). Can you evaluate such approximation error, ie. calculate the actual KL-divergence and check whether it indeed approaches zero?

Experiments:

. Table 1: The performance of the proposed GRAPHARM on Cora is not competitive. Can you explain that?

. Effect of Diffusion Ordering: Can you illustrate the proposed ordering visually to give a sense that it does reflect the topology/regularities of the graph when compared to the random ordering? 

clarity,_quality,_novelty_and_reproducibility: Clarity and Quality: The presentation of this paper is good.

Novelty: An autoregressive diffusion model has been proposed for the graph generation, where a proper ordering can be learned via training. 

Reproducibility: The authors have provided details about the training parameters and network architectures in the appendix. These would help to reproduce the experimental results.  
summary_of_the_review: The authors proposed an autoregressive diffusion model for the graph generation. The analysis is solid and the proposed method has been compared with several SOTA methods and showed its competitive performance. The paper can be further improved by adding more explanations and discussions (see the comments in Weaknesses above).
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes an autoregressive diffusion model (GraphArm)  for graph generation, based on the standard diffusion model paradigm with two separate forward and reverse diffusion processes. During training, the forward process incrementally masks nodes of the graph, connecting each masked node with all the other nodes. The forward process thus ends with a full-connected graph of masked nodes. A “denoising network” is then trained to recover the original graph, starting from the node masked last.
 
A key design choice in the forward process is how to set the order of nodes being masked. Instead of uniform sampling of possible orders, the authors propose a “diffusing ordering network” to learn the optimal order. This diffusion ordering network is jointly trained with the denoising network using a log-likelihood objective. Experiments on six different graphs suggest that GraphArm outperforms or matches strong baselines.
 
The reviewers agreed that the paper is well-written (reviewers EBHG and KoQP), the results are promising (reviewers EBHG, dB1j, and KoQP), and the proposed method has certain novelty (reviewers dB1j and KoQP). On the other hand, some reviewers (EBHG and KoQP) pointed out the similarities of the proposed method to previous work (Chen et al., 2021).  Also, serious concerns were raised and debated intensively by a reviewer (dB1j) on the correctness of some proofs/formula in this paper.
 
During the rebuttal, the authors addressed these concerns with extensive discussions, and submitted a revised version with additional theoretical analysis. The AC carefully checked those discussions, and recommended a (weak) rejection, or a conditional acceptance if no other borderline papers looked stronger.


justification_for_why_not_higher_score: See the summary of the Summary Of AC-reviewer Meeting.
justification_for_why_not_lower_score: See the summary of the Summary Of AC-reviewer Meeting.
Decision: Reject