基于图常量条件函数依赖的图修复规则发现

数据一致性是数据质量管理的一个重要内容。为了提升图数据一致性,大量关系型数据库中的数据依赖理论被引入到图数据库,包括图函数依赖、图关联规则等。图修复规则是最新提出的一种针对图数据的数据依赖规则,具有强大的修复能力,但目前尚无有效的挖掘算法。为了自动生成图修复规则并提高图数据修复的可靠性,提出一种将图常量条件函数依赖转化为图修复规则的方法(GenGRR)。通过图模式在图中匹配同构子图并映射成节点-属性二维表,从表中相应属性域中抽取错误模式把图常量条件函数依赖转化成图属性值修复规则;删去图模式中常量条件函数依赖RHS对应的节点与相连边生成图属性补充规则。基于最大公共同构子图筛选并验证生成图修复规则的一致性。在多个真实数据集上进行测试,验证相比图常量条件函数直接修复图数据,通过转化生成的图修复规则具有更好的修复效果。

基于区域路标引导的月面大范围高效行驶导航技术

载人月球探测任务中,受月面环境的复杂性和车载系统配置的限制,仅依靠车载导航系统难以全自主实现精确导航,需要遥操作中心对载人车大范围移动进行智能化支持。针对载人车在复杂月面环境中进行远距离探测时的高效导航问题,提出了基于区域路标引导的月面大范围高效行驶导航方法,通过分析载人车导航相机成像区域,将全路线可视区域中的月坑构建为月面路标图;并利用载人车导航相机图像中的月坑构建导航相机路标图,使用子图匹配的方法确定载人车可视区域内的月坑和环月卫星影像中月坑的对应关系,从而完成载人车位姿的解算。仿真试验结果表明:提出方法可以实现大范围移动过程中的高效导航。

基于PathSim的MOOCs知识概念推荐模型

大规模开放在线课程提供大规模开放式在线学习平台,为推进现代教育发挥关键作用。然而,减少用户学习盲区和改善用户体验方面的研究仍具有挑战性:交互数据稀疏;难以扩展到大型推荐任务上;用户需求不单由用户喜好决定,还受到不同教师、课程影响;以统一的方式对课程学习事件中不同类型实体及关系进行建模并不妥靠。基于此,引入相关性度量,依据全图结构信息计算各边权重,提出采用相关性度量算法PathSim进行邻域采样的知识概念推荐模型PathSimSage。各实体间相关性得分可在本地离线计算,将神经网络与传播过程分离,保证神经网络的堆叠层数和传播过程的独立性,大幅减少模型所需训练时间。在公开的MoocCube数据集上进行了综合实验,PathSimSage降低了不相关的信息甚至噪声的影响,解决随机游走采样所引发的高度节点偏差问题,并在一定程度上缓解了过平滑效应。

航班延误特征可视分析方法

为分析航班延误发生规律,提出一种数学模型联合多视图协同的可视分析方法。对SEIR传染病传播模型进行调整,建立航班延误传播模型分析延误的传播特征,在此基础上,运用频繁子图挖掘算法提取延误频繁模式;设计基于中点分割的地图网络图、矩阵热力图和时序图,分析延误的时空分布特征;设计VA-FDC系统用于方法验证。实验结果表明,VA-FDC能够有效分析航班延误时空分布特征,依据航班延误传播模型准确描述延误传播特征,为相关部门有效措施的制定提供借鉴。

k阶采样和图注意力网络的知识图谱表示模型

知识图谱表示(KGE)旨在将知识图谱中的实体和关系映射到低维度向量空间而获得其向量表示。现有的KGE模型只考虑一阶近邻,这影响了知识图谱中推理和预测任务的准确性。为了解决这一问题,提出了一种基于k阶采样算法和图注意力网络的KGE模型。k阶采样算法通过聚集剪枝子图中的k阶邻域来获取中心实体的邻居特征。引入图注意力网络来学习中心实体邻居的注意力值,通过邻居特征加权和得到新的实体向量表示。利用ConvKB作为解码器来分析三元组的全局表示特征。在WN18RR、FB15k-237、NELL-995、Kinship数据集上的评价实验表明,该模型在链接预测任务上的性能明显优于最新的模型。此外,还讨论了阶数k和采样系数b的改变对模型命中率的影响。

基于复杂网络的突发事件下汽车产业供应链韧性研究

汽车产业供应链中,各企业间由于合作伙伴关系或者竞争关系而产生的交互作用影响整个供应链网络,加之其参与主体众多,更易受到各种突发事件的干扰影响网络韧性。文章以复杂网络模型为基础,收集中国经济金融研究数据库数据库汽车供应链板块中141家车企数据构建复杂网络关系矩阵模型,通过复杂网络特性分析对所构建的网络模型进行检验。采用目标干扰和随机干扰两种方式来模拟突发事件产生的供应链中断情景,由矩阵工厂和大型复杂网络分析工具对网络进行仿真实验,通过最大连通子图所表示的弹性性能和效率性能两项数据来观测网络稳定性,得出提升汽车产业供应链韧性的方法。

以子图融合为最小单位的混合精度推理

近几年卷积神经网络作为深度学习最重要的技术,在图像分类、物体检测、语音识别等领域均有所建树。在此期间,由多层卷积神经网络组成的深度神经网络横空出世,在各种任务准确性方面具有显著提升。然而,神经网络的权重往往被限定在单精度类型,使网络体积相较于特定硬件平台上的内存空间更大,且floating point 16、INT 8等单精度类型已无法满足现在一些模型推理的现实需求。为此,提出一种以子图为最小单位,通过判断相邻结点之间的融合关系,添加了丰富比特位的混合精度推理算法。首先,在原有单精度量化设计的搜索空间中增加floating point 16半精度的比特配置,使最终搜索空间变大,为寻找最优解提供更多机会。其次,使用子图融合的思想,通过整数线性规划将融合后的不同子图精度配置,根据模型大小、推理延迟和位宽操作数3个约束对计算图进行划分,使最后累积的扰动误差减少。最终,在ResNet系列网络上验证发现,所提模型精度相较于HAWQ V3的损失没超过1%的同时,相较于其他混合精度量化方法在推理速度方面得到了提升,在ResNet18网络中推理速度分别提升18.15%、19.21%,在ResNet50网络中推理速度分别提升13.15%、13.70%。

基于图挖掘的黑灰产运作模式可视分析

为分析黑灰产网络资产图谱数据中黑灰产团伙掌握的网络资产及其关联关系,提出一种基于图挖掘的黑灰产运作模式可视分析方法.首先,在网络资产图谱数据中锁定潜在团伙线索;其次,根据潜在线索、黑灰产业务规则挖掘由同一黑灰产团伙掌握的网络资产子图,并识别子图中的核心资产与关键链路;最后,基于标记核心资产和关键链路的黑灰产子图实现可视分析系统,从而直观发现黑灰产团伙掌握的网络资产及其关联关系,帮助分析人员制定黑灰产网络资产打击策略.经实验验证,该方法能有效、直观地分析和发现黑灰产团伙及其网络资产关联关系,为更好监测黑灰产网络运作态势提供必要的技术支持.

一种基于子图转述的问题生成方法

本文提出了一种子图转述的方法用于解决知识图谱问题生成中的未见谓词问题.传统的问题生成方法主要利用标注的问答数据(问题-逻辑形式对)生成问题,然而标注数据难以覆盖知识图谱中所有的谓词,如何对未见的谓词生成问题依然是一个挑战.本文提出了一种基于子图结构的语义解耦方法,通过将复杂问题对应的知识图谱子图分解为原子级子图,从而将包含未见谓词的多跳子图拆分为易于处理的单跳子图.并且本文设计了一种子图转述方法,通过对数据集中的谓词进行采样,得到子图描述文本,并在大规模无监督数据上训练得到子图转述器,能够为包含未见谓词的子图提供自然语言形式的表述,为生成问题提供了有效的信息.本文定量分析了在不同的难度级别下模型的性能表现,在GrailQA等数据集上的实验结果表明,本文的方法达到了最先进的性能.

子图匹配和强化学习增强的三维点云配准

针对低质量三维点云数据配准精度不足、效率低的问题,为了实现低质量点云的精确、快速配准,提出一种基于子图匹配和强化学习的点云配准方法.首先将三维点云配准转化为一系列离散的刚性变换连续作用结果,利用强化学习策略训练一个端到端的模型以迭代输出刚性变换动作;然后对于模型架构,采用双流主干网络分别提取源点云与目标点云的局部特征信息,设计交叉图注意力模块将源点云图和目标点云图中的相似节点关联起来,使用带选通向量的加权实现图节点的聚合,分别获取源点云图与目标点云图的全局特征表示;最后融合源点云图与目标点云图的全局特征,基于融合特征预测离散的刚性变换动作.强化学习策略的引入显著提高了点云配准算法的泛化性,在加入交叉图注意力模块后,点云配准的精度及效率也进一步被提升.在ModelNet40和ScanObjectNN这2个公共基准数据集上与最新的点云配准方法 ReAgent进行实验的结果表明,所提方法能够将旋转误差的均方差数值降低至少0.16,各向同性旋转误差数值也降低至少0.16,有效地提升低质量点云配准的精度.

基于国产DCU异构平台的图匹配算法移植与优化

子图匹配是一种基础的图算法,被广泛应用于社交网络、图神经网络等众多领域。随着图数据规模的增长,人们迫切需要高效的子图匹配算法。GENEVA是一种基于GPU的并行子图匹配算法,其利用区间索引的图存储结构和并行匹配优化方法,能够大幅度减少存储开销,提升子图匹配性能。但由于平台底层硬件架构和编译环境的不同,GENEVA无法直接应用到国产DCU异构平台。为了解决该问题,提出了GENEVA面向国产DCU的移植和优化方案。IO时间开销是GENEVA算法主要的性能瓶颈,文中采用锁页内存、预加载、调度器3种优化策略来突破该瓶颈。其中,锁页内存技术避免了从可分页内存到临时锁页内存的额外数据传输,在DCU平台上大幅度减少了IO传输的时间开销;预加载技术将IO数据传输与DCU核函数计算重叠,掩盖了IO时间开销;调度器在满足预加载需求的同时,减少了冗余数据的传输。在3个不同规模的真实数据集上进行实验,结果表明,采用优化策略后算法性能显著提高。在92.6%的测试用例上,经过优化的GENEVA-HIP算法在国产DCU平台的执行时间比移植前的GENEVA算法在GPU服务器的执行时间短。在较大规模的数据集上,优化的GENEVA-HIP算法在DCU平台上的执行时间相比移植前的GENEVA算法在GPU服务器的执行时间减少了52.73%。

采用局部子图嵌入的MOOCs知识概念推荐模型

大规模开放在线课程(MOOCs)在减少用户学习盲区和改善用户体验方面已经有大量的研究,尤其是基于图神经网络的个性化课程资源推荐,但现有工作主要集中在固定或同质图上,容易受到数据稀疏问题的影响且难以扩展。在局部子图上使用图卷积,并结合扩展的矩阵分解(MF)模型来解决这一问题。首先,将异构图分解为多个基于元路径的子图,结合随机游走采样方法实现在采样节点富有影响力邻域的同时捕获实体之间复杂的语义关系,并在局部邻域上进行图卷积平滑各节点表示,实现高可扩展性;然后,使用注意力机制适应性地融合不同子图的上下文信息,更全面地构建用户偏好;最后,通过扩展矩阵分解优化模型参数,获得推荐列表。为了验证提出模型的性能,在公开的MOOCs数据集上进行对比实验,相较于最优基线,性能提升了2%,内存计算需求降低了近500%,缓解数据稀疏问题的同时仍具有较强的可扩展性。

基于可控制性度量的图神经网络门级硬件木马检测方法

随着全球化的不断深入,第三方知识产权(IP)核应用越来越广泛。随着硬件木马攻击技术逐渐成熟,使得在芯片设计阶段植入硬件木马成为可能。因此,在芯片设计过程中面临IP核被植入木马的严重威胁,现有研究所提的硬件木马检测方法具有依赖黄金参考电路、需要完备的测试向量、大量的样本进行学习等特征。面向IP核的硬件木马检测需求,提出一种基于可控制性度量的图神经网络检测方法。该方法以门级网表作为输入,首先以可控制性值为指导,得到可疑的门节点,用于缩小搜索范围;然后利用可疑门节点生成对应的子图,利用图卷积神经网络从子图中提取特征,实现对子图的分类和检测,最终识别硬件木马。实验结果表明,该方法无须测试激励和黄金模型,利用硬件木马的隐蔽特性与结构特征相结合的方法提升硬件木马的检测准确率,平均真阳率为100%,假阳率为0.75%,在保证较高真阳率的同时可有效降低假阳率,达到较好的检测效果。

基于知识子图与注意力机制的在线课程推荐模型

推荐系统可以帮助用户在海量的资源中筛选出满足其需求的项目,不断发展的推荐系统为在线教育提供了新的思路。在线课程资源推荐作为在线教育领域中的重要一环,目前存在课程资源过载和课程推荐结果缺乏可解释性的问题。对此,该文提出了一种基于知识子图与注意力机制的在线课程推荐模型,以利用知识子图进行推荐。有别于直接利用知识图谱进行推荐而忽略了知识表示不准确问题的模型,该模型首先采用Node2vec随机游走方法从知识图谱中提取连接用户-课程对的连通子图,然后通过分层注意网络对子图进行编码,以生成用于用户所需课程预测的子图嵌入,最后生成Top-N推荐课程列表,并给出模型的可解释性说明。为验证模型的有效性,以“中国大学MOOC(慕课)”上的数据为样本构建数据集,实验结果表明,相较于KGCN-PN、GAT、KGAT以及POCR模型,文中模型在NDCG、HR以及MRR评价指标上分别提升了10.6%,9.41%,13.7%。

面向干扰项增强的无监督常识问答模型

问题生成是无监督常识问答模型的一个核心子任务,目前的方法主要是根据给定知识生成问题和答案,并为每个问题随机生成多个干扰项,然而这些方法存在干扰项与问题相关性不强且随机性较大的问题。该文提出一种面向干扰项增强的无监督常识问答模型,首先根据知识三元组生成问题和正确答案,再为问题建立对应的问题子图,得到与问题相关的三元组集合,使用注意力机制增强特征并根据问题和正确答案确定干扰项,最后使用生成的数据对模型进行训练。该模型在四个不同类型的测试任务上的结果表明,该模型优于目前的最新方法,证明了该模型的有效性。

时序网络上异常演化模式研究

许多异常子图检测方法已经被成功应用于社交网络中的事件检测、道路网络中的交通拥堵检测等任务中。然而,在属性图中异常子图的动态演化方面,鲜有研究开展。文中提出了一种名为动态演化多异常子图扫描(DE-MASS)的方法,用于检测属性图上多个异常子图的演化模式,这是第一个捕捉相邻时间片上多个相连异常子图的动态图研究。DE-MASS在微博数据集、计算机流量数据集上的表现优于其他基准方法,并检测到3个实际应用中异常子图的演化模式:城市道路网络中的交通拥堵检测(北京、天津和南京)、社交网络(微博)中的事件检测和计算机流量网络中的网络攻击检测。

二维四角网格图的反馈数上界的改进

设G=(V,E)是简单图,子集F?V。若由点集V-F导出的子图不含圈,则称子集F是图G的反馈集。称反馈集的点数的最小值是图G的反馈数,用f(G)表示,即,f(G)=min{|F|:F是图G的反馈集}。Caragiannis等人给出了二维四角网格图反馈数的上界,本文改进了其上界。

SIHC:一种高效的时态图上k-core查询算法

许多实体之间的关系可以建模为时态图,其中每条边都与表示其发生的时间相关联,k-core是捕获密集子图的基本模型,在近些年得到了广泛研究.给定时间区间I=[s,e]和k值,时态图G上的k-core子图查询从区间I对应的快照图GI中返回相应的k-core子图.针对时态图中的k-core子图查询问题,现有方法是基于PHC索引(Pruned Historical Core-Index)的算法.对任意可能的k值,PHC索引维护了所有可能出现在某个时间区间的k-core子图中的顶点集Sk,且为集合中每个顶点存储了一组时间区间,用于判定该点是否属于给定时间区间的k-core子图.基于PHC索引查询k-core子图时,需要访问Sk集合中的所有顶点,并判断每个顶点的可满足性.由于Sk集合对应于最大区间快照图的k-core子图里的所有顶点,且实际中用户查询区间对应的快照图往往比最大区间快照图小得多,基于PHC索引的查询算法存在许多无效判断,需要对大量不在结果集中的顶点进行检测,且无效检测次数随着查询区间的缩短而增多,从而导致算法效率较低.针对该问题,本文提出一种新的索引,即最短区间历史核索引SIHC(Shortest Interval Historical Core Index).SIHC索引的基本思想是通过维护最短k核区间到顶点的倒排表,查询处理时,可基于用户给定的时间区间定位到SIHC索引中满足条件的区间,进而直接得到满足条件的k-core子图中的顶点,从而避免了基于PHC索引进行查询时所需的大量无效判断.我们从理论上证明了基于SIHC索引处理时态图上k-core子图查询的正确性,并设计了高效的索引构建算法.最后,基于真实世界的时态图进行了实验,实验结果表明本文提出的算法比现有算法快1~2个数量级.

融合子图结构的知识图谱嵌入对抗性攻击方法

知识图谱嵌入(Knowledge Graph Embedding,KGE)技术的高速发展极大提高了人类对于结构化知识的利用效率,该技术也为人工智能的相关应用提供了有利的支撑.但是知识图谱嵌入方法的脆弱性(vulnerability)给知识图谱的应用带来了巨大的挑战,近期的一些研究表明,在训练数据中添加微小的扰动便能对训练后的机器学习模型造成巨大的影响,甚至导致错误的预测结果.目前针对可能破坏知识图谱嵌入模型的安全漏洞的研究大多关注嵌入模型的损失函数而忽略图结构信息的作用,因此本文提出了一种融合子图结构深度学习的攻击方法DLOSSAA(Deep Learning of Subgraph Structure Adversarial Attack),对知识图谱嵌入的健壮性进行研究.DLOSSAA方法首先通过对子图结构的深度学习捕获相关子图的结构信息,然后通过修正的余弦相似度(Adjusted Cosine Similarity)筛选出最佳的攻击样本,最后将攻击样本添加到训练数据中进行攻击.实验结果表明,该方法能够有效降低攻击后的知识图谱嵌入模型的性能,攻击效果优于大部分已有的对抗性攻击方法.

大规模知识图谱数据的分布式存储与检索系统

知识图谱已经广泛应用于各个领域。针对传统集中式查询的效率低和硬件压力大等问题,对大规模知识图谱的分布式检索与查询进行了研究。采用基于查询负载优化的轻量级重划分算法,通过设置不同权重实现了服务器间的查询负载均衡,从而在查询速度和系统性能上都有了显著的提高。同时,设计了基于查询代价的子图分解查询算法,以查询图的结构信息为基础,加快了系统的查询速度。在分布式微服务管理系统中,采用Spring Cloud的分布式微服务架构和Nginx的负载均衡技术,保证了系统在高并发情况下的可靠性和高可用性。实验结果表明,这些算法在查询效率和系统性能方面都优于传统算法,具有实际应用价值。