一种基于图神经网络的种子集扩展方法及其系统

1.本发明属于大数据管理与分析技术领域，具体涉及一种基于图神经网络的种子集扩展方法及其系统，用于对图根据已知节点进行种子集扩展。


背景技术：

2.随着互联网的兴起，越来越多的网络受到了人们的广泛关注。在对各种复杂系统建模时，网络变得越来越重要，一般来说，网络由顶点(个体)和边(个体之间的关系)组成，且可将网络抽象成图。在商品推荐、犯罪团伙识别等应用场景中，人们感兴趣的是网络中某个社区(一些相似节点组成一个集合)的节点，这部分节点在某些情况下具有相似性，且通常情况下人们只知道该社区的少量节点。给定一个图中少量节点作为种子集，根据种子集扩展为一个更大的集合，以接近该社区的全部范围，扩展得到的节点需尽可能满足与种子集相似的条件。现已有很多方法可以用来解决种子集扩展问题，这些方法分为四类。第一类：邻居节点计数的方法有三种，neighbors、dn-neighbors是指已知社区标签下的邻居节点个数，outwardness计算社区内的度数量与社区外的度数量的差距、binomial prob计算社区中节点邻居的二项式概率。第二类：采用了贪心思想的算法有三种，modularity计算得到一个值，每次选择该值最高的节点作为扩展节点，是衡量社区划分的重要指标，也可用于种子集扩展中，set-modularity删除使其计算值增高的节点，添加使其计算值降低的节点，conductance计算了社区内部边与社区之间边的比例，是测量社区质量的重要标准。第三类：使用随机游走的方法有pagerank，在已有的文献中表述，pagerank能达到最好的扩展效果。第四类：augmented label propagation(动力标签传播，alp)算法依赖网络结构，利用动态传播和标签传播的思想来学习节点扩展。
3.传统的种子集扩展算法主要利用了标签传播以及图拓扑结构进行扩展。图拓扑结构知道节点与节点之间的连接信息，包括出度、入度等信息。主要根据出度入度以及边数量等信息计算重要节点，或通过边数量决定游走方式，通过不断迭代选择与种子集最相似的节点作为扩展的节点。但是，明显地，现实世界的网络不仅有结构信息，还带有多种属性信息，不难理解，这些信息对扩展可以起到正面作用。如引文网络，节点属性表示了文章摘要中的重要词汇，相同研究领域的文献可能会出现相同的关键词汇，这些关键词汇可以为找到相似文献起到关键性作用。因此，对于大部分图数据，利用节点属性可以对种子集扩展起到很好的帮助，但传统种子集扩展方法中，并没有结合节点属性进行种子集扩展的方式，使得扩展到的节点种子集节点数量较少。


技术实现要素：

4.针对上述现有的种子集扩展算法未使用节点属性进行种子集扩展导致扩展得到的节点属于种子集所在社区的节点数量较少的问题，本发明的目的在于，提供一种基于图神经网络的种子集扩展方法及其系统，本发明通过图神经网络(gnn)将图的结构信息、节点属性信息以及伪标签辅助训练，从图神经网络的角度利用这些信息，学习到关于节点属性
注意力系数和关于标签的注意力系数，对注意力系数单位化处理后，并将处理后的结果作为引导，为pagerank游走时提供具有倾向性的游走方式，使得节点游走过程中不是随机地游走到某一邻居节点，而是优先游走到关系更紧密的邻居节点，从而达到更好的扩展效果。
5.为了达到上述目的，本发明采用如下技术方案予以解决：
6.一方面，本发明给出一种基于图神经网络的种子集扩展方法，具体包括如下步骤：
7.步骤1，对于给定的图数据，获取图结构信息、节点属性，给定伪标签、种子集以及需要扩展节点个数k，通过em算法训练两个图神经网络，计算得到伪标签的注意力系数和节点特征的注意力系数；
8.步骤2、根据伪标签的注意力系数和节点特征的注意力系数计算得到概率矩阵a；
9.步骤3、根据需要扩展节点个数k，利用概率矩阵a中的概率系数引导pagerank进行游走，获取扩展到的节点。
10.进一步的，所述步骤1具体包括如下子步骤：
11.步骤11，获取图结构信息、节点属性、伪标签、种子集、需要扩展节点个数k；所述种子集是在数据集中相同类别的节点中取一定比例的节点得到；其中，图结构信息包括图节点id、边的连接信息；给定需要扩展的节点个数k；给定节点伪标签，初始伪标签矩阵为n
×
n的单位矩阵；
12.步骤12，将初始伪标签矩阵与邻接矩阵进行循环迭代处理，得到新的伪标签矩阵pl；
13.步骤13，对e步进行预训练：输入图结构信息和节点属性、伪标签矩阵pl，对gnn模型进行预训练；得到预训练后的gnn模型和未知标签节点的预测标签；
14.步骤14，进行第一次m步训练：输入图结构信息、伪标签矩阵pl，并将未知标签节点的预测标签作为损失函数的真实标签，训练gnn模型得到第一次m步训练后的训练模型及预测标签；
15.进行第一次e步训练：将第一次m步训练后的预测标签作为第一次e步训练的损失函数的真实标签，并输入图结构信息、节点特征，对预训练后的gnn模型进行e步训练，得到第一次e步训练后的预测标签；
16.进行第二次m步训练：将第一次e步训练后的预测标签作为第二次m步训练的损失函数的真实标签，并输入图结构信息、伪标签矩阵pl，对第一次m步训练后的模型进行第二次m步训练，得到第二次m步训练的预测标签，以及伪标签的注意力系数的集合，此处的伪标签的注意力系数在gnn模型中第二层gat模型中获取；
17.进行第二次e步训练：将第二次m步训练后的预测标签作为第二次e步训练的损失函数的真实标签，输入图结构信息、节点特征，对第一次e步训练后的模型进行第二次e步训练，得到第二次e步训练的节点特征的注意力系数的集合，此处的节点特征的注意力系数可在gnn模型中第二层gat模型中获取。
18.进一步的，所述步骤12具体包括如下操作：
19.第一步：将初始伪标签矩阵作为preds矩阵；
20.第二步：使用当前的preds矩阵与邻接矩阵相乘得到的结果替换当前的preds矩
阵；然后，使用当前的preds矩阵与伪标签矩阵相加得到的结果替换当前的preds矩阵；
21.第三步：将第二步输出的当前的preds矩阵中元素值大于1的值设置为1后，将得到的矩阵作为当前的preds矩阵；
22.第四步：重复执行第二步和第三步，共执行2次(即步骤12中第二步和第三步共执行3次)，将最后一次输出的preds矩阵赋值给伪标签矩阵，得到新的伪标签矩阵pl。
23.进一步的，所述步骤13和步骤14中的gnn模型中，第一层为gat模型，第二层也为gat模型，第三层为全连接层。
24.进一步的，所述步骤2具体包括如下子步骤：
25.步骤21，利用公式(11)计算得到节点i与邻居节点j的关于节点特征和伪标签的注意力系数均值e
ij
：
[0026][0027]
步骤22，利用公式(12)计算得到节点i与所有邻居节点关于特征和伪标签的注意力系数均值总和sei：
[0028][0029]
步骤23，利用公式(13)计算得到节点i游走到邻居节点j的概率系数；并将所有节点与其邻居节点的概率系数根据图的邻接矩阵组成概率矩阵
[0030][0031]
进一步的，所述步骤3具体包括如下子步骤：
[0032]
步骤31，对步骤2得到的概率矩阵a作为概率转移矩阵，采用个性化pagerank算法进行处理得到每个节点的pr值；
[0033]
步骤32，对得到的种子集以外的每个节点pr进行降序排序，取出pr值最高的k/t个节点；k为需要扩展的节点个数，为正整数，t为扩展过程的循环次数；
[0034]
步骤33，将得到的节点加入种子集得到新的种子集；
[0035]
步骤34，判断循环次数是否达到t次，是则执行步骤35，否则返回步骤31；循环t次后共得到k+|s|个节点；
[0036]
步骤35，从得到的节点中去掉初始种子集中的节点，共|s|个，得到扩展到的k个节点组成的节点集nk，扩展结束。
[0037]
另一方面，本发明给出一种基于图神经网络的种子集扩展系统，具体包括如下模块：
[0038]
注意力系数计算模块，用于实现如下功能：对于给定的图数据，获取图结构信息、节点属性，给定伪标签、种子集以及需要扩展节点个数k，通过em算法训练两个图神经网络，计算得到伪标签的注意力系数和节点特征的注意力系数；
[0039]
概率矩阵计算模块，用于根据伪标签的注意力系数和节点特征的注意力系数计算
得到概率矩阵a；
[0040]
节点扩展模块，用于根据需要扩展节点个数k，利用概率矩阵a中的概率系数引导pagerank进行游走，获取扩展到的节点。
[0041]
进一步的，所述注意力系数计算模块具体用于实现如下流程：
[0042]
步骤11，获取图结构信息、节点属性、伪标签、种子集、需要扩展节点个数k；所述种子集是在数据集中相同类别的节点中取一定比例的节点得到；其中，图结构信息包括图节点id、边的连接信息；给定需要扩展的节点个数k；给定节点伪标签，初始伪标签矩阵为n
×
n的单位矩阵；
[0043]
步骤12，将初始伪标签矩阵与邻接矩阵进行循环迭代处理，得到新的伪标签矩阵pl；
[0044]
步骤13，对e步进行预训练：输入图结构信息和节点属性、伪标签矩阵pl，对gnn模型进行预训练；得到预训练后的gnn模型和未知标签节点的预测标签；
[0045]
步骤14，进行第一次m步训练：输入图结构信息、伪标签矩阵pl，并将未知标签节点的预测标签作为损失函数的真实标签，训练gnn模型得到第一次m步训练后的训练模型及预测标签；
[0046]
进行第一次e步训练：将第一次m步训练后的预测标签作为第一次e步训练的损失函数的真实标签，并输入图结构信息、节点特征，对预训练后的gnn模型进行e步训练，得到第一次e步训练后的预测标签；
[0047]
进行第二次m步训练：将第一次e步训练后的预测标签作为第二次m步训练的损失函数的真实标签，并输入图结构信息、伪标签矩阵pl，对第一次m步训练后的模型进行第二次m步训练，得到第二次m步训练的预测标签，以及伪标签的注意力系数的集合，此处的伪标签的注意力系数在gnn模型中第二层gat模型中获取；
[0048]
进行第二次e步训练：将第二次m步训练后的预测标签作为第二次e步训练的损失函数的真实标签，输入图结构信息、节点特征，对第一次e步训练后的模型进行第二次e步训练，得到第二次e步训练的节点特征的注意力系数的集合，此处的节点特征的注意力系数可在gnn模型中第二层gat模型中获取。
[0049]
进一步的，所述概率矩阵计算模块具体用于实现如下流程：
[0050]
步骤21，利用公式(11)计算得到节点i与邻居节点j的关于节点特征和伪标签的注意力系数均值e
ij
：
[0051][0052]
步骤22，利用公式(12)计算得到节点i与所有邻居节点关于特征和伪标签的注意力系数均值总和sei：
[0053][0054]
步骤23，利用公式(13)计算得到节点i游走到邻居节点j的概率系数；并将所有节
点与其邻居节点的概率系数根据图的邻接矩阵组成概率矩阵
[0055][0056]
进一步的，所述节点扩展模块具体用于实现如下流程：
[0057]
步骤31，对步骤2得到的概率矩阵a作为概率转移矩阵，采用个性化pagerank算法进行处理得到每个节点的pr值；
[0058]
步骤32，对得到的种子集以外的每个节点pr进行降序排序，取出pr值最高的k/t个节点；k为需要扩展的节点个数，为正整数，t为扩展过程的循环次数；
[0059]
步骤33，将得到的节点加入种子集得到新的种子集；
[0060]
步骤34，判断循环次数是否达到t次，是则执行步骤35，否则返回步骤31；循环t次后共得到k+|s|个节点；
[0061]
步骤35，从得到的节点中去掉初始种子集中的节点，共|s|个，得到扩展到的k个节点组成的节点集nk，扩展结束。
[0062]
相较于现有技术，本发明的有益效果是：
[0063]
1、本发明首先通过em算法训练两个图神经网络，e步和m步两个步骤互相协作，期望e步的图神经网络预测的标签近似于m步的图神经网络预测的标签，在e步m步预测的节点标签很近似的情况后停止训练，此时可学习到最佳的节点特征表示以及预测到最准确的节点标签，通过最佳的节点特征表示和节点标签计算出相应的注意力系数，此时的注意力系数能够更准确地表示节点与邻居节点之间的关系。
[0064]
2、本发明的em算法的e步和m步训练的gnn模型中，主要使用到gat模型和全连接层，通过gat模型能够获得强有力的节点特征表示，gat模型在学习任意节点i特征表示的过程中，计算了节点i与其邻居节点的注意力系数和指向节点i本身的注意力系数，能够更准确地表示节点与邻居节点之间的关系，根据注意力系数聚合了节点i的邻居节点的特征以及节点i本身的特征，得到新的节点i特征表示后，再通过全连接层预测节点标签。
[0065]
3、根据伪标签的注意力系数和节点特征的注意力系数计算得到概率矩阵a，在这个过程中，先减去节点i指向自身的注意力系数，并对图中任意节点i与其邻居节点的注意力系数做单位化处理，得到节点i游走到邻居节点的概率系数，概率系数构成概率矩阵，为后续的个性化pagerank游走提供有倾向性的游走方式。
[0066]
4、个性化pagerank算法中，概率转移矩阵提供了随机游走的方式，在游走过程中，节点i游走到任意邻居节点j的概率是相等的。在本发明中，将在上一步中得到的概率矩阵作为概率转移矩阵，对于任意节点i，游走到节点j的概率是不同的，代入到个性化pagerank算法中，进行具有倾向性的游走，从而更准确的根据种子集进行扩展，得到更好的扩展结果。
[0067]
综上，本发明结合了标签和节点属性信息，并应用在种子集扩展过程中，经试验，扩展得到的节点集相比传统的种子集扩展算法，扩展得到的节点中有更多的节点属于种子集所在社区。
附图说明
[0068]
图1是本发明的基于图神经网络的种子集扩展方法的流程图。
[0069]
图2(a)是数据集pubmed在不同k取值且随机选择种子集情况下，本发明提出方法与传统种子集扩展算法比较召回率的结果展示。
[0070]
图2(b)是数据集citeseer在不同k取值且随机选取种子集情况下，本发明提出方法与传统种子集扩展算法比较召回率的结果展示。
[0071]
图3(a)是数据集citeseer在不同k取值且优选选择度高的节点作为种子集情况下，本发明提出方法与传统种子集扩展算法比较召回率的结果展示。
[0072]
图3(b)是数据集cora在不同k取值且优选选择度高的节点作为种子集情况下，本发明提出方法与传统种子集扩展算法比较召回率的结果展示。
[0073]
图4(a)是数据集citeseer在不同k取值且随机选取种子集情况下，本发明提出方法与传统种子集扩展算法比较扩展到同一社区的节点个数的结果展示。
[0074]
图4(b)是数据集cora在不同k取值且随机选取种子集情况下，本发明提出方法与传统种子集扩展算法比较扩展到同一社区的节点个数的结果展示。
[0075]
下面结合附图和具体实施方式对本发明进行详细说明。
具体实施方式
[0076]
如图1所示，本发明的基于图神经网络的种子集扩展方法(gnn-pagerank)，包括如下步骤：
[0077]
步骤1，对于给定的图数据，获取图结构信息、节点属性，给定伪标签、种子集以及需要扩展节点个数k，通过em算法训练两个图神经网络，计算得到伪标签的注意力系数和节点特征的注意力系数。
[0078]
具体操作如下：
[0079]
步骤11，获取图结构信息、节点属性、伪标签、种子集、需要扩展节点个数k。其中，种子集s随机获取，例如数据集citeseer中节点属于6个类别，其中类别为0的节点有224个，设置种子集占比为所属类别的10％，则种子集占比乘以种子集所属类别的节点个数，即为22个(向下取整)，则随机选取类别0的22个节点作为种子集(也可以设置其他类别，见本发明实施例。即种子集是在数据集中相同类别的节点中取一定比例的节点得到),种子集为已知标签的节点；其中，图结构信息包括图节点id、边的连接信息，为已知数据集；给定需要扩展的节点个数k,不同数据集的节点个数k不同；给定节点伪标签，初始伪标签矩阵为n
×
n的单位矩阵，伪标签矩阵的每一行即为一个节点的伪标签，n为节点个数，第i个节点的伪标签表示为第i列为1其他列为0的行向量，这样设置后，初始伪标签矩阵表示为单位矩阵。
[0080]
步骤12，将初始伪标签矩阵与邻接矩阵进行循环迭代处理，得到新的伪标签矩阵pl。包括如下操作：
[0081]
第一步：将初始伪标签矩阵作为preds矩阵；
[0082]
第二步：使用当前的preds矩阵与邻接矩阵相乘得到的结果替换当前的preds矩阵；然后，使用当前的preds矩阵与伪标签矩阵相加得到的结果替换当前的preds矩阵；
[0083]
第三步：将第二步输出的当前的preds矩阵中元素值大于1的值设置为1后，将得到的矩阵作为当前的preds矩阵；
[0084]
第四步：重复执行第二步和第三步，共执行2次(即步骤12中第二步和第三步共执行3次)，将最后一次输出的preds矩阵赋值给伪标签矩阵，得到新的伪标签矩阵pl；
[0085]
步骤13，对e步进行预训练：输入图结构信息和节点属性、伪标签矩阵pl(由步骤2得到)，对gnn模型进行预训练(训练200次)；得到预训练后的gnn模型和未知标签节点的预测标签；
[0086]
步骤14，进行第一次m步训练：输入图结构信息、伪标签矩阵pl(由步骤2得到)，并将未知标签节点的预测标签作为损失函数的真实标签，训练gnn模型(训练100次)得到第一次m步训练后的训练模型及预测标签；
[0087]
进行第一次e步训练：将第一次m步训练后的预测标签作为第一次e步训练的损失函数的真实标签，并输入图结构信息、节点特征(即节点属性)，对预训练后的gnn模型进行e步训练(训练100次)，得到第一次e步训练后的预测标签；
[0088]
进行第二次m步训练：将第一次e步训练后的预测标签作为第二次m步训练的损失函数的真实标签，并输入图结构信息、伪标签矩阵pl，对第一次m步训练后的模型进行第二次m步训练(训练100次)，得到第二次m步训练的预测标签，以及伪标签的注意力系数的集合，此处的伪标签的注意力系数在gnn模型中第二层gat模型中获取；
[0089]
进行第二次e步训练：将第二次m步训练后的预测标签作为第二次e步训练的损失函数的真实标签，输入图结构信息、节点特征，对第一次e步训练后的模型进行第二次e步训练(训练100次)，得到第二次e步训练的节点特征的注意力系数的集合，此处的节点特征的注意力系数可在gnn模型中第二层gat模型中获取。
[0090]
步骤13和步骤14中，所述gnn模型中，第一层为gat模型，第二层也为gat模型，第三层为全连接层。
[0091]
步骤1通过em算法训练两个图神经网络，e步训练的目标是在预测节点标签的过程中计算出节点特征的注意力系数，m步训练的目标是通过学习邻居节点的节点标签，计算出关于标签的注意力系数，在em算法过程中，在e步预测出标签将其作为真实标签为m步进行标签预测，m步输出的预测标签为e步提供，e步m步之间互相协作，期望e步预测的标签近似于m步预测的标签，e步m步在节点标签很近似的情况下停止训练，学习到最佳的节点特征表示以及节点标签，另外，e步和m步训练的gnn模型中，第一层为gat模型，第二层为gat模型，第三层为全连接层，通过gat模型能够获得强有力的特征表示学习，最终获取节点与邻居节点之间的注意力系数，能够更准确地表示节点与邻居节点之间的关系。
[0092]
步骤2、根据伪标签的注意力系数和节点特征的注意力系数计算得到概率矩阵a，具体操作如下：
[0093]
步骤21，利用公式(11)计算得到节点i与邻居节点j的关于节点特征和伪标签的注意力系数均值e
ij
：
[0094][0095]
步骤22，利用公式(12)计算得到节点i与所有邻居节点关于特征和伪标签的注意力系数均值总和sei：
[0096][0097]
步骤23，利用公式(13)计算得到节点i游走到邻居节点j的概率系数；并将所有节点与其邻居节点的概率系数根据图的邻接矩阵组成概率矩阵
[0098][0099]
步骤3、利用概率系数引导pagerank进行游走，获取扩展到的节点。
[0100]
具体操作如下：
[0101]
设需要扩展的节点个数为k，将扩展过程划分为t次(t取值为使得k可被t整除的正整数)进行扩展，即循环t次，每次的循环过程如下：
[0102]
步骤31，对步骤2得到的概率矩阵a作为概率转移矩阵，采用个性化pagerank算法进行处理得到每个节点的pr值。
[0103]
具体的，在个性化pagerank算法中，设置种子集的pr值为1，选择其余节点的pr值设置为0，阻尼系数d设置为0.85。
[0104]
步骤32，对得到的种子集以外的每个节点pr进行降序排序，取出pr值最高的k/t个节点。(k为正整数，每个实例中k取值有所不同)
[0105]
步骤33，将得到的节点加入种子集得到新的种子集。
[0106]
步骤34，判断循环次数是否达到t次，是则执行步骤35，否则返回步骤31；循环t次后共得到k+|s|个节点；
[0107]
步骤35，从得到的节点中去掉初始种子集中的节点(共|s|个)，得到扩展到的k个节点组成的节点集nk，扩展结束。
[0108]
为了验证本发明的可行性和有效性，本发明通过多组实验测试了给出的模型，并采用相对召回率来评估本发明的方法与pagerank算法的扩展效果。实验中所采用networkx版本为2.3，编译语言python3.6。实验中所使用的计算机处理器genuine intel(r)cpu@2.90ghz，内存64g，操作系统为windows10。
[0109]
相关术语：召回率：是覆盖面的度量，度量有多少歌正例被分为正例，recall＝tp/(tp+fn)＝tp/p。在种子集扩展问题中，召回率就是分为绝对召回率和相对召回率。种子集扩展的相对召回率为|p∩u|/|c-s|，绝对召回率为|p∩c|/|c|。相对召回率为属于种子集社区所在的节点，在种子集所在社区中所有节点减去种子集的占比。绝对召回率为属于种子集社区所在的节点在种子集所在社区中所有节点的占比。
[0110]
所有实例中，相关参数设置如下：图神经网络学习率为0.005，训练过程中使用的优化器是adam sgd,中间隐藏层维度为8，权值衰减为0.0005。e步m步的图神经网络中，均是先用dropout函数对输入的值(e步输入节点特征，m步输入伪标签)进行处理，dropout函数中神经元被选中的概率设置为0.6，处理得到特征值。然后接gat模型，设置多头注意力nheads为8，再通过激活函数relu进行处理，再接droput函数，dropout函数中神经元被选中的概率依旧设置为0.6，然后是第二个gat层，nheads设置为1，再通过relu激活函数进行处理，最后通过全连接层的两个参数分别设置为隐藏层维度8和数据集类别数classes。
[0111]
实施例中使用到的数据集为pubmed、citeseer、cora。数据集均为引文网络数据集，为公开数据集。
[0112]
datasetpubmedcoraciteseerclasses376nodes1971727083327edges4433854294732features50014333703
[0113]
实施例1：
[0114]
将数据集中同一标签的所有节点为一个社区，本实施例使用数据集pubmed、citeseer。数据集pubmed有3个类别，分别取k＝[400,800,1200,1600,2000,2400,2800],对0、1、2这3个类别分别进行5次随机选择种子集(共15次)，种子集选取占比为|s|/|c|＝0.1(种子集的节点个数占所述类别的节点个数)；t取10次(对于不同的k分10次扩展得到)，计算召回率并取均值，得到数据集pubmed在不同k下的召回率，本发明的gnn-pagerank算法是使用节点属性情况下计算得到的召回率，结果如图2a所示，gnn-pagerank算法的召回率明显高于传统算法pagerank和dn-pagerank。对于数据集citeseer,有6个类别，对于类别分别取k＝[40,80,120,160,200,240,280]，对0、1、2、3、4、5这6个类别分别对种子集进行5次随机选择(共30次)，种子集选取占比为|s|/|c|＝0.1，t取10(对于每个k分10次进行扩展)，计算召回率并取平均值，得到数据集citeseer在不同k下的召回率,结果如图2b所示，gnn-pagerank算法的召回率明显高于传统种子集扩展算法pagerank和dn-pagerank。
[0115]
实施例2：
[0116]
选择度高的节点作为种子集，设置同一标签的所有节点为一个社区，，选择该社区所有节点度高的节点作为种子集。数据集citeseer有6个类别，分别根据每个类别的节点的度数进行降序排序，选择每个类中节点的度排前10％的节点作为种子集，取k＝[100,200,300,400,500],t取值为10，对每个k，分10次进行扩展，得到每个类在不同k条件下的扩展结果，计算每个类的召回率，并取6个类在不同k的条件下召回率的均值。结果如图3(a)所示，本发明的gnn-pagerank算法的召回率明显高于传统种子集扩展算法的召回率，即扩展的准确率高于传统种子集扩展算法。数据集cora有7个类别，分别根据每个类别的节点的度进行降序排序，选择每个类中节点度排前10％的节点作为种子集，取k＝[100,200,300,400,500,600]，t取值为10，对每个k，分10次进行扩展，得到每个类在不同k条件下的扩展结果，计算每个类不同k下的召回率，取均值。结果如图3(b)所示，在k大于200后，gnn-pagerank算法的召回率略高于传统种子集扩展算法dn-pagerank，远高于传统种子集扩展算法pagerank。
[0117]
实施例3：
[0118]
设置同一标签的所有节点为一个社区，随机获取种子集，种子集在同一社区的占比为0.3，比较找到的节点个数。对于数据集citeseer，对于数据集citeseer,有6个类别，对于类别0、1、2、3、4、5，分别取k＝[40,80,120,160,200,240,280]，在不同k条件下，对6个类别分别对种子集进行5次随机选择(共30次)，取均值，并将其作为不同的k扩展得到的节点个数。t取10(对于每个k分为10次进行扩展)，在不同k条件下扩展得到的节点个数结果如图4a所示，明显地，本发明的gnn-pagerank算法扩展得到的节点个数多于传统种子集扩展算
法pagerank和dn-pagerank算法。同样地，对于数据集pubmed，有3个类别，对于类别0、1、2，分别取k＝[400,800,1200,1600,2000,2400,2800,3200],在不同k条件下，对3个类分别对种子集进行5次随机选择(共30次)，取均值，并将其作为不同的k扩展得到的节点个数。t取10(对于每个k分为10次进行扩展)，在不同k条件下扩展得到节点个数结果如图4b所示，明显地，pagerank算法扩展得到的节点个数远低于gnn-pagerank算法，dn-pagerank算法扩展得到的节点个数略低于gnn-pagerank算法。
[0119]
综上可知，本发明提出的方法(gnn-pagerank)在种子集扩展问题上，不论从召回率角度还是从扩展得到的节点个数角度上，在给定的种子集情况不同的条件下，gnn-pagerank算法扩展效果大部分情况下优于传统的种子集扩展算法。

技术特征：
1.一种基于图神经网络的种子集扩展方法，其特征在于，具体包括如下步骤：步骤1，对于给定的图数据，获取图结构信息、节点属性，给定伪标签、种子集以及需要扩展节点个数k，通过em算法训练两个图神经网络，计算得到伪标签的注意力系数和节点特征的注意力系数；步骤2、根据伪标签的注意力系数和节点特征的注意力系数计算得到概率矩阵a；步骤3、根据需要扩展节点个数k，利用概率矩阵a中的概率系数引导pagerank进行游走，获取扩展到的节点。2.如权利要求1所述的基于图神经网络的种子集扩展方法，其特征在于，所述步骤1具体包括如下子步骤：步骤11，获取图结构信息、节点属性、伪标签、种子集、需要扩展节点个数k；所述种子集是在数据集中相同类别的节点中取一定比例的节点得到；其中，图结构信息包括图节点id、边的连接信息；给定需要扩展的节点个数k；给定节点伪标签，初始伪标签矩阵为n
×
n的单位矩阵；步骤12，将初始伪标签矩阵与邻接矩阵进行循环迭代处理，得到新的伪标签矩阵pl；步骤13，对e步进行预训练：输入图结构信息和节点属性、伪标签矩阵pl，对gnn模型进行预训练；得到预训练后的gnn模型和未知标签节点的预测标签；步骤14，进行第一次m步训练：输入图结构信息、伪标签矩阵pl，并将未知标签节点的预测标签作为损失函数的真实标签，训练gnn模型得到第一次m步训练后的训练模型及预测标签；进行第一次e步训练：将第一次m步训练后的预测标签作为第一次e步训练的损失函数的真实标签，并输入图结构信息、节点特征，对预训练后的gnn模型进行e步训练，得到第一次e步训练后的预测标签；进行第二次m步训练：将第一次e步训练后的预测标签作为第二次m步训练的损失函数的真实标签，并输入图结构信息、伪标签矩阵pl，对第一次m步训练后的模型进行第二次m步训练，得到第二次m步训练的预测标签，以及伪标签的注意力系数的集合，此处的伪标签的注意力系数在gnn模型中第二层gat模型中获取；进行第二次e步训练：将第二次m步训练后的预测标签作为第二次e步训练的损失函数的真实标签，输入图结构信息、节点特征，对第一次e步训练后的模型进行第二次e步训练，得到第二次e步训练的节点特征的注意力系数的集合，此处的节点特征的注意力系数可在gnn模型中第二层gat模型中获取。3.如权利要求1所述的基于图神经网络的种子集扩展方法，其特征在于，所述步骤12具体包括如下操作：第一步：将初始伪标签矩阵作为preds矩阵；第二步：使用当前的preds矩阵与邻接矩阵相乘得到的结果替换当前的preds矩阵；然后，使用当前的preds矩阵与伪标签矩阵相加得到的结果替换当前的preds矩阵；第三步：将第二步输出的当前的preds矩阵中元素值大于1的值设置为1后，将得到的矩阵作为当前的preds矩阵；
第四步：重复执行第二步和第三步，共执行2次(即步骤12中第二步和第三步共执行3次)，将最后一次输出的preds矩阵赋值给伪标签矩阵，得到新的伪标签矩阵pl。4.如权利要求1所述的基于图神经网络的种子集扩展方法，其特征在于，所述步骤13和步骤14中的gnn模型中，第一层为gat模型，第二层也为gat模型，第三层为全连接层。5.如权利要求1所述的基于图神经网络的种子集扩展方法，其特征在于，所述步骤2具体包括如下子步骤：步骤21，利用公式(11)计算得到节点i与邻居节点j的关于节点特征和伪标签的注意力系数均值e
ij
：步骤22，利用公式(12)计算得到节点i与所有邻居节点关于特征和伪标签的注意力系数均值总和se
i
：步骤23，利用公式(13)计算得到节点i游走到邻居节点j的概率系数；并将所有节点与其邻居节点的概率系数根据图的邻接矩阵组成概率矩阵其邻居节点的概率系数根据图的邻接矩阵组成概率矩阵6.如权利要求1所述的基于图神经网络的种子集扩展方法，其特征在于，所述步骤3具体包括如下子步骤：步骤31，对步骤2得到的概率矩阵a作为概率转移矩阵，采用个性化pagerank算法进行处理得到每个节点的pr值；步骤32，对得到的种子集以外的每个节点pr进行降序排序，取出pr值最高的k/t个节点；k为需要扩展的节点个数，为正整数，t为扩展过程的循环次数；步骤33，将得到的节点加入种子集得到新的种子集；步骤34，判断循环次数是否达到t次，是则执行步骤35，否则返回步骤31；循环t次后共得到k+|s|个节点；步骤35，从得到的节点中去掉初始种子集中的节点，共|s|个，得到扩展到的k个节点组成的节点集n
k
，扩展结束。7.一种基于图神经网络的种子集扩展系统，其特征在于，具体包括如下模块：注意力系数计算模块，用于实现如下功能：对于给定的图数据，获取图结构信息、节点属性，给定伪标签、种子集以及需要扩展节点个数k，通过em算法训练两个图神经网络，计算得到伪标签的注意力系数和节点特征的注意力系数；概率矩阵计算模块，用于根据伪标签的注意力系数和节点特征的注意力系数计算得到概率矩阵a；节点扩展模块，用于根据需要扩展节点个数k，利用概率矩阵a中的概率系数引导
pagerank进行游走，获取扩展到的节点。8.如权利要求1所述的基于图神经网络的种子集扩展方法，其特征在于，所述注意力系数计算模块具体用于实现如下流程：步骤11，获取图结构信息、节点属性、伪标签、种子集、需要扩展节点个数k；所述种子集是在数据集中相同类别的节点中取一定比例的节点得到；其中，图结构信息包括图节点id、边的连接信息；给定需要扩展的节点个数k；给定节点伪标签，初始伪标签矩阵为n
×
n的单位矩阵；步骤12，将初始伪标签矩阵与邻接矩阵进行循环迭代处理，得到新的伪标签矩阵pl；步骤13，对e步进行预训练：输入图结构信息和节点属性、伪标签矩阵pl，对gnn模型进行预训练；得到预训练后的gnn模型和未知标签节点的预测标签；步骤14，进行第一次m步训练：输入图结构信息、伪标签矩阵pl，并将未知标签节点的预测标签作为损失函数的真实标签，训练gnn模型得到第一次m步训练后的训练模型及预测标签；进行第一次e步训练：将第一次m步训练后的预测标签作为第一次e步训练的损失函数的真实标签，并输入图结构信息、节点特征，对预训练后的gnn模型进行e步训练，得到第一次e步训练后的预测标签；进行第二次m步训练：将第一次e步训练后的预测标签作为第二次m步训练的损失函数的真实标签，并输入图结构信息、伪标签矩阵pl，对第一次m步训练后的模型进行第二次m步训练，得到第二次m步训练的预测标签，以及伪标签的注意力系数的集合，此处的伪标签的注意力系数在gnn模型中第二层gat模型中获取；进行第二次e步训练：将第二次m步训练后的预测标签作为第二次e步训练的损失函数的真实标签，输入图结构信息、节点特征，对第一次e步训练后的模型进行第二次e步训练，得到第二次e步训练的节点特征的注意力系数的集合，此处的节点特征的注意力系数可在gnn模型中第二层gat模型中获取。9.如权利要求1所述的基于图神经网络的种子集扩展方法，其特征在于，所述概率矩阵计算模块具体用于实现如下流程：步骤21，利用公式(11)计算得到节点i与邻居节点j的关于节点特征和伪标签的注意力系数均值e
ij
：步骤22，利用公式(12)计算得到节点i与所有邻居节点关于特征和伪标签的注意力系数均值总和se
i
：步骤23，利用公式(13)计算得到节点i游走到邻居节点j的概率系数；并将所有节点与其邻居节点的概率系数根据图的邻接矩阵组成概率矩阵
10.如权利要求1所述的基于图神经网络的种子集扩展方法，其特征在于，所述节点扩展模块具体用于实现如下流程：步骤31，对步骤2得到的概率矩阵a作为概率转移矩阵，采用个性化pagerank算法进行处理得到每个节点的pr值；步骤32，对得到的种子集以外的每个节点pr进行降序排序，取出pr值最高的k/t个节点；k为需要扩展的节点个数，为正整数，t为扩展过程的循环次数；步骤33，将得到的节点加入种子集得到新的种子集；步骤34，判断循环次数是否达到t次，是则执行步骤35，否则返回步骤31；循环t次后共得到k+|s|个节点；步骤35，从得到的节点中去掉初始种子集中的节点，共|s|个，得到扩展到的k个节点组成的节点集n
k
，扩展结束。

技术总结
本发明公开了一种基于图神经网络的种子集扩展方法及系统，该方法具体包括如下步骤：步骤1，对于给定的图数据，获取图结构信息、节点属性，给定伪标签、种子集以及需要扩展节点个数K，通过EM算法训练两个图神经网络，计算得到伪标签的注意力系数和节点特征的注意力系数；步骤2、根据伪标签的注意力系数和节点特征的注意力系数计算得到概率矩阵A；步骤3、根据需要扩展节点个数K，利用概率矩阵A中的概率系数引导PageRank进行游走，获取扩展到的节点。本发明结合了标签和节点属性信息，并应用在种子集扩展过程中，经试验，扩展得到的节点集相比传统的种子集扩展算法，扩展得到的节点中有更多的节点属于种子集所在社区。更多的节点属于种子集所在社区。更多的节点属于种子集所在社区。


技术研发人员：梁春泉 王紫 陈航 赵航
受保护的技术使用者：西北农林科技大学
技术研发日：2022.01.30
技术公布日：2022/5/25