用神经网络提升图匹配效率，速度比传统方法快100倍以上
Improving Subgraph Matching by Combining Algorithms and Graph Neural Networks
- 融合传统算法与图神经网络，构建首个基于GNN的同态匹配框架
- 在真实与合成数据上平均准确率达0.962，速度比精确算法快101.91倍
- 可区分更多不满足同态关系的图对，适合图推理与知识图谱应用
同态是保持图结构的关键映射技术。给定一个图和一个模式，子图同态问题旨在寻找从模式到图的映射，确保模式中相邻顶点映射到图中相邻顶点。与要求一一对应的子图同构不同，同态允许模式中多个顶点映射到图中同一顶点，因此更复杂。我们提出HFrame，首个基于图神经网络的子图同态框架，融合传统算法与机器学习技术。实验表明，HFrame相比标准GNN能更好区分模式不嵌入图的情况，并提供通用化误差界。在真实世界与合成图上的实验显示，其速度最高达精确匹配算法的101.91倍，平均准确率为0.962。
原文摘要 · Abstract (English)
Homomorphism is a key mapping technique between graphs that preserves their structure. Given a graph and a pattern, the subgraph homomorphism problem involves finding a mapping from the pattern to the graph, ensuring that adjacent vertices in the pattern are mapped to adjacent vertices in the graph. Unlike subgraph isomorphism, which requires a one-to-one mapping, homomorphism allows multiple vertices in the pattern to map to the same vertex in the graph, making it more complex. We propose HFrame, the first graph neural network-based framework for subgraph homomorphism, which integrates traditional algorithms with machine learning techniques. We demonstrate that HFrame outperforms standard graph neural networks by being able to distinguish more graph pairs where the pattern is not homomorphic to the graph. Additionally, we provide a generalization error bound for HFrame. Through experiments on both real-world and synthetic graphs, we show that HFrame is up to 101.91 times faster than exact matching algorithms and achieves an average accuracy of 0.962.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。