基于圖文法的邏輯型圖樣本生成方法

劉禹鋒，楊 帆，劉 健

（南京財經大學 信息工程學院，南京 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］，然而形狀文法由于格式上不符合圖論定義而不屬于圖文法的范疇，其語法語義的分析能力不足，在未來研究中將嘗試研究產生式的自動提取技術，降低設計人員的工作量和難度。此外，需要進一步規范和統一產生式和圖柄的選擇概率及探索基于邏輯的圖文法和機器學習方法的融合應用，從而滿足更多實際應用場景的需求。