樊 成, 王布宏, 田繼偉

(空軍工程大學(xué)信息與導(dǎo)航學(xué)院, 陜西 西安 710077)

0 引 言

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

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

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

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

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

(1) 提出了一種利用GNN來處理航空網(wǎng)絡(luò)節(jié)點(diǎn)分類問題的方法,該方法利用了GNN在處理圖結(jié)構(gòu)數(shù)據(jù)方面的優(yōu)勢(shì)及強(qiáng)大的學(xué)習(xí)能力,同時(shí)克服了傳統(tǒng)的基于復(fù)雜網(wǎng)絡(luò)中心性指標(biāo)的節(jié)點(diǎn)排序方法及基于機(jī)器學(xué)習(xí)的節(jié)點(diǎn)識(shí)別方法的不足。

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

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

(4) 為了衡量MTGCN模型的有效性及運(yùn)算效率,本文在3個(gè)基準(zhǔn)航空網(wǎng)絡(luò)數(shù)據(jù)集中對(duì)幾種常見的GNN模型進(jìn)行了對(duì)比實(shí)驗(yàn),結(jié)果表明了本文所提方法的優(yōu)勢(shì)。

1 MTGCN節(jié)點(diǎn)識(shí)別模型

1.1 問題形式化描述

利用復(fù)雜網(wǎng)絡(luò)理論構(gòu)建實(shí)際航空網(wǎng)絡(luò)圖={,},其中=(∪)為機(jī)場(chǎng)節(jié)點(diǎn)構(gòu)成的點(diǎn)集合,包含個(gè)有標(biāo)簽節(jié)點(diǎn)和個(gè)不帶標(biāo)簽節(jié)點(diǎn),=+為網(wǎng)絡(luò)總結(jié)點(diǎn)數(shù);={,,…,}為機(jī)場(chǎng)節(jié)點(diǎn)之間航線邊組成的邊集合,為網(wǎng)絡(luò)的總邊數(shù);=[]∈×為網(wǎng)絡(luò)的鄰接矩陣,表示節(jié)點(diǎn)和之間的連接關(guān)系;∈×表示網(wǎng)絡(luò)的特征矩陣,其每一行向量∈就表示節(jié)點(diǎn)的維特征向量,為每一節(jié)點(diǎn)的特征個(gè)數(shù);∈×為one-hot編碼后的標(biāo)簽矩陣,其每一行向量∈為節(jié)點(diǎn)的維標(biāo)簽向量,用來表示節(jié)點(diǎn)所屬的類別,為節(jié)點(diǎn)的總類別數(shù)。本文目標(biāo)是構(gòu)建一個(gè)分類模型,經(jīng)過訓(xùn)練后能夠?qū)斎霟o標(biāo)簽節(jié)點(diǎn)所屬類別進(jìn)行預(yù)測(cè)。

1.2 模型整體框架

MTGCN模型的主要框架如圖1所示,主要包括模型輸入、圖卷積、多任務(wù)學(xué)習(xí)、自適應(yīng)加權(quán)等部分,下面分別進(jìn)行介紹。

圖1 MTGCN模型結(jié)構(gòu)圖Fig.1 Structure of MTGCN model

(1) 模型輸入

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

(2) 節(jié)點(diǎn)的表示學(xué)習(xí)

模型圖卷積部分使用兩層的GCN結(jié)構(gòu)對(duì)輸入數(shù)據(jù)的特征進(jìn)行提取,中間使用ReLU激活函數(shù)。其中GCN層的矩陣形式為

(1)

此時(shí)模型的表示學(xué)習(xí)過程就可表示為

(2)

(3)

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

(3) 目標(biāo)任務(wù):節(jié)點(diǎn)分類

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

(4)

(5)

(4) 輔助任務(wù):節(jié)點(diǎn)對(duì)分類

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

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

(6)

(5) ADWS

在MTL中,模型的目標(biāo)函數(shù)是各任務(wù)損失函數(shù)的總和,因此對(duì)不同任務(wù)設(shè)定正確的權(quán)重就顯得尤為重要。本文采用ADWS,根據(jù)模型的訓(xùn)練情況自適應(yīng)地調(diào)整各任務(wù)的權(quán)重,避免了人為賦權(quán)的主觀性,提升了模型的訓(xùn)練效果。

下面對(duì)ADWS進(jìn)行說明:假設(shè)模型共有個(gè)任務(wù),各任務(wù)在訓(xùn)練集和驗(yàn)證集數(shù)據(jù)中對(duì)應(yīng)的損失值分別為和,那么第(=1,2,…,)個(gè)任務(wù)對(duì)應(yīng)的權(quán)重系數(shù)就為

(7)

(8)

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

=+

(9)

式中:和對(duì)應(yīng)任務(wù)的權(quán)重,根據(jù)ADWS進(jìn)行設(shè)定。隨后,使用Adam優(yōu)化器對(duì)模型進(jìn)行優(yōu)化。至此,MTGCN模型構(gòu)建完畢。整個(gè)訓(xùn)練過程可用算法1來描述。

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

2 實(shí)驗(yàn)準(zhǔn)備

2.1 實(shí)驗(yàn)數(shù)據(jù)集

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

表1 用于節(jié)點(diǎn)分類的數(shù)據(jù)集

(1) 巴西航空網(wǎng)絡(luò):數(shù)據(jù)源自巴西國家民用航空局,統(tǒng)計(jì)時(shí)間為2016年1月至2016年12月。該網(wǎng)絡(luò)包括131個(gè)節(jié)點(diǎn),1 038條邊(網(wǎng)絡(luò)直徑為4)。節(jié)點(diǎn)重要性的衡量標(biāo)準(zhǔn)是統(tǒng)計(jì)時(shí)間內(nèi)該機(jī)場(chǎng)起飛和著陸的飛機(jī)總數(shù)。

(2) 歐洲航空網(wǎng)絡(luò)。數(shù)據(jù)源自歐盟統(tǒng)計(jì)局,統(tǒng)計(jì)時(shí)間為2016年1月至2016年11月。該網(wǎng)絡(luò)包括399個(gè)節(jié)點(diǎn),5 995條邊(網(wǎng)絡(luò)直徑為5)。節(jié)點(diǎn)重要性的衡量標(biāo)準(zhǔn)是統(tǒng)計(jì)時(shí)間內(nèi)起飛和著陸的飛機(jī)總數(shù)。

(3) 美國航空網(wǎng)絡(luò)。數(shù)據(jù)源自美國交通部交通統(tǒng)計(jì)局,統(tǒng)計(jì)時(shí)間為2016年1月至2016年10月。該網(wǎng)絡(luò)包括1 190個(gè)節(jié)點(diǎn),13 599條邊(網(wǎng)絡(luò)直徑為8)。節(jié)點(diǎn)重要性的衡量標(biāo)準(zhǔn)是統(tǒng)計(jì)時(shí)間內(nèi)到達(dá)和離開該機(jī)場(chǎng)的總?cè)藬?shù)。

2.2 用于比較的其他算法

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

(1) GCN:

(10)

(2) GAT:

(11)

式中:為自注意力分?jǐn)?shù),表示節(jié)點(diǎn)對(duì)節(jié)點(diǎn)的重要度。與GCN相比,GAT引入了注意力機(jī)制,多了一個(gè)自適應(yīng)的邊權(quán)重系數(shù),它通過對(duì)中心節(jié)點(diǎn)相連邊的信息采集,為該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)分配不同的權(quán)重,提升了模型的學(xué)習(xí)能力。

(3) GraphSAGE:

(12)

(13)

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

(4)DEMO-Net:

(14)

(15)

(16)

2.3 評(píng)價(jià)指標(biāo)

本文分別選擇準(zhǔn)確率、微觀F1(Micro F1)和宏觀F1(Macro F1)作為不同模型對(duì)節(jié)點(diǎn)分類任務(wù)效能的評(píng)價(jià)指標(biāo)。下面對(duì)這些指標(biāo)的計(jì)算方法進(jìn)行介紹。首先對(duì)于多分類問題,其任一類別的實(shí)驗(yàn)結(jié)果可以分為4類,如表2所示。

表2 樣本分類結(jié)果

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

(17)

(18)

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

(19)

F1分?jǐn)?shù)定義為精確率和召回率的調(diào)和平均數(shù),通常用于權(quán)衡Precision和Recall,對(duì)于多分類問題常用Micro-F1和Macro-F1。Micro-F1定義為

(20)

(21)

(22)

而Macro-F1為每一類F1值的算術(shù)平均,其計(jì)算方式為

(23)

2.4 實(shí)驗(yàn)設(shè)置

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

3 仿真分析

3.1 準(zhǔn)確率分析

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

圖2 模型在不同數(shù)據(jù)集中的訓(xùn)練曲線Fig.2 Training curves of different models in different datasets

隨后對(duì)不同模型在3種數(shù)據(jù)集中的準(zhǔn)確率進(jìn)行對(duì)比,其中訓(xùn)練集、驗(yàn)證集和測(cè)試集按照7∶2∶1的比例劃分,每種方法獨(dú)立運(yùn)行10次,對(duì)所得的結(jié)果取平均,得到不同模型在3個(gè)航空網(wǎng)絡(luò)數(shù)據(jù)集的識(shí)別準(zhǔn)確率,結(jié)果如表3所示。

表3 不同模型對(duì)航空網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)分類的表現(xiàn)結(jié)果

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

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

(24)

(25)

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

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

3.2 添加輔助任務(wù)對(duì)模型的影響

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

表4 各任務(wù)權(quán)重在ADWS下隨訓(xùn)練過程的變化表

為進(jìn)一步觀察引入的輔助任務(wù)效果,此處設(shè)計(jì)了消融實(shí)驗(yàn),即分別在引入輔助任務(wù)(with auxiliary task,with AT)和不引入輔助任務(wù)(without auxiliary task, without AT)兩種情況下,觀察MTGCN模型對(duì)3種機(jī)場(chǎng)數(shù)據(jù)中節(jié)點(diǎn)分類的準(zhǔn)確性,結(jié)果如表5所示。

表5 輔助任務(wù)對(duì)航空網(wǎng)絡(luò)節(jié)點(diǎn)分類任務(wù)準(zhǔn)確性影響

通過表5可以看出,在引入了輔助任務(wù)后,能夠帶來1%～2%的識(shí)別準(zhǔn)確率的提升,這是因?yàn)檩o助任務(wù)從節(jié)點(diǎn)對(duì)的角度,對(duì)模型的識(shí)別過程增加了新的監(jiān)督信息,提升了識(shí)別的準(zhǔn)確性。因此，在MTL的情況下,能夠?yàn)槟Ｐ蛶砀玫男阅茉鲆妗?/p>

3.3 不同的數(shù)據(jù)集劃分的影響

此處觀察各類模型在不同的數(shù)據(jù)劃分情況下的識(shí)別準(zhǔn)確率表現(xiàn)。將訓(xùn)練集、測(cè)試集比例從10%增加到90%,每隔10%進(jìn)行一次記錄。每個(gè)記錄點(diǎn)依然采取獨(dú)立10次實(shí)驗(yàn),并將結(jié)果的平均值作為該占比下的識(shí)別準(zhǔn)確率,得到的結(jié)果如圖4所示。

圖4 不同訓(xùn)練集比例下對(duì)于航空網(wǎng)絡(luò)節(jié)點(diǎn)分類準(zhǔn)確性Fig.4 Node classification accuracy for airline networks using different train datasets ratios

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

3.4 模型的復(fù)雜度分析

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

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

圖5 模型在不同航空網(wǎng)絡(luò)數(shù)據(jù)集下運(yùn)算效率Fig.5 Operational efficiency of the models under different airline networks datasets

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

4 結(jié) 論

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

下一步的工作,一是將模型應(yīng)用于更多的航空網(wǎng)絡(luò)數(shù)據(jù)中,提升模型的泛化能力,二是考慮引入遷移學(xué)習(xí),減少模型的訓(xùn)練時(shí)間。