论文标题
对亚图同构的深入分析
Deep Analysis on Subgraph Isomorphism
论文作者
论文摘要
子图同构是一个众所周知的NP硬性问题，在许多应用中广泛使用，例如社交网络分析和知识图查询。它的性能通常受到固有的硬度的限制。自2012年以来，已经完成了几项有见地的工作，主要优化修剪规则和匹配订单，以加速枚举所有同构子图。然而，他们的正确性和表现尚未得到很好的研究。首先，在具有不同的汇编标志的实现中使用了不同的语言。其次，在同一平台和相同数据集上未完成实验。第三，一些不同作品的想法甚至是互补的。最后但并非最不重要的一点是，应用一些算法存在错误。在本文中，我们通过重新实现七个代表性的同构算法及其改进版本，并在各种图上进行全面实验来解决这些问题。结果显示了最先进的解决方案的优缺点，并探讨了新的优化方法。
Subgraph isomorphism is a well-known NP-hard problem which is widely used in many applications, such as social network analysis and knowledge graph query. Its performance is often limited by the inherent hardness. Several insightful works have been done since 2012, mainly optimizing pruning rules and matching orders to accelerate enumerating all isomorphic subgraphs. Nevertheless, their correctness and performance are not well studied. First, different languages are used in implementation with different compilation flags. Second, experiments are not done on the same platform and the same datasets. Third, some ideas of different works are even complementary. Last but not least, there exist errors when applying some algorithms. In this paper, we address these problems by re-implementing seven representative subgraph isomorphism algorithms as well as their improved versions, and conducting comprehensive experiments on various graphs. The results show pros and cons of state-of-the-art solutions and explore new approaches to optimization.
