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.


翻译:子系形态是一个众所周知的NP-硬问题,在许多应用程序中广泛使用,如社交网络分析和知识图形查询,其性能往往受到内在硬性的限制。自2012年以来,已经做了一些颇有见地的工作,主要是优化裁剪规则和匹配顺序,以加速罗列所有等形态子图。然而,没有很好地研究它们的正确性和性能。首先,不同语言用于不同的编译旗帜。第二,不同语言的运用在同一个平台和相同的数据集中并不使用。第三,不同作品的一些想法甚至互为补充。最后但并非最不重要的一点是,在应用某些算法时存在错误。在本文件中,我们通过重新实施七个具有代表性的子系形态算法及其改进版本来解决这些问题,并在各种图表上进行全面实验。结果显示了最新解决方案的利弊,并探索了新的优化方法。

0
下载
关闭预览

相关内容

【斯坦福2021新书】决策算法,694页pdf阐述不确定性决策
专知会员服务
222+阅读 · 2021年1月27日
【NeurIPS2020-MIT】子图神经网络,Subgraph Neural Networks
专知会员服务
45+阅读 · 2020年9月28日
专知会员服务
123+阅读 · 2020年9月8日
商业数据分析,39页ppt
专知会员服务
157+阅读 · 2020年6月2日
机器学习入门的经验与建议
专知会员服务
89+阅读 · 2019年10月10日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
RoBERTa中文预训练模型:RoBERTa for Chinese
PaperWeekly
57+阅读 · 2019年9月16日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
笔记 | Sentiment Analysis
黑龙江大学自然语言处理实验室
10+阅读 · 2018年5月6日
Python机器学习教程资料/代码
机器学习研究会
8+阅读 · 2018年2月22日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
【推荐】GAN架构入门综述(资源汇总)
机器学习研究会
10+阅读 · 2017年9月3日
Arxiv
0+阅读 · 2021年2月16日
Arxiv
0+阅读 · 2021年2月16日
Arxiv
8+阅读 · 2020年10月12日
Arxiv
27+阅读 · 2020年6月19日
Graph Analysis and Graph Pooling in the Spatial Domain
Arxiv
23+阅读 · 2018年10月1日
VIP会员
相关VIP内容
相关资讯
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
RoBERTa中文预训练模型:RoBERTa for Chinese
PaperWeekly
57+阅读 · 2019年9月16日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
笔记 | Sentiment Analysis
黑龙江大学自然语言处理实验室
10+阅读 · 2018年5月6日
Python机器学习教程资料/代码
机器学习研究会
8+阅读 · 2018年2月22日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
【推荐】GAN架构入门综述(资源汇总)
机器学习研究会
10+阅读 · 2017年9月3日
相关论文
Arxiv
0+阅读 · 2021年2月16日
Arxiv
0+阅读 · 2021年2月16日
Arxiv
8+阅读 · 2020年10月12日
Arxiv
27+阅读 · 2020年6月19日
Graph Analysis and Graph Pooling in the Spatial Domain
Arxiv
23+阅读 · 2018年10月1日
Top
微信扫码咨询专知VIP会员