[發(fā)明專利]分布式圖嵌入的方法及裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 201810819799.5
• 申請(qǐng)日: 2018-07-24
• 公開(kāi)（公告）號(hào): CN109194707B
• 公開(kāi)（公告）日: 2020-11-20
• 發(fā)明（設(shè)計(jì)）人: 梁琛;劉子奇
• 申請(qǐng)（專利權(quán)）人: 創(chuàng)新先進(jìn)技術(shù)有限公司
• 主分類號(hào): H04L29/08
• 分類號(hào): H04L29/08
• 代理公司: 北京億騰知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11309
• 代理人: 陳霽;周良玉

本說(shuō)明書實(shí)施例提供一種通過(guò)分布式架構(gòu)將關(guān)系網(wǎng)絡(luò)圖嵌入到多維空間的方法和裝置，其中分布式架構(gòu)包括多個(gè)處理設(shè)備，分別被分配有關(guān)系網(wǎng)絡(luò)圖的一組節(jié)點(diǎn)；該方法由某一處理設(shè)備執(zhí)行，并包括，首先確定本處理設(shè)備負(fù)責(zé)的第一節(jié)點(diǎn)的一階鄰居節(jié)點(diǎn)，并確定這些一階鄰居節(jié)點(diǎn)所對(duì)應(yīng)的處理設(shè)備。另一方面，還確定該第一節(jié)點(diǎn)的初始嵌入向量作為當(dāng)前階數(shù)嵌入向量。之后，利用一階鄰居節(jié)點(diǎn)的當(dāng)前階數(shù)嵌入向量計(jì)算第一節(jié)點(diǎn)的下一階數(shù)嵌入向量，并用下一階數(shù)嵌入向量更新當(dāng)前階數(shù)嵌入向量。不斷執(zhí)行更新步驟，直到當(dāng)前階數(shù)達(dá)到預(yù)設(shè)搜索深度，將此時(shí)的當(dāng)前階數(shù)嵌入向量作為到多維空間的嵌入向量。如此，高效地將關(guān)系網(wǎng)絡(luò)圖嵌入到多維空間中。

技術(shù)領(lǐng)域

本說(shuō)明書一個(gè)或多個(gè)實(shí)施例涉及計(jì)算機(jī)信息處理領(lǐng)域，尤其涉及采用分布式架構(gòu)進(jìn)行圖嵌入的方法和裝置。

背景技術(shù)

關(guān)系網(wǎng)絡(luò)圖是對(duì)現(xiàn)實(shí)世界中實(shí)體之間的關(guān)系的描述，目前廣泛地應(yīng)用于各種計(jì)算機(jī)信息處理中。一般地，關(guān)系網(wǎng)絡(luò)圖包含一個(gè)節(jié)點(diǎn)集合和一個(gè)邊集合，節(jié)點(diǎn)表示現(xiàn)實(shí)世界中的實(shí)體，邊表示現(xiàn)實(shí)世界中實(shí)體之間的聯(lián)系。例如，在社交網(wǎng)絡(luò)中，人就是實(shí)體，人和人之間的關(guān)系或聯(lián)系就是邊。

在許多情況下，希望將關(guān)系網(wǎng)絡(luò)圖中的每個(gè)節(jié)點(diǎn)(實(shí)體)用多維空間中的向量來(lái)表示，也就是將各個(gè)節(jié)點(diǎn)映射到一個(gè)多維空間中，用多維空間中的點(diǎn)代表圖中的節(jié)點(diǎn)。多維空間可以是2維、3維空間，也可以是更高維空間。用多維空間的坐標(biāo)來(lái)表達(dá)圖中的節(jié)點(diǎn)，可以應(yīng)用于計(jì)算節(jié)點(diǎn)和節(jié)點(diǎn)之間的相似度，發(fā)現(xiàn)圖中的社團(tuán)結(jié)構(gòu)，預(yù)測(cè)未來(lái)可能形成的邊聯(lián)系，以及對(duì)圖進(jìn)行可視化等。將圖中的節(jié)點(diǎn)映射到多維空間的過(guò)程稱為圖嵌入。

圖嵌入是一種非常重要的基礎(chǔ)技術(shù)能力。目前，在許多關(guān)系網(wǎng)絡(luò)圖(例如用戶社交網(wǎng)絡(luò))中，包含的節(jié)點(diǎn)數(shù)目達(dá)到上億甚至幾億，此時(shí)的圖嵌入計(jì)算將耗費(fèi)巨大的計(jì)算資源。為此，提出了分布式系統(tǒng)，其中包含多個(gè)處理設(shè)備(又稱為worker)和管理器(master),各個(gè)處理設(shè)備承擔(dān)一部分節(jié)點(diǎn)的計(jì)算量，而通過(guò)管理器實(shí)現(xiàn)各個(gè)處理設(shè)備之間的調(diào)配、異常檢測(cè)、參數(shù)聚合等功能。然而，在關(guān)系網(wǎng)絡(luò)圖的圖直徑過(guò)小，節(jié)點(diǎn)搜索深度較大等許多情況下，各個(gè)處理設(shè)備依然存在計(jì)算量過(guò)大，顯著超過(guò)負(fù)荷的情況，使得圖嵌入的過(guò)程難以高效進(jìn)行。

因此，希望能有改進(jìn)的方案，更加快速有效地進(jìn)行關(guān)系網(wǎng)絡(luò)圖的圖嵌入過(guò)程。

發(fā)明內(nèi)容

本說(shuō)明書一個(gè)或多個(gè)實(shí)施例描述了一種分布式圖嵌入方法，可以通過(guò)分布式架構(gòu)高效地將關(guān)系網(wǎng)絡(luò)圖中的節(jié)點(diǎn)嵌入到多維空間中，以便于后續(xù)的信息處理。

根據(jù)第一方面，提供了一種通過(guò)分布式架構(gòu)將關(guān)系網(wǎng)絡(luò)圖嵌入到多維空間的方法，所述關(guān)系網(wǎng)絡(luò)圖包括多個(gè)節(jié)點(diǎn)，所述分布式架構(gòu)包括多個(gè)處理設(shè)備，各個(gè)處理設(shè)備分別被分配有所述多個(gè)節(jié)點(diǎn)中的一組節(jié)點(diǎn)，所述方法由所述多個(gè)處理設(shè)備中的某一處理設(shè)備執(zhí)行，所述方法包括：

針對(duì)本處理設(shè)備所分配的第一節(jié)點(diǎn)組中的第一節(jié)點(diǎn)，根據(jù)所述關(guān)系網(wǎng)絡(luò)圖的鄰接信息，確定所述第一節(jié)點(diǎn)的至少一個(gè)一階鄰居節(jié)點(diǎn)；

根據(jù)節(jié)點(diǎn)分配信息，確定所述至少一個(gè)一階鄰居節(jié)點(diǎn)所對(duì)應(yīng)的至少一個(gè)處理設(shè)備，其中所述節(jié)點(diǎn)分配信息記錄所述多個(gè)節(jié)點(diǎn)在所述多個(gè)處理設(shè)備中的分配狀況；

確定所述第一節(jié)點(diǎn)的初始嵌入向量作為當(dāng)前階數(shù)嵌入向量；

更新所述第一節(jié)點(diǎn)的當(dāng)前階數(shù)嵌入向量，包括：從所述至少一個(gè)處理設(shè)備獲取所述至少一個(gè)一階鄰居節(jié)點(diǎn)所分別對(duì)應(yīng)的至少一個(gè)當(dāng)前階數(shù)嵌入向量；根據(jù)所述至少一個(gè)當(dāng)前階數(shù)嵌入向量，確定所述第一節(jié)點(diǎn)的下一階數(shù)嵌入向量；用所述下一階數(shù)嵌入向量更新所述第一節(jié)點(diǎn)的當(dāng)前階數(shù)嵌入向量；

判斷當(dāng)前階數(shù)是否達(dá)到預(yù)設(shè)節(jié)點(diǎn)搜索深度，在沒(méi)有達(dá)到的情況下，反復(fù)執(zhí)行所述更新所述第一節(jié)點(diǎn)的當(dāng)前階段嵌入向量，直到所述當(dāng)前階數(shù)達(dá)到預(yù)設(shè)節(jié)點(diǎn)搜索深度；

將當(dāng)前階數(shù)達(dá)到預(yù)設(shè)節(jié)點(diǎn)搜索深度時(shí)第一節(jié)點(diǎn)的當(dāng)前階數(shù)嵌入向量，確定為所述第一節(jié)點(diǎn)的嵌入向量。