1 Title
Generative Diffusion Models on Graphs: Methods and Application（Chengyi Liu , Wenqi Fan, Yunqing Liu, Jiatong Li, Hang Li, Hui Liu, Jiliang Tang and Qing Li）【IJCAI 2023】
2 Conclusion
This paper reviews representative algorithms for three variants of graph diffusion models, i.e., Score Matching with Langevin Dynamics (SMLD), Denoising Diffusion Probabilistic Model (DDPM), and Score-based Generative Model (SGM). Then, it summarizes the major applications of generative diffusion models on graphs with a specific focus on molecule and protein modeling. Finally, it discusses promising directions in generative diffusion models on graph-structured data.
3 Good Sentences
1、Particularly, autoregressive generation methods are designed to generate desired graphs in a sequential process, while oneshot generation methods generate the entire graph with topology structure and node/edge feature in one single step.（The role of traditional autoregressive models in graph diffusion）
2、Traditional graph generation methods rely on leveraging hand-crafted graph statistics (e.g., degrees and clustering coefficients properties), and learning kernel functions or engineered features to model the structural information.Although these deep generative methods have achieved promising performance, most of them still have several limitations.（The limitation of previous graph model and graph generative methods）
3、Most existing diffusion models for images are developed in continuous space. In contrast, the discrete nature of graph-structured data makes it hardly possible to directly deploy diffusion models on them. In this case, several works have tried to make diffusion models suitable to be used in discrete data by introducing discrete probabilistic distribution or bridging the gap between continuous and discrete spaces while there is still a lack of a universal and well- recognized method to solve this problem.(The probably frutrue direction of these methods)
主要的图生成范式分为两类：
1、自回归生成(Autoregressive Generation)：自回归生成模型将图的生成过程建模为一个递归的条件概率分布，每个节点和边的生成都依赖于之前生成的节点和边。
2、一次性生成(One-shot Generation)：一次性生成模型则直接生成完整的图样本。
由于图数据的复杂特征，基于图的生成模型仍面临着3大挑战 :
1.离散性 (Discreteness)：图的数据结构是离散的，由节点和边组成。这增加了图生成模型的训练和优化的复杂性（例如梯度的计算）。这使得广泛应用的优化算法难以直接应用于反向传播训练。
2.复杂的依赖关系 (Complex Intrinsic Dependencies)：图数据并非符合独立同分布,其复杂的结构依赖信息为模型生成带来了巨大的挑战。尤其对于传统的自回归模型，因为生成是逐步进行的。
3.排列不变性 (Permutation Invariance)：由于节点在图数据中是无序的，所以对于相同的图最多有种等价的表示方式。但是传统的生成模型对节点的顺序是敏感的，不同的排列会导致不同的生成结果。这要求生成模型对节点排列的变化具有鲁棒性
扩散模型(Diffusion Model)是一种新兴的生成式模型，其首先向数据分布中逐步添加随机噪声到预设的先验分布，然后通过学习其逆过程来重建新的数据样本。自2019年第一个扩散模型范式被提出以来，其强大的生成能力引发了研究热潮。通常而言，扩散模型具有三种生成范式Score Matching with Langevin Dynamics (SMLD)、Denoising Diffusion Probabilistic Model (DDPM)以及 Score-based Generative Model (SGM)
SMLD通过一系列递增的高斯噪声扰动原始的数据分布，然后在逆过程中学习数据分布的梯度,通过最小化分数匹配(Score Matching)的损失函数，优化生成模型的参数，并使用朗之万动力学(Langevin Dynamics)采样生成样本。这种方法通过限制噪声分布在低维流形(low dimensional manifold )上的运动和向数据分布低密度区域添加大尺度噪声提高了分数匹配的准确性。
DDPM构建了两个参数化的马尔可夫链(Markov Chain)，用预定义的噪声在离散的时间步上扩散数据，并从噪声中重建所需的样本。基于马尔可夫链的特性和重参数化技巧，DDPM可以直接通过原始数据和预定义的噪声对任意的正向扩散步进行样本采样。而反向马尔可夫过程由用神经网络参数化的高斯分布组成。神经网络将被训练以优化负对数似然的变分上界 (ELBO)。DDPM通过学习到的反向链递归地生成样本数据。
SGM使用随机微分方程(SDE)来建模扩散过程，把离散的扩散过程推广到连续的时间和空间。SGM利用标准维纳过程(Wiener Process)添加噪声到原始样本中得到扰动样本，然后通过计算扰动样本的分数梯度来估计样本的概率密度函数(PDF)以生成逼近真实数据分布的样本。
