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

　　關鍵詞：圖卷積網絡;鄰域選擇策略;圖嵌入;節點分類;半監督學習

　　0 引言

　　圖或網絡廣泛存在于日常生活中，是抽象現實世界中對象與對象之間關系的一種重要數據結構。如作者之間的引用關系、個人之間的社交關系、城市之間的物流和交通關系、蛋白質之間的交互關系等數據都可以通過圖或網絡抽象地表達。對這類數據的分析和建模能夠挖掘豐富的潛在信息，可廣泛應用于節點分類、社區發現、鏈接預測、推薦系統等任務。

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

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

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

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

　　1 相關工作

　　由于基于空間域的卷積更易擴展，最近得到研究者的密切關注，也出現了許多新的方法。

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

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

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

　　2 本文模型CoN-GCN

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

　　2.1 鄰域節點重要性排序

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

　　推薦閱讀：計算機專業論文投稿