融合拓扑特征和领域特征的非精确图匹配算法

针对结构模式识别领域中现有图匹配算法对反映图本身拓扑结构的节点特征挖掘不够充分的问题,提出融合拓扑特征和领域特征的非精确图匹配算法。利用建筑学与城市规划学科中的空间句法理论构造图拓扑特征的量化描述,并将其与节点属性和边属性等其他领域的非拓扑特征相结合,构造描述图特征的特征向量,以此为桥梁将结构模式识别问题转化为统计模式识别问题,进而借助支持向量机实现非精确图匹配。不同于其他的图匹配算法,该算法对图的拓扑表达能力强,并且可融合图的领域方面的非拓扑特征,通用性较好。实验结果表明,提出的图匹配算法在不同的图数据集上均具有较高的分类识别率。     

多图嵌入表示在人体运动模式识别中的应用

新颖和恰当的算法是人体运动模式识别系统的关键。在获取加速度传感器信号的基础上,提出了一种人体运动模式识别算法,其中多图嵌入表示用于特征降维,最近邻用于模式分类。该算法通过特征分组对原始特征空间进行多个独立子集的划分,并生成图;通过多维尺度分析法在每个子图上生成新的嵌入坐标,并找到这些嵌入坐标的线性组合来表示原始特征空间;最后通过最近邻分类器进行模式分类。该算法新颖、简单,能在最小信息丢失的基础上挖掘原始特征空间的潜在结构,提高特征选择的稳定性。实验结果表明,同其他代表性算法相比,该算法准确度高,能更好地区分人体运动。     

图嵌入模型综述

图分析用于深入挖掘图数据的内在特征,然而图作为非欧几里德数据,传统的数据分析方法普遍存在较高的计算量和空间开销。图嵌入是一种解决图分析问题的有效方法,其将原始图数据转换到低维空间并保留关键信息,从而提升节点分类、链接预测、节点聚类等下游任务的性能。与以往的研究不同,同时对静态图和动态图嵌入文献进行全面回顾,提出一种静态图嵌入和动态图嵌入通用分类方法,即基于矩阵分解的图嵌入、基于随机游走的图嵌入、基于自编码器的图嵌入、基于图神经网络(GNN)的图嵌入和基于其他方法的图嵌入。其次,对静态图和动态图方法的理论相关性进行分析,对模型核心策略、下游任务和数据集进行全面总结。最后,提出了四个图嵌入的潜在研究方向。     

基于原型选择的图嵌入方法研究

图嵌入方法为结构化模式识别问题转化为统计模式识别问题搭建了桥梁。而随着训练样本集规模的增加,为避免图嵌入时的维度灾难现象,对训练样本集进行原型选择是十分必要的。因此,本文提出一种基于类内和类间相均衡的原型选择方法,该方法通过对训练样本上的每一类的类内和其他类进行均衡化处理,分别选出每个类上依据均衡化程度排列的原型。实验表明,与未进行原型选择策略相比,本方法能较为有效地降低了图嵌入时的空间维度,且具有较高的分类精度。     

多尺度特征图融合的目标检测

目的 自然场景图像中,特征提取的质量好坏是决定目标检测性能高低的关键因素。大多数检测算法都是利用卷积神经网络（CNN）强大的学习能力来获得目标的先验知识,并根据这些知识进行目标检测。卷积神经网络的低层次特征缺乏特征的代表性,而高层次的特征则对小尺度目标的监测能力弱。方法 利用原始SSD（single shot multiBox detector）网络提取特征图,通过1×1卷积层将提取的特征图统一为256维;通过反卷积操作增加自顶向下特征图的空间分辨率;通过对应元素相加的操作,将两个方向的特征图进行融合。将融合后的特征图采用3×3的卷积核进行卷积操作,减小特征图融合后的混叠效应。根据以上步骤构建具有较强语义信息的特征图,同时保留原有特征图的细节信息;对预测框进行聚合,利用非极大抑制（NMS）实现最终的检测效果。结果 在PASCAL VOC 2007和PASCAL VOC 2012数据集上进行实验测试,该模型的mAP（mean average precision）为78.9%和76.7%,相对于经典的SSD算法,分别提高了1.4%和0.9%;此外,本文方法在检测小尺度目标时相较于经典SSD模型mAP提升了8.3%。结论 提出了一种多尺度特征图融合的目标检测算法,以自顶向下的方式扩展了语义信息,构造了高强度语义特征图用于实现精确目标检测。     

提升图嵌入框架及在表情识别中的应用 *

提出了一种提升图嵌入框架用于特征提取和选择 ,以及一种新的近邻权重计算方法 ,称为分类图。传统图嵌入模型的近邻权重采用欧氏距离 ,不能被提升算法所更新 ;相比较 ,分类图采用的是提升算法中样本的权重,反映的是样本在分类过程中的重要程度 ,有效地提高了图嵌入模型的分类性能。在通用人脸表情库上的识别实验结果验证了提升图嵌入模型的有效性。     

具有统计不相关性的核化图嵌入算法

提出统计不相关的核化图嵌入算法,为求解各种统计不相关的核化降维算法提供了一种统一方法。与已有核化降维算法相比,新的特征提取方法降低甚至消除了最佳鉴别矢量间的统计相关性,提高了识别率。通过在ORL,YALE和FERET人脸库上的实验结果表明,提出的具有统计不相关的核化图嵌入算法在识别率方面好于已有的核算法。另外,揭示了统计不相关的核化图嵌入与已有的核化图嵌入的内在关系。     

基于图嵌入的软件项目源代码检索方法

源代码检索是软件工程领域的一项重要研究问题,其主要任务是检索和复用软件项目API（application program interface,应用程序接口）.随着软件项目的规模越来越大、越来越复杂,当前,源代码检索一方面需要提高基于自然语言API查询的准确性,另一方面需要定位和展示目标API及其相关代码之间的关联,以更好地辅助用户理解API的实现逻辑和使用场景.为此,提出一种基于图嵌入的软件项目源代码检索方法.该方法能够基于软件项目源代码自动构建其代码结构图,并通过图嵌入对源代码进行信息表示.在此基础上,用户可以输入自然语言问题、检索并返回相关的API及其关联信息构成的连通代码子图,从而提高API检索和复用的效率.在以开源项目Apache Lucene和POI为例的检索实验中,该方法检索结果的F1值比现有基于最短路径的方法提高了10%,同时显著缩短了平均响应时间.     

基于空间句法和最短路径的图核

针对图模式识别领域中现有图核方法对反映图本身拓扑结构的节点特征挖掘不够充分的问题,提出了基于空间句法和最短路径的图核。借鉴建筑学与城市规划学科中的空间句法理论构造分布于图节点上的拓扑特征的量化描述,基于此提出了可表示、计算,正定、适用范围较广的空间句法核和基于最短路径的空间句法核,进而借助支持向量机实现了非精确图匹配。不同于其他图核方法,该方法对图的拓扑特征表达能力强,通用性较好。实验结果表明,所设计的图核在分类精度方面相较于最短路径核有较显著的改善。     

一种新的多嵌入延迟相空间重构方法

对文献[5]提出的Cao方法进行了改进,提出一种新的多嵌入延迟相空间重构方法,不仅能够判断最小嵌入维数,还能够确定最佳时间延迟矢量。Cao方法的应用领域得以扩展,使得相空间重构问题可以在一个判断标准下完成。数值仿真结果表明,该改进方法在处理包含多个强烈周期成分的信号时比目前常用的单一嵌入延迟方法有明显优势。     

一种改进的自适应知识图谱嵌入式表示方法

知识图谱的嵌入式表示方法以基于翻译的TransE最为经典,但在处理复杂关系时存在局限;使用欧氏距离作为得分函数中的度量,每个特征维度以相同的权重参与计算,准确性会受到无关维度的影响,灵活性不高。因此,针对这两个缺陷,提出一种自适应的知识图谱嵌入式表示方法TransAD。利用自适应度量方法更换度量函数,在得分函数中引入对角权重矩阵,为每一个特征维分别赋予权重,增加模型的表示能力。同时受TransD方法的启发,将实体与关系通过动态映射矩阵建立空间投影模型,来增强模型对复杂关系的处理能力,最后将两种优化集成在一个模型中。实验结果表明,新方法TransAD优于Trans(E,H,R,D),在链路预测和三元组分类任务的各项指标上均有提升,有一定的先进性。     

基于参考节点嵌入的图可达性查询

针对k步可达性查询算法无法解决带距离约束的图可达性查询问题,提出基于参考节点嵌入的图可达性查询算法。首先,从所有节点中选出极少数有代表性的全局参考节点,预先计算所有节点与全局参考节点之间的最短路径距离;然后,采用最短路径树和范围最小值查询技术求得局部参考节点;接着,利用三角不等式关系得到查询点对距离范围;最后,根据查询条件中的距离值与查询点对距离范围上、下限值的大小关系,可快速得出可达性结论。针对社会关系网络和公路网络数据,将所提算法与Dijkstra算法、K-Reach算法进行实验对比测试。相较于K-Reach算法,其索引建立时间小4个数量级,其索引规模小2个数量级;相较于Dijkstra算法,在公路网络和社会关系网络中,直接得出可达性结论的比例分别为92%和78.6%,其查询时间大大缩短,分别降低了95.5%和92%。实验结果表明：所提算法能够通过使用较小的索引开销,实现在线查询计算复杂度的降低,可很好地解决既适用于有权图又适用于无权图带距离约束的可达性查询问题。     

知识图谱的增强CP分解链接预测方法

CP分解作为知识图谱链接预测的方法之一,能够对一些包含常规数据的知识图谱进行链接预测补全。但当知识图谱存在大量稀疏数据及可逆关系时,该方法不能体现两个实体间具有的隐藏联系,无法对此类数据进行处理。为解决上述问题,提出增强CP分解方法,对三元组中前实体和后实体的两个嵌入向量分别进行学习,并在训练过程中使用概率方法生成更高质量的负例三元组,引入ELU损失函数和AMSGrad优化器,有效对可逆关系和稀疏数据进行处理。在通用数据集上的实验结果表明,所提方法可以有效提升链接预测精度,与对比模型相比取得了5%的性能提升,同时应用在汽车维修知识图谱数据集补全中,取得83.2%正确率的实体补全结果。     

Towards the Web of Embeddings: Integrating multiple knowledge graph embedding spaces with FedCoder

The Semantic Web is distributed yet interoperable: Distributed since resources are created and published by a variety of producers, tailored to their specific needs and knowledge; Interoperable as entities are linked across resources, allowing to use resources from different providers in concord. Complementary to the explicit usage of Semantic Web resources, embedding methods made them applicable to machine learning tasks. Subsequently, embedding models for numerous tasks and structures have been developed, and embedding spaces for various resources have been published. The ecosystem of embedding spaces is distributed but not interoperable: Entity embeddings are not readily comparable across different spaces. To parallel the Web of Data with a Web of Embeddings, we must thus integrate available embedding spaces into a uniform space.Current integration approaches are limited to two spaces and presume that both of them were embedded with the same method — both assumptions are unlikely to hold in the context of a Web of Embeddings. In this paper, we present FedCoder— an approach that integrates multiple embedding spaces via a latent space. We assert that linked entities have a similar representation in the latent space so that entities become comparable across embedding spaces. FedCoder employs an autoencoder to learn this latent space from linked as well as non-linked entities.Our experiments show that FedCoder substantially outperforms state-of-the-art approaches when faced with different embedding models, that it scales better than previous methods in the number of embedding spaces, and that it improves with more graphs being integrated whilst performing comparably with current approaches that assumed joint learning of the embeddings and were, usually, limited to two sources. Our results demonstrate that FedCoder is well adapted to integrate the distributed, diverse, and large ecosystem of embeddings spaces into an interoperable Web of Embeddings.     

Fast Frequent Free Tree Mining in Graph Databases

Free tree, as a special undirected, acyclic and connected graph, is extensively used in computational biology, pattern recognition, computer networks, XML databases, etc. In this paper, we present a computationally efficient algorithm F3TM (Fast Frequent Free Tree Mining) to find all frequently-occurred free trees in a graph database, . Two key steps of F3TM are candidate generation and frequency counting. The frequency counting step is to compute how many graphs in containing a candidate frequent free tree, which is proved to be the subgraph isomorphism problem in nature and is NP-complete. Therefore, the key issue becomes how to reduce the number of false positives in the candidate generation step. Based on our observations, the cost of false positive reduction can be prohibitive itself. In this paper, we focus ourselves on how to reduce the candidate generation cost and minimize the number of infrequent candidates being generated. We prove a theorem that the complete set of frequent free trees can be discovered from a graph database by growing vertices on a limited range of positions of a free tree. We propose two pruning algorithms, namely, automorphism-based pruning and canonical mapping-based pruning, which significantly reduce the candidate generation cost. We conducted extensive experimental studies using a real application dataset and a synthetic dataset. The experiment results show that our algorithm F3TM outperforms the up-to-date algorithms by an order of magnitude in mining frequent free trees in large graph databases.     

基于图的指纹匹配算法

研究了基于端点和分支点的点模式指纹匹配算法，通过对端点和分支点的完全图进行匹配，使其具有较好的稳定性。对匹配图像端点和分支点进行分组，通过每组的点和模板图像的细节点进行点模式匹配来实现指纹匹配，有效地降低了运算复杂度。实验结果表明，该方法在指纹产生非线性形变、指纹图像质量低等情况下有较好的性能，具有较强的实用性。