近年来,关于包含不同类型的实体和关系的异质信息网络(Heterogeneous Information Networks,HIN)的研究兴起,特别是知识图谱的出现和完善加快了异质信息网络下相关算法的研究进展。在这种网络中已经探索了许多数据挖掘任务,其中,预测实体之间潜在关系的.链接预测是重要任务之一,是解决异质网络中很多其他问题的基础。关系推理是指通过对异质网络中复杂的网络结构和多样的语义含义分析和挖掘,推理出网络中的潜在关系。它是解决链接预测任务的指导方法。本文首先研究了为关系推理服务的实体相似度度量这个基础性问题,提出了一个基于蒙特卡洛模拟的随机路径采样算法——RSSim,来解决传统基于矩阵链式乘法的算法(如PCRW和HeteSim)在时间效率与内存消耗上的问题。本文还给出了随机游走样本数取值的理论证明,并通过实验证明了仅使用一小部分采样样本足以保证相似度排名的准确率,同时给出了相似度误差设置的经验公式。主流的基于路径特征的关系推理方法是路径排序算法(Path Ranking Algorithm,PRA)。它通过两步算法来完成链接预测任务,第一步是用图上的遍历算法来找到所有的元路径作为特征,第二步是通过元路径受限的随机游走算法训练一个关系分类模型。本文在RSSim的基础上提出了一个新颖的关系推理方法——子图路径抽取算法。它将PRA算法的特征选择和特征计算两步在逻辑上进行综合,用实体子图搜索与合并的方式构造特征,大大节省了计算过程的时间开销。为了满足大规模知识图谱下的关系推理需求,本文还提出了子图路径抽取的分布式计算方法。该分布式算法包括两步:分布式子图路径特征计算与分布式多模型训练。并行的算法解决了单机训练各个模型的低效率问题,在分布式系统下,按照关系划分的多个模型将同时训练,极大提高了效率。