GraSP: Simple yet Effective Graph Similarity Predictions

Graph similarity computation (GSC) is to calculate the similarity between one\npair of graphs, which is a fundamental problem with fruitful applications in\nthe graph community. In GSC, graph edit distance (GED) and maximum common\nsubgraph (MCS) are two important similarity metrics, both of which are NP-hard\nto compute. Instead of calculating the exact values, recent solutions resort to\nleveraging graph neural networks (GNNs) to learn data-driven models for the\nestimation of GED and MCS. Most of them are built on components involving\nnode-level interactions crossing graphs, which engender vast computation\noverhead but are of little avail in effectiveness. In the paper, we present\nGraSP, a simple yet effective GSC approach for GED and MCS prediction. GraSP\nachieves high result efficacy through several key instruments: enhanced node\nfeatures via positional encoding and a GNN model augmented by a gating\nmechanism, residual connections, as well as multi-scale pooling. Theoretically,\nGraSP can surpass the 1-WL test, indicating its high expressiveness.\nEmpirically, extensive experiments comparing GraSP against 10 competitors on\nmultiple widely adopted benchmark datasets showcase the superiority of GraSP\nover prior arts in terms of both effectiveness and efficiency. The code is\navailable at https://github.com/HaoranZ99/GraSP.\n

Paper

Similar papers

© 2026 NYSGPT2525 LLC