知识图谱中有着丰富的知识,一个重要的应用是利用知识图谱进行文本扩充,从而帮助读者更好地理解文档内容,比如新闻。这需要将文本中出现的实体映射到知识图谱中,在图谱中找到连接目标实体的子图,称之为实体关联。这些关联能够给读者呈现文本的背景知识。一般来说,搜索实体关联代价较高,不能扩展到大的图谱中。因此,通常将实体关联限制为结构紧凑的,但这样可能导致结果不存在,因为关联太小而无法包含所有的目标实体。本文通过计算包含最重要,而不是所有的目标实体的近似关联来解决这个问题。本文面向关联搜索问题首先研究了查询松弛工作,提出了证书的概念并证明它只需满足两个距离条件就能够验证查询的成功,据此设计了一种基于距离估计的最佳优先搜索算法,进一步地,提出两种启发式加快算法的速度。实验结果表明了该算法的有效性和伸缩性。本文还提出了一种基于语义内聚性和关联与文本的相关性的上下文相关的排序算法,用户实验表明它优于现有的最先进的上下文相关的算法。此外,本文还设计了一个系统,将关联查询松弛、关联搜索和关联排序结合,应用在新闻知识扩充的场景中。