基于图文法的逻辑型图样本生成方法

刘禹锋，杨 帆，刘 健

（南京财经大学 信息工程学院，南京 210046）

0 概述

图文法是可视化语言的一种直观规范的描述工具。作为字符文法的二维扩展，图文法产生式（图重写规则）的左右端均为符合图论定义的点边图。类似于一维字符文法，图文法主要分为推导和归约两种工作流程，其中，推导可以从初始图出发生成各类可视化语言，归约可用来验证输入图与给定文法之间的归属关系，并且已被广泛应用于可视化语言配置［1］、软件系统分析［2-3］、模式识别［4-5］等任务。总体而言，图文法的多数实际应用所涉及的主要工作流是归约，推导的作用更多体现在可视化语言的形式定义上。目前，多数图文法应用的大致流程为：根据实际需求场景设计一组产生式，再根据这些产生式分析输入图的语法结构及语义模型完成具体任务。以图文法在实体-关系（E-R）图中的应用为例，若设计一组描述E-R 图的产生式，使用这些产生式对一个任意E-R 图进行归约可以用来验证该E-R 图语法语义上的合法性，而E-R 图的生成主要由数据库设计人员在概念设计阶段进行绘制而不是由初始图推导生成。因此，多数图文法框架都会配备一个分析算法用于归约流程的实际执行，而将推导仅视作分析算法的反方向流程来定义各类可视化语言。

作为一个具有双向工作流的形式化方法，图文法的推导操作具有不少潜在应用场景，其中最直接的应用方向应属图样本的自动生成。图样本生成技术是为了应对现实世界中图样本数量不足的挑战。一部分图样本生成方法依据统计方法进行图的生成操 作，例 如Erdos-Renyi［6］、Barabasi-Albert［7］以 及Watts-Strogatz［8］，这些方法的应用流程为：首先确定图结点数量，然后根据特定概率在结点之间进行边的连接；另一部分图样本生成方法将图生成相关问题建模成函数，并通过图深度模型进行学习处理，例如GCPN［9］、GraphRNN［10］、GRANs［11］、MolGAN［12］、L-MolGAN［13］以及MoFlow［14］。总体而言，这些方法所生成均为真实图的模拟或近似图。与之相比，通过图文法的产生式依据严格的图匹配和嵌入转换要求所生成的图样本的归属关系是确定的，生成结果具有其他方法难以比拟的准确性，在一些场景下也可以作为其他图生成模型的补充方法。例如，若使用图文法进行E-R 图的生成，只要产生式的设计符合规范，那么根据这些产生式正确推导所生成的图的语法结构和语义模型一定是合法的，即属于文法定义的语言。然而，推导工作流在实际应用中存在的主要问题为：1）图文法形式框架为了归约算法能够顺利停机，规定了产生式规模递增约束，即产生式右图结点数量或终结点数量大于左图，而这种规模递增约束在推导操作中导致了图规模可以无限制增加，反而会出现算法无法停机的情况；2）归约是一个基于回溯过程穷举产生式和图柄（产生式一端在图中的匹配子图）的过程。对于一个给定主图和一组产生式，只要存在任意一条可归约到初始结点的通路即可证明该图的合法性。相比之下，推导过程并不存在一个明确的目标图，而从一个初始图出发可生成图的空间是无限大的，过程中所产生的不确定性给产生式和图柄的选择带来了一定的困难。

针对上述问题，本文对图文法的自动推导技术进行研究，在EGG 图文法［15］的基础上提出一种自动推导算法，以解决图文法在自动推导过程中所面临的问题，并可作为一种新型的逻辑型图样本生成方法供用户使用。

1 图文法

类似于一维字符文法，图文法可以分为上下文无关文法和上下文相关文法。上下文无关文法的产生式左端只能包含一个结点，因此具有简洁而直观的优点，例如NCE［16］和HRG［17］。与之相比，上下文相关文法没有这样的限制，其产生式左端可以是一个具有任意数量结点的图，因此具有更强的表达能力。以E-R 图配置为例，若要设计一个可以在图中已有实体之间添加联系的文法，这对上下文无关文法而言非常困难［18］，而上下文相关文法可以将多个实体都放入产生式左端以解决该问题，常见的上下文相关文法包括LGG［18］和RGG［19］。此外，为了扩展图文法的应用范围，一部分研究者尝试在文法框架中引入时间、空间等语义信息，例如SGG［20］、CGG［21］、TEGG［22］以及TGGG［23］。

作为一种基于规则的系统［24］，图文法的基本操作为L/R-application，即使用产生式右图/左图替换左图/右图在主图中所匹配的子图（图柄）的过程，构成了推导或归约工作流。在替换过程中，新图的嵌入和旧图的删除都要严格依据文法上下文进行。因此，上下文描述是图文法形式框架的一个重要问题。按照上下文的形式，图文法可以分为隐式文法和显式文法。显式文法将上下文以结点的形式定义在产生式中，例如LGG 将上下文以结点的方式放置在产生式中，语义上通过通配符的方式管理结点标号的匹配。相比之下，隐式文法的产生式中不包含上下文结点。例如，RGG 的产生式中不包含上下文结点，形式更为简洁［25］，而图转换的操作都是通过结点中内嵌的顶点进行。对比两种类型的图文法，显式文法更加直观但产生式规模较大，隐式文法不够直观但形式简洁易于设计。不同于这些方法，EGG 使用了隐式文法和显式文法的一种折中形式的上下文描述形式。具体而言，EGG 产生式中虽然不包含上下文结点，但是保留了一条只有一个端点和结点相连接的边——悬边，来描述产生式的上下文。悬边仅考虑了上下文的结构信息而忽略了语义信息，因此EGG 可以在保留直观性的同时也具有较高的文法抽象性。图1 是一个EGG 产生式，产生式的两端各有两条悬边，并通过标号“1”和“2”构成双射关系。图2 是一个使用图1 产生式进行一步推导的实例，其中，图2 的上部是一个主图，虚线框内为产生式左端在主图中匹配的子图，即图柄，图的下部是使用产生式右端替换图柄产生的新主图。在L-application 操作过程中，悬边及其标号是替换操作的连接依据，保证了新主图中不会出现悬边。

图1 一个EGG 产生式Fig.1 An EGG production

图2 EGG 一步推导Fig.2 One-step derivation of EGG

2 图样本生成方法

2.1 图文法改进

如上文所述，产生式规模递增约束为图文法归约工作流的可停机性提供了保障，却给推导的自动化工作流程带来了一定的困难。一种较为直接的解决方案是进行主图规模约束，即为主图的结点数量设定一个最大值，从而使主图的规模不会在推导过程中无限制增加。然而，这种方案依然存在着不足之 处。如 图3 所 示，标号为“begin”、“end”、“statement”的结点为终结点，标号为“stat”的结点是非终结点。在该情况下，若设定主图的规模不能大于4，则无论使用哪一条产生式进行推导都会导致规模超过4。若将当前主图作为输出，由于存在非终结点“stat”，因此不符合语法上图句子的概念。针对该问题，为每个非终结点增加终结产生式。具体而言，由于每个非终结点都是一个子结构的抽象，因此将每个非终结点作为一个产生式的左端，右端为其终结形式。例如，在图4 中产生式p3 是一个终结产生式，其右端是左端非终结点的终结形式。需要注意的是，为了应对不同上下文，每个终结产生式（初始图为左端以及改进前存在的产生式除外）的悬边均使用通配悬边的形式，即在主图中可以匹配任意数量的边。如图4 所示，在限制主图规模不大于4 的情况下，使用终结产生式p3 可以生成所有结点均为终结点的主图。

图3 EGG 递增约束Fig.3 Size-increasing restriction of EGG

图4 终结产生式的应用Fig.4 Application of terminal productions

在推导的自动化过程中还存在产生式和图柄的选择问题。由于推导不需要归约过程中的穷举和回溯，为每个产生式p 绑定一个应用概率a，而同一个产生式的不同图柄具有相等的替换概率。具体而言：在一个文法中，具有相同左端的不同产生式概率之和等于1，而不同左端的产生式组具有相等的总应用概率。例如，图5 是一个由4 个EGG 产生式构成的文法，其中产生式p2、p3、p4 具有相等的左端，它们的应用概率之和等于1，而p1 是唯一包含初始图λ为左端的产生式，因此产生式p1 的应用概率等于1。具有相同左端不同产生式的具体概率可以通过先验知识或者图数据学习而来。由于实例产生式所描述对象为程序流程图，在语法结构上可以分为顺序、选择、循环3 种具备同等重要性的基本结构，因此假定相同左端的产生式在设计阶段具有相等的初始概率，而实际应用概率可以根据具体场景以及统计数据进行调整。此外，由于推导过程中匹配的是产生式左端，因此在产生式设计时应尽可能减少左端结点数量，以提高图柄查找效率。

2.2 图自动推导算法

给定一个文法，经过上述的改进操作后，便可以执行图自动推导算法，如算法1 所示。具体而言，输入主图G、产生式集合P、初始图λ以及图样本最大结点数m，输出一个样本图，算法执行过程可以大致分为以下4 步：

步骤1判断G中所有结点是否均为终结点，如果所有结点均为终结点则返回主图；如果所有结点均不符合要求，则执行步骤2。

步骤2对产生式集合P中每一个满足GsizepL.size+pR.size≤m的产生式，查找其左端在主图中的图柄：如果所有产生式均满足要求，则在产生式附加属性RedexSet 中记录产生式的图柄，并在MatchedPSet集合中记录该产生式，执行步骤3；如果所有产生式均不满足要求，则输入文法错误，算法终止。

步骤3在MatchedPSet 集合中根据产生式应用概率挑选一个产生式及其图柄，执行步骤4。

步骤4根据选中的产生式及图柄对主图执行L-application 操作，并返回步骤1。

算法1图自动推导算法

2.3 时间复杂度分析

定理1基于EGG 图自动推导算法的图样本生成方法的最坏时间复杂度为O(ml+1)，其中，m是图样本的最大规模，l是产生式左端的最大结点数。

证明首先，循环Loop 1 和Loop 3 均需要|P|次迭代，|P|是产生式数量，Loop 2 需要m次迭代；其次，在Loop 1 和Loop 2 中，循环体一次执行需要的计算次数分别为常数c1和c2，在Loop 3 中，函数FindRedex（）从规模为m的主图中为规模为l的左图查找图柄，最多需要次计算，循环体内其余代码开销为常数c3；函数L-application（）用产生式右端替换图柄，最多需要m次计算，剩下代码的开销为常数c4；最后，该算法是一个递归函数，由于产生式规模递增约束，该函数的最大递归次数为2m-1，其中，m-1 次递归用于增加结点，m次递归用于非终结点到终结点的转换。综上所述，所提方法的最坏时间复杂度可表示如下：

由于产生式集是在设计阶段确定的，其产生式数量|P|在推导阶段可以看作一个常数，因此时间复杂度t=O(|P|×ml+1)=O(ml+1)，证明结束。

通过上述证明过程可以发现，所提方法的时间开销在一定程度上受到产生式数量|P|的影响，因此终结产生式的增加带来了额外的时间开销，然而并没有影响其数量级。此外，终结产生式的最大数量是非终结点的数量，而抽象自子结构的非终结点的数量通常小于语义信息更丰富的终结点，因此文法中终结产生式在产生式组中的数量占比通常也较小。表1 列出了所提方法和5 种常见图样本生成方法的时间复杂度。由于左端结点数量大于等于1，因此所提方法的时间复杂度大于等于Erdos-Renyi［6］、Barabasi-Albert［7］、Watts-Strogatz［8］和GraphRNN［9］且大于GRANs［10］。然而，由于产生式左图结点数在推导阶段是一个常数，所提方法的时间复杂度仍然位于多项式级。与之相比，图文法归约算法则多数需要指数级的时间开销，根本原因在于归约中产生的大量回溯，而推导过程并不存在一个具体的目标图，因而避免了回溯的发生。此外，若按照上下文无关文法的要求设计产生式，即产生式左端有且只有一个非终结点，则所提方法的时间复杂度可进一步降为O(m2)，与Erdos-Renyi、Barabasi-Albert、Watts-Strogatz 以 及GraphRNN 方法相等。

表1 不同图样本生成方法的时间复杂度比较Table 1 Comparison of time complexity of different graph sample generation methods

3 程序流程图样本生成案例

本节给出一个将EGG 图自动推导算法应用在程序流程图样本生成中的实际案例。选择程序流程图作为案例的原因在于：程序流程图是一种较典型的可视化语言，包含了多数可视化语言所依赖的顺序、选择、循环3 种控制结构。图6 是一组用于描述程序流程图的EGG 产生式，其中，非终结点的标号为｛λ，stat｝，终结点 的标号 为｛begin，end，if，endif，while，endwhile，T-loop，T-fork，statement｝。由于产生式中不存在非终结点“λ”（文法初始图）的终结产生式，因此在文法改进时增加一条终结产生式，如图7 所示。

图6 一组描述程序流程图的EGG 产生式Fig.6 A group of EGG productions for program flowchart

图7 增加的终结产生式Fig.7 Added terminal production

使用上述产生式可以执行EGG 图自动推导算法，从而生成限制规模下（在该模块中规模为10）的程序流程图样本。如图8 所示（彩色效果见《计算机工程》官网HTML 版），在EGGSS 环境中开发了一个新模块用于演示该过程，其中在每一步推导过程中可以通过点击“随机选择产生式”按钮随机选择一条左端在主图中存在图柄的产生式，点击“随机图柄”按钮可以随机选择一个图柄，并用红色边框标识该图柄，随后点击下一步按钮可以执行L-application，生成一个规模不大于10 的新主图。图9 是在该模块下使用图6 和图7 产生式推导生成的一组程序流程图样本，其中每个结点都是终结点且每个图的规模（即结点数量）不超过10。

图8 一个程序流程图样本的生成过程Fig.8 Generation process of a program flowchart sample

图9 一组程序流程图样本Fig.9 A group of program flowchart samples

在未涉及先验知识和统计数据的情况下，相同左端不同产生式的应用概率具有相等的初始值。例如，在图6 中每个产生式左端为“stat”结点产生式的应用概率均为1/6≈16.67%。为了根据实际应用场景及时调整应用概率，通过该模块推导出了100 个图样本，并对其图样本规模（即结点数量）分布进行统计与分析。如图10（a）所示，53%的图样本规模等于1，即仅通过图7 中终结产生式执行一次推导操作生成了只包含终结点“empty”的图，而在剩下47 个图样本中包含规模为3 的图样本的比例为21/47≈44.68%，即初始图在使用图6 中产生式p1 进行推导后，直接使用p5、p6、p7 中的任意一个产生式进行推导而生成的图样本。显然，该分布情形与多数实际工程不符：首先工程中通常不存在如此高比例的空程序（仅含结点“empty”的流程图）；其次在规模限制为10 的情况下，规模不大于3 的图样本比例达到了74%，样本的平均规模过小，仅为3.16。总体而言，出现上述现象的原因在于：

图10 图样本规模分布Fig.10 Size distribution of graph samples

1）在图6 和图7 中左端为初始图λ的产生式仅有2 个，它们的应用概率分别为50%，导致推导出50%左右的单结点样本。

2）当初始图通过产生式p1 推导出规模为3 的主图时，下一步推导可以使用所有左端为“stat”结点的产生式（数量为6），每个产生式的应用概率为1/6≈16.67%，而在这些产生式中可以直接将“stat”结点转换成终结点的产生式有3 个（p5、p6、p7），因此在它们应用概率相等的情况下这一步生成图规模为3 的概率达到（1/6）×3=50%。

上述问题可以通过调整产生式应用概率来解决。一方面大幅度降低图7 中终结产生式的应用概率，在左端为λ的产生式中，将产生式p1 的应用概率从50%调整为90%，而终结产生式的应用概率从50%降为10%；另一方面适当降低产生式p5、p6、p7的应用概率，在左端为结点“stat”的产生式中，将p2、p3、p4 的应用 概率分别从1/6≈16.67% 调整为25%，产生式p5、p6、p7 的应用概率从1/6≈16.67%分别降为1/12≈8.33%。图10（b）描述了根据调整后应用概率进行推导所生成的图样本规模分布，可以看出规模为1 的图样本比例从53%降为9%，规模为3 的图在规模2～9 中的图样本比例也由原来的接近21/47≈44.68%降到了24/91≈26.37%左右，图样本的平均规模也由3.16 增长至6.87。若实际需求场景要求图样本的平均规模进一步增加，则可按照该方式继续调整产生式应用概率。

4 结束语

图文法的应用聚焦于图语法语义的分析，而图推导工作流仅作为图语言的形式定义存在，其原因在于推导过程中存在停机问题以及产生式和图柄选择问题。本文提出一种基于EGG 图文法的图自动推导算法，并将其用于图样本生成。首先，设计一种图文法改进方法，通过为非终结符定义终结产生式解决推导的停机问题。其次，为每个可匹配的产生式及其图柄关联概率，这些概率来自先验知识或样本学习，再根据这些概率进行图的自动推导。分析推导算法的时间复杂度得到算法时间复杂度是多项式级的，远小于多数图文法归约算法的指数级时间开销。此外，给出一个在EGGSS 环境中开发的图样本生成模块，使用该模块可以有效生成一定规模内的图样本，并通过程序流程图的样本生成作为案例演示了推导算法执行的详细过程。实验结果表明，与其他图样本生成方法相比，所提方法具有较高的准确性，原因在于只要是严格按照产生式推导生成的图，就一定是产生式所属文法所定义的语言，并且所提方法非常适用于对准确性要求较高的应用场景，也可作为传统统计方法的一种补充方法使用。

一般特定专业领域的设计人员通常不了解文法产生式，常见的解决方案是提升产生式形式的直观性，例如形状文法［26-27］使用形状作为产生式的基本元素，在建筑分析、场景重构以及艺术设计领域取得了广泛的应用［28］，然而形状文法由于格式上不符合图论定义而不属于图文法的范畴，其语法语义的分析能力不足，在未来研究中将尝试研究产生式的自动提取技术，降低设计人员的工作量和难度。此外，需要进一步规范和统一产生式和图柄的选择概率及探索基于逻辑的图文法和机器学习方法的融合应用，从而满足更多实际应用场景的需求。