A graph similarity measurement algorithm combining global and local fine-grained features

Abstract

Graph Similarity Computation (GSC) is not only a basic operation of graph similarity search, but also plays an important role in many application fields, including drug design, program analysis and social group identification. Since calculating the exact distance or similarity between two graphs is usually an NP-hard problem, the tradeoff between precision and speed needs to be addressed. In this paper, a pooling-based graph neural network method is proposed, which effectively integrates the coarse-grained interaction features of the two graph data and the fine -grained interaction features of the nodes between the subgraphs, and further reduce the computational cost while ensuring the accuracy. The experimental results show that the proposed method has good performance on real graph data sets. Compared with previous methods, the proposed method not only improves the accuracy but also improves the computational efficiency.