元子图(M)被定义为由异构信息网络(HIN)架构中一组连接的边类型构成的边展开子图，它是经典元路径的推广。尽管先前的研究利用了在架构上定义的特殊形状实例用于诸如凝聚子图发现、相似性测量和推荐等任务，但尚无现有工作正式定义M -实例搜索问题并开发专门的高效算法。在本文中，我们首先对M查询进行推广，然后系统地探索专门针对M实例搜索的高效算法。对于给定的查询M，顶点/边对应关系由架构固定。因此，我们不搜索嵌入；相反，我们直接检索相应的实例子图。这避免了生成嵌入排列，尽管决策版本仍然是NP完全的。我们提出了从回溯和退化排序策略中适应而来的两个基线算法，仅适用于小型HIN。然后，我们推导出M实例数量的新上界，即| Ans | * edge，这是AGM界限的一种特化，利用了M中的边类型邻接和类型边列表。在该界限的指导下，我们通过有效的剪枝增强回溯，达到复杂度O * (| Ans | * edge)。将此分析扩展和推广到M邻接的子图和M子图的实例 yields | Ans | * bag。通过充分考虑以下方面的权衡：1)导出最佳子查询的成本，2)估计子查询实例数量的准确性和成本，以及3)实现子查询实例的成本，我们建议利用M的星形子图来搜索M实例，运行在O * (| Ans | * star )并由于基于交叉星的剪枝而在实践中更快。对大型真实HIN的实验表明，我们的最佳算法运行速度比基线和直接基于AGM的方法快两个数量级。
Chen等人（Mon，）研究了这个问题。