图目前已被新兴应用广泛用于表示信息,例如谷歌的知识图谱以及基于资源描述框架(Resource Description Framework,RDF)的语义网应用。图结构数据在这些领域里用于描述实体的属性和实体间的关系。特别地,实体以及它们间的二元关系构成了实体关系图。实体之间不仅显式地通过代表关系的弧直接相连,还隐式地通过间接的路径或者子图相连。搜索多个实体之间的关联关系是很多领域中的一种常见信息需求。然而当图的数据规模变大之后,搜索实体间的关联将变得非常具有挑战性。一方面搜索的空间十分巨大,使得搜索本身十分有难度。另一方面,关联搜索的结果数目也十分之多,使得用户在理解和探索这些关联结果时充满困难。本文针对这些问题的解决方案进行了探索。特别地,在大规模图结构表示实体间关系的语义数据上(如知识图谱)进行深入研究。语义关联在这种场景下被定义为连接查询实体的极小连通子图。区别于传统检索高排名结果的方法,本文致力于显式的搜索所有的语义关联并挖掘它们的公共概念模式来组织、摘要结果。以便促进对关联关系结果的理解和探索。具体而言,本文主要有三方面的贡献:1.提出了一个基于距离剪枝的关联搜索算法。该关联搜索算法不仅可以用于传统的两个实体间的关联搜索,还可以应用于多个实体的场景。同时为了在搜索到的语义关联中去除重复,本文定义了语义关联标准码,并提出一种可以在搜索和挖掘中广泛使用的全序关系。2.提出了基于骨架划分的模式挖掘算法来摘要搜索到的语义关联。该算法同时利用语义关联的图结构和标签(即骨架)使得划分的语义关联块更加细粒度,因此可以高效的剪枝掉不可能频繁的语义关联模式。3.进行了较为丰富的实验来评估以上算法。使用了在不同维度充满多样性的真实世界中的大规模图来实验提出的语义关联搜索算法和语义关联模式挖掘算法。在不同参数设置下观察算法效率。