結合圖自編碼器與聚類的半監督表示學習方法

杜航原，郝思聰，王文劍，2*

（1.山西大學計算機與信息技術學院，太原 030006；2.計算智能與中文信息處理教育部重點實驗室（山西大學），太原 030006）

0 引言

網絡是真實世界中復雜系統的一種存在形式，在日常生活中存在各種網絡，如：社交平臺中，用戶和用戶之間關系構成的社交網絡；學術網站中，論文和論文之間相互引用構成的引文網絡；國家與國家、城市與城市之間運輸交通構成的交通網絡等。這些網絡很好地表達了現實世界物體以及物體之間的聯系，分析和研究網絡數據具有廣泛的學術價值和應用價值，這使得如何從網絡數據中學習到有用的信息成為學術界的一大熱點［1］。當今世界信息飛速發展，產生的信息網絡規模龐大，數據復雜，這對網絡研究和分析提出了巨大挑戰，而網絡研究和分析的有效性，很大程度取決于網絡的表示方式。網絡表示學習，又被稱為網絡嵌入，是銜接網絡中原始數據和網絡應用任務的橋梁，其目的是將網絡信息表示為低維稠密的實數向量，從而作為特征輸入到后續的網絡任務中，如節點分類、鏈接預測和可視化等［2］。

目前已有的網絡表示學習方法從實現手段可以歸納為3 類：1）基于矩陣分解的方法。較早的網絡表示學習方法多采用矩陣分解的方式學習網絡表示，此類方法以矩陣的形式表示網絡節點之間的連接，關系矩陣一般使用鄰接矩陣或Laplace 矩陣，利用矩陣分解將高維節點表示嵌入到潛在的、低維的向量空間中，如全局結構信息圖表示學習（learning Graph Representations with global structural information，GraRep）［3］、高階鄰近性保持嵌入（High-Order Proximity preserved Embedding，HOPE）［4］、模塊化非負矩陣分解（Modularized Nonnegative Matrix Factorization，M-NMF）［5］等方法都是通過矩陣分解生成節點嵌入向量。2）基于隨機游走的方法。此類方法利用隨機游走來捕獲節點之間的結構關系。首先對網絡節點進行采樣生成隨機游走序列，然后用Skip-gram 模型對隨機游走序列中每個局部窗口內的節點對進行概率建模，最大化隨機游走序列的似然概率，并最終使用隨機梯度下降學習參數，從而學習每個節點的網絡表示。深度游走（DeepWalk）［6］和node2vec［7］利用不同的隨機游走策略捕捉全局或局部的結構信息，并利用Skip-Gram 模型來學習節點嵌入。3）基于深度學習的方法。網絡結構復雜多變，并不都是簡單的線性結構，此類方法可以提取復雜的非線性網絡結構特征，利用深度學習技術學習網絡節點表示。結構化深度網絡嵌入（Structural Deep Network Embedding，SDNE）［8］、用于學習圖表示的深度神經網絡（Deep Neural networks for Learning Graph Representations，DNGR）［9］、基于生成式對抗網的圖表示學習（Graph representation learning with Generative Adversarial Nets，GraphGAN）［10］采用深度神經網絡學習網絡嵌入，捕捉到了非線性的結構信息。

早期的研究當中人們將網絡表示學習當作一種無監督的過程，關注的是屬性和拓撲結構的保持，在現實的網絡任務中，節點標簽也是一種重要的信息，如節點分類任務當中，節點標簽與網絡結構和節點屬性有很強的相關性，這種相關性在確定每個節點的分類中起著至關重要的作用。繼而研究者開始探索如何在網絡表示學習的過程中利用標簽信息，從而產生了半監督的網絡表示學習方法，如圖卷積網絡（Graph Convolutional Network，GCN）［11］、用數據的轉導式或歸納式嵌入預測標簽和鄰居（Predicting labels and neighbors with embeddings transductively or inductively from data，Planetoid）［12］、可擴展的轉導網絡嵌入（Transductive Largescale Information Network Embedding，TLINE）［13］等，在進行網絡表示學習的同時將已有的部分節點標簽信息作為監督信息來指導網絡表示的產生，以此獲得更優的網絡表示。

基于以上問題，本文提出了一種結合圖自編碼器與聚類的半監督表示學習方法（Semi-supervised Representation Learning method combining Graph Auto-Encoder and Clustering，GAECSRL），利用網絡中的部分節點標簽來尋求更有效的網絡表示方法，主要工作包括：

1）使用圖自編碼器保持原有網絡的結構信息。首先編碼器將圖編碼為低維稠密的嵌入，再通過解碼器解碼重構原始的圖，以此保持原有的網絡結構信息；同時利用圖神經網絡強大的擬合非線性函數的能力捕獲高度非線性的網絡特征。

2）將圖自動編碼器和k-means 統一到一個框架中，形成自監督機制。用聚類分布指導網絡表示的學習，網絡表示學習目標反過來監督聚類的生成，提高網絡表示的性能。

3）利用節點的標簽信息，指導聚類結果，并增強網絡表示的可區分性。

4）在真實數據集上進行節點分類、鏈接預測，與基準方法結果進行對比分析，實驗結果驗證了所提方法的有效性。

1 相關工作

1.1 網絡表示學習

隨著信息技術的發展，信息網絡成為人們生活中不可或缺的一部分，分析這些網絡可以揭示社會生活中的各種復雜關系，如何捕獲網絡節點的特征成為網絡研究的一個重要任務。網絡表示學習的目的就是學習網絡節點的潛在、低維表示，同時保留網絡的拓撲結構、節點內容和邊等其他信息［14］。生成的網絡表示可以直接作為節點的特征輸入到機器學習任務中，如節點分類、鏈接預測等，提高網絡分析的效率。

給定一個網絡G（V，E，X），其中：V表示節點，|V|表示網絡G中節點的個數，E表示連接節點的邊，X表示節點屬性矩陣。網絡表示學習的任務就是學習網絡數據到表示向量之間的映射函數f，映射函數f保留了原始網絡信息，使得原始網絡中相似的兩個節點在網絡表示向量空間中也相似。

1.2 圖神經網絡

Sperduti 等［15］在1997 年首次將神經網絡應用于有向無環圖，激發了對有向無環圖的早期研究。圖神經網絡的概念最初由Gori 等［16］提出，并在Scarselli 等［17］和Gallicchio 等［18］的論文中進一步闡述，通過迭代傳播鄰域信息來學習目標節點的表示，直到達到一個穩定的不動點，這個計算過程非常復雜，最近研究者提出了越來越多的方法來應對這些挑戰。經過十幾年的發展，近年來圖神經網絡已成為一種應用廣泛的圖分析方法。

網絡表示學習的目的是將原始網絡信息轉化為低維向量，其本質問題是學習這個轉化過程中的映射函數。一些早期的方法，如矩陣分解、隨機游走等，假設映射函數是線性的，然而網絡的形成過程復雜，且高度非線性，因此線性函數可能不足以將原始網絡映射到嵌入空間。而圖神經網絡可以為網絡表示學習提供一個有效的非線性函數學習模型［19］，將網絡結構和屬性信息高效地融合到網絡表示學習中；同時，圖神經網絡可以提供端到端的解決方案，在具有高級信息的復雜網絡中，利用圖神經網絡模型的端到端網絡嵌入解決方案可以有效分析復雜網絡信息［20］。

1.3 圖自編碼器

Kipf 等［21］于2016 年提出了變分圖自編碼器（Variational Graph Auto-Encoder，VGAE），還提出了一種不變分的圖自編碼器，自此開始，圖自編碼器（Graph Auto-Encoder，GAE）憑借其簡潔的Encoder-Decoder 結構和高效的編碼能力，在很多領域被廣泛應用。圖自動編碼器的基本思想是：首先輸入網絡的鄰接矩陣A和節點的特征矩陣X，然后通過編碼器學習節點低維向量表示Z，再利用解碼器重構網絡。圖自編碼器由于其使用的非線性映射函數能捕捉網絡的高度非線性結構，與大多數現有的用于節點分類和鏈接預測的無監督網絡表示學習模型相比，圖自編碼器具備較強的網絡表示能力。

2 結合圖自編碼器與聚類的半監督表示學習方法

為了同時保持網絡的標簽信息、結構信息和屬性信息，本文提出了一種結合圖自編碼器與聚類的半監督表示學習方法（GAECSRL），該方法的框架如圖1 所示，該方法包括圖自編碼器模塊、自監督模塊和半監督模塊3 個部分。首先，利用圖自編碼器生成網絡表示；然后，在生成網絡表示的基礎上，將圖自動編碼器和k-means 統一到一個框架中，形成自監督機制，用聚類分布指導低維嵌入的學習，嵌入目標反過來監督聚類的生成；最后，在網絡表示學習過程中使用標簽信息來監督圖自動編碼器的訓練過程，使具有相同類別標簽的節點具有相近的低維向量表示。

圖1 結合圖自編碼器與聚類的半監督表示學習框架Fig.1 Framework of semi-supervised representation learning combining graph auto-encoder and clustering

2.1 模型結構

給定一個圖G（V，E，X）且節點個數為|V|=N，鄰接矩陣A表示節點和節點之間的連接關系，矩陣X表示節點特征。

圖自編碼器模塊 使用圖自動編碼器得到網絡的低維向量表示，將鄰接矩陣A和特征矩陣X輸入到圖自編碼器中，通過編碼器編碼可得到低維表示Z。網絡表示Z可由式（1）計算得到：

解碼器采用簡單的內積得到重構的鄰接矩陣：

圖自編碼器的主要工作就是利用圖神經網絡將網絡數據逐層降維，最終投影到一個低維潛在空間中從而達到數據降維的目的。圖自編碼器使用GCN 作為解碼器來學習潛在的網絡表示，將網絡的鄰接矩陣和特征矩陣輸入到GCN 中，GCN 每層神經網絡之間的激活函數起到了將“線性”轉化為“非線性”的作用，這使得圖自編碼器可以很好地捕捉到網絡中的非線性結構，經過GCN 中多層神經網絡的層層編碼得到最終的網絡表示；然后將學習到的網絡表示作為輸入，輸入到內積解碼器中解碼得到重構鄰接矩陣，構建損失函數，通過迭代最小化損失優化圖自編碼器，使得重構的鄰接矩陣與原始鄰接矩陣盡可能相似，從而得到最優的網絡表示。

自監督模塊 將圖自編碼器和k-means 結合起來，統一到一個框架中，有效地對兩個模塊進行端到端的訓練，使它們相互促進、相互監督，形成自監督機制。

將網絡表示輸入到k-means 中進行聚類，對于第i個樣本和第j個聚類，使用學生分布來度量數據表示zi與聚類中心向量μj之間的相似性：

其中：zi是嵌入Z的第i行，μj在預訓練圖自編碼器學習的表示上用k-means 進行初始化，qij可以看作是將樣本i分配給聚類j的概率。在得到聚類結果分布Q后，通過學習高置信賦值來優化數據表示。

目標分布P由分布Q確定：

在目標分布P中，Q的每個任務都被平方并標準化，使任務具有更高的置信度。由于目標分布P是由聚類結果分布Q定義的，所以聚類的效果影響著網絡表示的生成，而網絡表示的優劣是聚類結果可信的關鍵，在不斷迭代更新的過程中，可信度高的聚類結果使得網絡表示更優，更優的網絡表示又導致更好的聚類效果，從而達到自監督的目的，最終使學習到的網絡表示保留更多的網絡信息，與原始網絡相似度更高。

半監督模塊 GAECSRL 方法設計了一個標簽矩陣來保存網絡的類別信息，將標簽矩陣記為B=[bij]。標簽矩陣定義如下：

對于任意兩個節點vi和vj：若有同一個類別標簽，bij被賦值為1；否則，bij被賦值為0。如果不知道節點vi或節點vj的標簽信息，bij也被賦值為0。

在現實網絡中，節點通常具有監督信息，即節點類別標簽。標簽信息在許多任務中都起著積極作用，例如節點分類。然而，采用無監督的方式學習網絡表示模型，忽略了節點的類別屬性。GAECSRL 將網絡中少數的真實標簽利用起來，監督網絡表示的學習，提高了網絡表示的可區分性。

2.2 模型優化

GAECSRL 方法的最終目標函數如下：

其中：Lr、Lc和Ls分別是重構損失、聚類損失和半監督損失，超參數α＞0。

重構損失函數Lr采用交叉熵作為損失函數，直觀上來看，合適的網絡表示能使重構出來的矩陣與原始矩陣盡可能相似。損失函數采用如下的形式：

其中：y是原始鄰接矩陣A中的值（0 或1）是重構鄰接矩陣中的值（0 到1 之間）。

自監督模型的目標函數Lc如下：

通過最小化Q分布和P分布之間的KL 散度（Kullback-Leibler divergence）損失，目標分布P可以幫助圖自編碼器模塊學習到更好的聚類任務表示，監督Q的更新，又因為目標分布P是由分布Q計算出來的，而分布Q反過來監督分布P的更新，這種相互監督機制就是自監督機制。在相互促進的過程中生成的網絡表示更有利于后續任務的進行。

在潛在表示空間中，期望具有相同標簽的點之間的距離更近。半監督模型的目標Ls定義為：

半監督損失Ls代表網絡表示｛zi｝與先驗信息B的一致性，最小化半監督損失可以最小化違反約束的代價，從而能學習到符合指定約束的特征表示。如果zi和zk屬于同一類，則zi和zk在潛在空間Z中的距離較小，使來自同一類的節點更加接近。通過這種使用先驗信息以某種方式糾正不適當的網絡表示，使網絡表示的結果更優。

在訓練過程中，使用隨機梯度下降（Stochastic Gradient Descent，SGD）和反向傳播對簇中心μ和網絡表示Z進行同步更新。分布Q在訓練過程中監督目標分布P的更新。由于目標的不斷變化會阻礙學習和收斂，在每次迭代中都用Q更新P會導致自訓練過程的不穩定性，因此設置了一個迭代間隔M，每M次迭代更新一次P，以避免上述可能出現的不穩定性。

每個數據點zi的梯度計算公式為：

在空間Z中，每個簇中心μj的梯度由式（11）計算得到：

在反向傳播過程中，通過傳遞梯度L/zi來更新圖自編碼器的參數，梯度L/μj通過SGD 更新聚類中心。在達到最大迭代次數時，停止算法。

綜上所述，GAECSRL 流程如算法1 所示。

算法1 結合圖自編碼器與聚類的半監督表示學習方法。

輸入 原始網絡G，鄰接矩陣A，特征矩陣X，節點類別數K，標簽集D，最大迭代次數MaxIter，目標分布更新間隔M。

輸出 網絡表示Z。

3 實驗結果及分析

3.1 數據集

為了驗證GAECSRL 方法的有效性，選取了一些基本方法在真實數據集上通過節點分類和鏈接預測任務與該方法進行對比。

在實驗中使用了以下4 個不同規模的真實數據集：Cora、CiteSeer、PubMed、Wiki。

Cora 數據集包含2 708 份科學出版物表示的節點，分為7類。引文網絡由5 429 條表示引文關系的邊組成。每個出版物的特征由一個1 433 維向量編碼。

CiteSeer 數據集包含來自6 個類和4 732 條邊的3 312 個出版物。每條邊表示兩份出版物之間的引用關系。每個節點表示出版物，每個節點的特征用3 703 維向量表示。

PubMed 引文網絡由19 717 篇科學論文和44 338 個鏈接組成。每個出版物特征都用500 維向量描述，并分為3 類。每個節點表示一篇科學論文，每條邊表示一個引用關系。

Wiki 數據集由2 405 個文檔組成，分為19 個類，它們之間有17 981 條邊。每個節點表示一個文檔，一個節點特征向量有4 973 維。

數據集的詳細統計信息如表1 所示。

表1 數據集的統計信息Tab.1 Statistics of datasets

3.2 對比方法

實驗過程中選取了DeepWalk、node2vec、GraRep、SDNE、Planetoid 作為對比方法驗證GAECSRL 的有效性。

DeepWalk 是一種無監督的網絡嵌入方法，它分為隨機游走和生成表示向量兩個部分。首先利用隨機游走算法（Random walk）從網絡中提取一些節點序列；然后借助自然語言處理的思路將生成的節點序列看作由單詞組成的句子，所有的序列可以看作一個大的語料庫；最后利用自然語言處理工具word2vec 將每一個節點表示為一個維度為d的向量。

node2vec 是一種無監督網絡嵌入方法，它擴展了DeepWalk 的采樣策略。它結合廣度優先搜索和深度優先搜索，在圖上生成有偏置的隨機游走，保持了圖中的高階相似性，同時廣度優先搜索和深度優先搜索之間的平衡可以捕獲圖中的局部結構以及全局社區結構。

GraRep 是一種基于矩陣分解的無監督網絡嵌入方法，使用不同的損失函數來捕獲不同的k階局部關系信息，利用奇異值分解（Singular Value Decomposition，SVD）技術對每個模型進行優化，并結合從不同模型中得到的不同表示來構造每個節點的全局表示。

SDNE 是一種基于深層神經網絡的網絡表示方法。整個模型可以被分為兩個部分：一個是由Laplace 矩陣監督的建模第一級相似度的模塊，另一個是由無監督的深層自編碼器對第二級相似度關系進行建模。最終SDNE 算法將深層自編碼器的中間層作為節點的網絡表示。

Planetoid 是一種半監督的網絡表示學習方法，它擴展了隨機游走方法，在嵌入算法中利用節點標簽信息。聯合預測一個節點的鄰居節點和類別標簽，類別標簽同時取決于節點表示和已知節點標簽，從而進行半監督表示學習。

3.3 評價指標

在本節中，對數據集進行節點分類、鏈接預測，以評估提出GAECSRL 方法性能。采用Micro-F1 和Macro-F1 作為節點分類的評價指標，AUC（Area Under Curve）作為鏈接預測的評價指標。

基于二分類問題可為每一類都建立如表2 混淆矩陣，其中：真正例（True Positive，TP）表示將正類預測為正類的個數，假反例（False Negative，FN）表示將正類預測為負類的個數，假正例（False Positive，FP）表示將負類預測為正類的個數，真反例（True Negative，TN）表示將負類預測為負類的個數。

表2 混淆矩陣Tab.2 Confusion matrix

根據矩陣，可計算出第i類的精確率（Precision，P）和召回率（Recall，R），如下所示：

F1 的計算公式如下：

1）Macro-F1。

對各類別的精確率（P）和召回率（R）求平均：

再利用F1 公式計算出來的值即為Macro-F1：

2）Micro-F1。

先計算出所有類別的總的精確率P和召回率R：

再利用F1 公式計算出來的值即為Micro-F1：

3）AUC。

ROC 曲線下的面積被稱為AUC，是評估算法預測能力的一項重要指標。分別結算模型結果的“真正例率”（True Positive Rate，TPR）和“假正例率”（False Positive Rate，FPR），將TPR作為縱坐軸，FPR作為橫坐軸作圖，即可得到ROC 曲線。TPR和FPR的計算公式如下：

AUC的計算公式如下：

首先將得分從小到大排序，然后只對正樣本的序號相加，并減去正樣本之前的數，最后除以總的樣本數得到AUC。

3.4 實驗結果與分析

為了驗證方法的有效性，在4 個真實數據集上分別通過節點分類和鏈接預測任務來評估GAECSRL 和對比方法的性能。在實驗中隨機抽取一部分標記的節點，并將它們的表示作為特征進行訓練，剩下的用于測試，在訓練中將標記節點比率從10%提高到90%。使用3 個小型網絡Cora、CiteSeer和Wiki 以及1 個大型網絡PubMed 來評估所有方法的性能。節點分類任務中采用Micro-F1 和Macro-F1 作為評價指標，鏈接預測任務中采用AUC 作為評價指標。對于所有方法，分別運行每種方法10 次，節點分類任務產生的平均Micro-F1和Macro-F1 如表3 和表4，鏈接預測任務產生的平均AUC 如表5。實驗以PyTorch 為框架，網絡表示空間維度設置為10。下面對GAECSRL 和基線方法產生的實驗結果分別進行分析比較，最好的結果用粗體顯示。

表4 不同數據集上節點分類的Macro-F1值 單位：%Tab.4 Macro-F1 values of node classification on different datasets unit：%

表5 不同數據集上鏈接預測的AUC值 單位：%Tab.5 AUC values of link prediction on different datasets unit：%

從表3～5 中可以看出，隨著節點標記率的提高，GAECSRL 和基線方法在節點分類和鏈接預測中的評價指標有所提高，說明節點標簽在生成網絡表示的過程中起著重要作用，加入節點標簽，使得GAECSRL 學習到的節點表示更具有代表性，與原始網絡更接近。

表3 不同數據集上節點分類的Micro-F1值 單位：%Tab.3 Micro-F1 values of node classification on different datasets unit：%

表3 展示了在不同數據集上進行節點分類的Micro-F1值，在Cora 數據集上，GAECSRL 在標記率為50%和60%時Micro-F1 值僅次于DeepWalk，但是相差僅為0.36 和0.4 個百分點，其他情況優于基線方法；在CiteSeer 和Wiki 數據集上，GAECSRL 與基線方法相比最優；在PubMed 數據集上，標記率為20%時，GAECSRL 次于node2vec，僅比node2vec 低0.38個百分點。除此之外，GAECSRL 相較基線方法，在Cora 和Wiki 數據集上GAECSRL 提高了0.9～11.37 個百分點，在CiteSeer 和PubMed 數據集上提升了9.43～24.46 個百分點，效果較為明顯，這是由于CiteSeer 和PubMed 為兩個較大的數據集，且節點的標記率較高，使得GAECSRL 學習到的節點表示更優。

表4 展示了在不同數據集上進行節點分類的Macro-F1值，在Cora 數據集上，GAECSRL 在標記率為40%和50%時Macro-F1 值僅次于DeepWalk 和node2vec，相差分別為0.59和0.07 個百分點，其他情況優于基線方法；在CiteSeer 和Wiki 數據集上，GAECSRL 在標記率為20% 時，次于Planetoid，分別相差0.20 和2.25 個百分點；在PubMed 數據集上，GAECSRL 與基線方法相比最優。在Cora 和Wiki 數據集上，GAECSRL 相較基線方法提高了0.76～10.85 個百分點，在CiteSeer 和PubMed 數據集上提升了2.04～24.20 個百分點，效果較為明顯，同樣是由于CiteSeer 和PubMed 數據集較大、節點標記率高，獲得了更優的網絡表示。

表5 展示了在不同數據集上進行鏈接預測的AUC 值，在數據集Cora 上，GAECSRL 在標記率為50%和60%時，結果僅次于DeepWalk 和node2vec，相差0.47 和0.13 個百分點；在CiteSeer 數據集上，GAECSRL 在標記率為60% 時次于node2vec，相差0.15 個百分點；在Wiki 數據集上，GAECSRL在標記率為40%時，結果比DeepWalk 低0.92 個百分點，其他情況都是最優。在不同數據集上，與基線方法相比，GAECSRL 提升的百分點都在10 以內。

接下來研究了參數的敏感度，即參數α對節點分類性能的影響。實驗中將節點分類訓練比設置為50，α的取值范圍為（0，1），在不同數據集上隨著參數α變化，Micro-F1 和Macro-F1 值如圖2 所示，可以看出Micro-F1 和Macro-F1 值受參數影響較小，參數敏感度低，所提GAECSRL 方法具有較好的魯棒性，故在實驗中設置α=0.5。

圖2 不同數據集上α值對評價指標的影響Fig.2 Influence of α value on evaluation indexes on different datasets

4 結語

現實世界的網絡數據具有豐富伴隨信息，如標簽信息和屬性信息等，這些伴隨信息對網絡表示的生成有積極意義。所提方法將節點的標簽信息、結構信息和屬性信息加入網絡表示學習的過程中，提出了一種結合圖自編碼器與聚類的半監督表示學習方法（GAECSRL）。該方法保持了網絡的結構相似性和屬性特征，用節點標簽信息指導網絡表示學習，提高了網絡表示學習的可區分性。在真實數據集上進行節點分類和鏈接預測任務，與基準算法進行對比，實驗證明了GAECSRL 方法的有效性。

GAECSRL 方法在實驗過程中表現出了較好的性能，但是時間復雜度較高；此外，網絡中仍存在其他高級的信息，如文本信息和語義信息等，而GAECSRL 只利用了節點的標簽信息。今后的工作中，將考慮如何降低GAECSRL 的時間復雜度，同時將其他的高級信息融合到網絡表示中。