一种基于随机子图样本分区的图分类方法

1.本发明涉及图分类技术领域，具体为一种基于随机子图样本分区的图分类方法。


背景技术：

2.图作为一种重要的数据结构，被广泛应用于化学信息，社交网络等重要领域。针对图结构的研究，可以分为多个研究方向，如图分类，图聚类，频繁子图挖掘等等。其中，图分类是一项重要的数据挖掘任务，其目的是将多图数据划分为两个或多个类别。建立自动化的图分类模型用于识别不同的图类之间所包含的有区别的图特征是具有非常重要的实际意义的。图分类是给定一组图，通过学习图和对应类别标签的映射关系，预测未知图的类别标签。
3.现有的基于子图网络的方法主要存在两个问题。一是多样性不足的问题。对子图进行抽样存在由于抽样技术关注以节点度高的节点或边的中介中心性排名靠前的边作为起始节点和起始边，而忽略了优先级较低的节点或边。但这并不代表这些少数结构作用效果不高。二是对大规模的子图的处理能力不足问题。在解决完多样性不足问题后，子图的数量可能呈指数级爆炸增长，甚至成为一个np问题。这对计算资源和计算能力是一项重大的考验，目前市场上普遍存在的是分而治之的方法，例如mapreduce方法将图数据切分成块级样本，放入到集群中进行计算。但这类方法仍然需要有足够的集群和计算能力，对中小型企业是不友好的。


技术实现要素：

4.针对现有技术的不足，本发明提供了一种基于随机子图样本分区的图分类方法，解决了现有基于采样子图网络的节点分类方法多样性不足和对大规模的子图的处理能力不足的问题。
5.为实现以上目的，本发明通过以下技术方案予以实现：一种基于随机子图样本分区的图分类方法，包括rgssp，所述rgssp由子图生成模型、rssp以及分类器模块组成，所述rssp为随机子图样本分区，所述rgssp是尽可能的生成数量足够的子图结构形成子图数据集，再通过将子图数据集切分成为具有代表性的块级样本，将少量块级样本代替完整数据集进行图分类。
6.优选的，一种基于随机子图样本分区的图分类方法，包括以下步骤：
7.步骤一：子图生成模型
8.通过sgn方法生成sgn子图以后，使用的抽样策略关注sgn子图的所有节点和边，并通过抽样不同阶次的sgn获得大量的子图，此外，更高阶的sgn可以获得更多潜在的结构，但由于本研究的研究对象为生成的大量小图，每个小图可能只包含十几个顶点和十几条边，对小图进行高阶转换，转换出来的子图信息会越来越少，甚至于3阶的子图可能就只剩下一个节点，所以，只选择将原始网络生成一阶和二阶子图；在采用的数据集上，在一阶子图和二阶子图上进行抽样子图集生成所达到的规模很多已经到了千万级别，在这个基础上生成
的子图规模会远远超过于原始网络进行抽样生成的子图规模，因此，样本分布不均衡会导致模型对一阶和二阶子图有倾向性，原始网络生成的子图结构很少会出现在rssp样本块中，为了保证rssp进行分块时每一个阶次的子图数据集都有相同的概率被选中，需要对原始网络生成的抽样子图进行向上采样，直到其规模与一阶和二阶抽样子图数据集规模相同，在算法1构建子图生成模型算法中，生成了原始网络生成的抽样子图，一阶抽样子图以及二阶抽样子图，考虑到一阶子图所提供的子图结构是最丰富的，因此以一阶子图所生成的抽样子图规模作为基准，先对原始网络g进行子图抽取，获得0阶抽样子结构接着对原始网络g进行sgn子图挖掘，生成一阶子图g
sub1
，再对g
sub1
进行抽样子图抽取生成一阶子图数据集此时的数量规模为不同阶的规模基准，由于一阶子图的规模会比零阶子图规模多出上百万的数量，因此需要对零阶子图进行上采样，直到规模与一阶子图规模相同，最后，对进行sgn子图挖掘，生成二阶子图数据集二阶子图数据集可以挖掘出更多潜在的子图结构，最后，将经过上采样的和都放入g
sub
集合中，再将g
sub
集合最终放入分类器进行分析；
9.步骤二：随机子图样本划分
10.rssp模型是为了解决大规模图数据的处理问题，在抽样子图的基础上进行随机样本分区，即rssp算法，rssp确保每个数据块都是大数据的随机样本，从而可以用来预估大数据的统计特性，rssp子图随机样本划分针对图数据，通过不同特征在同一数据集的rssp数据块之间具有相似的概率分布，证明了rssp算法可以将完整数据集切分成具有相似概率的rssp块，rssp算法的主要性质包括两个定义；
11.步骤三：基于rssp块的集成分析
12.基于rssp块的渐进集成学习采用逐步式过程从多批rssp块中进行集成模型学习，每批从t中选取的rssp块都是不可替换，大小相等的，逐步式过程是为了避免在同一批次中加载大量的rssp块，占用有限资源甚至导致系统内存不足，逐步式集成模型使得资源有限的计算集群可以扩展到更大的数据集。
13.优选的，所述rssp算法的定义如下：
14.定义1(数据集划分):设数据集g
sub
＝{x1,x2,...,xn}包含n个对象，t为可以将g
sub
划分为多个子集t＝{g
sub_1
,g
sub_2
,...,g
sub_k
}的操作，如果子集t满足下面两个条件，可以称之为g
sub
的一个分区；
15.条件1：
16.条件2：且i≠j
17.以上t是对g
sub
的分区操作，每一块g
sub_k
称之为g
sub
的数据块样本，上述定义是将完整数据集划分为不同的数据块，但这些数据块是不具有与完整数据集特征概率分布的性质，一般不能作为随机样本来分析大数据集样本；
18.定义2(随机子图样本划分):假设g
sub
表示由子图生成模型生成的海量图数据集，f(
·
)是g
sub
的样本分布函数，t为可以将g
sub
划分为多个子集t＝{g
′
sub_1
,g
′
sub_2
,...,g
′
sub_k
}的操作，g’sub
∈g
sub
表示完整数据集的样本分区，则如果
[0019][0020]
称t为g
sub
完整子图数据集的随机样本分区，其中，表示为g
′
sub_k
的样本分布函数，e(
·
)为其期望值。每个g
′
sub_k
为一个rssp块，t称为g
sub
上的rssp操作，在rssp中，本文采用度分布，图概率密度，平均聚集系数以及半径四个度量指标作为子图数据集的特征描述，即每一个rssp块与完整数据集中的四个度量指标概率分布一致；
[0021]
由子图生成模型生成了海量子图g
sub
后，通过rssp模型算法对g
sub
进行块级抽样，每一块rssp块需要抽取多大，是一个衍生的新问题，提出了基于图数据复杂度的块大小(graph data-driven complexity，gddc)测量算法：
[0022][0023]
其中，g
sub
代表生成的子图数据集，为在显著水平α》0，错误率e》0的情况下，双样本进行z分位数对应值，可以查表获得，c(g
sub
)代表生成的子图数据集的数据复杂度，可以由fisher判别式求得，fisher判别式关注的是差异化最大的特征维度，对于一个多维问题，只要存在一个区别特征就可以描述问题；
[0024][0025]
其中，μ和σ分别代表不同类的平均值和方差。
[0026]
本发明提供了一种基于随机子图样本分区的图分类方法。具备以下有益效果：
[0027]
1、本发明通过在基于sgn技术情况下，通过子图生成模型将对不同阶次的sgn子图进行采样，该采样算法覆盖所有节点和所有边，生成的子图数量可以达到上亿级别，有效解决了多样性不足的问题，挖掘出了更多的子图结构。同时设计了一个随机子图样本分区的计算框架，通过将完整图数据集切分成块级样本，这些块级样本在概率分布上与完整数据集一致，可以代替完整数据集进行近似计算，解决了由子图生成模型带来的大规模图数据处理问题，也填补了现有技术处理大规模子图的能力不足问题。
[0028]
2、本发明通过在sgn技术的基础上，抽样方法没有采用对节点度或边的中介中心性进行排名从而抽样出多数结构的算法，而是尽可能关注所有节点和边进行子图扩展，能够有效的保证了子图结构的多样性使得分类器训练更精准。其次，在获得子图结构以后，本发明没有采取特征融合的方法，而是将所有子图数据集切分成不同的rssp块，通过小部分数据块代替完整数据集进行近似计算，大大减少了计算压力和计算时间，提高了图分类的效率。
附图说明
[0029]
图1为本发明的rgssp框架流程图；
[0030]
图2为本发明的子图生成模型算法流程图；
[0031]
图3为本发明的rssp块算法流程图；
[0032]
图4为本发明的rssp生成流程图；
[0033]
图5为本发明的rssp集成分析流程图；
[0034]
图6为本发明的rssp块与完整数据集的节点度概率分布对比图；
[0035]
图7为本发明的rssp块与完整数据集的图密度概率分布对比图；
[0036]
图8为本发明的rssp块与完整数据集的平均聚集系数概率分布对比图；
[0037]
图9为本发明的rssp块与完整数据集的半径概率分布对比图。
具体实施方式
[0038]
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0039]
实施例一：
[0040]
如图1-9所示，本发明实施例提供一种基于随机子图样本分区的图分类方法，包括rgssp，rgssp由子图生成模型、rssp以及分类器模块组成，rssp为随机子图样本分区，rgssp是尽可能的生成数量足够的子图结构形成子图数据集，再通过将子图数据集切分成为具有代表性的块级样本，将少量块级样本代替完整数据集进行图分类。
[0041]
如图4所示，第一个保护点是在获得大规模的子图数据集后，将其切分成p份不重叠的数据集，再通过第二个步骤对每一份数据集中的样本打乱，切分成q份，随机从p个数据集中不放回抽取q次拼凑出一份新的数据集，该数据集为可以代替完整数据集进行近似分析的rssp块。
[0042]
图5展示了多批rssp块上运行集成学习算法的过程。每个rssp块经过f函数(即对每块rssp块进行基模型建模)进行基础模型建模后。如从第一批次中，g个rssp块经过f函数建立了g个基模型存储于π1中，将π1集成到π中。再从第二批次集成π2到π中。图5展示了两个批次以上的rssp块进行集成，一般批次的数量为奇数。每个批次对数据进行结果判断，最后将奇数个结果进行汇总，通过“投票法”选取出最后的分类结果。
[0043]
一种基于随机子图样本分区的图分类方法，包括以下步骤：
[0044]
步骤一：子图生成模型
[0045]
通过sgn方法生成sgn子图以后，使用的抽样策略关注sgn子图的所有节点和边，并通过抽样不同阶次的sgn获得大量的子图，此外，更高阶的sgn可以获得更多潜在的结构，但由于本研究的研究对象为生成的大量小图，每个小图可能只包含十几个顶点和十几条边，对小图进行高阶转换，转换出来的子图信息会越来越少，甚至于3阶的子图可能就只剩下一个节点，所以，只选择将原始网络生成一阶和二阶子图；在采用的数据集上，在一阶子图和二阶子图上进行抽样子图集生成所达到的规模很多已经到了千万级别，在这个基础上生成的子图规模会远远超过于原始网络进行抽样生成的子图规模，因此，样本分布不均衡会导致模型对一阶和二阶子图有倾向性，原始网络生成的子图结构很少会出现在rssp样本块中，为了保证rssp进行分块时每一个阶次的子图数据集都有相同的概率被选中，需要对原始网络生成的抽样子图进行向上采样，直到其规模与一阶和二阶抽样子图数据集规模相同，整体算法如图2所示。在算法1构建子图生成模型算法中，生成了原始网络生成的抽样子图，一阶抽样子图以及二阶抽样子图，考虑到一阶子图所提供的子图结构是最丰富的，因此以一阶子图所生成的抽样子图规模作为基准，先对原始网络g进行子图抽取，获得0阶抽样
子结构接着对原始网络g进行sgn子图挖掘，生成一阶子图g
sub1
，再对g
sub1
进行抽样子图抽取生成一阶子图数据集此时的数量规模为不同阶的规模基准，由于一阶子图的规模会比零阶子图规模多出上百万的数量，因此需要对零阶子图进行上采样，直到规模与一阶子图规模相同，最后，对进行sgn子图挖掘，生成二阶子图数据集二阶子图数据集可以挖掘出更多潜在的子图结构，最后，将经过上采样的和都放入g
sub
集合中，再将g
sub
集合最终放入分类器进行分析；
[0046]
步骤二：随机子图样本划分
[0047]
rssp模型是为了解决大规模图数据的处理问题，g
sub
集合包含了不同阶的子图数据集，数据规模可能达到上千万甚至上亿。在实际应用中，如果只是采用单机服务器进行运算是不切实际的；相反的，如果采用计算机集群资源将子图分配到不同的计算节点进行计算，对开发成本又提出了新的需求，并不是所有企业都能匹配高昂的集群资源。因此，本发明提出了在抽样子图的基础上进行随机样本分区，即rssp算法，rssp确保每个数据块都是大数据的随机样本，从而可以用来预估大数据的统计特性，rssp子图随机样本划分针对图数据，通过不同特征在同一数据集的rssp数据块之间具有相似的概率分布，证明了rssp算法可以将完整数据集切分成具有相似概率的rssp块，rssp算法的主要性质包括两个定义；
[0048]
步骤三：基于rssp块的集成分析
[0049]
基于rssp块的渐进集成学习采用逐步式过程从多批rssp块中进行集成模型学习，每批从t中选取的rssp块都是不可替换，大小相等的，逐步式过程是为了避免在同一批次中加载大量的rssp块，占用有限资源甚至导致系统内存不足，逐步式集成模型使得资源有限的计算集群可以扩展到更大的数据集。
[0050]
rssp算法的定义如下：
[0051]
定义1(数据集划分):设数据集g
sub
＝{x1,x2,...,xn}包含n个对象，t为可以将g
sub
划分为多个子集t＝{g
sub_1
,g
sub_2
,...,g
sub_k
}的操作，如果子集t满足下面两个条件，可以称之为g
sub
的一个分区；
[0052]
条件1：
[0053]
条件2：且i≠j
[0054]
以上t是对g
sub
的分区操作，每一块g
sub_k
称之为g
sub
的数据块样本，上述定义是将完整数据集划分为不同的数据块，但这些数据块是不具有与完整数据集特征概率分布的性质，一般不能作为随机样本来分析大数据集样本；但是，下面定义的rssp中的数据块可以作为大数据集的随机样本。
[0055]
定义2(随机子图样本划分):假设g
sub
表示由子图生成模型生成的海量图数据集，f(
·
)是g
sub
的样本分布函数，t为可以将g
sub
划分为多个子集t＝{g
′
sub_1
,g
′
sub_2
,...,g
′
sub_k
}的操作，g’sub
∈g
sub
表示完整数据集的样本分区，则如果
[0056][0057]
称t为g
sub
完整子图数据集的随机样本分区，其中，表示为g
′
sub_k
的
样本分布函数，e(
·
)为其期望值。每个g
′
sub_k
为一个rssp块，t称为g
sub
上的rssp操作，在rssp中，本文采用度分布，图概率密度，平均聚集系数以及半径四个度量指标作为子图数据集的特征描述，即每一个rssp块与完整数据集中的四个度量指标概率分布一致；
[0058]
由子图生成模型生成了海量子图g
sub
后，通过rssp模型算法对g
sub
进行块级抽样，每一块rssp块需要抽取多大，是一个衍生的新问题，提出了基于图数据复杂度的块大小(graph data-driven complexity，gddc)测量算法：
[0059][0060]
其中，g
sub
代表生成的子图数据集，为在显著水平α》0，错误率e》0的情况下，双样本进行z分位数对应值，可以查表获得，c(g
sub
)代表生成的子图数据集的数据复杂度，可以由fisher判别式求得，fisher判别式关注的是差异化最大的特征维度，对于一个多维问题，只要存在一个区别特征就可以描述问题，对rssp块的块大小通过fisher判别比进行数据复杂度的度量，再通过公式2测算出适合的rssp块大小；
[0061][0062]
其中，μ和σ分别代表不同类的平均值和方差。
[0063]
如图6至图9，在proteins数据集上，以gddc方法作为块大小的选择的标准，可以切分出若干块rssp块，从中随机选取出三块rssp块与原始数据集在不同特征上进行概率分布图的比较，主要选用度分布，图密度，平均聚集系数以及半径作为主要特征对不同的图数据集进行表示，发现不同的rssp块与完整子图数据集在上述4个度量指标上的概率分布都是相似的，且块与块之间的曲线趋势也相似。
[0064]
由子图生成模型生成的子图数据集g
sub
包含了一阶抽样子图，二阶抽样子图，以及原始网络抽样并经过上采样的子图。当g
sub
规模不大时，即有足够内存进行计算排序时，可以用以下步骤生成rssp块：
[0065]
1)第一阶段：设g
sub
共有n个对象，即n张图。均匀分布生成n个唯一的随机整数，并对这n个整数进行随机化重新打乱。
[0066]
2)第二阶段：根据块大小将n个正整数切分为q个小数据块，这q个小数据块中即包含n/q张图。设{g
sub_1
,g
sub_2
,...,g
sub_q
}表示上述的q个小数据块，每一块g
sub_k
,k∈{1,2,...,q}即为一个rssp块。
[0067]
当子图数量不多时，上述算法效果良好。但是在现实开发中，该数据集的规模可以达到千万甚至上亿级别。如果要对完整数据集进行相对应的图挖掘分析，所需的内存集群节点花费非常昂贵，这对中小型企业是非常不友好的。例如，当子图数据集达到tb级别的规模时，如果切分成了上万个数据块，此时将这些数据块分配至集群各个节点执行变得不切实际，对于集群数量不多的中小型企业，将很有可能会有许多进程因为竞争资源而导致集群宕机。因此，为了应对这种情况，实现近似计算的效益，采用了一种两阶段分区算法：
[0068]
1)第一阶段；将g
sub
按顺序切分成p个大小相同的数据块，用表示。hdfs算法已经将子图数据集提供了切分成p块的操作，但此时每一块hdfs数据块并不是随机样
本块。
[0069]
2)第二阶段：每个rssp数据块都是从p个hdfs数据块中随机抽取样本构建的。从每个hdfs数据块随机选择一个样本切片，不替换的形成一个新的rssp数据块。具体操作如下：
[0070]
步骤1；随机化每个g
sub_i
块；
[0071]
步骤2:把每个g
sub_i
块划分为q份即每一份包含n/(p
×
q)张子图；
[0072]
步骤3:从p个hdfs数据块的q份数据中不放回的随机取出一份，重复q次，组成一个新的数据块p，此时p为随机样本块，即rssp块；
[0073]
经过以上的步骤，子图数据集g
sub
被划分为具有随机性的若干个随机样本子图分区，这些子图分区和完整子图数据集之间在度分布，图密度等属性上概率分布是近似的，可以代替完整数据集作为图分类的分类对象，实现时间和空间上的效率提升。算法6表示了当g
sub
数据集的规模很大时，rssp块的生成算法。其中，m代表了每一块rssp块的大小，通过blb算法计算得出。
[0074]
通过两步式rssp块生成法，所有的rssp块存储在t集合中。单块rssp块进行分类预测具有偶然性，多个rssp块进行预测并对结果进行组合分析可以有效减少这种偶然性问题。
[0075]
实施例二：
[0076]
本发明实施例在三个真实数据集上对rgssp进行了实验，他们分别是mutag、proteins、imdb-bianry。这三个真实世界数据集包含了生物、化学、社交网络等类型的数据。同时本发明选择了graphlet核、dgcnn图神经网络、s2gn作为基准线方法来进行比较。本研究方法将每个数据集划分为训练集和测试集，为70％和30％。整体实验结果如表1和表2所示，从实验结果上看，本发明方法rgssp在三个数据集上的表现都要优于其他基准方法。
[0077]
表1、各方法实验准确率结果对比(％)
[0078][0079]
表2、各方法实验f1-score结果对比(％)
[0080][0081]
尽管已经示出和描述了本发明的实施例，对于本领域的普通技术人员而言，可以理解在不脱离本发明的原理和精神的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由所附权利要求及其等同物限定。

技术特征：
1.一种基于随机子图样本分区的图分类方法，包括rgssp，其特征在于：所述rgssp由子图生成模型、rssp以及分类器模块组成，所述rssp为随机子图样本分区，所述rgssp是尽可能的生成数量足够的子图结构形成子图数据集，再通过将子图数据集切分成为具有代表性的块级样本，将少量块级样本代替完整数据集进行图分类。2.根据权利要求1所述的一种基于随机子图样本分区的图分类方法，其特征在于：包括以下步骤：步骤一：子图生成模型通过sgn方法生成sgn子图以后，使用的抽样策略关注sgn子图的所有节点和边，并通过抽样不同阶次的sgn获得大量的子图，此外，更高阶的sgn可以获得更多潜在的结构，但由于本研究的研究对象为生成的大量小图，每个小图可能只包含十几个顶点和十几条边，对小图进行高阶转换，转换出来的子图信息会越来越少，甚至于3阶的子图可能就只剩下一个节点，所以，只选择将原始网络生成一阶和二阶子图；在采用的数据集上，在一阶子图和二阶子图上进行抽样子图集生成所达到的规模很多已经到了千万级别，在这个基础上生成的子图规模会远远超过于原始网络进行抽样生成的子图规模，因此，样本分布不均衡会导致模型对一阶和二阶子图有倾向性，原始网络生成的子图结构很少会出现在rssp样本块中，为了保证rssp进行分块时每一个阶次的子图数据集都有相同的概率被选中，需要对原始网络生成的抽样子图进行向上采样，直到其规模与一阶和二阶抽样子图数据集规模相同，在算法1构建子图生成模型算法中，生成了原始网络生成的抽样子图，一阶抽样子图以及二阶抽样子图，考虑到一阶子图所提供的子图结构是最丰富的，因此以一阶子图所生成的抽样子图规模作为基准，先对原始网络g进行子图抽取，获得0阶抽样子结构接着对原始网络g进行sgn子图挖掘，生成一阶子图g
sub1
，再对g
sub1
进行抽样子图抽取生成一阶子图数据集此时的数量规模为不同阶的规模基准，由于一阶子图的规模会比零阶子图规模多出上百万的数量，因此需要对零阶子图进行上采样，直到规模与一阶子图规模相同，最后，对进行sgn子图挖掘，生成二阶子图数据集二阶子图数据集可以挖掘出更多潜在的子图结构，最后，将经过上采样的和都放入g
sub
集合中，再将g
sub
集合最终放入分类器进行分析；步骤二：随机子图样本划分rssp模型是为了解决大规模图数据的处理问题，在抽样子图的基础上进行随机样本分区，即rssp算法，rssp确保每个数据块都是大数据的随机样本，从而可以用来预估大数据的统计特性，rssp子图随机样本划分针对图数据，通过不同特征在同一数据集的rssp数据块之间具有相似的概率分布，证明了rssp算法可以将完整数据集切分成具有相似概率的rssp块，rssp算法的主要性质包括两个定义；步骤三：基于rssp块的集成分析基于rssp块的渐进集成学习采用逐步式过程从多批rssp块中进行集成模型学习，每批从t中选取的rssp块都是不可替换，大小相等的，逐步式过程是为了避免在同一批次中加载大量的rssp块，占用有限资源甚至导致系统内存不足，逐步式集成模型使得资源有限的计
算集群可以扩展到更大的数据集。3.根据权利要求2所述的一种基于随机子图样本分区的图分类方法，其特征在于：所述rssp算法的定义如下：定义1(数据集划分):设数据集g
sub
＝{x1,x2,...,x
n
}包含n个对象，t为可以将g
sub
划分为多个子集t＝{g
sub_1
,g
sub_2
,...,g
sub_k
}的操作，如果子集t满足下面两个条件，可以称之为g
sub
的一个分区；条件1：条件2：且i≠j以上t是对g
sub
的分区操作，每一块g
sub_k
称之为g
sub
的数据块样本，上述定义是将完整数据集划分为不同的数据块，但这些数据块是不具有与完整数据集特征概率分布的性质，一般不能作为随机样本来分析大数据集样本；定义2(随机子图样本划分):假设g
sub
表示由子图生成模型生成的海量图数据集，f(
·
)是g
sub
的样本分布函数，t为可以将g
sub
划分为多个子集t＝{g
′
sub_1
,g
′
sub_2
,...,g
′
sub_k
}的操作，g’sub
∈g
sub
表示完整数据集的样本分区，则如果称t为g
sub
完整子图数据集的随机样本分区，其中，表示为g
′
sub_k
的样本分布函数，e(
·
)为其期望值。每个g
′
sub_k
为一个rssp块，t称为g
sub
上的rssp操作，在rssp中，本文采用度分布，图概率密度，平均聚集系数以及半径四个度量指标作为子图数据集的特征描述，即每一个rssp块与完整数据集中的四个度量指标概率分布一致；由子图生成模型生成了海量子图g
sub
后，通过rssp模型算法对g
sub
进行块级抽样，每一块rssp块需要抽取多大，是一个衍生的新问题，提出了基于图数据复杂度的块大小(graph data-driven complexity，gddc)测量算法：其中，g
sub
代表生成的子图数据集，为在显著水平α>0，错误率e>0的情况下，双样本进行z分位数对应值，可以查表获得，c(g
sub
)代表生成的子图数据集的数据复杂度，可以由fisher判别式求得，fisher判别式关注的是差异化最大的特征维度，对于一个多维问题，只要存在一个区别特征就可以描述问题；其中，μ和σ分别代表不同类的平均值和方差。

技术总结
本发明提供一种基于随机子图样本分区的图分类方法，涉及图分类技术领域。该随机子图样本分区的图分类方法，包括RGSSP，所述RGSSP由子图生成模型、RSSP以及分类器模块组成，所述RSSP为随机子图样本分区，所述RGSSP是尽可能的生成数量足够的子图结构形成子图数据集，再通过将子图数据集切分成为具有代表性的块级样本，将少量块级样本代替完整数据集进行图分类。通过子图生成模型将对不同阶次的SGN子图进行采样，该采样算法覆盖所有节点和所有边，生成的子图数量可以达到上亿级别，有效解决了多样性不足的问题，通过将完整图数据集切分成块级样本，可以代替完整数据集进行近似计算，解决了由子图生成模型带来的大规模图数据处理问题。处理问题。处理问题。


技术研发人员：包先雨 程立勋 郑文丽 敖耿源 李俊杰 蔡伊娜 郭云 吴绍精 黄孙杰
受保护的技术使用者：深圳大学
技术研发日：2023.04.10
技术公布日：2023/7/25