陳 獻(xiàn)，胡麗瑩*，林曉煒，陳黎飛，3

（1.福建師范大學(xué)計算機與網(wǎng)絡(luò)空間安全學(xué)院，福州 350117；2.數(shù)字福建環(huán)境監(jiān)測物聯(lián)網(wǎng)實驗室（福建師范大學(xué)），福州 350117；3.福建省應(yīng)用數(shù)學(xué)中心（福建師范大學(xué)），福州 350117）

（?通信作者電子郵箱hlyxyz@fjnu.edu.cn）

0 引言

圖結(jié)構(gòu)可以自然地表示網(wǎng)狀結(jié)構(gòu)的數(shù)據(jù)，如社交網(wǎng)絡(luò)、電力網(wǎng)絡(luò)、引文網(wǎng)絡(luò)、運輸網(wǎng)絡(luò)、蛋白質(zhì)-蛋白質(zhì)相互作用網(wǎng)絡(luò)［1］等。隨著各個領(lǐng)域網(wǎng)絡(luò)數(shù)據(jù)的增長以及對網(wǎng)絡(luò)數(shù)據(jù)處理的迫切需求，分析圖結(jié)構(gòu)以及挖掘圖結(jié)構(gòu)中的關(guān)系信息成為了熱點問題，圖聚類［2］是其中的一項基礎(chǔ)研究課題。圖聚類根據(jù)節(jié)點及節(jié)點間連接關(guān)系的相似性將節(jié)點劃分為簇，使得簇內(nèi)節(jié)點相似度較高，簇間的節(jié)點則差異較大。

目前已提出多種圖聚類算法，包括基于圖分割的算法［3］、層次聚類算法［4］、譜聚類算法［5］等，這些算法大多忽視節(jié)點連邊的方向性，把有向圖轉(zhuǎn)化為有無向圖進行處理。對于有向網(wǎng)絡(luò)如引文網(wǎng)絡(luò)、基因轉(zhuǎn)移網(wǎng)絡(luò)、運輸網(wǎng)絡(luò)等，若以無向圖方式處理將丟失有用信息甚至引發(fā)歧義。例如，對于由文獻(xiàn)間引用和被引用關(guān)系構(gòu)成的引文網(wǎng)絡(luò)，當(dāng)看作無向圖時，將出現(xiàn)文獻(xiàn)間僅存在的單方面引用關(guān)系變成同時包含引用和被引用雙向關(guān)系的錯誤情形。為有效建模節(jié)點間連接關(guān)系的方向性，目前典型的方法是將無向圖聚類算法推廣到有向圖，如Satuluri 等［6］提出的轉(zhuǎn)換有向圖為無向加權(quán)圖的方法，通過有向圖上非對稱鄰接矩陣隨機游走對稱化或節(jié)點的入度和出度對稱化手段來構(gòu)造新的對稱鄰接矩陣，但這種方法可能導(dǎo)致有向圖上某些獨特的邊方向性信息丟失?；贚aplacian 矩陣的多種譜聚類算法［7-9］則將聚類目標(biāo)函數(shù)擴展到有向圖中，并對得到的拉普拉斯矩陣做特征值分解；但該矩陣的特征值可能存在負(fù)值，降低了所構(gòu)造模型的可解釋性。

基于非負(fù)矩陣分解（Nonnegative Matrix Factorization，NMF）［10］的一類方法［11-12］則通過將圖鄰接矩陣的非負(fù)結(jié)構(gòu)分解（structured factorization）實現(xiàn)圖聚類。由于被分解的可以是非對稱矩陣且分解結(jié)果均為非負(fù)矩陣，該類方法對有向圖聚類具有良好的適應(yīng)性和可解釋性，近年來得到廣泛關(guān)注。譬如，Wang 等［11］提出的非對稱非負(fù)矩陣分解（Asymmetric NMF，ANMF）算法將有向圖的非對稱鄰接矩陣分解為分別表示“節(jié)點-簇”隸屬度和簇間相似性的非負(fù)矩陣，進而基于隸屬度矩陣對節(jié)點進行簇劃分；在此基礎(chǔ)上，Tosyali等［12］引入節(jié)點間的相似先驗信息為正則項，構(gòu)造了正則化的非對稱非負(fù)矩陣分解（Regularized Asymmetric NMF，RANMF）算法，提高了有向圖聚類的準(zhǔn)確性和魯棒性。

然而，以上算法忽略了有向圖上潛在的節(jié)點間的非線性關(guān)系。在許多實際應(yīng)用產(chǎn)生的圖（網(wǎng)絡(luò)）中，節(jié)點與節(jié)點之間通常是非線性相關(guān)的。如社交網(wǎng)絡(luò)中，個體（節(jié)點）之間的關(guān)系并不是單一的，有可能是同事、家人甚至更復(fù)雜的人際關(guān)系（有向邊）。顯然，這些關(guān)系不能簡單地以線性方式來逼近。當(dāng)前，深度學(xué)習(xí)（deep learning）與核學(xué)習(xí)（kernel learning）是兩種主流的節(jié)點間非線性關(guān)系建模方法。例如，Perozzi 等［13］提出深度游走（DeepWalk）算法，通過隨機游走捕捉圖的高階近鄰結(jié)構(gòu)，進而將深度學(xué)習(xí)技術(shù)運用到圖聚類問題中；但是，該算法并未考慮節(jié)點間連接的方向性。核學(xué)習(xí)方法［14］通過將低維數(shù)據(jù)嵌入到高維核空間中，使得低維不可分?jǐn)?shù)據(jù)在新空間中線性可分或接近線性可分，從而有效挖掘隱含在數(shù)據(jù)中的非線性關(guān)系。近年，已提出多種核非負(fù)矩陣分解（Kernel NMF，KNMF）算法，利用小樣本條件下核學(xué)習(xí)方法在非線性學(xué)習(xí)中的良好性能進行人臉識別、文本聚類等［15-18］。

本文提出用于非線性有向圖聚類的核非負(fù)矩陣分解算法，稱為正則化的核非對稱非負(fù)矩陣分解（Regularized Kernel Asymmetric NMF，RKANMF）。首先，基于核化機制構(gòu)造了有向圖核聚類目標(biāo)函數(shù)，定義了約束核空間中節(jié)點相似性關(guān)系的正則化項，以保持原空間中節(jié)點間相似關(guān)系的同時強化核空間中同簇節(jié)點間的（非線性）相似性；其次，基于梯度下降法提出了一種聚類優(yōu)化算法，證明了算法的收斂性；最后，在8個有向網(wǎng)絡(luò)數(shù)據(jù)集上進行了實驗，并與深度學(xué)習(xí)算法等進行了對比，實驗結(jié)果驗證了所提算法的有效性。

1 相關(guān)工作

1.1 基本定義

定義1有向圖。在有向圖中G=(V，E)，邊(i，j)∈E將節(jié)點i連接到節(jié)點j，|V|表示節(jié)點數(shù)，|E|表示邊數(shù)。有向圖可以由鄰接矩陣來表示。

構(gòu)建有向圖鄰接矩陣：鄰接矩陣A∈Rn×n+，其中n是節(jié)點數(shù)，若從節(jié)點到節(jié)點存在有向邊，[A]ij=1，否則[A]ij=0。特別地，[A]ii=0。本文用[·]ij表示矩陣第i行第j列元素。

圖聚類基于節(jié)點間的相似性：節(jié)點之間越相似，則越可能劃分到同一個簇。文獻(xiàn)中常用的節(jié)點相似性度量有：

1）Katz 中心相似性度量［19］。對于圖中每一條路徑，利用加權(quán)方案計算其權(quán)重，公式如下：

其中：I為元素全為1 的矩陣；當(dāng)參數(shù)β＜1 時，較長的路徑將分配到較小的權(quán)重，較短的路徑則獲得更大的權(quán)重，權(quán)重越大，節(jié)點間就越相似。

2）余弦相似性度量［19］。計算節(jié)點間公共鄰居的數(shù)量，公共鄰居的數(shù)量越多表示節(jié)點間越相似。計算公式為：

其中：cij表示節(jié)點i與節(jié)點j的公共鄰居數(shù)量；為由所有鄰居數(shù)量組成的向量的長度，取值在0到1之間。余弦相似度為1表示兩個節(jié)點具有相同的鄰居，0則表示沒有相同鄰居。

1.2 基于NMF的聚類算法

其中：r?min{m，n}為分解矩陣的秩；‖?‖F(xiàn)表示矩陣的Frobenious 范數(shù)。對于聚類任務(wù)［20］，分解結(jié)果中的W可以視為隸屬度矩陣，根據(jù)規(guī)則將第i個樣本xi分配到隸屬度最大的簇j*，完成聚類。

下面介紹兩種基于NMF 的代表性有向圖聚類算法：ANMF［12］和RANMF［13］算法。ANMF 將式（3）中的B矩陣用HWT代替，其中，，定義其優(yōu)化問題如下：

RANMF 在ANMF 算法基礎(chǔ)上添加了圖正則化項，對同簇節(jié)點間的相似性進行約束，其定義的優(yōu)化問題如下：

其中：Tr(?)是矩陣的跡；S是節(jié)點間相似性矩陣；D為對角矩陣，其中每個對角元Dii是矩陣S的第i行元素的和。

1.3 核函數(shù)與KNMF

核函數(shù)是從低維空間到高維空間中的一種映射函數(shù)。設(shè)R為輸入空間，H為特征空間（希爾伯特空間或核再生空間，以下簡稱核空間），核學(xué)習(xí)方法［14］利用核函數(shù)實現(xiàn)從R到H的映射：φ(X)：R→H。對于輸入空間的樣本對(xi，xj)，核技巧（kernel trick）通過替換核空間中樣本對的內(nèi)積為核函數(shù)κ(xi，xj)的值（核化），解決φ(X)難于計算的問題，即：

常用的核函數(shù)包括多項式核函數(shù)和徑向基核函數(shù)等，其定義分別如下：

為捕捉數(shù)據(jù)中的局部結(jié)構(gòu)信息，文獻(xiàn)［21］新近提出了分?jǐn)?shù)階核（Fractional power kernel）：

其中：zd表示任意向量z中每個元素的d次冪。鑒于圖聚類的目的在于根據(jù)圖的局部結(jié)構(gòu)特性進行節(jié)點分組，本文采用如式（4）所示的分?jǐn)?shù)階核函數(shù)，并用矩陣形式加以表示，如下：

在傳統(tǒng)NMF 的基礎(chǔ)上，利用上述核化機制可以對輸入矩陣進行核非負(fù)矩陣分解（KNMF）。例如，基于KNMF 的人臉識別［17-18］定義其優(yōu)化問題為：

意在優(yōu)化兩個非負(fù)矩陣W和B，使得映射后的人臉圖像在核空間可以近似地表示為基圖像的線性組合，即：φ(X)≈φ(W)B。相比僅能對數(shù)據(jù)中線性關(guān)系建模的傳統(tǒng)NMF，KNMF 的優(yōu)勢在于可以通過核函數(shù)對數(shù)據(jù)進行高維映射發(fā)掘隱含的非線性特征，并利用核技巧降低算法的時間復(fù)雜度。

2 RKANMF有向圖聚類算法

本章討論基于正則化核非對稱非負(fù)矩陣分解（RKANMF）的有向圖聚類算法。首先構(gòu)造了新的聚類優(yōu)化目標(biāo)函數(shù)，給出參數(shù)優(yōu)化方法；接著，提出優(yōu)化該目標(biāo)函數(shù)的聚類算法，并嚴(yán)格證明了算法的收斂性。

2.1 聚類目標(biāo)函數(shù)及其優(yōu)化方法

為在保持原空間中節(jié)點間（線性）相似關(guān)系的同時強化核空間中同簇節(jié)點間的（非線性）相似性，在構(gòu)造約束核空間中節(jié)點相似性關(guān)系的正則項的基礎(chǔ)上，利用核化機制定義RKANMF有向圖核聚類目標(biāo)函數(shù)如下：

其中：D是對角線矩陣，其對角元Dii是矩陣S的第i行的和。整理聚類目標(biāo)函數(shù)式（6）得到：

從優(yōu)化角度分析，聚類是求解聚類目標(biāo)函數(shù)最優(yōu)值的過程，即在矩陣W和H非負(fù)約束條件下最小化式（7）。根據(jù)梯度下降方法，矩陣W和H通過迭代以下乘法更新規(guī)則求解：

其中Zd表示矩陣Z中每個元素的d次冪。

2.2 聚類算法及收斂性分析

依據(jù)2.1 節(jié)中W和H的更新公式（式（8）和（9）），提出基于RKANMF的有向圖聚類算法，具體描述如下：

算法 基于RKANMF的有向圖聚類算法。

計算KWAWd和KWWHKWW的時間復(fù)雜度分別為O(n2r)和O(r2(r+n))，由于r＜n，每次迭代更新公式H的時間復(fù)雜度為O(n2r)。同理，每次迭代更新W的時間復(fù)雜度為O(n2r)，因此，算法在不考慮迭代次數(shù)的情況下，時間復(fù)雜度為O(n2r)。

接著對算法的收斂性進行分析，借鑒文獻(xiàn)［11，22］中的輔助函數(shù)法來證明在所提更新規(guī)則下算法的收斂性。

定理1式（7）中的目標(biāo)函數(shù)在矩陣W和H的更新規(guī)則式（8）和（9）下是單調(diào)非增的。

證明 當(dāng)固定H時，令

可得以下三個不等式：

令φ(W)=Wd，即得式（8）中W的更新公式。

同理，當(dāng)W固定時，正則項部分與H無關(guān)。此時，令

則有：

得出式（8）中H的乘法更新公式。又由于

3 實驗與分析

本章通過在三個領(lǐng)域有向網(wǎng)絡(luò)數(shù)據(jù)集上的實驗來驗證所提算法RKANMF 在有向圖聚類中的有效性，并與當(dāng)前若干主流算法（ANMF［11］、RANMF［12］及DeepWalk 算法［13］）進行對比。實驗平臺如下：Core i7-9750 2.60 GHz CPU，16.00 GB 內(nèi)存，操作系統(tǒng)為Windows 10。

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

實驗使用的有向網(wǎng)絡(luò)數(shù)據(jù)集包含專利-引文網(wǎng)絡(luò)（Patent Citation Network，PCN）數(shù)據(jù)集［23］、World Wide Knowledge Base（WebKB）數(shù)據(jù)集［24］和人工合成網(wǎng)絡(luò)LFR（Lancichinetti-Fortunato-Radicchi）數(shù)據(jù)集［25］，數(shù)據(jù)集的詳細(xì)信息見表1。

表1 有向網(wǎng)絡(luò)數(shù)據(jù)集的詳細(xì)信息Tab.1 Details of directed network datasets

①PCN 數(shù)據(jù)集。PCN 由4 142 個節(jié)點和18 385 條邊組成，形成一個單一的連接樹結(jié)構(gòu)。本文選擇PCN 中的149個節(jié)點（專利）和215 個有向邊（引用）來檢驗聚類效果。由于同一簇的專利不一定具有直接公共鄰居，而是具有一個或多個中間專利連接的非中間鄰居，因此根據(jù)式（1）計算相似矩陣。由于PCN數(shù)據(jù)集沒有提供節(jié)點標(biāo)簽，因此該數(shù)據(jù)集的簇數(shù)目未知，表1用“—”給予了標(biāo)識。

②WebKB 數(shù)據(jù)集。該數(shù)據(jù)集包含從4 所大學(xué)（Cornel、Texas、Washington 和Wisconsin）收集的網(wǎng)頁，網(wǎng)頁分為學(xué)生、課程、項目、教師和工作人員5 類。通常，一個高質(zhì)量的簇應(yīng)具有較少的簇間連接和更多的簇內(nèi)連接。由于WebKB 數(shù)據(jù)集中的簇與簇之間的連通性較高，選用式（2）計算節(jié)點間的相似矩陣。

③LFR 數(shù)據(jù)集。LFR 是一個人工合成數(shù)據(jù)集，包含的網(wǎng)絡(luò)是根據(jù)某些參數(shù)控制的機制產(chǎn)生的。比如，通過混合參數(shù)μ控制合成網(wǎng)絡(luò)中簇間連通性的強度，其值越大意味著更強的簇間連通性。本文取μ=0.1，0.3，0.5（分別對應(yīng)表1 中的LFR1、LFR2 和LFR3），并使用Katz 中心相似性度量式（2）計算節(jié)點間的相似矩陣。

3.2 評價指標(biāo)

當(dāng)數(shù)據(jù)集沒有真實簇劃分時采用Davies-Bouldin（DB）指標(biāo)［26］和Distance-based Quality Function（DQF）指標(biāo)［27］評價多個算法的聚類結(jié)果質(zhì)量；當(dāng)存在真實簇劃分時采用聚類準(zhǔn)確率（ACcuracy，AC）指標(biāo)、NMI 指標(biāo)及Jaccard 指標(biāo)［28］。各指標(biāo)簡要介紹如下：

①DB指標(biāo)。

計算簇內(nèi)散射與簇間分離之比，公式如下：

其中：N表示簇的個數(shù)；表示第i個簇中節(jié)點的平均分散程度；Mij為第i類與第j類簇的距離。當(dāng)DB 指標(biāo)值越小時，算法得到的聚類效果越好。

②DQF指標(biāo)。

計算簇與簇之間的平均距離，公式如下：

其中：A表示鄰接矩陣；是根據(jù)算法得到節(jié)點簇集合劃分r個簇后構(gòu)建的新鄰接矩陣，若節(jié)點i與j同簇，則。DQF指標(biāo)越高，則得到的聚類結(jié)果越好。

③AC指標(biāo)。

計算預(yù)測的節(jié)點簇集合的準(zhǔn)確率，公式如下：

其中：n表示節(jié)點個數(shù)；ri、si分別為第i個節(jié)點所對應(yīng)的獲得的標(biāo)簽和真實標(biāo)簽；map(ri)是一個映射函數(shù)，表示將ri映射到相應(yīng)的節(jié)點簇類上。δ是指示函數(shù)，其公式如下：

AC指標(biāo)越高，聚類質(zhì)量越高。

④NMI指標(biāo)。

計算預(yù)測的節(jié)點簇集合與真實節(jié)點簇劃分的相似度，公式如下：

其中：C1和C2分別是預(yù)測的節(jié)點簇集合與真實節(jié)點簇集合；分別表示真實簇的數(shù)目與預(yù)測簇的數(shù)目；矩陣R=代表混淆矩陣，rij為真實簇的節(jié)點i出現(xiàn)在發(fā)現(xiàn)簇j的數(shù)量，ri?和r?j分別是混淆矩陣第i行的和與第j列的和。NMI指標(biāo)越高則聚類質(zhì)量越好。

⑤Jaccard指標(biāo)。

計算預(yù)測的節(jié)點簇集合與真實節(jié)點簇集合的交集和并集之比，公式如下：

其中：C1表示預(yù)測的節(jié)點簇集合，C2為真實節(jié)點簇集合。Jaccard指標(biāo)越高，則得到聚類結(jié)果與真實簇劃分越相似。

3.3 參數(shù)設(shè)置

為檢驗本文RKANMF 算法是否能有效建模節(jié)點間的非線性關(guān)系，將它與ANMF算法［11］、RANMF算法［12］進行了比較，并通過對比DeepWalk算法［13］，檢驗了小樣本條件下算法對有向聚類的準(zhǔn)確性。

在對不同網(wǎng)絡(luò)數(shù)據(jù)集的實驗中，RANMF 算法與ANMF 算法中Katz 中心相似性度量的β參數(shù)以及懲罰項權(quán)重系數(shù)λ的設(shè)置與文獻(xiàn)［12］中的最佳參數(shù)一致，所有基于NMF 的算法統(tǒng)一設(shè)置迭代停止精度ε=10-6。DeepWalk 算法參照文獻(xiàn)［13］設(shè)置每個節(jié)點出發(fā)游走10 次，游走長度為10；skip-gram 模型設(shè)置詞向量的維度為30，窗口大小設(shè)置為7。

簇的數(shù)目r值是有向圖聚類算法的重要問題，也是各個算法需要設(shè)置的先驗參數(shù)，本文在具有類標(biāo)簽的數(shù)據(jù)集上采用真實簇的數(shù)目作為r值，對于沒有類標(biāo)簽的PCN 數(shù)據(jù)集，選取不同的r值來對算法性能進行測試。

在真實網(wǎng)絡(luò)數(shù)據(jù)集中（PCN 和WebKB 數(shù)據(jù)集）重點討論分?jǐn)?shù)階核的次冪d值與懲罰項權(quán)重系數(shù)λ值對RKANMF 算法的影響。在PCN 數(shù)據(jù)集的實驗中，為了與ANMF 與RANMF算法進行對照實驗，RKANMF 算法設(shè)置共同的參數(shù)λ=0.1，β=0.2。當(dāng)參數(shù)d值取得過小時，計算過程中，W的更新公式（8）中的分母可能會接近于0，因此選擇d值在0.2 到0.9 區(qū)間。圖1與圖2顯示當(dāng)簇數(shù)r=2，d=0.2時，RKANMF 算法在DB與DQF指標(biāo)上均取得最優(yōu)。隨著d值增加，越趨近于1時，算法不再對節(jié)點間的非線性關(guān)系建模，從而導(dǎo)致聚類質(zhì)量下降。為檢驗簇數(shù)不同時對算法的影響，統(tǒng)一設(shè)置參數(shù)d=0.2。

圖1 參數(shù)d對DB指標(biāo)的影響Fig.1 Influence of parameter d on DB index

圖2 參數(shù)d對DQF指標(biāo)的影響Fig.2 Influence of parameter d on DQF index

在具有真實簇劃分的WebKB 數(shù)據(jù)集實驗中，著重考慮d值在0.2 到0.9 區(qū)間變化時，RKANMF 算法對AC 指標(biāo)的影響。結(jié)果如圖3所示，在多個子數(shù)據(jù)集上，當(dāng)d值在0.4到0.5之間時，算法的聚類結(jié)果在AC 指標(biāo)上更高。當(dāng)d值趨于1 時AC指標(biāo)呈下降趨勢，算法不再建模節(jié)點間的非線性關(guān)系從而導(dǎo)致聚類質(zhì)量下降。根據(jù)圖3，對四個子數(shù)據(jù)集（Cornel、Texas、Washington 和Wisconsin）分別取合適的d值為0.4、0.4、0.9和0.5。

圖3 WebKB數(shù)據(jù)集上d值對AC指標(biāo)影響Fig.3 Influence of d value on AC index on WebKB dataset

為考慮λ值對算法的影響，當(dāng)固定d值后，設(shè)置權(quán)重系數(shù)λ值區(qū)間為0 到500。圖4 顯示，當(dāng)λ值越大時，算法越傾向于考慮節(jié)點間的相似性信息；當(dāng)λ值過大時，算法過于依賴節(jié)點相似性，將原來屬于不同簇的節(jié)點劃分到同一簇中從而導(dǎo)致聚類準(zhǔn)確性下降。根據(jù)圖4，對四個子數(shù)據(jù)集（Cornel、Texas、Washington 和Wisconsin）分別取合適的λ值為20、5、50 和20。同理，在LFR 的3個數(shù)據(jù)集中，所提算法通過對比多次得到的AC指標(biāo)值，設(shè)置合適的參數(shù)β=0.1，λ=0.1，d=0.88。

圖4 WebKB數(shù)據(jù)集中λ值對AC指標(biāo)影響Fig.4 Influence of λ value on AC index on WebKB dataset

3.4 PCN數(shù)據(jù)集的實驗結(jié)果對比分析

本節(jié)使用PCN 數(shù)據(jù)集［23］來檢驗四種算法的性能表現(xiàn)。表2 是利用DB 和DQF 指標(biāo)上對不同算法進行比較的結(jié)果。方便起見，表中均采用“Rnd”對隨機初始化策略進行標(biāo)識；用“SVD”表示基于SVD策略［12］的初始化，方法與文獻(xiàn)［12］一致；使用隨機初始化策略的算法運行100 次，每一次都按不同的初始化矩陣進行迭代，取最終結(jié)果的平均值。

表2 簇數(shù)（r）不同時各算法在PCN上的DB和DQF指標(biāo)比較Tab.2 Comparison of DB and DQF indexes on PCN for each algorithm with different number of clusters（r）

表2 結(jié)果表明，隨著簇數(shù)r的增加，所有算法的聚類質(zhì)量均有所下降，說明當(dāng)簇的數(shù)目r越來越多時，本應(yīng)該劃分到相同簇的節(jié)點被分到不同簇，導(dǎo)致聚類質(zhì)量降低。對于DB 指標(biāo)，當(dāng)簇數(shù)r=6 時，RANMF 算法與RKANMF 算法的DB 指標(biāo)均低于DeepWalk 算法，這是由于過多考慮非中間鄰居從而導(dǎo)致聚類效果變差。對于DQF 指標(biāo)，在隨機初始化的情況下，所提算法也能比基于SVD 策略初始化［12］的RANMF 與ANMF算法在DQF 指標(biāo)上取得更好的表現(xiàn)。這說明RKANMF 算法有效地對節(jié)點間的非線性關(guān)系建模得到了更好的特征表示，顯著提高了聚類質(zhì)量。對比三種基于NMF 的算法可知，好的初始化策略及考慮了非線性關(guān)系的NMF 算法均能避免分解過程陷入較差的局部最優(yōu)值。

3.5 WebKB數(shù)據(jù)集的實驗結(jié)果對比分析

本節(jié)使用WebKB 數(shù)據(jù)集［24］中的四個子數(shù)據(jù)集來檢驗幾種算法在數(shù)據(jù)集的簇間連通性強時的性能，結(jié)果如表3?？梢钥闯?，當(dāng)數(shù)據(jù)集簇間連通性較高時，基于隨機初始化策略的算法能得到較好的聚類結(jié)果，這是由于經(jīng)過多次隨機初始化的過程，算法更容易找到一個更好的局部極小值。對比基于NMF 的算法與DeepWalk 算法可知，在大多數(shù)情況下，基于NMF 的算法能得到更好的聚類結(jié)果。這說明當(dāng)圖的結(jié)構(gòu)變得模糊，DeepWalk 算法無法準(zhǔn)確獲取有向圖的高階近鄰結(jié)構(gòu)，從而導(dǎo)致聚類質(zhì)量下降。

表3 各算法在WebKB數(shù)據(jù)集上的結(jié)果比較Tab.3 Result comparison of different algorithms on WebKB dataset

在Cornell 子數(shù)據(jù)集中，RKANMF 算法在NMI 指標(biāo)上最高，表明在數(shù)據(jù)集的簇間連通性高的情況下，RKANMF 算法也能有效發(fā)掘節(jié)點間非線性關(guān)系。在Texas 子數(shù)據(jù)集中，RANMF 與RKANMF 算法的NMI 指標(biāo)低于ANMF 算法，因為在正則項權(quán)重系數(shù)逐漸變大的過程中，帶正則項的兩個算法均忽視了鄰接矩陣的結(jié)構(gòu)信息，從而聚類質(zhì)量下降。

3.6 LFR網(wǎng)絡(luò)數(shù)據(jù)集的實驗結(jié)果對比分析

本節(jié)使用LFR網(wǎng)絡(luò)［25］來檢驗幾種算法檢驗在度分布不平衡的復(fù)雜網(wǎng)絡(luò)中的表現(xiàn)，結(jié)果如表4。表4顯示了不同算法在LFR 網(wǎng)絡(luò)上的實驗結(jié)果，其中“—”表示基于SVD 策略初始化的ANMF算法得不到聚類結(jié)果。由表4可以看出，隨著μ值的增加，算法對簇的劃分變得愈加困難。當(dāng)簇類結(jié)構(gòu)變得模糊時，基于NMF 的算法在NMI 指標(biāo)上低于DeepWalk 算法，這說明DeepWalk 更有針對性地獲取圖的結(jié)構(gòu)來提高劃分簇的質(zhì)量。RKANMF 算法在AC 和Jaccard 指標(biāo)上有更好的表現(xiàn)，這是由于RKANMF 算法中正則項發(fā)掘了節(jié)點間的（非線性）相似性關(guān)系。相比其他基于NMF 的算法，RKANMF 不僅在NMI指標(biāo)上與DeepWalk 算法比較接近，且在AC 和Jaccard 指標(biāo)上有顯著的提高，這說明當(dāng)節(jié)點關(guān)系變得復(fù)雜時，對節(jié)點間的非線性關(guān)系進行建模能更有效地提高聚類算法的表現(xiàn)。

表4 各算法在LFR網(wǎng)絡(luò)數(shù)據(jù)集上的結(jié)果比較Tab.4 Result comparison of different algorithms on LFR network dataset

4 結(jié)語

本文提出了一個用于有向圖聚類的圖正則化核非對稱非負(fù)矩陣分解優(yōu)化方法。該方法基于核化機制構(gòu)造了有向圖聚類新目標(biāo)函數(shù)，其正則項同時考慮了原始空間中節(jié)點間的相似性及節(jié)點在核空間中的（非線性）相關(guān)性；基于梯度下降法推導(dǎo)了一個有向圖聚類（RKANMF）算法，給出了算法的詳細(xì)過程及收斂性分析，并在多個有向網(wǎng)絡(luò)數(shù)據(jù)集進行了實驗。實驗結(jié)果表明，與未結(jié)合核學(xué)習(xí)方法的非負(fù)矩陣分解算法及DeepWalk 等算法相比，新算法在多個聚類有效性指標(biāo)上有更好的表現(xiàn)。今后我們將針對性地考慮節(jié)點的方向性以及不同核函數(shù)對有向圖聚類的影響等方面做進一步研究。