随着互联网和人工智能技术的发展,对知识以及及知识间的关系逐渐得到重视。互联网已从超链的文档万维网转变成为了包含实体间大量关系的数据万维网,其包含了实体间丰富关系的语义网络,称为知识图谱(Knowledge Graph),被认为是未来搜索引擎的核心。各搜索公司如Google、百度和搜狗等纷纷展开知识图谱的研究,以提高搜索质量。目前主流的知识图谱,诸如Freebase,DBpedia,NELL等,虽包含了上亿条事实数据,但尚存在不足,如在自动构建知识图谱的过程中,实体与实体之间存在许多潜在未知关系,并未完全标识出。因此,基于知识推理算法,自动推理出实体间的关联关系来补全知识图谱,构建一个相对完整的知识图谱,在语义搜索,人工智能,商业决策等方面具有重要意义。本文针对目前基于图的知识推理算法存在的路径连通性问题和计算开销大的问题,进行了改进,主要工作包括:(1)对当前主流的知识图谱以及相关知识进行了分析介绍,在研究了国内外知识推理的研究现状的基础上,综述了知识图谱构建及推理涉及的关键技术,并指出了当前研究中存在的问题和挑战。(2)提出了一种基于特征词集合进行路径补全的优化方法。在基于图的游走过程中,由于知识图谱中实体间的关系缺失导致实体之间路径不连通,从而无法搜索到有效路径。本方法充分利用实体的描述文本信息,利用TF-IDF算法提取实体的特征词集合来补充路径缺失信息,较好的解决了路径连通性问题。实验结果表明,本方法提高了模型推理的精确度。(3)提出了一种利用上位词划分实体领域的路径约束游走剪枝的方法。由于知识图谱中的路径数量庞大,每步游走将导致路径数量呈指数级增长,为减少路径搜索的量级,本方法针对图上游走的路径发现策略进行了改进。基于百科分类体系构建包含层级分类结构的上位词表,通过word2vec训练词向量,计算字符串相语义相似度,对知识图谱中的实体进行领域划分,通过仅对相关领域内的实体节点进行游走,大大减少了条件约束下的路径数量类型。实验结果表明,本方法有效提高了计算性能。