摘要
图模拟是图处理与分析领域中最基础的问题之一。它可以帮助用户在不同规模上生成新图，以模仿许多应用中的现实世界图（如社交网络、生物网络和信息技术）。本文聚焦于最重要的一类图生成器——通用图生成器，这类生成器旨在无论在哪一领域都能重现观察到的图属性。尽管已有大量图生成器被提出，但该领域仍存在多个重要的研究空白。在本文中，我们首先概述了现有通用图生成器（包括近期出现的基于深度学习的方法），将其分为四类：简单模型基生成器、复杂模型基生成器、自动编码器基生成器和GAN基生成器。随后，我们对20种代表性图生成器进行了基于17个评估指标和12个现实世界图的全面实验评估，并提供了在不同场景下如何选择通用图生成器的一般性指导路线。此外，我们提出了一种新方法，在模拟质量和效率之间实现了良好的权衡。为帮助研究人员和从业者在其应用中使用通用图生成器或对所提出的通用图生成器进行综合评估，我们还实现了一个可供公众使用的端到端平台。
关键词图生成器· 图神经网络· 图模拟· 实验评估
1 引言
由于图具有强大的表达能力，电子商务、网络安全、社交网络、军事、公共卫生等领域的众多研究人员正转向图建模以支持现实世界的数据分析[11,22,67–70,78]。例如，在生物信息学中的药物发现中，图可用于建模化合物与蛋白质之间的相互作用（每个节点表示化合物或蛋白质，边表示它们之间的相互作用）[28,29,43,59,75]。在社交网络中，一个节点可以代表用户，一条边可以表示两个用户之间的关系（如友谊）[7,50,53]。
在图处理与分析领域，数据收集或生成是关键步骤。在某些应用中，使用图生成器（即图生成模型）基于现实世界图数据生成模拟图有两个重要原因：(1) 完整现实世界图的不可获取性；(2) 更好地理解图结构分布和其他特征。例如，在[61]中强调的数据采集是负责任的数据管理中的关键步骤，收集或生成代表性数据至关重要。在某些场景下，由于不完全可观测性、隐私顾虑和公司/政府政策等限制，用户只能获取现实世界图的小样本。此时有必要使用与现实世界图具有相似规模和分布的代表性图用于训练或性能评估目的。例如，在系统开发初期同时启动系统开发与数据收集是常见做法，尤其是当数据采集成本高昂（如反恐应用）或两项任务由不同团队管理时。为了更好地在系统开发过程中调整或验证算法的效率和可扩展性，使用具有代表性的大规模模拟图在真实大规模图可用之前是非常理想的。另一个例子是阿里巴巴集团图计算团队与蚂蚁集团金融数据分析团队在基于图模式的欺诈检测方面的合作。具体来说，图计算团队旨在开发高效且可扩展的图模式检测算法，在金融网络中发现异常图模式，从而使金融数据分析团队能够快速识别潜在威胁。由于金融网络数据具有敏感性无法直接发布，已部署图模拟器为图计算团队生成大规模金融网络。此外，图生成器可以为基于图的学习模型训练提供大量模拟图[29,75]。通过学习现实世界图的分布，图生成器也有助于更好地理解现实世界图。例如，图生成器可用于生成源代码[12] 和公式[76]，从而帮助理解图数据中的洞见。图生成器可以用于获取大规模网络的节点表示[34]，并从知识图谱中提取多重关系语义[71]。分子图生成器提取化合物分布并设计新的合理药物[60,75]。一些研究人员使用图生成器为模型架构搜索创建神经网络结构[72,74]。
1.1 研究动机
由于图生成器在直接相关应用中的重要性，许多领域（如数据库、数据挖掘和机器学习）对图生成器的研究已有悠久的历史。读者可参考近期综述[11]以了解该研究方向的全面概述。本文聚焦于通用图生成器，这类生成器旨在无论在哪一领域都能重现观测图的结构特性，在图生成模型研究中具有基础性意义。尽管已取得诸多突破性成果，我们仍注意到存在若干尚未解决的重要问题，这些问题构成了本实验论文的核心动机。
1. 缺乏对新兴深度学习基通用图生成器的全面综述
随着深度学习技术的进步，自编码器和生成对抗网络（GAN）等先进的生成模型已在图像、音频等多个领域广泛应用于数据生成，显著提升了传统方法的性能。不出所料，这些技术最近也已应用于图生成器（如[10,18,42,73,77]）。然而据我们所知，文献中尚未出现对这些新兴深度生成图模型的全面综述。例如，在近期关于图生成器的综述论文[11]中，作者仅在挑战与开放问题章节简要提及了若干基于机器学习的通用图生成器。
2. 缺乏通用图生成器的系统性、综合性性能比较
从本质上讲，图结构复杂，难以显式捕捉观测图的分布。例如，包含n个节点的图可通过至多n!种等价邻接矩阵表示，每种对应不同的任意节点排列/编号方式。此外，在不假设固定节点集合的情况下（如生成不同规模候选分子），我们需要学习可能图结构的分布。在这种情况下，传统图相似度指标（如图编辑距离[56]和最大公共子图[44]）无法用于判断两图是否来自相同分布。因此，与其他数据分布不同，对象集（如欧几里得空间中的点集）之间的相似性/差异性可通过数值直接衡量（如KL散度[36]和地球移动距离[14]），而我们必须依赖各种图属性的分布（如度分布）进行评估；即若两图来自相同分布，其特定属性（如度分布）对应的分布应非常相似。这催生了大量从不同视角评估两图可能性的指标，例如两个节点度分布之间的最大均值差异（Maximum Mean Discrepancy, MMD）。除模拟质量外，还有许多对研究人员和从业者在不同应用场景下决策至关重要的通用图生成器评估指标，如训练时间、推理时间、可扩展性、排列不变性和调参难度。据我们所知，现有研究通常仅考虑少数指标进行性能评估，许多值得关注的指标被忽视。此外，实验中使用的竞品数量和测试数据集规模都相当有限。我们也注意到某些论文报告的实验结果存在差异。例如，文献[42]指出GRAN [42]在蛋白质数据集上的模拟质量优于GraphRNN-S [77]，而我们的实验却得到了不同的结论。
3. 缺乏能在图模拟质量和效率（可扩展性）之间取得良好平衡的算法
传统图生成器通常依赖于明确的图模型，其对应的模拟算法通常高效且能很好地扩展到大规模图。然而这些技术是手工设计用于建模特定类别的图，缺乏从观测真实图中直接学习生成模型的能力。例如，B-A模型[3]专门设计用于捕捉经验度分布的无标度特性，但无法捕捉现实世界图的许多其他方面（如社区结构）。相反，新兴的深度生成模型在模拟质量上远超传统方法，但在将深度学习技术应用于通用图生成器时却面临效率和可扩展性低下问题。例如，基于RNN的图生成器（如GraphRNN [77]）需要存储长序列节点顺序以推断整个图的邻接矩阵，这会消耗大量时间和空间资源。尽管已有研究试图提升基于深度神经网络方法的效率，但其在模拟质量与效率（可扩展性）之间的权衡效果并不理想。例如，GRAN [42]通过每步生成一组节点加速图模拟过程，但仍需推断整个图，其邻接矩阵复杂度为O(n²)。受限于每秒浮点运算次数（FLOPS）和GPU内存容量，在我们的实验环境中无法生成超过10⁵个节点的图。
4. 缺乏通用图生成器用户的便捷工具包
为了提升特定技术的影响，提供便捷的软件库或工具包对用户快速应用这些技术至关重要。一个著名的例子是机器学习领域为支持向量机（SVM）技术开发的LIBSVM库[16]。尽管许多现有通用图生成器的源代码已公开，但据我们研究发现，目前似乎缺乏让用户便捷地将现有通用图生成器应用于其应用的软件工具包。此外，没有端到端平台供用户轻松集成他们新开发的通用图生成器以与现有方法进行综合性能评估。
1.2 贡献
本文旨在解决上述四个问题，主要贡献总结如下：
– 我们对现有通用图生成器（包括近期出现的基于深度学习的方法）进行了全面综述。我们根据其基础技术将现有方法分为四类，并详细描述了每类生成器的关键特征、代表性方法及其主要特性。
– 我们开展了系统性且全面的实验，比较通用图生成器的性能。具体而言，对所有类别中20种具有代表性的通用图生成器进行了评估；实验部署了12个流行图数据集和17个代表性评估指标，并提供了易于遵循的标准建议，指导用户在不同场景下如何选择合适的通用图生成器。我们认为这种全面实验评估将有利于学术界与工业界的实践者。
– 本研究过程中获得的经验与洞察启发我们设计了一种新型算法——可扩展图自编码器（Scalable Graph Autoencoder, SGAE），该算法能在图模拟质量与效率（可扩展性）之间取得令人满意的平衡。
– 我们实现了一个端到端平台，使研究人员和从业者不仅能够直接将多种现有通用图生成器应用于其应用，还能轻松集成他们自主开发的通用图生成器进行综合性能对比与分析。我们相信这将极大地促进未来研究及图生成器的应用发展。
论文结构安排
本文其余部分组织如下：第2节正式定义问题并概述本文评估的通用图生成器。第3节详细介绍各种图生成器及其优化目标。第4节提出对通用图生成器的若干改进方法。第5节展示通用图生成器的综合实验结果，并介绍我们开发的工具包。第6节总结全文。
2 背景
2.1 问题定义与符号表示
我们定义一个图 G = (V, E)。其中 V 表示包含 n 个节点（顶点）的集合，E 是边集（m 条边），满足 E ⊆ V × V，元组 e = (u, v) ∈ E 表示顶点 u 和 v 之间的边。图 G 也可以通过邻接矩阵 A ∈ {1, 0}^{n×n} 表示。如文献所示，我们假设 G 是无向图，因此其邻接矩阵是对称的。此外，我们将与图相关的（可选）节点特征矩阵表示为 X ∈ R^{n×d}，其中 n 表示节点数量，d 表示节点特征维度。我们用 MI 表示图 G 的初始矩阵。
问题陈述：给定一组观测图 {G}，通用图生成器的目标是学习一个生成模型以捕捉这些图的结构分布，从而生成具有相似结构分布的新图集合 {G'}。
理想情况下，通用图生成器应能够生成与观测图完全相同分布的新图。然而如第1节所述，由于图结构的复杂性，判断两图是否来自同一分布极其困难。在实践中，我们只能依赖文献中提出的代表性评估指标进行实验分析，这些指标旨在从不同视角（例如度分布）量化两个图（或图分布）的相似程度。更多细节请参见第5节。理想情况下，优秀的图生成器应能确保新生成的图在所有上述指标上与观测图保持一致的分布特性。此外，生成算法需要具备高效性和可扩展性，以满足实际应用中大规模图数据处理的需求。
2.2 研究范围
如近期综述[11]所示，现有图生成器可分为两类：通用图生成器（例如[2,10,34,77]）和领域专用图生成器（例如[6,7,30,60,80]）。值得注意的是，通用图生成器旨在模仿观测图的结构，使其能够再现诸如度分布、路径长度分布等关键属性，而与具体领域无关。领域专用图生成器则针对特定应用场景进行设计，如语义网络（例如[30]）、图数据库（例如[6]）、时序图（例如[80]）和社会网络（例如[7]）。
为开展全面且聚焦的比较分析，本文主要关注通用图生成器。在第2.3节中，我们将现有通用图生成器根据其基础技术划分为四类。对于每一类，第三部分将详细介绍其核心特征、主要特点以及代表性方法。为实现全面性能评估，我们选取了涵盖文献中各类实验的广泛代表性图数据集和评估指标作为研究样本。
2.3 通用图生成器分类
本小节根据基础技术对通用图生成器进行分类，以便读者能自然地了解这些方法的基本框架。如表1所示，我们区分出以下四类：
(1) 简单模型基通用图生成器（Simple Model-based Generator）；
(2) 复杂模型基通用图生成器（Complex Model-based Generator）；
(3) 自编码器基通用图生成器（Autoencoder-based Generator）；
(4) 生成对抗网络基通用图生成器（GAN-based Generator）。
以下是对各类别生成器的简要概述。表1还展示了每类生成器的输入参数和优化目标。
表1：通用图生成器的类别、名称、参考文献及优化目标
1. 简单模型基生成器
此类生成器依赖于已知的经典简单图模型，如二项式图模型[20]、随机小世界图模型[66]和偏好图模型[3]。这些模型可通过少量参数的公式显式表达。我们可以通过调整简单图模型的参数直接生成新图以保留观测图的某些特性（例如，对于偏好图模型保留幂律度分布[e.g., 3]）。表1列出了8种代表性简单模型基生成器。与其他类别相比，这些方法需要更少的参数，导致对观测图的表现力相对不足。为增强表现力，可以考虑分层组合多个小型"局部"简单图以生成"全局"图。例如，Kronecker图模型[37]给出了一个具体示例：小图的邻接矩阵 A_{local} ∈ {0,1}^{2×2} 可通过递归扩展为 A_{global} ∈ {0,1}^{2k × 2k}。
2. 复杂模型基生成器
通过使用参数更多的复杂模型，可以更好地捕捉观测图的特性。此类生成器依赖于概率图模型或基于决策过程的图模型（如混合成员随机块模型[1]、随机Kronecker图模型[37]和基于决策过程的图模型[18,42,77]），每种模型都需要大量参数进行建模。这些生成器通过优化似然函数来模拟新图，以拟合观测图的生成分布。表1列出了5种代表性复杂模型基生成器。
3. 自编码器基生成器
自编码器是一种无监督学习方法，用于从数据中学习表示（编码）并重构输入分布（解码），广泛应用于图像和文本生成。在自编码器基图生成器领域（即图自编码器），通常通过图神经网络（GNN）进行参数化。例如，VGAE[34]、Graphite[23] 和 SBMGNN[46] 都采用图卷积神经网络进行参数化。表1列出了3种代表性自编码器基生成器。
4. GAN基生成器
基于对抗网络（GAN）的图生成模型通过生成器与判别器之间的博弈学习稳健的观测数据分布。在GAN基图生成器领域，判别器需要保持灵活性以控制生成器输出的分布特性，例如节点潜在变量[49]、图表示[73]和随机游走[10]。相比自编码器基生成器，GAN基生成器能够产生更稳健的输出结果。表1列出了3种代表性GAN基生成器。
图1 另一种图生成器分类方式。
2.4 互补性分类
为更深入理解代表性图生成器的技术特点，在本小节中我们提供一个更为复杂且系统的分类体系（如图1所示），该体系包含5个主类和17个子类。
2.4.1 序列生成
指通过演化式建模逐步构建图G，即依赖现有不完整图生成新元素。图G可表示为一系列元素序列SN = {s₁, ..., sN}，然后通过s_{N+1} = f(SN)生成新元素（f表示生成模型，如RNN、MLP）。该类别包含以下三个子类：
1. 节点序列
GraphRNN [77] 以及[41,59,62] 采用逐个生成节点及其关联边的方式构建图。我们选择 GraphRNN 作为该类代表，因其能生成超过1000个节点的图（相比[41,59]），且在生成通用图方面表现出更优性能与影响力（相比[62]）。
2. 边序列
BiGG [18] 以及[4,5] 将图建模为边的序列。我们选择 BiGG 作为该类代表，因其在生成通用图时展现出更好的性能和可扩展性（相比[4,5]）。
3. 模式序列
GRAN [42] 以及[29,51] 通过顺序生成图模式（如节点块及其关联边）构建完整图。我们选择 GRAN 作为该类代表，因其比[29,51]具有更高的可扩展性。
2.4.2 一次性生成
指直接对整张图进行建模，即图中元素的生成无序贯依赖关系。此类生成器可进一步划分为以下3个子类：
1. 基于消息传递的编码器
VGAE [34] 和[57] 提出通过基于消息传递的编码器一次性生成整张图。我们选择 VGAE 作为该类代表，因其首次提出使用图卷积技术进行图生成。
2. 迭代解码器
Graphite [23] 采用反向消息传递解码器生成图。Graphite 被选为该类代表，因其对新型迭代解码器技术的贡献与影响力。
3. 稀疏潜在变量
SBMGNN [46] 通过建模稀疏潜在变量生成图。我们选择 SBMGNN 作为该类代表，因其在通过稀疏潜在变量保留社区结构方面的创新性贡献。
2.4.3 对抗生成
指通过生成器与判别器之间的博弈训练图生成模型。此类模型可进一步划分为以下3个子类：
1. 基于随机游走的对抗生成
NetGAN [10] 和[81] 通过对抗训练生成随机游走序列。我们选择 NetGAN 作为该类代表，因其在通用图生成方面表现更优。
2. 基于潜在变量的对抗生成
ARVGA [49] 被选为该类代表，因其在潜在变量的对抗训练方面的贡献。
3. 基于图的对抗生成
CondGEN [73] 被选为该类代表，因其在生成图的对抗训练方面的创新性贡献。
2.4.4 规则生成
指通过显式操作和少量参数建模图。此类生成器通过从预定义图族中采样节点构建图[3,37,53]，可进一步划分为以下5个子类：
1. 随机图模型
E-R [20] 通过伯努利分布（固定值参数化）为每条边进行采样生成图。我们选择 E-R、B-A 和 W-S 作为该类代表，因其在领域的影响力。
2. 偏好连接图模型
B-A [3] 通过随机添加新节点边生成无标度图。
3. 小世界图模型
W-S [66] 通过从环形图中随机重写边生成小世界图。
4. 随机类型图模型
RTG [2] 通过随机类型过程生成边列表。我们选择 RTG 作为该类代表，因其技术贡献和影响力。
5. 基于Kronecker积的图模型
R-MAT [15]、Kronecker [37] 和[47] 采用类似Kronecker积的递归删边机制建模图。我们选择 R-MAT 和 Kronecker 作为该类代表，因其在领域的影响力。
2.4.5 块生成
指通过建模“块”（即节点子集）构建图。此类模型可进一步划分为以下3个子类：
1. 标准随机块模型（SBM）[27] 最初用于建模社交网络。
2. 混合成员模型（MMSB）[1]
通过混合成员的随机块模型建模图，MMSB 对 SBM 进行了扩展以提高图模拟质量。
3. 度与聚类系数修正模型
DCSBM [31] 被提出用于修正块模型中的度分布。BTER [35] 通过双层级边采样过程修正每个块的平均聚类系数并修正度分布。
3 通用图生成器
在本节中，我们描述每类通用图生成器的关键特征，并总结其主要特性。对于每一类，我们将详细介绍其代表性生成器。
3.1 简单模型基生成器
简单模型基生成器依赖于一些经典且简单的图模型（家族），如二项式图[20]、随机小世界图[66]和优先连接图模型[3]。通常，每种图模型家族能较好地捕捉现实世界图的一个或几个特性。例如，B-A模型可以生成无标度网络，W-S模型能够捕获小世界图的关键特征。以下是该类别中8种代表性技术的详细描述。
E-R. 二项式图模型（E-R）最早由Erdős等人[20]提出并研究。在二项式图中，每条边独立生成的概率为P(Ai,j = 1) = p，其中常数p由用户控制。给定一个包含n个顶点和m条边的无向且无自环图，参数p可直接计算为p = 2m / [n(n−1)]。基于E-R模型的传统生成器实现方式对每对顶点以概率p生成边，时间复杂度为O(n²)，空间复杂度为O(m + n)。如文献[8]所示，实际应用中采用时间复杂度为O(m + n)的高效算法。
W-S. 小世界图（W-S）模型最早由Watts和Strogatz[66]提出。该模型通过重采样边来模拟真实图的随机连接，并通过调整采样概率和连接边的数量，使生成的图分布介于E-R图与完全正则图之间。基于W-S模型的生成器实现方式会随机重置每个源节点的目标节点（从正则环形图中），时间复杂度为O(k × n)，空间复杂度为O(m + n)（其中k是每个源节点连接的边数）。
B-A. 优先连接（B-A）模型[3]需要按顺序生成图节点，并为新节点添加固定数量的边，从而生成具有幂律分布的无标度图。基于B-A模型的生成器实现方式时间复杂度为O(k × n)，空间复杂度为O(m + n)（其中k是每个新节点连接的边数）。
RTG. 随机输入生成器[2]（Random-Typing Generator, RTG）创建一个二维键盘，将图中的边表示为单词。图生成过程被建模为单词输入过程，通过四个参数(K, W, q, β)控制生成分布：K是单个单词中可能的字符数，W是单词总数；q是空格键输入概率；β控制在二维键盘上随机输入对角线和非对角线字符的概率。这些参数有助于生成具有幂律度分布和社区结构的图。此外，RTG还能生成二分图。基于RTG的生成器实现方式时间复杂度为O(m log n)，空间复杂度为O(m + n + K²)。
BTER. 块级两层Erdős-Rényi模型（Block Two-level Erdős-Rényi Model, BTER）[35]旨在通过度数同时模拟真实图的度分布和聚类系数。这些特征直接从观测图中提取：首先创建亲和块，为节点分配度；然后在亲和块内部及之间分配边以匹配度分布；最后，在同一亲和块内连接节点时分配聚类系数。基于BTER的生成器实现方式时间复杂度为O(m + n)，空间复杂度为O(m + n)。
SBM & DCSBM. 随机块模型（Stochastic Block Model, SBM）[27]根据块概率矩阵B和每个块的节点数生成随机图。SBM生成的图被视为具有社区结构的ER图集合。修正度的随机块模型（Degree-corrected Stochastic Block Model, DCSBM）[31]在遵循SBM设定节点度的基础上，调整生成图的度分布。通过最大化观测图的模块度[9]选择最佳块划分方案（时间复杂度为O(m)）。确定块数量和块间边生成概率后，传统实现方式的时间复杂度为O(n²)，但如文献[31]所示，优化后的(DC) SBM生成器时间复杂度可降至O(m + n)，空间复杂度为O(m + n)。
R-MAT. 递归图模型（Recursive Matrix, R-MAT）[15]通过递归划分邻接矩阵并随机将边分配到四个象限之一来生成图。在参数优化中，我们采用作者提出的经验初始矩阵MI作为起点。R-MAT通过随机采样边以时间复杂度O(m log n)和空间复杂度O(m + n)生成包含n个节点和m条边的图。此外，R-MAT启发了Dai等人[18]将邻接矩阵的一行压缩为二叉树结构。
3.2 复杂模型基生成器
通过引入更多参数和更复杂的模型架构，统计学习与参数化模型能够以数值方式模拟和生成单个图的邻接矩阵 [1,37]。尽管相同的图可以通过 n! 种邻接矩阵排列进行表示，但这些方法仍能实现比简单模型基生成器更优的模拟质量。除了用邻接矩阵表示外，图结构还可建模为决策过程：节点和边按顺序生成，这便于对规则图进行表征和学习。以下是5种代表性复杂模型基通用图生成器的详细介绍。
MMSB. 混合成员随机块模型（Mixed Membership Stochastic Blockmodel, MMSB）[1] 采用概率模型构建图。首先从狄利克雷分布中采样节点 i 的混合成员向量 πi ∼ Dirichlet(α)（其中 α 表示参数）。随后，通过多项式分布 zi,j ∼ Multinomial(πi) 获取边的指示符。最后，从伯努利分布中采样边，其概率由边指示符的双线性函数计算得出：Ai,j ∼ Bernoulli(zT_i,j B z_i,j)，其中 B ∈ R^{K×K} 表示两个块之间生成一条边的概率矩阵。MMSB 通过最大化后验概率近似参数，但在模拟大规模图时，超参数 K（块数量）的选择较为困难。我们采用 Louvain 社区检测算法 [9] 确定块数 K。由于 MMSB 目标是逼近观测邻接矩阵，其参数更新的时间复杂度为 O(n²)，空间复杂度也为 O(n²)。值得注意的是，MMSB 的推断算法易于并行化。
Kronecker. Kronecker 图模型通过克罗内克积构建图，其中初始图是自连接的，并使用二进制矩阵表示边。随机 Kronecker 图的初始矩阵不是二进制的，而是表示生成一条边的概率。与 R-MAT 不同，初始矩阵元素之和不为 1，每条边的概率可独立计算如下：
P(Ai,j = 1) = \sum_{k=0}^{|\log n|−1} MI\left[\left\lfloor \frac{i-1}{2^k} \right\rfloor (\mod 2) + 1, \left\lfloor \frac{j-1}{2^k} \right\rfloor (\mod 2) + 1\right]. (1)
在优化阶段，Kronecker 图模型寻找最佳节点排列，并通过最大似然原理估计初始矩阵的参数。为加速生成过程，该模型模仿 R-MAT 将边递归地放入邻接矩阵中，其时间复杂度为 O(m log n)，空间复杂度为 O(m + n)。
GraphRNN. GraphRNN 部署了两个循环神经网络（RNN）。第一个称为图级 RNN，用于存储已生成的节点并生成新节点；第二个称为边级 RNN，用于存储新生成节点上的边并推断新边。每条边从伯努利分布中采样，其参数由边级 RNN 的输出决定。此时，图生成被建模为决策序列。假设 h₀ 和 hi,0 分别表示初始图状态和节点 i 的隐藏状态，则 GraphRNN 生成过程可表述如下：
hi = RNN₁(hi−1, Ai−1),
θi,j = RNN₂(hi,j−1, Ai,j−1)（hi,0 = hi）
Ai,j ∼ Bernoulli(θi,j)（j < i） (2)
其中，Ai−1 和 Ai 分别表示最后一个节点和下一个生成节点的邻接向量。在 GraphRNN 中，使用门控循环单元（GRU）[17] 编码图状态并推断节点-邻接向量。对于无边依赖性的图生成，作者提出变体 GraphRNN-S，用多层感知机（MLP）替换第二个 RNN。此时，邻接向量 Ai 从由 θi 参数化的多元伯努利分布中采样。GraphRNN-S 的生成过程可表述如下：
hi = RNN(hi−1, Ai−1),
θi,j = MLP(hi),
Ai ∼ Bernoulli(θi) (3)
该变体在生成蛋白质图和其他现实世界图时表现优异，这些图相比网格图和社区图具有更弱的边依赖性。GraphRNN-S 还推动了后续工作 [18,42] 将复杂模型基生成器扩展到更大规模的图。
将图建模为决策序列后，最重要的问题是：如何避免节点顺序影响模型的泛化性能。GraphRNN 采用广度优先搜索（BFS）排序减少观测图的排列数量，并最大化边依赖性和节点排列的概率。它逐步生成图的节点和边，每个周期的时间复杂度为 O(n²)，因此训练与推理的复杂度分别为 O(e × n²) 和 O(n²)（e 为训练轮数）。由于对节点和边存在必要依赖性，完整 GraphRNN 的生成过程无法并行执行。因此，后续工作主要致力于提升 GraphRNN 的可扩展性。
GRAN. 图递归注意力网络 [42]（Graph Recurrent Attention Networks, GRAN）旨在解决以下问题以改进 GraphRNN 性能：(1) 由于对节点顺序和边的强依赖性导致泛化能力差；(2) 仅具有一种规范节点顺序的表达能力；(3) 相比图自编码器，平行化性能较差。为减少依赖性同时保留图自回归模型（如 GraphRNN）的表达能力，GRAN 利用图注意力网络 [65]（Graph Attention Networks, GAT）在生成整张图时推断伯努利分布参数。GRAN 通过 t 步生成图，每步生成 B 个节点（称为块）。若 B > 1，则可通过从上一个块的第 S 行开始生成新块以加速过程（称为步长，1 ≤ S ≤ B）。在第 t 步生成时，GRAN 通过线性映射减小前序节点嵌入维度以生成大规模图：
Li = [Lbi,1...Lbi,B],
hi = WLi + b, ∀i < t (4)
其中 [·] 表示向量拼接操作，Li ∈ R^{Bn} 是由块输出向量拼接而成的向量。初始节点表示通过 hi = GRU(hi, GAT(hi)) 进行回归更新（与文献[40]一致）。更新节点表示后，为表达一个块中的边依赖性，GRAN 通过伯努利分布混合模型推断生成边的概率：
p(Lbt |Lb1 , ..., Lbt−1 ) = \sum_{k=1}^{K} α_k \prod_{i∈bt} \prod_{j≤i} θk,i,j,
α₁,...,α_K = Softmax\left(\sum_{i∈bt,j≤i} MLP_α(hi − h_j)\right),
θ₁,i,j,...,θK,i,j = Sigmoid(MLP_θ (hi − h_j)) (5)
其中 K 为混合组件数量。当 K > 1 时，由于潜在的混合组件存在，生成边不再独立，但仍能保持并行化无损失的边依赖性。
为在多个规范节点顺序下学习图生成模型，GRAN 提出最大化对数似然下界的新目标：
log p(G) = log \sum_{π} p(G, π) ≥ log \sum_{π∈Π} p(G, π) (6)
其中Π 表示选中的图节点规范顺序集合。选择的规范顺序越多，该界越紧。
受图神经网络（GNN）并行性的启发，GRAN 通过调整块大小和步长 S，在计算成本与生成性能之间提供灵活权衡，其每轮时间复杂度为 O(n²/S)。在生成大规模图时（如我们实验环境下超过500节点的图），其效率和可扩展性显著优于 GraphRNN。
BiGG. 受递归图模型 [15]（RMAT）启发，BiGG 是一种具有树结构的图自回归模型。假设 G 为稀疏大图（m ≪ n²），仅生成边而非每个节点的邻接向量更为高效，可表述为：
p(A) = p(e₁)p(e₂|e₁)...p(emu|e₁, ..., e_{m-1}) (7)
其中每条边 ei = (u, v) 包含两个节点索引。因此生成过程包含 m 步。在先前工作中，单个边可分解为 p(ei) = p(u)p(v|u)，且假设 p(v|u) 是 n 个节点上的简单多项分布，导致复杂度 O(n)。BiGG 通过将 p(v|u) 表述如下减少指定 v 的决策数量：
p(v|u) = \prod_{i=1}^{\log_2 n} p(xi = xv_i ) (8)
其中 xv_i ∈ {left, right} 表示节点序列中第 i 个决策，p(xi = xv_i ) 表示第 i 个决策导致 v 的概率。注意 xv_i = left（right）表示在节点 v 的第 i 个决策中选择左（右）子树。BiGG 使用 Eu = {(u, v) ∈ E} 表示连接节点 u 的边集合，Nu = {v | (u, v) ∈ Eu} 表示 u 的邻居节点集合。对于每个节点 u 的邻接矩阵行，生成所有边 Eu 等价于生成二叉树 Tu（其中每个 v ∈ Nu 从根节点开始生成至叶节点）。每个节点 t 通过其左子树 lch(t) 和先前生成的节点作为条件生成，右子树 rch(t) 在生成左子树及其依赖后生成（类似于二叉树中序遍历）。设 contextu(t) 和 contextu(lch(t)) 分别表示节点 t 的前文上下文和其左子树摘要上下文，则递归生成的 p(Eu) 可表述为：
p(Eu) = p(Tu) = \prod_{t∈Tu} p(lch(t))p(rch(t))
= \prod_{t∈Tu} p(lch(t)|contextu(t)) p(rch(t)|contextu(t), contextu(lch(t))) (9)
其中 p(lch(t)|·) 和 p(rch(t)|·) 是由 TreeLSTM 网络 [63] 参数化的伯努利分布。至此，邻接矩阵 A 的每一行可通过二叉树构建递归生成，p(E) = \prod_{u=1}^n p(Eu) 需要 O(m log n) 时间。完整模型按行依次生成邻接矩阵。类似地，BiGG 将 n 个边二叉树的根节点建模为节点摘要上下文，并递归构建行二叉树，耗时 O(n log n)。BiGG 生成图的时间复杂度为 O((m + n) log n)，在生成大规模稀疏图时尤为高效。二叉树中每层参数可并行更新，仅需 O(log n) 步，相较于 GRAN 和 GraphRNN-S 的 O(n) 步更高效。
3.3 自编码器基生成器
在图自编码器（Graph Autoencoders, GAEs）出现之前，复杂模型基图生成器面临生成性能的瓶颈。得益于变分自编码器和深度学习技术的进步 [32,52]，研究人员将自编码器扩展至图表示学习与图生成领域。同时，图神经网络 [33,65,69,78] 也在图表示与生成模型方面展现出卓越效果。
图2 自编码器基生成器框架概览
如图2所示，自编码器基生成器采用以下框架：首先使用编码器学习观测图的表征（即编码），并通过深度图神经网络（GNN）捕获概率参数。通过添加随机噪声，可对潜变量进行重参数化，并利用解码器重构（即解码）出新图。GNN的参数将根据模拟精度进行更新。上述过程重复直至生成高质量的新图（如重构误差较小）。以下介绍三种代表性自编码器基图生成器。
**VGAE.** 变分图自编码器 [34] 由Kipf等人提出，旨在自然提取节点特征并推断观测图的生成分布。VGAE使用GNN [33] 作为图数据的编码器。其参数化为W的GNN层定义如下：
$$
\text{GNN}_W(X, A) = \bar{D}^{-1/2} \bar{A} \bar{D}^{-1/2} X W \quad (10)
$$
其中 $\bar{A} = A + I_n$ 表示添加自环的邻接矩阵，$\bar{D}$ 为 $\bar{A}$ 的度矩阵（$\bar{D}_{i,i} = \sum_j \bar{A}_{i,j}$）。VGAE使用两层GNN推断随机变量 $Z \in \mathbb{R}^{n\times f}$ 的参数，其中 $f$ 表示潜变量维度。对于GAE模型，推理模型 $q(Z|X, A)$ 参数化如下：
$$
Z = \text{GNN}_{W_2}\left( \sigma\left(\text{GNN}_{W_1}(X, A)\right) \right) \quad (11)
$$
其中 $\sigma$ 表示非线性激活函数。生成模型定义为节点潜变量的双线性函数，即 $P(A_{i,j} = 1) = \sigma(Z_i Z_j^T)$，其中 $Z_i$ 表示节点 $i$ 的潜变量。VGAE有两个优化目标：一是重构邻接矩阵，二是逼近先验分布。这导致以下变分下界优化：
$$
L = \mathbb{E}_{q(Z|X,A)}[\log p(A|Z)] - \text{KL}\left(q(Z|X, A) || p(Z)\right) \quad (12)
$$
其中 $p(A|Z)$ 为生成分布（$p(A|Z) = \prod_{i,j} p(A_{i,j}|Z_i,Z_j)$），$\text{KL}(·||·)$ 表示Kullback-Leibler散度，用于衡量两个分布间距离，而 $p(Z)$ 是高斯先验（$p(Z) = \prod_{i=1}^n \mathcal{N}(Z_i | 0, I)$）。VGAE生成新图需 $O(n^2)$ 时间与空间复杂度 $O(m + n)$，训练过程中每轮时间为 $O(n^2)$。
**Graphite.** Graphite [23] 的工作方式与VGAE相似，其使用图神经网络参数化变分自编码器的迭代生成模型。Graphite的主要贡献在于用节点表示与中间图替代了VGAE的内积解码器。解码过程公式如下：
$$
Z^* = \text{GNN}_\theta(\hat{A}, [Z | X]), \quad \hat{A} = \frac{ZZ^T}{||Z||_2} + I_{n\times n} \quad (13)
$$
其中 $\theta$ 表示GNN参数，[·|·] 表示拼接操作。$\hat{A}$ 是中间图，在矩阵中加入常数1以保持非负性。特征矩阵 $Z^*$ 可逐步优化直至获得最终特征生成邻接矩阵。
Graphite在编码器与优化目标上与VGAE一致，但由于内积运算的存在，其时间复杂度仍为每轮 $O(n^2)$，空间复杂度为 $O(m + n)$。尽管迭代解码器的实现加速至 $O(n \times f^2)$（$f$ 为潜变量维度），但整体性能与VGAE类似。
**SBMGNN.** Nikhil等人 [46] 提出了一种稀疏变分自编码器，通过融合SBM的可解释性与图神经网络的快速推理能力。如MMSB所示，SBMGNN使用印度自助过程（Indian Buffet Process, IBP）的stick-breaking构造推断社区成员规模，公式如下：
$$
v_k \sim \text{Beta}(\alpha, 1), \quad k = 1, ..., K \\
b_{nk} \sim \text{Bernoulli}(\pi_k), \quad \pi_k = \sum_{j=1}^k v_j \quad (14)
$$
其中 $K$ 表示社区数量，$\pi_k$ 是所有成员归属的概率。与MMSB不同，SBMGNN通过图神经网络推断这些分布的变分参数。SBMGNN还使用变分图自编码器（VGAE）逼近密集潜变量 $r_n$。与VGAE相比，SBMGNN将节点嵌入建模为 $z_n = b_n \odot r_n$（其余部分保持一致）。目前，推断过程可定义如下：
$$
q_\phi(v_{nk}) = \text{Beta}(v_{nk} | \text{GNN}_\alpha(X, A), \text{GNN}_\beta(X, A)) \\
q_\phi(b_{nk}) = \text{Bernoulli}(b_{nk} | \text{GNN}_\pi(X, A)) \\
q_\phi(r_n) = \mathcal{N}\left(\text{GNN}_{\mu_n}(X, A), \text{diag}(\text{GNN}_{\sigma^2_n}(X, A))\right) \quad (15)
$$
SBMGNN的图生成过程与其他自编码器基生成器相同。其推断与生成模型的整体优化目标可表述为这些近似分布的KL散度与重构损失之和，这一目标可从VGAE的目标函数扩展而来。SBMGNN的时间复杂度为 $O(n^2)$，通过增加更多参数实现了模型的可解释性。
图3 生成对抗网络（GAN）基生成器框架概览
3.4 GAN基生成器
生成对抗网络 [21]（Generative Adversarial Networks, GANs）的核心思想是通过判别器生成高质量且鲁棒的伪造数据。如图3所示，GAN基图生成器的关键在于：使用图生成器建立从随机变量到图伪隐变量的映射，并将其与真实图的编码隐变量一同输入判别器。这些模型的目标是使生成器稳定运行并产生逼真的隐变量，进而解码以模拟现实图。以下介绍三种代表性GAN基生成器。
**ARVGA.** 对抗正则化变分图自编码器 [49]（Adversarial Regularized Variational Graph Autoencoder, ARVGA）旨在生成图嵌入。给定一个图G，通过与VGAE相同的图编码方法获得隐变量矩阵Z。然后判别器通过优化以下交叉熵损失函数多次更新参数：
$$
\mathbb{E}_{z \sim q(\cdot|Z)} [\log(1 - D(z))] + \mathbb{E}_{a \sim N(\cdot|0,I)} [\log D(a)] \quad (16)
$$
其中 $z$、$a$ 分别是从Z和真实数据分布 $N(0, I)$ 中采样的向量，$D$ 基于标准多层感知机（MLP）构建。在每次更新图自编码器参数前，判别器的参数会多次更新。
ARVGA与VGAE的主要区别在于：前者通过判别器直接将编码器输出正则化为先验分布，而后者仅通过KL散度逼近先验分布。生成的鲁棒嵌入在链路预测和节点聚类任务中表现出优于VGAE的性能。ARVGA每轮时间复杂度为 $O(n^2)$，因此训练与图推断的时间复杂度分别为 $O(e × n^2)$ 和 $O(n^2)$（$e$ 为训练所需的轮数）。
**NetGAN.** NetGAN [10] 是首个通过随机游走生成图的模型。它利用长短期记忆网络 [26]（Long Short-Term Memory, LSTM）生成随机游走序列。随机游走序列越长，LSTM捕获的拓扑信息越多。当序列长度为2时，NetGAN将直接学习边概率。
作为NetGAN生成器组件的输入，其初始细胞状态 $C_0$ 和隐藏状态 $h_0$ 通过以下方式从多元正态分布映射：
$$
z \sim N(0, I) \\
C_0 = MLP(C)(z),\quad h_0 = MLP(h)(z) \quad (17)
$$
其中 $MLP(\cdot)$ 包含两个线性层和tanh激活函数。随后，参数为 $\theta$ 的LSTM可开始推断随机游走：
$$
(p_1, C_1, h_1) = LSTM(C_0, h_0, 0),\quad v_1 \sim \text{Cat}(\text{Softmax}(p_1)) \\
(p_T, C_T, h_T) = LSTM(C_{T-1}, h_{T-1}, v_{T-1}),\quad v_T \sim \text{Cat}(\text{Softmax}(p_T)) \quad (18)
$$
其中 $\text{Cat}$ 表示分类分布。目前，生成器 $G$ 可按顺序生成随机游走 $(v_1, ..., v_T)$。然而，$p_T$ 和 $v_T$ 的维度为 $n$，导致LSTM计算成本较高。为此，使用上投影矩阵 $W_{\text{up}} \in \mathbb{R}^{h × n}$ 将LSTM输出 $o_T \in \mathbb{R}^h$ 映射至 $\mathbb{R}^n$；下投影矩阵 $W_{\text{down}} \in \mathbb{R}^{n × h}$ 用于将节点 $v_t$ 映射为LSTM的低维输入。生成的随机游走与真实随机游走被输入参数化为另一个LSTM的判别器 $D$，后者输出随机游走为真实的概率。模型参数通过Wasserstein GAN [24]（WGAN）框架进行训练。
更新生成器 $G$ 参数后，通过组装邻接矩阵可将推断出的随机游走解码为新图。得分矩阵 $S$ 表示生成随机游走中每条边出现的概率。随后，每条边 $(i, j)$ 从由 $p(i,j) = \frac{s_{i,j}}{\sum_{u,v} s_{u,v}}$ 参数化的分类分布中采样。整个图的边通过选择得分矩阵前 $m$ 个最大值生成。由于NetGAN的边采样策略，其图生成过程时间复杂度为 $O(n^2)$，节点数和边数分别固定为 $n$ 和 $m$。
**CondGEN.** 条件变分自编码器结合生成对抗网络（Conditional Variational Autoencoder with GAN, CondGEN）[73] 提出时考虑了条件图结构的编码与生成。其主要贡献是通过修改VGAE中随机潜变量 $Z$ 的推导，实现了排列不变性和平行生成任意规模图的能力：
$$
\bar{\mu} = \frac{1}{n} \sum_{i=1}^n g_\mu(X, A)_i,\quad
\bar{\sigma}^2 = \frac{1}{n^2} \sum_{i=1}^n [g_\sigma(X, A)_i]^2 \\
q(z_i | X, A) \sim N(\bar{z} | \bar{\mu}, \text{diag}(\bar{\sigma}^2)) \quad (19)
$$
其中 $g(X, A) = \text{GNN}_{W_2}(\text{ReLU}(\text{GNN}_{W_1}(X, A)))$ 是一个两层GNN模型。$\bar{z}$ 的建模对保持排列不变性至关重要，可视为图 $G$ 的嵌入表示。从 $\bar{z}$ 中采样的样本也可通过基于FNN的解码器解码为新图。
在对抗优化目标方面，不同于ARVGA，CondGEN设计用于学习观测数据的生成分布：
$$
L_{\text{gan}} = \log D(A) + \log(1 - D(G(Z_p))) + \log(1 - D(G(Z_q))) \quad (20)
$$
其中 $D$ 是两层GNN后接两层FNN，$Z_p$ 和 $Z_q$ 分别是从高斯先验和潜变量分布 $q(z_i | X, A)$ 中采样的隐变量。CondGEN旨在学习一组图的结构分布，并生成排列不变图，其可通过对应条件进行控制。由于CondGEN中的谱嵌入推导，其每轮训练时间复杂度为 $O(n^3)$。在我们的实验中，CondGEN无需任何编码过程即可生成新图，因此其推理时间复杂度为 $O(n^2)$。
表2 通用图生成器的时间复杂度、可扩展性及排列不变性
3.5 总结
本小节从时间和空间复杂度角度对图生成器进行总结，并评估了其重要属性（如排列不变性和社区保留性）。
**时间复杂度**：在表2中，我们报告了每种生成器的学习（训练）过程和新图推断过程的时间复杂度。通常，简单模型基生成器无需训练过程，可轻易计算所需参数（时间复杂度 $O(m + n)$）。由于模型的简洁性，其推理时间也非常高效。其他类别的生成器则需要更多学习和推理时间。许多图生成器的主要成本是邻接矩阵的生成，导致推断过程的时间复杂度为 $O(n^2)$。对于基于深度神经网络的生成器，学习时间由网络结构和训练轮数决定。特别地，现有通用图生成器使用的GNN和RNN具有每轮时间复杂度分别为 $O(m + n)$ 和 $O(n^2)$。由于CondGEN中的谱嵌入推导，其训练过程每轮时间复杂度为 $O(n^3)$。我们指出总训练时间还依赖于所需的训练轮数。在我们的实验中，GraphRNN相较于CondGEN需要更多训练时间，因其训练过程中涉及的训练轮数较多。
**空间复杂度**：表2报告了每种生成器的空间复杂度。通常，部分生成器非常节省空间，因为它们只需存储观测图（空间 $O(m + n)$）。注意对于基于深度神经网络的生成器，我们假设顶点潜变量（即嵌入）维度为常数（实践中通常为32、64或128）。对于图神经网络（GNN），我们将邻接矩阵和单位矩阵存储为稀疏矩阵，成本为 $O(m + n)$ 而非 $O(n^2)$。因此，基于GNN的生成器空间复杂度为 $O(m + n)$。对于通用递归神经网络（RNN）如GraphRNN-S和GRAN，我们需要存储节点序列的长期记忆，其空间消耗取决于节点数量。包括观测图在内，RNN基生成器对应的空间复杂度为 $O(m + n)$。MMSB、GraphRNN和NetGAN是空间占用最多的生成器，因为MMSB和GraphRNN需要维护所有n个节点的概率图，而NetGAN需构建空间复杂度为 $O(n^2)$ 的得分矩阵。
**排列不变性属性**：表2展示了具有排列不变性属性的生成器。该属性意味着我们可以随意设定图节点的学习顺序，且不会影响图生成器的模拟和生成结果。具有排列不变性属性的图生成器无需考虑节点顺序即可泛化到大规模图，可能产生 $O(n!)$ 个实例。
**社区保留属性**：表2还表明了具有社区保留属性的生成器。图生成器需要较好地保留观测图的社区结构。例如，具有相似社区结构的模拟图可用于增强社区检测。
4 改进
本研究获得的经验与洞察使我们能够设计出一种新方法——可扩展图自编码器（Scalable Graph Autoencoder, SGAE），该方法在图模拟质量与效率（可扩展性）之间取得了良好的平衡。
我们的方法遵循VGAE [34] 的框架，并在以下三个方面引入了新的技术改进：
**编码器**
我们首先利用图神经网络（GNNs）对图进行编码并推断节点表示。GNN的实现方式如下：
$$
\bar{A} = \bar{D}^{-1/2} (\tilde{A}) \bar{D}^{-1/2} \\
X_{i+1} = \text{GNN}_i(X_i, \bar{A}) = \bar{A} X_i W_i \quad (21)
$$
其中 $\tilde{A}$ 是包含自环的邻接矩阵（$\tilde{A} = A + I_n$），$\bar{D}$ 是 $\tilde{A}$ 的度矩阵（$\bar{D}_{i,i} = \sum_j \tilde{A}_{i,j}$），$X_0$ 默认设为单位矩阵 $I_n$，$W_i$ 是 GNN 第 $i$ 层的参数。为解决过平滑问题，我们在每层 GNN 后引入 PairNorm [79] 层以保留节点表示的距离。归一化过程如下：
$$
x_c^i = x_i - \frac{1}{n} \sum_{i=1}^n x_i \\
x_p^i = s \cdot \frac{x_c^i}{\|x_c^i\|_2} \quad (22)
$$
其中 $x_i$ 是第 $i$ 个节点的表示，$x_c^i$ 是按节点中心化的表示，$x_p^i$ 是特征归一化后的表示，$s$ 是用于调整节点表示距离的超参数。我们的编码器在每层激活函数前添加了 PairNorm 层。注意 GNN 的第一层对内存占用最大：$\tilde{A}$ 需 $O(m)$ 空间，$X_0$ 需 $O(n)$，而权重矩阵 $W_0 \in \mathbb{R}^{n×d}$（$d$ 为节点表示维度）需 $O(n × d)$。因此，编码器的时间和空间复杂度分别为 $O(n + m)$ 和 $O(m + n × d)$。
**解码器**
在本文中，我们选择每次训练时解码一个包含 $n_s$ 节点的子图。每轮训练后，从编码器获取节点表示，并从中选取 $n_s$ 个节点作为临时真实子图 $A_s$。解码器输出通过以下方式计算：
$$
P(A_{i,j} = 1) = \sigma(Z_i Z_j^T) \\
\hat{A} = \sum_{i,j \in V_s} P(A_{i,j} = 1) \quad (23)
$$
其中 $\sigma$ 表示 Sigmoid 激活函数，$\hat{A}$ 是包含 $n_s$ 节点的子图估计邻接矩阵，$V_s$ 表示该子图的节点集合。
如 Guillaume Salha 等人 [55] 所指出的，高度节点需要更频繁地训练以避免丢失重要信息。因此我们采用基于节点度数的子图选取策略：
$$
P_i = \frac{\deg_i}{\sum_{i=1}^n \deg_i}, \quad P_i 为选择第 i 个节点的概率 (24)
$$
每轮训练中，我们随机采样节点组装子图。注意 $n_s$ 是平衡效率与效果的重要超参数。然而，完整生成仍需 $O(n^2)$ 时间和空间复杂度。为此，我们改进 NetGAN [10] 的邻接矩阵组装方式：
(i) 获取 $n$ 个节点的潜变量；(ii) 对每个节点采样边以解码邻接矩阵的一行，并清除零值内存；(iii) 重复 (ii) 直至生成所有行。该过程空间复杂度为 $O(m + n)$，适用于大规模图生成。
**优化**
由于每轮计算的损失与真实损失 $L$ 存在偏差，我们采用近似损失函数 $L_{n_s}$ 优化模型参数：
$$
L_{n_s} = \frac{1}{m_s} \left[ \sum_{(i,j) \in E^{pos}} (1 - \hat{A}_{i,j}) \log \hat{A}_{i,j} + \sum_{(i,j) \in E^{neg}} \hat{A}_{i,j} \log (1 - \hat{A}_{i,j}) \right] \quad (25)
$$
其中 $m_s$ 表示子图中的边数，$E^{pos}$ 和 $E^{neg}$ 分别为从 $A_s$ 中选取的正样本边和负样本边集合，$\hat{A}_{i,j}$ 是解码器输出的概率。
总体而言，我们提出的图生成器基于自编码框架，命名为 **可扩展图自编码器**（Scalable Graph Autoencoder, SGAE）。SGAE 继承了神经网络基图生成器的优秀表达能力，并在训练过程速度上相比其他深度神经网络方法实现了显著提升。具体而言，编码器和解码器每轮时间复杂度分别为 $O(n + m)$ 和 $O(n_s^2)$（$n_s$ 为采样子图大小），推理时间仍保持 $O(n^2)$，空间复杂度为 $O(m + n + n_s^2)$。与基于自编码器的生成器类似，SGAE 具备排列不变性与社区保留特性。
5 评估
我们整合了所有纳入的模型并进行了大量实验以评估图生成器的性能。我们的评估平台细节详见第5.1节。实验设置请参见第5.2节。在第5.3至第5.6节中，分别从图模拟质量、社区结构保留性、参数敏感性和模型可扩展性四个方面进行了实验。第5.6节研究了图生成器的效率和可扩展性。最后，根据全面的实验研究，在第5.7节中为用户提供了推荐路线图。
5.1 性能评估工具包
为了帮助研究人员和从业者在其应用中使用通用图生成器，或对其提出的通用图生成器进行综合评估，我们开发了一个端到端平台，并已公开提供。在该工具包的详细说明中，我们展示了：(i) 如何在用户的应用中使用现有的通用图生成器；(ii) 如何将新的、开发中的通用图生成器集成到系统中；以及 (iii) 评估指标的细节及其如何用于性能评估。目前，我们的软件包已提供Python接口，并将在未来考虑其他编程语言的支持。
平台特性简介如下：
·模块化流程
我们将数据类型定义为基于NetworkX库[25]实现的Graph对象列表。图生成器和评估指标均采用相同的输入输出类型，通过单条命令即可直接获得实验结果（包括指定的数据集、图生成器及特定评估指标）。
·自定义与扩展
我们允许用户通过将自己的实现集成到相关源代码脚本中，将自有数据集、图生成器和新评估指标添加到本地库中。我们欢迎其他开发者在GitHub上为平台贡献代码。
需要注意的是，本文所有实验均基于此平台进行。
5.2 实验设置
本节介绍实验所用的数据集、评估指标及参数配置。
数据集
我们收集了现有通用图生成器常用的一些代表性数据集（见表3）。各数据集的详细信息如下：
·引文网络：无向图，由论文及其引用关系构成。Cora和Cora-ML数据集分别包含2708和2810篇机器学习类论文；Citeseer和PubMed数据集分别包含3327和19,717篇论文。
·生物网络：从真实生物学信息中提取的图结构数据。Protein数据集包含620个节点（每个节点表示一种氨基酸），当氨基酸间距离小于6Å时形成边；Protein–protein Interaction (PPI) 数据集包含2361个节点（每个节点代表一种酵母蛋白），若两种蛋白质之间存在相互作用则生成边。
·社交网络：从真实社交关系中提取的图结构数据。Deezer数据集包含47,538个节点（每个节点表示用户），边表示用户间的友谊；Facebook数据集包含50,515个节点（每个节点代表一个页面），若页面间存在互相关注则生成边。
·其他数据集：来自真实对象的图结构数据。3D点云数据集包含5037个节点（表示家庭物品的点），基于欧几里得距离计算k近邻以形成边；自主系统数据集包含6474个节点（代表计算机网络路由器），边表示路由器间的通信。
注： 对于部分存在孤立节点或自环边的数据，无法成功运行RNN基生成器（如GraphRNN [77]、BiGG [18]）和NetGAN。因此，所有数据集的自环边均被移除，并选择最大连通分量作为图生成模型的输入。
5.2.1 评估指标
我们收集并设计了适当的评估指标以衡量原始图与生成图之间的差异。用于图模拟质量的指标可分为以下四类：
节点分布
通过计算度、聚类系数、谱嵌入、中介中心性（Betweenness Centrality）和接近中心性（Closeness Centrality）在最大均值差异（MMD, Maximum Mean Discrepancy）下的分布进行评估。两组样本从分布 p 和 q 中取样的平方MMD计算公式为：
MMD2(p∣∣q)=Ex,y∼p[k(x,y)]+Ex,y∼q[k(x,y)]−2Ex∼p,y∼q[k(x,y)](25)
其中 k 表示相关核函数。我们采用地球移动距离（Earth Mover’s Distance, EMD）作为高斯核，公式为：
EMD(p,q)=γ∈Γ(p,q)infE(x,y)∼γ[∣∣x−y∣∣](26)
其中Γ(p,q) 表示边际分别为 p 和 q 的所有分布集合，γ 是传输计划。
图元（Graphlet）分布
通过计算4节点内所有图元的出现次数，并利用总变分（TV）核的Orbit MMD公式衡量两分布间的距离：
TV(p,q)=Ei[∣∣πp(i)−πq(i)∣∣](27)
其中πp(i) 表示图分布 p 中第 i 个图元的概率。
图统计量
通过以下三个指标评估：特征路径长度（CPL）、基尼系数（GINI）和幂律指数（PLE）。CPL是所有节点对最短路径长度的平均值；GINI表示节点度分布的不平等程度；PLE是幂律分布的指数。
社区结构
分两步评估：建模社区结构并比较节点社区归属差异。对于生成图或观测图，首先使用Louvain [9] 算法获取其节点的社区成员关系，然后利用归一化互信息（NMI）和调整兰德指数（ARI）衡量两个图的社区相似性。
注意： 对于所有与图模拟质量相关的指标，较小值在性能评估中更优。所有基于MMD的评估指标中，Orbit的标准差设为30，其他标准差设为1.0。我们采用[77]中的Orbit计数实现计算4节点图元以提高效率，并从观测图中重复采样200个节点估计每个节点的中介中心性。其余评估指标设置与文献[18]和[10]一致。
5.3到5.7包含了大量的实验评估数据结果，由于篇幅原因在此省略，保留最后一张完整全面比较的打分表格，如下所示：
该表格给出了不同任务要求下的各个图生成器的表现水平，后续研究人员可以根据不同的需求选择合适的生成模型。
6 结论
图数据模拟在社交网络、电子商务和生物信息学等众多应用领域中具有基础性作用。本文通过以下四个方面的研究填补了该领域的关键空白：(i) 系统梳理20种代表性通用图生成器的概况，涵盖近期出现的基于深度学习的方法；(ii) 对20种代表性通用图生成器进行全面实验评估，并为研究人员和实践者提供跨维度的使用建议；(iii) 开发新型算法以实现图模拟质量与效率之间的良好平衡；(iv) 构建用户友好的平台，使研究者和从业者既能便捷地应用现有通用图生成器开展工作，又能即时集成自定义的生成器进行多维度性能对比与分析。