Subgraph Matching on Multi-Attributed Graphs Based on Contrastive Learning

Abstract

Graphs have been widely used in fields ranging from chemical informatics to social network analysis. Graph-related problems become increasingly significant, with subgraph matching standing out as one of the most challenging tasks. The goal of subgraph matching is to find all subgraphs in the data graph that are isomorphic to the query graph. Traditional methods mostly rely on search strategies with high computational complexity and are hard to apply to large-scale real datasets. With the advent of graph neural networks(GNNs), researchers have turned to GNNs to address subgraph matching problems. However, the multi-attributed features on nodes and edges are overlooked during the learning of graphs, which causes inaccurate results in real-world scenarios. To tackle this problem, we propose a novel model called subgraph matching on multiattributed graph network(SGMAN). SGMAN first utilizes improved line graphs to capture node and edge features. Then, SGMAN integrates GNN and contrastive learning(CL) to derive graph representation embeddings and calculate the matching matrix to represent the matching results. We conduct experiments on public datasets, and the results affirm the superior performance of our model.

Keywords

subgraph matching / graph neural network(GNN) / multi-attributed graph / contrastive learning(CL)

References

[1] LAN Z X, YU L M, YUAN L L, et al. Sub-GMN:the subgraph matching network model[EB/OL].(2019-03-15) [2024-09-10]. https://arxiv.org/abs/2104.00186v3.

[2] LAN Z X, MA Y, YU L M, et al. AEDNet:adaptive edge-deleting network for subgraph matching[J]. Pattern Recognition, 2023,133:109033.

[3] LIU X, SONG Y Q. Graph convolutional networks with dual message passing for subgraph isomorphism counting and matching[J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2022, 36(7):7594-7602.

[4] BARNES J A, HARARY F. Graph theory in network analysis[J]. Social Networks, 1983, 5(2):235-244.

[5] XIAO S X, WANG S P, DAI Y F, et al. Graph neural networks in node classification:survey and evaluation[J]. Machine Vision and Applications, 2021, 33(1):4.

[6] HANG M H, CHEN Y X. Link prediction based on graph neural networks[EB/OL].(2018-02-27) [2024-09-10].

[7] PRANNAY K, PIOTR T, CHEN W, et al. Supervised contrastive learning[J]. Advances in Neural Information Processing Systems. 2020,33:18661-18673.

[8] HE K M, FAN H Q, WU Y X, et al. Momentum contrast for unsupervised visual representation learning[C]//2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). New York: IEEE, 2020:9726-9735.

[9] HAFIDI H, GHOGHO M, CIBLAT P, et al. GraphCL:contrastive self-supervised learning of graph representations[EB/OL].(2020-08-25) [2024-09-10].

[10] QIU J Z, CHEN Q B, DONG Y X, et al. GCC:graph contrastive coding for graph neural network pre-training[C]//Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM, 2020:1150-1160.

[11] ULLMANN J R. An algorithm for subgraph isomorphism[J]. Journal of the ACM, 1976, 23(1):31-42.

[12] CORDELLA L P, FOGGIA P, SANSONE C, et al. A (sub)graph isomorphism algorithm for matching large graphs[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(10):1367-1372.

[13] ZOU L, CHEN L, YU J X, et al. A novel spectral coding in a large graph database[C]//Proceedings of the 11th International Conference on Extending Database Technology Advances in Database Technology-EDBT’08. New York: ACM, 2008:181-192.

[14] SHASHA D, WANG J T L, GIUGNO R. Algorithmics and applications of tree and graph searching[C]//Proceedings of the Twenty-First ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. New York: ACM, 2002:39-52.

[15] CHOI D, LEE H, LIM J, et al. Efficient continuous subgraph matching scheme considering data reuse[J]. Knowledge-Based Systems, 2023,282:111120.

[16] LIU L H, DU B X, XU J J, et al. G-finder:approximate attributed subgraph matching[C]//2019 IEEE International Conference on Big Data. New York: IEEE, 2019:513-522.

[17] BHATTARAI B, LIU H, HUANG H H. CECI:compact embedding cluster index for scalable subgraph matching[C]//Proceedings of the 2019 International Conference on Management of Data. New York: ACM, 2019:1447-1462.

[18] ARAI J, FUJIWARA Y, ONIZUKA M. GuP:fast subgraph matching by guard-based pruning[J]. Proceedings of the ACM on Management of Data, 2023, 1(2):1-26.

[19] MA Y X, XU B M, YIN H F. Tps:a new way to find good vertex-search order for exact subgraph matching[J]. Multimedia Tools and Applications, 2024, 83(27):69875-69896.

[20] HE J Z, CHEN Y X, LIU Z Y, et al. Optimizing subgraph retrieval and matching with an efficient indexing scheme[J]. Knowledge and Information Systems, 2024, 66(11):6815-6843.

[21] YANG F, ZHANG H Y, TAO S M. Semi-supervised classification via full-graph attention neural networks[J]. Neurocomputing, 2022,476:63-74.

[22] SOCHER R, CHEN D Q, MANNING C D, et al. Reasoning with neural tensor networks for knowledge base completion[J]. Advances in Neural Information Processing Systems, 2013,12:926-934.

[23] YING R, LOU Z Y, YOU J X, et al. Neural subgraph matching[EB/OL].(2020-07-06) [2024-09-10]. https://arxiv.org/abs/2007.03092.

[24] CEN Y K, ZOU X, ZHANG J W, et al. Representation learning for attributed multiplex heterogeneous network[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM, 2019:1358-1368.

[25] SCHLICHTKRULL M, KIPF T N, BLOEM P, et al. Modeling relational data with graph convolutional networks[M]//Lecture Notes in Computer Science. Cham: Springer International Publishing, 2018:593-607.

[26] VASHISHTH S, SANYAL S, NITIN V, et al. Composition-based multi-relational graph convolutional networks[EB/OL].(2019-11-08)[2024-09-10].

[27] CAO J H, FANG J Y, MENG Z Q, et al. Knowledge graph embedding:a survey from the perspective of representation spaces[J]. ACM Computing Surveys, 2024, 56(6):1-42.

[28] CARLETTI V, FOGGIA P, SAGGESE A, et al. Introducing VF3:a new algorithm for subgraph isomorphism[C]//International Workshop on Graph-Based Representations in Pattern Recognition. Cham: Springer, 2017:128-139.

[29] TAUD H, MAS J F. Multilayer perceptron (MLP)[M]// Geomatic Approaches for Modeling Land Change Scenarios. Cham: Springer, 2018:451-455.

[30] OKU H, ISHIKAWA M. High-speed liquid lens with 2 ms response and 80.3 nm root-mean-square wavefront error[J]. Applied Physics Letters, 2009, 94(22):221108.

[31] LOSHCHILOV I, HUTTER F. Decoupled weight decay regularization[EB/OL].(2019-01-04) [2024-09-11].https://doi.org/10.48550/arxiv.1711.05101.