基于图相似性匹配的海水溶解氧辅助评价方法

海水溶解氧评价的正确性对于维护海洋生态系统的稳定性具有重要意义。海水溶解氧数据属于非线性时间序列,可视图方法(时间序列转化为图)是分析这类数据较有效的方法,但仍存在未同时考虑数据的时间演变特性以及变量间相互影响的问题。针对现存问题,本研究提出基于图相似性匹配的海水溶解氧辅助评价方法。首先,同时考虑海温、盐度对海水溶解氧的影响以及数据的不可逆性,提出溶氧温盐-转移概率(dissolved oxygen temperature salinity-transition probability,DOTS-TP)有向可视图方法,实现了多变量时间序列到单变量溶解氧图的转化;然后,在将墨西哥湾溶解氧图作为评价参照的基础上,综合利用图的多层次信息,提出子图节点全局(subtree node global,SNG)图相似性匹配方法,通过计算SNG评价指数实现对海水溶解氧的辅助评价。实验结果表明DOTS-TP有向可视图方法能更准确地表达海水溶解氧信息,SNG图相似性匹配方法适用于所有海水溶解氧数据,并能得出正确的辅助评价结果。

NAGSim:一种基于图神经网络与注意力机制的图相似计算模型

传统的基于图编辑距离的图相似性计算算法模型复杂,时空代价大,精确度不高.本文研究基于图神经网络的图相似性计算,提出一种新的图相似计算模型-NAGSim.NAGSim运用图注意力网络生成节点向量,提取图中每一节点的特征信息,再利用注意力机制判断图中节点的重要性,并生成图的整体向量.NAGSim通过节点级嵌入与图级嵌入更好地保留了图的全局信息.最终,将生成的图嵌入输入神经张量网络层,关联两图向量,再输入到全连接层得到相似性得分.文中通过多项对比实验证明了模型的有效性,实验结果表明,相比于传统算法以及现有的端到端学习模型,NAGSim取得了更好的图相似性判别结果.对比目前的基于图神经网络的图相似性计算模型,NAGSim取得了显著的结果.

基于坐标映射及多重图划分的图相似查询研究

图相似查询是图数据库资源管理最重要的操作之一。目前的相似性查询算法几乎都是采用对整个图数据库进行过滤得到候选集的方式,没有考虑在实际图数据库中各数据图规模之间存在着一定的差距,没有必要对整个图数据库进行计算。因此,提出了一种基于坐标映射的批量处理方式,从规模上对数据图进行剔除,使得后续需要计算的数据图数量大大减少。同时给出了一个参数化的、基于选择性划分的GED下界,使得图划分方式具有约束性,而不是随机的,并在此基础上给出了一个多层索引结构,用于GED下限交叉检查。模拟实验结果表明,所提出的处理方法在通过坐标映射来尽量缩减计算时间的同时,较好地提升了过滤精度,甚至能在过滤阶段就得到相似查询的结果。

一种基于自适应结构感知池化图匹配的图相似度计算模型

图相似度计算在许多有关图的任务中起着重要作用,例如图相似性搜索、图分类和图聚簇等。由于计算2个图之间的精确距离/相似度通常是NP-hard的,因此基于神经网络提出了自适应结构感知池化图匹配网络模型(ASAPMN),用端到端的方式来计算任意2个图结构之间的相似性。利用一种新颖的自我注意网络和一种改进的图神经网络来确定给定图中每个节点的重要性,通过学习对每一层的节点进行稀疏软集群分配,从而有效地池化子图,形成池化图。在池化后的图对上利用结点-图匹配网络有效地学习一个图的每个节点与另一整个图之间的跨层交互提取图间相似度。在4个公共数据集上的综合实验结果表明,ASAPMN在图-图分类和回归任务中优于最先进的基线模型。

基于元结构匹配与有偏采样的图相似度计算方法

作为图分类、图相似搜索等诸多图数据分析任务的核心步骤,图相似度计算一直是备受研究者们所重视的一个热点问题.由于传统图相似度计算方法的复杂性,无法适用于实时计算节点较多的图相似度任务,针对此问题研究者们提出了新型的基于图神经网络的图相似度计算方法.然而这些算法虽有效加快了图相似度的计算,但是仍然存在两方面的不足,从而影响了他们的性能:(1)多数现有工作通过节点级或图级嵌入的比较来衡量图之间的相似度,忽略了大图中丰富的局部结构特征;(2)所有现有工作均随机采样生成图对数据,导致样本包含的结构不均匀,训练所得模型只对部分特定结构敏感因而误差较大.为此,本文提出了一种新颖的基于元结构匹配与有偏采样的图相似度计算方法MB-GSC(Meta-Structure Matching and Biased Sampling based Graph Similarity Computation).首先提出GSE(Graph Structure Extraction)算法提取图中元结构并构建图的结构分布向量,然后基于此向量提出有偏采样策略RSG(Representative Sample Generation)进行代表性样本的生成,用于后续模型训练.同时,提出算法MSA(Meta Structure Alignment)对提取到的元结构进行最优匹配对齐,从而获取公有结构形状差异与特有结构数量差异,进而构建蕴含有效的局部相似信息的子结构相似向量.最后,在模型中集成节点级成对比较相似向量、图级神经张量网络相似向量、子结构相似向量进行图对相似性计算.为验证算法的有效性,采用5个评估指标在4个真实数据集上与基准方法进行了大量对比实验,对模型性能进行全面评估.实验结果验证了本文所提算法MB-GSC能够更准确且高效地计算图之间的相似度,在GED预测、MCS预测任务上的准确度比现有模型分别提升11.16%、7.45%,且在保证相同准确率的同时使训练样本数平均减少54%.

面向图相似性搜索的高效图编辑距离算法

在图相似性搜索问题中,图编辑距离是较为普遍的度量方法,其计算性能很大程度上决定了图相似性搜索算法的性能。针对传统图编辑距离算法中存在的因大量冗余映射和较大搜索空间导致的性能低下问题,提出了一种改进的图编辑距离算法。该算法首先对图中顶点进行等价划分,以此计算映射编码来判断等价映射;然后定义映射完整性更新等价映射优先级,选出主映射参与扩展;其次,设计高效的启发式函数,提出基于映射编码的下界计算方法,快速得到最优映射。最后,将改进的图编辑距离算法扩展应用于图相似性搜索。在不同数据集上的实验结果表明,该算法具有更好的搜索性能,在搜索空间上最大可降低49%,速度提升了约29%。

高效低索引的图相似性搜索算法

图相似性搜索是在给定的度量标准下查找与查询图相似的图集合,目前大多采用“过滤-验证”的计算框架。针对现有方法中过滤下界不紧密和索引空间占用较大等问题,提出了一种基于查询图分区的多层级过滤、低索引空间占用的图相似性搜索算法Z-Index。该算法首先通过全局粗粒度过滤得到预候选集;然后提出基于扩展概率的查询图分区算法,并采用层级过滤机制进一步精简候选集,增强下界紧密性;最后引入序列相似性差值计算序列中数据分布的稀疏度,提出分区压缩和差值压缩两种编码压缩算法,并据此构建“零”索引结构,降低索引空间开销。实验结果表明,Z-Index算法所得下界更加紧密,产生的候选集大小可减少50%左右,算法执行时间大大缩短,且该算法在索引空间占用极小的情况下仍具有可扩展性。

基于子图相似性的多动症患者脑网络分析

多动症会严重影响儿童发育,对多动症患者的有效诊断受到广泛关注。该文结合脑网络的拓扑结构信息和图上的信号,提出一种基于稀疏表示的图相似性计算方法,从微观到宏观分析脑区之间的差异。该方法使用Pearson相关系数构建全连通脑网络,基于稀疏表示从底层结构中提取节点子网络,根据图核函数计算子网络相似性,最后给出了脑网络相似性的全局指标。以受试者间的相似性作为特征在公共数据集ADHD-200上的分类实验结果表明,该方法能够以93.1%的准确度区分多动症患者和健康对照者,分类性能明显优于其他已有算法。此外,结果表明多动症患者在中央前回、丘脑、海马和脑岛等脑区之间有更强的连接。

谱图相似度分析结合保留指数对单萜烯同分异构体的GC-MS定性分析

运用欧氏距离的最短距离聚类分析法,对在质谱数据库NIST02.L检索到的37种单萜烯同分异构体的93张质谱图进行了分类。结果显示,单萜烯被分成5类,大部分单萜烯聚到1类,包括30种单萜烯的77张质谱图。但部分谱图很近似,仅用传统的质谱库匹配鉴定其结构存在一定的困难。采用改进的谱图相似度分析结合保留指数实现了有效定性,并将该方法用于实际样品的定性分析。

子图相似性的恶意程序检测方法

动态行为分析是一种常见的恶意程序分析方法,常用图来表示恶意程序系统调用或资源依赖等,通过图挖掘算法找出已知恶意程序样本中公共的恶意特征子图,并通过这些特征子图对恶意程序进行检测.然而这些方法往往依赖于图匹配算法,且图匹配不可避免计算慢,同时,算法中还忽视了子图之间的关系,而考虑子图间的关系有助于提高模型检测效果.为了解决这两个问题,提出了一种基于子图相似性恶意程序检测方法,即DMBSS.该方法使用数据流图来表示恶意程序运行时的系统行为或事件,再从数据流图中提取出恶意行为特征子图,并使用"逆拓扑标识"算法将特征子图表示成字符串,字符串蕴含了子图的结构信息,使用字符串替代图的匹配.然后,通过神经网络来计算子图间的相似性即将子图结构表示成高维向量,使得相似子图在向量空间的距离也较近.最后,使用子图向量构建恶意程序的相似性函数,并在此基础上,结合SVM分类器对恶意程序进行检测.实验结果显示,与其他方法相比,DMBSS在检测恶意程序时速度较快,且准确率较高.

基于图相似匹配的政务网络结构一致性验证方法

针对政务网络结构的一致性验证问题,提出一种基于图相似匹配的政务网络结构一致性验证方法。方法首先抽象出政务网络的图模型,利用网络结构的模块化特征和顶点的k-邻近关系进行可扩展的图相似匹配,获取两图之间的所有相似结构;然后引入节点重要性贡献和路径距离衰减因素,提出一种改进的图相似性度量函数,计算网络结构之间的一致性程度。实验结果表明,该方法能够准确、有效地评估政务网络结构的一致性程度,细粒度地反映网络结构之间的相似差异情况,包括网络拓扑与系统部署存在的各种违规情况。

BMGSJoin:一种基于MapReduce的图相似度连接算法

图相似度连接在数据挖掘领域应用广泛,尤其是在数据预处理阶段,可用于数据清理、近复本检测等,其研究具有十分重要的意义.针对基于编辑距离约束的图相似度连接问题进行研究,返回两个图集合中所有编辑距离不超过给定阈值的图对.基于分布式编程框架MapReduce,设计采用"过滤-验证"框架的MGSJoin算法,利用基于路径的q-gram签名实现非解候选对的过滤,计数过滤.鉴于该算法键值对数量庞大的潜在问题,引入Bloom Filter技术对算法进行改进并设计BMGSJoin算法.实验结果表明,提出的两种图相似度连接算法能较大地改善现有算法的效率和可扩展性,并能较好地应对当前大数据挖掘分析的需求.

基于SQL的图相似性查询方法

图作为一种表示复杂信息的数据结构,被广泛应用于社交网络、知识图谱、语义网、生物信息学和化学信息学等领域.随着各领域应用的普及和深入开展,如何管理这些复杂图数据,是目前图数据库技术面临的巨大挑战.图的相似性查询是图数据管理中的热点问题之一,对图查询问题的研究主要包括图的相似性查询等.重点研究基于编辑距离(graph edit distance)的图相似性查询处理问题.首先,通过对目前代表性的问题求解算法分析发现,目前已提出的过滤规则都具有自己的优缺点和适用性.其次,针对已有方法在过滤阶段自身存在的优缺点和适用性的问题,提出一种面向关系型数据库的过滤框架,新的过滤框架可以支持所有已有的过滤规则,从而通过结合不同的过滤规则来优化图相似查询算法以提高查询效率.该方法可以最大程度地保留不同过滤规则的优点并克服其缺点,从而对不同查询具有普遍适用性.最后,基于PubChem数据集,通过比较算法在求解查询结果的时间消耗,验证所提出算法的高效性及可扩展性.实验结果表明,所提出的方法优于现有算法.

基于图相似日和PSO-XGBoost的光伏功率预测

为充分利用历史信息,最大限度优化模型效果,提高光伏功率预测精度,提出了基于图相似日和粒子群优化极限梯度提升树(particle swarm optimization-extreme gradient boosting tree,PSO-XGBoost)的光伏功率预测方法。将每天由天气特征组成的向量转换成格拉姆矩阵,以便充分挖掘各个向量之间的关系;然后将拉姆矩阵转换为图像,采用结构相似性算法(structural similarity,SSIM)寻找与待预测日最相似的历史日,并选取历史日的光伏功率、待预测日的辐照度、温度、湿度作为极限梯度提升树的输入变量;为充分发挥模型的预测能力,运用粒子群算法优化极限梯度提升树确定最优的超参数,最终输出各时段的光伏功率预测值。利用光伏电站实际数据进行验证,结果表明:相比于未改进的XGBoost模型,所提方法在晴天下的均方根误差(root mean square error,RMSE)降低了31.6%,平均绝对误差(mean absolute error,MAE)降低了31.6%;在多云天气下的RMSE降低了24.1%,MAE降低了40%;在阴雨天气下的RMSE降低了25%,MAE降低了38.5%,有效地提高了模型的预测精度和泛化能力。

基于垂直维序列动态时间规整方法的图相似度度量

针对图相似度度量过程中复杂度高、信息缺失的问题,采用将图转换为广义树,将广义树表示为垂直维序列的方法,通过计算垂直维序列的距离度量图的相似度。该方法把度量图相似度的问题简化为计算垂直维序列距离的问题。垂直维序列不仅包含了顶点标号、入度和出度信息,而且体现了顶点的层次结构特性,保留了图中的路径信息。与现有方法相比,该方法在度量过程中考虑了更多的图信息,并将时间复杂度降至O(n^2)。

恶意代码的函数调用图相似性分析

恶意代码的相似性分析是当前恶意代码自动分析的重要部分。提出了一种基于函数调用图的恶意代码相似性分析方法,通过函数调用图的相似性距离SDMFG来度量两个恶意代码函数调用图的相似性,进而分析得到恶意代码的相似性,提高了恶意代码相似性分析的准确性,为恶意代码的同源及演化特性分析研究与恶意代码的检测和防范提供了有力支持。

基于分子图相似度的医药文献推荐方法

当今生物医学等领域的文献快速增长,一方面促进了科研交流,但同时也为研究人员带来了巨大的阅读压力,尽管业界已出现了一些论文搜索和推荐的方法,但其大都只依据论文的元信息和文本信息,而对文章内容,尤其是插图等非文字对象尚未充分挖掘并利用,因此现有系统在给读者的推荐结果中,还存在着大量重复、泛化等低效情况。为此,我们探索并建立了一个基于论文内容的文档级推荐系统,具体包括:文档解析、文本对象理解、内容相似性度量、多级索引机制、以及优化推荐结果等主要环节。其中,针对生物医学类科技文献中特有的分子式图片,我们提出了一种图相似度的度量方法,即半分支编辑距离(Half-branch GED,简称HB-GED)算法,同时针对分子图形表示和文档之间关系表示也提出了图卷积模型。在真实数据集上的实验结果表明,本文提出的论文推荐方法,可有效筛选出更符合查询者意图的候选论文。

基于分区过滤-增量验证的图编辑相似查询

图编辑相似查询问题是指从图集G中查询出所有与查询图q的图编辑距离(Graph Edit Distance,GED)在给定阈值τ内的数据图.由于GED计算是NP-Hard问题,现有的研究多采用过滤-验证框架进行查询,对未能过滤掉的图采用A*-GED算法验证.本文提出了分区过滤-增量验证框架PFIV来处理图相似查询问题,在增强过滤效果的同时,还能加快验证速度.首先,在过滤阶段提出了2种分区策略,用来加快分区速度.(1)映射顶点顺序策略:在分区过程中,基于图的特征信息和结构信息提出分区时顶点的映射顺序,尽快过滤掉不相似的图,减少计算量;(2)分区结束条件策略:在分区过程中,设置分区结束条件,加快不相似图的过滤速度.其次,在验证阶段提出了增量验证策略,利用过滤阶段保留的映射结果,设计状态空间树,进行增量验证,加快验证阶段的计算.最后,通过大量实验验证了PFIV能够高效地处理图编辑相似查询问题,对比原有算法,查询效率提高8%~17%,并证明了所提出策略的有效性.

自适应相似图联合优化的多视图聚类

相比于单一视图学习,多视图学习往往可以获得学习对象更全面的信息,因而在无监督学习领域,多视图聚类受到了研究者的极大关注,其中基于图的多视图聚类,近年来取得了很大的研究进展.基于图的多视图聚类一般是先从各个视图原始数据学习相似图,再进行视图间相似图的融合来获得最终聚类结果,因此,多视图聚类的效果是由相似图质量和相似图融合方法共同决定的.然而,现有基于图的多视图聚类方法几乎都聚焦在视图间相似图的融合方法研究上,而缺乏对相似图本身质量的关注.这些方法大多数都是孤立地从各视图的原始数据中学习相似图,并且在后续图融合过程中保持相似图不变.这样得到的相似图不可避免地包含噪声和冗余信息,进而影响后续的图融合和聚类.而少量考虑相似图质量的研究,要么相似图构造和图融合过程是直接联立迭代的,要么在预定义相似图过程中提前利用秩约束进一步初始化,要么就是利用相似图存在的一些底层结构来获取融合图的.这些方法对相似图本身改进很小,最终聚类性能提升也十分有限.同时现有基于图的多视图聚类流程也缺乏对各视图间一致性和不一致性的综合考虑,这也会严重影响最终的多视图聚类性能.为了避免低质量预定义相似图对聚类结果的不利影响以及综合考虑视图间一致性与不一致性来提升最终聚类效果,本文提出了一种自适应相似图联合优化的多视图聚类方法.首先通过Hadamard积来获得视图间高质量一致性部分信息,再将每个预定义相似图和这部分信息对标,重构各个视图的预设相似图.这个过程强化了各视图间的一致性部分,弱化了不一致性部分.其次设计了相似图重构改进和图融合联合迭代优化框架,实现了相似图的自适应改进,最终达到相似图和聚类结果共同提升的效果.该方法将相似图改进过程与图融合过程联合起来进行自适应迭代优化,并且在迭代优化中不断强化各视图间的一致性,弱化视图间的不一致性.此外,本文的方法也集成了现有多视图聚类方法的一些优点,自加权以及无需额外聚类步骤等.在九个基准数据集上与八个对比方法的实验验证了本文方法的有效性与优越性.

基于相似图投影学习的多视图聚类

随着数据来源方式的多样化发展,多视图聚类成为研究热点。大多数算法过于专注利用图结构寻求一致表示,却忽视了如何学习图结构本身;此外,一些方法通常基于固定视图进行算法优化。为了解决这些问题,提出了一种基于相似图投影学习的多视图聚类算法(multi-view clustering based on similarity graph projection learning, MCSGP),通过利用投影图有效地融合了全局结构信息和局部潜在信息到一个共识图中,而不仅是追求每个视图与共识图的一致性。通过在共识图矩阵的图拉普拉斯矩阵上施加秩约束,该算法能够自然地将数据点划分到所需数量的簇中。在两个人工数据集和七个真实数据集的实验中,MCSGP算法在人工数据集上的聚类效果表现出色,同时在涉及21个指标的真实数据集中,有17个指标达到了最优水平,从而充分证明了该算法的优越性能。