摘 要：鄰域的組成對于基于空間域的圖卷積網(wǎng)絡(luò)(GCN)模型有至關(guān)重要的作用。針對模型中節(jié)點鄰域排序未考慮結(jié)構(gòu)影響力的問題，提出了一種新的鄰域選擇策略，從而得到改進(jìn)的GCN模型。首先，為每個節(jié)點收集結(jié)構(gòu)重要的鄰域并進(jìn)行層級選擇得到核心鄰域;然后，將節(jié)點及其核心鄰域的特征組成有序的矩陣形式;最后，送入深度卷積神經(jīng)網(wǎng)絡(luò)(CNN)進(jìn)行半監(jiān)督學(xué)習(xí)。節(jié)點分類任務(wù)的實驗結(jié)果表明，該模型在Cora、Citeseer和Pubmed引文網(wǎng)絡(luò)數(shù)據(jù)集中的節(jié)點分類準(zhǔn)確性均優(yōu)于基于經(jīng)典圖嵌入的節(jié)點分類模型以及四種先進(jìn)的GCN模型。作為一種基于空間域的GCN，該模型能有效運用于大規(guī)模網(wǎng)絡(luò)的學(xué)習(xí)任務(wù)。

　　關(guān)鍵詞：圖卷積網(wǎng)絡(luò);鄰域選擇策略;圖嵌入;節(jié)點分類;半監(jiān)督學(xué)習(xí)

　　0 引言

　　圖或網(wǎng)絡(luò)廣泛存在于日常生活中，是抽象現(xiàn)實世界中對象與對象之間關(guān)系的一種重要數(shù)據(jù)結(jié)構(gòu)。如作者之間的引用關(guān)系、個人之間的社交關(guān)系、城市之間的物流和交通關(guān)系、蛋白質(zhì)之間的交互關(guān)系等數(shù)據(jù)都可以通過圖或網(wǎng)絡(luò)抽象地表達(dá)。對這類數(shù)據(jù)的分析和建模能夠挖掘豐富的潛在信息，可廣泛應(yīng)用于節(jié)點分類、社區(qū)發(fā)現(xiàn)、鏈接預(yù)測、推薦系統(tǒng)等任務(wù)。

　　傳統(tǒng)的網(wǎng)絡(luò)表示(如鄰接矩陣)存在結(jié)構(gòu)稀疏和維度過高的問題，難以有效地學(xué)習(xí)。而手動抽取網(wǎng)絡(luò)的結(jié)構(gòu)特征(如共同鄰居數(shù))需要豐富的領(lǐng)域知識，根據(jù)網(wǎng)絡(luò)特點人工選擇有效的特征，因此不具有普適性。直覺上來看，在網(wǎng)絡(luò)中拓?fù)浣Y(jié)構(gòu)相似的節(jié)點也應(yīng)該具有相近的向量表示[1]。因此，研究者開始學(xué)習(xí)圖或網(wǎng)絡(luò)的內(nèi)在表示形式，自動融合網(wǎng)絡(luò)的結(jié)構(gòu)特征和節(jié)點的內(nèi)在特征。之后，這些學(xué)得的特征能夠更好地用于各類學(xué)習(xí)任務(wù)。由于網(wǎng)絡(luò)表示學(xué)習(xí)研究具有重要的學(xué)術(shù)價值和應(yīng)用背景，近年來吸引了大量研究者的關(guān)注，出現(xiàn)了諸如DeepWalk[2]、node2vec[3]、大規(guī)模信息網(wǎng)絡(luò)嵌入(Large-scale Information Network Embedding， LINE) [4]等一系列經(jīng)典而有效的算法。

　　最近，研究者嘗試將卷積神經(jīng)網(wǎng)絡(luò)(Convolutional Neural Network， CNN)用于圖數(shù)據(jù)的處理，進(jìn)行了圖卷積網(wǎng)絡(luò)(Graph Convolutional Network， GCN)機器學(xué)習(xí)范式的研究，并已取得階段性的成果。CNN具有自動抽取高階語義和自動編碼降維的優(yōu)勢，在圖像分類[5]、目標(biāo)檢測[6]等圖像處理任務(wù)中表現(xiàn)突出。圖像數(shù)據(jù)具有規(guī)則的柵格結(jié)構(gòu)(圖1(a))，CNN通過固定的卷積核掃描整幅圖像，獲得卷積核覆蓋范圍內(nèi)的局部信息，通過訓(xùn)練獲得卷積核參數(shù)，實現(xiàn)特征的自動抽取。然而，圖數(shù)據(jù)一般不具備規(guī)則的空間結(jié)構(gòu)，每個節(jié)點的連接數(shù)量不盡相同(圖1(b))，因此CNN的平移不變性在圖上不再適用，需要為待編碼節(jié)點選擇固定數(shù)量且有序的近鄰節(jié)點，以滿足傳統(tǒng)卷積的輸入要求。

　　已有的GCN方法大致可以分為兩類：第一類是基于譜域的卷積，也是GCN的理論基礎(chǔ)。經(jīng)典的工作如：Bruna等[7]通過傅里葉變換將圖拉普拉斯矩陣進(jìn)行特征分解，之后再進(jìn)行圖卷積，但該方法的復(fù)雜度較高;Defferrard等[8]使用切比雪夫多項式逼近譜圖濾波器，降低了算法復(fù)雜度;Kipf等[9]提出譜圖濾波器的一階線形逼近，進(jìn)一步簡化了計算。基于譜域的卷積方法受譜圖理論限制，因此難以有效擴(kuò)展至大規(guī)模網(wǎng)絡(luò)中。第二類是基于空間域的卷積，與基于譜域的卷積相比具有較好的擴(kuò)展性。經(jīng)典的方法如：Niepert等[10]提出的方法PATCHY-SAN(Patch Select-Assemble-Normalize)，在預(yù)處理時對所有節(jié)點的重要程度和相似程度進(jìn)行編號，但編號固定導(dǎo)致后續(xù)難以通過堆疊卷積層獲取更多的信息;Velickovic等[11]提出圖關(guān)注網(wǎng)絡(luò)(Graph ATtention network， GAT)，在卷積的過程中引入了注意機制以學(xué)習(xí)不同近鄰節(jié)點的權(quán)重，得到改進(jìn)的GCN;還有Gao等[12]提出的大規(guī)模可學(xué)習(xí)圖卷積神經(jīng)網(wǎng)絡(luò)(large-scale Learnable GCN， LGCN)，通過對鄰居節(jié)點的單個特征值大小進(jìn)行排序以實現(xiàn)數(shù)據(jù)預(yù)處理，訓(xùn)練時采用傳統(tǒng)的卷積。

　　在基于空間域的GCN模型中，節(jié)點的鄰域組成較為簡單，通常由一階鄰居節(jié)點組成，而忽視了二階乃至高階鄰居節(jié)點;此外，鄰居節(jié)點的排序也僅僅根據(jù)節(jié)點的自身屬性，而沒有考慮到節(jié)點的結(jié)構(gòu)重要性。因此，為獲得找到更有效的鄰域序列，本文提出了一種基于鄰域選擇策略的GCN模型——CoN-GCN(Core Neighbors-GCN)。該模型主要工作在于提出了一種啟發(fā)式的鄰域選擇策略，為待編碼節(jié)點選擇重要的鄰域節(jié)點并分級采樣得到固定數(shù)量的核心鄰域節(jié)點。經(jīng)過初步編碼后，將節(jié)點及其鄰域的特征矩陣送入卷積層，和傳統(tǒng)GCN模型一樣進(jìn)行半監(jiān)督的節(jié)點分類。通過為每個節(jié)點聚合其鄰域節(jié)點的特征，能夠?qū)W得該節(jié)點的有效嵌入表示。

　　1 相關(guān)工作

　　由于基于空間域的卷積更易擴(kuò)展，最近得到研究者的密切關(guān)注，也出現(xiàn)了許多新的方法。

　　一些方法著重于采樣策略的設(shè)計，例如：PATCHY-SAN方法[10]使用圖形標(biāo)記方法(如Weisfeiler-Lehman核[13])為節(jié)點分配序號，在每個節(jié)點vi的k步鄰域Nk(i)中選擇固定數(shù)量的節(jié)點定義vi的“接收場”，然后采用標(biāo)準(zhǔn)的1-D CNN并進(jìn)行歸一化處理。不過該方法依賴于圖形標(biāo)記過程，并且節(jié)點排序策略較為簡單。PinSage方法[14]是在圖上進(jìn)行隨機游走以改進(jìn)鄰域采樣方法，在真正的超大規(guī)模網(wǎng)絡(luò)中具有良好的性能。在FastGCN方法[15]中，研究者不是對每個節(jié)點的鄰居進(jìn)行采樣，而是將圖卷積操作視為積分過程，按照生成的積分函數(shù)對每個卷積層中的節(jié)點進(jìn)行采樣。

　　另一些方法設(shè)計如何聚合鄰居節(jié)點的特征，例如：圖采樣與聚合(Graph Sample and AGgrEgate， GraphSAGE)算法[16]提出了一種鄰居節(jié)點特征聚集方法，每個節(jié)點都采樣固定數(shù)量的鄰居，通過聚集鄰居節(jié)點的特征更新當(dāng)前節(jié)點的特征。隨著模型層數(shù)的增加，每個節(jié)點可以獲取到距離更遠(yuǎn)的節(jié)點信息。LGCN[12]使用了對鄰居節(jié)點特征值排序的方式進(jìn)行聚合，首先將節(jié)點及其鄰域整合為一個矩陣，并按特征值的大小對每列元素進(jìn)行排序，不過該方法改變了節(jié)點的原始特征，可解釋性較差。GAT方法[11]采用注意力機制學(xué)習(xí)相鄰節(jié)點的特征權(quán)重并聚合，每一個節(jié)點由局部過濾器得到所有的相鄰節(jié)點，并通過度量每個鄰居節(jié)點與中心節(jié)點之間特征向量的相關(guān)性來獲得不同的權(quán)重。

　　此外，還有一些方法對卷積的過程進(jìn)行設(shè)計，例如：跳躍知識網(wǎng)絡(luò)(Jumping Knowledge Networks， JK-Nets)[17]將所有中間層的信息跳至輸出層，使得模型有選擇性地學(xué)習(xí)全局和局部結(jié)構(gòu)，解決了GCN模型隨層數(shù)加深而效果變差的問題。 雙圖卷積網(wǎng)絡(luò)(Dual GCN， DGCN)[18]基于全局一致性和局部一致性的概念，采用基于鄰域節(jié)點和基于鄰域擴(kuò)散的雙圖卷積模式，通過引入無監(jiān)督時間損失函數(shù)將兩個網(wǎng)絡(luò)進(jìn)行整合。

　　2 本文模型CoN-GCN

　　本文提出了一種基于空間域的GCN模型CoN-GCN，其偽代碼見算法1。該模型的重點在于如何設(shè)計新的采樣策略，以更好地聚合鄰域節(jié)點的特征。首先為待編碼節(jié)點選擇核心鄰域節(jié)點，隨后將待編碼節(jié)點及其核心鄰域節(jié)點的特征矩陣送入深度CNN中進(jìn)行訓(xùn)練，最終實現(xiàn)節(jié)點分類任務(wù)。其中，核心鄰域節(jié)點的選擇可分為兩步：第一步是根據(jù)結(jié)構(gòu)緊密度獲得每個待編碼節(jié)點的候選鄰域節(jié)點序列;第二步是從候選鄰域節(jié)點序列中為待編碼節(jié)點按級數(shù)從小到大選擇k個固定數(shù)量的核心鄰域節(jié)點。

　　2.1 鄰域節(jié)點重要性排序

　　假設(shè)圖中的每個節(jié)點v有M個描述特征，即每個節(jié)點可以表示為x∈R1×M，其中，x=〈x1，x2，…，xM〉。令v0表示待編碼的節(jié)點，xv0i表示v0的第i個特征(i=1，2，…，M)。為了獲得v0的核心鄰域節(jié)點，需要先對候選節(jié)點的重要性進(jìn)行排序，得到v0的候選鄰域節(jié)點序列N(v0)。為將本文提出的算法應(yīng)用范圍擴(kuò)展到僅有連接關(guān)系而沒有具體特征值的數(shù)據(jù)集上，采用了結(jié)構(gòu)優(yōu)先原則。

　　推薦閱讀：計算機專業(yè)論文投稿