检索结果-南通市图书馆

作者：张军伟桂林电子科技大学

学位级别：硕士

图编辑距离（Graph Edit Distance,GED）是衡量两个图之间相似度的常用方法之一,且被广泛应用于图相似性搜索问题中。图编辑距离算法根据求得的代价值是否精确,主要分为两类:精确图编辑距离算法和近似图编辑距离算法。其中,精确图编辑... 详细信息

图编辑距离（Graph Edit Distance,GED）是衡量两个图之间相似度的常用方法之一,且被广泛应用于图相似性搜索问题中。图编辑距离算法根据求得的代价值是否精确,主要分为两类:精确图编辑距离算法和近似图编辑距离算法。其中,精确图编辑距离算法具有高时空复杂度的特点,主要用于图相似性搜索的验证阶段,以及作为判断近似图编辑距离算法求解精度的评价指标。然而,近似图编辑距离算法则可以在多项式时间内求得相应的解,且基于代价矩阵的近似图编辑距离算法具有较高的求解精度,并受到广泛研究。如何在保证高精确度的情况下提高代价矩阵的求解速度是研究者致力解决的问题。为了能够在多项式时间内求得图编辑距离,且保证近似算法求解的高精确度。因此,本文针对基于代价矩阵的近似图编辑距离算法进行研究,并将其应用到精确图编辑距离求解算法,以及图相似性搜索问题中,具体研究内容及成果如下所示:（1）针对现有的代价矩阵求解算法求解复杂度高,且无法直接对非方阵求解这一问题,本文提出了基于最小费用最大流问题的代价矩阵求解模型MCMF（Minimum Cost and Maximum Flow）,并在此基础上提出了一种简化的求解模型SMCMF（Simplified Minimum Cost and Maximum Flow）,且SMCMF模型具有通用性,尤其在求解非方阵的代价矩阵时性能优越。（2）针对SMCMF模型求解过程中,需要多次查找最短路径这一问题,本文提出一种预处理算法,该算法可在O（n）时间复杂度内求得一组最优匹配,对SMCMF模型进行预处理,以此减少最短路径的查找次数。同时,考虑到代数决策图（Algebraic Decision Diagram,ADD）可以有效改善伪布尔函数的表述能力,本文通过对SMCMF模型的伪布尔函数表述,提出了一种求解图编辑距离的符号ADD算法,称为ADD＿SMCMF算法。实验结果表明,在AIDS和Pub Chem数据集下,该算法在求解规模和时空性能上均优于AStar-BMao算法和FBP（Fast Bipartite）算法。（3）针对图相似性搜索问题中的验证算法AStar-BMao的下界求解复杂度高,以及其在图相似性搜索验证阶段需要对候选集中的每个图进行精确验证这一问题,本文引入ADD＿SMCMF求解思想,提出了一个新的下界求解算法BP-lb ,在此基础上结合改进的上下界求解方法,设计了一个用于图相似性搜索验证阶段的混合算法,称为BP-AStar算法。实验结果表明,该算法可以有效提升图相似性搜索验证阶段的验证效率。

关键词：图编辑距离最佳优先搜索代价矩阵最小费用最大流图相似性搜索下界代数决策图

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于图神经网络的子图同构符号求解技术研究

基于图神经网络的子图同构符号求解技术研究

作者：杨欣桂林电子科技大学

学位级别：硕士

图作为一种重要的数据结构,可以有效刻画现实世界中事物之间的复杂关系。子图匹配问题是图数据分析中的基础问题,具有重要的研究意义。由于子图匹配问题属于NP难问题,随着数据规模的增长,其计算复杂度呈指数增长。因此,目前子图匹配算... 详细信息

图作为一种重要的数据结构,可以有效刻画现实世界中事物之间的复杂关系。子图匹配问题是图数据分析中的基础问题,具有重要的研究意义。由于子图匹配问题属于NP难问题,随着数据规模的增长,其计算复杂度呈指数增长。因此,目前子图匹配算法的研究着重点在于如何提升算法的时间与空间效率。图神经网络可以有效的聚合图节点的邻域信息,使节点的特征向量包含局部邻域信息。此外,代数决策图是一种高紧凑易操作的隐式存储结构,可以实现在较小的存储空间中操作较大规模的图。本文结合图神经网络和代数决策图技术主要研究了基于图神经网络的子图匹配符号算法以及基于代数决策图的子图同构过滤算法。主要工作如下:(1)针对现有子图同构算法中存在的搜索空间大的问题,本文提出了基于图神经网络的子图匹配符号算法(SMMGNN)。该算法采用图卷积神经网络获取包含节点局部邻域信息的特征向量,并以该向量作为过滤条件得到查询图的节点候选集。此外,SMMGNN引入了符号代数决策图存储结构,在数据图中实现各候选区域的并行运算与公共子图的共享存储。其次,为了减少回溯搜索的次数,优化了匹配顺序的计算方法。实验表明,与经典的算法相比,明显地提升了子图匹配的求解性能。(2)针对(1)中提取特征向量时,忽略了不同邻接节点对于中心节点的影响力的问题,对节点特征提取方法提出改进,利用图注意力神经网络提取节点特征,该模型可以根据邻接节点的特征为其分配不同的权重。同时,考虑邻接节点的度中心性以及不同阶的邻接节点对于中心节点产生影响不同,对注意力系数进行了优化,从而抽取更加关键的信息。(3)针对候选集中的无效节点导致大量冗余搜索的问题,提出了基于代数决策图的子图同构过滤算法。该算法给出一种新的候选集编码方式,以采用代数决策图操作对节点候选集并行搜索。其次,在SSMGNN算法的匹配顺序基础上考虑了查询图层次结构信息,给出一种新的匹配顺序。通过查询图节点与邻接节点的关系优化了剪枝策略,并以查询图半径为迭代次数,多次过滤剔除候选集中的无效节点并减少候选区的边集。实验表明,采用该过滤算法能够剔除候选集中的无效节点,从而提高搜索效率。

关键词：子图匹配问题图神经网络代数决策图信息聚合并行搜索

近似图匹配算法及其在全局网络比对中的应用研究

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

近似图匹配算法及其在全局网络比对中的应用研究

作者：黄文文桂林电子科技大学

学位级别：硕士

近似图匹配广泛应用于社交分析、情报学、生物信息学等领域,是当前研究的主流方向。由于受噪声的制约,传统的近似算法无法高效地对近似图匹配问题进行求解,尤其是近似子图匹配问题。采用统计显著性模型是缓解乃至克服噪音问题的一种可... 详细信息

近似图匹配广泛应用于社交分析、情报学、生物信息学等领域,是当前研究的主流方向。由于受噪声的制约,传统的近似算法无法高效地对近似图匹配问题进行求解,尤其是近似子图匹配问题。采用统计显著性模型是缓解乃至克服噪音问题的一种可行策略。全局网络比对问题是生物信息学中热门的研究领域之一,通过网络比对侦测功能相似性蛋白质和发现不同物种之间蛋白质同源关系等具有重要意义。全局网络比对的目标是在两个网络之间找出最佳全局的比对,通过适当描述,可将全局网络比对问题转化为近似图匹配问题。本文以图论和统计显著性模型为基础,对近似子图匹配问题进行了研究和探索;在此基础上,对全局网络比对问题进行了研究。论文主要工作包括:（1）对近似子图匹配问题进行了研究。针对近似子图匹配算法忽略查询图标签信息和待搜索大型数据图标签信息之间存在“潜在分布”关系的问题,提出一种基于卡方统计量捕获的统计显著性来表征近似子图结构匹配相似度的方法,其中统计显著性在处理噪音时具有鲁棒性,并能够充分考虑节点邻域的内在结构和标签信息之间存在“潜在分布”的关系。通过与传统算法作对比实验,表明算法效果较好,运算效率较高。（2）基于破坏性等价于重要性对全局网络比对问题进行了研究。针对现有的全局网络比对算法缺乏对false hub蛋白质和致命性hub蛋白质在结构和性质上差异的考虑,提出了一种基于“破坏性等价于重要性”的思路,根据破坏远近不同的节点给网络整体连通状况所带来的损失来度量蛋白质结构重要性的方法。对比其他最新、最流行的算法表现出更高的比对精确度和保持功能一致性。（3）基于统计显著性对全局网络比对问题进行了研究。针对PPI网络数据存在大量噪音的事实,结合统计显著性模型,提出一种基于卡方统计的全局网络比对算法。对几个真实的数据集进行了大量的实验,结果表明本文提出的算法在比对结果精确度和运算效率上要优于部分最先进的算法。

关键词：近似子图匹配全局网络比对卡方统计统计显著性节点删除破坏性

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于神经网络的图匹配算法及应用研究

基于神经网络的图匹配算法及应用研究

作者：李萍桂林电子科技大学

学位级别：硕士

图匹配是用于在图结构数据中进行高效查询的一种技术,其广泛应用在生物信息学、知识图谱、计算机视觉等领域。相较于传统图匹配算法,基于机器学习和深度学习的方法将匹配任务描述为最小化能量函数问题,利用构建的模型自适应学习图的特... 详细信息

图匹配是用于在图结构数据中进行高效查询的一种技术,其广泛应用在生物信息学、知识图谱、计算机视觉等领域。相较于传统图匹配算法,基于机器学习和深度学习的方法将匹配任务描述为最小化能量函数问题,利用构建的模型自适应学习图的特征并修正参数,整个过程更加智能高效。然而,现有的无监督学习匹配算法中存在随机性强的问题,导致结果不稳定,以及监督学习算法中人为构造的特征存在不准确的可能性,从而导致匹配结果准确度较低。基于此,本文研究了基于神经网络的自适应特征学习匹配算法,并以蛋白质复合物识别和特征点匹配为应用背景验证所提出的算法的准确性和有效性。论文主要研究工作包括:(1)针对无监督学习匹配算法存在随机性的问题,以及监督学习匹配算法存在人为构造特征不准确的问题,提出了基于图嵌入与拓扑结构信息相结合的匹配算法。该算法利用图嵌入神经网络模型自适应学习图的特征并利用非线性分类器得到匹配结果,有效解决了现有方法存在的问题从而达到提高匹配准确度的目的。(2)针对研究内容(1)中的神经网络模型利用随机游走生成根子图,并将其作为学习图嵌入的基本要素会存在信息冗余,进一步导致了最终学习到的图嵌入特征代表性不强的问题,研究了更有针对性的图神经网络来自适应学习特征,并在网络模型中加入了空间转换网络用以对图中重要的结构加重学习,从而实现提升算法的准确性和有效性的目标。(3)为验证以上算法的准确性和有效性,将其应用于生物信息学领域和计算机视觉领域,分别解决蛋白质复合物识别和特征点匹配问题。实验结果表明,相较于其他算法,本文所提出的算法提高了准确度的同时,其在F-measure和敏感度上也有着不错的表现。

关键词：图匹配蛋白质复合物识别特征点匹配神经网络模型

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于增量的动态图模式匹配符号算法研究

基于增量的动态图模式匹配符号算法研究

作者：许昌胜桂林电子科技大学

学位级别：硕士

图作为一种可以描述事物之间关系的数据结构,在现实生活中应用广泛。子图匹配问题是图数据分析研究中的基本课题,有着十分重要的研究价值。但随着数据规模越来越大并且伴随实时变化,基于快照模式的动态图匹配算法无法满足实时响应的要... 详细信息

图作为一种可以描述事物之间关系的数据结构,在现实生活中应用广泛。子图匹配问题是图数据分析研究中的基本课题,有着十分重要的研究价值。但随着数据规模越来越大并且伴随实时变化,基于快照模式的动态图匹配算法无法满足实时响应的要求。基于辅助索引结构的动态图匹配算法能够在数据图发生变化时基于辅助结构的信息进行局部更新,获得比快照模式更快的求解效率。我们从两个方面对现有的动态图匹配技术进行优化,一方面优化辅助结构的候选集存储,通过为辅助结构添加更多的约束来优化辅助结构的存储空间,另一方面引入新的压缩技术,其中代数决策图是一种存储紧凑且易于操作的隐式存储结构,可以在相对较小的存储空间内实现大规模图的运算。本文引入代数决策图技术研究了动态图匹配符号算法以及考虑邻域约束解决现有算法中存在的信息冗余问题。主要研究成果和结论如下:(1)针对现有的动态图匹配算法数据图规模庞大,求解过程产生大量的内存消耗的问题,本文引入了代数决策图(Algebraic decision diagram,ADD)结构作为数据的表示方式,实现数据查询与更新的并行运算以及公共子图的共享存储,有效平衡了算法的空间和时间效率。(2)针对(1)中随着数据规模的快速增长,基于增量的有界模拟图匹配算法在更新过程中存在大量的重复计算,以及通过逐点扩展的方式确认受影响区域时的算法效率低下问题,本文基于ADD提出了一种新的编码方式来构建辅助索引结构ADD Index(AIndex),该辅助结构不仅可以压缩存储节点间的路径信息,同时可以利用ADD并行操作的特性,实现快速查找和维护;其次为了增量维护辅助结构和匹配结果,提出了适用于AIndex的增量更新算法。实验表明,与经典算法相比,优化了存储空间,求解性能有了明显提升。(3)为了降低动态子图匹配候选集空间和提高算法效率,针对目前最先进的增量子图同构匹配算法Symbi中的索引结构动态候选空间(Dynamic Candidate Space,DCS)中存在的信息冗余问题,引入邻域信息约束,提出了一种新的索引结构ZDCS,并提出了ZDCS的更新算法INCZDCS来动态维护ZDCS索引结构和匹配结果,进一步提出了动态图的增量子图匹配算法ZSymbi。最后,在真实数据集上与Symbi算法进行实验对比,结果表明ZSymbi有效缩减了计算空间并提高了算法的求解效率。

关键词：动态图匹配代数决策图符号技术邻域约束 ZSymbi

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

图编辑距离求解技术研究

图编辑距离求解技术研究

作者：韦贤强桂林电子科技大学

学位级别：硕士

图是一种强大的数据模型,它广泛应用于模式识别、自然语言处理、装配序列规划等现实领域。图匹配是通过建立两个图之间最优的对应关系,计算两个图模型之间的相似性。在众多的图匹配方法中,图编辑距离(GED)方法是一种高效的图匹配方式,... 详细信息

图是一种强大的数据模型,它广泛应用于模式识别、自然语言处理、装配序列规划等现实领域。图匹配是通过建立两个图之间最优的对应关系,计算两个图模型之间的相似性。在众多的图匹配方法中,图编辑距离(GED)方法是一种高效的图匹配方式,其是通过衡量两个图的相异性来衡量匹配准确性。图编辑距离算法分为精确图编辑距离算法和近似图编辑距离算法,精确图编辑距离算法可以求解出两个图之间的最优匹配,但是搜索空间过大,时间复杂度高,且受噪声的影响大。近似图编辑距离可以在多项式时间内得到解,但是精度不足,且花费存储空间大,导致图规模增大时,不能有效求解。由于精度不足的缺陷,近似图编辑距算法在匹配精度要求高的应用领域并不适用,为此,本文针对精确图编辑距离算法进行研究,具体内容如下:(1)DF＿GED算法作为A*算法的一种改良方法,通过BP算法得上界,到采用深度优先和上下界剪枝策略,实现加快计算图编辑距离。通过分析DF＿GED算法,发现其上界算法存在空间存储较大的问题,而且时间仍可以提高。在获得相同上界时,FBP算法比BP算法的求解速度更快,但是使用FBP算法的条件是代价值定义的需要满足约束条件。为此,在FBP算法基础上提出一种新的上界算法,通过引入参数来调整成本值之间的关系,可以提高FBP算法的通用性,新的上界算法可以降低计算时间和存储空间。(2)约束满足问题(CSP)是人工智能中处理大规模求解问题的重要方法,是一种可以有效解决组合类搜索问题的技术,为图匹配问题的求解提供了一个行之有效的思路。WCSP是传统CSP的一种拓展,其为约束附上了权值,这样可以通过该权值评判出解的好坏,可以很好刻画图编辑编辑操作代价。为此,提出一种图编辑距离的加权约束满足(WCSP)模型。将源图的顶点集作为变量集,目标图顶点集作为值域,并引入空值去表示插入和删除操作,每个变量赋值可以看做是顶点匹配情况,通过建立约束条件刻画出具体的编辑操作,将匹配过程中产生的编辑代价作为加权值,将GED刻画成WCSP模型。(3)结合最大约束准则和深度优先分支定界法,提出WCSP＿GED算法对图编辑距离的加权约束满足模型进行约束求解。采用分支定界法可以有效缩减搜索空间,通过最大约束准则将模型变量重新排序,快速更新边界。实验结果表明,在真实据集下,该算法求解规模和速度均优于A*GED算法和DF＿GED算法。

关键词：图匹配图编辑距离删除策略加权约束满足问题

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于约束框架的图模式匹配符号算法研究

基于约束框架的图模式匹配符号算法研究

作者：龙广兴桂林电子科技大学

学位级别：硕士

图能有效刻画事物之间的相互关系,现实生活中存在许多复杂应用场景都可以使用图数据结构进行抽象表示。图匹配问题是在两个图之间找到某个映射函数,该映射函数能够保证查询图到数据图之间存在结构的相似性。而子图匹配作为图匹配问题中... 详细信息

图能有效刻画事物之间的相互关系,现实生活中存在许多复杂应用场景都可以使用图数据结构进行抽象表示。图匹配问题是在两个图之间找到某个映射函数,该映射函数能够保证查询图到数据图之间存在结构的相似性。而子图匹配作为图匹配问题中的基础性问题,具有重要的研究意义。传统的子图匹配求解算法受制于组合复杂性约束,随着数据规模增长,算法的时间复杂度也会呈指数级增长。约束满足问题CSP（Constraint Satisfaction Problem）为组合优化问题提供了一个通用的求解框架和有效的求解策略,并且结合代数决策图（ADD）高效紧凑且易于操作等特点,采用符号技术对匹配模型进行隐式描述是降低子图匹配问题中组合复杂性的一种可行策略。同时,通过代数决策图之间的并行约束处理能有效加快搜索速度,减少问题的空间需求。因此,本文在CSP和代数决策图的基础上,研究了基于符号技术的子图同构求解算法,并且将该技术扩展到多子图匹配问题的求解上。具体的研究内容如下:（1）现有的子图匹配算法都是按节点顺序进行串行匹配,每次匹配都要对候选集中的节点逐个进行约束判断,这将导致算法在最坏的情况下具有指数级的时间复杂度,限制了算法的求解效率。鉴于每次对候选节点的评估都是使用相同的约束条件,对此本文提出了DDSubISO算法,将ADD符号操作与启发式搜索剪枝策略相结合,提出了多条并行化的符号约束求解策略,实现搜索过程中对所有候选点进行并行约束处理,在单核处理器上显著提升了子图匹配算法的求解效率。（2）多子图匹配问题是子图匹配问题的一种扩展形式,旨在利用查询图之间的公共子图加速匹配的效率。本文针对多子图匹配查询中两两相似性检测的时间复杂度高以及存储查询中间结果的空间复杂度高的问题,提出了一种新的多子图匹配符号算法DDMQO。通过引入图神经网络技术对查询图集合进行预分组,降低图相似性检测复杂度;利用代数决策图（ADD）对查询图和数据图进行存储表示,降低存储空间复杂度。为进一步提高有效共享子图检测效率,提出了一种新的最大公共连通子图符号算法DDMCS。最后,利用改进的子图匹配符号算法SSMGNN求解多子图匹配问题,提高了多子图匹配的求解效率。为了更进一步提升多子图匹配算法的求解效率,对（1）中提出的DDSubISO算法进行修改替代子图匹配符号算法SMMGNN。由于DDSubISO算法的输出结果是对解的隐式表达,不但自身求解效率要优于SMMGNN算法,也更有助于高效便捷地将公共子图的子图同构解集嵌入到查询图中,进一步提升求解效率。

关键词：图匹配子图同构多子图匹配约束满足代数决策图

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于符号技术的子图同构约束求解算法

基于符号技术的子图同构约束求解算法

作者：王嘉鑫桂林电子科技大学

学位级别：硕士

图是一种非常重要的数据结构,由节点和边组成,生活中可以用来表示社交网络中用户之间的关系,或者在地图中表示城市之间的路线等。子图同构问题是图模式匹配中的一类核心问题,并且是NP完全问题,如何提高子图同构问题的求解效率一直是学... 详细信息

图是一种非常重要的数据结构,由节点和边组成,生活中可以用来表示社交网络中用户之间的关系,或者在地图中表示城市之间的路线等。子图同构问题是图模式匹配中的一类核心问题,并且是NP完全问题,如何提高子图同构问题的求解效率一直是学者们致力解决的问题。代数决策图,是一种用于表示和操作布尔函数的数据结构,其紧凑性可以在相同的存储空间内存储更多的数据,并且运算过程中以集合为单元使得其求解效率更高。此外,弧一致性技术主要用于求解约束满足问题,通过减少搜索空间,达到提高求解效率的效果。本文结合代数决策图主要研究了基于符号技术的子图同构约束求解算法以及弧一致性符号过滤算法。主要工作如下:(1)针对目前子图同构求解算法中构建候选集结构所导致的时间以及空间复杂度高的问题,本文提出了基于符号技术的子图同构约束求解算法DDCS。将传统子图同构DAF算法中的CS结构,进行编码并使用布尔函数表示,进一步使用代数决策图进行压缩存储。在此结构的基础上添加约束进行预处理,从而减少候选集中的冗余节点。同时,为了减少在搜索求解过程中的笛卡尔积计算,优化了匹配顺序。实验结果表明,与传统子图同构DAF求解算法相比,求解效率有明显提升。(2)针对传统弧一致性算法处理大规模复杂约束满足问题效率低的问题,提出了弧一致性符号过滤算法DDAC。对约束满足问题进行编码并使用布尔函数表示,进一步使用代数决策图进行压缩存储。此外,给出了一种新的变量序,使得符号过滤技术可以与子图同构求解算法更好的结合。同时,引入符号操作中的全称量化操作,进一步加强弧一致性技术的剪枝能力。实验结果表明,该过滤算法可以删除值域中的冗余解,提高求解效率。(3)对子图同构DDCS算法进行优化。在DDCS算法的预处理阶段以及求解过程中引入符号过滤算法DDFilter,对候选集进行剪枝,减小搜索空间,提高子图同构的求解效率。实验结果表明,符号过滤算法DDFilter的引入提升了子图同构DDCS算法的求解效率。

关键词：子图同构代数决策图弧一致性并行搜索约束满足问题

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于图表示学习的子图同构约束求解技术研究

基于图表示学习的子图同构约束求解技术研究

作者：李珍桂林电子科技大学

学位级别：硕士

图作为一种结构化的数据结构非常容易刻画事物之间的内联关系,现实生活中的许多数据都可以用图来进行表示。图匹配中的子图同构问题作为一种查询技术被广泛的应用于社交网络、网络安全、计算生物学和化学等领域中。子图同构属于NP-hard... 详细信息

图作为一种结构化的数据结构非常容易刻画事物之间的内联关系,现实生活中的许多数据都可以用图来进行表示。图匹配中的子图同构问题作为一种查询技术被广泛的应用于社交网络、网络安全、计算生物学和化学等领域中。子图同构属于NP-hard问题,随着其数据规模的上升,其求解的复杂度也往往呈指数上升。图表示学习作为处理图数据的表示技术,可以高效的学习出表示图结构和属性信息的特征向量。此外,对求解过程中所出现的“组合爆炸”问题,约束满足问题(CSP)模型可以起到一定程度的抑制作用。本文在图表示学习和CSP的技术上主要研究了基于邻居信息聚合的子图同构约束求解算法以及基于随机游走图表示学习的子图同构过滤算法。主要的工作如下:(1)现有的子图同构算法大多是基于邻居关系来构建约束条件,而忽略了节点的局部邻域信息。针对这个问题,提出了一种基于邻居信息聚合的子图同构约束求解算法。首先根据图的标签、度等特征属性,对节点的匹配顺序进行优化,以减少搜索分支。其次,将模式图和目标图导入改进后的图卷积神经网络,得到聚合后的节点局部邻域信息,以此来得到聚合权值约束,并建立子图同构的CSP的新模型。最后,结合CSP求解技术进行回溯求解。实验结果表明,与经典的算法相比,该算法可以有效地提高子图同构的求解效率。(2)在现实生活中,图数据中的边通常也具有一定的实际意义与属性。针对(1)中在对特征提取时只提取以节点为中心的邻域信息这一问题提出了一种改进算法。该算法在(1)的研究基础上将图转换为关联矩阵进行描述,采用另一组图卷积神经网络对其边的邻域信息进行聚合,并加以整合以此得出蕴含节点和边的局部邻域信息的特征向量。实验结果表明,采用改进的算法可以进一步的提高子图同构的求解效率。(3)为了缩减问题的搜索空间,减少不必要的解,提出了一种基于随机游走图表示学习的子图同构过滤算法,在子图同构的预处理阶段进行使用。首先,根据子图同构问题的匹配特性,给出了“最近邻”有偏随机游走策略,以此策略来进行随机游走采样。其次,针对图的属性特征,加入节点标签进行训练。最后通过相似性度量对不可行解进行过滤。实验结果表明,该过滤算法可以有效的缩减搜索空间,以提高问题的求解效率。

关键词：图表示学习子图同构约束满足问题信息聚合随机游走

基于树分解技术的子图同构约束求解符号算法研究

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于树分解技术的子图同构约束求解符号算法研究

作者：吴量桂林电子科技大学

学位级别：硕士

子图同构作为图数据库中的一种查询技术,广泛应用于计算机视觉、社交网络分析及生物化学分析等领域。子图同构是NP完全问题,随着图规模的增大,算法的时间和空间复杂度呈指数增长。提升候选集的过滤技术、减少计算消耗的内存空间及降低... 详细信息

子图同构作为图数据库中的一种查询技术,广泛应用于计算机视觉、社交网络分析及生物化学分析等领域。子图同构是NP完全问题,随着图规模的增大,算法的时间和空间复杂度呈指数增长。提升候选集的过滤技术、减少计算消耗的内存空间及降低问题的求解规模是提高子图同构求解效率的有效途径。约束满足问题是求解组合优化问题的通用框架,利用约束传播和分解技术,能够起到删减匹配候选集和降低问题求解规模的作用,通过结合符号技术,利用代数决策图紧凑和易操作的优点,达到减少内存消耗和缓解组合爆炸的目的,同时符号操作具有并行性,能够有效加快计算速度。鉴于此,本文结合约束求解技术和符号技术对子图同构问题进行了研究,主要研究内容和结论如下:(1)为了描述子图同构问题,本文结合约束求解技术和符号技术给出了子图同构问题的一种新的约束符号模型,首先使用伪布尔函数对新模型的各要素进行形式化描述,然后使用ADD数据结构对模型进行压缩存储。与传统约束模型相比,该模型具有更好的适用性和紧凑性。(2)为了提高候选集的过滤效果,在子图同构的约束符号模型基础上,研究了全不同约束,给出了全不同约束的广义弧一致性符号算法,对值域进行了初步删减,并对算法进行了优化,提出了冗余边过滤算法和平凡SCC剪枝来加快计算速度。同时通过挖掘图的结构和属性信息,提出了邻域标签约束过滤算法,有效删减了值域。之后结合全不同约束的传播算法,进一步过滤了变量的值域。(3)为了缓解状态的组合爆炸,采取分治的思想,结合树分解算法对原CSP问题进行分解,得到多个子问题,限制了问题的求解规模,降低了求解难度。并对符号树分解算法进行了改进,通过引入优先函数提高了并行性,加快了计算速度,最后使用无回溯的树搜索算法求解和组合子问题以得到原问题的解。(4)为了验证算法的有效性,通过CUDD软件包实现了所有符号算法,并在随机测试实例和公开基准数据集上进行了广泛的实验对比,实验结果表明本文算法提高了子图同构求解的时间和空间效率。

关键词：图匹配子图同构约束满足问题全不同约束树分解技术符号算法代数决策图