一种面向海量数据解决异质图神经网络数据划分不均衡处理的方法

1.本发明涉及一种面向海量数据解决异质图神经网络数据划分不均衡的处理方法，属于深度学习领域。


背景技术：

2.截至2022年6月，我国网民规模达10.51亿，互联网普及率达74.4％，移动互联网呈现全新的发展趋势。随着互联网的普及，用户数据不断增加，需要更高水平的用户行为分析和用户类别区分。为了提高分类和预测结果，模型参数数量增加，导致训练时间延长，计算资源需求更高。
3.图神经网络技术被证明是处理非欧几里得图形数据的有效工具，在搜索、推荐和风险控制等多个领域得到广泛应用。然而，由于图神经网络模型的训练数据规模较大，训练时间较长，分布式训练成为一种很好的选择，可以利用多台机器并行训练，以解决单机无法快速独立训练的问题。
4.在分布式图神经网络训练的主要流程，其中首要步骤是将数据划分到各个分区内，以便在不同计算节点上分布图数据的“子图”。进行图划分有助于将大规模图数据集分解为可并行计算的多个子集，从而实现分布式的训练过程。已有的多数研究表明，机器训练过程中由于数据分布不均衡，数据关联度不高等问题，会造成通信量和计算量的失衡。在一方面，由于不均衡的数据分配导致的参数同步等待时间增加，模型的训练时间也会增加。另一方面，数据划分不当还会造成其他影响，比如各个计算节点的模型训练过程中，容易存在训练结果差异大的问题，这会使得参数同步过程中引入更大的误差，进而影响整体模型的精度。因此，在进行图划分时，必须谨慎考虑计算量和通信量，使得两者达到平衡，进一步确保模型训练的高效性和精度。
5.目前多数分布式图神经网络框架在划分数据时多采用metis进行快速图划分。metis是一种简单的分区算法，它基于多级编码的思想，旨在将大型稀疏矩阵的分区任务分解为一系列更容易解决的多级划分子任务，使其具有较少的空间复杂度。distdgl对上述的划分方式进行了优化，通过对密集连接的节点进行优化，将高频繁访问的热节点进行唯一分区指定，并将非核心节点但却存在一定频率跨分区访问的顶点进行多次复制，从而确保每个分区的局部顶点的邻居是可访问的。这样在后续训练采样过程中可以减少跨分区的通讯访问，除此以外也减少了低质量边的保留，对高权重边进行了保留，以提高整体性能。通过约束机制支持平衡分区的边和节点使其数量相似。但这种方式针对少量关系的图划分具有较好的表现结果，而在复杂关系的异质图数据集中，节点及边的类型组合方式造成了多种元路径的组合，会导致划分结果不符合预期。
6.总体而言，多数用于分布式图神经网络的图划分方法基于同质图进行考虑，而对于异质图的划分却相对较少。在异质图中，由于存在异质的节点，且节点间数量多寡存在差异，采用现有的划分方式往往导致图的划分结果不均衡，由此造成不同计算节点之间的数
据交换更加频繁，进而影响图神经网络的精度和训练效率。对此提出了本文的大规模异质图均衡划分方法，从拆分聚合角度，对大规模的异质图数据进行合理划分，使其具备数据均衡性，提高数据相关性，并降低后续模型的跨分区交互频率。


技术实现要素：

7.为了克服现有技术的不足，本发明提供了一种面向海量数据解决异质图神经网络数据划分不均衡处理的方法。该方法能够对社交网络、学术网络、商品交易网络情景下，面向异质图图神经网络数据，其中，这类数据存在异质节点、异质关系、节点及本身的特征向量。首先根据边的交互关系将全图数据均分至各类型子图，将全图g根据类型依赖关系拆分成g1,g2,
…
,gk；而后使用基于均衡策略的metis算法进行快速划分，以解决带权的k路图划分问题；接下来，根据划分的各类型子图结果，计算矩阵间最大收益，以得到最佳合并方案；最后，根据合并方案查询原始数据集，以组合节点和边集，最终实现大规模数据的均衡划分，得到相应的划分结果。本发明能够在大规模数据划分下进行使用，其划分结果在各个分区内节点数量及类型大致一致，具备较好的负载均衡特性，对于临界节点复制比率不高，并有效的减少了跨分区通讯量，能够较好的支持异质图神经网络模型训练，减少总体训练时间。
8.本发明解决其技术问题所采用的技术方案包括如下步骤：
9.步骤1：加载异质的图神经网络数据g到内存以进行后续处理，所述图神经网络数据g数据为学术论文数据或社交网络数据或商品交易网络，存在异质节点、异质关系、节点及本身的特征向量。
10.步骤2：根据边的交互关系将全图数据均分至各类型子图，将全图g根据类型依赖关系拆分成g1,g2,
…
,gk，用于简化划分难度，减少原始图在初次划分中可能存在的不均衡问题，为后续步骤合并区块提供数据计算的依赖关系；
11.步骤2-1：对于属于图g的边类型φ(ei)，从中获取某类型边φ(ei)两侧的节点类型τ(nj),τ(nk)；
12.步骤2-2：在全图g中获取由步骤2-1中得到的类型τ(nj),τ(nk)及其相关边的所有关系边；
13.步骤2-3：将全图g类型拆分成多个异质类型拆分图g1,g2,
…
,gk，使得对于任意拆分图gi，存在唯一的τ(nk)∧φ(n)≠φ(k)，并且在所有拆分图中对于任意拆分图gi都存在图gj，使得两图间存在一种节点类型相同；
14.步骤3：使用多约束均衡策略的metis算法对步骤2中最终得到的g1,g2,
…
,gk单独进行图的划分，针对每个拆分图gi，都能获得各分区拆分结果g
i,j
，其中g
i,j
代表第i个拆分图中的第j个划分分区；
15.步骤3-1：对图gi使用metis划分方式，设置参数时根据异质数据集特性进行指定，对于异质图而言，建议设置边均衡及点均衡；
16.步骤3-2：为减少通信开销，使用distdgl中的边缘复制方法对边缘节点进行一定比例的复制处理，以保留连通边的其他分区节点信息。
17.步骤4：根据步骤3中的各图划分结果，计算最佳异质图合并区间方案；
18.步骤4-1：在步骤3中能够得到各分区拆分结果g
i,j
，其中g
i,ｊ
代表第i个拆分图中的
第j个划分分区；
19.步骤4-2：根据步骤2-3中的节点间的相关性，对所有拆分图中具有步骤2-3中描述关系的gi和gj，其中两图的分区分别记为g
i,k
和g
j,l
。根据g
i,ｋ
和ｇ
ｊ,ｌ
能够计算得到矩阵ａ，其中矩阵ａ中的每个元素ａ
i,j
代表g
i,k
和g
j,l
中各个分区间重叠节点的具体数目。
20.步骤4-3：使用约束函数，对各分区进行计算以获得最佳合并方案，其中约束函数如下所示，maximize为取得最大值，subject to表示约束条件。
[0021][0022][0023]
步骤4-4：根据步骤4-3中得到的最大收益z值，记录当时的计算矩阵x，其各个元素表示x
i,j
，其值表示为1取，0不取，即合并区间的方案。
[0024]
步骤5：根据步骤4中得到合并区间的方案构建划分子图。
[0025]
步骤5-1：根据步骤4-4中得到的合并方案，查询原图中的各节点，得到各个子图节点集vi[0026]
步骤5-2：根据步骤5-1中得到的节点集vi，查询原图中的各节点间的依赖关系，得到子图边集ei[0027]
步骤5-3：根据步骤5-1中的节点集vi及步骤5-2中的边集ei，即可构建划分子图gi＝(vi,ei)。
[0028]
本发明的有益效果如下：
[0029]
本发明能够在大规模数据下进行使用，方法拆分各类型节点并对各图进行快速划分，之后统计划分后各类型节点集重合度，以组合各类型节点点集，从而得到划分结果，其具备一定有效性，由于合理划分，在分布式计算中，跨计算节点分区读取数据量减少，从而降低了分区间的通讯频率。在此基础上，保持分区复制率无大幅度提升，最后能够划分结果提供给不同的分布式节点，并结合不同的异质图神经网络模型进行后续训练。
附图说明
[0030]
图1是实施例中节点含义示意图；
[0031]
图2是实施按类型拆分全图示意图；
[0032]
图3是实施划分各类型拆分图示意图；
[0033]
图4是实施分区重复度计算示意图；
[0034]
图5是实施根据点查询原数据集生成划分子图示意图；
具体实施方式
[0035]
下面结合附图和实施例对本发明进一步说明。
[0036]
具体来说，如图1所示，本实施例中的异质图数据集为学术数据集，包含的数据为论文、作者、机构、所属期刊等；其中的边与节点间存在相应关系，如《论文，所属领域，领域》，《论文，所属期刊，期刊》，《作者，撰写，论文》，《作者，隶属于，机构》等。
[0037]
步骤1：假定异质图数据集全图为g，图g包含对应的点集n以及边集e，以及相应的特征信息。假定其中某节点为n，其周边连通两点为n1和n2。n节点类型为τ(n)，相似的n1,n2节点类型为τ(n1),(n2)。假定n1,n2与节点n的连通边分别为e1,e2，其中e1,e2的边类型分别为φ(e1),φ(e2)，且e1＝(n1,t),e2＝(n2,t)。以目标节点出发的相关结构可以称之为元关系，简单表示为《τ(n1),φ(n),τ(n2)》。加载上述图数据g到内存，以进行后续处理。具体来说，点集n在例子中为论文、作者、机构、所属期刊等具体节点集合，边集e在例子中包含的关系为《论文，所属领域，领域》，《论文，所属期刊，期刊》，《作者，撰写，论文》，《作者，隶属于，机构》等。
[0038]
步骤2：根据边的交互关系将全图数据均分至各类型子图，将全图g根据类型依赖关系拆分成g1,g2,
…
,gk，用于简化划分难度，减少原始图在初次划分中可能存在的不均衡问题，为后续步骤合并区块提供数据计算的依赖关系；
[0039]
步骤2-1：对于属于图g的边类型φ(ei)，从中获取某类型边φ(ei)两侧的节点类型τ(nj),τ(nk)，具体来说，假设获取的边类型为“撰写”，那么需要获取“撰写”关系周边的节点类型“作者”和“论文”；
[0040]
步骤2-2：在全图g中获取由步骤2-1中得到的类型τ(nj),τ(nk)及其相关边的所有关系边；
[0041]
步骤2-3：将全图g类型拆分成多个异质类型拆分图g1,g2,
…
,gk，使得对于任意拆分图gi，存在唯一的τ(nk)∧φ(n)≠φ(k)，并且在所有拆分图中对于任意拆分图gi都存在图gj，使得两图间存在一种节点类型相同；
[0042]
具体来说，假定存在一定节点颜色表示含义同图1所示，其中的边与节点间存在相应关系，如《论文，所属领域，领域》，《论文，所属期刊，期刊》，《作者，撰写，论文》，《作者，隶属于，机构》等。如图2所示，将全图中依据边关系进行分解得到的图称为同类型拆分图，根据这种拆分方式能够得到三个拆分图，即图g1为“研究领域-论文”拆分图，图g2为“论文-作者”拆分图，图g3为：“作者-研究机构”拆分图。其中图g1与图g2间具备相同节点“论文”，其中图g2与图g3间具备相同节点“作者”，每张图中存在异质节点间的唯一关系，且仅存在一种节点作为两张图的联系；
[0043]
步骤3：使用多约束均衡策略的metis算法对步骤2中最终得到的g1,g2,
…
,gk单独进行图的划分，针对每个拆分图gi，都能获得各分区拆分结果g
i,j
，其中g
i,j
代表第i个拆分图中的第j个划分分区；
[0044]
步骤3-1：对图gi使用metis划分方式，设置参数时根据异质数据集特性进行指定，对于异质图而言，建议设置边均衡及点均衡；
[0045]
步骤3-2：为减少通信开销，使用distdgl中的边缘复制方法对边缘节点进行一定比例的复制处理，以保留连通边的其他分区节点信息。划分示意图如图3所示。
[0046]
步骤4：根据步骤3中的各图划分结果，计算最佳异质图合并区间方案；
[0047]
步骤4-1：在步骤3中能够得到各分区拆分结果g
i,j
，其中g
i,ｊ
代表第i个拆分图中的第j个划分分区；
[0048]
步骤4-2：根据步骤2-3中的节点间的相关性，对所有拆分图中具有步骤2-3中描述关系的gi和gj，其中两图的分区分别记为g
i,k
和g
j,l
，g
i,ｋ
为第i个图的第k个分区，g
j,l
为第j个图的第l个分区。根据g
i,k
和g
j,l
能够计算得到矩阵a，其中矩阵a中的每个元素a
i,j
代表g
i,k
和g
j,l
中各个分区间重叠节点的具体数目。
[0049]
步骤4-3：使用约束函数，对各分区进行计算以获得最佳合并方案，其中约束函数如下所示，maximize为取得最大值，subject to表示约束条件。
[0050][0051][0052]
在该步骤中，具体的讲，假定存在n
×
n矩阵a，给定目标函数其中x
i,j
是一个二元变量，表示矩阵中第i行第j列的数是否被取，令1表示取，0表示不取，a
i,j
是矩阵中第i行第j列的数。需要在满足目标和时取得z的最大值。直观的，矩阵中计算所得的重复度越高，总体节点间的关联度也就越高，从而可以为异质图类型的拆分结果提供有益的融合方案。
[0053]
步骤4-4：根据步骤4-3中得到的最大收益z值，记录当时的计算矩阵x，其各个元素表示x
i,j
，其值表示为1取，0不取，即合并区间的方案，其计算结果即为图4所示。
[0054]
步骤5：根据步骤4中得到合并区间的方案构建划分子图。
[0055]
步骤5-1：根据步骤4-4中得到的合并方案，查询原图中的各节点，得到各个子图节点集vi[0056]
步骤5-2：根据步骤5-1中得到的节点集vi，查询原图中的各节点间的依赖关系，得到子图边集ei[0057]
步骤5-3：根据步骤5-1中的节点集vi及步骤5-2中的边集ei，即可构建划分子图gi＝(vi,ei)，即图5中的划分结果。
[0058]
通过该实例可以看出，学术数据集得到了合理划分，这对下游分布式模型训练能够起到降低单轮训练时长，降低通讯频率的作用。

技术特征：
1.一种面向海量数据解决异质图神经网络数据划分不均衡处理的方法，其特征在于，包括如下步骤：步骤1：加载异质的图神经网络数据g到内存以进行后续处理，所述图神经网络数据g数据为学术论文数据或社交网络数据，存在异质节点、异质关系、节点及本身的特征向量。步骤2：根据边的交互关系将全图数据均分至各类型子图，将全图g根据类型依赖关系拆分成g1，g2，...，g
k
，用于简化划分难度，减少原始图在初次划分中可能存在的不均衡问题，为后续步骤合并区块提供数据计算的依赖关系；步骤2-1：对于属于图g的边类型φ(e
i
)，从中获取某类型边φ(e
i
)两侧的节点类型τ(n
j
)，τ(n
k
)；步骤2-2：在全图g中获取由步骤2-1中得到的类型τ(n
j
)，τ(n
k
)及其相关边的所有关系边；步骤2-3：将全图g类型拆分成多个异质类型拆分图g1，g2，...，g
k
，使得对于任意拆分图g
i
，存在唯一的τ(n
k
)∧φ(n)≠φ(k)，并且在所有拆分图中对于任意拆分图g
i
都存在图g
j
，使得两图间存在一种节点类型相同；步骤3：使用多约束均衡策略的metis算法对步骤2中最终得到的g1，g2，...，g
k
单独进行图的划分，针对每个拆分图g
i
，都能获得各分区拆分结果g
i，j
，其中g
i,j
代表第i个拆分图中的第j个划分分区；步骤3-1：对图g
i
使用metis划分方式，设置参数时根据异质数据集特性进行指定，对于异质图而言，建议设置边均衡及点均衡；步骤3-2：为减少通信开销，使用distdgl中的边缘复制方法对边缘节点进行一定比例的复制处理，以保留连通边的其他分区节点信息。步骤4：根据步骤3中的各图划分结果，计算最佳异质图合并区间方案；步骤4-1：在步骤3中能够得到各分区拆分结果g
i，j
，其中g
i，j
代表第i个拆分图中的第j个划分分区；步骤4-2：根据步骤2-3中的节点间的相关性，对所有拆分图中具有步骤2-3中描述关系的g
i
和g
j
，其中两图的分区分别记为g
i，k
和g
j，l
。根据g
i，k
和g
j，l
能够计算得到矩阵a，其中矩阵a中的每个元素a
i，j
代表g
i，k
和g
j，l
中各个分区间重叠节点的具体数目。步骤4-3：使用约束函数，对各分区进行计算以获得最佳合并方案，其中约束函数如下所示，maximize为取得最大值，subject to表示约束条件。to表示约束条件。步骤4-4：根据步骤4-3中得到的最大收益z值，记录当时的计算矩阵x，其各个元素表示x
i，j
，其值表示为1取，0不取，即合并区间的方案。
步骤5：根据步骤4中得到合并区间的方案构建划分子图。步骤5-1：根据步骤4-4中得到的合并方案，查询原图中的各节点，得到各个子图节点集v
i
步骤5-2：根据步骤5-1中得到的节点集v
i
，查询原图中的各节点间的依赖关系，得到子图边集e
i
步骤5-3：根据步骤5-1中的节点集v
i
及步骤5-2中的边集e
i
，即可构建划分子图g
i
＝(v
i
，e
i
)。

技术总结
本发明涉及一种面向海量数据解决异质图神经网络数据划分不均衡的处理方法，属于深度学习领域。该方法首先根据边的交互关系将全图数据均分至各类型子图，将全图G根据类型依赖关系拆分成Ｇ


技术研发人员：王柱 钱锦麟 安粱义 常远星 赵师瑶 郭斌 於志文
受保护的技术使用者：西北工业大学
技术研发日：2023.03.07
技术公布日：2023/7/19