论文标题
神经子图匹配
Neural Subgraph Matching
论文作者
论文摘要
子图匹配是确定大目标图中给定查询图的存在和位置的问题。尽管是NP完整的问题，但在网络科学和数据库系统到生物化学和认知科学的领域中，子图匹配问题至关重要。但是，基于组合匹配和整数编程的现有技术无法处理大型目标和查询图的匹配问题。在这里，我们提出了NeuroMatch，这是一种准确，高效且可靠的神经方法，可用于子图匹配。 NeuroMatch将查询图分解为小子图，并使用图形神经网络嵌入它们。经过培训以捕获与子图关系相对应的几何约束，然后神经匹配有效地在嵌入空间中直接执行子图匹配。实验表明，神经匹配比现有组合方法快100倍，比现有近似子图匹配方法高出18％。
Subgraph matching is the problem of determining the presence and location(s) of a given query graph in a large target graph. Despite being an NP-complete problem, the subgraph matching problem is crucial in domains ranging from network science and database systems to biochemistry and cognitive science. However, existing techniques based on combinatorial matching and integer programming cannot handle matching problems with both large target and query graphs. Here we propose NeuroMatch, an accurate, efficient, and robust neural approach to subgraph matching. NeuroMatch decomposes query and target graphs into small subgraphs and embeds them using graph neural networks. Trained to capture geometric constraints corresponding to subgraph relations, NeuroMatch then efficiently performs subgraph matching directly in the embedding space. Experiments demonstrate NeuroMatch is 100x faster than existing combinatorial approaches and 18% more accurate than existing approximate subgraph matching methods.
