趙衛(wèi)績 孫曉霞 劉井蓮 佟 良

（綏化學(xué)院信息工程學(xué)院 黑龍江綏化 152061)

隨著Facebook，Twitter 微信，微博等在線社會(huì)媒體網(wǎng)絡(luò)的蓬勃發(fā)展，產(chǎn)生了海量的網(wǎng)絡(luò)大數(shù)據(jù)[1]。傳統(tǒng)的網(wǎng)絡(luò)分析技術(shù)是將網(wǎng)絡(luò)表示成鄰接矩陣，存在著數(shù)據(jù)稀疏性和高時(shí)間空間復(fù)雜度[2]。網(wǎng)絡(luò)表示學(xué)習(xí)，即網(wǎng)絡(luò)嵌入，就是將網(wǎng)絡(luò)中的節(jié)點(diǎn)或者邊投影到低維向量空間中，再用于后續(xù)的機(jī)器學(xué)習(xí)或者數(shù)據(jù)挖掘任務(wù)[3]，這對(duì)于對(duì)于復(fù)雜網(wǎng)絡(luò)來說是一個(gè)比較新的嘗試。近幾年，國內(nèi)外的相關(guān)研究工作及成果展示了網(wǎng)絡(luò)表示學(xué)習(xí)技術(shù)的廣闊發(fā)展前景。目前已經(jīng)成功應(yīng)用于節(jié)點(diǎn)分類、連接預(yù)測(cè)，社區(qū)發(fā)現(xiàn)等任務(wù)中。北京大學(xué)陳偉政等人和清華大學(xué)涂存超等人對(duì)近幾年的網(wǎng)絡(luò)表示學(xué)習(xí)技術(shù)與應(yīng)用成果進(jìn)行了全面的綜述分析[1，3]，為網(wǎng)絡(luò)表示學(xué)習(xí)技術(shù)研究者指引了方向。但這些綜述性文獻(xiàn)主要是針對(duì)的同構(gòu)網(wǎng)絡(luò)，基于此，在對(duì)網(wǎng)絡(luò)表示學(xué)習(xí)技術(shù)的相關(guān)文獻(xiàn)深入研究的基礎(chǔ)上，本文分別對(duì)同構(gòu)網(wǎng)絡(luò)和異質(zhì)網(wǎng)絡(luò)上的著名的表示學(xué)習(xí)技術(shù)與應(yīng)用成果進(jìn)行闡述和分析，試圖為網(wǎng)絡(luò)表示學(xué)習(xí)初學(xué)者提供一個(gè)很好的指引方向。

一、問題定義

網(wǎng)絡(luò)結(jié)構(gòu)是信息系統(tǒng)的一種重要組織形式，傳統(tǒng)網(wǎng)絡(luò)的存儲(chǔ)采用的是鄰接矩陣，但由于網(wǎng)絡(luò)中大部分節(jié)點(diǎn)間沒有連接，所以鄰接矩陣非常稀疏，不利于存儲(chǔ)計(jì)算。因此，近年來，興起了網(wǎng)絡(luò)表示學(xué)習(xí)（Network Representation Learning，NRL），也稱為網(wǎng)絡(luò)嵌入（NetworkEmbedding，NE），采用低維、稠密、實(shí)值的向量表示網(wǎng)絡(luò)中的節(jié)點(diǎn)，解決了傳統(tǒng)網(wǎng)絡(luò)存儲(chǔ)數(shù)據(jù)稀疏問題。首先，參考文獻(xiàn)[4]中的信息網(wǎng)絡(luò)和元路徑定義并進(jìn)行擴(kuò)展，給出與網(wǎng)絡(luò)表示學(xué)習(xí)相關(guān)的定義1和定義2，具體如下。

定義1 信息網(wǎng)絡(luò)[4]，信息網(wǎng)絡(luò)可以表示為一個(gè)圖G=(V，E，A，R)，其中 V 是節(jié)點(diǎn)集合；E 是節(jié)點(diǎn)間邊的集合；A 是節(jié)點(diǎn)類型；R 是邊類型。從 V 到A 存在映射 φ：V→A；從 E到R 存在映射：Ψ：E→R。當(dāng)節(jié)點(diǎn)類型|A|=1，邊類型|R|=1，|A|+|R|=2，表示是一種同構(gòu)網(wǎng)絡(luò)；當(dāng)|A|+|R|＞2，表示的是一種異質(zhì)網(wǎng)絡(luò)，其中|A|=2，|R|=1，表示的是一種最簡單的異質(zhì)網(wǎng)絡(luò)，即二分網(wǎng)絡(luò)。異質(zhì)網(wǎng)絡(luò)中一般存在多種關(guān)系或多種類型節(jié)點(diǎn)。Rk=＜Ai，Aj＞兩個(gè)類型的節(jié)點(diǎn)間通過一種類型邊連接，這里的i 和j 可以相同，也可以不同，因?yàn)橥愋凸?jié)點(diǎn)可能存在邊的情況，此外Rk中k 也可能值為多個(gè)，因?yàn)閮蓚€(gè)類型節(jié)點(diǎn)可以存在多種關(guān)系，比如學(xué)生跟老師可以是師生關(guān)系，可能還同時(shí)是父子關(guān)系。例如，DBLP 學(xué)術(shù)信息網(wǎng)絡(luò)，作者（Writer，簡寫W），論文（Paper，簡寫P），發(fā)表處（Conference or Journal，簡寫V），在這里節(jié)點(diǎn)類型A={W，P，V}，關(guān)系類型 R={R1，R2，R3，R4，R5，R6}，其中 R1，R2分別表示的是作者和文章之間的寫與被寫關(guān)系，R3，R4分別表示期刊或會(huì)議和文章之間的發(fā)表與被發(fā)表關(guān)系，R5，R6分別表示文章和文章之間的引用與被引用關(guān)系，這六種關(guān)系可以形成一個(gè)數(shù)目信息網(wǎng)絡(luò)模式。一般為了方便，作者，論文和發(fā)表處僅用三種關(guān)系來表達(dá)，分別是作者與論文是發(fā)表關(guān)系，論文與期刊或會(huì)議是出版關(guān)系，論文與論文是引用關(guān)系。

定義2 元路徑[4]，元路徑描述的是網(wǎng)絡(luò)中節(jié)點(diǎn)類型之間是如何關(guān)聯(lián)的，一條元路徑是節(jié)點(diǎn)類型與邊類型形成的交替序列，元路徑可以看成是網(wǎng)絡(luò)模式圖中的子圖。例如，在DBLP學(xué)術(shù)信息網(wǎng)絡(luò)中，WPW是一條元路徑，表示的是兩個(gè)作者共同發(fā)表一篇論文，WPVPW是一條元路徑，表示的是兩個(gè)作者在同一處發(fā)表論文。

參考文獻(xiàn)[1]中對(duì)網(wǎng)絡(luò)表示學(xué)習(xí)的定義并進(jìn)行擴(kuò)展，給出定義3，如下。

定義3 網(wǎng)絡(luò)表示學(xué)習(xí)[1]，是將網(wǎng)絡(luò)中的節(jié)點(diǎn)學(xué)習(xí)低維稠密的向量表示，網(wǎng)絡(luò)表示學(xué)習(xí)的任務(wù)是對(duì)每個(gè)節(jié)點(diǎn)v 學(xué)習(xí)一個(gè)低緯的實(shí)數(shù)向量，Rv∈Rd，其中，d＜＜|V|，|V|是網(wǎng)絡(luò)中的節(jié)點(diǎn)總個(gè)數(shù)。網(wǎng)絡(luò)中的節(jié)點(diǎn)V，映射函數(shù)f：V→R(|V|*d。對(duì)于異質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)，由于節(jié)點(diǎn)相似度與異質(zhì)網(wǎng)絡(luò)中元路徑相關(guān)，因此除了學(xué)習(xí)節(jié)點(diǎn)的低緯實(shí)數(shù)向量，同時(shí)還要學(xué)習(xí)關(guān)系的低緯實(shí)數(shù)向量。在大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)中，節(jié)點(diǎn)之間的鏈接關(guān)系可能會(huì)非常復(fù)雜，通過在低維向量空間中進(jìn)行分析，可以很直觀地觀察節(jié)點(diǎn)之間的關(guān)系。

二、基于不同網(wǎng)絡(luò)結(jié)構(gòu)的表示學(xué)習(xí)

近年來，網(wǎng)絡(luò)表示學(xué)習(xí)，成為了復(fù)雜網(wǎng)絡(luò)分析中的一個(gè)新興研究熱點(diǎn)，網(wǎng)絡(luò)表示學(xué)習(xí)是銜接網(wǎng)絡(luò)原始結(jié)構(gòu)和網(wǎng)絡(luò)應(yīng)用任務(wù)的橋梁，網(wǎng)絡(luò)表示學(xué)習(xí)算法是將網(wǎng)絡(luò)信息轉(zhuǎn)化為低維稠密實(shí)數(shù)向量，用作機(jī)器學(xué)習(xí)算法的輸入[3]。

（一）同構(gòu)網(wǎng)絡(luò)表示學(xué)習(xí)。隨著著名的網(wǎng)絡(luò)表示學(xué)習(xí)算法word2vec在圖像處理、自然語言處理上的成功應(yīng)用，掀起了基于表示學(xué)習(xí)的研究熱潮[5]。出現(xiàn)了著名的網(wǎng)絡(luò)表示學(xué)習(xí)典型算法 DeepWalk 算法，Line 算法，Node2vec 算法。2014年，Perozzi等人提出了著名的基于深度學(xué)習(xí)技術(shù)的Deepwalk算法[6]，實(shí)現(xiàn)了從詞序列到圖上的一個(gè)擴(kuò)展，通過在圖上進(jìn)行隨機(jī)游走獲取網(wǎng)絡(luò)的局部結(jié)構(gòu)，采用SkipGram 的方法進(jìn)行網(wǎng)絡(luò)中節(jié)點(diǎn)的表示學(xué)習(xí)，使用隨機(jī)梯度下降的方法來優(yōu)化參數(shù)。Deepwalk算法的隨機(jī)游走是隨機(jī)游走隨機(jī)均勻地選取網(wǎng)絡(luò)節(jié)點(diǎn)，并生成固定長度的隨機(jī)游走序列，將此序列類比為自然語言中的句子，然后應(yīng)用skip-gram 模型學(xué)習(xí)節(jié)點(diǎn)的分布式表示。2015年，清華大學(xué)唐建等人提出一種適用于大規(guī)模的有向帶權(quán)圖的LINE算法[7]，通過節(jié)點(diǎn)對(duì)的一級(jí)接近度和二級(jí)接近度進(jìn)行概率建模，來刻畫節(jié)點(diǎn)間關(guān)系，參數(shù)學(xué)習(xí)同樣由梯度下降算法決定。在LINE算法里，一階接近度是指如果網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)之間存在邊，那么它們之間的一階接近度是這條邊的權(quán)重，沒有邊相連則接近度等于0。二階接近度是指如果網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)有鄰居節(jié)點(diǎn)，那么它們之間的二階接近度是它們鄰居集合的相似度，沒有共同好友則接近度等于0，文獻(xiàn)[7]在實(shí)驗(yàn)中證明了LINE算法在節(jié)點(diǎn)標(biāo)簽預(yù)測(cè)任務(wù)上要優(yōu)于Deepwalk 算法。2016年，Grover 等人對(duì)Deepwalk 算法進(jìn)行改進(jìn)，提出了著名的Node2Vec[8]，主要的創(chuàng)新點(diǎn)在于改進(jìn)了隨機(jī)游走的策略，定義了兩個(gè)參數(shù)p和q，在BFS和DFS中達(dá)到一個(gè)平衡，同時(shí)考慮到局部和宏觀的信息，并且具有很高的適應(yīng)性。也是采用SkipGram 的方法進(jìn)行網(wǎng)絡(luò)中節(jié)點(diǎn)的表示學(xué)習(xí)。

Deepwalk算法，相當(dāng)于Node2vec算法的一種特例，就是最平凡情況下的讓其隨機(jī)游走。LINE算法本質(zhì)上相當(dāng)于一個(gè)限制的BFS，只不過它只找一階和二階鄰居節(jié)點(diǎn)，不探尋到更遠(yuǎn)的節(jié)點(diǎn)。Node2Vec采用BFS能夠探究圖中的結(jié)構(gòu)性質(zhì)，而DFS則能夠探究出內(nèi)容上的相似性（相鄰節(jié)點(diǎn)之間的相似性）。其中結(jié)構(gòu)相似性不一定要相連接，甚至可能相距很遠(yuǎn)。

（二）異質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)。當(dāng)前已經(jīng)的網(wǎng)絡(luò)表示學(xué)習(xí)技術(shù)大多是針對(duì)同構(gòu)網(wǎng)絡(luò)，已有的幾篇網(wǎng)絡(luò)表示學(xué)習(xí)綜述性論文主要探討的也都是同構(gòu)網(wǎng)絡(luò)表示學(xué)習(xí)。不同于以往網(wǎng)絡(luò)表示學(xué)習(xí)綜述文獻(xiàn)，本文對(duì)異質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)研究進(jìn)展也進(jìn)行了探討。2016年，著名數(shù)據(jù)挖掘大師韓家煒課題組Shang等人提出一篇用于相似搜索的異質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)的Esim算法[9]，ESim 模型考慮了節(jié)點(diǎn)間的不同關(guān)系，但是該模型缺點(diǎn)是過于依賴人為定義的元路徑以及每條元路徑人為設(shè)置的權(quán)重。2017年，F(xiàn)u等人提出著名的HIN2Vec算法[10]，這是在國際會(huì)議CIKM2017上的一項(xiàng)重要工作，HIN2Vec 模型通過研究節(jié)點(diǎn)之間不同關(guān)系類型和網(wǎng)絡(luò)結(jié)構(gòu)，學(xué)習(xí)異質(zhì)信息網(wǎng)絡(luò)中豐富的信息。相比之前的一些模型，HIN2Vec模型保留了更多的上下文信息，不僅假設(shè)存在關(guān)系的兩個(gè)節(jié)點(diǎn)是相關(guān)的，而且還區(qū)分節(jié)點(diǎn)之間的不同關(guān)系。主要貢獻(xiàn)是：判斷節(jié)點(diǎn)對(duì)間關(guān)系，將一個(gè)多分類問題轉(zhuǎn)化為二分類。HIN2Vec模型分為兩部分：基于隨機(jī)游走的數(shù)據(jù)生成部分和表示學(xué)習(xí)部分。數(shù)據(jù)生成部分，基于隨機(jī)游走和負(fù)采樣生成符合目標(biāo)關(guān)系的數(shù)據(jù)，以用于表示學(xué)習(xí)。表示學(xué)習(xí)部分是一個(gè)神經(jīng)網(wǎng)絡(luò)模型，通過最大化預(yù)測(cè)節(jié)點(diǎn)之間關(guān)系的可能性，同時(shí)學(xué)習(xí)節(jié)點(diǎn)和關(guān)系的表示向量。這種多任務(wù)學(xué)習(xí)方法能夠把不同關(guān)系的豐富信息和整體網(wǎng)絡(luò)結(jié)構(gòu)聯(lián)合嵌入到節(jié)點(diǎn)向量中。該文論文考慮到了節(jié)點(diǎn)和關(guān)系的語義是不同的，對(duì)關(guān)系向量運(yùn)用了一個(gè)正則函數(shù)，對(duì)于隨機(jī)游走過程中可能會(huì)出現(xiàn)循環(huán)節(jié)點(diǎn)的問題，論文也給出了解決方法并進(jìn)行了實(shí)驗(yàn)分析，同時(shí)闡述了負(fù)采樣時(shí)候節(jié)點(diǎn)及節(jié)點(diǎn)類型的選擇，該論文有一定的創(chuàng)新。論文的不足之處在于隨機(jī)游走過程中如何消除循環(huán)，沒有給出較為詳細(xì)的解釋說明。2017年，Swami等人提出了對(duì)異質(zhì)網(wǎng)絡(luò)的表示學(xué)習(xí)算法 metapath2vec 和metapath2vec++[11]，這是Swami 等人的國際重要會(huì)議KDD2017 的一項(xiàng)重要工作。Swami 等人是通過元路徑來指導(dǎo)隨機(jī)游走的鄰居節(jié)點(diǎn)的選擇，本質(zhì)上是一種帶偏置的隨機(jī)游走，由元路徑來指導(dǎo)隨機(jī)游走的跳轉(zhuǎn)，如果下一節(jié)點(diǎn)的類型滿足元路徑中的類型，那么跳轉(zhuǎn)的概率就是該類型節(jié)點(diǎn)數(shù)分之一（等概率跳轉(zhuǎn)），否則，全部為0，然后基于異質(zhì)的skipgram 模型進(jìn)行節(jié)點(diǎn)表示學(xué)習(xí)。其中metapath 算法和DeepWalk、node2vec 算法基本類似，只是處理的網(wǎng)絡(luò)不同，分別對(duì)應(yīng)同質(zhì)網(wǎng)絡(luò)和異質(zhì)網(wǎng)絡(luò)，但是其本質(zhì)似乎都是通過隨機(jī)游走選擇鄰居節(jié)點(diǎn)，然后用skip-garm 模型學(xué)習(xí)節(jié)點(diǎn)的表示，不同的是隨機(jī)游走的過程中，鄰居節(jié)點(diǎn)的跳轉(zhuǎn)選擇策略是不同的，metapath2vec++用不同類型節(jié)點(diǎn)的特征表示進(jìn)行歸一化，對(duì)每種類型節(jié)點(diǎn)指定不同的一組多項(xiàng)式分布，相當(dāng)于在輸出層根據(jù)節(jié)點(diǎn)類型，把異質(zhì)網(wǎng)絡(luò)分解成不同的同質(zhì)網(wǎng)絡(luò)。

三、面向應(yīng)用任務(wù)的網(wǎng)絡(luò)表示學(xué)習(xí)

文獻(xiàn)[3]對(duì)面向鏈接預(yù)測(cè)和節(jié)點(diǎn)分類的應(yīng)用任務(wù)給予詳盡的介紹。在這里不再重復(fù)，社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)中一個(gè)重要特征，社區(qū)發(fā)現(xiàn)問題是一種對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行無監(jiān)督的聚類。近幾年，國內(nèi)外學(xué)者對(duì)社區(qū)發(fā)現(xiàn)問題進(jìn)行深入研究，但基于網(wǎng)絡(luò)表示學(xué)習(xí)技術(shù)的社區(qū)發(fā)現(xiàn)具有較少的研究。2013年，Yang 等人給出一種基于非負(fù)矩陣分解方法重疊社區(qū)發(fā)現(xiàn)算法BIGCLAM[12]，BIGCLAM 是為每個(gè)網(wǎng)絡(luò)中的節(jié)點(diǎn)學(xué)習(xí)了一個(gè)上述的k維非負(fù)向量表示，最大化目標(biāo)是整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)的最大似然概率。最優(yōu)化求解參數(shù)的過程也是由隨機(jī)梯度下降算法實(shí)現(xiàn)。2016年，天津大學(xué)何東曉等人把基于深度學(xué)習(xí)技術(shù)的網(wǎng)絡(luò)表示學(xué)習(xí)應(yīng)用到社區(qū)發(fā)現(xiàn)研究中[13]，實(shí)驗(yàn)結(jié)果表明，相比較一些經(jīng)典的社區(qū)發(fā)現(xiàn)算法，具有較好的效果。以上網(wǎng)絡(luò)表示學(xué)習(xí)算法中隨機(jī)游走僅僅是基于節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，沒有考慮到網(wǎng)絡(luò)中社區(qū)信息。2018年，Keikha等人提出一種新穎的CARE 算法[14]，首先利用getphi 識(shí)別出網(wǎng)絡(luò)中的全局社區(qū)結(jié)構(gòu)，然后在起始節(jié)點(diǎn)的鄰居或所在社區(qū)內(nèi)進(jìn)行隨機(jī)游走。采用SkipGram的方法進(jìn)行網(wǎng)絡(luò)中節(jié)點(diǎn)的表示學(xué)習(xí)。該算法應(yīng)用在多標(biāo)簽分類和鏈接預(yù)測(cè)中具有較好的性能。

四、結(jié)語

近幾年，國內(nèi)外學(xué)者在網(wǎng)絡(luò)表示學(xué)習(xí)研究上做了大量工作，斯坦福大學(xué)Jure Leskovec，新加坡大學(xué)的hongyan cai，清華大學(xué)唐建、涂存超課題組等人，涂，存超等人分別在同構(gòu)異質(zhì)網(wǎng)絡(luò)表示做了大量工作，取得了很大進(jìn)展，并對(duì)之前的網(wǎng)絡(luò)表示學(xué)習(xí)工作進(jìn)行過系統(tǒng)的前面的介紹和總結(jié)，https：//github.com/thunlp/NRLPapers。清華大學(xué)劉知遠(yuǎn)課題組就知識(shí)表示學(xué)習(xí)研究進(jìn)展也進(jìn)行全面的介紹和系統(tǒng)的總結(jié)。在深入研究網(wǎng)絡(luò)表示學(xué)習(xí)算法和綜述性文獻(xiàn)的基礎(chǔ)上，本文對(duì)近幾年的網(wǎng)絡(luò)表示學(xué)習(xí)技術(shù)和面向社區(qū)發(fā)現(xiàn)任務(wù)的表示學(xué)習(xí)研究進(jìn)行了全面介紹和分析，對(duì)以往表示學(xué)習(xí)綜述文獻(xiàn)是一個(gè)很好的補(bǔ)充，為網(wǎng)絡(luò)表示學(xué)習(xí)初學(xué)者起到一定的指導(dǎo)作用。未來研究方向：融合異質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)與社區(qū)發(fā)現(xiàn)的研究，動(dòng)態(tài)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)研究。