GraphRCG: Self-Conditioned Graph Generation

## Abstract

Abstract Graph generation aims to create new graphs that closely align with a target graph distribution. Existing works often implicitly capture this distribution by aligning the output of a generator with each training sample. As such, the overview of the entire distribution is not explicitly captured and used for graph generation.
In contrast, in this work, we propose a novel self-conditioned graph generation framework designed to explicitly model graph distributions and employ these distributions to guide the generation process.
We first perform self-conditioned modeling to capture the graph distributions by transforming each graph sample into a low-dimensional representation and optimizing a representation generator to create new representations reflective of the learned distribution. Subsequently, we leverage these bootstrapped representations as self-conditioned guidance for the generation process, thereby facilitating the generation of graphs that more accurately reflect the learned distributions.
We conduct extensive experiments on generic and molecular graph datasets.
Our framework demonstrates superior performance over existing state-of-the-art graph generation methods in terms of graph quality and fidelity to training data.

## 1 Introduction

The task of generating graphs that align with a specific distribution plays a crucial role in various fields such as drug discovery [], public health [], and traffic modeling []. In recent times, deep generative models have been prevalently studied to address the problem of graph generation. Unlike conventional methods that rely on random graph models, recent methods generally learn graph distributions through advanced deep generative models, e.g., variational autoencoders (VAEs) [, ], generative adversarial networks (GANs) [, ], normalizing flows [, ], and diffusion models [, , ].
These models excel at capturing complex structural patterns in graphs, enabling the creation of new graphs with desirable characteristics.

Despite these advances, the precise modeling and utilization of graph distributions, although crucial for high-fidelity generation, remains underexplored.
In fact, it is essential to accurately capture and utilize important patterns in the training data for generation [, ], particularly in complex scenarios like molecular graph generation []. For example, precise modeling of molecular properties is key to optimizing molecular structures while maintaining similarity to known molecules. However, the prevalent strategy is to use reconstruction loss to implicitly embed graph distribution within the generator, which may compromise effectiveness.
Moreover, the utilization of the captured graph distributions is also less investigated. Ideally, generators should be designed to explicitly guide the generative process, ensuring that the output graphs closely follow the defined graph distributions. Nonetheless, existing research tends to rely on simple features to control generation, such as molecular characteristics [] or degree information []. Such a strategy requires domain knowledge to design the specific features, while also lacking more comprehensive modeling of the entire distribution. Therefore, the study of graph generation is confronted with two crucial research questions (RQs): (RQ1) Capturing Distributions. How to precisely capture the graph distribution with rich information helpful for the generation process? (RQ2) Utilizing Distributions. How to adeptly harness these distributions as direct guidance for the generation of graphs? Addressing these challenges is essential for high-fidelity graph generation.

Figure: Figure 1: The comparison between the conventional framework and ours. Instead of directly learning the graph distribution, we encode graphs into representations, and learn their distributions for further utilization during generation.
Refer to caption: extracted/5739351/img/framework.png

In practice, however, the above research questions present significant challenges due to the intricate nature of graph data.
(1) Complex Dataset Patterns. Real-world graphs, such as social networks [] and molecular structures [], exhibit highly complex patterns. These include varying degrees of sparsity, inconsistent clustering coefficients, and specific distributions of node and edge attributes []. Capturing these complex patterns accurately through generative models can be particularly challenging.
(2) Progressive Alignment to Training data. Unlike images, where generation is often treated as a pixel-wise or patch-wise process [, , ], the generation of graphs is inherently sequential [, , ]. That being said, graphs are generated through a sequence of steps, each with significant implications, such as modifying chemical properties via the addition or removal of atoms and bonds [, , ].
As a result, it is suboptimal to directly guide generation toward true distributions, particularly in the initial steps of the process with graphs largely deviating from the learned distribution.

To deal with these two challenges, in this work, we introduce a novel graph generation framework named GraphRCG, which targets at Graph Representation-Conditioned Generation. As presented in Fig. 1, our framework is designed to first encode graphs into representations, and then capture and utilize such representation distributions for graph generation. By operating on representations instead of directly on graphs, we manage to effectively distill complex, dataset-specific knowledge into these representations and also enable their further utilization for graph generation.
GraphRCG is built upon two integral components: (1) Self-Conditioned Modeling. To capture graph distributions while addressing the issue of complex dataset patterns in RQ1, we propose to model the essence of graph distribution through a representation generator, which could produce bootstrapped representations that authentically reflect the learned distribution. This strategy is able to enhance the quality of captured graph distributions by encapsulating the complex patterns in a parametrized manner. Moreover, the design also enables the subsequent utilization of captured distributions for generation through sampling diverse representations. (2) Self-Conditioned Guidance. We utilize the acquired distributions to guide graph generation to ensure the fidelity of generated graphs regarding the learned distributions. Regarding RQ2, to overcome the challenge of discrete sequential generation, we introduce a novel strategy of step-wise guidance. This strategy employs bootstrapped representations with varying degrees of noise throughout different steps of graph generation, guiding each step closer to the learned distributions in a progressive manner while obviating the need for additional human intervention.
In summary, our contributions are as follows:

- •
In this work, we explore the potential and importance of capturing and utilizing training data distributions for graph generation to enhance generation performance.
- •
We innovatively propose a self-conditioned graph generation framework to capture and utilize training data distributions via bootstrapped representations with our devised self-conditioned modeling and self-conditioned guidance, respectively.
- •
We perform a systematic study to evaluate the performance of our framework in a variety of real-world and synthetic datasets. The results demonstrate the effectiveness of our framework in comparison to other state-of-the-art baselines.

## 2 Related Works

### 2.1 Denoising Diffusion Models for Generation

Recently, denoising diffusion models [, , ] have been widely adopted in various fields of generation tasks. Their notable capabilities span various domains, including image generation [, , ], text generation [, , ], and temporal data modeling [, ]. In general, denoising diffusion models are probabilistic models designed to learn a data distribution by denoising variables with normal distributions [, ]. In particular, they first create noisy data by progressively adding and intensifying the noise in the clean data, in a Markovian manner.
Subsequently, these models learn a denoising network to backtrack each step of the perturbation. During training, the denoising networks are required to predict the clean data or the added noise, given the noisy data after perturbation. After optimization, the denoising networks could be used to generate new data via iterative denoising of noise sampled from a prior distribution [, ].

### 2.2 Graph Generation

Based on the strategies used, graph generation methods could be classified into two categories: (1) *One-shot Generation*. In this category, the models generate all edges among a defined node set in one single step. One-shot generation models are typically built upon the Variational Autoencoder (VAE) or the Generative Adversarial Network (GAN) structure, aiming to generate edges independently based on the learned latent embeddings. Normalizing flow models [, ] propose to estimate the graph density, by establishing an invertible and deterministic function to map latent embeddings to the graphs. More recently, diffusion models have also been adopted for graph generation [, ]. To deal with the discrete nature of graph data, DiGress [] leverages discrete diffusion by considering node and edge types as states in the Markovian transition matrix. (2) *Sequential Generation*. This strategy entails generating graphs through a series of sequential steps, typically by
incrementally adding nodes and connecting them with edges. Models in this category often utilize recurrent networks [, ] or Reinforcement Learning (RL) [] to guide the generation process [, ]. Sequential generation is particularly suitable for generating graphs with specific desired properties [].

### 2.3 Conditional Generation

Recent works have also explored various strategies to condition generation on specific classes or features. For example, ARM [] proposes to utilize gradients from classifiers to guide the generation process within each step. LDM [] enables the incorporation of external information, such as text [] and semantic maps [], with a specific encoder to learn the representations. The representations are then incorporated into the underlying UNet backbone [].
In RCG [], the authors employ a self-conditioned strategy to condition generation on representations learned from a pre-trained encoder.
Despite the advancements in image generation, it still presents significant difficulty when applying these methods in graph generation, due to the complex dataset patterns [, , ] and discrete sequential generation [, , ]. In contrast, our framework deals with these challenges with self-conditioned modeling and guidance to enhance graph generation efficacy.

Figure: Figure 2: The overall process of GraphRCG during training. Specifically, we learn from the training data a representation generator that outputs a representation based on noise sampled from a standard Gaussian distribution. After that, a graph generator is trained to generate new graphs from noisy graphs under the guidance of the representations.
Refer to caption: extracted/5739351/img/training_denoising.png

## 3 GraphRCG: Self-Conditioned Graph Generation

Our self-conditioned graph generation framework consists of two modules: self-conditioned modeling and self-conditioned guidance for RQ1 and RQ2, respectively. As illustrated in Fig. 2, in self-conditioned modeling, we employ a representation generator to capture graph distributions by learning to denoise representations with noise. The alignment loss between noisy representations and noisy graphs acts as a self-supervised loss to train the encoder. With the optimized representation generator, we train the graph generator by denoising graphs with added noise. At each generation step, we perform self-conditioned guidance via bootstrapped representations with noise at the same timestep. We further enhance guidance by aligning the denoised graph with the clean representations.

In this work, we represent a graph as $G=(\mathbf{X},\mathbf{E})$, where $\mathbf{X}\in\mathbb{R}^{n\times a}$ and $\mathbf{E}\in\mathbb{R}^{n\times n\times b}$ contain all the one-hot encodings of nodes and edges, respectively. Here $a$ and $b$ are the numbers of node types and edge types, respectively. We consider the state of “no edge” as an edge type. $n$ is the number of nodes in $G$. Notably, although we focus on discrete categorical features (i.e., types) in this paper, our work can be easily extended to scenarios with continuous features.

### 3.1 Self-Conditioned Modeling

Our framework GraphRCG aims to capture graph distributions (RQ1) by learning a low-dimensional representation distribution, such that the representations could be subsequently used for guidance during the generation process.
Therefore, this requires the representation generator to comprehensively capture the complex patterns in graph datasets, in terms of both node features and structures.

To transform graphs into representations, we first employ a graph encoder $h_{\eta}$ (parametrized by $\eta$) to transform an input graph $G=(\mathbf{X},\mathbf{E})$, into a low-dimensional representation: $\mathbf{h}=h_{\eta}(\mathbf{X},\mathbf{E})$.

Representation Generator.
Given the representations of all training data provided by the graph encoder, the representation generator is required to learn to generate representations with the same distribution. To enhance generation performance, following [], we utilize the Representation Diffusion Model (RDM) architecture, which generates representations from Gaussian noise, based on the process of Denoising Diffusion Implicit Models (DDIM) []. In particular, RDM utilizes a backbone comprising a fully connected network with multiple residual blocks. Each block is composed of an input layer, a timestep embedding projection layer, and an output layer. The number of residual blocks and the hidden dimension size both act as hyper-parameters. During training, given a representation of a graph sample, learned by the graph encoder, we first perturb it by adding random noise as follows:

$$ $\mathbf{h}_{t}=\sqrt{\alpha_{t}}\mathbf{h}_{0}+\sqrt{1-\alpha_{t}}\epsilon, \quad\text{where}\quad\epsilon\sim\mathcal{N}(\mathbf{0},\mathbf{I}),$ (1) $$

where $\mathbf{h}_{0}$ is the clean representation learned from $G$ by the graph encoder, i.e., $\mathbf{h}_{0}=h_{\eta}(\mathbf{X},\mathbf{E})$. $\mathbf{h}_{t}$ is the noisy version of $\mathbf{h}_{0}$ at timestep $t$. $\alpha_{1:T}\in(0,1]^{T}$ is a decreasing sequence, where $T$ is the total number of timesteps.
Then the representation generator $f$, parameterized by $\gamma$, is trained to denoise the perturbed representation to obtain a clean one. In this way, the corresponding objective for the representation generator could be formulated as follows:

$$ $\mathcal{L}_{RG}=\mathbb{E}_{\mathbf{h}_{0},\epsilon\sim\mathcal{N}(0,1),t} \left[\left\|\mathbf{h}_{0}-f_{\gamma}\left(\mathbf{h}_{t},t\right)\right\|_{2 }^{2}\right],$ (2) $$

where $\mathbf{h}_{0}$ is sampled from representations of graphs in training data, and $t$ is uniformly sampled from $\{1,2,\dotsc,T\}$. The target of the representation generator $f_{\gamma}$ is to capture the representation distribution and learn to generate representations from random noise. After optimization, the representation generator could perform sampling from random noise, following the DDIM strategy [], to obtain new representations.

On the other hand, the noisy representation $\mathbf{h}_{t}$, i.e., the input to the representation generator, is not related to any noisy graph. That being said, the noisy representation might not faithfully represent the noise added to an actual graph. Therefore, to enhance such consistency, we propose an alignment loss to train the encoder, which is formulated as follows:

$$ $\mathcal{L}_{AR}=\mathbb{E}_{G,t}\left[\left\|\mathbf{h}_{t}-h_{\eta}(\mathbf{ X}_{t},\mathbf{E}_{t})\right\|_{2}^{2}\right],$ (3) $$

where $G_{t}=(\mathbf{X}_{t},\mathbf{E}_{t})$ denotes the noisy graph with the same timestep $t$. The loss $\mathcal{L}_{AR}$ is designed to align the noise processes of representations and graphs, such that the noisy representation $\mathbf{h}_{t}$ preserves the same information as the noisy graph at the same timestep $G_{t}$.
In the following, we detail the process of adding noise to any graph.

Adding Noise to Graphs.
In discrete diffusion, adding noise equates to transitioning between states, that is, choosing a state based on a categorical distribution. For each timestep $t$, the probability of moving from one state to another is defined by a Markov transition matrix $\mathbf{Q}_{t}$, where $\mathbf{Q}_{t}[i,j]$ represents the likelihood of transitioning from state $i$ to state $j$. For graph generation, these states generally represent specific node types or edge types. Particularly, an edge-type state represents the absence of an edge. The process of adding noise is performed in a disentangled manner, which operates independently across nodes and edges with separate noise perturbations. A step of the noise process could be expressed as

$$ $q(G_{t}|G_{t-1})=(\mathbf{X}_{t-1}\mathbf{Q}_{t}^{\mathbf{X}},\mathbf{E}_{t-1} \mathbf{Q}_{t}^{\mathbf{E}}),$ (4) $$

where $t$ is the timestep. Moreover, $\mathbf{Q}_{t}^{\mathbf{X}}$ and $\mathbf{Q}_{t}^{\mathbf{E}}$ represent the transition matrices for the nodes and edges at timestep $t$, respectively.

Given the Markovian nature of the noise model, the noise addition is not cumulative, as the probability $q(G_{t}|G_{0})$ could be directly calculated from all the respective Markov transition matrices:

$$ $q(G_{t}|G_{0})=(\mathbf{X}_{0}\prod_{i=1}^{t}\mathbf{Q}_{i}^{\mathbf{X}}, \mathbf{E}_{0}\prod_{i=1}^{t}\mathbf{Q}_{i}^{\mathbf{E}}),$ (5) $$

where $\mathbf{X}_{0}=\mathbf{X}$ and $\mathbf{E}_{0}=\mathbf{E}$ denote the input node and edge types of $G$, respectively.
This formulation captures the essence of the discrete diffusion process, i.e., applying independent, state-specific transitions at each timestep for both nodes and edges in graph generation. In this manner, we could obtain $\mathbf{X}_{t}=\mathbf{X}_{0}\prod_{i=1}^{t}\mathbf{Q}_{i}^{\mathbf{X}}$ and $\mathbf{E}_{t}=\mathbf{E}_{0}\prod_{i=1}^{t}\mathbf{Q}_{i}^{\mathbf{E}}$.

To specify the Markov transition matrices, previous works have explored several feasible choices. The most prevalent choices in the literature have been uniform transitions [, ] and absorbing transitions [, ]. However, these do not contain the distribution information and thus could not benefit the capturing of graph distribution in our framework. Therefore, in our approach, we leverage the marginal transitions [, ], in which the probability of transitioning to any given state is directly related to its marginal probability observed in the dataset. In this manner, the transition matrices are modeled in a way that mirrors the natural distribution of states in graph data. As the edges are generally sparse in the graph data, the probability of jumping to the state of “no edge” is significantly higher than that of other states. To present the noise process, we first define $\mathbf{p}^{\mathbf{X}}\in\mathbb{R}^{a}$ and $\mathbf{p}^{\mathbf{E}}\in\mathbb{R}^{b}$ as the marginal distributions for the node and edge types, respectively. The marginal transition matrices for nodes and edges are formulated as

$$ $\displaystyle\mathbf{Q}_{t}^{\mathbf{X}}=\alpha^{t}\mathbf{I}+\beta^{t}\mathbf {1}_{a}(\mathbf{p}^{\mathbf{X}})^{\top},\ \ \text{and}\ \ \mathbf{Q}_{t}^{ \mathbf{E}}$ $\displaystyle=\alpha^{t}\mathbf{I}+\beta^{t}\mathbf{1}_{b}(\mathbf{p}^{\mathbf {E}})^{\top}.$ (6) $$

The above formulation ensures that $\lim_{t\rightarrow\infty}\prod_{i=1}^{t}\mathbf{Q}_{i}^{\mathbf{X}}=\mathbf{P}
^{\mathbf{X}}$, where each column in $\mathbf{P}^{\mathbf{X}}$ is $\mathbf{p}^{\mathbf{X}}$. The equation also holds true for the edges.
More details of the noise model are provided in Appendix A.
The overall process of our self-conditioned modeling module is presented in Algorithm 1.

### 3.2 Self-Conditioned Guidance (Training)

In self-conditioned guidance for RQ2, we optimize a graph generator to create new graphs conditioned on bootstrapped representations from the representation generator. Existing works have explored various methods to perform generation conditioned on specific properties, such as high activity in molecular graph generation []. However, these properties are generally several scalar values, which could capture only a small fraction of the information in the dataset. Moreover, these approaches often adopt a classifier or regressor to guide the generation process, which could not exploit the useful information in representations. In contrast, using representations as guidance for generation could largely benefit from the learned distribution in our representation generator.

As our representation generator is implemented by a diffusion model, we aim to utilize the information from not only the generated representation but also its generation process. With this in mind, we implement the generator as a denoising diffusion model, so that each step of diffusion could benefit from the representation of the same denoising step in a boostrapped manner. Our graph generator $g_{\theta}$, implemented as a denoising network and parametrized by $\theta$, is trained to predict the clean graph, given a noisy graph $G_{t}=(\mathbf{X}_{t},\mathbf{E}_{t})$ at a randomly sampled timestep $t$:

$$ $(\widetilde{\mathbf{p}}^{\mathbf{X}},\widetilde{\mathbf{p}}^{\mathbf{E}})=g_{ \theta}(\mathbf{X}_{t},\mathbf{E}_{t},\widetilde{\mathbf{h}}_{t},t),$ (7) $$

where $\widetilde{\mathbf{h}}_{t}=f_{\gamma}(\mathbf{h}_{t},t)$ is the denoised representation, generated from the representation generator at timestep $t$. Moreover, $\widetilde{\mathbf{p}}^{\mathbf{X}}\in\mathbb{R}^{a}$ and $\widetilde{\mathbf{p}}^{\mathbf{E}}\in\mathbb{R}^{b}$ are the predicted distributions for the node types and the edge types, respectively. The graph generator is based on the message-passing transformer
architecture [], as it effectively extracts the complex correlations between nodes and edges, while also being suitable for incorporating representations for conditioning [].
Specifically, the layers incorporate the graph attention mechanism [] into a Transformer framework [], achieved by including normalization and feedforward layers.
For each given (noisy) graph, the graph generator projects nodes and edges separately into low-dimensional representations and processes them through totally $L$ transformer layers, denoted as $(\mathbf{x}^{(l+1)}_{t},\mathbf{e}^{(l+1)}_{t})=M_{(l)}(\mathbf{x}^{(l+1)}_{t}
,\mathbf{e}^{(l+1)}_{t})$.
Here $\mathbf{x}_{t}^{(l)}$ (or $\mathbf{e}_{t}^{(l)}$) is the representation for the nodes (or edges) in the $l$-th layer of the transformer, denoted as $M_{(l)}$.

Figure: Figure 3: The sampling process of our framework with self-conditioned guidance. Our step-wise incorporation strategy employs the denoised presentation at each timestep to guide the denoising of the noisy graph at the same time step, thereby progressively guiding each step closer to the learned distributions.
Refer to caption: extracted/5739351/img/sampling.png

Cross-Attention. To effectively utilize the representations for guidance, we map them to the intermediate layers of the graph transformer via the cross-attention mechanism [], achieved by

$$ $\operatorname{Attention}(Q,K,V)=\operatorname{softmax}(QK^{T}/\sqrt{d})\cdot V.$ (8) $$

Specifically, the values of $Q$, $K$, and $V$ are computed as follows:

$$ $Q=W_{Q}^{(l)}\cdot\mathbf{x}^{(l)},K=W_{K}^{(l)}\cdot\widetilde{\mathbf{h}}_{t },V=W_{V}^{(l+1)}\cdot\widetilde{\mathbf{h}}_{t},$ (9) $$

where $W_{Q}^{(l)}\in\mathbb{R}^{d\times d_{x}}$,$W_{K}^{(l)}\in\mathbb{R}^{d\times d_{h}}$, $W_{V}^{(l)}\in\mathbb{R}^{d\times d_{h}}$ are learneable projection matrices. $d_{x}$ and $d_{h}$ are the dimensions of $\mathbf{x}$ and $\mathbf{h}$, respectively. Notably, the above process is performed for edge representations $\mathbf{e}^{(l)}$ in the same way with different parameters.

With the representations as guidance, the denoising network is then tasked to predict the clean graph, given the noisy graph $G_{t}=(\mathbf{X}_{t},\mathbf{E}_{t})$. The reconstruction objective is described as follows:

$$ $\mathcal{L}_{GG}=\mathbb{E}_{G,t}\left[\sum\limits_{i=1}^{n}\text{CE}(\mathbf{ X}_{i},\widetilde{\mathbf{p}}^{\mathbf{X}}_{i})+\sum\limits_{i=1}^{n}\sum \limits_{j=1}^{n}\text{CE}(\mathbf{E}_{i,j},\widetilde{\mathbf{p}}^{\mathbf{E} }_{i,j})\right],$ (10) $$

where $t$ is uniformly sampled from $\{1,2,\dotsc,T\}$. $\text{CE}(\cdot,\cdot)$ denotes the cross-entropy loss, as the prediction results of $\mathbf{X}$ and $\mathbf{E}$ are categorical, obtained from Eq. (7).

In addition, as we expect the representation to guide graph generation, we also aim to align the representation of the generated graph with the clean representation. In particular, we introduce another alignment loss that aligns the generated (clean) graph with the denoised (clean) representation from the representation generator. The loss is formulated as follows:

$$ $\mathcal{L}_{AG}=\mathbb{E}_{G,t}\left[\left\|h_{\eta}(p^{\mathbf{X}},p^{ \mathbf{E}})-f_{\gamma}\left(\mathbf{h}_{t},t\right)\right\|_{2}^{2}\right].$ (11) $$

Note that $\mathcal{L}_{AG}$, together with $\mathcal{L}_{GG}$, will be only used for optimizing the graph generator, not involving the representation generator. In this way, we can ensure that the representation generator focuses on capturing the graph distribution. The detailed overall process of self-conditioned guidance is presented in Algorithm 2.

### 3.3 Self-Conditioned Guidance (Sampling)

After optimization, our graph generator could be used to create new graphs. Specifically, we first sample a fixed number of nodes $n$ based on the prior distribution of the graph size in the training data, and $n$ remains fixed during generation. Next, a random graph is sampled from the prior graph distribution $G_{T}\sim\mathbf{p}^{\mathbf{X}}\times\mathbf{p}^{\mathbf{E}}$, where $\mathbf{p}^{\mathbf{X}}$ and $\mathbf{p}^{\mathbf{E}}$ represent the marginal distribution for each node type and edge type present in the dataset, respectively. Note that $\mathbf{p}^{\mathbf{X}}$ and $\mathbf{p}^{\mathbf{E}}$ are both categorical distributions.
As presented in Fig. 3, with the sampled noisy graph $G_{T}$, we could leverage the generator to recursively sample a cleaner graph $G_{t-1}$ from the previous graph $G_{t}$. As we perform self-conditioned guidance, the sampling process within each step should also involve representations.

Step-wise Incorporation of Bootstrapped Represenations. We introduce guidance into each sampling step with the representation obtained at the same timestep. That being said, for the representation generator, we utilize all (intermediate) representations during sampling, instead of only the last clean one. In this manner, the sampling process is described as

$$ $G_{t-1}\sim p_{\theta}(G_{t-1}|G_{t},\mathbf{h}_{t-1}),\ \ \text{where}\ \ \mathbf{h}_{t-1}=f_{\gamma}(\mathbf{h}_{t},t).$ (12) $$

In concrete, we keep track of the representation sampling process in the representation generator and utilize the representation in each step to guide the graph sampling in the same timestep $t$. In this manner, the generation process will absorb the graph distribution information learned by the representation generator, thereby improving generation performance.

## 4 Experiments

In our experiments, we evaluate GraphRCG across graph datasets covering realistic molecular and synthetic non-molecular datasets, in comparison to baselines, including auto-regressive models: GRAN [] and GraphRNN [], a GAN-based model: SPECTRE [], and diffusion models: EDP-GNN [], DiGress [], GDSS [], GraphARM [], HiGen [], and SparseDiff []. We provide implementation details and hyperparameter settings in Appendix D.2.

For generic graph generation, we evaluate the quality of the generated graphs with structure-based evaluation metrics. We follow previous work [] and calculate the MMD (Maximum Mean Discrepancy) between the graphs in the test set and the generated graphs, regarding (1) degree distributions, (2) clustering coefficients distributions, (3) the number of orbits with four nodes, and (4) the spectra of the graphs obtained from the eigenvalues of the normalized graph
Laplacian [, ]. For molecular graph generation, following previous works [, ], we evaluate the generated molecular graphs with several key metrics: (1) Frechet ChemNet Distance (FCD) [], (2) Neighborhood Subgraph Pairwise Distance Kernel (NSPDK) MMD [], (3) Validity, and (4) Uniqueness. We provide details of these metrics in Appendix D.3.

**Table 1: Comparison of generation results on SBM, Planar, and Ego. The best results are shown in bold.**
|  | SBM | Planar | Ego |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Model | Deg. $\downarrow$ | Clus. $\downarrow$ | Orbit $\downarrow$ | Spec. $\downarrow$ | Deg. $\downarrow$ | Clus. $\downarrow$ | Orbit $\downarrow$ | Spec. $\downarrow$ | Deg. $\downarrow$ | Clus. $\downarrow$ | Orbit $\downarrow$ | Spec. $\downarrow$ |
| Training | 0.0008 | 0.0332 | 0.0255 | 0.0063 | 0.0002 | 0.0310 | 0.0005 | 0.0052 | 0.0002 | 0.0100 | 0.0120 | 0.0014 |
| GraphRNN | 0.0055 | 0.0584 | 0.0785 | 0.0065 | 0.0049 | 0.2779 | 1.2543 | 0.0459 | 0.0768 | 1.1456 | 0.1087 | - |
| GRAN | 0.0113 | 0.0553 | 0.0540 | 0.0054 | 0.0007 | 0.0426 | 0.0009 | 0.0075 | 0.5778 | 0.3360 | 0.0406 | - |
| SPECTRE | 0.0015 | 0.0521 | 0.0412 | 0.0056 | 0.0005 | 0.0785 | 0.0012 | 0.0112 | - | - | - | - |
| DiGress | 0.0013 | 0.0498 | 0.0433 | - | 0.00027 | 0.0563 | 0.0098 | 0.0062 | 0.0708 | 0.0092 | 0.1205 | - |
| HiGen | 0.0019 | 0.0498 | 0.0352 | 0.0046 | - | - | - | - | 0.0472 | 0.0031 | 0.0387 | 0.0062 |
| SparseDiff | 0.0016 | 0.0497 | 0.0346 | 0.0043 | 0.0007 | 0.0447 | 0.0017 | 0.0068 | 0.0019 | 0.0537 | 0.0209 | 0.0050 |
| GraphRCG | 0.0011 | 0.0475 | 0.0378 | 0.0038 | 0.00025 | 0.0341 | 0.0010 | 0.0059 | 0.0015 | 0.0448 | 0.0183 | 0.0042 |

### 4.1 Comparative Results

Generic Graph Generation.
In this subsection, we further evaluate our framework on generic graph datasets with relatively larger sizes than molecular graphs. In particular, we consider two synthetic datasets: SBM, drawn from stochastic block models [], with a maximum size of 200 nodes, and Planar, containing planar graphs with a fixed size of 64 []. In addition, we consider a realistic citation dataset Ego [], originated from Citeseer []. Further details of these datasets are provided in Appendix D.1. From the results presented in Table 1, we could obtain the following observations: (1) GraphRCG outperforms other baselines on all three datasets across various metrics for graph generation, demonstrating the effectiveness of our framework in precisely capturing graph distributions and utilizing them for generation guidance. (2) The performance improvement over other methods is more substantial on the Planar dataset. As illustrated in the t-SNE plot in Fig. 7 (b), the distribution of the Planar dataset is more scattered, increasing the difficulty of accurately capturing it. Nevertheless, our framework learns graph distributions with a representation generator, which enables the modeling of complex underlying patterns. (3) GraphRCG is particularly competitive in the MMD score regarding degree distributions and the number of orbits. This observation demonstrates that GraphRCG could authentically capture the complex graph distribution of the training samples with the help of self-conditioned modeling.
We include additional visualization results of graphs generated by our framework in Appendix F.

**Table 2: Results of various methods on the QM9 and ZINC250k Datasets.**
|  | QM9 Dataset | ZINC250k Dataset |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Model | Validity↑ | NSPDK↓ | FCD↓ | Unique↑ | Validity↑ | NSPDK↓ | FCD↓ | Unique↑ |
| EDP-GNN | 47.52 | 0.005 | 2.68 | 99.25 | 82.97 | 0.049 | 16.74 | 99.79 |
| SPECTRE | 87.33 | 0.163 | 47.96 | 35.7 | 90.20 | 0.109 | 18.44 | 67.05 |
| GDSS | 95.72 | 0.003 | 2.9 | 98.46 | 97.01 | 0.019 | 14.66 | 99.64 |
| DiGress | 99.01 | 0.0005 | 0.36 | 96.66 | 91.02 | 0.082 | 23.06 | 81.23 |
| GraphARM | 90.25 | 0.002 | 1.22 | 95.62 | 88.23 | 0.055 | 16.26 | 99.46 |
| GraphRCG | 99.12 | 0.0008 | 0.28 | 98.39 | 92.38 | 0.041 | 13.48 | 96.15 |

Molecular Graph Generation.
To evaluate our framework on molecular graph generation, we select two popular datasets: QM9 [] and ZINC250k [], with details and provided in Appendix D.1.
We present the molecular graph generation results on QM9 in Table 2. Specifically, GraphRCG demonstrates competitive performance on QM9 across various metrics, compared to other state-of-the-art baselines. The best FCD values on QM9 and ZINC250k indicate that GraphRCG effectively captures the chemical property distributions in the dataset. Furthermore, the outstanding validity score on QM9 also signifies that our framework GraphRCG is capable of generating valid molecules that are more closely aligned with the training data distribution.

Figure: (a) *
Refer to caption: extracted/5739351/img/interp/graph_b.png

### 4.2 Representation Interpolation

As our self-conditioned guidance leverages representations, we could manually perform linear interpolation for two representations to generate graphs that represent the properties of both representations. With our step-wise incorporation strategy, we extract two series of representations generated by our representation generator for all timesteps, i.e., $t=1,2,\dotsc,T$, and perform interpolation for each timestep. We denote $\alpha$ as the interpolation ratio, where $\alpha=0$ and $\alpha=1$ indicate that we entirely utilize one of the representations. We provide the visualization results in Fig. 4, from which we observe that the generated graphs guided by interpolated representations remain meaningful with different interpolation ratios. This result demonstrates that our representation generator is capable of capturing smooth graph distributions with rich information. Furthermore, our design also enables further applications with specific representations as guidance.

### 4.3 Ablation Study

Effect of Self-Conditioned Modeling.
Previous works [] have also explored various strategies to capture and model distributions for the guidance of graph generation. For example, DiGress leverages manually designed structural features (e.g., the number of cycles)
for graph generation. However, such features contain less information and require domain knowledge.
In this subsection, we compare several variants of our framework with these structural features to evaluate the efficacy of self-conditioned modeling in encapsulating the graph distribution. We consider using the following features (representations) to replace our self-conditioned modeling module: (1) structural features proposed in DiGress, (2) representations of true training samples, which limit the uniqueness of generation, (3) a mixture of true representations, and (4) distributions learned by a Gaussian Mixture Model (GMM).
As the structural features involve molecular information, we conduct experiments on the QM9 dataset with explicit hydrogens, which is a more complex setting with larger graphs.

**Table 3: The ablation study results regarding self-conditioned modeling on dataset QM9 with explicit hydrogen.**
| Model | Valid↑ | Unique↑ | Atom S.↑ | Mol S.↑ |
| --- | --- | --- | --- | --- |
| Dataset | 97.8 | 100 | 98.5 | 87.0 |
| DiGress w/o A | 92.3 | 97.9 | 97.3 | 66.8 |
| DiGress w/ A | 95.4 | 97.6 | 98.1 | 79.8 |
| GraphRCG w/ A | 92.9 | 95.4 | 93.1 | 76.6 |
| GraphRCG w/ T | 91.2 | 91.5 | 90.5 | 72.3 |
| GraphRCG w/ T+M | 94.6 | 97.0 | 90.2 | 74.9 |
| GraphRCG w/ GMM | 96.4 | 94.1 | 91.5 | 77.1 |
| GraphRCG | 96.9 | 98.1 | 97.2 | 81.9 |

From the results presented in Table 3, we first observe that the inclusion of structural features significantly enhances the performance of DiGress, especially in the metric of molecule stability, which benefits from the integration of molecular characteristics. The substitution of self-conditioned modeling with structural features, however, results in a notable decline in performance, highlighting the importance of distributions with comprehensive information for effective guidance. Furthermore, among the variants that directly operate on training sample representations, it is evident that the mere utilization of pre-existing representations yields suboptimal outcomes, especially concerning the metric of uniqueness.
This suggests that relying solely on existing representations captures only a small portion of the authentic distribution, thereby adversely impacting the overall performance.

**Table 4: The ablation study results regarding self-conditioned guidance on the dataset Ego.**
| Dataset | Ego |  |  |  |
| --- | --- | --- | --- | --- |
| Model | Deg. $\downarrow$ | Clus. $\downarrow$ | Orbit $\downarrow$ | Spec. $\downarrow$ |
| GraphRCG-Gradient | 0.0134 | 0.0955 | 0.0464 | 0.0151 |
| GraphRCG w/o $\mathcal{L}_{AG}$ | 0.0088 | 0.0647 | 0.0252 | 0.0092 |
| GraphRCG-fixed | 0.0053 | 0.0653 | 0.0310 | 0.0125 |
| GraphRCG | 0.0015 | 0.0448 | 0.0183 | 0.0042 |

Effect of Self-Conditioned Guidance.
In this subsection, we investigate the effect of self-conditioned guidance in our framework. We first replace the entire guidance strategy with a gradient-based method, which leverages computed gradients as guidance. Therefore,
the graph generator does not involve any representation during training. For the second variant, we remove the alignment loss $\mathcal{L}_{AG}$ described in Eq. (11). Without this loss, the graph generator is not well-aligned with the representations produced by the representation generator, thereby affecting the guidance performance. For the third variant, we directly use the fixed representation, i.e., the clean representation, to guide generation. In this case, the step-wise guidance strategy is removed, resulting in the infeasibility of progressive guidance. We provide further details regarding these variants in Appendix D.5.
From the results presented in Table 4, we could first observe that our framework outperforms all other variants in most evaluation metrics, demonstrating the effectiveness of our self-conditioned guidance strategy. Moreover, GraphRCG-Gradient and GraphRCG w/o $\mathcal{L}_{AG}$ exhibit significantly poorer performance, as evidenced by higher scores across all metrics. This deterioration, particularly in Clus. and Orbit values, underscores the difficulty in preserving graph distributions without representation guidance or alignment loss. GraphRCG-fixed shows improved performance relative to the other variants, demonstrating the benefits of representation guidance even with a fixed one. Nevertheless, the results also indicate that the step-wise self-conditioned guidance is more beneficial for progressively guiding the generation process.

## 5 Conclusion

In this work, we investigate the importance of capturing and utilizing distributions for graph generation. We propose a novel self-conditioned generation, that encompasses self-conditioned modeling and self-conditioned guidance. Instead of directly learning from graph distributions, we encode all graphs into representations to capture graph distributions, which could preserve richer information. Our self-conditioned guidance module further guides the generation process in each timestep with representations with different degrees of noise. We conduct extensive experiments to evaluate our framework, and the results demonstrate the efficacy of our framework in graph generation.

## Appendix A Noise Model

In this section, we provide additional information on the noise model used during the training of our graph generator. Particularly, the graphs at timestep $t$ could be represented as $\mathbf{X}_{t}=\mathbf{X}_{0}\prod_{i=1}^{t}\mathbf{Q}_{i}^{\mathbf{X}}$ and $\mathbf{E}_{t}=\mathbf{E}_{0}\prod_{i=1}^{t}\mathbf{Q}_{i}^{\mathbf{E}}$. Here, $\mathbf{Q}_{i}^{\mathbf{X}}$ and $\mathbf{Q}_{i}^{\mathbf{E}}$ are defined in Eq. (13), i.e.,

$$ $\displaystyle\mathbf{Q}_{t}^{\mathbf{X}}=\alpha^{t}\mathbf{I}+\beta^{t}\mathbf {1}_{a}(\mathbf{p}^{\mathbf{X}})^{\top},\ \ \text{and}\ \ \mathbf{Q}_{t}^{ \mathbf{E}}$ $\displaystyle=\alpha^{t}\mathbf{I}+\beta^{t}\mathbf{1}_{b}(\mathbf{p}^{\mathbf {E}})^{\top}.$ (13) $$

In practice, the noise process is not cumulative. By defining $\overline{\alpha}^{t}=\prod_{i=1}^{t}\alpha^{i}$ and $\overline{\beta}^{t}=1-\overline{\alpha}^{t}$, we could achieve

$$ $\prod_{i=1}^{t}\mathbf{Q}_{i}^{\mathbf{X}}=\overline{\alpha}^{t}\mathbf{I}+ \overline{\beta}^{t}\mathbf{1}_{a}(\mathbf{p}^{\mathbf{X}})^{\top},\ \ \text{ and}\ \ \prod_{i=1}^{t}\mathbf{Q}_{i}^{\mathbf{E}}=\overline{\alpha}^{t} \mathbf{I}+\overline{\beta}^{t}\mathbf{1}_{a}(\mathbf{p}^{\mathbf{E}})^{\top}.$ (14) $$

Following [], we set $\overline{\alpha}^{t}=\cos(0.5\pi(t/T+s)/(1+s))^{2}$ with $s$ being a small value. In this manner, when computing the noisy graphs $G_{t}=(\mathbf{X}_{t},\mathbf{E}_{t})$, we do not need to recursively multiply $Q_{t}^{\mathbf{X}}$. Instead, we utilize the value of $\overline{\alpha}^{t}$ to directly obtain $G_{t}$.

The noise model for the representation generator is similar and in a simpler form. We first sample $\epsilon\sim\mathcal{N}(0,\mathbf{I})$ and compute the noisy representations based on
$\mathbf{h}_{t}=\sqrt{\alpha_{t}}\mathbf{h}_{0}+\sqrt{1-\alpha_{t}}\epsilon.$

## Appendix B Self-conditioned Modeling

In this section, we present the detailed algorithm of our self-conditioned modeling module in Algorithm 1. Specifically, we aim to optimize a representation generator along with a graph encoder. The overall process is presented in Fig. 2.

Figure: Algorithm 1 The training process of self-conditioned modeling.

## Appendix C Self-conditioned Guidance

Figure: Algorithm 2 Detailed training and sampling process of our self-conditioned guidance module.

### C.1 Comparison with Other Methods

In this subsection, we discuss and compare our framework GraphRCG with other diffusion-based generative models for graph data. We provide the comparisons regarding technical details in Table 5.
Typically, existing diffusing methods for graph generation rely on either continuous or discrete diffusion. As a classific example, GDSS [] adopts Gaussian transition kernels to perform continuous diffusion with a score-matching strategy. DiGress, on the other hand, performs discrete diffusion while considering categorical features of nodes and edges. Nevertheless, although continuous representations could capture complex structural patterns in graph distributions, they are less effective in generating discrete graph data. In contrast, our framework is capable of leveraging continuous diffusion to guide discrete diffusion, thereby combining the strengths of both and allowing for the generation of a wider range of graph structures. Regarding the convergence type, which refers to the pure noise state, we also combine both continuous and discrete noise to facilitate the optimization of both our representation generator and graph generator. Comparing the conditional generation type, our framework is conditioned on representations, which preserve richer information of complex distributions of each dataset. As a result, the generation process could significantly benefit from the guidance of representations.

**Table 5: Comparison of different denoising diffusion models for graph generation. $G(n,p)$ denotes the Erdős-Rényi graph model [], where $p$ is the probability of an edge existing between two nodes, and $n$ is the graph size.**
| Model | Diffusion Type | Convergence | Conditional Generation | Featured Generation |
| --- | --- | --- | --- | --- |
| EDP-GNN | Continous | $\mathcal{N}(0,1)$ | - | - |
| GDSS | Continous | $\mathcal{N}(0,1)$ | - | ✓ |
| DiscDDPM | Discrete | $G(n,0.5)$ | - | - |
| DiGress | Discrete | Empirical | Gradients from a classifier | ✓ |
| SparseDiff | Discrete | Empirical | - | ✓ |
| EDGE | Discrete | $G(n,0)$ | Degree sequence | ✓ |
| Ours | Continous & Discrete | $\mathcal{N}(0,1)$ & Empirical | Representation | ✓ |

## Appendix D Experimental Settings

**Table 6: Detaile statistics of generic datasets used in our experiments.**
| Name | Graph number | Node range | Edge range |
| --- | --- | --- | --- |
| Planar | 200 | [64, 64] | [346, 362] |
| SBM | 200 | [44, 187] | [258, 2258] |
| Ego | 757 | [50, 399] | [112, 2124] |

### D.1 Dataset Details

For generic datasets, we consider SBM, Planar, and Ego. In particular, the two synthetic datasets, SBM and Planar, are obtained following the settings in SPECTRE []. The Ego dataset setting follows SparseDiff [].

- •
The SBM dataset contains 2022 Stochastic Block Model graphs. Each graph has 2 to 5 communities, each of which has 20 to 40 nodes. The inter-community edge probability is 0.3 and the intra-community edge probability is 0.05.
- •
The Planar dataset contains 200 planar graphs, each with 64 nodes. The graphs are generated via Delaunay triangulation on a set of randomly placed points.
- •
The Ego dataset contains 757 graphs, each with 50 399 nodes, sampled from the Citeseer Network Dataset [].

The detailed statistics of these datasets are provided in Table 6.

For molecular datasets, we consider ZINC250k and QM9 following GraphARM [].
Particularly, QM9 consists of molecular graphs with a maximum of nine heavy atoms that could be treated with implicit or explicit hydrogens. We provide the details of dataset statistics in Table 7.
ZINC-250k consists of approximately 250,000 drug-like molecules, each of which has up to 38 atoms. The dataset contains nine atom types and three edge types.

**Table 7: Detaile statistics of molecular datasets used in our experiments.**
| Dataset | Number of graphs | Node range | Number of node types | Number of edge types |
| --- | --- | --- | --- | --- |
| QM9 | 133,885 | [1, 9] | 4 | 3 |
| ZINC250k | 249,455 | [6, 38] | 9 | 3 |

### D.2 Training Settings

All experiments in our evaluation part are conducted on an NVIDIA A6000 GPU with 48GB of memory. For the specific parameters in each dataset, we follow the settings in DiGress [] and SparseDiff [].
We utilize the Adam optimizer [] for optimization. We also utilize the Xavier initialization []. For the representation generator, we implement it as an RDM (Representation Diffusion Model) used in RCG []. The representation dimension size is set as 256 for all datasets. The learning rate of the RDM is set as $10^{4}$, and the weight decay rate is set as 0.01. The number of residual blocks in the RDM is set as 12. The batch size is various across datasets, adjusted according to the GPU memory consumption in practice. The total number of timesteps $T$ is set as 1,000. For the graph transformer architecture used to implement our graph generator, we set the number of layers as 8, with the hidden dimension size as 256.
We provide our code in the supplementary materials.

### D.3 Evaluation Metrics

For molecular graph generation, following previous works [, ], we evaluate the generated molecular graphs with several key metrics:
(1) Frechet ChemNet Distance (FCD) [], which quantifies the discrepancy between the distributions of training and generated graphs, based on the activation values obtained from the penultimate layer in ChemNet. (2) Neighborhood Subgraph Pairwise Distance Kernel (NSPDK) MMD [], which measures the Maximum Mean Discrepancy (MMD) between the generated and the test molecules, considering both node and edge features. (3) Validity, which refers to the proportion of generated molecules that are structurally valid without requiring valency adjustments. (4) Uniqueness, which measures the proportion of unique molecules that are distinct from each other.

### D.4 Required Packages

We list the required packages for running the experiments below.

- •
Python == 3.9.18
- •
torch == 2.0.1
- •
pytorch_lightning==2.0.4
- •
cuda == 11.6
- •
scikit-learn == 1.3.2
- •
pandas==1.4.0
- •
torch_geometric==2.3.1
- •
torchmetrics==0.11.4
- •
torchvision==0.15.2+cu118
- •
numpy == 1.23.0
- •
scipy == 1.11.0
- •
wandb==0.15.4
- •
tensorboard == 2.15.1
- •
networkx == 2.8.7

### D.5 Ablation Study for Self-conditioned Guidance

With different ways to incorporate the bootstrapped representations, in our ablation study, we explore the following possible sampling strategies with self-conditioned guidance.

Gradient-based Guidance. In this method, the incorporation of representations is not explicitly performed in graph transformer layers. Instead, the representation guidance is performed via a gradient-based strategy, where each sampling step will output graphs that are closer to the given representation.

$$ $G_{t-1}\sim p_{\theta}(G_{t-1}|G_{t})p_{\eta}({\mathbf{h}}_{t}|G_{t-1}),$ (15) $$

where $p_{\eta}({\mathbf{h}}_{t}|G_{t-1})\propto\exp(-\lambda\langle\nabla_{G_{t}}\|
\mathbf{h}_{t}-h_{\eta}(G_{t})\|_{2}^{2},G^{t-1}\rangle)$. The form is based on the classifier-guided DDIM sampling strategy in ADM []. As a result, the training of the denoising network does not involve representation, which reduces the complexity during optimization. However, as the optimizations of the representation generator and the graph generator are separate, the guidance effect of representations cannot be guaranteed during sampling.

Guidance with Fixed Representations.
In this method, the sampling step is based on the forward process in the denoising network. However, the representation is generated from the last sampling step in the representation generator, and is fixed during graph generation. In other words,

$$ $G_{t-1}\sim p_{\theta}(G_{t-1}|G_{t},\mathbf{h}_{0}).$ (16) $$

The benefit of this strategy is that the representation used for guidance is clean, and maximally contains the knowledge learned in the representation generator.

**Table 8: The performance of various methods on three generic datasets.**
| Model | Community | Cora | Enzymes |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Deg. | Clus. | Orbit | Deg. | Clus. | Orbit | Deg. | Clus. | Orbit |  |
| SPECTRE | 0.048 | 0.049 | 0.016 | 0.021 | 0.080 | 0.007 | 0.136 | 0.195 | 0.125 |
| GDSS | 0.045 | 0.086 | 0.007 | 0.160 | 0.376 | 0.187 | 0.026 | 0.061 | 0.009 |
| DiGress | 0.047 | 0.041 | 0.026 | 0.044 | 0.042 | 0.223 | 0.004 | 0.083 | 0.002 |
| GraphARM | 0.034 | 0.082 | 0.004 | 0.273 | 0.138 | 0.105 | 0.029 | 0.054 | 0.015 |
| GraphRCG | 0.040 | 0.053 | 0.029 | 0.038 | 0.036 | 0.173 | 0.004 | 0.079 | 0.002 |

## Appendix E Additional Results

In this section, we consider additional experiments on three generic datasets.
As our framework is based on discrete graph diffusion, we mainly follow the dataset settings used in DiGress [] and the following work SparseDiff [] for the three generic datasets. We consider the following datasets: Community [], Cora [], and Enzymes [], order to further improve the integrity of our evaluation. We provide the results in Table 8. The results of other baselines are obtained from GraphARM []. From the results, we could observe that our framework also achieves competitive results, compared to other methods on various datasets. The performance is particularly better on dataset Cora and Enzymes, indicating that our framework is generalizable to various datasets.

## Appendix F Visualization Results

In this section, we provide additional visualization results from the experiments of generic graph generation. Particularly, we sample different generation results from the SBM and Planar datasets. The results are provided in Fig. 5 and Fig. 6.

Figure: (a) *
Refer to caption: extracted/5739351/img/sbm_results/graph_0.png

Figure: (a) *
Refer to caption: extracted/5739351/img/planar_results/graph_0.png

Figure: (a) SBM
Refer to caption: extracted/5739351/img/tsne_sbm.png

## Appendix G Representation Quality

In this section, we provide visualization results to evaluate the quality of the generated representations. We present the t-SNE plot of representations from training samples and our representation generator on datasets SBM and Planar in Fig. 7. From the visualization results, we could observe that our representation generator could faithfully capture the graph distributions from training samples. In other words, the generated representations closely align with training graph distributions. More importantly, our framework can generate representations that slightly deviate from the training samples in specific directions. This indicates that our framework is capable of discovering novel graph distributions that are not present in training samples, while still ensuring the validity of these representations for further guidance during generations.

## Appendix H Limitation

In this section, we discuss the potential limitations presented in our framework.
Although our framework is capable of generating graphs conditioned on the representations provided by our representation generator, it also means that the optimization quality of the representation generator is critical for graph generation. In other words, if the representation generator is not well-trained, the output representations could be detrimental to graph generation. In addition, the learned representations are not evaluated for their quality, as there are not ground truths for evaluation. A feasible solution is to create a dataset that is directly generated from representations. In this manner, the representations learned in our framework could be evaluated for their quality and similarity to the ground truths.

## Appendix I Broader Impact

As our datasets only involve datasets, the information in these datasets is ensured to be anonymized. We only use datasets from public releases, and thus we infer that this work does not have negative social impacts.

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: Please address the weaknesses above.
soundness: 3
strengths: - The motivation of this work seems reasonable: Using graph representation for conditioning the generation process to learn the complex distribution. Yet, this motivation and the method of using representation generation has been studied in previous work (Li et al., 2024)

Li et al., 2024, Return of Unconditional Generation: A Self-supervised Representation Generation Method
summary: This paper proposes a self-conditioned graph generation method for capturing the entire distribution. The representation generator produces a low-dimensional representation of graphs that reflect the learned distribution, and the learned distribution is used to guide the denoising diffusion process. The experimental results show that representation-generated conditioning improves generation quality.
weaknesses: - This paper is an unfinished work as the equations and notations are incomplete. For example, as in Eq.(5), (6), (10), and (11), random variables are only represented as subscripts and the parenthesis are in weird positions.

- The idea of using a representation generator to condition the generation process is mostly based on the Representation-Conditioned Generation framework (Li et al., 2024) which conditions the image generator with generated representation from the self-supervised encoder. The difference only comes from the difference in the domain.

- The V.U.N. (valid, unique, and novel) metric for generic graph generation (SBM, Planar) is required to fully evaluate the model. 

- The experimental results are different from those reported in previous works: For SBM and Planar, the DiGress results in this paper are worse than the original results from the DiGress paper. For the molecule generation task, the results of DiGress are worse than the results reported in the recent work (Jo et al., 2024); DiGress and GruM (Jo et al., 2024) achieve very low FCD in QM9 and ZINC250k (DiGress: QM9=0.095, ZINC250k=3.482, GruM QM9=0.108, ZINC250k=2.257). What is the reason for this difference? 

[1] Li et al., Return of Unconditional Generation: A Self-supervised Representation Generation Method, arXiv 2024

[2] Jo et al., Graph Generation with Diffusion Mixture, ICML 2024

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 1
questions: - Is the discrete diffusion model actually more beneficial than the diffusion model on the continuous space such as GDSS or GruM for the proposed framework?

- Which architectures did the authors use for the graph encoder?

- Why did the authors not use the pre-trained graph encoders?
soundness: 1
strengths: - The proposed method improves performance by leveraging the auxiliary graph representations in the generative process.
- Compared to the original RCG [1], the proposed step-wise guidance is novel.

[1] Li et al., "Return of Unconditional Generation: A Self-supervised Representation Generation Method", NeurIPS 2024.
summary: This paper introduces GraphRCG, a self-conditioned graph generation framework to align the generated graph distribution to the training distribution. The authors propose to encode graphs into low-dimensional representations so that the graph encoders capture the data distribution and then leverage the learned representations to guide the generation process. Additionally, GraphRCG introduces step-wise guidance where the generative process of the representations progressively affects the graph generative process. The authors perform experiments on generic and molecular graph datasets.
weaknesses: - The proposed techniques are largely covered by recent works. The graph generation technique is directly adopted from DiGress [2] which also utilizes the marginal transitions and conditioning method with graph features. Additionally, conditioning the generative process with the generated representations is proposed in the original RCG [1].

- The second challenge lacks soundness and clarity. The authors argue that graph generation is inherently sequential, as meeting the desired conditions should be performed in a sequential manner. However, to meet the desired conditions, accurately generating core substructures, such as communities in general graphs or functional groups in molecules, is crucial and it is difficult to be achieved by using a sequential approach. Therefore, directly guiding the generation toward the true distribution seems to be promising to meet the desired properties. I suggest that the authors clarify why the step-wise guidance is crucial for graph generation.

- The experimental setup does not show that the learned graph representations can actually capture the data distributions. To show this effect, the authors should show whether the learned representations can understand the structural information in the training dataset. For example, on the SBM dataset, it would be better to classify the training and generated graphs in terms of the number of communities and then visualize the corresponding representations of training and generated graphs. 

- The experimental result in section 4.2 does not show the interpolation effect, as the target graph distribution is not diverse. I recommend interpolating between distinct graphs such as molecules with benzene rings and molecules without benzene rings.

- There are significant errors in most of the equations, making it difficult for readers to understand the proposed method.

- Some related works such as EDGE [3] and GruM [4] are missing and not compared. Also, it would be better to apply the proposed method to the recent diffusion models to emphasize the effectiveness of the proposed method.

[1] Li et al., "Return of Unconditional Generation: A Self-supervised Representation Generation Method", NeurIPS 2024.

[2] Vignac et al., "DiGress: Discrete Denoising diffusion for graph generation", ICLR 2023.

[3] Chen et al., "Efficient and Degree-Guided Graph Generation via Discrete Diffusion Modeling", ICML 2023.

[4] Jo et al., "Graph Generation with Diffusion Mixture", ICML 2024.

---

confidence: 5
contribution: 2
initial_rating: 3
presentation: 2
questions: - Is there something wrong in the formula rendering in the submitted pdf? It cause great inconvenience to read this paper.
soundness: 3
strengths: - The model corporate the implicit representation distribution into modeling graph data is reasonable.
- Experiments show the superior performance compared to other baselines.
- This paper is easy to follow and the motivation is clear.
summary: The paper proposes GraphRCG, a self-conditioned framework for graph generation that leverages graph distributions explicitly to enhance graph generation quality and fidelity. Unlike conventional models that implicitly capture graph distributions through direct output alignment, GraphRCG encodes each graph into a low-dimensional representation. These representations are then used to guide the generation process progressively. Extensive experiments demonstrate GraphRCG's superior performance compared to baseline models​.
weaknesses: - Although the motivation is clear, the improvement compared to other conditional graph generative models seems is incremental. Augmenting the data feature and modeling joint distribution of $p(G, z)$ with representation in latent space are common in generative models, not limited to graph generation and the learnable features, so is there any comparison between modeling the joint distribution and inject the additional feature into the original model. 

- I strongly suggest you should compare proposed model with more advanced graph generative models, like EDGE[1], SwinGNN[2], GruM[3] and so on.
- Have you tried other more complex neural network architecture like graph transformer in DiGress[4]?



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

[2] SwinGNN: Rethinking Permutation Invariance in Diffusion Models for Graph Generation.

[3] Graph generation with diffusion mixture. 

[4] Discrete denoising diffusion for graph generation.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: 1) Figure 1:
From this figure, one could infer that the representation and graph generation diffusion models are trained separately and only during graph generation is the conditional information incorporated. This interpretation contradicts the description in the rest of the paper.
Additionally, it is unclear what the term *capture* in this context means and how it differs from "learning".
I suggest revising the figure to better reflect the overall approach.


2) Validity of planar and sbm graphs:
Previous studies (SPECTRE and DiGress) report the fraction of valid planar and sbm graphs generated. Given that Table 2 includes results from these studies, why has the validity of planar and sbm graphs been omitted? How does the proposed method compare in this regard?
soundness: 2
strengths: The paper is well structured and easy to follow. Figure 2 provides a clear overview of the proposed method and its components. The work introduces some interesting ideas, such as the joint training of the graph encoder and the generative diffusion model, and alignment losses during both representation and graph generation training. The empirical performance of the proposed method is demonstrated on several graph generation benchmarks, showing competitive performance compared to existing methods. Additionally, the ablation study offers insights into the significance of the various components of the method.
summary: The work presents a two-step approach to graph generation. First, a vector representation is generated, which conditions the subsequent graph generation.
These vector representations are obtained using a graph encoder, jointly trained with a generative diffusion model that transforms noise into the representations.
Graph generation is performed by a conditional diffusion model, parameterized by a message-passing transformer, that generates graphs conditioned on representations. 
The model is evaluated on several graph generation benchmarks and shows competitive performance compared to existing methods.
weaknesses: First of all, there appears to be a problem with the latex rendering in the paper, as a substantial portion of symbols in math equations are missing. So the following comments are based on what could be inferred from the text and figures.

1) **Contributions and differences from previous work**:
The paper adapts the previous work RCG [1] from image to graph generation. However, there are key differences: while RCG employs a pretrained image encoder to obtain representations, the proposed method jointly trains the graph encoder with a diffusion model. Additionally, the proposed method introduces alignment losses during both representation and graph generation training. Furthermore, during graph generation, the diffusion model is conditioned on a noisy version of the representation, rather than the "clean" one, with noise strength aligning with the current denoising step. The paper should clearly delineate which aspects of the method are adapted from [1] and which are novel.

2) **Theoretical justification**:
The joint training, alignment losses, and noisy conditioning convolute the modeling approach. For instance, if the graph generation diffusion model were conditioned on the clean representation, it would be clear to see that the model distribution p(G) is decomposed as P(G) = P(G | R) P(R), where P(R) means the distribution of the representation R. However, with the noisy conditioning, it is not clear what the model distribution decomposes into, and what the role of the conditioning noise is. The alignment losses add further complexity. Although the ablation study demonstrates empirical benefits of these components, there is neither theoretical justification nor intuitive explanation for these design choices, making it difficult to grasp the underlying principles of the proposed method. Similarly, the joint training of the graph encoder and the representation diffusion model lacks theoretical justification or intuitive explanation for why it would yield meaningful representations. Additionally, as the representation distribution evolves during generator training, the convergence of this procedure should be discussed.

3) **Fair ablation study**:
The ablation study highlights the empirical benefits of the method's components, but the increase in model capacity and training time is ignored. For instance, the total number of parameters for the generative model is X (parameters for the representation diffusion model) + Y (parameters for the graph generation diffusion model). It would be insightful to see how the performance of the proposed method compares to an unconditional graph generation diffusion model with the same number of parameters, i.e. X + Y. Furthermore, for a fair comparison, the training time of the proposed method (joint training of the graph encoder and the representation diffusion model + conditional graph generation training) should be compared to other graph generation methods.

4) **Related work**:
Some overlooked works on graph generation should be discussed in the related work section: [2-8].


[1]: Li et al., Return of Unconditional Generation: A Self-supervised Representation Generation Method

[2]: Goyal et al., GraphGen: A Scalable Approach to Domain-agnostic Labeled Graph Generation

[3]: Grover et al., Graphite: Iterative Generative Modeling of Graphs

[4]: Davies et al., Size Matters: Large Graph Generation with HiGGs

[5]: Haefeli et al., Diffusion Models for Graphs Benefit From Discrete State Spaces

[6]: Diamant et al., Improving Graph Generation by Restricting Graph Bandwidth

[7]: Qi et al., SwinGNN: Rethinking Permutation Invariance in Diffusion Models for Graph Generation

[8]: Bergmeister et al., Efficient and Scalable Graph Generation through Iterative Local Expansion

Meta-review: All reviewers agree that the method of this submission is mainly based on recent work and there are many holes in writing and experiments. The authors did not provide any feedback in the rebuttal and discussion phase. Taking all these into account, I think this submission is not qualified enough for ICLR.

Decision: Reject