面向不同網(wǎng)絡結(jié)構(gòu)和應用任務的網(wǎng)絡表示學習研究進展

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

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

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

一、問題定義

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

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

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

參考文獻[1]中對網(wǎng)絡表示學習的定義并進行擴展，給出定義3，如下。

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

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

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

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

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

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

三、面向應用任務的網(wǎng)絡表示學習

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

四、結(jié)語

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