基于多層次隨機梯度下降的大規(guī)模圖布局算法
2024-12-31 00:00:00周穎鑫李學俊吳亞東張紅英王嬌張秋梅王桂娟
計算機應用研究 2024年11期
摘 要：大規(guī)模圖布局問題是圖可視化領(lǐng)域研究熱點之一。應力布局模型在保持全局布局結(jié)構(gòu)方面表現(xiàn)出色，然而其求解速度卻不及彈簧電荷模型，且局部布局質(zhì)量也有所欠缺。在維持全局結(jié)構(gòu)穩(wěn)定條件下，為提高應力模型求解大規(guī)模圖時的布局速度、改進布局局部結(jié)構(gòu)表達，提出了一個新的多層次隨機梯度下降圖布局模型。首先利用基于鄰居結(jié)構(gòu)的圖壓縮合并算法生成層次圖結(jié)構(gòu)，再使用節(jié)點最優(yōu)放置算法初始化節(jié)點坐標。最后利用融合了節(jié)點正負樣本的隨機梯度下降算法細化布局，改進局部布局質(zhì)量。同時多層次方法也有效提高了布局速度。在30個不同規(guī)模的數(shù)據(jù)集上與現(xiàn)有布局模型進行對比實驗，從布局計算效率、布局質(zhì)量以及可視化效果三個方面證明了該方法的有效性。
關(guān)鍵詞：大規(guī)模圖布局；應力模型；隨機梯度下降；多層次布局；圖可視化
中圖分類號：TP391 文獻標志碼：A 文章編號：1001-3695（2024）11-028-3394-07
doi：10.19734/j.issn.1001-3695.2024.03.0073
Large-scale graph layout algorithm based on multi-level stochastic gradient descent
Zhou Yingxin1a， Li Xuejun1a， Wu Yadong2， Zhang Hongying1b， Wang Jiao1b， Zhang Qiumei1a， Wang Guijuan1a， 1b?
（1.a.School of Computer Science amp; Technology， b.School of Information Engineering， Southwest University of Science amp; Technology， Mianyang Sichuan 621000， China; 2.School of Computer Science amp; Engineering， Sichuan University of Science amp; Engineering， Zigong Sichuan 643000， China）
Abstract：Large-scale graph layout remains a prominent focus in graph visualization research. While the stress model excels in representing global structure， its speed lags behind the spring-electric model， and its local structure quality is suboptimal. This paper proposed a graph layout algorithm， aimed at enhancing the efficiency of layout while preserving global structure and improving local quality. The model first utilized graph compression based on neighbor structure to generate a hierarchical graph structure， and then used the node optimal placement algorithm to initialize the node coordinates. Next， it improved the local quality of layout using a SGD layout algorithm based on positive and negative samples， and further enhanced the layout speed through multi-level algorithm. Finally， comparative experiments with existing layout models on 30 datasets of different scales demonstrate the effectiveness of the proposed model in terms of efficiency， layout quality and visualization.
Key words：large-scale graph layout; stress model; stochastic gradient descent; multi-level layout; graph visualization
0 引言
網(wǎng)絡或圖表達對象實體之間的關(guān)系，是一種常見的數(shù)據(jù)結(jié)構(gòu)類型，廣泛存在于多個領(lǐng)域并發(fā)揮著重要作用［1，2］，例如社會網(wǎng)絡、知識圖譜、生物化學網(wǎng)絡以及神經(jīng)網(wǎng)絡等。網(wǎng)絡（圖）可視化在信息可視化領(lǐng)域已經(jīng)成為分析和理解大型復雜網(wǎng)絡隱藏結(jié)構(gòu)的有效工具，其中最有效的是節(jié)點連接圖［3，4］，它將實體與關(guān)系分別建模為節(jié)點與節(jié)點間的連邊，是描述圖數(shù)據(jù)整體結(jié)構(gòu)和理解節(jié)點間關(guān)系的有效方法［2］。節(jié)點連接圖的繪制需要一種布局模型根據(jù)節(jié)點的連接關(guān)系計算所有節(jié)點合理有效的2維或3維坐標。理想情況下，圖布局算法可以快速執(zhí)行并產(chǎn)生符合圖布局領(lǐng)域美學標準的布局，例如應力誤差、鄰域相似度和最小角度等指標［5］。然而，隨著數(shù)據(jù)規(guī)模增加至數(shù)十萬，布局算法運行時間大幅增加［6］，部分算法難以在短時間內(nèi)獲得結(jié)果，若得到在視覺上、美學指標表現(xiàn)較差的布局結(jié)果，則無法實現(xiàn)有效可視化。因此，圖布局模型求解大規(guī)模圖的速度和產(chǎn)生優(yōu)秀布局結(jié)果的能力對圖可視化任務至關(guān)重要［1，4，7］。
本文主要將現(xiàn)有圖布局算法分為彈簧電荷模型［3，6，8，9］、應力模型［10，11］、維度下降類［2，12，13］以及深度學習［14］四類，詳細介紹可參考文獻［7］。應力模型將圖布局問題轉(zhuǎn)換為了一個優(yōu)化問題，認為布局節(jié)點之間的距離應該等于圖論距離，也被稱為理想距離（ideal length， IL）。該模型主要反映了節(jié)點間的整體連接關(guān)系，在保持全局結(jié)構(gòu)上效果更好［10］。由于應力模型需計算全對最短路徑長度（all-pairs shortest path，APSP），且傳統(tǒng)求解方法［15，16］時間與空間復雜度高，布局易陷入較差的局部最小化，無法滿足較大規(guī)模的圖布局任務。為了提高應力模型的求解速度與質(zhì)量，Khoury等人［17］提出了基于奇異值分解的low-rank方法實現(xiàn)近似計算APSP。Ortmann等人［18］借助PMDS只計算樞軸頂點和其他頂點之間的距離，減少了計算復雜度。雖然這些模型在一定程度上提升了速度，但受限于基礎(chǔ)求解方法，仍無法用于大規(guī)模圖布局。最近，Zheng 等人［10］提出了隨機梯度下降布局方法SGD2，與上述傳統(tǒng)方法相比，能更快收斂且不依賴初始布局，但其最小角度等局部布局優(yōu)化較差。Xue等人［19］提出的Taurus模型可以轉(zhuǎn)換應力模型為彈簧電荷模型，使用SGD［10］與BH綜合求解器計算布局，但布局速度仍然較慢。Ahmed等人［20］提出了SGD2布局算法，以線性組合的美學指標為目標函數(shù)，使布局結(jié)果滿足指定美學要求，但未優(yōu)化其布局速度?？傊F(xiàn)有應力模型求解方法能有效保持布局全局結(jié)構(gòu)，但更多關(guān)注遠距離節(jié)點對［3］，局部布局質(zhì)量優(yōu)化較差，布局時間較長。本文則結(jié)合了多層次布局［9］與SGD2［10］算法提升布局速度，并改進了目標函數(shù)實現(xiàn)局部質(zhì)量優(yōu)化。
多層次布局［9］是一種常用于彈簧電荷模型中提升布局速度與質(zhì)量的技術(shù)，其通過圖聚合算法在原圖基礎(chǔ)上生成一個粗粒度圖，再遞歸壓縮得到多個具有映射關(guān)系的粗粒度圖，布局時方向與壓縮階段相反，每次利用前一層次的布局結(jié)果進行初始化，逐層細化最終得到原圖布局結(jié)果。不同多層次布局方法的主要區(qū)別在于使用了不同的分層聚合和布局細化方法，例如FM3［21］使用了類似“太陽系統(tǒng)”的聚合方法，在細化過程中使用BH［22］近似計算頂點間的斥力。DRGraph［2］是一種強調(diào)鄰域的維度下降布局模型，使用了一種線性復雜度的分層算法保持全局結(jié)構(gòu)。最近Hong等人［23］提出基于Louvain的快速多層次算法，使用三種力引導算法細化布局。周銳等人［24］提出了一種強調(diào)網(wǎng)絡聚類的布局算法，使用基于個性化PageRank的社團劃分算法粗化網(wǎng)絡和基于IL的FR算法細化布局。若將多層次布局算法應用到應力模型，會出現(xiàn)“布局節(jié)點抖動”問題，其根本原因是應力模型需要使用IL作為優(yōu)化目標，而對圖分層會使不同層次中相同節(jié)點的IL不一致，優(yōu)化目標不一致導致了抖動現(xiàn)象發(fā)生，并且由于時間復雜度的關(guān)系，也無法簡單地通過計算大規(guī)模圖的APSP解決。本文則通過基于鄰居結(jié)構(gòu)的圖壓縮合并、新增節(jié)點最優(yōu)放置算法減弱抖動現(xiàn)象。
針對上述應力布局模型中“布局節(jié)點抖動”，布局求解時間較長，局部布局質(zhì)量優(yōu)化差的問題，本文提出了基于多層次隨機梯度下降的大規(guī)模圖布局算法（multi-level stochastic gradient descent algorithm for graph layout， MLSGD）。首先利用基于鄰居結(jié)構(gòu)的圖壓縮合并，將節(jié)點及其1階鄰居逐層聚合，防止相鄰層次圖結(jié)構(gòu)劇烈變化，在布局時減少節(jié)點抖動增加穩(wěn)定性。然后利用新增節(jié)點最優(yōu)放置算法，先根據(jù)相鄰層次圖直徑縮放布局坐標，減少節(jié)點IL差異來減少抖動，再為每個新增節(jié)點尋找多個已定位節(jié)點，計算節(jié)點最優(yōu)坐標，加快單層布局收斂速度。再利用融合了正負樣本的隨機梯度下降布局細化算法PN-SSGD，通過設計新目標函數(shù)強化MLSGD對布局的鄰域結(jié)構(gòu)的關(guān)注度，實現(xiàn)局部布局質(zhì)量的優(yōu)化。最后利用理想距離與權(quán)重修正算法補償布局細化過程中因近似梯度估計丟失的結(jié)構(gòu)信息，使MLSGD在提高布局速度優(yōu)化局部結(jié)構(gòu)的同時還能維持應力模型在全局結(jié)構(gòu)表達上的穩(wěn)定性。
綜上所述，本文主要貢獻如下：a）針對應力模型求解速度較慢的問題，提出了MLSGD圖布局算法，解決了“布局節(jié)點抖動”問題，提供了一種多層次應力布局模型的解決方案；b）針對應力模型局部布局質(zhì)量優(yōu)化較差問題，設計了新的目標函數(shù)，提出了PN-SSGD布局細化算法，通過增加正樣本節(jié)點鄰域范圍及其約束［10］比例，強化模型對局部結(jié)構(gòu)的關(guān)注度； c）設計了詳細的對比實驗評估本文算法在布局速度與質(zhì)量上的表現(xiàn)，驗證了本文算法的有效性。
1 MLSGD算法框架
MLSGD算法框架如圖1（a）所示，共分為三個階段。a）壓縮合并階段。使用線性時間復雜度的基于鄰居結(jié)構(gòu)的圖壓縮合并算法將圖聚合為規(guī)模依次減小的一系列粗粒度圖。b）初始布局階段。首先隨機初始化最頂層粗粒度圖Gn節(jié)點坐標，使用SGD2［10］或2.3節(jié)描述的PN-SSGD算法細化布局。c）節(jié)點插值及布局細化階段。對每一層圖包含兩個步驟： （a）新增節(jié)點坐標插值。首先根據(jù)相鄰兩層次圖直徑比例縮放上一層的布局結(jié)果，然后使用新增節(jié)點最優(yōu)放置算法初始化新增節(jié)點坐標，使其迅速到達最終節(jié)點位置附近。（b）布局細化。使用本文單層布局算法PN-SSGD細化布局，其利用采集的正負樣本節(jié)點中包含的結(jié)構(gòu)信息估計節(jié)點梯度并移動節(jié)點，通過增大正樣本約束［10］范圍與比例來增強模型對局部結(jié)構(gòu)的關(guān)注，提高局部布局質(zhì)量。算法1為MLSGD的詳細步驟。
算法1 MLSGD布局算法框架
輸入：節(jié)點集V={v1，v2，…，vN}；邊集E={e1，e2，…，eN}；劃分閾值TH。
輸出：節(jié)點二維布局坐標Pos={X1，X2，…，XN}，Xi=（xi，yi）。
a）對原始圖或新生成的圖層，將節(jié)點及其一階鄰居合并成新節(jié)點，并計算新邊權(quán)重，獲得一系列粗粒度圖Gs={G0，G1，…，Gn}，Gi=（Vi，Ei）；
b）隨機初始化Gn=（Vn，En）節(jié)點坐標，若|Vn|≤TH，使用SGD2細化布局，否則使用PN-SSGD算法；
c）對i=n-1到i=0逐層細化Gi布局，重復執(zhí)行步驟d）e）：
d）將上層布局Posi－1坐標縮放，賦值給Gi中對應的節(jié)點，對Gi新增節(jié)點t∈Vi－1－Vi利用最優(yōu)放置算法進行坐標插值；
e）使用本文PN-SSGD布局算法細化Gi=（Vi，Ei）布局；
f）算法達到收斂條件或最大迭代次數(shù)時返回Pos。
圖1（b）為數(shù)據(jù)集data在第三階段的布局實例。經(jīng)階段1得到了包含初始層的3層網(wǎng)絡，從上至下分別為G2、G1、G0，規(guī)模依次增大，第0層為data最終布局結(jié)果，從圖中可以看出粗化過程中，網(wǎng)絡結(jié)構(gòu)得到了很好的保留，避免了結(jié)構(gòu)突變。
2 MLSGD算法實現(xiàn)
2.1 基于鄰居結(jié)構(gòu)的圖壓縮合并算法
層次劃分算法是多層次布局算法的重要組成部分。為了減少圖數(shù)據(jù)層次劃分的時間并保持網(wǎng)絡結(jié)構(gòu)，本文改進了文獻［2］實現(xiàn)了一種具備權(quán)重的線性時間復雜度的快速層次劃分算法，避免了同類算法的高時間復雜度或網(wǎng)絡結(jié)構(gòu)變動范圍較大的缺點。圖2解釋了從圖G0生成下一層粗粒度的圖G1示例，詳細過程見算法2。
算法2 基于鄰居結(jié)構(gòu)的圖壓縮算法
輸入：圖G0=（V0，E0），TH=500，γ=0.7。
輸出：一系列粗粒度圖Gs={G0，G1，…，Gn}，Gi=（Vi，Ei）。
a）對于當前層Gi，若|Vi|gt;TH，則繼續(xù)執(zhí)行步驟b），否則結(jié)束。
b）節(jié)點合并階段。對于圖Gi，隨機選擇一個節(jié)點vi，m；將vi，m及其未被分配的1階鄰居合并到vi，m并在圖Gi+1中創(chuàng)建新節(jié)點si+1，m。
c）若vi，m和vi，n在Gi+1中被分配到同一節(jié)點si+1，x，則刪除圖Gi中的邊ei=（vi，m，vi，n）。重復步驟b），直到無法分配節(jié)點為止，再執(zhí)行步驟d）。
d）邊生成階段。遍歷Gi中未刪除的邊，查找端點在Gi+1中對應的聚合節(jié)點si+1，u，si+1，v。
e）若si+1，u≠si+1，v，按式（1）計算聚合節(jié)點間的權(quán)重W（si+1，u，si+1，v）。
f）若|Vi+1|≤γ|Vi|，則執(zhí)行步驟a），否則結(jié)束算法。
W（si+1，u，si+1，v）=min（u，v）∈Ei（d（si，u，u）+d（u，v）+d（v，si，v））（1）
其中：d表示兩節(jié)點在Gi中的最短路徑長度。粗化步驟減少了每個層級上的節(jié)點數(shù)量。然而，當Gi+1的大小非常接近Gi時，層次劃分算法的成本會顯著增加［21］。因此，除了步驟a）設置固定大小的劃分閾值之外，當相鄰層節(jié)點數(shù)滿足|Vi+1|gt;γ|Vi|時，表示在當前壓縮合并規(guī)則下，數(shù)據(jù)規(guī)模不能有效縮減，此時停止劃分。為平衡劃分速度與質(zhì)量，本文將γ設置為0.7。
2.2 新增節(jié)點最優(yōu)放置算法
本算法應用于節(jié)點坐標插值階段中圖Gi+1到Gi的新增節(jié)點坐標初始化過程，即圖2的逆向過程。常見的同類方法有重心放置、圓環(huán)放置和隨機放置［23］，它們沒有考慮節(jié)點之間的理想距離，不適用于本模型。文獻［25］提出了一種初始節(jié)點放置算法，對Gi中的新增節(jié)點，在Gi+1中查找距離最近的3個節(jié)點，利用式（2）計算坐標，該算法存在三個問題：a）多個新增節(jié)點若屬于同一組節(jié)點的鄰居，最終初始化為相同坐標；b）不考慮相對位置得到的3個節(jié)點可能使初始位置不準確；c）沒有考慮相鄰層次間相同節(jié)點對最短路徑長度差異。為了使新增節(jié)點迅速到達最終節(jié)點位置附近，減小節(jié)點抖動加速布局收斂，本文同時考慮鄰居結(jié)構(gòu)和歐氏距離改進文獻［25］所提節(jié)點初始化算法，算法描述如下：
算法3 新增節(jié)點最優(yōu)放置算法
輸入：上一層次圖Gi+1節(jié)點坐標Posi+1={X1，X2，…，X|Vi+1|}，m=5。
輸出：當前層次圖Gi節(jié)點的初始坐標Posi={X1，X2，…，X|Vi|}。
a） 計算圖Gi+1、Gi的直徑φi+1、φi。 /*使用相鄰圖直徑縮放下層坐標*/
b） 計算Posi+1（φi/φi+1），作為Gi對應節(jié)點的初始坐標。" /*減少差異*/
c） 對Gi中的新增節(jié)點t，在Gi中查找d（t，i）最小的m個已定位節(jié)點。
d） 按照如下規(guī)則選擇3個節(jié)點D={u，v，w}；節(jié)點u與t直接相連；節(jié)點v距離u最遠；節(jié)點w距離直線uv最遠。
e） D中節(jié)點求解如式（2）得到6個錨點，然后選擇出距離最近的3個錨點得到t的坐標。
f） 重復步驟c）～e），所有新增節(jié)點坐標初始化完成時，算法結(jié)束。
（xt－xi）2+（yt－yi）2=d（t，i）2（xt－xj）2+（yt－yj）2=d（t， j）2 {i， j}∈D2（2）
其中：d同式（1）；x與y為坐標，詳細推導參見文獻［25］。
2.3 基于節(jié)點正負樣本的隨機梯度下降布局算法PN-SSGD
為了進一步提升算法的速度與局部布局質(zhì)量，本文改進了文獻［18］提出的稀疏應力求解模型，設計了新的目標函數(shù)，將其用于多層次布局中細化階段。類似于文獻［18］，本文將應力模型目標函數(shù)拆分為鄰域與非鄰域兩部分，如式（3）（4）所示。
C=∑i∈V ∑j∈N（r）（1+λ|P|N（r））wijQij+∑i∈V ∑p∈P＼N（r）w′ipQip（3）
Qij=（‖Xi－Xj‖－dij）2（4）
其中：C的第一部分表示節(jié)點的正樣本（r階鄰居）構(gòu)成的約束項，因子λ用于控制正樣本相對于負樣本的比例，通過（r， λ）調(diào)節(jié)模型對局部結(jié)構(gòu)的關(guān)注度。C的第二部分為節(jié)點與負樣本之間P構(gòu)成的約束項，P通過式（5）生成累計概率分布采集得到，也稱為樞軸點集合，此部分約束項用與保持布局的全局結(jié)構(gòu)。N（r）為某節(jié)點的r階鄰居節(jié)點集合，wij，w′ip表示兩種節(jié)點間權(quán)重，dij為節(jié)點間圖論距離，d′ip為普通節(jié)點i與樞軸節(jié)點p理想距離，d′ip與w′ip計算方式將在2.5與2.6節(jié)介紹。C的核心是利用單個節(jié)點與正負樣本節(jié)點的梯度值近似估計其與所有節(jié)點的梯度值，再根據(jù)該值更新節(jié)點坐標。
單個節(jié)點的正樣本定義為節(jié)點的r階鄰居，r通常取1或2，本文研究發(fā)現(xiàn)，正樣本相對于負樣本的數(shù)量比例以及r的取值對節(jié)點的局部結(jié)構(gòu)布局質(zhì)量有較強的相關(guān)性，可以有效提高邊長變化度和最小角度等質(zhì)量指標。
對于所有節(jié)點的負樣本P節(jié)點集合，本文算法使用基于最短路徑長度與度數(shù)的累計概率分布采樣得到，計算少量均勻分布在圖空間且度數(shù)較大的采樣節(jié)點P到其余所有節(jié)點的最短路徑長度，可以避免計算APSP，考慮節(jié)點度數(shù)的原因是在移動非相鄰節(jié)點對時，負樣本節(jié)點坐標保持不變，有助于減少大度數(shù)節(jié)點移動次數(shù)穩(wěn)定布局結(jié)構(gòu)。每個節(jié)點的采樣權(quán)重計算方法為式（5），其中α與β控制采樣依據(jù)比例，默認情況下α=0.8，β=0.2，然后對節(jié)點權(quán)重計算累計概率分布進行采樣，P為已采集的節(jié)點集合，d同上，deg（v）為節(jié)點度數(shù)，默認|P|=200。
w（v）=minu∈P d（u，v）·α+deg（v）·β（5）
目標函數(shù)確定后，本文采用類似于文獻［10］的隨機梯度下降求解方法，該方法在每輪迭代中每次隨機選擇一對頂點vi、vj構(gòu)成的約束wijQij按式（6）（7）進行梯度下降計算，然后如圖3所示沿著相反的梯度方向大小為式（8）更新節(jié)點坐標。引入隨機性后，損失能夠較快地降低至較小水平，能夠有效地避免陷入較差地局部最小化。與標準SGD不同的是，式（9）中的η更新步長系數(shù)可取較大的值使節(jié)點快速移動，設置方法與文獻［10］一致。
?（wijQij）?Xk=4wijr
k=i－4wijrk=j0others（6）
r=‖Xi－Xj‖－dij2Xi－Xj‖Xi－Xj‖（7）
XiXj=XiXj+ΔXiΔXj=XiXj－μr－r（8）
μ=min{η×4wij，1}，ηmax=1wmin，ηmin=0.1wmax（9）
2.4 布局收斂條件
為不同規(guī)模類型圖數(shù)據(jù)設計出統(tǒng)一的收斂條件是非常困難的［25］，為了平衡布局算法收斂速度與布局質(zhì)量，考慮到多層次布局的特點，本文根據(jù)文獻［10］與實驗經(jīng)驗為每一層設計出式（10）的收斂規(guī)則。在每次迭代中檢測節(jié)點移動量Δdisp，δ=0.03×max{［|V|/5×104］，30}，li為第i層圖，i第i層圖平均邊權(quán)重，每層最大迭代次數(shù)為20（li/ltotal）。
max‖Δdisp‖lt;δ×li×i（10）
2.5 設置理想距離IL
上述算法雖然減少了計算量，但是也丟失了部分的結(jié)構(gòu)信息。為了補償近似梯度估計丟失的結(jié)構(gòu)信息，本文改進文獻［18］的處理方法。由于每個節(jié)點總能找到一個距離其最近的樞軸點p∈P，所有具有相同最近p節(jié)點的v∈V被劃分到同一區(qū)域R（p），從而將每個樞軸節(jié)點p關(guān)聯(lián)為一組節(jié)點R（p）V，它們滿足∪p∈PR（p）=V，R（p1）∩R（p2）=。因此，節(jié)點i與R（p）中節(jié)點之間的約束就可以近似替換為節(jié)點i與樞軸p之間的約束，文獻［18］直接使用dip作為ip的IL，但隨著dip增大，節(jié)點i與區(qū)域R（p）的應力誤差會變得越來越顯著。本文則是利用i到R（p）的平均圖論距離作為新的IL。但由于本文算法無法得到任意節(jié)點i到R（p）中所有節(jié)點的圖論距離，所以采用了一種近似的方法求得平均值：首先找到節(jié)點i所屬節(jié)點pi，然后計算pi到區(qū)域R（pj）所有節(jié)點的平均最短路徑長度d（pi，R（pj）），再按照式（11）計算得出最終的近似IL。
d′ipj=d（pi，R（pj））dpip×dipj（11）
2.6 移動權(quán)重修正
按式（3）進行布局梯度計算時，由于普通節(jié)點v與樞軸點p普遍距離較遠，當pN（v，1），需保持p靜止維持布局穩(wěn)定，再通過調(diào)整v的移動尺度補償因p不移動產(chǎn)生的距離誤差。文獻［18］使用參數(shù)s設置節(jié)點v與p之間的移動權(quán)重，取值如式（12）所示，當節(jié)點距離p節(jié)點較遠時，s可能取到非常大的值（|V|/|P|），使節(jié)點移動幅度過大，破壞布局穩(wěn)定性。
s=|{j∈R（p）：dpj≤dpi2}|（12）
為了穩(wěn)定在多層次布局中節(jié)點穩(wěn)定性，防止在較低層次時布局逐漸收斂時發(fā)生大的布局波動，本文改進s參數(shù)計算方法為式（13），理論上其最大值處于|P|左右，參數(shù)含義同上。最后，按照式（14）設置式（3）中普通節(jié)點與樞軸節(jié)點之間的權(quán)重。
s′=d′ipjΦ（R（pj））（13）
w′ipx=s′×d′ip-2x（14）
2.7 算法復雜度分析
本節(jié)將從時間與空間復雜度兩個方面分析算法運行性質(zhì)。a）時間復雜度。本文算法主要耗時由以下幾個部分組成：壓縮合并階段逐層縮減圖數(shù)據(jù)規(guī)模O（|V|+|E|）、初始布局階段布局初始化O（|Vn|2）或為O（P|Vn|+|En|）、各層節(jié)點坐標初始化插值O（|V|）與布局細化階段O（P|V|+|E|），其中|Vn|為頂層圖節(jié)點數(shù)目，通常較小，可以視為常數(shù)時間，L表示層次數(shù)量，P為樞軸點Pivots數(shù)量，T為迭代次數(shù)：
CcomputationMLSGD=O（|V|+|E|+|Vn|2+LPT|V|）（15）
b）空間復雜度分析。本文算法對內(nèi)存的需求由以下幾個部分構(gòu)成：存儲經(jīng)過壓縮合并階段后產(chǎn)生的N個層次圖O（|V|+|E|）、記錄節(jié)點間的最短路徑長度矩陣O（P（|V|－1））、存儲細化階段需要使用約束項O（P|V|+|E|）以及保存所有節(jié)點的坐標位置O（|V|）：
CmemoryMLSGD=O（|V|+|E|+P|V|+（P+ω）|V|+|E|+|V|）（16）
3 實驗與結(jié)果分析
3.1 實驗設計
為了驗證本文算法的有效性，與幾個經(jīng)典的和最近的布局方法在一組圖數(shù)據(jù)上進行實驗，從布局時間與布局質(zhì)量上評估了MLSGD算法，所有代碼運行于Intel? CoreTM i5-12400F CPU 32 GB的單核Ubuntu-24 GB虛擬機中。
3.1.1 數(shù)據(jù)集
為了實現(xiàn)客觀綜合評價，本文收集了如表1所示常用于同類型文獻［2，3，10，13］的30個具有不同節(jié)點和邊數(shù)的圖數(shù)據(jù)，主要選取自Florida Collection［26］、SNAP network Collection［27］以及文獻［2，3］使用的數(shù)據(jù)。該組數(shù)據(jù)涵蓋樹圖、網(wǎng)格圖、地鐵、引文和社交網(wǎng)絡等真實世界的圖數(shù)據(jù)，這些圖的節(jié)點數(shù)從77到1 957 027，邊數(shù)從254到5 885 829。
3.1.2 對比方法
本文選擇了五種圖布局領(lǐng)域較新的和經(jīng)典算法，它們分別是屬于力模型（force-based）的t-FDP-BH［3］和基于頂點隨機采樣的RVS［6］模型，屬于應力模型（stress-based）的SSGD［10］、最大熵應力布局模型Maxent［28］和GRIP［25］算法。t-FDP-BH和RVS算法使用文獻［3］提供的BH與RVS版本代碼，SSGD、Maxent和GRIP算法的源代碼分別來自文獻［10］、Networkit［29］和Tulip［30］。本文算法參數(shù)（r，λ）設置為（1，0），（1，0.3）和（2，0.6）時，分別用MLSGD、MLSGD-N1和MLSGD-N2標識。所有算法都在［-10，10］隨機初始化，參數(shù)設置為各自文獻推薦值，所有實驗重復5次以消除隨機性的影響。
3.1.3 評估指標
本文從兩個方面評估算法：a）算法執(zhí)行效率，對比該算法與其他算法的時間消耗；b）算法有效性，使用應力誤差［28］、鄰域相似度［13］、邊交叉度（crosslessness， CL）［5］、邊長變化度（edge length variation， ELV）［31］和最小角度（minimum angle， MA）［5］五個評估指標和視覺效果綜合評估各算法的布局質(zhì)量。
3.2 算法效率對比
圖4比較了上述算法在所有數(shù)據(jù)集上的對數(shù)運行時間。所有算法只測量布局時CPU占用時間，不包括數(shù)據(jù)加載等處理步驟。圖中數(shù)據(jù)缺省項表示由于巨大的內(nèi)存消耗或計算時間成本導致相應算法無法在有效時間內(nèi)（lt;7 200 s）獲得結(jié)果。
圖4表示運行時間與圖節(jié)點數(shù)的關(guān)系，實線為節(jié)點數(shù)與時間之間的擬合曲線，其中本文三個不同參數(shù)的算法時間消耗非常接近，為減少重疊，只展示了MLSGD的擬合曲線。從圖4可以看出大部分布局模型可以在有效時間內(nèi)處理所有數(shù)據(jù)集，布局對數(shù)時間同節(jié)點數(shù)目大致為線性增大關(guān)系。從整體上看，除了個別小規(guī)模數(shù)據(jù)集，本文算法MLSGD具有最快的布局速度，由此可見，本文采用多層次布局思想和新增節(jié)點最優(yōu)放置算法能夠有效使節(jié)點迅速到達最終位置附近，再結(jié)合隨機梯度下降使布局迅速收斂，有效減少了布局時間。使用拉普拉斯變換和BH斥力計算的Maxent與使用頂點隨機采樣的線性FR-RVS算法具有相似的執(zhí)行效率，但整體上仍然慢于本文算法。GRIP多層次布局算法與SSGD算法在具有少量節(jié)點的情況下優(yōu)于本文算法，這是因為在數(shù)據(jù)規(guī)模較小時，層次劃分與最短路徑長度計算所需時間占總體時間比例較大，但隨著數(shù)據(jù)規(guī)模增大，如圖4中子圖所示，多層次與節(jié)點采樣結(jié)合的隨機梯度下降布局算法優(yōu)勢逐漸明顯，計算效率最高可提升至8倍。使用的BH版本t-FDP與RVS類似，固定布局迭代次數(shù)，其O（n log n）的時間復雜度導致了其布局最慢。
3.3 布局質(zhì)量對比
3.3.1 應力誤差（normalized stress error， SE）
SE用于評估一個布局結(jié)果的全局結(jié)構(gòu)保持度，其測量圖形布局與理論理想距離的擬合程度。SE定義如下：
SE=2|V|（|V|－1）∑ilt;j（‖Xi－Xj‖－SPD（i， j）2）SPD（i， j）2（17）
其中：dij是節(jié)點vi 和vj 之間的最短路徑距離，s是均勻縮放布局的縮放因子，用于不同規(guī)模圖數(shù)據(jù)公平比較。
表2為不同算法在30個圖數(shù)據(jù)集的SE指標測試結(jié)果，加粗值對應的算法在該數(shù)據(jù)集上全局結(jié)構(gòu)保持最優(yōu)。從表2可以看出，本文算法在大多數(shù)數(shù)據(jù)集中優(yōu)于基準算法SSGD，在其他數(shù)據(jù)集中也與該算法相當，這是因為本文算法采用了多層次的布局思想，從多個層次采集了結(jié)構(gòu)信息用于布局，可以很好地避免陷入局部極小值造成的全局結(jié)構(gòu)損失，同時理想距離與權(quán)重修正也有助于算法獲取更精確的全局結(jié)構(gòu)信息。除此之外，SSGD并未提供完全收斂的布局算法，其限制了迭代次數(shù)，而本文算法則是設計了一個平衡算法速度與布局質(zhì)量的收斂條件，最終得到了比SSGD更低的SE值。Maxent會使節(jié)點均勻的分布的空間中，這會以犧牲SE值為代價來換取其他布局質(zhì)量指標的提升。雖然GRIP屬于stress-based算法，但是它在最后一層的布局細化過程中使用了force-based算法，導致其全局結(jié)構(gòu)保持變差。t-FDP-BH與更傾向于關(guān)注鄰域結(jié)構(gòu)，布局初始化狀態(tài)對其有較大的影響，隨機初始化則加重了這一結(jié)果，故SE值普遍較高。FR-RVS除了初始布局狀態(tài)原因外，在每輪迭代計算時隨機選擇部分節(jié)點進行斥力計算，引入了更多的不確定性，全局結(jié)構(gòu)也保持較差。
3.3.2 鄰域相似度（neighborhood preservation degree， NP）
NP定義為圖空間與布局空間之間的Jaccard相似系數(shù)，測量節(jié)點的鄰域在布局空間中的保留程度。
NP=1|V|∑i|Ng（gi，r）∩Nl（li，r）||Ng（gi，r）∪Nl（li，r）|（18）
其中：Ng（gi，r）表示節(jié)點i在圖空間中的r階近鄰；Nl（li，r）表示節(jié)點i在布局空間中的r個最近的鄰居。與文獻［2］一致，本文也用k=2（NP2）來評估鄰域保存的相似性。
圖5比較了所有算法布局結(jié)果的NP2值，橫軸為數(shù)據(jù)集編號，從左至右節(jié)點數(shù)依次增大，NP2越大表示鄰域保持結(jié)果越好。從圖5可以看出MLSGD在將一半的數(shù)據(jù)集中鄰域保持效果最好，在大部分數(shù)據(jù)集中都接近最優(yōu)值，少量數(shù)據(jù)集中弱于t-FDP-BH和Maxent算法。原因是布局細化過程中，PN-SSGD能夠有效利用正樣本提供的鄰域信息來保持鄰域結(jié)構(gòu)。與SSGD算法相比，本文算法通過多層次的正負節(jié)點采樣的方法捕獲了更多樣的局部結(jié)構(gòu)，同時SSGD存在更多關(guān)注較遠節(jié)點［3］問題，這也是NP2優(yōu)于SSGD的原因。MLSGD-N1、N2在NP2指標的實驗結(jié)果表明調(diào)整應力模型關(guān)注鄰域與全局結(jié)構(gòu)信息的數(shù)量與比例并不能有效解決文獻［3］提出的應力模型在NP2指標保持較差的問題。它們在NP2指標上相較于MLSGD有所下降，在分析了其他布局指標結(jié)果（3.3.3節(jié)）后，本文發(fā)現(xiàn)這兩種算法是以損耗一部分NP2質(zhì)量的形式優(yōu)化了其他的局部結(jié)構(gòu)，這也是文獻［20］所提到的難以同時優(yōu)化的結(jié)構(gòu)案例。對t-FDP-BH隨機初始化節(jié)點坐標，即使擁有關(guān)注鄰域的特殊力形式，其NP2仍然表現(xiàn)較差。圖中紅色實線表明RVS很難保持較好的鄰域結(jié)構(gòu)。
3.3.3 局部布局質(zhì)量
在本節(jié)中，將計算其他算法與本文算法在CL［5］、ELV［31］和MA［5］指標上的相對值式（19）。CL表示邊相交的程度，ELV是有效衡量布局質(zhì)量的美學標準之一，MA計算每個節(jié)點實際最小角與理想最小角之間的平均偏差，以上每個指標本文都計算其歸一化值，相對值大于0時（紅色豎線）則表示Xs代表的算法在該指標上越優(yōu)秀。對于CL及ELV，經(jīng)過歸一化計算后值即便非常接近，也有較大視覺差異。
從圖6（a）可以看出，本文MLSGD與SSGD在CL指標上效果基本持平，邊交叉數(shù)量較少，與其余四種算法對比中，超過3/4的數(shù)據(jù)本文算法都表現(xiàn)更好。圖6（b）比較了本文MLSGD-N1，可以看出Maxent在ELV指標中表現(xiàn)最好且略優(yōu)于本文算法，布局結(jié)果邊長長度較為統(tǒng)一，布局美觀，而本文算法比包含SSGD在內(nèi)的算法表現(xiàn)更好，說明增加1階鄰域信息在迭代過程中的比例能夠有效改善局部結(jié)構(gòu)。從圖6（c）可看出，Maxent在MA指標中將近一半的數(shù)據(jù)集上優(yōu)于本文MLSGD-N2，節(jié)點最小入射邊角度更大，布局更加美觀，而本文算法在增大鄰域范圍后（r=2）也有效改進了原算法SSGD在MA上的布局結(jié)果，說明在布局過程中增加鄰域范圍及其約束比例能夠有效改進局部布局結(jié)構(gòu)。圖6（d）（e）分別顯示了本文算法設置不同參數(shù)（1，0.3）和（2，0.6）后與設置默認參數(shù)（1，0）的MLSGD在ELV和MA指標中的相對誤差值，結(jié)果表明，擴大正樣本鄰域范圍與約束比例能夠有效改善局部布局質(zhì)量。
3.4 可視化效果展示
圖7展示六種算法的布局效果。其中force-based類型算法t-FDP-BH和FR-RVS算法可視化效果較差，一方面原因是節(jié)點數(shù)目的增多，算法也越來越難以解開圖結(jié)構(gòu)，布局結(jié)果較雜亂，另一方面，此類模型依賴初始布局的缺點也變得明顯。luxembourg是現(xiàn)實道路網(wǎng)絡拓撲數(shù)據(jù)，與MLSGD布局效果相比，可見兩個算法均沒能維持全局結(jié)構(gòu)。本文MLSGD與SSGD可以產(chǎn)生類似的布局結(jié)果，節(jié)點分布均勻，能夠清晰觀察到局部連接結(jié)構(gòu)，全局結(jié)構(gòu)也保持得更好，保持了較好的對稱性。Maxent在sierpinski3d得到了另一種結(jié)構(gòu)的布局結(jié)構(gòu)，這與其盡量使節(jié)點均勻分布的特性相符合，在finan512數(shù)據(jù)集上則產(chǎn)生了較多的邊交叉，局部結(jié)構(gòu)維持較差，其他三個圖則產(chǎn)生了與本文類似的布局結(jié)構(gòu)。
4 結(jié)束語
本文提出了一個新的面向大規(guī)模圖的布局算法，提供了一種多層次應力布局模型的解決方案，用以實現(xiàn)大規(guī)模圖的快速布局計算，維持布局全局結(jié)構(gòu)的同時提高局部結(jié)構(gòu)質(zhì)量。該算法有基于啟發(fā)式隨機梯度下降的多層次布局算法和基于節(jié)點正負樣本的隨機梯度下降單層布局算法兩個主要的創(chuàng)新點。MLSGD通過多層次布局與啟發(fā)式隨機梯度下降提高布局速度并維持全局結(jié)構(gòu)，還可調(diào)整節(jié)點正樣本捕獲的鄰域結(jié)構(gòu)，增加正樣本約束比例，使布局模型關(guān)注更多的鄰域信息，從而改善算法的局部布局質(zhì)量。實驗結(jié)果表明，本文算法有效提高了布局算法完成大規(guī)模圖布局任務的計算速度，并生成了與SSGD視覺上類似的布局結(jié)果，同時優(yōu)化了最小角度等局部布局效果。除此之外，與其他經(jīng)典和最新的算法相比，在布局速度、全局結(jié)構(gòu)保持和局部鄰域保持等其他局部質(zhì)量指標上都有不同程度的領(lǐng)先。盡管本文算法在大規(guī)模圖布局問題中具有高效性和可靠性，但未來也存在一些進一步優(yōu)化的工作，首先現(xiàn)有布局收斂規(guī)則是依據(jù)實驗經(jīng)驗設定的，未來將根據(jù)不同類型圖數(shù)據(jù)的特征設計自適應布局收斂規(guī)則。除此之外，還會考慮基于GPU并行計算進一步提升本文算法的計算速度。
參考文獻：
［1］Alkadi M， Serrano V， Scott-Brown J， et al. Understanding barriers to network exploration with visualization： a report from the trenches ［J］. IEEE Trans on Visualization and Computer Graphics， 2022， 29（1）： 907-917.
［2］Zhu Minfeng， Chen Wei， Hu Yuanzhe， et al. DRGraph： an efficient graph layout algorithm for large-scale graphs by dimensionality reduction ［J］. IEEE Trans on Visualization and Computer Graphics， 2020， 27（2）： 1666-1676.
［3］Zhong Fahai， Xue Mingliang， Zhang Jian， et al. Force-directed graph layouts revisited： a new force based on the t-distribution ［J］. IEEE Trans on Visualization and Computer Graphics， 2023，30（7）：3650-3663.
［4］楊卓， 謝雅淇， 陳誼，等. 圖可視化布局方法最新研究進展綜述 ［J］. 計算機工程與應用， 2023， 59（16）： 1-15. （Yang Zhuo， Xie Yaqi， Chen Yi， et al. A review of the latest research progress of graph visualization layout methods ［J］. Computer Engineering and Applications， 2023， 59（16）： 1-15.）
［5］Purchase H C. Metrics for graph drawing aesthetics ［J］. Journal of Visual Languages amp; Computing， 2002， 13（5）： 501-516.
［6］Gove R. A random sampling O（n） force-calculation algorithm for graph layouts ［J］. Computer Graphics Forum， 2019， 38（3）： 739-751.
［7］Zhang Shuhang， Xu Ruihong， Quan Yining. Large graph layout optimization based on vision and computational efficiency： a survey ［J］. Visual Intelligence， 2023， 1（1）： 14.
［8］Fruchterman T M J， Reingold E M. Graph drawing by force-directed placement ［J］. Software： Practice and Experience， 1991， 21（11）： 1129-1164.
［9］Walshaw C. A multilevel algorithm for force-directed graph drawing ［C］//Proc of the 8th International Symposium on Graph Drawing. Berlin： Springer， 2001： 171-182.
［10］Zheng J X， Pawar S， Goodman D F M. Graph drawing by stochastic gradient descent ［J］. IEEE Trans on Visualization and Computer Graphics， 2018， 25（9）： 2738-2748.
［11］薛明亮. 圖可視化節(jié)點布局與邊捆綁優(yōu)化問題研究 ［D］. 濟南：山東大學， 2023. （Xue Mingliang. Research on graph visualization node layout and edge binding optimization ［D］. Jinan：Shandong University， 2023.）
［12］Rahman M K， Sujon M H， Azad A. Scalable force-directed graph representation learning and visualization ［J］. Knowledge and Information Systems， 2022， 64（1）： 207-233.
［13］Kruiger J F， Rauber P E， Martins R M， et al. Graph layouts by t-SNE ［J］. Computer Graphics Forum， 2017， 36（3）： 283-294.
［14］劉小芝. 基于圖神經(jīng)網(wǎng)絡的圖布局評估與生成研究 ［D］. 杭州：杭州電子科技大學， 2023. （Liu Xiaozhi. Research on graph layout evaluation and generation based on graph neural network ［D］. Hangzhou： Hangzhou Dianzi University， 2023.）
［15］Kamada T， Kawai S. An algorithm for drawing general undirected graphs ［J］. Information Processing Letters， 1989， 31（1）： 7-15.
［16］Gansner E R， Koren Y， North S. Graph drawing by stress majorization ［C］//Proc of the 12th International Symposium on Graph Drawing. Berlin： Springer， 2005： 239-250.
［17］Khoury M， Hu Yifan， Krishnan S， et al. Drawing large graphs by low-rank stress majorization ［J］. Computer Graphics Forum， 2012，31（3pt1）： 975-984.
［18］Ortmann M， Klimenta M， Brandes U. A sparse stress model ［C］// Proc of International Symposium on Graph Drawing and Network Visua-lization. Cham： Springer International Publishing， 2016： 18-32.
［19］Xue Mingliang，Wang Zhi，Zhong Fahai， et al. Taurus： towards a unified force representation and universal solver for graph layout ［J］. IEEE Trans on Visualization and Computer Graphics， 2022， 29（1）： 886-895.
［20］Ahmed R， De Luca F， Devkota S， et al. Multicriteria scalable graph drawing via stochastic gradient descent， （SGD）2 （SGD）2 ［J］. IEEE Trans on Visualization and Computer Graphics， 2022， 28（6）： 2388-2399.
［21］Hachul S， Jünger M. Drawing large graphs with a potential-field-based multilevel algorithm ［C］//Proc of International Symposium on Graph Drawing. Berlin： Springer， 2004： 285-295.
［22］Barnes J， Hut P. A hierarchical O（N log N） force-calculation algorithm ［J］. Nature， 1986， 324（6096）： 446-449.
［23］Hong S H， Eades P， Torkel M， et al. Louvain-based multi-level graph drawing ［C］// Proc of the 14th IEEE Pacific Visualization Symposium. Piscataway，NJ：IEEE Press， 2021： 151-155.
［24］周銳， 王桂娟， 鄧皓天，等. 復雜網(wǎng)絡聚類特征層次布局算法 ［J］. 計算機應用研究， 2022， 39（2）： 479-484. （Zhou Rui， Wang Guijuan， Deng Haotian， et al. Hierarchy clustering characte-ristics of complex network layout algorithm ［J］. Application Research of Computers， 2022， 39（2）： 479-484.）
［25］Gajer P， Kobourov S G. GRIP： graph drawing with intelligent placement ［J］. Journal of Graph Algorithms and Applications， 2004， 6（3）： 203-224.
［26］Davis T A， Hu Yifan. The University of Florida sparse matrix collection ［J］. ACM Trans on Mathematical Software， 2011， 38（1）： 1-25.
［27］Leskovec J， Krevl A. SNAP datasets： Stanford large network dataset collection ［DB/OL］. （2014）. https：//snap.stanford.edu/data/.
［28］Gansner E R， Hu Yifan， North S. A maxent-stress model for graph layout ［J］. IEEE Trans on Visualization and Computer Gra-phics， 2012， 19（6）： 927-940.
［29］Staudt C L， Sazonovs A， Meyerhenke H. NetworKit： a tool suite for large-scale complex network analysis ［J］. Network Science， 2016， 4（4）： 508-530.
［30］Auber D， Archambault D， Bourqui R， et al. TULIP 5 ［EB/OL］. （2017）. https：//tulip.labri.fr/site/.
［31］Kieffer S， Dwyer T， Marriott K， et al. Hola： human-like orthogonal network layout ［J］. IEEE Trans on Visualization and Computer Graphics， 2015， 22（1）： 349-358.
［32］Miller J， Huroyan V， Kobourov S. Spherical graph drawing by multi-dimensional scaling ［C］//Proc of International Symposium on Graph Drawing and Network Visualization. Cham： Springer International Publishing， 2022： 77-92.
