陳可佳　楊澤宇

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

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

中圖分類號(hào)： TP311文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-9081（2019）12-3415-05

DOI：10.11772/j.issn.1001-9081.2019071281

Graph convolutional network model using neighborhood selection strategy

CHEN Kejia1，2， YANG Zeyu， LU Hao1，2

1. School of Computer Science， Nanjing University of Posts and Telecommunications， Nanjing Jiangsu 210046， China;

2. Jiangsu Key Laboratory of Big Data Security and Intelligent Processing， Nanjing Jiangsu 210046， China

Abstract： The composition of neighborhoods is crucial for the spatial domain-based Graph Convolutional Network （GCN） model. To solve the problem that the structural influence is not considered in the neighborhood ordering of nodes in the model， a novel neighborhood selection strategy was proposed to obtain an improved GCN model. Firstly， the structurally important neighborhoods were collected for each node and the core neighborhoods were selected hierarchically. Secondly， the features of the nodes and their core neighborhoods were organized into a matrix. Finally， the matrix was sent to deep Convolutional Neural Network （CNN） for semi-supervised learning. The experimental results on Cora， Citeseer and Pubmed citation network datasets show that， the proposed model has a better accuracy in node classification tasks than the model based on classical graph embedding and four state-of-the-art GCN models. As a spatial domain-based GCN， the proposed model can be effectively applied to the learning tasks of large-scale networks.

Key words： Graph Convolutional Network （GCN）; neighborhood selection strategy; graph embedding; node classification; semi-supervised learning

0 引言

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

傳統(tǒng)的網(wǎng)絡(luò)表示（如鄰接矩陣）存在結(jié)構(gòu)稀疏和維度過高的問題，難以有效地學(xué)習(xí)。而手動(dòng)抽取網(wǎng)絡(luò)的結(jié)構(gòu)特征（如共同鄰居數(shù)）需要豐富的領(lǐng)域知識(shí)，根據(jù)網(wǎng)絡(luò)特點(diǎn)人工選擇有效的特征，因此不具有普適性。直覺上來看，在網(wǎng)絡(luò)中拓?fù)浣Y(jié)構(gòu)相似的節(jié)點(diǎn)也應(yīng)該具有相近的向量表示[1]。因此，研究者開始學(xué)習(xí)圖或網(wǎng)絡(luò)的內(nèi)在表示形式，自動(dòng)融合網(wǎng)絡(luò)的結(jié)構(gòu)特征和節(jié)點(diǎn)的內(nèi)在特征。之后，這些學(xué)得的特征能夠更好地用于各類學(xué)習(xí)任務(wù)。由于網(wǎng)絡(luò)表示學(xué)習(xí)研究具有重要的學(xué)術(shù)價(jià)值和應(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）機(jī)器學(xué)習(xí)范式的研究，并已取得階段性的成果。CNN具有自動(dòng)抽取高階語義和自動(dòng)編碼降維的優(yōu)勢，在圖像分類[5]、目標(biāo)檢測[6]等圖像處理任務(wù)中表現(xiàn)突出。圖像數(shù)據(jù)具有規(guī)則的柵格結(jié)構(gòu)（圖1（a）），CNN通過固定的卷積核掃描整幅圖像，獲得卷積核覆蓋范圍內(nèi)的局部信息，通過訓(xùn)練獲得卷積核參數(shù)，實(shí)現(xiàn)特征的自動(dòng)抽取。然而，圖數(shù)據(jù)一般不具備規(guī)則的空間結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)的連接數(shù)量不盡相同（圖1（b）），因此CNN的平移不變性在圖上不再適用，需要為待編碼節(jié)點(diǎn)選擇固定數(shù)量且有序的近鄰節(jié)點(diǎn)，以滿足傳統(tǒng)卷積的輸入要求。

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

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

1 相關(guān)工作

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

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

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

此外，還有一些方法對(duì)卷積的過程進(jìn)行設(shè)計(jì)，例如：跳躍知識(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é)點(diǎn)和基于鄰域擴(kuò)散的雙圖卷積模式，通過引入無監(jiān)督時(shí)間損失函數(shù)將兩個(gè)網(wǎng)絡(luò)進(jìn)行整合。

2 本文模型CoN-GCN

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

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

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

1）計(jì)算網(wǎng)絡(luò)中所有節(jié)點(diǎn)與中心節(jié)點(diǎn)之間的結(jié)構(gòu)度量作為關(guān)系緊密度，值越高則說明該節(jié)點(diǎn)對(duì)于中心節(jié)點(diǎn)越重要。其中，結(jié)構(gòu)度量可使用共同鄰居數(shù)[19]、Jaccard系數(shù)[20]、Adamic/Adar系數(shù)[21]等常用指標(biāo)，相關(guān)計(jì)算式如下。

其中Γ（v）表示節(jié)點(diǎn)v的1階鄰居節(jié)點(diǎn)集合。

2）如果序列中出現(xiàn)結(jié)構(gòu)度量值相同的節(jié)點(diǎn)，表示從結(jié)構(gòu)上看這些候選節(jié)點(diǎn)對(duì)中心節(jié)點(diǎn)同等重要。為進(jìn)一步區(qū)分它們的重要性，本文采用距離度量方法，即在節(jié)點(diǎn)的外部特征向量空間中，按候選節(jié)點(diǎn)與中心節(jié)點(diǎn)之間距離進(jìn)一步判定候選節(jié)點(diǎn)的重要程度，距離越小候選節(jié)點(diǎn)越重要。式（4）表示歐氏距離度量：

Dist（v0，vk）=（∑Mi=1（xvki-xv0i）1/2; vk∈N（v0）

（4）

考慮到節(jié)點(diǎn)特征的稀疏性問題，算法1先對(duì)v0進(jìn)行降維（第1）行），第4）～5）行實(shí)現(xiàn)了鄰域節(jié)點(diǎn)重要性排序。第4）行是根據(jù)結(jié)構(gòu)重要性對(duì)候選節(jié)點(diǎn)排序。第5）行表示在結(jié)構(gòu)重要性一致的情況下，使用特征相似度對(duì)候選節(jié)點(diǎn)序列進(jìn)一步調(diào)整。

2.2 核心鄰域節(jié)點(diǎn)的選擇

傳統(tǒng)CNN要求卷積對(duì)象的每次輸入格式固定，因此需要確定k個(gè)最核心的鄰域節(jié)點(diǎn)，組成C（v0）。在鄰域節(jié)點(diǎn)重要性排序后，可能出現(xiàn)高階鄰居節(jié)點(diǎn)排在低階鄰居節(jié)點(diǎn)之前的情況。此外，還可能存在節(jié)點(diǎn)的鄰居數(shù)量較少而無法獲得足夠核心鄰域節(jié)點(diǎn)的情況。因此，本文采用層級(jí)擴(kuò)展策略：先對(duì)低階鄰居節(jié)點(diǎn)按重要性順序采樣，再逐步進(jìn)入高階鄰居節(jié)點(diǎn)層采樣，直至C（v0）達(dá)到k為止。當(dāng)遇到候選節(jié)點(diǎn)的結(jié)構(gòu)重要度為0而C（v0）還未達(dá)到k時(shí)，則由序列中的第一個(gè)節(jié)點(diǎn)補(bǔ)足。

算法1中的第7）～11）行表示核心鄰域選擇過程。Select （·）表示從C（v0）中選出當(dāng)前層的鄰居序列。

2.3 1-D CNN生成節(jié)點(diǎn)嵌入

經(jīng)過上述操作，本文獲得了維度固定且高度有序的矩陣結(jié)構(gòu)V0∈R（k+1）×M，隨后使用1-D卷積核進(jìn)行特征抽取，將核心鄰域節(jié)點(diǎn)的信息向待編碼節(jié)點(diǎn)進(jìn)行整合。多次卷積操作之后，v0節(jié)點(diǎn)編碼為x∈R1×m，即節(jié)點(diǎn)維度從M維變?yōu)閙維。

算法1中的第12）行描述了通過1-D CNN得到節(jié)點(diǎn)v0的嵌入表示。STACK（·）表示將v0和C（v0）的特征向量按行進(jìn)行拼接。

圖2為CoN-GCN單層卷積過程示例，左側(cè)部分即為核心鄰域節(jié)點(diǎn)的采樣（k=4，M=4）。圖例中，結(jié)構(gòu)重要度通過Jaccard系數(shù)判定。當(dāng)Jaccard系數(shù)相同，如圖中JC（v1）=JC（v2），根據(jù)式（4），v1比v2更接近v0，因此v1的特征向量排在v2前面。隨后，將中心節(jié)點(diǎn)v0的原始向量放在首行，按順序拼接核心鄰域節(jié)點(diǎn)的外部特征向量，構(gòu)造出由k+1個(gè)向量組成的矩陣結(jié)構(gòu)。圖2的右側(cè)部分表示使用兩層1-D CNN對(duì)其進(jìn)行操作，兩層卷積核的數(shù)量分別為n和m。其中，1-D CNN也可采用其他CNN模型。

2.4 深度CoN-GCN

單層CoN-GCN中聚合的是經(jīng)過選擇的鄰域節(jié)點(diǎn)的信息，較為有限。為了獲得更好的特征，本文還提供了更深的CoN-GCN模型，如圖3所示，能夠逐步聚合更遠(yuǎn)節(jié)點(diǎn)的信息。CoN-GCN的堆疊數(shù)量一般取決于任務(wù)的復(fù)雜性，如類的數(shù)量、圖中節(jié)點(diǎn)的數(shù)量等參數(shù)。為了提升CoN-GCN模型性能并促進(jìn)訓(xùn)練過程，本文在堆疊的過程中加入了前層信息。在整個(gè)模型的最后使用全連接層完成對(duì)全部節(jié)點(diǎn)信息的收集，并通過softmax函數(shù)得到節(jié)點(diǎn)分類結(jié)果。

在算法1中，外層循環(huán)（第3）行）描述了這一過程。CAT（·）表示將特征向量按列進(jìn)行拼接。

3 實(shí)驗(yàn)結(jié)果與分析

本章比較了CoN-GCN與經(jīng)典的節(jié)點(diǎn)嵌入方法DeepWalk[2]以及四種近期提出的GCN方法[8-9，12，22]在節(jié)點(diǎn)分類任務(wù)上的準(zhǔn)確性，并針對(duì)不同的結(jié)構(gòu)度量指標(biāo)和不同的超參數(shù)k進(jìn)行了性能對(duì)比實(shí)驗(yàn)。

3.1 數(shù)據(jù)集

本文使用了Cora、Citeseer和Pubmed三個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集，統(tǒng)計(jì)信息見表1。這三個(gè)數(shù)據(jù)集均為引用被引用網(wǎng)絡(luò)數(shù)據(jù)集，其中節(jié)點(diǎn)表示論文，邊表示引用關(guān)系。每個(gè)節(jié)點(diǎn)的特征為該論文的詞袋表示（bag of words）。為了便于比較，所有方法均采用了相同的實(shí)驗(yàn)設(shè)置：對(duì)于每個(gè)類，20個(gè)節(jié)點(diǎn)用于訓(xùn)練，500個(gè)節(jié)點(diǎn)用于驗(yàn)證，1000個(gè)節(jié)點(diǎn)用于測試。

實(shí)驗(yàn)進(jìn)行了直推學(xué)習(xí)（transductive learning）下的節(jié)點(diǎn)分類任務(wù)。直推學(xué)習(xí)是一種半監(jiān)督學(xué)習(xí)算法，在節(jié)點(diǎn)分類任務(wù)中，由于數(shù)據(jù)集里僅存在一部分有類別標(biāo)簽的節(jié)點(diǎn)，該方法可以在訓(xùn)練過程中使用其他節(jié)點(diǎn)（包括測試節(jié)點(diǎn)）的特征以及節(jié)點(diǎn)間的連接關(guān)系。

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

由于數(shù)據(jù)集中節(jié)點(diǎn)的特征維度較高，實(shí)驗(yàn)使用了GCN算法[9]將特征降維至32維。在分類準(zhǔn)確性的比較實(shí)驗(yàn)中，本文在三種結(jié)構(gòu)度量指標(biāo)（CN、JC、AA）下均進(jìn)行了CoN-GCN方法的實(shí)驗(yàn)，并將核心節(jié)點(diǎn)數(shù)k設(shè)置為8。在Cora、Citeseer和Pubmed中，CoN-GCN的層數(shù)分別為2、1和1。最后使用一個(gè)全連接層用于節(jié)點(diǎn)分類和預(yù)測。在全連接層之前，本文對(duì)特征進(jìn)行拼接。為了防止過擬合，輸入層使用失活率為0.16的Dropout算法，卷積層使用L2正則化（λ=0.0005）。在訓(xùn)練過程中，本文使用Adam優(yōu)化器對(duì)訓(xùn)練速度進(jìn)行優(yōu)化，學(xué)習(xí)率為0.1，當(dāng)驗(yàn)證集錯(cuò)誤率出現(xiàn)持續(xù)上升時(shí)，則停止訓(xùn)練。

3.3 節(jié)點(diǎn)分類比較結(jié)果與分析

表2給出了不同方法（DeepWalk[2]、Planetoid[22]、Chebyshev[8]、GCN[9]、LGCN[12]、CoN-GCNCN、CoN-GCNJC、CoN-GCNAA）在節(jié)點(diǎn)分類中運(yùn)行10次得到的平均準(zhǔn)確率。實(shí)驗(yàn)結(jié)果表明，CoN-GCN模型在不同數(shù)據(jù)集的節(jié)點(diǎn)分類任務(wù)中的表現(xiàn)均優(yōu)于其他模型，驗(yàn)證了本文鄰域采樣策略的有效性。在對(duì)比算法中，GCN等由于所使用的種子固定具有復(fù)現(xiàn)性，而LGCN等不具備復(fù)現(xiàn)性，同時(shí)為了觀察不同結(jié)構(gòu)度量對(duì)于鄰域選擇的影響，還比較了本文方法在三種配置下（CoN-GCNCN、CoN-GCNJC和CoN-GCNAA）的實(shí)驗(yàn)結(jié)果，發(fā)現(xiàn)總體上CoN-GCNCN表現(xiàn)更好，這表明共同鄰居數(shù)依然是最有效的結(jié)構(gòu)相似性度量方法。Admic/Adar系數(shù)表現(xiàn)較差，可能的原因是該系數(shù)常用于度量社交網(wǎng)絡(luò)的節(jié)點(diǎn)結(jié)構(gòu)相似性，而不太適用于引用被引用網(wǎng)絡(luò)。

3.4 超參數(shù)k的影響

為了觀察不同超參數(shù)k對(duì)CoN-GCN的影響，本文對(duì)多個(gè)k值（k=4，6，8，10，12，14，16）分別進(jìn)行了實(shí)驗(yàn)，觀察CoN-GCN在三個(gè)數(shù)據(jù)集上的分類結(jié)果變化情況，結(jié)果如圖4所示。

實(shí)驗(yàn)結(jié)果表明，當(dāng)k=8時(shí)，CoN-GCN模型在所有三個(gè)數(shù)據(jù)集中均具有良好的表現(xiàn)。經(jīng)過統(tǒng)計(jì)可知，Cora、Citeseer和Pubmed數(shù)據(jù)集的平均節(jié)點(diǎn)度分別為4、5和6。從實(shí)驗(yàn)結(jié)果推測，k值通常可選擇比網(wǎng)絡(luò)平均節(jié)點(diǎn)度稍大的值。圖4中，當(dāng)k值過大時(shí)，模型的性能有所下降?？赡艿脑蚴呛诵泥徲蚬?jié)點(diǎn)中存在過多的零向量，而簡單的填充操作會(huì)降低卷積的特征提取能力。

4 結(jié)語

本文提出了一種基于空間域的圖卷積模型——CoN-GCN，通過鄰域采樣策略實(shí)現(xiàn)對(duì)通用圖數(shù)據(jù)的處理，然后進(jìn)行常規(guī)的卷積操作。實(shí)驗(yàn)結(jié)果表明，在直推學(xué)習(xí)節(jié)點(diǎn)分類任務(wù)中， CoN-GCN具有更優(yōu)的準(zhǔn)確率。接下來的工作中，我們將繼續(xù)探討CoN-GCN的深度對(duì)于分類性能的影響，并在更多任務(wù)（如鏈接預(yù)測、社團(tuán)檢測等）中考察CoN-GCN的魯棒性。此外，我們還將繼續(xù)探討異質(zhì)信息網(wǎng)絡(luò)[23]中的CoN-GCN模型。

參考文獻(xiàn) （References）

[1]涂存超，楊成，劉知遠(yuǎn)，等.網(wǎng)絡(luò)表示學(xué)習(xí)綜述[J].中國科學(xué)：信息科學(xué)，2017，47（8）：980-996.（TU C C， YANG C， LIU Z Y， et al. Network representation learning： an overview [J]. SCIENTIA SINICA Informationis， 2017， 47（8）： 980-996.）

[2]PEROZZI B， AL-RFOU R， SKIENA S. DeepWalk： online learning of social representations [C]// Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2014： 701-710.

[3]GROVER A， LESKOVEC J. Node2Vec： scalable feature learning for networks [C]// Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2016： 855-864.

[4]TANG J， QU M， WANG M， et al. LINE： large-scale information network embedding [C]// Proceedings of the 24th International Conference on World Wide Web. New York： ACM， 2015： 1016-1077.

[5]DENG J， DONG W， SOCHER R， et al. ImageNet： a large-scale hierarchical image database [C]// Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway： IEEE， 2009： 248-255.

[6]REN S， HE K， GIRSHICK R， et al. Faster R-CNN： towards real-time object detection with region proposal networks [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2017， 39（6）： 1137-1149.

[7]BRUNA J， ZAREMBA W， SZLAM A， et al. Spectral networks and locally connected networks on graphs [EB/OL]. [2018-10-13]. https：//arxiv.org/pdf/1312.6203.

[8]DEFFERRARD M， BRESSON X， VANDERGHEYNST P. Convolutional neural networks on graphs with fast localized spectral filtering [C]// Proceedings of the 30th Conference on Neural Information Processing Systems. New York： JMLR， 2016： 3837-3845.

[9]KIPF T N， WELLING M. Semi-supervised classification with graph convolutional networks [EB/OL]. [2018-11-20]. https：//arxiv.org/pdf/1609.02907.

[10]NIEPERT M， AHMED M， KUTZKOV K. Learning convolutional neural networks for graphs [C]// Proceedings of the 33nd International Conference on Machine Learning. New York： PMLR， 2016： 2014-2023.

[11]VELICKOVIC P， CUCURULL G， CASANOVA A， et al. Graph attention networks [EB/OL]. [2018-09-10]. https：//arxiv.org/pdf/1710.10903.

[12]GAO H Y， WANG Z， JI S. Large-scale learnable graph convolutional networks [C]// Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2018： 1416-1424.

[13]SHERVASHIDZE N， SCHWEITZER P， VAN LEEUWEN E J， et al. Weisfeiler-Lehman graph kernels [J]. Journal of Machine Learning Research， 2011， 12（9）： 2539-2561.

[14]YING R， HE R， CHEN K， et al. Graph convolutional neural networks for web-scale recommender systems [C]// Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2018： 974-983.

[15]CHEN J， MA T， XIAO C. FastGCN： fast learning with graph convolutional networks via importance sampling [EB/OL]. [2018-12-20]. https：//arxiv.org/pdf/1801.10247.

[16]HAMILTON W， YING Z， LESKOVEC J. Inductive representation learning on large graphs [C]// Proceedings of the 2017 Conference on Neural Information Processing Systems. San Mateo， CA： Morgan Kaufmann， 2017： 1024-1034.

[17]XU K， LI C， TIAN Y， et al. Representation learning on graphs with jumping knowledge networks [C]// Proceedings of the 35th International Conference on Machine Learning. New York： JMLR， 2018： 5453-5462.

[18]ZHUANG C， MA Q. Dual graph convolutional networks for graph-based semi-supervised classification [C]// Proceedings of the 2018 World Wide Web Conference. New York： ACM， 2018： 499-508.

[19]LYU L， ZHOU T. Link prediction in complex networks： a survey [J]. Physica A： Statistical Mechanics and its Applications， 2011， 390（6）： 1150-1170.

[20]JACCARD P. The distribution of the flora in the alpine zone [J]. New Phytologist， 1912， 11（2）： 37-50.

[21]ADAMIC L， ADAR E. How to search a social network [J]. Social Networks， 2005， 27（3）： 187-203.

[22]YANG Z， COHEN W W， SALAKHUTDINOV R. Revisiting semi-supervised learning with graph embeddings [C]// Proceedings of the 33rd International Conference on Machine Learning. New York： JMLR， 2016： 40-48.

[23]SHI C， LI Y， ZHANG J， et al. A survey of heterogeneous information network analysis [J]. IEEE Transactions on Knowledge and Data Engineering， 2017， 29（1）： 17-37.

This work is partially supported by the National Natural Science Foundation of China （61603197， 61772284）.

CHEN Kejia， born in 1980， Ph. D.， associate professor. Her research interests include data mining， complex network analysis.

YANG Zeyu， born in 1994， M. S. candidate. His research interests include graph convolutional network.

LIU Zheng， born in 1980， Ph. D.， lecturer. His research interests include graph data mining.

LU Hao， born in 1995， M. S. candidate. His research interests include graph convolutional network， network representation learning.

收稿日期：2019-04-29;修回日期：2019-08-07;錄用日期：

2019-08-12?；痦?xiàng)目：國家自然科學(xué)基金資助項(xiàng)目（61603197，61772284）。

作者簡介：陳可佳（1980—），女，江蘇淮安人，副教授，博士， CCF會(huì)員，主要研究方向：數(shù)據(jù)挖掘、復(fù)雜網(wǎng)絡(luò)分析;楊澤宇（1994—），男，山西晉中人，碩士研究生，主要研究方向：圖卷積網(wǎng)絡(luò);劉崢（1980—） ，男，江蘇南京人，講師，博士， CCF會(huì)員，主要研究方向：圖數(shù)據(jù)挖掘;魯浩（1995—） ，男，河南濮陽人，碩士研究生，主要研究方向：圖卷積網(wǎng)絡(luò)、網(wǎng)絡(luò)表示學(xué)習(xí)。