樊 成, 王布宏, 田繼偉

(空軍工程大學信息與導航學院, 陜西 西安 710077)

0 引 言

隨著經濟社會的不斷發(fā)展,航空網絡作為航空運輸的載體愈加重要,然而受天氣及人為因素的影響,航空網絡容易發(fā)生航班推遲、取消甚至使網絡整體癱瘓的問題。研究表明,在網絡中存在少部分關鍵節(jié)點,當這類節(jié)點被移除時,網絡的拓撲結構和穩(wěn)定性方面會受到較大影響。例如在生物群體的傳染病網絡中,及時控制一個或幾個傳染源能夠保護整個群體。在電力網絡中,對重要傳輸節(jié)點的保護能夠防止電網的災難性中斷。在航空網絡中,少數重要機場的故障會引起大面積的航班延誤,因此準確識別航空網絡的關鍵機場節(jié)點,具有重大的理論研究意義和應用價值。

航空網絡本質上是由機場節(jié)點和航線組成的圖數據,可以抽象為復雜網絡,并通過圖結構來建模描述并加以分析。這樣航空網絡的關鍵節(jié)點識別問題就轉為了復雜網絡的關鍵節(jié)點識別問題?，F有的復雜網絡關鍵節(jié)點識別方法,一類是利用復雜網絡中心性指標對關鍵節(jié)點進行識別:Lordan等利用度中心性和介數中心性對節(jié)點重要性進行排序,并依此序對網絡中節(jié)點進行移除,觀察網絡的功能性變化,以此來衡量關鍵節(jié)點識別情況是否準確;閆玲玲等利用度和聚類系數對關鍵節(jié)點進行排序;Pradhan等從節(jié)點鄰居節(jié)點的重要性角度入手,提出了基于特征向量中心性的排序方法;Salavati等利用了節(jié)點的局部特征,通過改進的接近中心性指標對網絡中具有影響力的節(jié)點進行識別,該方法計算復雜度低,適用于大規(guī)模網絡;此后為了克服單一中心性指標在描述節(jié)點重要性時的局限性,Tang等利用Dempster-Shafer(D-S)證據理論對不同的中心性指標進行融合,形成了綜合性的評價指標。事實上,復雜網絡的中心性指標是從網絡拓撲結構的角度出發(fā)描述節(jié)點在網絡中的重要性,然而節(jié)點的結構重要性并不能完全反映該節(jié)點在網絡中的功能重要性。因此單純利用復雜網絡的中心性指標對網絡中關鍵節(jié)點進行識別,就可能導致識別結果與現實情況存在偏差。另一類是利用機器學習對網絡中的節(jié)點進行分類,進而找出關鍵節(jié)點的方法:基于決策樹的分類算法、基于支持向量機分類算法和基于粒子群的識別算法。這類方法已被應用于某些領域的關鍵節(jié)點尋找,如Twitter網絡中的影響力節(jié)點識別和社交網絡關鍵節(jié)點識別等,并取得了一定成效。然而基于機器學習的節(jié)點分類算法,需要將大量的工作都放于數據的處理和轉換上,通過獲得更好的特征來提升算法的識別效果,導致這類算法的性能嚴重依賴于特征工程,并且該類算法只能處理歐幾里得結構數據,無法用于圖數據這類非歐幾里得數據的處理,而航空網絡恰恰是典型的圖數據。這就導致了利用基于機器學習的方法對航空網絡節(jié)點進行分類時,在分類的準確率方面存在一定不足?？偟膩碚f,現有的節(jié)點分類識別算法,在計算過程中往往將節(jié)點的特征信息及結構信息孤立開來,單純使用節(jié)點的特征信息,而忽略了節(jié)點之間的連接關系這類結構信息。這就導致了在處理航空網絡這類圖結構數據時,其節(jié)點分類的準確率并不理想。

圖神經網絡(graph neural network,GNN)的出現解決了這一問題,它將卷積應用于圖結構數據中,通過對節(jié)點及其鄰居節(jié)點特征向量的聚合操作來不斷提取節(jié)點信息,能夠同時利用節(jié)點的特征信息和結構信息。這些特性使得GNN成為了目前的研究熱點,并廣泛應用于交通流量預測、文本分類、節(jié)點識別等領域,均取得了較好的成效。本文利用GNN在處理圖結構數據方面的優(yōu)勢及強大的表示學習能力,將GNN應用于航空網絡的節(jié)點分類中。在這方面,前人已經做了不少工作:Kipf等設計了圖卷積網絡(graph convolution network, GCN);Velickovic等提出了圖注意力網絡(graph attention network, GAT),通過引入注意力機制,對網絡節(jié)點和邊賦予不同的權重,優(yōu)化了GCN的結構;Wang等提出了一種非局部通道注意力機制(non-local channel attention machine mechanism, NL-CAM),用于解決復雜數據的高維信息提取問題;Hamilton等提出了GraphSAGE (graph sample and aggregate)模型,通過采樣鄰居的策略改進了GCN的訓練方式,使其可應用于大規(guī)模的圖數據中;Zhao等提出了infGCN模型,選取4類復雜網絡的中心性指標來構建特征矩陣,同時采用預訓練及遷移學習的方法,用來解決訓練數據及特征集合較少的問題;Li等從數據擴充的角度出發(fā),通過自訓練和協(xié)同訓練兩種策略來擴展訓練數據集,進而提升模型的訓練效果;Chen等則在模型訓練過程中通過動態(tài)優(yōu)化輸入圖數據的拓撲結構及調整網絡中各節(jié)點的感受域,來解決圖神經網絡的過平滑問題。

以上基于GNN的節(jié)點識別模型,大部分還是聚焦于設計新的模型架構來提升模型性能,對于高級訓練方法的探索仍然較少,并且其對航空網絡數據的節(jié)點分類效果還有待檢驗。為了解決利用復雜網絡中心性指標的識別方法和基于機器學習的方法在航空網絡節(jié)點識別中的不足,同時改進GNN模型的訓練方法及對航空網絡數據的節(jié)點識別效能,本文提出了一種結合多任務學習(multi-task learning, MTL)和自適應加權策略的多任務GCN(multi-task GCN, MTGCN)模型。該模型將航空網絡的鄰接矩陣作為特征矩陣,采用兩層的GCN結構進行特征聚合,利用softmax函數進行結果分類,再使用交叉熵損失計算分類結果與標簽矩陣的損失值。此外,考慮到同一類型的節(jié)點特征相似這一特性,而不同類型的節(jié)點在特征相差較大,引入節(jié)點對分類作為模型輔助任務,計算不同節(jié)點對之間的相關性,并將此作為模型額外的監(jiān)督信息,與交叉熵損失值一起構成模型的損失值,再使用Adam優(yōu)化器對模型進行迭代優(yōu)化。通過在3個實際的航空網絡數據集的對比實驗,結果表明本文所提模型在識別準確率與運算復雜度方面均取得了優(yōu)勢,具備一定的應用價值。

本文的主要工作及創(chuàng)新點如下:

(1) 提出了一種利用GNN來處理航空網絡節(jié)點分類問題的方法,該方法利用了GNN在處理圖結構數據方面的優(yōu)勢及強大的學習能力,同時克服了傳統(tǒng)的基于復雜網絡中心性指標的節(jié)點排序方法及基于機器學習的節(jié)點識別方法的不足。

(2) 提出了改進GNN節(jié)點分類任務性能的思路。在模型中引入MTL的訓練方法,將“節(jié)點-節(jié)點相關性”作為額外監(jiān)督信息加入到模型訓練過程中,增加了模型對于不同類型節(jié)點的區(qū)分度,形成了最終訓練框架MTGCN。

(3) 為了保持MTL中各任務權重的合理性,引入了自適應動態(tài)加權策略(adaptive dynamic weighting strategy, ADWS),該策略根據模型的訓練情況自適應地調整各任務的權重,避免了人為賦權的主觀性,提升了模型的訓練效果。

(4) 為了衡量MTGCN模型的有效性及運算效率,本文在3個基準航空網絡數據集中對幾種常見的GNN模型進行了對比實驗,結果表明了本文所提方法的優(yōu)勢。

1 MTGCN節(jié)點識別模型

1.1 問題形式化描述

利用復雜網絡理論構建實際航空網絡圖={,},其中=(∪)為機場節(jié)點構成的點集合,包含個有標簽節(jié)點和個不帶標簽節(jié)點,=+為網絡總結點數;={,,…,}為機場節(jié)點之間航線邊組成的邊集合,為網絡的總邊數;=[]∈×為網絡的鄰接矩陣,表示節(jié)點和之間的連接關系;∈×表示網絡的特征矩陣,其每一行向量∈就表示節(jié)點的維特征向量,為每一節(jié)點的特征個數;∈×為one-hot編碼后的標簽矩陣,其每一行向量∈為節(jié)點的維標簽向量,用來表示節(jié)點所屬的類別,為節(jié)點的總類別數。本文目標是構建一個分類模型,經過訓練后能夠對輸入無標簽節(jié)點所屬類別進行預測。

1.2 模型整體框架

MTGCN模型的主要框架如圖1所示,主要包括模型輸入、圖卷積、多任務學習、自適應加權等部分,下面分別進行介紹。

圖1 MTGCN模型結構圖Fig.1 Structure of MTGCN model

(1) 模型輸入

圖1左側為模型的輸入部分,將航空網絡圖結構數據作為輸入,網絡中節(jié)點分為兩類:一類是有標簽節(jié)點,用深色表示,其上數字表示該節(jié)點所屬類別,數值越高其在網絡中的重要程度越高;另一類是無標簽節(jié)點,其上不帶有數字表示,需要對其重要程度進行預測。根據網絡圖結構數據可得網絡鄰接矩陣和特征矩陣,將此輸入模型的GCN卷積部分。

(2) 節(jié)點的表示學習

模型圖卷積部分使用兩層的GCN結構對輸入數據的特征進行提取,中間使用ReLU激活函數。其中GCN層的矩陣形式為

(1)

此時模型的表示學習過程就可表示為

(2)

(3)

式中：=;為中間層輸出,=∈×為第二層GCN輸出,也是節(jié)點表示學習的結果。

(3) 目標任務:節(jié)點分類

將得到的節(jié)點表示,利用softmax函數進行處理,得到每一節(jié)點的對于不同類別概率分布:

(4)

(5)

(4) 輔助任務:節(jié)點對分類

MTL的概念由Caruana提出,Vandenhende等則將MTL用于深度學習中。區(qū)別于傳統(tǒng)的單任務學習(single task learning, STL),MTL改變了原來的單一模型對應單一任務的模式,利用跨任務的有用信息來提高模型的泛化能力,進而提升模型的學習性能。

在以往節(jié)點的分類過程中,節(jié)點對之間的相關性往往沒有被考慮到。事實上,屬于同一類型的節(jié)點其標簽分布更接近,不同類型的節(jié)點其標簽差異較大。因此，本文將節(jié)點對之間的相關性引入到模型訓練過程中,將節(jié)點對的分類作為輔助任務,通過計算不同的節(jié)點對之間的相關性并將此作為模型的損失函數之一,使同一類型節(jié)點對在模型輸出結果中分布更接近,不同類型節(jié)點對相距更遠,令模型訓練效果與數據標簽相一致,對標簽分布帶來了強制的成對約束,提升了模型的學習性能。

(6)

(5) ADWS

在MTL中,模型的目標函數是各任務損失函數的總和,因此對不同任務設定正確的權重就顯得尤為重要。本文采用ADWS,根據模型的訓練情況自適應地調整各任務的權重,避免了人為賦權的主觀性,提升了模型的訓練效果。

下面對ADWS進行說明:假設模型共有個任務,各任務在訓練集和驗證集數據中對應的損失值分別為和,那么第(=1,2,…,)個任務對應的權重系數就為

(7)

(8)

式中:(-1)表示在上一輪迭代過程中驗證集損失和訓練集損失之間的比例;表示當前的迭代輪數。由式(8)可知,當任務在訓練過程中出現過擬合時,就有驗證集損失大于訓練集損失,即>,此時(-1)<0;當任務在訓練過程中未出現過擬合時,訓練集損失值與驗證集損失相近,即≈,此時(-1)≈0,結果是>,過擬合任務的權重會減小,模型在訓練過程中更多的集中于未出現過擬合的任務。此外,為了保證模型在初始時刻訓練中的平順性,設定當=1,2時,()=1。這樣采用了ADWS后,就可以保證在多任務訓練的過程中合理分配各任務權重,同時避免因出現過擬合的任務對模型訓練帶來影響。整個模型的損失函數可以表示為

=+

(9)

式中:和對應任務的權重,根據ADWS進行設定。隨后,使用Adam優(yōu)化器對模型進行優(yōu)化。至此,MTGCN模型構建完畢。整個訓練過程可用算法1來描述。

算法1 基于MTGCN的節(jié)點分類算法輸入 圖結構數據G(V,E),GCN卷積層數l+1,最大迭代次數q,特征矩陣X,標簽矩陣YL輸出 無標簽節(jié)點的標簽矩陣YU1. H(0)=X2. for epoch=1,2,…,q do:3. for i=0,1,…,l:4. 輸入H(i)計算該GCN層的輸出H(i+1)5. end6. 利用式(8)計算目標任務的損失值ln7. 利用式(9)計算輔助任務的損失值lp8. 使用ADWS動態(tài)調整各任務的權重9. 此時模型損失函數L=λnln+λplp10. 使用Adam優(yōu)化器進行迭代優(yōu)化,使L最小11. end12. Yprob=softmax(H(l+1)),根據每行概率最大值得到該節(jié)點所屬類別,繼而得到YU13. ReturnYU

2 實驗準備

2.1 實驗數據集

所選數據來自2019年國際數據挖掘與知識發(fā)現大會,具備一定的權威性。該數據集包括3個國家和地區(qū)的航空網絡,分別是巴西、歐洲和美國,其中每個節(jié)點對應一個機場,邊表示機場之間存在商業(yè)航班,每一數據集根據機場的航班和人流量將節(jié)點劃分為4類,用于表示機場節(jié)點的重要程度。3個航空網絡的規(guī)模及拓撲結構并不相同,具體結構如表1所示。

表1 用于節(jié)點分類的數據集

(1) 巴西航空網絡:數據源自巴西國家民用航空局,統(tǒng)計時間為2016年1月至2016年12月。該網絡包括131個節(jié)點,1 038條邊(網絡直徑為4)。節(jié)點重要性的衡量標準是統(tǒng)計時間內該機場起飛和著陸的飛機總數。

(2) 歐洲航空網絡。數據源自歐盟統(tǒng)計局,統(tǒng)計時間為2016年1月至2016年11月。該網絡包括399個節(jié)點,5 995條邊(網絡直徑為5)。節(jié)點重要性的衡量標準是統(tǒng)計時間內起飛和著陸的飛機總數。

(3) 美國航空網絡。數據源自美國交通部交通統(tǒng)計局,統(tǒng)計時間為2016年1月至2016年10月。該網絡包括1 190個節(jié)點,13 599條邊(網絡直徑為8)。節(jié)點重要性的衡量標準是統(tǒng)計時間內到達和離開該機場的總人數。

2.2 用于比較的其他算法

本文選取了3種常用圖卷積模型進行比較,分別為GCN、GAT、GraphSAGE和DEMO-Net。下面對其原理進行簡要介紹。

(1) GCN:

(10)

(2) GAT:

(11)

式中:為自注意力分數,表示節(jié)點對節(jié)點的重要度。與GCN相比,GAT引入了注意力機制,多了一個自適應的邊權重系數,它通過對中心節(jié)點相連邊的信息采集,為該節(jié)點的鄰居節(jié)點分配不同的權重,提升了模型的學習能力。

(3) GraphSAGE:

(12)

(13)

式中：Agg表示聚合算子;()表示節(jié)點的鄰接節(jié)點。GraphSAGE從兩個方面對GCN做了改動:一方面是通過采樣鄰居的策略將GCN從全圖的訓練方式改造成以節(jié)點為中心的小批量訓練方式;另一方面是該算法對聚合鄰居的操作進行了拓展,提出了替換GCN中卷積新的方式。

(4)DEMO-Net:

(14)

(15)

(16)

2.3 評價指標

本文分別選擇準確率、微觀F1(Micro F1)和宏觀F1(Macro F1)作為不同模型對節(jié)點分類任務效能的評價指標。下面對這些指標的計算方法進行介紹。首先對于多分類問題,其任一類別的實驗結果可以分為4類,如表2所示。

表2 樣本分類結果

根據表2的結果,可得該類別下的模型的精確率(Precision)、召回率(Recall):

(17)

(18)

那么模型的準確率(Accuracy)為

(19)

F1分數定義為精確率和召回率的調和平均數,通常用于權衡Precision和Recall,對于多分類問題常用Micro-F1和Macro-F1。Micro-F1定義為

(20)

(21)

(22)

而Macro-F1為每一類F1值的算術平均,其計算方式為

(23)

2.4 實驗設置

本文實驗采用Pytorch深度學習框架,使用Python語言編程實現,操作系統(tǒng)為Windows 10(64位),內存為16 GB,處理器為Intel(R) Core(TM) i7-6500U2,59 GHz。在模型設置方面,MTGCN模型使用了兩層卷積層,隱藏層的單元分別為64和16,最大迭代次數為2 000,使用Adam優(yōu)化器,模型的學習率設置為0.001,損失函數為交叉熵損失函數,激活函數為ReLU。為了防止模型在訓練中出現過平滑情況,本文將dropout值設置為05。同時為了進行比較實驗,用于對比模型的設置與所出自論文中一致。

3 仿真分析

3.1 準確率分析

首先對各模型的訓練情況進行分析。圖2繪制了各模型在不同數據集中的訓練曲線,迭代次數為2 000次。通過觀察圖2中損失值及準確率隨著迭代次數的變化,可以看出:MTGCN在3個數據集的訓練過程中損失值下降最快,說明模型的加速收斂能力強,并且能夠取得最高的準確率。

圖2 模型在不同數據集中的訓練曲線Fig.2 Training curves of different models in different datasets

隨后對不同模型在3種數據集中的準確率進行對比,其中訓練集、驗證集和測試集按照7∶2∶1的比例劃分,每種方法獨立運行10次,對所得的結果取平均,得到不同模型在3個航空網絡數據集的識別準確率,結果如表3所示。

表3 不同模型對航空網絡關鍵節(jié)點分類的表現結果

通過表3可以看出,在不同的評價指標下,本文所提MTGCN模型均優(yōu)于其他模型。與GCN模型相比,在歐洲數據集中,準確率提升更高,達到了6.3%,可以看出MTGCN模型相對于GCN有了一定提升,說明了MTL機制對于傳統(tǒng)GCN模型的提升效果。

為了更直觀表示各模型的識別性能,此處繪制了各模型在巴西航空網絡數據集下的受試者工作特性曲線(receiver operating characteristic, ROC)及查準率-查全率(precision-recall, PR)曲線,結果如圖3所示。圖3(a)中的TPR、FPR分別表示真正例率和假正例率，其計算方法為

(24)

(25)

圖3 巴西數據集下各模型的ROC及PR曲線Fig.3 ROC and PR curves of different models in Brazil datasets

從圖3可以看出,MTGCN模型在航空網絡節(jié)點分類任務中聚有良好的穩(wěn)定性及敏感度,圖3(a)中各曲線下的面積表示模型的識別準確率,MTGCN最高,達到了81.7%;圖3(b)中MTGCN曲線位于其他模型曲線上方,也說明了該模型的優(yōu)勢。

3.2 添加輔助任務對模型的影響

為觀察ADWS在模型訓練過程中對各任務權重賦值情況,對不同迭代次數下的權重值進行了記錄,結果如表4所示。從表中可以看出,節(jié)點分類任務的權重相較于節(jié)點對分類任務上升較快,說明模型一開始更關注節(jié)點分類任務,隨后節(jié)點對分類任務的權重逐漸增加,從而為模型的訓練提供更多的監(jiān)督信息。隨著訓練的進行,不同任務的權重逐漸趨于穩(wěn)定,同一任務的權重隨著迭代次數的增加其變化量也逐漸減小,說明了ADWS能夠在訓練過程中使各任務的權重穩(wěn)定收斂,同時與對應的數據集及學習任務相匹配。

表4 各任務權重在ADWS下隨訓練過程的變化表

為進一步觀察引入的輔助任務效果,此處設計了消融實驗,即分別在引入輔助任務(with auxiliary task,with AT)和不引入輔助任務(without auxiliary task, without AT)兩種情況下,觀察MTGCN模型對3種機場數據中節(jié)點分類的準確性,結果如表5所示。

表5 輔助任務對航空網絡節(jié)點分類任務準確性影響

通過表5可以看出,在引入了輔助任務后,能夠帶來1%～2%的識別準確率的提升,這是因為輔助任務從節(jié)點對的角度,對模型的識別過程增加了新的監(jiān)督信息,提升了識別的準確性。因此，在MTL的情況下,能夠為模型帶來更好的性能增益。

3.3 不同的數據集劃分的影響

此處觀察各類模型在不同的數據劃分情況下的識別準確率表現。將訓練集、測試集比例從10%增加到90%,每隔10%進行一次記錄。每個記錄點依然采取獨立10次實驗,并將結果的平均值作為該占比下的識別準確率,得到的結果如圖4所示。

圖4 不同訓練集比例下對于航空網絡節(jié)點分類準確性Fig.4 Node classification accuracy for airline networks using different train datasets ratios

從圖4可以看出,在所有數據集上,所提出的MTGCN在所有不同訓練集大小下都優(yōu)于其他方法,在訓練集占比只有10%的條件時,即只有少量節(jié)點參與訓練的條件下,模型的表現優(yōu)于其他模型,并且這種優(yōu)勢隨著訓練集數目增加而增加,這也說明了本文所提的MTGCN模型更容易捕捉學習過程中的信息。

3.4 模型的復雜度分析

對MTGCN的運算復雜度進行理論分析:如果不增加輔助任務,那么模型的復雜度與GCN模型相同。因此,首先對有層的GCN模型復雜度進行分析,假設其每一層隱藏單元的維數都相同,用表示,為迭代次數,||為網絡的邊數,那么它的運算復雜度就為(||),與網絡的邊數||成線性關系。隨后對MTL輔助任務的運算復雜度進行分析,假設共有對節(jié)點對,那么輔助任務的運算復雜度就為(||),從而MTGCN模型的復雜度就為(||)+(||)。又因為帶標簽節(jié)點是有限的,所以||通常遠小于||,因此MTGCN模型的運算復雜度為(||),即該模型的運算時間主要取決于GCN,輔助任務的引入對運算復雜度帶來的影響較小。

下面對各模型在不同數據集上的運算時間進行實驗比較。每一數據集下分別進行10次實驗,每次迭代次數為2 000次,記錄各模型的運算時間,所得結果取平均值,得到各模型的運算時間如圖5所示。

圖5 模型在不同航空網絡數據集下運算效率Fig.5 Operational efficiency of the models under different airline networks datasets

通過圖5可以看出:與基本的常見GNN模型進行比較,本文提出的MTGCN模型并未顯著增加運行時間,結果與理論分析一致,說明添加輔助任務并未明顯增加模型的運算時間。DEMO-Net模型因在分類過程中首先要依據節(jié)點度值對圖數據進行重構,因此運算復雜度較高。

4 結 論

本文針對航空網絡的關鍵節(jié)點識別問題,提出了一種基于MTL的圖卷積模型MTGCN,通過將節(jié)點對分類作為輔助任務加入模型的訓練過程中,為模型引入了額外的監(jiān)督信息,同時采用自適應加權的方式對不同任務自適應地賦予權重,提升了模型的學習性能。通過在3種實際航空網絡的仿真實驗,結果表明,本文所提模型在識別準確率及運算效率方面優(yōu)于主流的GNN。

下一步的工作,一是將模型應用于更多的航空網絡數據中,提升模型的泛化能力,二是考慮引入遷移學習,減少模型的訓練時間。