A Prior-based Discrete Diffusion Model for Social Graph Generation

1 Introduction

Generating graphs based on a target distribution is a fundamental problem in various domains [Liu et al., 2023a]. In the context of social network propagation [Vosoughi et al., 2018], graph generation plays a pivotal role in uncovering hidden patterns of information flow and influence spread, which are crucial for tasks like source localization [Xu et al., 2024a] and user behavior prediction [Zhou et al., 2020]. Understanding the graph generation process in social network propagation sets the foundation for subsequent downstream tasks.

Recent advancements in deep generative models have significantly improved social network analysis, especially compared to traditional random graph models [Leskovec and Faloutsos, 2007]. Deep models, such as Variational Autoencoders (VAEs) [Kingma, 2013], Generative Adversarial Networks (GANs) [Goodfellow et al., 2014], diffusion model [Ho et al., 2020], and other deep generative approaches, learn to capture complex structural patterns in graph data and generate new graphs with desired properties.

Among them, probabilistic diffusion models have received widespread attention due to their unique ability to handle noise through forward and reverse processes. This noisebased framework allows for flexible customization in learning the complex distributions of social propagation using various social context information, such as user profiles [Jiang et al., 2023], and the propagation structure [Zhu et al., 2024]. Consequently, diffusion models are extensively researched and applied in the generation of propagation graphs within social networks [Cao et al., 2024].

However, existing diffusion models present certain challenges when applied to graph data. Firstly, the forward pro-

continuous, which limits their effectiveness in capturing the discrete nature of graph structures in social networks. Secondly, the reverse process of probabilistic diffusion models typically begins with Gaussian noise, and the iterative reconstruction process often fails to fully eliminate the inherent error, leading to the persistence of bias. Such a biased distribution may not align well with the true underlying distributions of social network graphs.

To overcome these limitations, we propose a Prior based Discrete Diffusion Model (PDDM) for social graph generation. Firstly, PDDM redefines the forward process to adhere to a discrete Markovian process, in which the denoising module learns the node sequence. Secondly, PDDM establishes a new starting point for the reverse process by utilizing user similarity as the probability matrix to mitigate reverse starting bias. These improvements for forward and reverse processes enhance the flexibility and realism of diffusion models for social graph generation. Moreover, it is worth noting that PDDM ensures that the denoising module focuses on node-level tasks, specifically the edge probabilities between new nodes and previously denoised nodes. This enables the convenient use of lightweight models, such as Graph Attention Network (GAT), within the framework, demonstrating the model's generalizability and scalability. The main contributions are as follows.

• To address the limitations of continuous forward processes in traditional diffusion models for the discrete graph generation task, we propose a discrete Markovian forward process. This reformulation enables the denoising module to effectively learn the connection probabilities between new and previously denoised nodes, making the model better suited for capturing discrete structure characteristics.
• To mitigate the bias introduced by Gaussian noise in the reverse process, we introduce a novel reverse process starting point based on user similarity as the probability matrix. The prior guidance of social context ensures that the reverse denoising process more accurately reflects the true structure of social networks, decreasing the bias influence from the random noise.
• PDDM allows for the easy integration of lightweight deep graph models, demonstrating the flexibility and applicability to a wide range of graph generation tasks.

2 RelatedWork

Graph generation is the task of generating graph-structured data that can serve various applications, including molecular design, social network modeling, and recommendation systems [You et al., 2018a; Jin et al., 2018]. With the advancement of deep learning, researchers have employed deep generative models (such as variational autoencoders, generative adversarial networks, and autoregressive models) for graph data generation [Faez et al., 2021; You et al., 2018b]. For instance, GraphVAE employs the encoder to map a graph to a latent space and the decoder to reconstruct the graph from this representation [Simonovsky and Komodakis, 2018]. This allows for the generation of novel graph instances by sampling from the learned latent space. MolGAN combines graph structures with generative adversarial networks to generate molecular graphs [De Cao and Kipf, 2018]. DAVA adopts a variational autoencoder with exponential distribution sampling for graph-level generation and focuses on user attributes for edge-level generation, allowing for a more nuanced approach to capture user-driven dynamics in the social graphs [Hou et al., 2024].

Denoising diffusion probabilistic models have demonstrated significant potential in various generation fields such as image and video [Ho et al., 2020]. Compared to the aforementioned methods, diffusion-based graph generative models are capable of modeling complex dependencies and generating diverse graph structures [Liu et al., 2023b]. Jo et al. introduce a continuous-time generative model, using stochastic differential equations to model the joint distribution of nodes and edges in the graph diffusion process [Jo et al., 2022]. However, this continuous encoding disrupts the sparsity of the graph. Therefore, DiGress gradually adds noise through independent graph edits (addition/deletion/modification) and trains a graph transformer network to learn the noise process, simplifying the learning of graph structure data distribution into a general classification task [Vignac et al., 2023]. Further, Kong et al. propose an autoregressive diffusion model for graph generation, defining absorbing node states on discrete graphs. In the forward process, each step involves a node autoregressively decaying to the absorbing state, while in the reverse process, a denoising network learns the reverse node absorption diffusion process to reconstruct the graph structure [Kong et al., 2023]. However, the reverse process in these models usually starts with Gaussian noise, and the iterative reconstruction often fails to completely eliminate the inherent errors, resulting in the persistence of bias. This biased distribution may not accurately match the true underlying distributions of social network graphs.

3 Method

This section presents the prior based discrete diffusion model for graph generation. First, we introduce the problem definition and a unified strategy for the graph automorphism. Then, we describe the modifications made to the probabilistic diffusion model for a discrete closed-form solution of social graph generation.

3.1 ProblemDefinition

Consider a directed acyclic graph G = (V, E, F ), which represents a propagation graph from social platforms. In this graph, V denotes the set of users, E = {(vi, vj)} represents the propagation paths, where each directed edge from vi to vj indicates that information flows from user vi to user vj. The feature set F contains user-specific attributes, such as profiling and behaviors. In our setting, F includes description, blue verification status, location, registration date, number of posts, number of fans, and number of followings.

The objective is to design a generative model that can generate a new network G′ = (V ′ ,E′ , F ′ ), where V ′ , E′ , and F ′ are the sets of users, propagation paths, and user features in the newly generated network. The generated network G′ should exhibit statistical characteristics that closely match those of the observed network G.

3.2 Graph Automorphism

Existing diffusion-based generative models assign a unique ID to each node in the initial graph in order to obtain the unique decay ordering [Chen et al., 2021; Kong et al., 2023].

However, this strategy could limit reusability across different graphs. Therefore, a unified influence evaluation strategy based on user profiles is employed.

The six categories of user profiles are collected into F ∈ R|V |×7 . A label vector y of length |V | is constructed, where each entry indicates whether the corresponding cascade is rumor-associated or non-rumor-associated. To avoid scale biases in the chi-square test, we normalize F to F ′ using MinMax normalization, ensuring each feature is within the [0,1] range [Patro and Sahu, 2015]. This enables a fair comparison of feature importance. Next, we perform the Chi-Squared test on F ′ and y to compute the Chi-Squared statistic for each feature. A smaller p-value indicates a stronger association between the feature and cascade classification. The Chi-Squared statistic for the j-th feature is defined as [Moore, 2017]:

where f ′k (c, v) is the k-th normalized feature of the user v in the c-th cascade, and µ0fk and µ1fk are the expected values for all non-rumor and rumor-associated cascades, respectively. After sorting the importance of different features {f ′1 , f ′2 , ...}, a unique one-hot encoding representation I(v) for each user based on the sorted dimension{f ′1 , f ′2 , ...} can be obtained.

3.3 Discrete Forward Process of PDDM

The forward process of the diffusion model is mathematically described by the following equations [Ho et al., 2020]:

These equations define the probabilistic progression from any state xt-1 to xt, where βt are variance parameters that control the noise level at each step.

To eliminate the bias from the random Gaussian noise, we introduce the similarity matrix P as the new starting point to guide the reverse process with the underlying probability of the nodes. Therefore, we use P as a guiding component to adjust the latent distribution space of G, i.e., ˜G:

where P can be conveniently fetched using the variational strategy and attention mechanism. ˜Gt is viewed from a probabilistic perspective, ensuring the smoothness of reverse process and the diversity of the graph generation.

Here, to enhance the applicability of probabilistic diffusion models to the discrete space, we modify the Gaussian noise matrix I. Instead of continuous noise, the variance in graph is transformed into a learnable single interaction matrix ψt, corresponding to the propagation edge from node i to node j set to 1. And an operator ⊙ is defined in a discrete way to handle the perturbations on the graph. However, predicting a single interaction matrix ψt with extremely spare topology is infeasible. To address this, we reformulate the problem into a classification task, as shown in Fig. 2. By leveraging GNNs, we can effectively solve this classification problem without the need to directly predict the interaction matrix. Therefore, in this framework, the sparse matrix is utilized solely for deriving a closed-form solution, rather than being directly predicted as noise.

Theorem 1. As T →∞, ˜GT →P in Eq. (4). Proof: Without loss of generality, we define αt = 1 - βt, and ¯αt = ∏ti=1 αi. Starting from the iterative diffusion equation:

where ¯αt = ∏ti=1 αi, ψt-1, ψt-2, · · · is the single interaction matrix at each step, ψt-1 ⊙ψt-2 sums the single interaction matrix cumulatively, ¯ ψt-1 = ⊙t-1 i=0 ψt-1. G-ψ can be interpreted from a discrete perspective, as shown in Fig. 2. Therefore, the operations involving G and graph variance ψ are strictly discrete, involving only discrete 0 or 1 updates. In the spatial domain, this corresponds to progressively learning the graph structure by incrementally adding edges as the forward process progresses. As t increases, the cumulative interaction matrix ψ gradually approximates G, reflecting the original graph's topology.

As T → ∞, the product √ ¯αT tends to zero due to the properties of the parameters αt which are designed such that 0 ≤ αt < 1. This leads to √ ¯αT (G0 - ψ) vanishing, and the expression simplifies to:

converges to P. Therefore, ˜GT →P as T →∞. ■ Theorem 2. PDDM ensures a 95% confidence interval for

optimal performance when min |V | ≥ 15.

Proof: To achieve a 95% confidence interval, the perturbations introduced by the cumulative interaction matrix ψ must be constrained within the region around 0, consistent with the properties of standard Gaussian noise, which has a mean of 0. This ensures that the original graph information is retained during the generation process. Consider a propagation graph with |V | nodes, the average edge density is given by:

where ϕ is the threshold derived from the z-value corresponding to the 95% confidence interval, which represents a 95% confidence that the desired threshold ϕ does not deviate far from the mean (i.e., 0). From the CDF of the standard normal distribution, the z-value corresponding to a cumulative probability of 0.525 is approximately z = 0.063. Using this z-value as ϕ, we can solve the quadratic inequality and get |V | ≥ 15. This condition is easily achievable in social networks, which typically involve more than 15 users.

■

Algorithm 1 Training for PDDM

Input: A total of K propagation graphs Gk = (Vk, Ek, Fk). Output: Optimized parameters θ.

• 1: repeat
• 2: V,E, F ∼ q (Gk)
• 3: Determine the number of the diffusion step T = |V |
• 4: Sort user influence I in ascending order based on F
• using the Chi-Squared statistic
• 5: Deploy a deepmodule θ1 to learn similaritymatrix P
• 6: for t = 1 . . . T do
• 7: Select the smallest influence node vt = I[t]
• 8: G(V, E, F ) ← (V \ vt, E \ vt, F \ vt)
• 9: Gt ← Absorb(G, vt ) //Absorb node vt by connecting it to all nodes in G
• 10: Yt ← {binary label(vt,w) | (w, v) ∈ E}
• 11: Define a denoising module ˆ Yt = θ2 (P, Gt )
• 12: Take gradient descent step on: ∇θ ∥∥∥Yt - ˆ Yt∥∥∥2
• 13: end for
• 14: until converged
• 15: return optimized parameters θ

3.4 Reverse Process of PDDM

As defined in Sec. 3.3, the optimized forward process establishes a discrete framework for graph structures and converges to the prior similarity matrix P. Further, PDDM reconstructs the original graph by iteratively denoising these perturbations. As shown in Fig. 3, the reverse mechanism leverages P to guide the denoising steps, effectively mitigating the bias introduced by random Gaussian noise and ensuring that the generated graph accurately mirrors the underlying social network structure. Similarly to the forward process, by transforming the denoising task into a binary classification problem, the reverse process uses the trained lightweight models to predict edge probabilities.

It is worth mentioning that in the reverse process, directly using the autoregressive step for graph generation is feasible. However, this strategy can lead to issues such as overfitting and a lack of diversity in the generated graphs. In contrast, PDDM employs a closed-form solution based on q(Gt-1|Gt,G), leveraging a robust probabilistic foundation. By deriving a discrete version, the reverse process is grounded in a well-defined probabilistic framework, ensuring that the generation process adheres to statistical principles. This results in more diverse graph generation and a closer reflection of real-world social graph distributions.

Consistent with the traditional diffusion model [Ho et al., 2020], the variational lower bound (VLB) for PDDM is given by:

where G0 is the original graph G, and G1:T represents the graph denoising the node in a user influence increment order. Here, LVLB serves as the objective function to be maximized during training, ensuring that the generated graph G′0 closely resembles the original graph G. Among them, the summation ∑Tt=2 KL (q(Gt-1 | Gt,G)∥pθ(G′t-1 | G′t )) represents the cumulative KL divergence between the true reverse distribution q and the model's reverse distribution pθ across all diffusion steps. Minimizing this term aligns the model's predictions with the true data distribution. The conditional probability distribution of the reverse process is as follows:

Given that the forward process is a Markov chain, q(Gt | Gt-1,G) is independent of G, thus we can get:

Theorem 3. For a |V | × |V | sparse matrix G with exactly t elements equal to 1 and all other elements equal to 0, and a |V | × |V | Gaussian matrix X where each element Xij is independently sampled from the standard normal distribution N (0, 1), scaling X by a factor of √t |V | ensures that the variance of each element in the scaled matrix ˜X = √t |V | X matches the variance of the corresponding element in G.

Proof. Consider the sparse matrix G ∈ {0, 1}|V |×|V | where exactly t elements are 1 and the remaining |V |2 - t elements are 0. For large |V |, the mean µG and variance σ2G of each element Gij are approximately:

Since the number of nodes in a social network is large, the above equality condition is easily established. Now, consider the Gaussian matrix X ∈ R|V |×|V | where each element Xij ∼ N(0, 1). We can get the variance Var(Xij) = 1.

To match the variance of the sparse matrix G, we scale the Gaussian matrix X by a factor c = √t |V | , resulting in the scaled matrix ˜X = cX. The variance of each element in ˜X is then:

Thus, by setting c = √t |V | , we ensure that:

Therefore, the scaled Gaussian matrix ˜X has consistent variances that match those of the sparse matrix G.

■

Based on Theorem 1, we can get the three forward equations q(Gt | Gt-1), q(Gt-1 | G), and q(Gt | G) in Eq. (7). And through scaling, Theorem 3 ensures that the variance remains consistent across different diffusion steps and guarantees smoothness. Based on the probability density function, Eq. (7) can be further expanded as follows:

After the single interaction matrix is evaluated, the perturbation coefficient can be determined as follows:

And the mean can be determined as follows:

Based on q(Gt | G) = √ ¯αt(G- √1- ¯αtψt-1) + (1 - √ ¯αt)P , we can get:

Then, Eq. (10) for µt-1|t can be demonstrated as follows:

Thus, the variance σ2 t-1|t of the posterior conditional distribution from a probabilistic perspective is given by Eq. (9), and the mean µt-1|t is expressed by Eq. (12). With these closed-form solutions established, we can predict the edge appearance discretely and the graph sampling continuously, which ensures the discreteness required for graph generation tasks while also enhancing the diversity.

The training process of PDDM is demonstrated in Alg. 1. In lines 2-5, the algorithm solves the graph permutation problem based on the user influence evaluation and deploys a deep module θ1 to learn the similarity matrix P. Then, lines 7-12 iterates over the discrete absorbing process and the denoising module θ2 predicts the constructed binary label Yt. This procedure repeats until convergence, ensuring that PDDM learns to handle the discrete structure of social networks while capturing rich propagation characteristics. However, discrete learning for the edge consistently replicates the original graph edge connection distribution. This coarse-grained replication lacks transferability in unseen continuous spaces and cannot guarantee the diversity of the generative capacity.

Therefore, the closed-form reverse diffusion process in Alg. 2 from T to t1 corrects the coarse-grained replication. After T iterations, the cumulative interaction matrix ψ is guided by the prior P from a probabilistic perspective, while the variance introduced in line 7 is correctly scaled according to Theorem 3. Finally, edges with the highest probabilities are selected based on a permutation influence order, reconstructing ˆG with diversity by robustly introducing randomness.

4 Experiments

4.1 Datasets and Baselines

We use real-world propagation graphs on Weibo and Twitter platforms for graph generation, namely Weibo [Ma et al.,

Algorithm 2 Graph generation process of PDDM

Input: The optimized denoising module θ; A candidate user set (V, F).

Output: The generative graph ˜G.

• 1: Determine the number of the diffusion step T = |V |
• 2: Sort user influence I in ascending order
• 3: P = θ1(V, F), ˜Gt ←P
• 4: Compute Y1 · · · Yt and construct ¯ ψt-1 · · · ¯ ψ0
• 5: for t = T, . . . , 1 do
• 6: z ∼ N(0, I) if t > 1, else z = 0
• 7: σ2 t-1|t = t |V |2 · (t-1)¯αt-1 (t-1)¯αt-1+1 //Eq. (9)

• 9: ˜Gt-1 = µt-1|t + σt-1|t · z
• 10: end for
• 11: return ˜G = argmaxv∈permutation ˜G0(v)

Table 1: Statistics of the datasets. G is the largest component of the joint historical relationship network based on UIDs.

To highlight the generative performance of the proposed methods, we choose seven SOTA methods for comparison. And we compare the SOTA methods of DAVA [Hou et al., 2024], GRAPHARM [Kong et al., 2023] (denoted as ARM), DAGG [Han et al., 2023], GVAE MM [Zahirnia et al., 2022], D-VAE [Zhang et al., 2019], GraphVAE [Simonovsky and Komodakis, 2018], GraphRNN [You et al., 2018b].

4.2 Experimental Setting

We use two strategies to evaluate the performance of data generation. (1) Following the SOTA settings, we use 80% of the graphs as training set and the rest 20% as test sets [Kong et al., 2023] for each dataset. We measure generation quality using the maximum mean discrepancy (MMD) [Kawai et al., 2019] as a distribution distance between the generated graphs and the test graphs. We generate the same number of samples as the test set for each dataset, based on the users in each graph of the test set. Specifically, we compute the MMD of degree distribution and the normalized minimum number of graph edit distances required to transform the generated graphs into real-world graphs in the test set. (2) To demonstrate the practicality of the generated data in real-world scenarios, we use source localization as an example to explore whether utilizing generated data can enhance the model's predictive ability in real-world contexts. We also report the generation time of different methods.

4.3 Overall Performance

MMD Based Metric Evaluation

Tab. 2 summarizes the MMD evaluation results for the generated propagation graph across all social platforms. To ensure the generalizability and reusability of the proposed framework, we employ convenient GCNs and GATs as the denoising module. It can be seen that PDDM consistently outperforms existing methods, achieving an average 15.60% reduction in MMD compared to the best baseline across datasets, both in terms of degree distribution and normalized graph edit distances. The improved generation capability of PDDM can be attributed to three main factors. (1) The developed discrete forward diffusion process enhances the learning ability to capture discrete structure characteristics from the perspective of edge connection probability, which provides a suitable strategy for topology generation. (2) The employed new reverse starting point mitigates random Gaussian noise bias, leveraging user similarity as the probability matrix to ensure more accurate structure generation aligned with social context. (3) The application of the reverse diffusion process in a probabilistic distribution space not only corrects the coarsegrained generation but also introduces robustness to enhance the diversity of generated graphs.

We further incorporate diversity-related metrics, including Uniqueness and Novelty [Vignac et al., 2023; Xu et al., 2024b]. Specifically, Uniqueness reports the fraction of generated non-isomorphic graphs, and Novelty reports the fraction of the generated graphs that are not isomorphic to any graph from the training set. The Unique and Novelty columns in Table 3 show that PDDM consistently maintains high diversity.

Utility of Generated Data in Downstream Tasks

Many downstream tasks, such as information cascade prediction, influence maximization, fake news detection, and source localization, rely on propagation models [Hou et al., 2024]. To analyze whether generated data can enhance model performance in downstream tasks, we use source localization as a case study. The convenient localization models GCNSI [Dong et al., 2019] and TGASI [Hou et al., 2023] can easily use the generated snapshots for training and source prediction. In the experiment, we use four groups to ensure the rigor of the study.

• The original group trains the localization models on 90% of the Twitter propagation data and tests on the remaining 10%.
• The augmentation group of PDDM additionally generates 1,000 propagation graphs using PDDM and adds the generated graph to the training set.
• The augmentation group of SOTA models additionally generates 1,000 propagation graphs using DAVA and GRAPHARM for training.
• The control group simulates 1,000 snapshots using traditional SI, SIR, IC, and LT models.

As shown in Tab. 4, training on simulated data from traditional models leads to reduced performance on downstream tasks in real-world propagation scenarios, indicating limited applicability of these models to actual tasks. In contrast, augmenting with real generated data results in improved performance, with the best results observed when using propagation data generated by PDDM. This highlights the significance of realistic graph generation and underscores PDDM's effectiveness in enhancing model performance.

4.4 Ablation Study

We further study the effectiveness of the components to verify their contributions to graph generation tasks. The critical ablation settings include:

• "P →N(0, I)" uses the standard Gaussian noise in the DDPM instead of the user similarity matrix at the T step.
• "Discrete →DDPM" uses the Vanilla DDPM [Ho et al., 2020] instead of the proposed discrete forward process.
• "-Reverse" removes the reverse diffusion process of the probabilistic distribution perspective.
• "-Att" removes the graph attention module, and only the GCNs are available.
• "-PE" does not consider the time step index in the denoising module.

As shown in Tab. 5, it will lead to a performance decrease no matter removing or exchanging any critical modules. Among the changes, the most significant performance drop occurs when the discrete forward process is omitted. This suggests that the discrete forward process plays a pivotal role in capturing the inherent topology characteristics of the graph generation task. Without the discrete process, the model struggles to effectively learn the edge connection distribution, leading to distinct degraded performance. Furthermore, the influence of the diffusion framework is found to be greater than that of the denoising module. This highlights the crucial role of the proposed diffusion framework in ensuring effective graph generation. The results indicate that the PDDM framework benefits most from its novelly designed forward and reverse processes. Additionally, the attention mechanism has the greatest impact on the generation time, as it is involved in every step of the computation, resulting in significant overhead.

5 Conclusion

In social graph generation tasks, existing probabilistic diffusion models may face challenges such as the limited ability to handle discrete topology characteristics and the introduced bias at the reverse starting point sampling by the random Gaussian. In this paper, we introduce a prior-based discrete diffusion model to address these limitations. By redefining the forward process as a discrete Markovian process, PDDM transfers the random noise learning task to the edge connection probability learning task from a discrete generative perspective of social propagation graphs. Furthermore, by introducing a novel reverse process starting point based on user similarity as the probability matrix, PDDM mitigates reverse starting bias and aligns better with the true structure of social networks. Not only does PDDM outperform in terms of MMD metrics, but the generated data also leads to improvements in downstream tasks, proving the practical significance.

Acknowledgments

This research was supported by the National Natural Science Foundation of China (Nos. 62271411, U22A2098, 62261136549, 62471403), the Technological Innovation Team of Shaanxi Province (No. 2025RS-CXTD-009), the International Cooperation Project of Shaanxi Province (No. 2025GH-YBXM-017), the Fundamental Research Funds for the Central Universities (Nos. G2024WD0151, D5000240309).