用简单有效方法提升图相似度预测准确率和速度
GraSP: Simple yet Effective Graph Similarity Predictions
- 通过位置编码与门控GNN增强节点特征，结合多尺度池化
- 在多个数据集上比10个基线方法更准更快，效率提升显著
- 适合需要高效图相似度计算的研究者与工业应用
图相似度计算（GSC）是图领域基础性问题，广泛应用于图分析。其中图编辑距离（GED）和最大公共子图（MCS）是两个关键指标，但均属于NP难问题。现有方法多依赖跨图的节点级交互，计算开销大且效果提升有限。本文提出GraSP，一种简单而高效的GSC方法，用于预测GED和MCS。GraSP通过位置编码增强节点特征，并结合门控机制、残差连接和多尺度池化，在理论上可超越1-WL测试，具备强表达能力。大量实验表明，在多个主流基准数据集上，相比10种竞争方法，GraSP在准确性和效率上均表现更优。代码已公开于https://github.com/HaoranZ99/GraSP。
原文摘要 · Abstract (English)
Graph similarity computation (GSC) is to calculate the similarity between one pair of graphs, which is a fundamental problem with fruitful applications in the graph community. In GSC, graph edit distance (GED) and maximum common subgraph (MCS) are two important similarity metrics, both of which are NP-hard to compute. Instead of calculating the exact values, recent solutions resort to leveraging graph neural networks (GNNs) to learn data-driven models for the estimation of GED and MCS. Most of them are built on components involving node-level interactions crossing graphs, which engender vast computation overhead but are of little avail in effectiveness. In the paper, we present GraSP, a simple yet effective GSC approach for GED and MCS prediction. GraSP achieves high result efficacy through several key instruments: enhanced node features via positional encoding and a GNN model augmented by a gating mechanism, residual connections, as well as multi-scale pooling. Theoretically, GraSP can surpass the 1-WL test, indicating its high expressiveness. Empirically, extensive experiments comparing GraSP against 10 competitors on multiple widely adopted benchmark datasets showcase the superiority of GraSP over prior arts in terms of both effectiveness and efficiency. The code is available at https://github.com/HaoranZ99/GraSP.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。