訪問【W(wǎng)RITE-BUG數(shù)字空間】_[內(nèi)附完整源碼和文檔]

圖節(jié)點(diǎn)鄰近度用于衡量圖上節(jié)點(diǎn)相對某一給定起始節(jié)點(diǎn)的相對距離。根據(jù)圖 學(xué)習(xí)理論，鄰近度較高的節(jié)點(diǎn)普遍具有較高的相似性。以節(jié)點(diǎn)分類任務(wù)為例，由 于節(jié)點(diǎn)鄰近度的高低間接指示了圖結(jié)構(gòu)上節(jié)點(diǎn)間的相似關(guān)系，進(jìn)而包含了各節(jié)點(diǎn) 的類別信息，故而可以使用節(jié)點(diǎn)鄰近度計(jì)算結(jié)果進(jìn)行神經(jīng)網(wǎng)絡(luò)的節(jié)點(diǎn)分類訓(xùn)練。

一、背景介紹

圖，作為計(jì)算機(jī)科學(xué)領(lǐng)域中一類重要的數(shù)據(jù)結(jié)構(gòu)，提供了一種抽象表示事物 之間關(guān)系的方法。圖結(jié)構(gòu)包含兩類主要元素——“節(jié)點(diǎn)”和“邊”，其中，“節(jié)點(diǎn)”常 被用作表示各種事物，“邊”被用作表示事物之間的關(guān)系，由此抽象出現(xiàn)實(shí)世界真 實(shí)關(guān)系的表達(dá)形式，這對我們研究實(shí)際生活中復(fù)雜的關(guān)系網(wǎng)絡(luò)提供了可能。盡管 另一重要的數(shù)據(jù)結(jié)構(gòu)“樹”也含有“節(jié)點(diǎn)”和“邊”兩種元素，但是，圖結(jié)構(gòu)比樹結(jié)構(gòu) 更具靈活性。圖結(jié)構(gòu)中節(jié)點(diǎn)的平等關(guān)系和自由的連邊方式，使其可以表示出事物 之間的多種關(guān)系形式，但樹結(jié)構(gòu)的表達(dá)能力卻會因?yàn)樽陨矶x而受到限制。比如， 我們無法用樹結(jié)構(gòu)表示一個關(guān)系閉環(huán)，也很難在現(xiàn)實(shí)世界中找到一個占有絕對主 導(dǎo)地位的“根節(jié)點(diǎn)”。從這一點(diǎn)中，我們更能看出圖結(jié)構(gòu)在關(guān)系網(wǎng)絡(luò)的表達(dá)方面具 有的天然優(yōu)勢。

由于圖結(jié)構(gòu)在關(guān)系表達(dá)方面的出色特性，我們常將其應(yīng)用在多種實(shí)際場景中。 比如，在交通網(wǎng)絡(luò)中，我們常用節(jié)點(diǎn)表示城市，邊表示城市之間的道路，邊上的 權(quán)重表示道路的長短，進(jìn)而延伸出圖節(jié)點(diǎn)間的最短路徑問題等，以此提升路徑規(guī) 劃問題的效率。在論文引用網(wǎng)絡(luò)中，我們常用節(jié)點(diǎn)表示論文，邊表示論文之間的 引用關(guān)系，進(jìn)而幫助人們梳理論文體系、辨識重要論文等。在生命科學(xué)中的蛋白 質(zhì)運(yùn)輸路徑研究領(lǐng)域，我們可以用節(jié)點(diǎn)表示蛋白質(zhì)分子，用邊表示蛋白質(zhì)之間的 物質(zhì)運(yùn)輸關(guān)系，進(jìn)而幫助研究人員梳理蛋白質(zhì)的活動規(guī)律，識別具有相似功能的 蛋白質(zhì)等。在社交網(wǎng)絡(luò)中，我們常用節(jié)點(diǎn)表示用戶，用邊表示用戶之間的好友關(guān) 系，由此刻畫出用戶之間的親疏關(guān)系，進(jìn)而展開社區(qū)發(fā)現(xiàn)、相似用戶推斷、興趣 產(chǎn)品推薦等領(lǐng)域的研究等。

近年來，根據(jù)圖結(jié)構(gòu)信息和節(jié)點(diǎn)和邊上攜帶的特征信息進(jìn)行表示學(xué)習(xí)與挖掘 的問題吸引了研究者的廣泛關(guān)注，相關(guān)理論、算法和應(yīng)用系統(tǒng)相繼涌現(xiàn)，研究成 果日益豐富。但是與此同時，海量數(shù)據(jù)規(guī)模的復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)對現(xiàn)有的圖表示學(xué)習(xí) 研究帶來了艱巨的挑戰(zhàn)。為了能有效獲取屬性異質(zhì)圖數(shù)據(jù)所攜帶的結(jié)構(gòu)信息和屬 性、特征信息，在進(jìn)行屬性異質(zhì)圖的表示學(xué)習(xí)與挖掘中，現(xiàn)有研究工作普遍會在 圖信息傳播階段，將初始給定的節(jié)點(diǎn)、邊的屬性和特征信息按照圖結(jié)構(gòu)沿鄰邊進(jìn) 行聚合，進(jìn)而得到高質(zhì)量的節(jié)點(diǎn)表示向量，再將節(jié)點(diǎn)表示向量放入神經(jīng)網(wǎng)絡(luò)訓(xùn)練 框架中進(jìn)行訓(xùn)練。為了得到高質(zhì)量的圖信息傳播結(jié)果，現(xiàn)有方法大多會選擇一個 適合的圖節(jié)點(diǎn)鄰近度衡量指標(biāo)，通過計(jì)算圖節(jié)點(diǎn)鄰近度間接獲得圖信息的傳播結(jié) 果。但是，現(xiàn)有工作使用的圖節(jié)點(diǎn)鄰近度衡量指標(biāo)各不相同，缺乏通用的節(jié)點(diǎn)鄰 近度計(jì)算范式來指導(dǎo)圖信息的聚合過程，從而難以宏觀理解圖傳播過程的核心， 也不易提出通用的圖信息傳播優(yōu)化算法，以統(tǒng)一提升所有圖表示學(xué)習(xí)與挖掘過程 中的圖信息傳播效率。

二、算法概述

圖節(jié)點(diǎn)鄰近度用于衡量圖上節(jié)點(diǎn)相對某一給定起始節(jié)點(diǎn)的相對距離。根據(jù)圖 學(xué)習(xí)理論，鄰近度較高的節(jié)點(diǎn)普遍具有較高的相似性。以節(jié)點(diǎn)分類任務(wù)為例，由 于節(jié)點(diǎn)鄰近度的高低間接指示了圖結(jié)構(gòu)上節(jié)點(diǎn)間的相似關(guān)系，進(jìn)而包含了各節(jié)點(diǎn) 的類別信息，故而可以使用節(jié)點(diǎn)鄰近度計(jì)算結(jié)果進(jìn)行神經(jīng)網(wǎng)絡(luò)的節(jié)點(diǎn)分類訓(xùn)練。 目 前 常用的 屬 性 異 質(zhì) 圖節(jié)點(diǎn) 鄰 近 度衡量指標(biāo) 主要包 括 ： Personalized PageRank(PPR)、heat kernel PageRank(HKPR)、轉(zhuǎn)移概率(transition probability)、 Katz 等。由于不同的節(jié)點(diǎn)鄰近度衡量指標(biāo)可能會影響最后的預(yù)測結(jié)果，因此，目 前的研究工作普遍會根據(jù)具體的下游任務(wù)，選擇計(jì)算最合適的鄰近度衡量指標(biāo)， 以獲得圖結(jié)構(gòu)、屬性信息的集成結(jié)果。所以，設(shè)計(jì)一個通用的節(jié)點(diǎn)鄰近度計(jì)算范 式對統(tǒng)一不同的鄰近度計(jì)算步驟大有裨益。