用于图生成的自回归扩散模型 笔记

1 Title

        Autoregressive Diffusion Model for Graph Generation(Lingkai Kong、Jiaming Cui、Haotian Sun、Yuchen Zhuang、B. Aditya Prakash、Chao Zhang)【PMLR 2022】

2 Conclusion        

        This study propose an autoregressive diffusion model for graph generation. Unlike existing methods, we define a node-absorbing diffusion process that operates directly in the discrete graph space. For forward diffusion, it designs a diffusion ordering network, which learns a datadependent node absorbing ordering from graph topology. For reverse generation, it designs a denoising network that uses the reverse node ordering to efficiently reconstruct the graph by predicting the node type of the new node and its edges with previously denoised nodes at a time.Based on the permutation invariance of graph, it shows that the two networks can be jointly trained by optimizing a simple lower bound of data likelihood.

3 Good Sentences

        1、Diffusion-based graph generative models have recently obtained promising results for graph generation. However, existing diffusion-based graph generative models are mostly one-shot generative models that apply Gaussian diffusion in the dequantized adjacency matrix space. Such a strategy can suffer from difficulty in model training, slow sampling speed, and incapability of incorporating constraints.(The difficult problems of previous works has not solve.)
        2、Diffusion models decompose the full complex transformation between noise and real data into man small steps of simple diffusion. Compared with prior deep generative models, diffusion models enjoy both flexibility in modeling architecture and tractability of the model’s probability distributions.(The advantages of Diffusion Model which used in graph generates)
        3、While ARDM offers an efficient and general diffusion framework for discrete data, two key questions remain to be addressed for applying ARDM for graphs: (1) How do we define absorbing states for inter-dependent nodes and edges in graphs without losing the efficiency of ARDM? (2) While ARDM imposes a uniform ordering for arriving at an orderagnostic variational lower bound (VLB) of likelihood, a random ordering fails to capture graph topology(There are still two problems which needed to solve in ARDM)
        4、Compared with the random diffusion ordering, our design has two benefits: (1) We can automatically learn a datadependent node generation ordering which leverages the graph structural information. (2) We can consider the diffusion ordering network as an optimized proposal distribution of importance sampling for computing the data likelihood,
which is more sample-efficient than a uniform proposal distribution.(The advantages of this method)


        从目标分布生成图形是许多领域的基本问题,传统随机图模型方法用强大的深度生成模型拟合图形数据,包括变分自编码器(VAEs) 、生成对抗网络、归一化流(Madhawa等人,2019)和基于能量的模型(EBMs) ,这些模型捕获复杂的图结构模式,然后生成具有所需属性的新的高保真图。

与已有的深度生成模型相比,扩散模型既具有建模结构的灵活性,又具有模型概率分布的可追溯性。然而,现有的基于扩散的图生成模型有三个主要缺点:(1)Generation Efficiency。采样过程缓慢,因为需要很长的扩散过程才能达到平稳的噪声分布,因此反向生成过程也很耗时。(2) Incorporating constraints。它们都是一次性生成模型,因此在一次性生成过程中不容易合并约束。(3)Continuous Approximation。这会使得模型训练的难度加大。

        在GRAPHARM中,本文为图设计了节点吸收自回归扩散算法,它直接将图扩散到离散图空间中,而不是在去量化的邻接矩阵空间中。前向传递通过屏蔽每个步骤中的一个节点及其连接边来吸收节点,重复此过程,直到所有用于图生成的自回归扩散模型节点被吸收,图变为空为止。除此以外,本文进一步在 GRAPHARM 中设计了一个扩散排序网络,该网络与反向生成器联合训练,以学习与数据相关的扩散节点排序。GRAPHARM 中的后向传递通过学习反向节点吸收扩散过程和去噪网络来恢复图结构。反向生成过程是自回归的,这使得 GRAPHARM 更容易处理生成过程中的约束条件。

        如何学习反向节点排序分布以优化数据似然是一个关键挑战。本文的研究表明,只需使用精确的反向节点排序,并根据图形生成的置换不变性属性优化一个简单的似然下限,就能规避这一难题。利用似然下限,可以使用强化学习程序和梯度下降法联合训练去噪网络和扩散排序网络。

一些背景知识

       吸收离散扩散的定义:吸收扩散是在离散状态空间中定义的马尔可夫破坏过程,对于time steps:t,第i个维度中的元素x_t^{(i)}都以独立概率α(t)衰变为吸收态(数据的一个维度或一旦数据进入吸收态,它就不会再对后续的扩散过程产生影响,相当于在这个维度上的信息已经被“吸收”或“丢失”了)吸收状态可以是文本的[MASK]标记或图像的灰度像素。扩散过程最终收敛到一个平稳分布,使所有元素都处于吸收态。利用分类分布学习吸收扩散的逆过程,生成原始数据。通常,衰减概率α(t)需要很小,扩散步长t需要很大才能获得良好的性能。

        自回归扩散模型(ARDM):一种随机吸收过程,其中每一步恰好有一个维度衰减到吸收状态。这个过程重复进行,直到所有维度都被吸收。

        这个定义的另一个描述是:首先采样一个队列σ,σ∈S_DS_D是一个从1到D的排列集合。然后,数据的每个维度都按照σ的顺序向吸收状态衰减,相应的生成过程然后以与排列完全相反的顺序对变量进行建模。ARDM相当于连续时间限制的吸收扩散

在本文中:两个节点之间没有边视为特定的边。

Autoregressive Graph Diffusion Process:当一个节点进入吸收状态时,会发生以下两个变化:

  1. 掩蔽(Masking): 该节点会被掩蔽,意味着在扩散过程中,该节点不再活跃,它的特征将不再对图中的其它节点产生影响。

  2. 连接所有其他节点(Connecting to All Other Nodes): 被掩蔽的节点会被连接到图中所有其他节点,这些连接通过掩蔽边(masked edges)表示。这样做的原因是在吸收状态下,我们不能确定被掩蔽节点的原始邻居节点,因此通过将它与所有其他节点连接,可以保持图中的连通性信息。

因此,图自回归扩散过程的定义如下:

        在自回归图扩散中,从扩散排序网络中采样节点衰减排序σ。然后,根据采样的扩散顺序,每次恰好有一个节点衰减到吸收状态。这个过程一直进行,直到所有的节点都被吸收。

上图是自回归图扩散过程,正向传递中,节点自回归衰减到吸收状态,由扩散排序网络产生的排序决定顺序,在反向过程中,生成网络使用反向节点排序重新生成图结构。因为扩散过程为G_0中的每个节点分配一个唯一的ID以获得衰减顺序,所以不需要考虑同自同构(具体来说就是,节点排列的置换不变性,这意味着无论节点如何重新排列,只要重新排列后的图在结构上与原始图相同,模型就能正确地生成图。)

扩散排序网络遵循循环结构,这意味着每一步 t 的节点 \sigma _t 的分布不仅依赖于原始图 G_0​,还依赖于之前所有步骤节点顺序。本文使用使用图神经网络(GNN)对图中的结构信息进行编码,为了捕获部分排序,本文将位置编码添加到节点特征中,将传递GNN后节点v_i的更新节点嵌入表示为h^d_i并参数化为分类分布。利用,grapharm就可以学习优化节点的扩散排序,不过这也需要我们推断反向传递中的反向生成顺序,这很难。

反向生成过程:一个去噪网络将按照与扩散过程相反的顺序对掩模图进行去噪。我们将设计为图注意网络(GAT),用θ参数化,使模型能够区分被屏蔽和未被屏蔽的边缘。

        在时刻t,去噪网络的输入是之前的掩模图G_{t+1},一种直接的方法是使用Gt+1,它包含了所有被屏蔽节点及其相应的被屏蔽边。然而,在最初的生成步骤中,图几乎与屏蔽边完全连接。这导致两个问题:(1)消息传递过程将由被屏蔽的边缘主导,这使得消息不具有信息性。(2)存储密集邻接矩阵占用大量内存,导致模型无法扩展到大型图。因此,在每个生成步骤中,本文只保留待去噪的被屏蔽节点及其相关的被屏蔽边,而忽略其他被屏蔽节点。

修改后的掩码图称为G'_t,如图所示

去噪网络首先使用一个嵌入层将每个节点v_i编码为一个连续的嵌入空间,即h_i= embedding (v_i)。在第l条消息传递时,通过聚合来自相邻节点的关注消息来更新节点v_i的嵌入。

,其中其中W是权重矩阵,a是注意力向量。经过L轮消息传递后,最终得到每个节点的最终嵌入h_i^L,然后预测新节点v_{\sigma_t}的节点类型以及v_{\sigma_t}与所有先前去噪节点{v_{\sigma (>t)}}之间的边缘类型。出于时间复杂度上的考虑,本文使用混合多项分布来预测新节点与所有先前节点的连接。混合分布可以捕获待生成边之间的依赖关系,同时将自回归生成步骤减少到O(n)。

训练目标:使用近似最大似然作为grapharm的训练目标。首先推导似然的变分下界(VLB)为:

其中,G_{0:n}表示t = 0,1,···,n时G_t的所有值, 为生成排序的分布。从以上公式可以看出,扩散过程引入了一个单独的逆生成排序网络。因为在中间学习过程中没有原始图G_0,所以是一个非平凡任务,然而,在自回归扩散模型的标准变分下界(VLB)中,通常会包含一个KL散度项,用于衡量真实分布和近似分布之间的差异。作者提出,可以忽略这个KL散度项,简化模型的训练过程,从而避免或者非平凡任务。

第一项将鼓励去噪网络以完全相反的扩散过程顺序预测节点和边缘类型,因此去噪网络本身可以作为生成顺序的代理。由于排列不变性,可以简单地在每个时间步用预测的节点和边类型替换任何被屏蔽节点及其被屏蔽边。因此,可以忽略第二项,最终得到一个简单的训练目标:

其中,t被当作随机变量,且符合范围为0到n的均匀分布U_nv_{\sigma _t}的节点类型和它与所有先前去噪的节点的边,即

Soft Label Training : ARDM的架构同时预测所有被屏蔽的维度,这使得并行训练的单变量条件成为可能。在grapharm中,由于图的节点排列不变性,这种并行训练可以简化为用扩散排序网络给出的概率加权的软标签训练:其中,

因此,通常只考虑那些与最高概率相关的节点标签就足够了

实验结果如图。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/596975.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【数据结构】单链表和双链表的基操实现

文章目录 一、链表的概念及结构二、链表的分类三、无头单向非循环链表1.单链表创建2.尾插和头插3.尾删和头删4.打印5.查找6.插入7.删除8.销毁 四、带头双向循环链表1.双链表的创建2.初始化3.判断链表是否为空4.尾插和头插5.尾删和头删6.查找7.插入8.删除9.销毁 五、总结链表和顺…

深入理解回溯算法

大家好,我是 方圆,本篇我们来讲回溯。回溯相当于穷举搜索,它会尝试各种可能的情况直到找到一个满足约束条件的解,寻找解的手段一般通过 DFS 实现,是一个 增量构造答案 的过程。回溯法适用于解决能够将原问题拆分成子问…

OpenSSL实现AES-CBC加解密,可一次性加解密任意长度的明文字符串或字节流(QT C++环境)

本篇博文讲述如何在Qt C的环境中使用OpenSSL实现AES-CBC-Pkcs7加/解密,可以一次性加解密一个任意长度的明文字符串或者字节流,但不适合分段读取加解密的(例如,一个4GB的大型文件需要加解密,要分段读取,每次…

常见通信协议

1、串口:(串行异步全双工,先发低位) 因为是异步的,所以没有时钟线,因为是全双工,所以有两条数据传输线,实现数据的收发。 帧格式 起始位1位,数据位8位,校验…

【C++】stack、queue和priority_queue的模拟实现

在本篇博客中,作者将会讲解STL中的stack、queue和priority_queue的模拟实现,同时还会带大家了解一下deque这个容器。 一.什么是适配器 STL中一共有6大组件:容器,适配器,空间配置器,仿函数,迭代器…

控制台调试 hover 后才出现的元素

调试 hover后才出现的元素 打开开发者工具,鼠标放在hover时才出现的元素上,然后点击右键; 不要选中任何选项,将鼠标移动到开发者工具的调试面板中; 按下N键,此时悬浮的元素不会消失,定位成功。…

Java注解介绍

注解(Annotation)是Java提供的一种元数据形式,它可以被添加到Java代码的各种元素上,如类、方法、变量、参数等。注解的作用主要包括: 1. 代码文档:注解可以用于生成文档,提高代码的可读性。 2.…

前端之深拷贝

前提: 就是在实际开发中,我有一个编辑的弹窗,可以查看和编辑,因为弹窗里面是一个步骤条,点击下一步就要向对应的接口发送请求,考虑到就比如我点击下一步,此次表箱信息其实不需要修改&#xff0…

大模型_DISC-MedLLM基于Baichuan-13B-Base医疗健康对话

文章目录 DISC-MedLLM介绍概述数据集部署推理流程 DISC-MedLLM 介绍 DISC-MedLLM 是一个专门针对医疗健康对话式场景而设计的医疗领域大模型,由复旦大学数据智能与社会计算实验室 (Fudan-DISC) 开发并开源。 该项目包含下列开源资源: DISC-Med-SFT 数据集 (不包…

智慧园区综合物业管理平台解决方案PPT(130页精品)

我们对智慧园区的理解 智慧园区,是通过信息技术和各类资源的整合,充分降低企业运营成本,提高工作效率,加强各类园区创新、服务和管理能力,为园区铸就一套超强的软实力。智慧园区的实现是多技术融合、多系统融合、多领域…

初识C语言——第十三天

关键字2: static 修饰局部变量,改变了局部变量的生命周期(本质上是改变了变量的存储类型) static修饰全局变量,使得这个全局变量只能在自己所在的源文件(.c)内部可以使用,其他源文件不能使用 …

全方位了解 Meta Llama 3

本文将为您提供 Llama 3 的全面概览,从其架构、性能到未来的发展方向,让您一文了解这一革命性大语言模型的所有要点。 Meta Llama 发展历程 Llama 1 Llama 是由 Meta(FaceBook) AI 发布的一个开源项目,允许商用,影响力巨大。Lla…

基于springboot+vue+Mysql的在线动漫信息平台

开发语言:Java框架:springbootJDK版本:JDK1.8服务器:tomcat7数据库:mysql 5.7(一定要5.7版本)数据库工具:Navicat11开发软件:eclipse/myeclipse/ideaMaven包:…

Qt | QLCDNumber 类(LCD 数字),LCD 表示液晶显示屏

01、上节回顾 Qt 基础教程合集02、QLCDNumber 1、QLCDNumber 类用于显示类似于 LCD 显示屏上的字符(见右图) ​ 2、QLCDNumber 类是 QFrame 类的直接子类,因此 QLCDNumber 以使用从 QFrame 类继承而来的边框效果 3、QLCDNumber 可显示的符号有:0,1,2,3,4,5,6,7,8,…

ue引擎游戏开发笔记(33)——武器与角色的匹配,将新武器装备到角色身上

1.需求分析: 武器能出现在世界中,完成了第一步,下一步需要角色和武器适配,即不论角色跑动,射击等,武器和角色都相匹配,将武器装备到角色身上。 2.操作实现: 1.首先先把角色原有的武…

【数据结构】--- 深入剖析二叉树(中篇)--- 认识堆堆排序Topk

Welcome to 9ilks Code World (๑•́ ₃ •̀๑) 个人主页: 9ilk (๑•́ ₃ •̀๑) 文章专栏: 数据结构之旅 文章目录 🏠 初识堆 📒 堆的概念 📒 堆的性质 🏠 向上调整算法 && 向下调整算…

vector的oj题

1.只出现1次的数字 给你一个 非空 整数数组 nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。 方法:…

【Stable Diffusion】三句话,让Ai帮你画18万张图

本文介绍Stable Diffusion的快速上手,本地部署,以及更多有趣的玩法展示。 在 DALL-E 2 和 Imagen 之后,AI绘图领域又一个热乎的深度学习模型出炉——Stable Diffusion 。8月份发布的 Stable Diffusion 更加高效且轻量,可以在消费…

第六节课《Lagent AgentLego 智能体应用搭建》

PDF链接:https://pan.baidu.com/s/1JFtvBWgEGFWJq8pHafvIUg?pwd6666 提取码:6666 Lagent & AgentLego 智能体应用搭建_哔哩哔哩_bilibili https://github.com/InternLM/Tutorial/blob/camp2/agent/README.md InternStudio 一、为什么需要agent…

网页html版面分析-- BeauifulSoup(python 文档解析提取)

介绍 BeauifulSoup 是一个可以从HTML或XML 文件中提取数据的python库;它能通过转换器实现惯用的文档导航、查找、修改文档的方式。 BeauifulSoup是一个基于re开发的解析库,可以提供一些强大的解析功能;使用BeauifulSoup 能够提高提取数据的效…