A Graph Similarity Algorithm Based on Graph Partitioning and Attention Mechanism

In recent years, graph similarity algorithms have been extensively developed based on neural networks. However, with an increase in the node count in graphs, these models either suffer from a reduced representation ability or face a significant increase in the computational cost. To address this issue, a graph similarity algorithm based on graph partitioning and attention mechanisms was proposed in this study. Our method first divided each input graph into the subgraphs to directly extract the local structural features. The residual graph convolution and multihead self-attention mechanisms were employed to generate node embeddings for each subgraph, extract the feature information from the nodes, and regenerate the subgraph embeddings using varying attention weights. Initially, rough cosine similarity calculations were performed on all subgraph pairs from the two sets of subgraphs, with highly similar pairs selected for precise similarity computation. These results were then integrated into the similarity score for the input graph. The experimental results indicated that the proposed learning algorithm outperformed the traditional algorithms and similar computing models in terms of graph similarity computation performance.