针对知识推理模型在捕获实体之间的复杂语义特征方面难以捕捉多层次语义信息,同时未考虑单一路径的可解释性对正确答案的影响权重不同等问题,提出一种融合路径与子图特征的知识图谱(KG)多跳推理模型PSHAM(Hierarchical Attention Model ...针对知识推理模型在捕获实体之间的复杂语义特征方面难以捕捉多层次语义信息,同时未考虑单一路径的可解释性对正确答案的影响权重不同等问题,提出一种融合路径与子图特征的知识图谱(KG)多跳推理模型PSHAM(Hierarchical Attention Model fusing Path-Subgraph features)。PS-HAM将实体邻域信息与连接路径信息进行融合,并针对不同路径探索多粒度的特征。首先,使用路径级特征提取模块提取每个实体对之间的连接路径,并采用分层注意力机制捕获不同粒度的信息,且将这些信息作为路径级的表示;其次,使用子图特征提取模块通过关系图卷积网络(RGCN)聚合实体的邻域信息;最后,使用路径-子图特征融合模块对路径级与子图级特征向量进行融合,以实现融合推理。在两个公开数据集上进行实验的结果表明,PS-HAM在指标平均倒数秩(MRR)和Hit@k(k=1,3,10)上的性能均存在有效提升。对于指标MRR,与MemoryPath模型相比,PS-HAM在FB15k-237和WN18RR数据集上分别提升了1.5和1.2个百分点。同时,对子图跳数进行的参数验证的结果表明,PS-HAM在两个数据集上都在子图跳数在3时推理效果达到最佳。展开更多
With the development of information technology, the amount of power grid topology data has gradually increased. Therefore, accurate querying of this data has become particularly important. Several researchers have cho...With the development of information technology, the amount of power grid topology data has gradually increased. Therefore, accurate querying of this data has become particularly important. Several researchers have chosen different indexing methods in the filtering stage to obtain more optimized query results because currently there is no uniform and efficient indexing mechanism that achieves good query results. In the traditional algorithm, the hash table for index storage is prone to "collision" problems, which decrease the index construction efficiency. Aiming at the problem of quick index entry, based on the construction of frequent subgraph indexes, a method of serialized storage optimization based on multiple hash tables is proposed. This method mainly uses the exploration sequence to make the keywords evenly distributed; it avoids conflicts of the stored procedure and performs a quick search of the index. The proposed algorithm mainly adopts the "filterverify" mechanism; in the filtering stage, the index is first established offline, and then the frequent subgraphs are found using the "contains logic" rule to obtain the candidate set. Experimental results show that this method can reduce the time and scale of candidate set generation and improve query efficiency.展开更多
Subgraph matching problem is identifying a target subgraph in a graph. Graph neural network (GNN) is an artificial neural network model which is capable of processing general types of graph structured data. A graph ma...Subgraph matching problem is identifying a target subgraph in a graph. Graph neural network (GNN) is an artificial neural network model which is capable of processing general types of graph structured data. A graph may contain many subgraphs isomorphic to a given target graph. In this paper GNN is modeled to identify a subgraph that matches the target graph along with its characteristics. The simulation results show that GNN is capable of identifying a target sub-graph in a graph.展开更多
Bollobas and Gyarfas conjectured that for n 〉 4（k - 1） every 2-edge-coloring of Kn contains a monochromatic k-connected subgraph with at least n - 2k ＋ 2 vertices. Liu, et al. proved that the conjecture holds when...Bollobas and Gyarfas conjectured that for n 〉 4（k - 1） every 2-edge-coloring of Kn contains a monochromatic k-connected subgraph with at least n - 2k ＋ 2 vertices. Liu, et al. proved that the conjecture holds when n 〉 13k - 15. In this note, we characterize all the 2-edge-colorings of Kn where each monochromatic k-connected subgraph has at most n - 2k ＋ 2 vertices for n ≥ 13k - 15.展开更多
Alavi and his fellows defined the concept of ascending subgraph decomposition of a graph and conjectured that every graph with positive size has an ascending subgraph decomposition in paper [1]. Paper [2] proved that ...Alavi and his fellows defined the concept of ascending subgraph decomposition of a graph and conjectured that every graph with positive size has an ascending subgraph decomposition in paper [1]. Paper [2] proved that K n-R n-1 has a star ascending subgraph decomposition,here K n is the complete graph with order n and R n-1 is a subgraph of K n with size at most n-1. In paper [3],Ma Kejie and Chen Huaitang proved that K n-R n has an ascending subgraph decomposition when the size of R n is not greater than n. In this paper we will prove K n-R has an ascending subgraph decomposition when the size of R is less than 3n/2. This paper will also give the concept of comet and prove that K n-R n-1 has a comet ascending subgraph decomposition.展开更多
The definition of the ascending subgraph decomposition was given by Alavi. It has been conjectured that every graph of positive size has an ascending subgraph decomposition. In this paper it is proved that the regular...The definition of the ascending subgraph decomposition was given by Alavi. It has been conjectured that every graph of positive size has an ascending subgraph decomposition. In this paper it is proved that the regular graphs under some conditions do have an ascending subgraph decomposition.展开更多
近几年卷积神经网络作为深度学习最重要的技术,在图像分类、物体检测、语音识别等领域均有所建树。在此期间,由多层卷积神经网络组成的深度神经网络横空出世,在各种任务准确性方面具有显著提升。然而,神经网络的权重往往被限定在单精度...近几年卷积神经网络作为深度学习最重要的技术,在图像分类、物体检测、语音识别等领域均有所建树。在此期间,由多层卷积神经网络组成的深度神经网络横空出世,在各种任务准确性方面具有显著提升。然而,神经网络的权重往往被限定在单精度类型,使网络体积相较于特定硬件平台上的内存空间更大,且floating point 16、INT 8等单精度类型已无法满足现在一些模型推理的现实需求。为此,提出一种以子图为最小单位,通过判断相邻结点之间的融合关系,添加了丰富比特位的混合精度推理算法。首先,在原有单精度量化设计的搜索空间中增加floating point 16半精度的比特配置,使最终搜索空间变大,为寻找最优解提供更多机会。其次,使用子图融合的思想,通过整数线性规划将融合后的不同子图精度配置,根据模型大小、推理延迟和位宽操作数3个约束对计算图进行划分,使最后累积的扰动误差减少。最终,在ResNet系列网络上验证发现,所提模型精度相较于HAWQ V3的损失没超过1%的同时,相较于其他混合精度量化方法在推理速度方面得到了提升,在ResNet18网络中推理速度分别提升18.15%、19.21%,在ResNet50网络中推理速度分别提升13.15%、13.70%。展开更多
基金supported by the State Grid Science and Technology Project (Title: Research on High Performance Analysis Technology of Power Grid GIS Topology Based on Graph Database, 5455HJ160005)
文摘With the development of information technology, the amount of power grid topology data has gradually increased. Therefore, accurate querying of this data has become particularly important. Several researchers have chosen different indexing methods in the filtering stage to obtain more optimized query results because currently there is no uniform and efficient indexing mechanism that achieves good query results. In the traditional algorithm, the hash table for index storage is prone to "collision" problems, which decrease the index construction efficiency. Aiming at the problem of quick index entry, based on the construction of frequent subgraph indexes, a method of serialized storage optimization based on multiple hash tables is proposed. This method mainly uses the exploration sequence to make the keywords evenly distributed; it avoids conflicts of the stored procedure and performs a quick search of the index. The proposed algorithm mainly adopts the "filterverify" mechanism; in the filtering stage, the index is first established offline, and then the frequent subgraphs are found using the "contains logic" rule to obtain the candidate set. Experimental results show that this method can reduce the time and scale of candidate set generation and improve query efficiency.
文摘Subgraph matching problem is identifying a target subgraph in a graph. Graph neural network (GNN) is an artificial neural network model which is capable of processing general types of graph structured data. A graph may contain many subgraphs isomorphic to a given target graph. In this paper GNN is modeled to identify a subgraph that matches the target graph along with its characteristics. The simulation results show that GNN is capable of identifying a target sub-graph in a graph.
基金Supported by the National Natural Science Foundation of China(10701065 and 11101378)Zhejiang Provincial Natural Science Foundation(LY14A010009)
文摘Bollobas and Gyarfas conjectured that for n 〉 4（k - 1） every 2-edge-coloring of Kn contains a monochromatic k-connected subgraph with at least n - 2k ＋ 2 vertices. Liu, et al. proved that the conjecture holds when n 〉 13k - 15. In this note, we characterize all the 2-edge-colorings of Kn where each monochromatic k-connected subgraph has at most n - 2k ＋ 2 vertices for n ≥ 13k - 15.
文摘Alavi and his fellows defined the concept of ascending subgraph decomposition of a graph and conjectured that every graph with positive size has an ascending subgraph decomposition in paper [1]. Paper [2] proved that K n-R n-1 has a star ascending subgraph decomposition,here K n is the complete graph with order n and R n-1 is a subgraph of K n with size at most n-1. In paper [3],Ma Kejie and Chen Huaitang proved that K n-R n has an ascending subgraph decomposition when the size of R n is not greater than n. In this paper we will prove K n-R has an ascending subgraph decomposition when the size of R is less than 3n/2. This paper will also give the concept of comet and prove that K n-R n-1 has a comet ascending subgraph decomposition.
文摘The definition of the ascending subgraph decomposition was given by Alavi. It has been conjectured that every graph of positive size has an ascending subgraph decomposition. In this paper it is proved that the regular graphs under some conditions do have an ascending subgraph decomposition.
文摘近几年卷积神经网络作为深度学习最重要的技术,在图像分类、物体检测、语音识别等领域均有所建树。在此期间,由多层卷积神经网络组成的深度神经网络横空出世,在各种任务准确性方面具有显著提升。然而,神经网络的权重往往被限定在单精度类型,使网络体积相较于特定硬件平台上的内存空间更大,且floating point 16、INT 8等单精度类型已无法满足现在一些模型推理的现实需求。为此,提出一种以子图为最小单位,通过判断相邻结点之间的融合关系,添加了丰富比特位的混合精度推理算法。首先,在原有单精度量化设计的搜索空间中增加floating point 16半精度的比特配置,使最终搜索空间变大,为寻找最优解提供更多机会。其次,使用子图融合的思想,通过整数线性规划将融合后的不同子图精度配置,根据模型大小、推理延迟和位宽操作数3个约束对计算图进行划分,使最后累积的扰动误差减少。最终,在ResNet系列网络上验证发现,所提模型精度相较于HAWQ V3的损失没超过1%的同时,相较于其他混合精度量化方法在推理速度方面得到了提升,在ResNet18网络中推理速度分别提升18.15%、19.21%,在ResNet50网络中推理速度分别提升13.15%、13.70%。
