基于局部圖結(jié)構(gòu)的鏈接預(yù)測(cè)模型

收稿日期：2022-03-14；修回日期：2022-05-09

作者簡(jiǎn)介：趙思云（1997-），女，江西九江人，碩士，主要研究方向?yàn)閳D卷積神經(jīng)網(wǎng)絡(luò)（19210980108@fudan.edu.cn）；黃增峰（1985-），男，浙江杭州人，青年研究員，博導(dǎo)，主要研究方向?yàn)闄C(jī)器學(xué)習(xí)算法與理論、大數(shù)據(jù)計(jì)算、理論計(jì)算機(jī)科學(xué)、復(fù)雜網(wǎng)絡(luò)分析．

摘 要：鏈接預(yù)測(cè)是基于已知的部分圖數(shù)據(jù)來(lái)預(yù)測(cè)節(jié)點(diǎn)之間未被觀(guān)測(cè)到的邊或者未來(lái)可能產(chǎn)生的邊的任務(wù)。鏈接預(yù)測(cè)領(lǐng)域目前最表現(xiàn)最佳的方法是，對(duì)所有目標(biāo)節(jié)點(diǎn)對(duì)提取周?chē)牡碗A鄰居小圖，使用小圖進(jìn)行圖分類(lèi)預(yù)測(cè)鏈接的方法。然而，這種方法的穩(wěn)定性和性能受限于圖的局部結(jié)構(gòu)特異性。所提方法在上述算法的基礎(chǔ)上進(jìn)行了改進(jìn)，其根據(jù)目標(biāo)節(jié)點(diǎn)周?chē)?jié)點(diǎn)的結(jié)構(gòu)特征計(jì)算周?chē)?jié)點(diǎn)優(yōu)先值，根據(jù)優(yōu)先值篩選出高優(yōu)先值的節(jié)點(diǎn)集合，并同時(shí)選出一定數(shù)量的隨機(jī)節(jié)點(diǎn)，共同組成封閉子圖，提取子圖特征進(jìn)行鏈接預(yù)測(cè)。實(shí)驗(yàn)表明，該算法有效提高了在不同結(jié)構(gòu)的圖數(shù)據(jù)上選出的小圖的精準(zhǔn)性和穩(wěn)定性，顯著提升了鏈接預(yù)測(cè)的效果。

關(guān)鍵詞：鏈接預(yù)測(cè)；子圖提取；PageRank；節(jié)點(diǎn)編號(hào)

中圖分類(lèi)號(hào)：TP391.4"" 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2022）09-025-2723-08

doi：10.19734/j.issn.1001-3695.2022.03.0117

Link prediction method based on local topological structure

Zhao Siyun，Huang Zengfeng

（School of Data Science，F(xiàn)udan University，Shanghai 200433，China）

Abstract：Link prediction is a task of predicting unobserved edges between nodes or edges that may be connected in the future based on partial graph data.The current state-of-art method of link prediction is to extract the surrounding low-hop subgraphs for all target node pairs and perform graph classification algorithm on the subgraphs to predict the focal link.However，its stability and performance are limited by the diversity of local topological structures.This paper proposed a method to improve the above algorithm.The algorithm calculated the priority value of the surrounding nodes according to their topological feature，selected the most important nodes among the surrounding nodes and a certain number of random nodes to form a closing subgraph together，then extracted feature from the closing subgraph to predict the link.Experiments show that the algorithm ensures the accuracy and stability of intelligently extracting subgraphs on graph data of different structures，and significantly improves the accuracy of link prediction.

Key words：link prediction；subgraph extraction；PageRank；node labeling

0 引言

在高度信息化的現(xiàn)代社會(huì)，數(shù)據(jù)有很多不同的表現(xiàn)形式，其中圖數(shù)據(jù)在生物［1］、醫(yī)療［2］、社交網(wǎng)絡(luò)［3］、知識(shí)補(bǔ)全［4］等領(lǐng)域都具有非常好的應(yīng)用，而鏈接預(yù)測(cè)則是圖數(shù)據(jù)分析中比較重要的任務(wù)之一。圖數(shù)據(jù)由節(jié)點(diǎn)和邊構(gòu)成，每個(gè)節(jié)點(diǎn)表示不同的實(shí)體，而邊則表示實(shí)體之間的各種關(guān)聯(lián)。在實(shí)際情況中，圖數(shù)據(jù)往往都是不完整和動(dòng)態(tài)變化的，在某個(gè)時(shí)刻觀(guān)測(cè)到的圖數(shù)據(jù)可能具有片面性和時(shí)效性，所以如何依據(jù)已知的部分圖數(shù)據(jù)對(duì)真實(shí)的節(jié)點(diǎn)關(guān)聯(lián)情況進(jìn)行預(yù)測(cè)就變得尤為重要。

傳統(tǒng)的鏈接預(yù)測(cè)算法主要是啟發(fā)式的算法，從節(jié)點(diǎn)的相似性出發(fā)，認(rèn)為具有相似背景或者處于相似環(huán)境中的節(jié)點(diǎn)具有更大的傾向會(huì)建立關(guān)聯(lián)關(guān)系，而在已知圖中距離較遠(yuǎn)、所處拓?fù)洵h(huán)境差異較大的節(jié)點(diǎn)對(duì)則在直觀(guān)上來(lái)看毫無(wú)聯(lián)系，也就被認(rèn)為建立連邊的可能性更小。這一類(lèi)的方法在特定的領(lǐng)域仍然具有很好的表現(xiàn)，例如，張玲玲等人［5］將啟發(fā)式的算法與節(jié)點(diǎn)本身的特性結(jié)合，在對(duì)研發(fā)者的潛在合作者進(jìn)行鏈接預(yù)測(cè)時(shí)取得了不錯(cuò)的效果。基于圖嵌入學(xué)習(xí)的方法［6～8］也被用于進(jìn)行鏈接預(yù)測(cè)任務(wù)。無(wú)監(jiān)督的圖嵌入算法會(huì)通過(guò)學(xué)習(xí)圖中的拓?fù)浣Y(jié)構(gòu)，將在圖上距離比較近或者關(guān)聯(lián)比較緊密、鄰居結(jié)構(gòu)比較相似的節(jié)點(diǎn)賦予相近的特征向量，然后用兩個(gè)節(jié)點(diǎn)的特征向量作為輸入訓(xùn)練一個(gè)簡(jiǎn)單的0-1分類(lèi)器就能比較好地對(duì)鏈接進(jìn)行預(yù)測(cè)。在圖卷積神經(jīng)網(wǎng)絡(luò)［9～11］出現(xiàn)之后，通過(guò)圖卷積的方法，先結(jié)合鄰居節(jié)點(diǎn)特征對(duì)每個(gè)節(jié)點(diǎn)的初始特征向量進(jìn)行卷積變換，再用得到的新特征向量進(jìn)行分類(lèi)預(yù)測(cè)，將鏈接預(yù)測(cè)任務(wù)的效果提升了很大一個(gè)臺(tái)階。由于圖卷積神經(jīng)網(wǎng)絡(luò)的卷積層數(shù)往往比較低，對(duì)于每一個(gè)節(jié)點(diǎn)而言，算法輻射的跳數(shù)范圍比較有限，所以說(shuō)明圖數(shù)據(jù)的局部拓?fù)浣Y(jié)構(gòu)對(duì)鏈接預(yù)測(cè)任務(wù)具有比較高的有效性。近年來(lái)，Singh等人［12］提出了基于邊集兩次預(yù)測(cè)的鏈接預(yù)測(cè)模型，認(rèn)為原始的訓(xùn)練集中的邊與真實(shí)數(shù)據(jù)存在較大差異的現(xiàn)象是影響鏈接預(yù)測(cè)準(zhǔn)確性的主要原因。他們使用一種方法對(duì)訓(xùn)練集中的邊進(jìn)行一次預(yù)測(cè)補(bǔ)全后，再選用另一相同或不同的算法，基于補(bǔ)全后的邊集來(lái)進(jìn)行鏈接預(yù)測(cè)。Li等人［13］提出了基于距離增強(qiáng)的鏈接預(yù)測(cè)方法，在全圖中選出一些較為重要的節(jié)點(diǎn)，并計(jì)算其他節(jié)點(diǎn)到這些節(jié)點(diǎn)的距離參數(shù)，將這些參數(shù)加入神經(jīng)網(wǎng)絡(luò)中進(jìn)行預(yù)測(cè)。

Zhang等人［14］提出了SEAL模型，該工作證明了所有啟發(fā)式的算法均可用中心節(jié)點(diǎn)的k跳子圖做近似，并提出了抽取目標(biāo)節(jié)點(diǎn)對(duì)周?chē)泥従觡跳小圖，對(duì)小圖進(jìn)行圖分類(lèi)進(jìn)行鏈接預(yù)測(cè)的方法，也使得鏈接預(yù)測(cè)任務(wù)在穩(wěn)健性和準(zhǔn)確性上取得了很大的突破。

上述方法各自從不同的角度對(duì)鏈接預(yù)測(cè)算法進(jìn)行了改善和提升，但是仍然存在一些局限性。圖數(shù)據(jù)的稠密程度、全圖結(jié)構(gòu)特征、局部連邊結(jié)構(gòu)在不同背景的數(shù)據(jù)集上差異非常大。所以希望在目前表現(xiàn)最佳的“提取子圖+圖分類(lèi)”的鏈接預(yù)測(cè)框架下，圖分類(lèi)端輸入的子圖能更加規(guī)范，這就要求它至少具有相近的節(jié)點(diǎn)個(gè)數(shù)。另一方面，目標(biāo)節(jié)點(diǎn)對(duì)的周?chē)匾潭雀叩墓?jié)點(diǎn)不一定位于它們的低跳鄰居里，所以希望能更加智能地找到鏈接預(yù)測(cè)任務(wù)中重要程度更高的節(jié)點(diǎn)。

本文基于SEAL［14］提出的鏈接預(yù)測(cè)框架進(jìn)行了改進(jìn)，提出了一種更有針對(duì)性的固定節(jié)點(diǎn)個(gè)數(shù)的子圖提取方法，在不同稠密程度和拓?fù)浣Y(jié)構(gòu)的局部區(qū)域上，可以兼顧隨機(jī)性和特異性的選擇重要的周?chē)?jié)點(diǎn)進(jìn)入封閉子圖，同時(shí)相對(duì)應(yīng)地調(diào)整了適合的節(jié)點(diǎn)編號(hào)與圖分類(lèi)方法，顯著地提升了模型的性能。總的來(lái)說(shuō)，本文的貢獻(xiàn)主要包括以下三點(diǎn)：

a）基于“提取子圖+圖分類(lèi)”的鏈接預(yù)測(cè)框架，結(jié)合個(gè)性化PageRank（personalized PageRank，PPR）等啟發(fā)式方法，提出了一種端到端的鏈接預(yù)測(cè)模型，應(yīng)對(duì)不同稠密程度和不同背景的圖數(shù)據(jù)，發(fā)現(xiàn)周?chē)?jié)點(diǎn)對(duì)于中心節(jié)點(diǎn)的重要性差異，智能地對(duì)大圖進(jìn)行預(yù)處理和子圖提取，并最終通過(guò)圖分類(lèi)算法得到鏈接預(yù)測(cè)結(jié)果。

b）提出了一種針對(duì)目標(biāo)節(jié)點(diǎn)對(duì)的封閉子圖提取方法，綜合目標(biāo)節(jié)點(diǎn)對(duì)周?chē)?jié)點(diǎn)的全局重要性和局部重要性，使每個(gè)提取出的封閉子圖具有更高的表達(dá)力和相同的規(guī)模，提高了在鏈接預(yù)測(cè)場(chǎng)景下圖分類(lèi)任務(wù)的輸入規(guī)范性。

c）在多個(gè)不同背景的數(shù)據(jù)集上進(jìn)行大量實(shí)驗(yàn)，并與多個(gè)具有代表性的基線(xiàn)模型進(jìn)行實(shí)驗(yàn)對(duì)比，得到了非常優(yōu)秀的效果。

基于子圖提取和圖分類(lèi)的鏈接預(yù)測(cè)框架如圖1所示。

1 相關(guān)工作

1.1 啟發(fā)式方法

啟發(fā)式方法是最早被用來(lái)進(jìn)行鏈接預(yù)測(cè)的傳統(tǒng)方法之一，它是基于一些可以計(jì)算的圖數(shù)據(jù)上的靜態(tài)特征描述節(jié)點(diǎn)之間的相似性，并通過(guò)這些相似性對(duì)節(jié)點(diǎn)間是否存在邊相連進(jìn)行預(yù)測(cè)方法的統(tǒng)稱(chēng)。總的來(lái)說(shuō)，這類(lèi)方法認(rèn)為節(jié)點(diǎn)相似性越高的節(jié)點(diǎn)對(duì)存在邊的概率越高，反之越低。啟發(fā)式方法可以粗略地分為一階方法、二階方法和高階方法。顧名思義，一階的啟發(fā)式方法在計(jì)算過(guò)程中只需要用到兩個(gè)節(jié)點(diǎn)之間的一階鄰居，如共同鄰居個(gè)數(shù)法、Jaccard系數(shù)法、擇優(yōu)連接法［15］等；二階的啟發(fā)式方法最多用到兩個(gè)目標(biāo)節(jié)點(diǎn)的二度鄰居，如AA（Adamic-Adar）［3］和RA（resource allocation）［16］；高階的啟發(fā)式方法可以用到兩個(gè)目標(biāo)節(jié)點(diǎn)的三度及以上的所有鄰居，最常見(jiàn)的有Page-Rank［17］、SimRank［18］、Katz系數(shù)法［19］等。啟發(fā)式方法的局限性也非常明顯，即基于靜態(tài)圖計(jì)算的指標(biāo)特征在不同的數(shù)據(jù)上都有比較大的差異，而且單個(gè)的指標(biāo)往往無(wú)法比較全面地衡量拓?fù)浣Y(jié)構(gòu)的多維特征，所以表達(dá)力度也比較有限。本文模型可以基于不同數(shù)據(jù)的特點(diǎn)智能地訓(xùn)練鏈接預(yù)測(cè)模型，同時(shí)也綜合了多個(gè)維度的啟發(fā)式方法，比較全面地描述了節(jié)點(diǎn)之間的相關(guān)關(guān)系。

1.2 基于圖嵌入方法的鏈接預(yù)測(cè)

圖數(shù)據(jù)是一種非常高維的非歐壓數(shù)據(jù)結(jié)構(gòu)，所以想要直接利用圖網(wǎng)絡(luò)結(jié)構(gòu)中的所有信息會(huì)非常困難，而且計(jì)算代價(jià)很大。因此圖嵌入方法［6，7，20，21］應(yīng)運(yùn)而生，它的本質(zhì)是希望通過(guò)低維的向量來(lái)表達(dá)每個(gè)節(jié)點(diǎn)中蘊(yùn)涵的圖結(jié)構(gòu)信息。好的圖嵌入方法可以在學(xué)到了圖中每個(gè)節(jié)點(diǎn)的圖嵌入向量特征之后，能夠通過(guò)這些節(jié)點(diǎn)特征向量盡可能準(zhǔn)確地反推出完整的圖網(wǎng)絡(luò)結(jié)構(gòu)。變分圖自編碼器模型［7］將節(jié)點(diǎn)特征矩陣的每一行看做是一個(gè)高維高斯分布的隨機(jī)變量，構(gòu)建模型學(xué)習(xí)高斯分布的均值和方差，通過(guò)高斯分布采樣得到每個(gè)節(jié)點(diǎn)的特征矩陣Zn×d，其中n表示節(jié)點(diǎn)數(shù)量，d表示特征維數(shù)，之后使用Z·ZT作為解碼器還原出原始的鄰接矩陣。node2vec［6］是基于隨機(jī)游走的無(wú)監(jiān)督圖嵌入方法，它用圖上的連邊權(quán)重來(lái)構(gòu)建從每個(gè)節(jié)點(diǎn)出發(fā)走到其他鄰居節(jié)點(diǎn)的概率矩陣，然后以此在圖上采樣出大量隨機(jī)游走序列，同時(shí)使用負(fù)采樣的方式，隨機(jī)抽取一些在圖上相距非常遠(yuǎn)的節(jié)點(diǎn)對(duì)，通過(guò)優(yōu)化節(jié)點(diǎn)特征向量的內(nèi)積使得距離越近的節(jié)點(diǎn)特征向量越相似，而距離越遠(yuǎn)的節(jié)點(diǎn)特征向量越無(wú)關(guān)。因此，圖嵌入方法所得到的節(jié)點(diǎn)特征向量往往天然與圖上的連邊情況息息相關(guān)，使用圖嵌入方法之后，再將目標(biāo)節(jié)點(diǎn)對(duì)的兩個(gè)節(jié)點(diǎn)特征輸入簡(jiǎn)單的分類(lèi)器模型，就往往能得到很好的效果。這一類(lèi)的圖嵌入方法聚焦學(xué)習(xí)圖網(wǎng)絡(luò)結(jié)構(gòu)，但是無(wú)法將節(jié)點(diǎn)的原生特征與圖的拓?fù)浣Y(jié)構(gòu)綜合到一起進(jìn)行學(xué)習(xí)，所以還是損失了一定的信息和學(xué)習(xí)效率。本文模型通過(guò)能夠綜合節(jié)點(diǎn)的原生特征和局部拓?fù)浣Y(jié)構(gòu)，很好地解決了這一問(wèn)題。

1.3 圖卷積神經(jīng)網(wǎng)絡(luò)

圖卷積神經(jīng)網(wǎng)絡(luò)也是圖數(shù)據(jù)上的一類(lèi)可擴(kuò)展性和表達(dá)力度都很高的模型。這類(lèi)方法的基本思想是在圖結(jié)構(gòu)中通過(guò)鄰居關(guān)系來(lái)傳遞并聚合信息。一般來(lái)說(shuō)，圖卷積神經(jīng)網(wǎng)絡(luò)類(lèi)方法會(huì)先聚合每個(gè)節(jié)點(diǎn)的周?chē)朽従犹卣鳎賹⒕酆虾蟮男畔⑴c目標(biāo)節(jié)點(diǎn)當(dāng)前的信息進(jìn)行加權(quán)合并，然后使用這些信息同時(shí)更新圖上所有節(jié)點(diǎn)的特征向量。在圖卷積神經(jīng)網(wǎng)絡(luò)類(lèi)的算法研究中，不同的加權(quán)方法、采樣方法、聚合方法等被納入考慮進(jìn)行了研究。Kipf等人［11］提出的GCN模型通過(guò)使用均值聚合來(lái)近似計(jì)算的方式，把圖的卷積操作推廣到了圖的譜域上。為了解決圖的動(dòng)態(tài)更新問(wèn)題以及不同節(jié)點(diǎn)鄰居數(shù)量分布不均勻的問(wèn)題，Hamilton等人［9］提出了GraphSAGE模型，該方法采用有放回抽樣的方式在每次聚合操作時(shí)對(duì)每個(gè)節(jié)點(diǎn)抽取相同數(shù)量的鄰居節(jié)點(diǎn)，將所有所抽取的鄰居節(jié)點(diǎn)特征與中心節(jié)點(diǎn)特征合并，并逐點(diǎn)更新下一層的節(jié)點(diǎn)特征。GAT模型［10］在圖卷積神經(jīng)網(wǎng)絡(luò)中引入了注意力機(jī)制，它考慮到聚合過(guò)程中每個(gè)鄰居節(jié)點(diǎn)不同的相對(duì)重要性，通過(guò)學(xué)習(xí)多個(gè)注意力參數(shù)來(lái)控制聚合過(guò)程中鄰居節(jié)點(diǎn)的相對(duì)權(quán)重，使得圖卷積變得更加智能。GIN模型［22］提出了一種新型的聚合合并方式，使得圖卷積神經(jīng)網(wǎng)絡(luò)模型可以在區(qū)別同構(gòu)圖的問(wèn)題上做到接近Weisfeiler-Lehman測(cè)試［23］的效果，同時(shí)也在圖卷積神經(jīng)網(wǎng)絡(luò)的傳統(tǒng)任務(wù)中達(dá)到了非常良好的性能。然而基于全圖的圖卷積神經(jīng)網(wǎng)絡(luò)方法由于訓(xùn)練時(shí)讀入的視野范圍非常大，而無(wú)法聚焦目標(biāo)節(jié)點(diǎn)對(duì)周?chē)男D的局部拓?fù)浣Y(jié)構(gòu)，所以忽略了很多局部特征。本文模型通過(guò)提取目標(biāo)節(jié)點(diǎn)對(duì)周?chē)泥従有D進(jìn)行訓(xùn)練的方式，使得模型能夠更多地關(guān)注到目標(biāo)節(jié)點(diǎn)對(duì)周?chē)木植烤W(wǎng)絡(luò)結(jié)構(gòu)的細(xì)微特征，從而更準(zhǔn)確地對(duì)鏈接是否存在進(jìn)行預(yù)測(cè)。

1.4 SEAL

SEAL模型［14］是近年來(lái)最有突破性的鏈接預(yù)測(cè)模型之一，是目前為止在鏈接預(yù)測(cè)任務(wù)上表現(xiàn)最佳的模型，也是本文的主要對(duì)比模型之一。SEAL開(kāi)創(chuàng)性地提出了基于“封閉小圖提取+圖分類(lèi)”的鏈接預(yù)測(cè)框架，證明了所有的高階或低階的啟發(fā)式特征均能夠用目標(biāo)節(jié)點(diǎn)對(duì)的低階鄰居子圖做近似，從而說(shuō)明了對(duì)于鏈接預(yù)測(cè)任務(wù)而言，每一個(gè)目標(biāo)節(jié)點(diǎn)對(duì)周?chē)淖訄D包含了進(jìn)行鏈接預(yù)測(cè)所需要的所有高階和低階的特征，為“封閉小圖提取+圖分類(lèi)”的框架提出了理論支持。同時(shí)，SEAL提出了節(jié)點(diǎn)編號(hào)對(duì)于該框架的重要性，它認(rèn)為鄰居節(jié)點(diǎn)（包括直接鄰居和高階鄰居）對(duì)于目標(biāo)節(jié)點(diǎn)的重要性是各不相同的，需要在小圖進(jìn)行區(qū)別，因而提出了“雙半徑編號(hào)法”來(lái)表示在封閉小圖中不同地位的節(jié)點(diǎn)，相同地位（編號(hào)）的節(jié)點(diǎn)共享同一個(gè)特征向量，這樣在對(duì)封閉小圖進(jìn)行圖分類(lèi)時(shí)就可以共享相同的參數(shù)。

雖然在目標(biāo)節(jié)點(diǎn)對(duì)周?chē)崛》忾]子圖進(jìn)行訓(xùn)練的方法在大部分?jǐn)?shù)據(jù)集上都表現(xiàn)極佳，但是粗暴地直接取k跳子圖的方式并不能很好地發(fā)揮出封閉子圖表達(dá)力度的極限，反而可能會(huì)因?yàn)檫x取了無(wú)關(guān)或者比較邊緣的節(jié)點(diǎn)，導(dǎo)致學(xué)習(xí)封閉子圖的結(jié)構(gòu)效率變低或者效果受到噪聲干擾。另一方面，直接選取的k跳子圖規(guī)模大小會(huì)隨著不同目標(biāo)節(jié)點(diǎn)對(duì)所處位置的局部連邊稠密程度而改變。這也使得后續(xù)的圖分類(lèi)任務(wù)變得更加不規(guī)范，在全圖稠密程度差異較大的情況下，選出的封閉子圖中的節(jié)點(diǎn)數(shù)量的方差就會(huì)很大，在同一個(gè)圖分類(lèi)模型下的分類(lèi)準(zhǔn)確率就會(huì)進(jìn)一步降低。本文模型很好地解決了這幾個(gè)問(wèn)題。一方面，本文模型可以在不同背景、不同拓?fù)浣Y(jié)構(gòu)以及全圖分布差異性較大的圖數(shù)據(jù)上，更加智能地選出對(duì)于位于中心的目標(biāo)節(jié)點(diǎn)對(duì)而言，重要程度排名較高的前n個(gè)節(jié)點(diǎn)；這可以使得小圖的規(guī)模更加精準(zhǔn)統(tǒng)一，而不是隨著稠密程度和局部拓?fù)浣Y(jié)構(gòu)的不同而自由改變規(guī)模的大小；另一方面，本文模型在提取封閉子圖的過(guò)程中，使用了多個(gè)啟發(fā)式的方法，在綜合考量了全圖信息和局部信息的同時(shí)，還保留了一定的可以調(diào)節(jié)的隨機(jī)性；這使得本文的鏈接預(yù)測(cè)模型在收集封閉子圖的時(shí)候，有能力隨機(jī)地看到分布在目標(biāo)節(jié)點(diǎn)對(duì)的周?chē)窃局匾圆桓叩沫h(huán)境節(jié)點(diǎn)，從而保留了模型對(duì)于反常拓?fù)浣Y(jié)構(gòu)的一定的適應(yīng)性。

2 提出模型

本文提出了一種基于優(yōu)先值的鄰居圖提取鏈接預(yù)測(cè)算法（priority-based neighbor subgraph extraction method for link prediction，PNSEL）。與SEAL［14］不同，PNSEL能更有針對(duì)性地提取子圖，并且根據(jù)提取子圖提取時(shí)的節(jié)點(diǎn)重要性進(jìn)行編號(hào)，從而在目標(biāo)節(jié)點(diǎn)對(duì)周?chē)崛〕鲇凶銐虮磉_(dá)力的封閉子圖，然后對(duì)封閉子圖使用圖分類(lèi)算法，預(yù)測(cè)中心節(jié)點(diǎn)對(duì)之間是否存在邊相連，如圖2所示。PNSEL主要包括三個(gè)步驟：a）對(duì)全圖的邊進(jìn)行篩選保留重要性高的邊；b）對(duì)訓(xùn)練集中的每個(gè)節(jié)點(diǎn)對(duì)提取一個(gè)封閉子圖并對(duì)其中的節(jié)點(diǎn)進(jìn)行節(jié)點(diǎn)編號(hào)；c）在每一個(gè)小圖上使用圖分類(lèi)算法進(jìn)行0-1預(yù)測(cè)。

2.1 問(wèn)題定義

鏈接預(yù)測(cè)任務(wù)的目標(biāo)是，根據(jù)已知的圖結(jié)構(gòu)數(shù)據(jù)，預(yù)測(cè)圖中可能存在或者即將出現(xiàn)的其他邊。具體的數(shù)學(xué)定義如下：輸入的圖數(shù)據(jù)為G=（Euclid Math OneVAp，Euclid Math OneEAp），其中，Euclid Math OneVAp表示所有的節(jié)點(diǎn)集合，Euclid Math OneEAp表示輸入的已知邊的集合，其中εi，j∈Euclid Math OneEAp當(dāng)且僅當(dāng)vi，vj∈Euclid Math OneVAp且vi與vj在輸入圖數(shù)據(jù)中之間存在一條邊相連。測(cè)試集Euclid Math OneEAptest是由節(jié)點(diǎn)對(duì)（vi，vj）組成的集合，滿(mǎn)足vi，vj∈Euclid Math OneVAp且εi，jEuclid Math OneEAp。鏈接預(yù)測(cè)任務(wù)要解決的問(wèn)題就是，通過(guò)在G上的建模和學(xué)習(xí)，對(duì)測(cè)試集Euclid Math OneEAptest里的節(jié)點(diǎn)對(duì)之間是否存在連邊進(jìn)行預(yù)測(cè)。

2.2 邊篩選器

邊篩選器是對(duì)圖中的邊進(jìn)行篩選的模塊。在非常稠密的圖中，總邊數(shù)的數(shù)量級(jí)非常大，會(huì)導(dǎo)致封閉子圖提取步驟的計(jì)算量非常大，同時(shí)也會(huì)使封閉子圖占用很大的存儲(chǔ)空間。可以通過(guò)設(shè)置邊篩選器模塊解決這個(gè)問(wèn)題，邊篩選器模塊可以過(guò)濾掉訓(xùn)練集中的一些重要程度不高的邊，保留比較核心的邊，在保持核心拓?fù)浣Y(jié)構(gòu)不變的情況下減小計(jì)算量，提高算法的效率。具體做法如下：

對(duì)于任意的εi，jEuclid Math OneEAp，本文計(jì)算它的兩個(gè)端點(diǎn)vi、vj之間的Jaccard系數(shù)作為這個(gè)邊的優(yōu)先級(jí)，即

S（vi，vj）=|Γ（vi）∩Γ（vj）||Γ（vi）∪Γ（vj）|（1）

其中：Γ（v）表示節(jié)點(diǎn)v的一階鄰居節(jié)點(diǎn)集合。Jaccard系數(shù)越高，說(shuō)明兩節(jié)點(diǎn)之間的關(guān)聯(lián)緊密程度越大，這個(gè)邊存在的重要性就越高。本文對(duì)所有邊的Jaccard系數(shù)進(jìn)行排序，并保留［k×|Euclid Math OneEAp|］條邊作為訓(xùn)練集中輸入的鄰接矩陣，其中k∈（0，1］表示保留邊的百分比，［x］表不超過(guò)x的最大整數(shù)，新的邊集合記為Euclid Math OneEAp′。當(dāng)k=1時(shí)，保留所有的原始邊，不進(jìn)行邊篩選。

2.3 封閉子圖提取

本節(jié)中提出了一種新的封閉子圖提取方法，主要步驟如圖3所示。這種方法不僅能夠選中在目標(biāo)節(jié)點(diǎn)對(duì)周?chē)挠绊懥椭匾愿叩墓?jié)點(diǎn)，而且能夠保留一定的隨機(jī)性。隨著跳數(shù)的擴(kuò)散，被選入封閉子圖的可能性將被隨機(jī)地分配到目標(biāo)節(jié)點(diǎn)對(duì)附近的其他節(jié)點(diǎn)上。對(duì)于一個(gè)給定的目標(biāo)節(jié)點(diǎn)對(duì)（vi，vj），先從節(jié)點(diǎn)層面出發(fā)，在目標(biāo)節(jié)點(diǎn)對(duì)周?chē)x擇恰當(dāng)?shù)墓?jié)點(diǎn)集合Euclid Math OneVApi，j，從而得到封閉子圖的邊集合Euclid Math OneEApi，j={εx，y|vx，vy∈Euclid Math OneVApi，j且εx，y∈Euclid Math OneEAp′}，即端點(diǎn)均為Euclid Math OneVApi，j中的節(jié)點(diǎn)且出現(xiàn)在過(guò)濾完的全圖邊的集合Euclid Math OneEAp′中的所有邊構(gòu)成的集合，最終提取的封閉子圖就是Gi，j=（Euclid Math OneVApi，j，Euclid Math OneEApi，j）。

在節(jié)點(diǎn)集合的提取過(guò)程中，為了使提取的子圖兼具影響力和隨機(jī)性，將提取的節(jié)點(diǎn)集合分成兩個(gè)部分：核心節(jié)點(diǎn)集合Euclid Math OneVAp priori，j和隨機(jī)節(jié)點(diǎn)集合Euclid Math OneVAprandi，j。它們之間滿(mǎn)足這樣的關(guān)系，Euclid Math OneVApi，j=Euclid Math OneVAppriori，j∪Euclid Math OneVAprandi，j，Euclid Math OneVAppriori，j∩Euclid Math OneVAprandi，j=。本文使用超參數(shù)α來(lái)決定封閉子圖節(jié)點(diǎn)集合的隨機(jī)性和影響力排序的重要性大小占比，即本文使用核心節(jié)點(diǎn)提取方法提取［α×|Euclid Math OneVApi，j|］數(shù)量的點(diǎn)，使用隨機(jī)節(jié)點(diǎn)提取方法提取［（1-α）×|Euclid Math OneVApi，j|］數(shù)量的點(diǎn)，其中：

α=|Euclid Math OneVAppriori，j||Euclid Math OneVApi，j|=|Euclid Math OneVAppriori，j||Euclid Math OneVAprandi，j|+|Euclid Math OneVAppriori，j|∈［0，1］（2）

2.3.1 核心節(jié)點(diǎn)提取

核心節(jié)點(diǎn)提取部分旨在提取出相對(duì)于目標(biāo)節(jié)點(diǎn)對(duì)和全圖都具有高影響力的重要節(jié)點(diǎn)。在實(shí)際操作中，使用全局PageRank和個(gè)性化的PageRank［17］來(lái)表示節(jié)點(diǎn)的全局影響力和相對(duì)于目標(biāo)節(jié)點(diǎn)對(duì)的局部影響力。用pri，vi∈Euclid Math OneVAp表示全局PageRank，用ppryx表示以節(jié)點(diǎn)vy為出發(fā)點(diǎn)計(jì)算出來(lái)的節(jié)點(diǎn)vx的個(gè)性化的PageRank，其中vx，vy∈Euclid Math OneVAp。那么對(duì)于一個(gè)固定的目標(biāo)節(jié)點(diǎn)對(duì)（vi，vj），它們周?chē)墓?jié)點(diǎn)vx的全局影響力就用prx表示；vx的局部相對(duì)影響力用分別以?xún)蓚€(gè)目標(biāo)節(jié)點(diǎn)為核心節(jié)點(diǎn)計(jì)算出來(lái)的個(gè)性化的PageRank的最大值來(lái)計(jì)算，也就是說(shuō)節(jié)點(diǎn)vx相對(duì)于目標(biāo)節(jié)點(diǎn)對(duì)（vi，vj）的局部相對(duì)影響力大小為max（pprix，pprjx）。同時(shí)，本文用超參數(shù)β來(lái)控制局部影響力在核心節(jié)點(diǎn)排序評(píng)分中的重要性大小，也就是說(shuō)最后的周?chē)?jié)點(diǎn)優(yōu)先值計(jì)算方法如下：

pi，jx=β×max（pprix，pprjx）+（1-β）×prx vx∈Euclid Math OneVAp（3）

然后可以通過(guò)排序所有節(jié)點(diǎn)的優(yōu)先值得到優(yōu)先值最高的 n1=［α×fix_node_num］個(gè)節(jié)點(diǎn)，來(lái)得到目標(biāo)節(jié)點(diǎn)對(duì)的核心節(jié)點(diǎn)集合。

2.3.2 隨機(jī)節(jié)點(diǎn)提取

隨機(jī)節(jié)點(diǎn)提取部分旨在隨機(jī)提取出目標(biāo)節(jié)點(diǎn)對(duì)周?chē)泥従庸?jié)點(diǎn)（包括直接相鄰和間接相鄰）。在隨機(jī)節(jié)點(diǎn)提取部分，所提方法采用了類(lèi)似最小哈希算法（MinHash）［24］的思想，最小哈希算法是利用低維編碼的方式快速近似計(jì)算兩個(gè)集合的Jaccard相似性的算法。在這個(gè)模塊中，所提算法將每個(gè)篩選出來(lái)的節(jié)點(diǎn)集合視為一個(gè)編碼，分別編碼目標(biāo)節(jié)點(diǎn)對(duì)（vi，vj）的p跳鄰居：Euclid Math OneNAp pi，Euclid Math OneNAp pj，其中p=1，2，3，…，num_hops，這樣所篩選出來(lái)的節(jié)點(diǎn)就能很好地代表兩個(gè)中心節(jié)點(diǎn)的鄰居特征。

具體來(lái)說(shuō)，隨機(jī)節(jié)點(diǎn)提取模塊提取節(jié)點(diǎn)的總數(shù)量為

n2=［（1-α）×fix_node_num］（4）

先生成n2次相互獨(dú)立的全圖節(jié)點(diǎn)隨機(jī)排列的哈希函數(shù)

permk：Euclid Math OneVAp→Euclid Math TwoNAp k=1，2，…，n2（5）

A函數(shù)的輸出是0到（節(jié)點(diǎn)總數(shù)-1）上的正整數(shù)，輸入是圖中的某一個(gè)節(jié)點(diǎn)。同時(shí)構(gòu)建一個(gè)固定序號(hào)哈希函數(shù)h：Euclid Math TwoNAp→Euclid Math OneVAp，即每個(gè)序號(hào)唯一的對(duì)應(yīng)圖上的某一個(gè)節(jié)點(diǎn)。為了均勻地分配提取的隨機(jī)節(jié)點(diǎn)，本文的算法會(huì)在每一跳的鄰居上采樣

node_per_hop=［n2num_hops］（6）

個(gè)節(jié)點(diǎn)，其中［node_per_hop/2］個(gè)節(jié)點(diǎn)用來(lái)編碼vi，即對(duì)于每一個(gè)p=1，2，3，…，num_hops，本文使用

hmin（Euclid Math OneNAp p（vi））=h（minu∈Euclid Math OneNAp p（vi）permk（u））（7）

計(jì)算［node_per_hop/2］次，得到選取的節(jié)點(diǎn)集合，其中Euclid Math OneNAp p（vi）表示節(jié)點(diǎn)vi的第p跳鄰居。同樣，用剩下的［node_per_hop/2］個(gè)節(jié)點(diǎn)來(lái)編碼vj，即采樣函數(shù)為

hmin（Euclid Math OneNAp p（vj））=h（minu∈Euclid Math OneNAp p（vj）perm（u））（8）

最后，將這些選中的節(jié)點(diǎn)加入隨機(jī)節(jié)點(diǎn)提取集合Vrandi，j。

2.3.3 節(jié)點(diǎn)編號(hào)

節(jié)點(diǎn)編號(hào)部分的任務(wù)是，在已經(jīng)提取好的封閉子圖里，給每一個(gè)節(jié)點(diǎn)按照重要性賦予一個(gè)節(jié)點(diǎn)編號(hào)。為了在有節(jié)點(diǎn)特征和無(wú)節(jié)點(diǎn)特征的圖鏈接預(yù)測(cè)任務(wù)中都進(jìn)行子圖分類(lèi)訓(xùn)練，并且統(tǒng)一地在不同的封閉子圖中學(xué)到局部特征結(jié)構(gòu)來(lái)預(yù)測(cè)核心節(jié)點(diǎn)之間是否存在邊相連，需要使用相同的規(guī)則給子圖中的節(jié)點(diǎn)進(jìn)行編號(hào)。在所有的子圖進(jìn)入圖卷積神經(jīng)網(wǎng)絡(luò)中進(jìn)行圖分類(lèi)訓(xùn)練之前，給相同編號(hào)的節(jié)點(diǎn)賦予相同的節(jié)點(diǎn)特征。節(jié)點(diǎn)編號(hào)在鏈接預(yù)測(cè)中具有非常重要的意義。Zhang等人［25］最近提出了一種節(jié)點(diǎn)編號(hào)理論，該理論提出，鏈接預(yù)測(cè)任務(wù)本質(zhì)上是基于點(diǎn)集來(lái)提取信息特征進(jìn)行訓(xùn)練和預(yù)測(cè)的任務(wù)。如果僅僅關(guān)注節(jié)點(diǎn)本身的拓?fù)浣Y(jié)構(gòu)特征，那么就會(huì)陷入對(duì)稱(chēng)性的陷阱當(dāng)中。

該理論還定義了一種編號(hào)技巧（labeling trick），并證明了在使用圖卷積神經(jīng)網(wǎng)絡(luò)來(lái)訓(xùn)練節(jié)點(diǎn)特征的情況下，結(jié)合編號(hào)技巧來(lái)提取點(diǎn)集特征的方法是一種最具表達(dá)力的點(diǎn)集結(jié)構(gòu)特征提取方法。

編號(hào)技巧的定義如下：給定（S，A）作為節(jié)點(diǎn)集合和節(jié)點(diǎn)—連邊特征矩陣，如果一個(gè)編號(hào)向量L（S）∈Euclid Math TwoRApn×n×d滿(mǎn)足以下條件就可以稱(chēng)為一個(gè)編號(hào)技巧：對(duì)于任意的S，A，S′，A′，π∈Πn，均有

a）目標(biāo)節(jié)點(diǎn)標(biāo)識(shí)性。

L（S）=π（L（S′））S=π（S′）（9）

b）排列變換相等性。

S=π（S′），A=π（A′）L（S）=π（L（S′））（10）

其中：π是一個(gè)排列變換；Πn是n個(gè)元素的所有可能的排列組合。

在跳數(shù)更小節(jié)點(diǎn)區(qū)別性更高的情況下，本文提出了一種新的編號(hào)方法，即用核心節(jié)點(diǎn)提取模塊中計(jì)算的目標(biāo)節(jié)點(diǎn)周?chē)?jié)點(diǎn)優(yōu)先值排序來(lái)作為編號(hào)：最重要的節(jié)點(diǎn)即兩個(gè)目標(biāo)節(jié)點(diǎn)對(duì)，編號(hào)為1，剩下的其他節(jié)點(diǎn)按照優(yōu)先值降序依次編號(hào)為3至n=fix_node_num，而其他未被選中的所有節(jié)點(diǎn)均編號(hào)為0。下面來(lái)證明這種編號(hào)方法是一種編號(hào)技巧：

a）如果存在L（S）=π（L（S′）），即S′經(jīng)過(guò)變換過(guò)的節(jié)點(diǎn)編號(hào)與S完全相同，由于除了目標(biāo)兩節(jié)點(diǎn)對(duì)的編號(hào)為1，其他節(jié)點(diǎn)的編號(hào)均為一點(diǎn)一個(gè)編號(hào)，所以肯定可以找一種映射方式π使得S中的每個(gè)節(jié)點(diǎn)一一對(duì)應(yīng)到S′中編號(hào)相同節(jié)點(diǎn)。

b）如果S=π（S′），A=π（A′），即圖（S，A）與（S′，A′）是同構(gòu)圖，那么以節(jié)點(diǎn)vi′∈S′為出發(fā)點(diǎn)計(jì)算的個(gè)性化PageRank與以節(jié)點(diǎn)vi=π（vi′）為出發(fā)點(diǎn)計(jì)算的個(gè)性化PageRank向量必然完全相等，因而由個(gè)性化PageRank排序得到的節(jié)點(diǎn)編號(hào)必然也相等。

所以，本文證明了所提的編號(hào)方法能夠與圖卷積神經(jīng)網(wǎng)絡(luò)結(jié)合，構(gòu)造出一種最具表達(dá)力的點(diǎn)集結(jié)構(gòu)特征提取方法。

2.4 圖分類(lèi)

最后，使用圖卷積神經(jīng)網(wǎng)絡(luò)來(lái)對(duì)每個(gè)構(gòu)建好的封閉子圖進(jìn)行0-1圖分類(lèi)預(yù)測(cè)。預(yù)測(cè)為0表示目標(biāo)節(jié)點(diǎn)對(duì)之間不存在邊，預(yù)測(cè)為1表示目標(biāo)節(jié)點(diǎn)對(duì)之間存在邊。

先通過(guò)圖卷積神經(jīng)網(wǎng)絡(luò)提取子圖特征

gi，j=GNN（Euclid Math OneGApi，j）=GNN（（Euclid Math OneVApi，j，Euclid Math OneEApi，j））（11）

其中：GNN（·）表示某一種圖卷積神經(jīng)網(wǎng)絡(luò)函數(shù)。

這里主要使用的是GraphSAGE［11］模型。具體來(lái)說(shuō)，模型先初始化節(jié)點(diǎn)特征為圖數(shù)據(jù)的節(jié)點(diǎn)原生特征。

Z（0）=X（12）

然后通過(guò)聚合鄰居節(jié)點(diǎn)的特征，來(lái)逐層更新節(jié)點(diǎn)特征。

ztEuclid Math OneNAp（v）=aggregatet（{zt-1u，u∈Euclid Math OneNAp（v）}）

ztv=σ（Wt·concat（zt-1v，zt{Euclid Math OneNAp（v）））（13）

其中：t∈{1，2，…，h-1}，將兩個(gè)目標(biāo)節(jié)點(diǎn)vi，vj的節(jié)點(diǎn)特征做哈達(dá)瑪積（Hadamard product）得到子圖的圖特征向量。

gi，j=zi⊙zj

gi，j［x］=zi［x］×zj［x］（14）

然后將子圖特征通過(guò)多層感知機(jī)，得到鏈接預(yù)測(cè)值。

g（0）i，j=gi，j

g（k）i，j=ReLU（Wkg（k-1）i，j+bk） k∈{1，2，…，K-1}

yi，j=σ（WKg（K-1）i，j+bK）（15）

其中：σ（·）是sigmoid函數(shù)；yi，j即為對(duì)vi，vj的連邊情況的預(yù)測(cè)。

3 實(shí)驗(yàn)及分析

在有節(jié)點(diǎn)特征的數(shù)據(jù)集和不含節(jié)點(diǎn)特征的數(shù)據(jù)集上分別進(jìn)行了實(shí)驗(yàn)，并與幾個(gè)基線(xiàn)模型進(jìn)行了對(duì)比實(shí)驗(yàn)。下面從數(shù)據(jù)集、基線(xiàn)模型、評(píng)估指標(biāo)、與基線(xiàn)模型的對(duì)比和模型分析討論等方面對(duì)實(shí)驗(yàn)和模型進(jìn)行描述。

3.1 含節(jié)點(diǎn)特征數(shù)據(jù)集

chameleon和squirrel數(shù)據(jù)集來(lái)自維基百科數(shù)據(jù)集［26］，在這兩個(gè)數(shù)據(jù)集中每個(gè)節(jié)點(diǎn)代表一個(gè)網(wǎng)頁(yè)，而每一條邊代表兩個(gè)不同網(wǎng)頁(yè)之間的超鏈接，節(jié)點(diǎn)特征則表示網(wǎng)頁(yè)中存在的特定的代表性的名詞含量。

actor數(shù)據(jù)集［27］取自一個(gè)“電影—導(dǎo)演—演員—作家”網(wǎng)絡(luò)，數(shù)據(jù)集中的每一個(gè)節(jié)點(diǎn)表示一個(gè)演員，如果兩個(gè)演員在同一個(gè)維基百科網(wǎng)頁(yè)上同時(shí)出現(xiàn)過(guò)，那么他們會(huì)存在一條連邊，節(jié)點(diǎn)特征反映了該演員的維基百科介紹頁(yè)面上的一些關(guān)鍵詞情況。

Cornell、Texas和Wisconsin數(shù)據(jù)集［27］是卡耐基梅隆大學(xué)收集整理的不同大學(xué)計(jì)算機(jī)系的校園網(wǎng)頁(yè)數(shù)據(jù)集。每個(gè)數(shù)據(jù)集來(lái)自一個(gè)大學(xué)，數(shù)據(jù)集內(nèi)的每個(gè)節(jié)點(diǎn)表示一個(gè)網(wǎng)站，網(wǎng)頁(yè)分為學(xué)生、項(xiàng)目、課程、員工和教師這五個(gè)類(lèi)別，節(jié)點(diǎn)之間的連邊表示網(wǎng)頁(yè)之間的超鏈接，節(jié)點(diǎn)特征也是網(wǎng)頁(yè)上出現(xiàn)的關(guān)鍵詞信息。

PubMed、Cora和CiteSeer數(shù)據(jù)集是非常經(jīng)典的不同領(lǐng)域的論文引用網(wǎng)絡(luò)數(shù)據(jù)集［28，29］。在這三個(gè)數(shù)據(jù)集中，每個(gè)節(jié)點(diǎn)表示一篇論文，節(jié)點(diǎn)之間的連邊表示論文之間的互相引用關(guān)系，節(jié)點(diǎn)特征表示論文的代表詞描述信息。

這九個(gè)含節(jié)點(diǎn)特征數(shù)據(jù)集來(lái)自不同的背景，也具有不同的大小規(guī)模和平均節(jié)點(diǎn)度數(shù)，能夠很好地綜合反映PNSEL在不同結(jié)構(gòu)的數(shù)據(jù)集上的性能，具體的數(shù)據(jù)規(guī)模描述如表1所示。

3.2 無(wú)節(jié)點(diǎn)特征數(shù)據(jù)集

本文使用了八個(gè)無(wú)節(jié)點(diǎn)特征數(shù)據(jù)集，分別是美國(guó)航線(xiàn)數(shù)據(jù)集USAir、網(wǎng)絡(luò)科學(xué)研究人員的合作關(guān)系網(wǎng)絡(luò)NS［30］、美國(guó)政治博客網(wǎng)絡(luò)PB［31］、蛋白質(zhì)相互作用網(wǎng)絡(luò)Yeast［32］、秀麗隱桿線(xiàn)蟲(chóng)的生物神經(jīng)網(wǎng)絡(luò)C.elegans［33］、美國(guó)西部電網(wǎng)分布結(jié)構(gòu)Power［33］、路由器構(gòu)建的互連網(wǎng)絡(luò)圖Router［34］、大腸桿菌中代謝物的成對(duì)反應(yīng)網(wǎng)絡(luò)E.coli［35］。它們具有不同的背景、數(shù)據(jù)規(guī)模、平均度數(shù)和聚類(lèi)系數(shù)，具體數(shù)值分布如表2所示。

所有數(shù)據(jù)集均隨機(jī)選取原圖中80%的邊作為訓(xùn)練集里的可見(jiàn)邊，10%的邊作為測(cè)試集里面的正樣本，并隨機(jī)選取等數(shù)量的不存在邊相連的節(jié)點(diǎn)對(duì)作為測(cè)試集里面的負(fù)樣本，剩下的10%的邊作為驗(yàn)證集里的正樣本，也同時(shí)獨(dú)立抽取等數(shù)量的訓(xùn)練集里不存在邊相連的節(jié)點(diǎn)對(duì)作為驗(yàn)證集里的負(fù)樣本。

3.3 基線(xiàn)模型

由于所提方法是建立在“提取子圖+圖分類(lèi)”框架下的預(yù)測(cè)算法，目前采用這個(gè)框架的算法只有SEAL模型，所以SEAL是主要的對(duì)比對(duì)象。近些年來(lái)也涌現(xiàn)了一下不同思路的鏈接預(yù)測(cè)方法，考慮到算法的角度不同，這里不做對(duì)比。本文選擇的一些有代表性的模型有：

a）SEAL［14］。該模型使用目標(biāo)節(jié)點(diǎn)對(duì)周?chē)膋跳鄰居小圖，通過(guò)圖分類(lèi)進(jìn)行鏈接預(yù)測(cè)，是建立在“提取子圖+圖分類(lèi)”框架下的目前表現(xiàn)最佳的算法。

b）node2vec［6］。該模型是一種非常有效的無(wú)監(jiān)督的圖嵌入方法，通過(guò)隨機(jī)游走序列學(xué)習(xí)每個(gè)節(jié)點(diǎn)的圖嵌入表達(dá)。訓(xùn)練完成后將目標(biāo)兩節(jié)點(diǎn)特征的哈達(dá)瑪積通過(guò)線(xiàn)性層和激活層后進(jìn)行鏈接預(yù)測(cè)。

c）MLP。多層感知機(jī)模型可以使用在含有節(jié)點(diǎn)特征的圖數(shù)據(jù)中。模型讀入節(jié)點(diǎn)的原始特征，將兩節(jié)點(diǎn)的原始特征的哈達(dá)瑪積通過(guò)深度神經(jīng)網(wǎng)絡(luò)后進(jìn)行0-1預(yù)測(cè)。

d）GraphSAGE［9］。該模型是一種結(jié)合鄰居采樣和動(dòng)態(tài)更新節(jié)點(diǎn)特征的圖卷積神經(jīng)網(wǎng)絡(luò)模型。模型先在全圖進(jìn)行卷積操作更新所有節(jié)點(diǎn)的特征，再取出目標(biāo)節(jié)點(diǎn)對(duì)的特征向量進(jìn)行建模預(yù)測(cè)鏈接是否存在。

3.4 評(píng)估指標(biāo)

鏈接預(yù)測(cè)任務(wù)是一種二分類(lèi)任務(wù)，測(cè)試集由未知連邊情況的節(jié)點(diǎn)對(duì)組成，其中50%的節(jié)點(diǎn)對(duì)在原數(shù)據(jù)集上存在邊相連，但是在訓(xùn)練數(shù)據(jù)中連邊被刪去不可見(jiàn)；另外50%的節(jié)點(diǎn)對(duì)是隨機(jī)采樣取出的在原圖中本來(lái)就沒(méi)有連邊的節(jié)點(diǎn)對(duì)，所以正負(fù)樣本比例為1：1。

本文采用AUC、F1-score、precision和recall作為評(píng)價(jià)指標(biāo)，綜合的評(píng)價(jià)預(yù)測(cè)的準(zhǔn)確性。具體計(jì)算方法為

AUC=∑i∈PositiveClass ranki-M×（M+1）2M×N（16）

其中：ranki表示序號(hào)為i的樣本的預(yù)測(cè)概率在所有樣本從小到大排序后的排序序號(hào)；M、N表示是正樣本和負(fù)樣本的個(gè)數(shù)；PositiveClass表示正樣本的序號(hào)集合。

precision=TPTP+FP，recall=TPTP+FN（17）

其中：precision即精準(zhǔn)率，表示分類(lèi)器判定的正例中的正樣本比例；recall即召回率，表示正樣本中被分類(lèi)器判定為正例的比例；TP表示預(yù)測(cè)為正例的正樣本數(shù)量；FP表示預(yù)測(cè)為正例的負(fù)樣本數(shù)量；FN表示預(yù)測(cè)為負(fù)例的正樣本數(shù)量。

F1-score=2×precision×recallprecision+recall（18）

3.5 參數(shù)設(shè)置

本文在九個(gè)含節(jié)點(diǎn)特征數(shù)據(jù)集和八個(gè)不含節(jié)點(diǎn)特征的數(shù)據(jù)集上對(duì)上述的基線(xiàn)模型進(jìn)行了實(shí)驗(yàn)。對(duì)于node2vec模型，本文采用的隨機(jī)游走步長(zhǎng)為10，窗口長(zhǎng)度為5，訓(xùn)練的節(jié)點(diǎn)特征維數(shù)為128維，然后使用相同的訓(xùn)練集驗(yàn)證集測(cè)試集劃分，用node2vec得到的節(jié)點(diǎn)特征為輸入訓(xùn)練MLP分類(lèi)模型來(lái)做鏈接預(yù)測(cè)。在有節(jié)點(diǎn)特征的數(shù)據(jù)集上使用MLP方法作為一個(gè)基線(xiàn)模型，使用節(jié)點(diǎn)原生特征作為MLP模型的輸入特征向量，MLP的層數(shù)設(shè)置為三層，隱藏層的向量維數(shù)為256維。對(duì)于GraphSAGE模型，在有節(jié)點(diǎn)特征的數(shù)據(jù)集上，本文采用了兩種訓(xùn)練方式：a）初始化節(jié)點(diǎn)特征向量為節(jié)點(diǎn)原生特征，固定輸入的節(jié)點(diǎn)特征向量，這種模型記為GraphSAGE1；b）隨機(jī)初始化節(jié)點(diǎn)的特征向量，然后將特征向量當(dāng)成參數(shù)進(jìn)行訓(xùn)練，這種模型記為GraphSAGE2。在不含節(jié)點(diǎn)特征的數(shù)據(jù)集上，本文只采用了隨機(jī)初始化節(jié)點(diǎn)特征向量參數(shù)，并訓(xùn)練特征向量參數(shù)的方式，模型記作GraphSAGE。GraphSAGE的卷積層數(shù)設(shè)置為兩層，隱藏層的向量維數(shù)同樣設(shè)置為256維。對(duì)于SEAL模型，在原文中已有實(shí)驗(yàn)的數(shù)據(jù)集，本文采用與SEAL本文中相同的實(shí)驗(yàn)設(shè)置。在原文中沒(méi)有的數(shù)據(jù)集，本文使用與原文中相似數(shù)據(jù)集類(lèi)似的參數(shù)實(shí)驗(yàn)，并對(duì)主要的超參實(shí)驗(yàn)了主要可能的取值，選擇最佳結(jié)果作為實(shí)驗(yàn)最終結(jié)果。本文算法PNSEL同樣使用了256維的隱藏層維數(shù)，在計(jì)算周?chē)?jié)點(diǎn)優(yōu)先值時(shí)，局部影響力占比超參數(shù)β在［0，0.3，0.5，0.7，1］這幾個(gè)數(shù)值中進(jìn)行了實(shí)驗(yàn)。在分配核心節(jié)點(diǎn)提取比例時(shí)，核心節(jié)點(diǎn)占比超參數(shù)α在［0，0.3，0.5，0.8，1］。本文模型使用的編號(hào)方式為雙半徑編號(hào)法和優(yōu)先值排序編號(hào)法，使用的圖分類(lèi)模型為DGCNN［36］和GraphSAGE，選擇最佳結(jié)果作為實(shí)驗(yàn)的最終結(jié)果。PNSEL與SEAL均將batch size數(shù)量設(shè)置為32。上述模型均使用各數(shù)據(jù)集上最佳的學(xué)習(xí)率，訓(xùn)練的epoch數(shù)均為100，并進(jìn)行獨(dú)立實(shí)驗(yàn)10次，計(jì)算正確率的均值和方差。

3.6 與基線(xiàn)模型的對(duì)比

分別在有節(jié)點(diǎn)特征和無(wú)節(jié)點(diǎn)特征兩種情況下分析本文模型的性能。表3～8是在有節(jié)點(diǎn)特征的九個(gè)數(shù)據(jù)集上的AUC、F1-score、precision和recall的實(shí)驗(yàn)結(jié)果（precision和recall的結(jié)果為10次獨(dú)立實(shí)驗(yàn)的均值）。

GraphSAGE276.18±7.2193.09±0.0699.46±0.0178.84±3.8376.56±4.63" 如表3～8所示，對(duì)于有節(jié)點(diǎn)特征的數(shù)據(jù)，PNSEL在社交網(wǎng)絡(luò)、論文引用、生物關(guān)聯(lián)等網(wǎng)絡(luò)關(guān)系數(shù)據(jù)中與其他基線(xiàn)模型相比，都表現(xiàn)出了最佳的平均AUC和F1-score，同時(shí)，precision和recall的表現(xiàn)也非常均衡，precision和recall綜合來(lái)看的平均情況最佳，這說(shuō)明本文模型具有很好的性能。

node2vec模型在部分?jǐn)?shù)據(jù)上也有比較優(yōu)良的表現(xiàn)，說(shuō)明無(wú)監(jiān)督的圖嵌入方法也能在一定程度上提取出鏈接預(yù)測(cè)需要用到的拓?fù)湫畔ⅲ窃谄渌拇蟛糠謹(jǐn)?shù)據(jù)上則無(wú)法保持很好的效果。MLP模型在chameleon、Wisconsin、CiteSeer上表現(xiàn)也不錯(cuò)，其中Wisconsin的預(yù)測(cè)AUC比其他基線(xiàn)模型都高，說(shuō)明對(duì)于某些含節(jié)點(diǎn)特征的圖網(wǎng)絡(luò)結(jié)構(gòu)而言，節(jié)點(diǎn)的原生特征對(duì)于鏈接預(yù)測(cè)起到了首要的作用。GraphSAGE模型在使用和不使用原生特征的情況下，總的來(lái)說(shuō)模型表現(xiàn)差異不大，在大部分?jǐn)?shù)據(jù)集上均能有不錯(cuò)的效果，其中在CiteSeer和Cora上的AUC完全超過(guò)其他基線(xiàn)模型但是F1-score卻比較低，說(shuō)明圖神經(jīng)網(wǎng)絡(luò)模型對(duì)于鏈接預(yù)測(cè)來(lái)說(shuō)的表達(dá)力很強(qiáng)，但是存在正負(fù)例的預(yù)測(cè)準(zhǔn)確性不均衡的問(wèn)題。SEAL模型綜合了以上模型的優(yōu)點(diǎn)，是所有數(shù)據(jù)集上平均表現(xiàn)第二好的模型，說(shuō)明“子圖提取+圖分類(lèi)”的框架在鏈接預(yù)測(cè)問(wèn)題上具有非常好的效果，但是仍有一定的提升空間。而PNSEL在大部分的數(shù)據(jù)集上均表現(xiàn)出了顯著高于SEAL的AUC和F1-score，說(shuō)明本文的改進(jìn)是非常有效且合理的。

表9～11是在不含節(jié)點(diǎn)特征的8個(gè)數(shù)據(jù)集上的AUC、F1-score、precision和recall的實(shí)驗(yàn)結(jié)果（precision和recall的結(jié)果為10次獨(dú)立實(shí)驗(yàn)的均值）。對(duì)于不含節(jié)點(diǎn)特征的數(shù)據(jù)集，node2vec可以比較好地學(xué)到數(shù)據(jù)中的結(jié)構(gòu)信息，與GraphSAGE的表現(xiàn)不相上下，但與表現(xiàn)最佳的模型仍有一定的顯著差距。這說(shuō)明在不存在節(jié)點(diǎn)特征的情況下，這兩種模型在不同背景不同特質(zhì)的圖數(shù)據(jù)中不能穩(wěn)定預(yù)測(cè)鏈接是否存在。SEAL的表現(xiàn)明顯優(yōu)于另外兩個(gè)模型，同時(shí)PNSEL也相比SEAL有顯著的性能提升，說(shuō)明所提模型不僅在對(duì)節(jié)點(diǎn)特征利用上有更好的性能，而且在不存在節(jié)點(diǎn)特征的情況下，PNSEL也能更有效地利用子圖信息作出預(yù)測(cè)。

3.7 模型分析和討論

本節(jié)通過(guò)控制改變單一維度的參數(shù)進(jìn)行實(shí)驗(yàn)來(lái)說(shuō)明本文算法中的關(guān)鍵部分對(duì)模型的效果及作用。

3.7.1 收斂性分析

AUC是模型訓(xùn)練時(shí)的主要指示性指標(biāo)，本文通過(guò)繪制訓(xùn)練次數(shù)與正確率（AUC）變化曲線(xiàn)來(lái)觀(guān)察模型的收斂情況，如圖4所示。

本文選擇了五個(gè)有特征數(shù)據(jù)集和六個(gè)無(wú)特征數(shù)據(jù)集的訓(xùn)練情況進(jìn)行繪圖，分別用虛線(xiàn)和實(shí)線(xiàn)表示。由于正確率的量級(jí)不同，曲線(xiàn)分開(kāi)繪制在兩張圖上。從圖4可以看出，在所有的數(shù)據(jù)集上，雖然正確率的收斂速度和曲線(xiàn)形狀有所不同，但是最終正確率都收斂到了某一特定值，說(shuō)明PNSEL具有良好的收斂性。

3.7.2 核心節(jié)點(diǎn)占比參數(shù)影響

核心節(jié)點(diǎn)比重參數(shù)α表示的是在封閉子圖提取時(shí)，按節(jié)點(diǎn)優(yōu)先值提取的節(jié)點(diǎn)數(shù)量占節(jié)點(diǎn)總數(shù)的比例。本文選取了三個(gè)含節(jié)點(diǎn)特征數(shù)據(jù)集和兩個(gè)不含節(jié)點(diǎn)特征的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，在各自最佳參數(shù)的其他參數(shù)保持不變的情況下，改變?chǔ)吝M(jìn)行實(shí)驗(yàn)，獨(dú)立進(jìn)行三次實(shí)驗(yàn)取平均結(jié)果，如圖5所示。

可以看出，核心節(jié)點(diǎn)比重參數(shù)對(duì)鏈接預(yù)測(cè)任務(wù)的準(zhǔn)確性在不同的數(shù)據(jù)集上均具有明顯的影響。其中，在含節(jié)點(diǎn)特征的數(shù)據(jù)集上，不同的數(shù)據(jù)往往有著不同的最佳α選擇，過(guò)大或者過(guò)小均不能達(dá)到最佳的預(yù)測(cè)準(zhǔn)確性。這說(shuō)明這些圖結(jié)構(gòu)更適合核心節(jié)點(diǎn)抽取與隨機(jī)節(jié)點(diǎn)抽取結(jié)合的方式。

而在不含節(jié)點(diǎn)特征的數(shù)據(jù)集上，本文注意到它們的最佳水平往往出現(xiàn)在α=1時(shí)，且隨著α變大預(yù)測(cè)準(zhǔn)確性大致呈上升趨勢(shì)，說(shuō)明在這類(lèi)不含節(jié)點(diǎn)特征的數(shù)據(jù)集上，完全使用核心節(jié)點(diǎn)抽取是最佳的提取封閉子圖的方法。

3.7.3 局部影響力占比參數(shù)影響

局部影響力占比參數(shù)β表示的是在計(jì)算周?chē)?jié)點(diǎn)優(yōu)先值時(shí)，局部影響力特征所占的比重。β越大，節(jié)點(diǎn)的局部影響力在優(yōu)先值里的比重就越大，節(jié)點(diǎn)的全圖影響力在優(yōu)先值里的比重就越小。本文選取了同樣三個(gè)含節(jié)點(diǎn)特征數(shù)據(jù)集和兩個(gè)不含節(jié)點(diǎn)特征的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，在各自最佳參數(shù)的其他參數(shù)保持不變的情況下，改變?chǔ)逻M(jìn)行實(shí)驗(yàn)，獨(dú)立進(jìn)行三次實(shí)驗(yàn)取平均結(jié)果，結(jié)果如圖6所示。

可以看到，除了actor數(shù)據(jù)對(duì)于β不敏感之外，其他數(shù)據(jù)集的準(zhǔn)確性均受β的取值影響比較明顯。其中，在Wisconsin、Texas和C.elegans上，模型的正確率均隨著β的增加而增加。這說(shuō)明對(duì)于這些數(shù)據(jù)而言，考慮節(jié)點(diǎn)優(yōu)先值時(shí)僅考慮局部影響力是最佳選擇，全局影響力對(duì)于局部的節(jié)點(diǎn)預(yù)測(cè)準(zhǔn)確性意義不大。而在Power數(shù)據(jù)集上，當(dāng)β取0或者1時(shí)，模型具有最佳表現(xiàn)，說(shuō)明僅選取全圖最重要的節(jié)點(diǎn)或者僅選取局部重要的節(jié)點(diǎn)都能為鏈接預(yù)測(cè)提供足夠的有效信息，而兩者結(jié)合反而會(huì)使得篩選變得低效。

4 結(jié)束語(yǔ)

本文對(duì)鏈接預(yù)測(cè)領(lǐng)域目前表現(xiàn)最佳的模型提出了一種改進(jìn)的方案，基于“子圖提取+圖分類(lèi)”的鏈接預(yù)測(cè)結(jié)構(gòu)，提出了一種基于優(yōu)先值的鄰居子圖提取連接預(yù)測(cè)算法（PNSEL）。所提算法可以在固定小圖規(guī)模的情況下，結(jié)合局部圖結(jié)構(gòu)和全圖結(jié)構(gòu)信息，選出對(duì)于目標(biāo)節(jié)點(diǎn)對(duì)最為重要的周?chē)?jié)點(diǎn)，并保留了一定的隨機(jī)性以應(yīng)對(duì)差異化的圖結(jié)構(gòu)。通過(guò)大量在不同背景的真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)，本文將PNSEL與具有代表性的幾個(gè)基線(xiàn)模型進(jìn)行對(duì)比，證明了PNSEL相比改進(jìn)前能顯著帶來(lái)正確率的提高，同時(shí)也通過(guò)拆解實(shí)驗(yàn)證明了主要參數(shù)的影響性。

參考文獻(xiàn)：

［1］Qi Yanjun，Bar-Joseph Z，Klein-Seetharaman J.Evaluation of different biological data and computational classification methods for use in protein interaction prediction［J］.Proteins：Structure，F(xiàn)unction，and Bioinformatics，2006，63（3）：490-500.

［2］Stanfield Z，Coskun M，Koyutürk M.Drug response prediction as a link prediction problem［J］.Scientific Reports，2017，7（1）：1-13.

［3］Adamic L A，Adar E.Friends and neighbors on the Web［J］.Social Networks，2003，25（3）：211-230.

［4］王星，王碩，陳吉，等.聯(lián)合圖注意力和卷積神經(jīng)網(wǎng)絡(luò)的鏈接預(yù)測(cè)方法［J］.山西大學(xué)學(xué)報(bào)：自然科學(xué)版，2021，44（3）：462-470.（Wang Xing，Wang Shuo，Chen Ji，et al.A link prediction method by joint graph attention and convolutional neural networks［J］.Journal of Shanxi University：Natural Science Edition，2021，44（3）：462-470.）

［5］張玲玲，陳衛(wèi)靜.合作網(wǎng)絡(luò)中關(guān)鍵研發(fā)者潛在重要合作者鏈接預(yù)測(cè)［J］.情報(bào)探索，2022（3）：19-25.（ Zhang Lingling.Chen Weijing.Research on link prediction of potential important partners for key developers in the cooperation network［J］.Information Research，2022（3）：19-25.）

［6］Grover A，Leskovec J.node2vec：scalable feature learning for networks［C］//Proc of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM Press，2016：855-864.

［7］Kipf T N，Welling M.Variational graph auto-encoders［EB/OL］.（2016-11-21） .https：//arxiv.org/abs/1611.07308.

［8］郝宵榮，王莉，廉濤.基于節(jié)點(diǎn)表示和子圖結(jié)構(gòu)的動(dòng)態(tài)網(wǎng)絡(luò)鏈接預(yù)測(cè)［J］.模式識(shí)別與人工智能，2021，34（2）：117-126.（ Hao Xiao-rong，Wang Li，Lian Tao.Dynamic network link prediction based on node representation and subgraph structure［J］.Pattern Recognition and Artificial Intelligence，2021，34（2）：117-126.）

［9］Hamilton W，Ying Zhitao，Leskovec J.Inductive representation lear-ning on large graphs［C］//Advances in Neural Information Processing Systems.2017：1025-1035.

［10］Velicˇkovic＇ P，Cucurull G，Casanova A，et al.Graph attention networks［EB/OL］.（2017-10-30）.https：//arxiv.org/abs/1710.10903.

［11］Kipf T N，Welling M.Semi-supervised classification with graph convolutional networks［EB/OL］.（2016-09-09） .https：//arxiv.org/abs/1609.02907.

［12］Singh A，Huang Qian，Huang S L，et al.Edge proposal sets for link prediction［EB/OL］.（2021-06-30）.https：//arxiv.org/abs/2106.15810.

［13］Li Boning，Xia Yingce，Xie Shufang，et al.Distance-enhanced graph neural network for link prediction［EB/OL］.（2021）.https：//icml-compbio.github.io/2021/papers/WCBICML2021_paper_52.pdf.

［14］Zhang Muhan，Chen Yixin.Link prediction based on graph neural networks［C］//Advances in Neural Information Processing Systems.2018：5165-5175.

［15］Barabási A L，Albert R.Emergence of scaling in random networks［J］.Science，1999，286（5439）：509-512.

［16］Zhou Tao，Lyu Linyuan，Zhang Yicheng.Predicting missing links via local information［J］.The European Physical Journal B，2009，71（4）：623-630.

［17］Page L，Brin S，Motwani R，et al.The PageRank citation ranking：Bringing order to the Web，1999-66［R］.［S.l.］ ：Stanford InfoLab，1999.

［18］Kovács I A，Luck K，Spirohn K，et al.Network-based prediction of protein interactions［J］.Nature Communications，2019，10（1）：1-8.

［19］Katz L.A new status index derived from sociometric analysis［J］.Psychometrika，1953，18（1）：39-43.

［20］Perozzi B，Al-Rfou R，Skiena S.Deepwalk：online learning of social representations［C］//Proc of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM Press，2014：701-710.

［21］Tang Jian，Qu Meng，Wang Mingzhe，et al.Line：large-scale information network embedding［C］//Proc of the 24th International Confe-rence on World Wide Web.2015：1067-1077.

［22］Xu Keyulu，Hu Weihua，Leskovec J，et al.How powerful are graph neural networks？［EB/OL］.（2018-10-01） .https：//arxiv.org/abs/1810.00826.

［23］Leman A A，Weisfeiler B.A reduction of a graph to a canonical form and an algebra arising during this reduction［J］.Nauchno-Technicheskaya Informatsiya，1968，2（9）：12-16.

［24］Broder A Z.On the resemblance and containment of documents［C］//Proc of Compression and Complexity of Sequences.Piscataway，NJ：IEEE Press，1997：21-29.

［25］Zhang Muhan，Li Pan，Xia Yinglong，et al.Labeling trick：a theory of using graph neural networks for multi-node representation learning［C］//Advances in Neural Information Processing Systems.2021：9061-9073.

［26］Rozemberczki B，Allen C，Sarkar R.Multi-scale attributed node embedding［J］.Journal of Complex Networks，2021，9（2）：cnab014.

［27］Pei Hongbin，Wei Bingzhe，Chang K C C，et al.Geom-GCN：geometric graph convolutional networks［EB/OL］.（2020-02-13） .https：//arxiv.org/abs/2002.05287.

［28］Sen P，Namata G，Bilgic M，et al.Collective classification in network data［J］.AI Magazine，2008，29（3）：93-106.

［29］Yang Zhilin，Cohen W，Salakhudinov R.Revisiting semi-supervised learning with graph embeddings［C］//Proc of International Confe-rence on Machine Learning.2016：40-48.

［30］Newman M E J.Finding community structure in networks using the eigenvectors of matrices［J］.Physical Review E，2006，74（3）：036104.

［31］Ackland R.Mapping the US political blogosphere：are conservative bloggers more prominent？［C］//Proc of BlogTalk Downunder Conference.2005.

［32］Von Mering C，Krause R，Snel B，et al.Comparative assessment of large-scale data sets of protein-protein interactions［J］.Nature，2002，417（6887）：399-403.

［33］Watts D J，Strogatz S H.Collective dynamics of‘small-world’networks［J］.Nature，1998，393（6684）：440-442.

［34］Spring N，Mahajan R，Wetherall D.Measuring ISP topologies with Rocketfuel［J］.ACM SIGCOMM Computer Communication Review，2002，32（4）：133-145.

［35］Zhang Muhan，Cui Zhicheng，Oyetunde T，et al.Recovering metabolic networks using a novel hyperlink prediction method［EB/OL］.（2016-10-21） .https：//arxiv.org/abs/1610.06941.

［36］Zhang Muhan，Cui Zhicheng，Neumann M，et al.An end-to-end deep learning architecture for graph classification［C］//Proc of the 32nd AAAI Conference on Artificial Intelligence.2018：4438-4445.