基于神經網絡的圖布局技術綜述

閆 凱， 趙鐵軍

(哈爾濱工業大學 語言技術研究中心， 哈爾濱 150001)

0 引 言

在對圖數據進行可視化分析時，首先需要進行圖的布局，將頂點數據合理地映射到二維平面的點上。一個良好的布局能夠幫助使用者快速且正確地理解可視化背后所隱含的數據本體。傳統的繪圖學領域中頂點的布局方法通常可以分為基于力引導的方法和基于降維的方法。前者通過模擬物理過程，力圖達到受力平衡的狀態，這一類方法通常會形成比較美觀易讀的布局結果；后者則通過將圖的頂點表示為高維空間中的數據點，利用降維的方式將其投影到二維平面上，所得到的布局結果往往能比較好地反映全局結構或局部的頂點位置關系。圖布局本身是NP-Hard(需要超多項式時間才能求解)的問題，這兩類算法都是通過迭代逼近局部最優，模擬退火則是最常用到的優化方式。

近年來隨著科技活動的發展，人們所要面臨的圖數據的大小和數量不斷上升，而基于迭代的傳統繪圖方法雖然能夠得到高質量的布局，但所消耗的時間成本過高。當需要處理大量的圖數據，比如社交網絡分析者想要連續查看幾十個用戶的朋友圈網絡，或者生物信息工作者想要對比數十上百的蛋白質交互過程時，這些算法的性能顯得捉襟見肘。而如果可視分析達不到實時性的要求，分析者往往會因為不同圖之間展示時的延遲，而難以形成連貫的思考和決策。

自2017年圖神經網絡研究逐漸成為熱點，陸續提出一些通過神經網絡學習出端到端圖布局模型的算法，或是其他應用機器學習和神經網絡手段對圖可視化任務進行輔助的策略。機器學習和圖布局任務的結合在當前的圖布局研究中屬于較為前沿的研究話題，調研中發現這一類的方法目前屬于零散地出現，尚沒有比較完整的綜述。本文將對神經網絡和圖布局問題的結合進行一個系統的梳理，并討論這一領域的研究前景。

1 圖布局問題概述

當前圖可視化領域中，圖數據最常用呈現方法是“頂點-鏈接圖”，這一表達方式能夠將圖中的頂點間關系、社群關系、圖上不同區域的整體結構特征等直觀地表達出來。一組2000年美國橄欖球隊比賽圖如圖1所示，頂點表示球隊，邊表示球隊之間進行過比賽，圖1(a)為圖的鄰接矩陣，行和列均表示頂點，矩陣的某一格非空表示這兩個對應的頂點有邊關聯。這種表示通常用于數據的存儲和計算而非可視化表達；圖1(b)為可視化的“頂點-鏈接圖”表示。顯然，后者能夠清晰地告訴數據分析者，該圖里有9個社群存在，事實上，這9個社群對應的正是9個不同的橄欖球聯合會。

(a) 鄰接矩陣表示 (b) 頂點-鏈接圖

當使用“頂點-鏈接圖”呈現時，頂點的坐標位置就是所要關注的重點。一個好的頂點排布能夠幫助用戶可靠地確定圖數據的整體特征。

當前圖布局技術研究領域所針對的數據對象主要是無向無權圖，即給定無向無權圖G=(V,E)，其中V是頂點集合，E?V×V是邊的集合，算法輸出為頂點到二維坐標的映射P:V→2。大部分圖布局技術的研究都是針對如何從原始圖結構G生成頂點排布P。基于神經網絡的端到端布局生成也主要面向這一問題。

另一方面，如何判定一個圖布局的質量好壞，歷來沒有統一的標準。雖然邊交叉率、邊夾角等易讀性準則受到了廣泛認可，但這些準則到底多大程度上反映了圖布局的質量，一直處于研究者們的探索之中，如何利用神經網絡進行圖布局P的質量評估，也是值得研究的重點話題。此外，由于圖布局的結果通常會經過渲染后生成具體的圖像作為可視化呈現，有一部分工作著力于直接通過渲染后的圖形來評估布局質量。

2 端到端的布局生成模型

在圖神經網絡研究領域，頂點的數目或圖的數目這兩個變量通常有一個是固定的。而在處理圖布局問題時，需要面對不同的圖數據，且每個圖的頂點數都是可變的，這使得直接設計端到端的布局模型并非平凡問題。Kwon等人[1]沒有直接進行布局結果的生成，而是將圖分解為預設的圖元，不同的圖元組合得到的布局的整體形態往往是類似的，提出以圖元的統計結果作為圖的特征，在布局之前，預測出圖可能會被布局成什么樣子，這種設計方式避開了直接去設計端到端模型，而是讓神經網絡學習出對布局渲染之后的圖像，用戶可以根據預測結果估計這種圖像是否是自己期望的布局形態，從而選擇是否采納一個可能需要大量迭代的布局算法，雖然沒有直接生成布局，但在幫助用戶減少布局過程中的試錯代價，挑選合適的算法和參數方面做出了貢獻。

在基于現代神經網絡進行端到端的圖布局生成的工作中，Leow等人[2]提出的GraphTSNE可以稱得上是較有前瞻性的研究，該方法以t-SNE損失條件(由Maaten和Hinton[3]在2008年提出的一種信息損失度量)作為神經網絡的損失函數，試圖用圖神經網絡來學習端到端的布局過程，直接從輸入的圖數據中擬合出滿足t-SNE損失條件的布局結果出來。該工作使用了兩層的圖卷積神經網絡， 使用反向傳播算法進行優化。雖然在布局效果上并沒有達到很好的質量，從網絡架構上來講也并非一個“深度”的神經網絡，但該工作的開創性在于從證明了t-SNE、布局應力準則(stress)這樣對布局進行整體描述的損失函數也是可以通過神經網絡的方式學習出來，對后來的算法有重要的啟發。

在2019年，王勇等人[4]提出了DeepDrawing算法，修改雙向LSTM網絡的結構，按照圖的結構在雙向LSTM網絡上加入LSTM單元之間的跳躍鏈接，如圖2所示，該方法是第一個實際意義上的以深度學習方式進行端到端布局學習的方法。DeepDrawing以經典算法生成的圖布局結果作為訓練數據，所訓練出的模型能夠學習到近似于原算法的布局效果，并且在推理時性能遠遠超出經典算法。但由于在每次計算時都會對LSTM結構本身進行修改，算法的訓練過程失去了現代神經網絡的并行性，在算法本身參數量巨大的情況下，訓練的性能并不高；另外，DeepDrawing以生成好的布局作為輸入，自動生成的訓練數據本身質量并不能得到良好的保障。這兩點都在一定程度上限制了DeepDrawing的可擴展性。

圖2 DeepDrawing的網絡架構[4]

Wang等人[5]提出了DeepGD算法，利用圖卷積神經網絡的堆疊，用經典算法所要優化的布局應力準則結合不同的美學指標作為損失函數，利用多目標學習的技術，直接從圖數據中生成滿足一定美觀度和可讀性需求的圖布局，效果如圖3所示。這種方法不需要利用傳統算法進行數據標注，在模型訓練上更加自由，且多層卷積神經網絡也保障了訓練時的并行性，訓練性能得以提升。但DeepGD方法為了適應卷積神經網絡的結構，需要對原始的圖數據進行修改，用全源最短路經進行重新賦權，得到完全圖作為輸入，這一過程使得模型在應用的時候并不直觀，且存在一定扭曲信息的可能。

圖3 基于各種美學準則的DeepGD布局效果[5]

Giovannangeli等人[6]提出一種稱作(DNN)2的算法，以殘差神經網絡ResNet50為基礎架構，用基于譜方法的圖卷積模塊代替了ResNet中的卷積層，以tsNet算法的優化目標作為損失函數，同時采用在隨機圖上進行預訓練的技術，得到了一個高質量的神經網絡模型，如圖4所示。當然，基于ResNet架構的模型存在其固然的缺陷，應用于機器視覺領域的ResNet模型通過大量的池化層來縮小所要處理的數據規模并聚合有效信息，而這一過程在圖數據上并沒有得到很好的應用，(DNN)2算法中并沒有這一步驟。雖然圖神經網絡本身的聚合性較強，但訓練量巨大這一問題無法避免。

(a) 基于ResNet的網絡架構

鑒于從前的算法在訓練時，損失函數或者為對標注數據的比較，或者為特定的準則函數，Tiezzi等人[7]設計了一個兩段式的學習模型，同時訓練網絡來進行布局的生成和布局質量的驗證。這一方法將布局生成和驗證結合起來，形成了一個較為統一的模型。

Safarli等人[8]用多智能體強化學習的方式，將傳統基于力引導的算法過程中通過合力對頂點進行移動的步驟，視為智能體的強化過程，將圖的布局質量作為強化學習的適應性函數。這一研究并沒有提出一種學習之后可以直接預測出新的圖數據的布局的模型，但其從另一角度對傳統算法進行了解釋，其工作為新的布局算法的設計提供了基于多智能體的一種新視角。

3 基于神經網絡的布局驗證

Mchedlildze等人[9]以文獻中現有的美學準則、圖的統計特征和用凝聚態物理學理論對頂點進行的統計分析結果作為特征向量，構造孿生神經網絡，通過向網絡中同時輸入用經典算法生成的好的布局和故意構造的差的布局，學習出一個判別模型，用來判斷一個生成的布局是否是“好”布局，而這個“好”的標準取決于這些美觀度的準則與經典的算法之間的吻合度，這種方式給出了傳統算法在美學特征上的判別尺度。但傳統算法是否完全可以作為“好 ”布局的金標準，是一個值得討論的問題，完全使用機器智能來判定圖的質量，仍有待于研究。

Haleem等人[10]使用卷積神經網絡來進行圖布局可讀性度量的計算。與使用布局本身的美學特征作為輸入數據的方法不同，其所選擇的是直接使用力引導算法布局并渲染好的頂點-鏈接圖，而所計算的內容則是如頂點傳播度、頂點沖突、邊交叉、邊夾角、邊長方差以及組間重疊等可讀性度量。利用卷積神經網絡對圖像數據的識別能力，該工作能夠對布局的美學準則進行預測，為用戶在不同布局結果圖之間進行挑選提供了有效參考信息。但當不同頂點規模的圖擁有相近的布局形態時，這種方法可能會由于圖像本身的分辨率等問題造成誤判，根據該工作所報告的擴展性，該方法能夠處理600頂點以下的圖數據，對于邊相關的準則預測的結果尚不充分。

與此類似，Cai等人[11]通過人類標注的方式，向孿生神經網絡中輸入有明顯人類選擇傾向的布局，對渲染出的圖像通過網絡學習出哪種布局更容易被人類選擇。與自動生成的好和壞的布局對相比，這種方式顯然更能體現出圖的美觀性對人類的視覺價值。然而，由于人類的視覺判別存在主觀性，這種方式得到的結果，更大程度上是從“美觀”而非“可信”視角上進行布局判定。在圖的可視化問題上，圖的可信度嚴重影響了使用者對圖背后隱含的結構化數據的理解，而人類標注數據時事實上是很難與原始數據進行合理對應的，這就使得判別出來的圖的實際可用性受到了限制。

4 結束語

針對圖布局日益增長的性能需求和神經網絡技術的蓬勃發展，近年來研究者們不斷提出基于神經網絡的圖布局算法和評估模型。本文介紹了近5年中神經網絡應用于圖布局問題的主要工作及其利弊，供需要借助神經網絡手段進行圖可視化研究的科研人員和需要進行圖數據可視化分析的分析者了解該研究領域的現狀，選擇自身科技工作任務所適宜的技術手段。

此外，通過對現有文獻的調研成果進行分析，總結出將會是這一研究領域中較有前景的主題：

(1)基于圖神經網絡的有約束布局。有約束布局一直是圖布局中較為實用的研究方向，如出版物中常常需要應對翻頁問題而對折紙的邊界進行約束；電路圖等特定布局場景下需要使用正交布局；用戶需要對選中的一些區域進行錨定等等。有約束布局往往會有比自由布局有更大的計算量和更常見的使用場景，而這一部分的研究當前仍處于空白狀態；

(2)基于神經網絡的動態圖布局或流式圖布局。動態圖相比于靜態圖，除了圖的總數量的增長以外，保持相鄰時間片之間布局的心智地圖的連貫性也是其研究要點，而流式圖相比之下更需要能實時反饋圖數據更新后的布局結果，這兩種數據在科技工作中大量存在，而現有的工作均是服務于靜態圖的技術；

(3)風格化的預訓練模型。即使在傳統布局中，用戶往往需要通過對布局參數進行調整以得到自己想要的布局效果。現有的技術中雖然已經有了預訓練方法的參與，但主要是針對數據的預訓練，而如果能使用神經網絡捕捉到布局所需要的特征本質，繼而針對具體需要的布局風格進行調優，那么布局的靈活性將會有大大的提高。