層次標簽引導的屬性網絡嵌入

陳 潔，陳嘉琳，趙 姝+，張燕平

1.安徽大學 計算智能與信號處理教育部重點實驗室，合肥 230601

2.安徽大學 計算機科學與技術學院，合肥 230601

網絡嵌入（network embedding，NE）是一種旨在學習網絡節點的低維向量表示的方法，使其保留網絡的重要性質，如反映節點間相似性的網絡結構、節點屬性等，所得向量表示可用以解決基于圖的各種下游任務，如分類[1]、聚類、鏈路預測和個性化推薦[2]等。通過網絡嵌入將異質信息投影到同一個低維空間，能夠更好地捕捉到網絡中復雜的結構和豐富的語義信息，具有重要意義。

近年來，研究者們提出各種網絡嵌入方法，學習圖的結構或節點之間的鄰接關系，將所有節點映射為等維度的向量，學習網絡中節點的低維表示。實際上，除結構信息，網絡節點上的屬性信息，如文本、標簽、得分等，也是網絡嵌入需保留的重要信息。目前網絡嵌入主要可以分為三類：第一類網絡嵌入只考慮網絡的結構信息；第二類網絡嵌入不但考慮網絡的結構信息，還考慮網絡節點的屬性信息；第三類屬于有監督學習，在網絡嵌入時，引入標簽的監督作用，綜合考慮網絡的結構信息、節點的屬性信息以及標簽信息。

現實中，許多網絡節點不僅具有標簽信息，而且標簽具有豐富的層次結構，圖1 列出了ACM 計算分類體系（computing classification system，CCS）中的部分層次化標簽。一篇論文分配標簽時，首先被分配到葉子節點，然后可以使用從頂層標簽到葉子標簽的路徑中涉及的所有標簽進行分層標記。由圖1 可知，一篇關于機器翻譯（machine translation）的論文和一篇關于信息提取（information extraction）的論文具有兩個不同的標簽，這兩個標簽位于分類樹的第四層（根節點為第0 層）。但從第三層次來看，這兩類論文是相似的，因為它們都屬于自然語言處理（natural language processing，NLP）這個共同的父節點。由此可以看出，不同層次的標簽揭示不同粒度的相似性。層次標簽以最簡潔的方式展示了數據不同粒度的特征，通過層次結構展示了多視角下的分類結果[3-4]。

Fig.1 Part of ACM computing classification system圖1 部分ACM 計算分類體系

然而，現有基于標簽的屬性網絡嵌入方法大都未曾考慮標簽信息的層次性，只使用單一粒度層面的標簽信息。因此，如何引入分層標簽信息進行監督學習，指導網絡嵌入是本文研究的要點。本文將從以下兩方面進行研究：首先研究如何利用層次標簽信息指導屬性網絡嵌入，生成多層次嵌入結果；再研究如何基于不同層次標簽之間的關聯關系進行嵌入向量的融合。

通過對上述兩個問題的研究，本文提出一種新的網絡嵌入框架，基于層次標簽的屬性網絡嵌入框架（hierarchical labels guided attributed network embedding framework，HLANE）。該框架在多個標簽層次上進行網絡嵌入，充分考慮層次標簽之間的關聯關系，獲得不同層次下的節點向量表示。本文的主要貢獻包括：

（1）針對現有網絡嵌入方法未考慮標簽的層次性這一問題，提出基于層次標簽的屬性網絡嵌入框架。利用標簽的層次信息，指導屬性網絡嵌入，獲得更有效的節點向量表示。

（2）提出基于層次標簽的屬性網絡嵌入框架HLANE，利用節點層次標簽指導網絡嵌入，學習有效的節點嵌入表示。通過構建層次注意力層，基于屬性信息建立層次標簽之間的關聯關系。

（3）實驗結果表明了HLANE 框架的有效性。HLANE 框架有效提高了基準網絡嵌入算法在分類任務上的性能。

1 相關工作

本章從基于結構的網絡嵌入、屬性網絡嵌入和基于標簽的屬性網絡嵌入三方面介紹網絡嵌入的相關研究現狀，其中基于結構的網絡嵌入是指網絡嵌入時僅考慮網絡的結構信息；屬性網絡嵌入指網絡嵌入時考慮網絡的結構信息和節點的屬性信息；基于標簽的屬性網絡嵌入指網絡嵌入時綜合考慮網絡的結構信息、屬性信息以及標簽信息。

1.1 基于結構的網絡嵌入方法

基于結構的網絡嵌入方法只考慮網絡的結構信息，忽略節點屬性。這類網絡嵌入的常用算法有Deep-Walk[5]、Node2Vec[6]、LINE（large-scale information network embedding）[7]、NetMF（network embedding as matrix factorization）[8]和NECS（network embedding with community structural information）[9]等。Deep-Walk、Node2Vec 和LINE 這三種算法均基于隨機游走或邊緣采樣獲取節點的鄰域信息生成向量，該類方法首先利用Skip-gram[10]進行節點嵌入，然后通過矩陣分解近似求解；NetMF 是一個統一的矩陣因式分解框架，從理論上理解和改進了DeepWalk 和LINE；NECS 算法通過發現網絡中的社區結構保留節點間的高階近似性，從而學習節點的向量表示。這些方法以低維向量表示節點，保留原有的網絡結構信息。

1.2 屬性網絡嵌入方法

屬性網絡的嵌入要求生成的節點向量不僅包含網絡拓撲結構信息，還要保持節點屬性信息。目前常見的算法有TADW（text-associated DeepWalk）[11]、ANRL（attributed network representation learning）[12]、STNE（self-translation network embedding）[13]、CAN（co-embedding model for attributed networks）[14]和DANE（deep attributed network embedding）[15]等。TADW 算法通過矩陣分解將節點的文本特征融入到網絡表征學習中，實現對屬性網絡的嵌入；ANRL 算法使用鄰居增強自編碼器對節點屬性信息進行建模，并使用Skip-gram 模型捕獲網絡結構；STNE 模型將節點屬性和網絡結構信息融合，通過LSTM（long short-term memory）網絡學習節點的高階鄰近性；CAN 方法在同一語義空間中同時實現屬性和節點的網絡嵌入，從而有效度量屬性和節點之間的相似性；DANE 算法首先獲取網絡結構和節點屬性的多階相似性，通過融合多階相似性構建屬性網絡的矩陣表示。此外，研究者們還對異構信息網絡的表示學習進行探索，用以求解異構網絡問題[16]。HERec（heterogeneous information network based recommendation）[17]算法基于元路徑的隨機游走構造節點序列，再分別學習同構序列的向量表示，最后根據具體任務學習融合方法，獲得統一的網絡嵌入；GATNE（general attributed multiplex heterogeneous network embedding）[18]模型實現了多重異構網絡的表示學習。上述方法有效地融合節點屬性信息和網絡的結構信息，實現屬性網絡的節點向量表示。

1.3 基于標簽的網絡嵌入方法

基于標簽的網絡嵌入方法利用現有的標簽信息來指導網絡嵌入。該類常規方法屬于有監督學習，在網絡嵌入中引入標簽的監督作用。如TriDNR（triparty deep network representation）[19]獲取了網絡中結構信息、屬性信息和標簽這三種信息，利用Skip-gram模型實現三者的信息融合；LANE（label informed attributed network embedding）[20]將屬性網絡及其相關標簽映射到一個統一的向量空間中，保持它們之間的相關性。

基于圖神經網絡的方法是監督或半監督的，其利用標簽信息學習節點向量表示。GCN（graph convolutional networks）[21]使用卷積將鄰居節點的特征表示融合到自身的特征表示中；GraphSAGE（graph sample and aggregate）[22]方法同時利用節點屬性信息和結構信息得到映射函數，可擴展性更強；H-GCN（hierarchical graph convolutional networks）[23]首先對結構相似的節點進行聚合形成超點，構造粗粒度圖，然后細化回原圖，還原每個節點的表示；GWNN（graph wavelet neural network）[24]利用圖小波變換克服傅里葉變換的不足，同時圖小波變換不需要進行運算開銷很大的矩陣特征分解，有良好的可解釋性。上述方法均可用以帶標簽的屬性網絡的嵌入，同時兼顧結構、屬性和標簽信息，然而這些方法都忽略了標簽的層次性，沒有考慮具有層次標簽的網絡的多層次特征。

2 問題定義

下面給出本文所提問題定義及使用的符號定義。設G=(V,E,X)為屬性網絡，其中V表示|V|個節點集合，E為|E|條邊的集合。X∈R|V|×q是包含所有節點屬性信息的矩陣，其中q表示屬性的個數，xv∈R1×q表示節點v相關的屬性向量。

定義1（網絡嵌入[5]）給定網絡G=(V,E)，通過學習得到映射函數f:G→Z∈R|V|×d，可以將網絡中每個節點v∈V表示為一個低維向量zv，其中d?|V|。映射函數f有效保留網絡的重要屬性。

定義2（層次標簽）層次標簽是一種樹型結構，可定義為T=(T(0),T(1),…,T(|T|))，其中T(|T|)表示第|T|層的節點的標簽，T(0)表示樹的根。

例如，在圖1 中，T(0)={CCS（計算分類體系）}，T(2)={Discrete Mathematics（離散數學），Information Theory（信息理論），AI（人工智能），Machine Learning（機器學習）}。

問題定義基于層次標簽的屬性網絡嵌入給定一個網絡及其層次標簽(G,T)，通過學習獲得映射函數f:(G,T)→H∈R|V|×d，將網絡中每個節點v∈V表示為低維向量hv，所得節點表示向量hv即為基于層次標簽的屬性網絡嵌入。

3 算法描述

本文提出了一種基于層次標簽的屬性網絡嵌入（HLANE)框架。圖2 給出了HLANE 框架的具體架構，由三層網絡構成：初始化層、標簽-屬性注意力層和分層嵌入層。

3.1 初始化層

對于給定的屬性網絡G=(V,E,X)，層次標簽T，初始化層用以初始化網絡嵌入Z∈R|V|×d：

這里的嵌入函數Nembed(?)可以是目前流行的任一嵌入方法，如基于結構的圖嵌入方法DeepWalk 等或者屬性網絡的圖嵌入方法STNE 等。

層次標簽樹T的編碼可以表示為L=(L(1),L(2),…,L(|T|))，其中L(t)表示以s(t)為長度編碼的第t層的層次標簽。層次標簽通常采用onehot編碼、標簽路徑或其他編碼方法進行編碼。

3.2 標簽-屬性注意力層

標簽-屬性注意力層利用層次標簽指導屬性網絡嵌入，對初始網絡嵌入Z進行更新，根據不同層次標簽生成一系列屬性網絡嵌入H(1),H(2),…,H(|T|)。每個層次的屬性網絡嵌入包含對應層次的標簽信息和節點屬性信息。

由于層次標簽樹有|T|層，該層有|T|個標簽-屬性注意力單元（label-attribute attention，LA-Att)，通過學習各層標簽與節點屬性之間的權重，實現層次標簽之間的信息融合與傳遞。為了表示節點的每個標簽和每個屬性之間的重要性，使用注意力機制來獲取標簽-屬性權重矩陣，第t層節點v的注意力權重矩陣為：

Fig.2 Framework of proposed HLANE圖2 HLANE 算法框架

其中，第t-1 層標簽j是第t層的標簽i的父節點，*表示哈達瑪積。層次標簽樹的第1 層中，標簽沒有父標簽信息，第1 層的注意力權重A(1)=A′(1)。

通過對父標簽權重的繼承，可以有效實現層次標簽間的信息融合。每個LA-Att 單元的標簽-屬性權重將統一進行標準化。

其中，avg(?)是第t層上標簽的平均值函數。

如圖2 所示的第1 層節點，使用初始網絡嵌入Z來指導生成這一層的嵌入:

最后，使用全連接層來保持H(t)的有效特征，并將每一層維度降為d維。

標簽-屬性注意力層著力于將層次標簽信息和屬性信息集成到初始網絡嵌入中，并考慮層次間關聯關系。以此實現基于層次標簽的屬性網絡嵌入方法。

3.3 分層嵌入層

通過多層標簽-屬性注意力單元LA-Att，可獲得每層的標簽-屬性網絡嵌入向量，分別對應于每一層的標簽。分層嵌入層采用混合生成方法來生成最終的嵌入結果，并捕獲整個層次標簽樹的信息。首先對于層次嵌入結果H(1),H(2),…,H(|T|)，將學習到的嵌入向量連接為特定語義的嵌入：

為了保留有效的特征，H′由全連接層降為d維：

采用σ激活函數生成網絡的最終嵌入：

由此，HLANE 將節點屬性、網絡結構和層次標簽信息保存在一個統一的框架中。節點向量的初始嵌入在每一層中不斷更新，每層嵌入均繼承父標簽的信息。

下面給出HLANE 框架的具體算法：

算法1HLANE

下面對HLANE 算法進行時間復雜度分析。對于第t層中每個節點v，注意力權重矩陣計算階段（第5 行）的時間復雜度為O(|T(t)|×q)，標簽-屬性向量生成階段（第6～7 行）的時間復雜度為O(|V|×|T(t)|×q2)，層次嵌入生成階段（第9～13 行）的時間復雜度為O(|V|×d)。最終嵌入向量生成階段（第15～16 行）的時間復雜度為O(d2)+O(|V|×d)。因此，算法HLANE在最差情況下，時間復雜度為其中|T|為層次數，|T(t)|為第t層標簽數，|V|為節點數，q為特征數，d為向量維度。

4 實驗分析

下面給出節點分類任務上的對比實驗結果及分析，驗證HLANE處理節點分類的有效性，其中節點分類任務是現有網絡嵌入方法評估中常用的下游任務。

4.1 數據集

本文共使用四個公用數據集：Cora、Citeseer、Paper和Patent。

（1）Cora[25]是一個包含2 708 篇機器學習論文的引文網絡，分為7 個研究領域。引文網絡共5 278 條邊，表示論文（節點）之間的引文關系。每篇論文均包含標題和摘要內容。該數據集只有單層標簽信息，實驗完成單標簽分類任務。

（2）Citeseer[25]是一個引文網絡數據集。它包含6個研究領域的3 312 篇研究論文，含有4 660 條邊。每篇論文均包含標題和摘要內容。該數據集只有單層標簽信息，實驗也是完成單標簽分類任務。

（3）Paper數據集是由ACM 數字圖書館提供的由計算機科學論文組成的數據集（https://libraries.acm.org/）。每篇論文至少有一個標簽，這些標簽均是CCS分類樹中的節點，每個節點的標簽層次不固定。提取1980—2017 年的論文數據中標簽層次|T|為2，3，4的所有論文。數據集共提取了28 450 篇論文，每篇論文有10 條語義鏈接邊。每篇論文均有標題和摘要內容。該數據集標簽具有層次性，實驗完成多標簽分類任務。

（4）Patent 數據集是一個由USPTO 提供的專利數據集（https://www.uspto.gov/patent）。每個專利至少被標記為一個合作專利分類方案（cooperative patent classification，CPC）號，CPC 分類是一種具有樹狀結構的分類方案。由于CPC 分類樹葉子節點過多，選取CPC 號前3 層，即|T|=3 作為層次標簽。首先提取2016—2018 年的專利數據，隨后從第二層的每個標簽下包含的專利中隨機抽取20%數據組成本文實驗數據集Patent。Patent 數據集包括112 065 項授權的美國專利，使用專利的標題和摘要作為屬性。與Paper 數據集類似，Patent 數據集中每篇專利有10 條語義鏈接邊。該數據集上的實驗完成多標簽分類任務。

數據集具體信息如表1、表2 所示。表2 給出具有層次標簽的數據集Paper 和Patent 每個層次標簽的詳細信息。

Table 1 Information statistics of datasets表1 數據集信息統計

Table 2 Statistics of each layer information of datasets表2 數據集單層信息統計

4.2 對比算法

為了證明HLANE 框架的有效性，本文選取的對比算法分為以下三組：

（1）基于結構的網絡嵌入方法。這類對比算法只考慮網絡的結構信息，忽略節點屬性和標簽。如DeepWalk 和Node2Vec 算法，采用隨機游走生成節點序列，然后將節點序列輸入Skip-gram 模型學習潛在的節點表示。

（2）屬性網絡嵌入方法。這類方法的主要目的是保持原有網絡拓撲結構和節點屬性的相似性。如CAN 算法將屬性和節點映射到相同的語義空間，學習節點的低維向量表示，從而有效度量節點之間的相似性；DANE 算法關注于網絡拓撲結構和節點屬性的高度非線性關系；STNE 算法通過序列模型融合了結構和屬性信息；ANRL算法對節點屬性信息建模，提出基于屬性增強的Skip-gram模型獲取網絡結構表示。

（3）標簽監督的屬性網絡嵌入方法。這類方法利用單層的標簽信息進行網絡嵌入。對于具有層次標簽信息的Paper 和Patent 數據集，這類方法忽略標簽的層次關系。如LANE 算法將屬性網絡及其相關標簽映射到一個統一的嵌入空間中，以保持標簽、屬性和網絡結構的相關性；H-GCN 算法是利用半監督節點分類的深度層次圖卷積網絡。

本文將上述三類方法學習所得的嵌入向量應用于節點分類任務，從而對各類方法的有效性進行評價。在獲得節點表示后，均使用邏輯回歸分類器測試性能。所得實驗結果均重復五次，取平均結果。除了H-GCN 算法，所有的對比算法在Cora、Citeseer和Paper 數據集中設定維數d=128，Patent 數據集中設定維數d=256。對于需要進行Random walk[26]的算法，游走節點數和步長設為10。實驗選取數據集的80%用于訓練，20%用于測試，所有的對比算法均使用原論文提供的源代碼實現，并進行了尋優。表3所列HLANE 框架結果是在初始化層使用one-hot 方法對分層標簽進行編碼的結果。

4.3 實驗結果

本節共設置了兩組實驗來證明HLANE 框架的有效性。在這兩組實驗中，Paper 和Patent 數據集使用多個標簽，包含了從葉子標簽到根節點路徑上的每一層標簽，進行多標簽預測。表3 給出了所有算法實驗結果的Micro-F1 指標。

從表3 可以看出，本文提出的HLANE 框架在所列方法中性能最好。H-GCN 算法在Paper 和Patent數據集上出現損失爆炸，因此并未列出對應實驗結果，其原因可能是由于數據的層次結構和標簽類別過多造成。HLANE 框架利用標簽-屬性注意力單元LA-Att 建立了標簽和屬性之間的關聯，從而提高了分類性能，即使在沒有層次標簽的Cora 和Citeseer 數據集上，與對比算法相比，HLANE 框架仍然取得更好的分類效果。此外，HLANE_flat模型是HLANE 模型的變體，其屏蔽了標簽-屬性的注意力權重在層級間的傳遞，以驗證不同層次標簽間信息傳遞對于該模型的影響。對比HLANE 和HLANE_flat 模型的實驗結果可以發現，在具有層次標簽的Paper 和Patent數據集上HLANE 框架的性能明顯更優，這是由于HLANE 將父標簽的信息傳遞給子標簽，實現了層級間信息的關聯，在嵌入時充分考慮了標簽的層次性。

Table 3 Micro-F1 performance of node classification表3 節點分類的Micro-F1 指標結果

表4 展示了HLANE 框架對現有網絡嵌入方法DeepWalk、Node2Vec、CAN、DANE、STNE 和ANRL的增強效果。從表4 可以看出，不同基本嵌入方法下HLANE 框架在不同數據集上均提升了性能指標。表4 第一列中的DeepWalk、Node2Vec、CAN、DANE、STNE 和ANRL 算法是指不使用HLANE 框架的原算法；HLANE（DW）、HLANE（NV）、HLANE（CAN）、HLANE（DANE）、HLANE（STNE）和HLANE（ANRL）算法是指使用括號內的不同嵌入方法進行初始化的HLANE 框架算法。表4 給出了不同嵌入方法初始化的HLANE 框架實驗結果，并在括號內標明相比原始算法改進的百分比。可以看出，對于未考慮節點屬性信息的方法（DeepWalk、Node2Vec），在Cora 和Citeseer數據集上應用HLANE 框架得到顯著提升，這正說明在網絡嵌入中考慮節點屬性信息能得到更優的節點嵌入。對比屬性網絡嵌入方法（CAN、DANE 等），HLANE 框架使用層次標簽進行網絡嵌入，使得學習到的節點嵌入具有更強的識別性。

Table 4 Effect enhancement of different network embedding after applying HLANE framework表4 采用HLANE 框架的不同嵌入方法性能提升

4.4 分層效果分析

為了更好分析層次標簽的嵌入效果，HLANE 框架在Paper 和Patent 數據集上為每一層標簽生成層次嵌入結果，并使用每層嵌入結果進行多標簽分類，所得Micro-F1 結果如圖3 所示。在Paper 數據集的第3層和第4 層進行實驗時，部分數據的標簽層級不足則不列入測試集，只考察具有該層標簽的測試數據的正確率。從圖3 可以看出，HLANE 框架在所有標簽層上的表現均優于其他對比算法。從表2 中可以看出，標簽的數量隨著層級變深而迅速增加；相應地，圖3 中的Micro-F1 指標值也隨著層級變深有下降的趨勢。

Fig.3 Hierarchical classification results圖3 分層分類結果

即使分類結果在葉子標簽層級上不夠理想，也不影響下一個（或更高)層次對有效信息的利用和正確預測。為了更好體現標簽層級的重要性，圖3 所示實驗中給出了HLANE 框架的變型HLANE_flat 算法進行對比。HLANE_flat 算法把不同層次的標簽都看作單層的標簽，然后進行實驗。如圖3 所示，HLANE框架比HLANE_flat 算法效果更好，這充分說明了HLANE 框架嵌入時考慮標簽層次性，繼承父標簽的信息，所得節點向量表示質量更佳。

5 結束語

本文研究基于層次標簽的屬性網絡嵌入，提出基于層次標簽的屬性網絡嵌入框架HLANE。該框架充分考慮了標簽的層次信息，建立了層次標簽層之間的關聯關系，將父標簽信息繼承到子標簽中。再設計標簽-屬性注意力單元（LA-Att)來學習每個屬性對每個標簽的重要性，進一步加強標簽、屬性以及結構之間的聯系，生成基于層次標簽的屬性網絡嵌入結果。在四個真實數據集上的實驗結果表明，HLANE 框架可以有效提高基本網絡嵌入方法的嵌入質量。