結(jié)合圖自編碼器與聚類的半監(jiān)督表示學(xué)習(xí)方法

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

（1.山西大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，太原 030006；2.計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室（山西大學(xué)），太原 030006）

0 引言

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

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

早期的研究當(dāng)中人們將網(wǎng)絡(luò)表示學(xué)習(xí)當(dāng)作一種無監(jiān)督的過程，關(guān)注的是屬性和拓?fù)浣Y(jié)構(gòu)的保持，在現(xiàn)實(shí)的網(wǎng)絡(luò)任務(wù)中，節(jié)點(diǎn)標(biāo)簽也是一種重要的信息，如節(jié)點(diǎn)分類任務(wù)當(dāng)中，節(jié)點(diǎn)標(biāo)簽與網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)屬性有很強(qiáng)的相關(guān)性，這種相關(guān)性在確定每個(gè)節(jié)點(diǎn)的分類中起著至關(guān)重要的作用。繼而研究者開始探索如何在網(wǎng)絡(luò)表示學(xué)習(xí)的過程中利用標(biāo)簽信息，從而產(chǎn)生了半監(jiān)督的網(wǎng)絡(luò)表示學(xué)習(xí)方法，如圖卷積網(wǎng)絡(luò)（Graph Convolutional Network，GCN）［11］、用數(shù)據(jù)的轉(zhuǎn)導(dǎo)式或歸納式嵌入預(yù)測標(biāo)簽和鄰居（Predicting labels and neighbors with embeddings transductively or inductively from data，Planetoid）［12］、可擴(kuò)展的轉(zhuǎn)導(dǎo)網(wǎng)絡(luò)嵌入（Transductive Largescale Information Network Embedding，TLINE）［13］等，在進(jìn)行網(wǎng)絡(luò)表示學(xué)習(xí)的同時(shí)將已有的部分節(jié)點(diǎn)標(biāo)簽信息作為監(jiān)督信息來指導(dǎo)網(wǎng)絡(luò)表示的產(chǎn)生，以此獲得更優(yōu)的網(wǎng)絡(luò)表示。

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

1）使用圖自編碼器保持原有網(wǎng)絡(luò)的結(jié)構(gòu)信息。首先編碼器將圖編碼為低維稠密的嵌入，再通過解碼器解碼重構(gòu)原始的圖，以此保持原有的網(wǎng)絡(luò)結(jié)構(gòu)信息；同時(shí)利用圖神經(jīng)網(wǎng)絡(luò)強(qiáng)大的擬合非線性函數(shù)的能力捕獲高度非線性的網(wǎng)絡(luò)特征。

2）將圖自動(dòng)編碼器和k-means 統(tǒng)一到一個(gè)框架中，形成自監(jiān)督機(jī)制。用聚類分布指導(dǎo)網(wǎng)絡(luò)表示的學(xué)習(xí)，網(wǎng)絡(luò)表示學(xué)習(xí)目標(biāo)反過來監(jiān)督聚類的生成，提高網(wǎng)絡(luò)表示的性能。

3）利用節(jié)點(diǎn)的標(biāo)簽信息，指導(dǎo)聚類結(jié)果，并增強(qiáng)網(wǎng)絡(luò)表示的可區(qū)分性。

4）在真實(shí)數(shù)據(jù)集上進(jìn)行節(jié)點(diǎn)分類、鏈接預(yù)測，與基準(zhǔn)方法結(jié)果進(jìn)行對(duì)比分析，實(shí)驗(yàn)結(jié)果驗(yàn)證了所提方法的有效性。

1 相關(guān)工作

1.1 網(wǎng)絡(luò)表示學(xué)習(xí)

隨著信息技術(shù)的發(fā)展，信息網(wǎng)絡(luò)成為人們生活中不可或缺的一部分，分析這些網(wǎng)絡(luò)可以揭示社會(huì)生活中的各種復(fù)雜關(guān)系，如何捕獲網(wǎng)絡(luò)節(jié)點(diǎn)的特征成為網(wǎng)絡(luò)研究的一個(gè)重要任務(wù)。網(wǎng)絡(luò)表示學(xué)習(xí)的目的就是學(xué)習(xí)網(wǎng)絡(luò)節(jié)點(diǎn)的潛在、低維表示，同時(shí)保留網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、節(jié)點(diǎn)內(nèi)容和邊等其他信息［14］。生成的網(wǎng)絡(luò)表示可以直接作為節(jié)點(diǎn)的特征輸入到機(jī)器學(xué)習(xí)任務(wù)中，如節(jié)點(diǎn)分類、鏈接預(yù)測等，提高網(wǎng)絡(luò)分析的效率。

給定一個(gè)網(wǎng)絡(luò)G（V，E，X），其中：V表示節(jié)點(diǎn)，|V|表示網(wǎng)絡(luò)G中節(jié)點(diǎn)的個(gè)數(shù)，E表示連接節(jié)點(diǎn)的邊，X表示節(jié)點(diǎn)屬性矩陣。網(wǎng)絡(luò)表示學(xué)習(xí)的任務(wù)就是學(xué)習(xí)網(wǎng)絡(luò)數(shù)據(jù)到表示向量之間的映射函數(shù)f，映射函數(shù)f保留了原始網(wǎng)絡(luò)信息，使得原始網(wǎng)絡(luò)中相似的兩個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)表示向量空間中也相似。

1.2 圖神經(jīng)網(wǎng)絡(luò)

Sperduti 等［15］在1997 年首次將神經(jīng)網(wǎng)絡(luò)應(yīng)用于有向無環(huán)圖，激發(fā)了對(duì)有向無環(huán)圖的早期研究。圖神經(jīng)網(wǎng)絡(luò)的概念最初由Gori 等［16］提出，并在Scarselli 等［17］和Gallicchio 等［18］的論文中進(jìn)一步闡述，通過迭代傳播鄰域信息來學(xué)習(xí)目標(biāo)節(jié)點(diǎn)的表示，直到達(dá)到一個(gè)穩(wěn)定的不動(dòng)點(diǎn)，這個(gè)計(jì)算過程非常復(fù)雜，最近研究者提出了越來越多的方法來應(yīng)對(duì)這些挑戰(zhàn)。經(jīng)過十幾年的發(fā)展，近年來圖神經(jīng)網(wǎng)絡(luò)已成為一種應(yīng)用廣泛的圖分析方法。

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

1.3 圖自編碼器

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

2 結(jié)合圖自編碼器與聚類的半監(jiān)督表示學(xué)習(xí)方法

為了同時(shí)保持網(wǎng)絡(luò)的標(biāo)簽信息、結(jié)構(gòu)信息和屬性信息，本文提出了一種結(jié)合圖自編碼器與聚類的半監(jiān)督表示學(xué)習(xí)方法（GAECSRL），該方法的框架如圖1 所示，該方法包括圖自編碼器模塊、自監(jiān)督模塊和半監(jiān)督模塊3 個(gè)部分。首先，利用圖自編碼器生成網(wǎng)絡(luò)表示；然后，在生成網(wǎng)絡(luò)表示的基礎(chǔ)上，將圖自動(dòng)編碼器和k-means 統(tǒng)一到一個(gè)框架中，形成自監(jiān)督機(jī)制，用聚類分布指導(dǎo)低維嵌入的學(xué)習(xí)，嵌入目標(biāo)反過來監(jiān)督聚類的生成；最后，在網(wǎng)絡(luò)表示學(xué)習(xí)過程中使用標(biāo)簽信息來監(jiān)督圖自動(dòng)編碼器的訓(xùn)練過程，使具有相同類別標(biāo)簽的節(jié)點(diǎn)具有相近的低維向量表示。

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

2.1 模型結(jié)構(gòu)

給定一個(gè)圖G（V，E，X）且節(jié)點(diǎn)個(gè)數(shù)為|V|=N，鄰接矩陣A表示節(jié)點(diǎn)和節(jié)點(diǎn)之間的連接關(guān)系，矩陣X表示節(jié)點(diǎn)特征。

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

解碼器采用簡單的內(nèi)積得到重構(gòu)的鄰接矩陣：

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

自監(jiān)督模塊 將圖自編碼器和k-means 結(jié)合起來，統(tǒng)一到一個(gè)框架中，有效地對(duì)兩個(gè)模塊進(jìn)行端到端的訓(xùn)練，使它們相互促進(jìn)、相互監(jiān)督，形成自監(jiān)督機(jī)制。

將網(wǎng)絡(luò)表示輸入到k-means 中進(jìn)行聚類，對(duì)于第i個(gè)樣本和第j個(gè)聚類，使用學(xué)生分布來度量數(shù)據(jù)表示zi與聚類中心向量μj之間的相似性：

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

目標(biāo)分布P由分布Q確定：

在目標(biāo)分布P中，Q的每個(gè)任務(wù)都被平方并標(biāo)準(zhǔn)化，使任務(wù)具有更高的置信度。由于目標(biāo)分布P是由聚類結(jié)果分布Q定義的，所以聚類的效果影響著網(wǎng)絡(luò)表示的生成，而網(wǎng)絡(luò)表示的優(yōu)劣是聚類結(jié)果可信的關(guān)鍵，在不斷迭代更新的過程中，可信度高的聚類結(jié)果使得網(wǎng)絡(luò)表示更優(yōu)，更優(yōu)的網(wǎng)絡(luò)表示又導(dǎo)致更好的聚類效果，從而達(dá)到自監(jiān)督的目的，最終使學(xué)習(xí)到的網(wǎng)絡(luò)表示保留更多的網(wǎng)絡(luò)信息，與原始網(wǎng)絡(luò)相似度更高。

半監(jiān)督模塊 GAECSRL 方法設(shè)計(jì)了一個(gè)標(biāo)簽矩陣來保存網(wǎng)絡(luò)的類別信息，將標(biāo)簽矩陣記為B=[bij]。標(biāo)簽矩陣定義如下：

對(duì)于任意兩個(gè)節(jié)點(diǎn)vi和vj：若有同一個(gè)類別標(biāo)簽，bij被賦值為1；否則，bij被賦值為0。如果不知道節(jié)點(diǎn)vi或節(jié)點(diǎn)vj的標(biāo)簽信息，bij也被賦值為0。

在現(xiàn)實(shí)網(wǎng)絡(luò)中，節(jié)點(diǎn)通常具有監(jiān)督信息，即節(jié)點(diǎn)類別標(biāo)簽。標(biāo)簽信息在許多任務(wù)中都起著積極作用，例如節(jié)點(diǎn)分類。然而，采用無監(jiān)督的方式學(xué)習(xí)網(wǎng)絡(luò)表示模型，忽略了節(jié)點(diǎn)的類別屬性。GAECSRL 將網(wǎng)絡(luò)中少數(shù)的真實(shí)標(biāo)簽利用起來，監(jiān)督網(wǎng)絡(luò)表示的學(xué)習(xí)，提高了網(wǎng)絡(luò)表示的可區(qū)分性。

2.2 模型優(yōu)化

GAECSRL 方法的最終目標(biāo)函數(shù)如下：

其中：Lr、Lc和Ls分別是重構(gòu)損失、聚類損失和半監(jiān)督損失，超參數(shù)α＞0。

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

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

自監(jiān)督模型的目標(biāo)函數(shù)Lc如下：

通過最小化Q分布和P分布之間的KL 散度（Kullback-Leibler divergence）損失，目標(biāo)分布P可以幫助圖自編碼器模塊學(xué)習(xí)到更好的聚類任務(wù)表示，監(jiān)督Q的更新，又因?yàn)槟繕?biāo)分布P是由分布Q計(jì)算出來的，而分布Q反過來監(jiān)督分布P的更新，這種相互監(jiān)督機(jī)制就是自監(jiān)督機(jī)制。在相互促進(jìn)的過程中生成的網(wǎng)絡(luò)表示更有利于后續(xù)任務(wù)的進(jìn)行。

在潛在表示空間中，期望具有相同標(biāo)簽的點(diǎn)之間的距離更近。半監(jiān)督模型的目標(biāo)Ls定義為：

半監(jiān)督損失Ls代表網(wǎng)絡(luò)表示｛zi｝與先驗(yàn)信息B的一致性，最小化半監(jiān)督損失可以最小化違反約束的代價(jià)，從而能學(xué)習(xí)到符合指定約束的特征表示。如果zi和zk屬于同一類，則zi和zk在潛在空間Z中的距離較小，使來自同一類的節(jié)點(diǎn)更加接近。通過這種使用先驗(yàn)信息以某種方式糾正不適當(dāng)?shù)木W(wǎng)絡(luò)表示，使網(wǎng)絡(luò)表示的結(jié)果更優(yōu)。

在訓(xùn)練過程中，使用隨機(jī)梯度下降（Stochastic Gradient Descent，SGD）和反向傳播對(duì)簇中心μ和網(wǎng)絡(luò)表示Z進(jìn)行同步更新。分布Q在訓(xùn)練過程中監(jiān)督目標(biāo)分布P的更新。由于目標(biāo)的不斷變化會(huì)阻礙學(xué)習(xí)和收斂，在每次迭代中都用Q更新P會(huì)導(dǎo)致自訓(xùn)練過程的不穩(wěn)定性，因此設(shè)置了一個(gè)迭代間隔M，每M次迭代更新一次P，以避免上述可能出現(xiàn)的不穩(wěn)定性。

每個(gè)數(shù)據(jù)點(diǎn)zi的梯度計(jì)算公式為：

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

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

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

算法1 結(jié)合圖自編碼器與聚類的半監(jiān)督表示學(xué)習(xí)方法。

輸入 原始網(wǎng)絡(luò)G，鄰接矩陣A，特征矩陣X，節(jié)點(diǎn)類別數(shù)K，標(biāo)簽集D，最大迭代次數(shù)MaxIter，目標(biāo)分布更新間隔M。

輸出 網(wǎng)絡(luò)表示Z。

3 實(shí)驗(yàn)結(jié)果及分析

3.1 數(shù)據(jù)集

為了驗(yàn)證GAECSRL 方法的有效性，選取了一些基本方法在真實(shí)數(shù)據(jù)集上通過節(jié)點(diǎn)分類和鏈接預(yù)測任務(wù)與該方法進(jìn)行對(duì)比。

在實(shí)驗(yàn)中使用了以下4 個(gè)不同規(guī)模的真實(shí)數(shù)據(jù)集：Cora、CiteSeer、PubMed、Wiki。

Cora 數(shù)據(jù)集包含2 708 份科學(xué)出版物表示的節(jié)點(diǎn)，分為7類。引文網(wǎng)絡(luò)由5 429 條表示引文關(guān)系的邊組成。每個(gè)出版物的特征由一個(gè)1 433 維向量編碼。

CiteSeer 數(shù)據(jù)集包含來自6 個(gè)類和4 732 條邊的3 312 個(gè)出版物。每條邊表示兩份出版物之間的引用關(guān)系。每個(gè)節(jié)點(diǎn)表示出版物，每個(gè)節(jié)點(diǎn)的特征用3 703 維向量表示。

PubMed 引文網(wǎng)絡(luò)由19 717 篇科學(xué)論文和44 338 個(gè)鏈接組成。每個(gè)出版物特征都用500 維向量描述，并分為3 類。每個(gè)節(jié)點(diǎn)表示一篇科學(xué)論文，每條邊表示一個(gè)引用關(guān)系。

Wiki 數(shù)據(jù)集由2 405 個(gè)文檔組成，分為19 個(gè)類，它們之間有17 981 條邊。每個(gè)節(jié)點(diǎn)表示一個(gè)文檔，一個(gè)節(jié)點(diǎn)特征向量有4 973 維。

數(shù)據(jù)集的詳細(xì)統(tǒng)計(jì)信息如表1 所示。

表1 數(shù)據(jù)集的統(tǒng)計(jì)信息Tab.1 Statistics of datasets

3.2 對(duì)比方法

實(shí)驗(yàn)過程中選取了DeepWalk、node2vec、GraRep、SDNE、Planetoid 作為對(duì)比方法驗(yàn)證GAECSRL 的有效性。

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

node2vec 是一種無監(jiān)督網(wǎng)絡(luò)嵌入方法，它擴(kuò)展了DeepWalk 的采樣策略。它結(jié)合廣度優(yōu)先搜索和深度優(yōu)先搜索，在圖上生成有偏置的隨機(jī)游走，保持了圖中的高階相似性，同時(shí)廣度優(yōu)先搜索和深度優(yōu)先搜索之間的平衡可以捕獲圖中的局部結(jié)構(gòu)以及全局社區(qū)結(jié)構(gòu)。

GraRep 是一種基于矩陣分解的無監(jiān)督網(wǎng)絡(luò)嵌入方法，使用不同的損失函數(shù)來捕獲不同的k階局部關(guān)系信息，利用奇異值分解（Singular Value Decomposition，SVD）技術(shù)對(duì)每個(gè)模型進(jìn)行優(yōu)化，并結(jié)合從不同模型中得到的不同表示來構(gòu)造每個(gè)節(jié)點(diǎn)的全局表示。

SDNE 是一種基于深層神經(jīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)表示方法。整個(gè)模型可以被分為兩個(gè)部分：一個(gè)是由Laplace 矩陣監(jiān)督的建模第一級(jí)相似度的模塊，另一個(gè)是由無監(jiān)督的深層自編碼器對(duì)第二級(jí)相似度關(guān)系進(jìn)行建模。最終SDNE 算法將深層自編碼器的中間層作為節(jié)點(diǎn)的網(wǎng)絡(luò)表示。

Planetoid 是一種半監(jiān)督的網(wǎng)絡(luò)表示學(xué)習(xí)方法，它擴(kuò)展了隨機(jī)游走方法，在嵌入算法中利用節(jié)點(diǎn)標(biāo)簽信息。聯(lián)合預(yù)測一個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)和類別標(biāo)簽，類別標(biāo)簽同時(shí)取決于節(jié)點(diǎn)表示和已知節(jié)點(diǎn)標(biāo)簽，從而進(jìn)行半監(jiān)督表示學(xué)習(xí)。

3.3 評(píng)價(jià)指標(biāo)

在本節(jié)中，對(duì)數(shù)據(jù)集進(jìn)行節(jié)點(diǎn)分類、鏈接預(yù)測，以評(píng)估提出GAECSRL 方法性能。采用Micro-F1 和Macro-F1 作為節(jié)點(diǎn)分類的評(píng)價(jià)指標(biāo)，AUC（Area Under Curve）作為鏈接預(yù)測的評(píng)價(jià)指標(biāo)。

基于二分類問題可為每一類都建立如表2 混淆矩陣，其中：真正例（True Positive，TP）表示將正類預(yù)測為正類的個(gè)數(shù)，假反例（False Negative，F(xiàn)N）表示將正類預(yù)測為負(fù)類的個(gè)數(shù)，假正例（False Positive，F(xiàn)P）表示將負(fù)類預(yù)測為正類的個(gè)數(shù)，真反例（True Negative，TN）表示將負(fù)類預(yù)測為負(fù)類的個(gè)數(shù)。

表2 混淆矩陣Tab.2 Confusion matrix

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

F1 的計(jì)算公式如下：

1）Macro-F1。

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

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

2）Micro-F1。

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

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

3）AUC。

ROC 曲線下的面積被稱為AUC，是評(píng)估算法預(yù)測能力的一項(xiàng)重要指標(biāo)。分別結(jié)算模型結(jié)果的“真正例率”（True Positive Rate，TPR）和“假正例率”（False Positive Rate，F(xiàn)PR），將TPR作為縱坐軸，F(xiàn)PR作為橫坐軸作圖，即可得到ROC 曲線。TPR和FPR的計(jì)算公式如下：

AUC的計(jì)算公式如下：

首先將得分從小到大排序，然后只對(duì)正樣本的序號(hào)相加，并減去正樣本之前的數(shù)，最后除以總的樣本數(shù)得到AUC。

3.4 實(shí)驗(yàn)結(jié)果與分析

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

表4 不同數(shù)據(jù)集上節(jié)點(diǎn)分類的Macro-F1值 單位：%Tab.4 Macro-F1 values of node classification on different datasets unit：%

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

從表3～5 中可以看出，隨著節(jié)點(diǎn)標(biāo)記率的提高，GAECSRL 和基線方法在節(jié)點(diǎn)分類和鏈接預(yù)測中的評(píng)價(jià)指標(biāo)有所提高，說明節(jié)點(diǎn)標(biāo)簽在生成網(wǎng)絡(luò)表示的過程中起著重要作用，加入節(jié)點(diǎn)標(biāo)簽，使得GAECSRL 學(xué)習(xí)到的節(jié)點(diǎn)表示更具有代表性，與原始網(wǎng)絡(luò)更接近。

表3 不同數(shù)據(jù)集上節(jié)點(diǎn)分類的Micro-F1值 單位：%Tab.3 Micro-F1 values of node classification on different datasets unit：%

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

表4 展示了在不同數(shù)據(jù)集上進(jìn)行節(jié)點(diǎn)分類的Macro-F1值，在Cora 數(shù)據(jù)集上，GAECSRL 在標(biāo)記率為40%和50%時(shí)Macro-F1 值僅次于DeepWalk 和node2vec，相差分別為0.59和0.07 個(gè)百分點(diǎn)，其他情況優(yōu)于基線方法；在CiteSeer 和Wiki 數(shù)據(jù)集上，GAECSRL 在標(biāo)記率為20% 時(shí)，次于Planetoid，分別相差0.20 和2.25 個(gè)百分點(diǎn)；在PubMed 數(shù)據(jù)集上，GAECSRL 與基線方法相比最優(yōu)。在Cora 和Wiki 數(shù)據(jù)集上，GAECSRL 相較基線方法提高了0.76～10.85 個(gè)百分點(diǎn)，在CiteSeer 和PubMed 數(shù)據(jù)集上提升了2.04～24.20 個(gè)百分點(diǎn)，效果較為明顯，同樣是由于CiteSeer 和PubMed 數(shù)據(jù)集較大、節(jié)點(diǎn)標(biāo)記率高，獲得了更優(yōu)的網(wǎng)絡(luò)表示。

表5 展示了在不同數(shù)據(jù)集上進(jìn)行鏈接預(yù)測的AUC 值，在數(shù)據(jù)集Cora 上，GAECSRL 在標(biāo)記率為50%和60%時(shí)，結(jié)果僅次于DeepWalk 和node2vec，相差0.47 和0.13 個(gè)百分點(diǎn)；在CiteSeer 數(shù)據(jù)集上，GAECSRL 在標(biāo)記率為60% 時(shí)次于node2vec，相差0.15 個(gè)百分點(diǎn)；在Wiki 數(shù)據(jù)集上，GAECSRL在標(biāo)記率為40%時(shí)，結(jié)果比DeepWalk 低0.92 個(gè)百分點(diǎn)，其他情況都是最優(yōu)。在不同數(shù)據(jù)集上，與基線方法相比，GAECSRL 提升的百分點(diǎn)都在10 以內(nèi)。

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

圖2 不同數(shù)據(jù)集上α值對(duì)評(píng)價(jià)指標(biāo)的影響Fig.2 Influence of α value on evaluation indexes on different datasets

4 結(jié)語

現(xiàn)實(shí)世界的網(wǎng)絡(luò)數(shù)據(jù)具有豐富伴隨信息，如標(biāo)簽信息和屬性信息等，這些伴隨信息對(duì)網(wǎng)絡(luò)表示的生成有積極意義。所提方法將節(jié)點(diǎn)的標(biāo)簽信息、結(jié)構(gòu)信息和屬性信息加入網(wǎng)絡(luò)表示學(xué)習(xí)的過程中，提出了一種結(jié)合圖自編碼器與聚類的半監(jiān)督表示學(xué)習(xí)方法（GAECSRL）。該方法保持了網(wǎng)絡(luò)的結(jié)構(gòu)相似性和屬性特征，用節(jié)點(diǎn)標(biāo)簽信息指導(dǎo)網(wǎng)絡(luò)表示學(xué)習(xí)，提高了網(wǎng)絡(luò)表示學(xué)習(xí)的可區(qū)分性。在真實(shí)數(shù)據(jù)集上進(jìn)行節(jié)點(diǎn)分類和鏈接預(yù)測任務(wù)，與基準(zhǔn)算法進(jìn)行對(duì)比，實(shí)驗(yàn)證明了GAECSRL 方法的有效性。

GAECSRL 方法在實(shí)驗(yàn)過程中表現(xiàn)出了較好的性能，但是時(shí)間復(fù)雜度較高；此外，網(wǎng)絡(luò)中仍存在其他高級(jí)的信息，如文本信息和語義信息等，而GAECSRL 只利用了節(jié)點(diǎn)的標(biāo)簽信息。今后的工作中，將考慮如何降低GAECSRL 的時(shí)間復(fù)雜度，同時(shí)將其他的高級(jí)信息融合到網(wǎng)絡(luò)表示中。