Reinforcement Learning Based Meta _路径

该协会主办的AAAI年会（AAAIon）是国际顶级人工智能学术会议之一。
摘要
元路径以其灵活性和可解释性来捕获对象之间复杂的语义关系，是异构信息网络(HINs)中各种数据挖掘和网络分析任务的重要工具。到目前为止，大多数HIN分析仍然依赖于手工制作元路径，这需要丰富的领域知识，而在复杂、大规模和模式丰富的HIN中很难获得这些知识。在这项工作中，我们提出了一种新的框架，即强化学习元路径发现(MPDRL)，以识别来自复杂和大规模HIN的信息元路径。为了获取对象之间的不同语义信息，我们在强化学习框架中提出了一种新的多跳推理策略，旨在推断出源实体与目标实体之间的下一个有希望的关系。此外，为了提高效率，我们开发了一种嵌入类型上下文表示的方法来扩展RL框架，以处理百万量级的HIN 。由于多跳推理产生丰富的、长度不同的元路径，我们进一步执行元路径归纳步骤，使用最低共同祖先原则总结重要的元路径。在Yago和NELL两个大型HIN上的实验结果验证了我们的方法，并表明我们的算法不仅在链路预测任务中取得了优越的性能，而且还识别了可能被人类专家忽略的有用元路径。
1.介绍
现实世界结构化数据中的复杂交互，如社会网络、生物网络和知识图，可以建模为异构信息网络(HINs) (Sun和Han 2013)，其中对象和边缘被注释为多种类型。由于HIN能够保留对象之间丰富而复杂的相互依赖关系，近年来引起了越来越多的研究关注。然而，HIN的异质性和复杂性也给对象之间的关系分析带来了巨大的挑战，特别是在大规模网络中。为了应对这些限制，元路径的概念被提出来捕获对象之间的语义关系(Sun et al. 2009;2011) 。
图1举例说明了两个对象之间的元路径，巴拉克·奥巴马和美国。为了理解个人和国家之间的关系，我们可以利用以下元路径:a)个人是国家的政治家，b)出生的人是地区的人是国家，c)毕业的人是大学的人是国家的人。虽然它们的长度不同，涉及的中间对象也不同，但这些元路径都有助于推断(, )的语义关系。因此，很容易从图1中推断巴拉克·奥巴马是美国公民。由于元路径承载丰富的语义信息，它们被广泛应用于许多数据挖掘和网络分析任务(Shi et al. 2016)
现有的大多数元路径研究或元路径指导研究都规定预定义可枚举的元路径集，这在很大程度上取决于领域专家，并且是劳动密集型的，因为在hin中寻找有趣的元路径非常具有挑战性。一般来说，这可以被认为是一个搜索问题(Lao and Cohen 2010) 。更具体地说，给定一个类型集T，一个关系集R，一个固定长度l，可能的元路径在大小为
的搜索空间中。如此巨大的空间，随着|T |、|R|、l规模的增大，会导致组合爆炸。大多数现有的基于人类定义元路径的方法只能在模式简单的HIN上可行，例如DBLP 。一旦HIN的模式较大且复杂，就无法预先定义足够的元路径，尤其是较长的元路径，从而导致许多HIN分析任务的性能下降。因此，开发合适的策略来发现有意义的元路径是必要的，这仍然是该领域的一个挑战。
以前的一些研究旨在自动发现元路径。图遍历方法，如宽度优先搜索(BFS) (Kong et al. 2012)，A*算法(Zhu et al. 2018)，已被用于在模式简单HIN中寻找最短路径。但他们很难应对一个复杂的大规模HIN 。孟等人(2015)提出了一种贪心算法FSPG，迭代发现最相关的元路径。然而，FSPG是在一个完全离散的空间中运行的，这使得在HIN中评估和比较相似的物体和关系变得困难。
最近，多跳推理(Shen et al. 2018;Xiong, Hoang, and Wang 2017)，已经成为一种很有前途的方法，用于推断知识图中连接两个对象的路径，也被认为是一种语义丰富的HIN 。这种方法包括对最有希望的关系(边)进行采样，以扩展从源节点到目标节点的路径。然而，该方法有以下局限性:1)它不是端到端推理方法，它严重依赖于预先计算的实体嵌入，通常通过基于平移的嵌入方法(如 ( et al. 2013))学习，因此推理状态可以在连续空间中表示，并用于强化学习(RL)代理。在推理之前采用嵌入学习方法不仅耗时，而且增加了内存消耗，阻碍了它处理百万级HIN的能力。2)这些算法只生成连接两个对象的裸路径，没有对链路预测等下游任务进行元路径归纳(汇总) 。3)这些方法忽略了实体中不同的类型信息，但这是非常重要的，可以为hin中对象之间的关系提供丰富的解释。