提出新模型NC-Iso,提升子图匹配的精度与排序能力。
Hierarchy-Aware Neural Subgraph Matching with Enhanced Similarity Measure
- 通过构建节点根子树的层级依赖关系,保持特征相对位置一致性。
- 在九个数据集上实现高精度匹配,且响应时间高效。
- 适合需要精确排序的子图检索场景,如知识图谱应用。
子图匹配因需耗时的组合搜索而具挑战性。基于图神经网络(GNN)的方法通过编码器提取图信息,并利用铰链距离度量保证嵌入空间中的包含约束,显著缩短响应时间,成为有前景的子图检索方案。然而,这些方法在编码过程中忽视了节点根子树中特征的相对位置,仅关注特征数量,导致尺度差异干扰包含约束,引发误判;同时其铰链距离度量对匹配图对的区分能力不足,制约排名性能。本文提出NC-Iso,一种新型GNN架构用于神经子图匹配。NC-Iso通过建立节点根子树内相邻层级间的层级依赖,保留特征的相对位置,确保匹配图对在特征数量和层级结构上均满足一致性和包含约束。为增强匹配对的排序能力,引入新颖的相似性主导比增强度量,量化图对间相似性相对于差异性的主导程度。在九个数据集上的实验验证了NC-Iso的有效性、泛化性、可扩展性与迁移能力,同时保持时间效率,提供更具区分性的神经子图匹配解决方案。代码开源于https://github.com/liuzhouyang/NC-Iso。
原文摘要 · Abstract (English)
Subgraph matching is challenging as it necessitates time-consuming combinatorial searches. Recent Graph Neural Network (GNN)-based approaches address this issue by employing GNN encoders to extract graph information and hinge distance measures to ensure containment constraints in the embedding space. These methods significantly shorten the response time, making them promising solutions for subgraph retrieval. However, they suffer from scale differences between graph pairs during encoding, as they focus on feature counts but overlook the relative positions of features within node-rooted subtrees, leading to disturbed containment constraints and false predictions. Additionally, their hinge distance measures lack discriminative power for matched graph pairs, hindering ranking applications. We propose NC-Iso, a novel GNN architecture for neural subgraph matching. NC-Iso preserves the relative positions of features by building the hierarchical dependencies between adjacent echelons within node-rooted subtrees, ensuring matched graph pairs maintain consistent hierarchies while complying with containment constraints in feature counts. To enhance the ranking ability for matched pairs, we introduce a novel similarity dominance ratio-enhanced measure, which quantifies the dominance of similarity over dissimilarity between graph pairs. Empirical results on nine datasets validate the effectiveness, generalization ability, scalability, and transferability of NC-Iso while maintaining time efficiency, offering a more discriminative neural subgraph matching solution for subgraph retrieval. Code available at https://github.com/liuzhouyang/NC-Iso.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。