SSGTN: A Graph Similarity Calculation Method Combining Subgraph and Global Features
Main Article Content
Keywords
graph neural network, graph similarity calculation, graph embedding, graph editing distance, maximum common subgraph
Abstract
Graph similarity computation is one of the fundamental challenges in graph data mining, with critical applications in chemical molecule analysis and social network analysis. Traditional methods, such as graph edit distance and maximum common subgraph, are NP-hard and computationally expensive. Although neural network-based approaches have improved efficiency and accuracy, existing methods still exhibit limitations: they often focus excessively on global features while neglecting local substructures, or vice versa, and fail to evaluate the relative importance of node-level, subgraph level, and global features. To address these issues, this paper proposes Similarity Subgraph Global Tensor Network(SSGTN), a novel graph similarity computation framework that integrates subgraph and global features. Specifically, SSGTN employs graph convolutional networks to extract subgraph features and graph attention mechanisms to capture global representations. A Subgraph Global Tensor Network is then designed to dynamically fuse pooled subgraph features with global features, thereby jointly optimizing local and global characterizations. Finally, all features are aggregated to generate the graph similarity score. Experiments on real-world datasets demonstrate that SSGTN outperforms baseline models across three evaluation metrics, confirming its efficiency and accuracy.
References
- An, L., Wu, A., Yuan, Y., SUN, S. Q. and WANG, G. R., (2023). Graph similarity computation method based on meta-structures matching and biased sampling. Chinese Journal of Computers, vol. 46, no. 7, pp. 1513-1531.
- Bai, Y., Ding, H., Bian, S., Chen, T., Sun, Y. and Wang, W., (2019). Published. Simgnn: A neural network approach to fast graph similarity computation. Proceedings of the twelfth ACM international conference on web search and data mining, Melbourne, VIC. ACM, pp. 384-392.
- Bai, Y., Ding, H., Gu, K., Sun, Y. and Wang, W., (2020). Published. Learning-based efficient graph similarity computation via multi-scale convolutional set matching. Proceedings of the AAAI conference on artificial intelligence, New York, NY. AAAI, pp. 3219-3226.
- Berahmand, K., Saberi-Movahed, F., Sheikhpour, R., Li, Y. and Jalili, M., (2025). A comprehensive survey on spectral clustering with graph structure learning. arXiv preprint arXiv:2501.13597.
- Berretti, S., Del Bimbo, A. and Vicario, E., (2001). Efficient matching and indexing of graph models in content-based retrieval. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 23, no. 10, pp. 1089-1105.
- Blumenthal, D. B. and Gamper, J., (2020). On the exact computation of the graph edit distance. Pattern Recognition Letters, vol. 134, pp. 46-57.
- Bunke, H., (1997). On a relation between graph edit distance and maximum common subgraph. Pattern recognition letters, vol. 18, no. 8, pp. 689-694.
- Bunke, H. and Shearer, K., (1998). A graph distance metric based on the maximal common subgraph. Pattern recognition letters, vol. 19, no. 3-4, pp. 255-259.
- Bunke., H., (1983). What is the distance between graphs. Bulletin of the EATCS 20, vol. 20, no. 1983, pp. 35-39.
- Kipf, T., (2016). Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907.
- Koutra, D., Vogelstein, J. T. and Faloutsos, C., (2013). Published. Deltacon: A principled massive-graph similarity function. Proceedings of the 2013 SIAM international conference on data mining, Austin, Texas. SIAM, pp. 162-170.
- Ktena, S. I., Parisot, S., Ferrante, E., Rajchl, M., Lee, M., Glocker, B. and Rueckert, D., (2017). Published. Distance Metric Learning Using Graph Convolutional Networks: Application to Functional Brain Networks. Medical Image Computing and Computer Assisted Intervention − MICCAI 2017, Cham. Springer International Publishing, pp. 469-477.
- Li, Y., Gu, C., Dullien, T., Vinyals, O. and Kohli, P., (2019). Published. Graph matching networks for learning the similarity of graph structured objects. International conference on machine learning, Long Beach. PMLR, pp. 3835-3845.
- Ling, X., Wu, L., Wang, S., Ma, T., Xu, F., Liu, A. X., Wu, C. and Ji, S., (2021). Multilevel graph matching networks for deep graph similarity learning. IEEE Transactions on Neural Networks and Learning Systems, vol. 34, no. 2, pp. 799-813.
- Liu, J., Ma, G., Jiang, F., Lu, C. T., Yu, P. S. and Ragin, A. B., (2019). Published. Community-preserving Graph Convolutions for Structural and Functional Joint Embedding of Brain Networks. 2019 IEEE International Conference on Big Data (Big Data), Los Angeles, CA. IEEE, pp. 1163-1168.
- Ma, G., Ahmed, N. K. and Willke, T. L., (2021). Deep graph similarity learning: A survey. Data Mining and Knowledge Discovery, vol. 35, no. 3, pp. 688-725.
- Noble, C. C. and Cook, D. J., (2003). Published. Graph-based anomaly detection. Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, Washington, DC. ACM, pp. 631-636.
- Riba, P., Fischer, A., Lladós, J. and Fornés, A., (2018). Published. Learning graph distances with message passing neural networks. 2018 24th International Conference on Pattern Recognition (ICPR), Beijing, China. IEEE, pp. 2239-2244.
- Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P. and Bengio, Y., (2018). Published. Graph Attention Networks. International Conference on Learning Representations, Vancouver, Canada. ICLR, pp. 1-12.
- Wang, L., Zheng, Y., Jin, D., Li, F., Qiao, Y. and Pan, S., (2024). Contrastive graph similarity networks. ACM Transactions on the Web, vol. 18, no. 2, pp. 1-20.
- Xiu, H., Yan, X., Wang, X., Cheng, J. and Cao, L., (2020). Hierarchical graph matching network for graph similarity computation. arXiv preprint arXiv:2006.16551.
- Zeng, Z., Tung, A. K., Wang, J., Feng, J. and Zhou, L., (2009). Comparing stars: On approximating graph edit distance. Proceedings of the VLDB Endowment, vol. 2, no. 1, pp. 25-36.
- Zhang, Z., Bu, J., Ester, M., Li, Z., Yao, C., Yu, Z. and Wang, C., (2021). Published. H2mn: Graph similarity learning with hierarchical hypergraph matching networks. Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining, Virtual. ACM, pp. 2274-2284.
- Zhuo, W. and Tan, G., (2022). Efficient graph similarity computation with alignment regularization. Advances in Neural Information Processing Systems, vol. 35, pp. 30181-30193.
Article Sidebar
This work is licensed under a Creative Commons Attribution 4.0 International License.