面向不同網絡結構和應用任務的網絡表示學習研究進展

趙衛績 孫曉霞 劉井蓮 佟 良

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

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

一、問題定義

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

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

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

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

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

二、基于不同網絡結構的表示學習

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

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

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

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

三、面向應用任務的網絡表示學習

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

四、結語

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