一種基于矩陣分解的網(wǎng)絡(luò)嵌入方法NetMF

　　隨著互聯(lián)網(wǎng)的普及，越來越多的問題以社交網(wǎng)絡(luò)這樣的網(wǎng)絡(luò)形式出現(xiàn)。網(wǎng)絡(luò)通常用圖數(shù)據(jù)表示，由于圖數(shù)據(jù)處理的挑戰(zhàn)性，如何從圖中學(xué)習(xí)到重要的信息是當(dāng)前被廣泛關(guān)注的問題。網(wǎng)絡(luò)嵌入就是通過分析圖數(shù)據(jù)得到反映網(wǎng)絡(luò)結(jié)構(gòu)的特征向量，利用它們進(jìn)而實現(xiàn)各種數(shù)據(jù)挖掘任務(wù)，例如邊預(yù)測、節(jié)點分類、網(wǎng)絡(luò)重構(gòu)、標(biāo)簽推薦和異常檢測。最近，基于矩陣分解的網(wǎng)絡(luò)嵌入方法 Net mf被提出，它在理論上統(tǒng)一了多種網(wǎng)絡(luò)嵌入方法，并且在處理實際數(shù)據(jù)時表現(xiàn)出很好的效果。然而，在處理大規(guī)模網(wǎng)絡(luò)時， Net Mf需要極大的時間和空間開銷。本文使用快速隨機化特征值分解和單遍歷奇異值分解技術(shù)對 Net mf進(jìn)行改進(jìn)，提出一種高效率、且內(nèi)存用量小的矩陣分解網(wǎng)絡(luò)嵌入算法 enemy.首先，我們提出了適合于對稱稀疏矩陣的隨機化特征值分解算法 freigs，它在處理實際的歸一化網(wǎng)絡(luò)矩陣時比傳統(tǒng)的截斷特征值分解算法快近10倍，且?guī)缀醪粨p失準(zhǔn)確度。其次，我們提出使用單遍歷奇異值分解處理Net mf方法中高次近似矩陣從而避免稠密矩陣存儲的技術(shù)，它大大減少了網(wǎng)絡(luò)嵌入所需的內(nèi)存用量。最后，我們提出一種簡潔的、且保證分解結(jié)果對稱的隨機化單遍歷奇異值分解算法，將它與上述技術(shù)結(jié)合得到 enet mf算法?；?個實際的網(wǎng)絡(luò)數(shù)據(jù)集，我們評估了 enetmf學(xué)習(xí)到的網(wǎng)絡(luò)低維表示在多標(biāo)簽節(jié)點分類和邊預(yù)測上的有效性實驗結(jié)果表明，使用 enetmf替代NeM后在后續(xù)得到的多標(biāo)簽分類性能指標(biāo)上幾乎沒有損失，但在處理大規(guī)模數(shù)據(jù)時有超過40倍的加速與內(nèi)存用量節(jié)省。在一臺32核的機器上， enet MF僅需約1.3h即可對含一百多萬節(jié)點的 Youtube數(shù)據(jù)學(xué)習(xí)到網(wǎng)絡(luò)嵌入，內(nèi)存用量僅為30GB，并得到較高質(zhì)量的分類結(jié)果。此外，最近被提出的網(wǎng)絡(luò)嵌人算法 Netsmf由于圖稀疏化過程的內(nèi)存需求太大，無法在256GB內(nèi)存的機器上處理兩個較大的網(wǎng)絡(luò)數(shù)據(jù)，而PNE算法則在多標(biāo)簽分類的結(jié)果上表現(xiàn)不穩(wěn)定，得到的 Macro f1值都比較差因此， e Neeme算法在結(jié)果質(zhì)量上明顯優(yōu)于 Netsmf和 Prone算法，在邊預(yù)測任務(wù)上， enem算法也表現(xiàn)出與其它方法差不多甚至更好的性能。