[發明專利]基于參數服務器架構的圖數據與參數數據的混合劃分方法

有效

• 申請號: 202110458807.X
• 申請日: 2021-04-27
• 公開（公告）號: CN113191486B
• 公開（公告）日: 2023-10-13
• 發明（設計）人: 谷峪;袁嘉隆;宋振;李傳文;李芳芳;于戈
• 申請（專利權）人: 東北大學
• 主分類號: G06N3/0442
• 分類號: G06N3/0442;G06N3/098;G06N3/084;H04L67/10;H04L67/1008
• 代理公司: 沈陽東大知識產權代理有限公司 21109
• 代理人: 李在川

1.一種基于參數服務器架構的圖數據與參數數據的混合劃分方法，其特征在于，包括：

步驟1：在原始圖數據中構建初始頂點，包括：

步驟1.1：通過使用廣度優先遍歷，將原始圖數據ID進行重新編號；

步驟1.2：將重新編號后的所有頂點ID劃分為大小均等的P個區間，計算每個ID分區內編號的中間值計算公式如下：

式中，x_r表示每個編號區間的右端點值，x_l表示每個編號區間的左端點值，表示向下取整運算；

步驟1.3：選取每個ID分區的中間值所對應的頂點作為初始頂點；

步驟2：以初始頂點作為初始分區對圖數據進行鄰域分區；

步驟3：計算每個分區的參數權重向量，根據P個分區的參數權重向量對圖神經網絡模型參數按行劃分為P個分區，將參數行劃分至需要使用其進行圖神經網絡計算的頂點數量最多的分區中。

2.根據權利要求1所述的一種基于參數服務器架構的圖數據與參數數據的混合劃分方法，其特征在于，所述步驟2包括：

步驟2.1：根據公式(2)定義圖數據G(V,E)中每個分區X的鄰居頂點集合B(X)；

B(X)＝{u|u∈V\X,v∈X,e_v,u∈E} (2)

式中，V表示圖數據中所有頂點的集合，E表示頂點之間邊的集合，v∈X表示分區X中的頂點，u∈V\X表示屬于集合V但不屬于集合X的頂點，e_v,u表示頂點v、u之間的邊；

步驟2.2：從分區X的初始頂點開始不斷搜索分區X的鄰居頂點集合中的頂點，選擇增加分區網絡開銷最小的頂點加入到分區X中，直到分區X中的頂點個數超過預設上限值，并將選擇過的頂點從集合V中刪除；

步驟2.3：針對每個初始頂點和集合V中剩余的頂點，重復步驟2.2繼續劃分分區，如果得到的分區數小于P且剩余的集合V中不存在初始頂點時，任意指定其他頂點為初始頂點繼續劃分分區，直到得到P個分區。

3.根據權利要求2所述的一種基于參數服務器架構的圖數據與參數數據的混合劃分方法，其特征在于，所述步驟2.2中選擇增加分區網絡開銷最小的頂點加入到分區X中，包括：

步驟2.2.1：將分區X中所有稀疏性向量累計得到參數權重向量ζ：

式中，n′表示分區X中的頂點數量，η_i表示第i個頂點對應的稀疏性向量；

步驟2.2.2：將參數權重向量中的每個元素與每個頂點的稀疏性向量中的對應元素一一相減，相減后的向量中負數元素的個數記為與分區X內頂點特征稀疏性不一致的維度的數量m；

步驟2.2.3：對分布式系統運行圖神經網絡算法時，圖數據中的頂點間通信代價C_edge、參數通信代價C_parameter分別表示為：

式中，n表示頂點u加入到分區X時分區與鄰域之間邊數量的變化值，f表示頂點的特征向量維度，j表示圖神經網絡模型的參數矩陣的列數量，m表示與分區X內頂點特征稀疏性不一致的維度的數量，C_int表示網絡傳輸中整型變量所占字節數，C_float表示網絡傳輸中單精度變量所占字節數；

步驟2.2.4：利用公式(5)計算分區X的鄰域內每個頂點的代價分數S(u)；

S(u)＝2n(fC_float+C_int)+2m(jC_float+C_int) (5)

步驟2.2.5：根據代價分數對分區X鄰域頂點排序，將最小代價分數所對應的頂點作為增加分區網絡開銷最小的頂點。

4.根據權利要求1所述的一種基于參數服務器架構的圖數據與參數數據的混合劃分方法，其特征在于，所述步驟3中根據P個分區的參數權重向量對圖神經網絡模型參數按行劃分為P個分區，包括：

步驟3.1：對比所有圖數據分區的參數權重向量ζ₁,ζ₂,…,ζ_P在第0維度的值，找出最大值對應的參數權重向量ζ_t，將圖神經網絡模型的第0行參數劃分至第t個參數分區；

步驟3.2：檢查第t個參數分區的參數行數量，若達到上限，則將參數權重向量ζ_t全部值更改為0；

步驟3.3：針對參數權重向量的剩余維度，重復步驟3.1與步驟3.2，直至劃分完畢圖神經網絡模型的所有參數行。