融合全局与局部细粒度特征的图相似度度量算法

doi:10.13229/j.cnki.jdxbgxb.20231143

Abstract

Abstract:

Since calculating the exact 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 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 existing methods， the proposed method not only improves the accuracy but also improves the computational efficiency.

Key words: computer application technology, graph neural network, graph similarity computation, graph pooling, graph edit distance

CLC Number:

TP391.4

Xiang-jiu CHE,Liang LI. Graph similarity measurement algorithm combining global and local fine-grained features[J].Journal of Jilin University(Engineering and Technology Edition), 2025, 55(7): 2365-2371.

Figures/Tables 6

Fig.1

Fig.2

Table 1

Table 2

Table 3

Fig.3

References 28

[1]	徐冰冰, 岑科廷, 黄俊杰, 等. 图卷积神经网络综述[J].计算机学报, 2020, 43(5): 755-780.
	Xu Bing-bing, Cen Ke-ting, Huang Jun-jie, et al. A survey on graph convolutional neutral network[J]. Chinese Journal of Computers, 2020, 43(5): 755-780.
[2]	刘俊奇, 涂文轩, 祝恩. 图卷积神经网络综述[J].计算机工程与科学, 2023, 45(8): 1472-1481.
	Liu Jun-qi, Tu Wen-xuan, Zhu En. Survey on graph convolutional neutral network[J]. Computer Engineering & Science, 2023, 45(8): 1472-1481.
[3]	Kipf T N, Welling M. Semi-supervised classification with graph convolutional networks[J/OL].[2016-02-16]. .
[4]	Hamilton W, Ying Z, Leskovec J. Inductive representation learning on large graphs[J]. Advances in Neural Information Processing Systems, 2017, 30: 1024-1034.
[5]	Veličković P, Cucurull G, Casanova A, et al. Graph attention networks[[J/OL].[2017-06-16]. .
[6]	Brody S, Alon U, Yahav E. How attentive are graph attention networks?[J/OL].[2021-06-26]. .
[7]	Ying Z, You J, Morris C, et al. Hierarchical graph representation learning with differentiable pooling[J]. Advances in Neural Information Processing Systems, 2018, 31: 4800-4810.
[8]	Gao H Y, Ji S W. Graph U-nets[C]∥Proceedings of the 36th International Conference on Machine Learning. New York: Curran Associates, Inc., International Machine Learning Society, 2019: 2083-2092.
[9]	Lee J, Lee I, Kang J. Self-attention graph pooling[C]∥Proceedings of the 36th International Conference on Machine Learning. New York: Curran Associates, Inc., International Machine Learning Society, 2019: 3734-3743.
[10]	Luo Y, McThrow M, Au W Y, et al. Automated data augmentations for graph classification[J/OL].[2022-08-11]. .
[11]	Bai Y, Ding H, Bian S, et al. SimGNN: A neural network approach to fast graph similarity computation[C]∥Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining. Yew York: ACM, 2019: 384-392.
[12]	Bai Y, Ding H, Gu K, et al. Learning-based efficient graph similarity computation via multi-scale convolutional set matching[J]. AAAI, 2020, 34(4): 3219-3226.
[13]	Krizhevsky A, Sutskever I, Hinton G E. Imagenet classification with deep convolutional neural networks[J]. Advances in Neural Information Processing Systems, 2012, 25: 1106-1114.
[14]	Ling X, Wu L, Wang S,et al.Multilevel graph matching networks for deep graph similarity learning[J]. IEEE Transactions on Neural Networks and Learning Systems, 2023, 34: 799-813.
[15]	Qin C, Zhao H, Wang L, et al. Slow learning and fast inference: Efficient graph similarity computation via knowledge distillation[J]. Advances in Neural Information Processing Systems, 2021, 34: 14110-14121.
[16]	Ranjan R, Grover S, Medya S, et al. GREED: a neural framework for learning graph distance functions[J]. Advances in Neural Information Processing Systems, 2022, 35: 22518-22530.
[17]	Zhuo W, Tan G. Efficient graph similarity computation with alignment regularization[J]. Advances in Neural Information Processing Systems, 2022, 35: 30181-30193.
[18]	Qureshi R J, Ramel J Y, Cardot H. Graph based shapes representation and recognition[C]∥Graph-Based Representations in Pattern Recognition: 6th IAPR-TC-15 International Workshop. Berlin: Springer, 2007: 49-60.
[19]	Bromley J, Guyon I, LeCun Y, et al. Signature verification using a "siamese" time delay neural network[J]. Advances in Neural Information Processing Systems, 1993, 6: 737-744.
[20]	Socher R, Chen D, Manning C D, et al. Reasoning with neural tensor networks for knowledge base completion[J]. Advances in Neural Information Processing Systems, 2013, 26: 926-934.
[21]	Wang X, Ding X, Tung A K H, et al. An efficient graph indexing method[C]∥Proceedings of the 28th IEEE International Conference on Data Engineering, Piscataway, USA, 2012: 210-221.
[22]	Yanardag P, Vishwanathan S V N. Deep graph kernels[C]∥Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York,USA, 2015: 1365-1374.
[23]	Neuhaus M, Riesen K, Bunke H. Fast suboptimal algorithms for the computation of graph edit distance[C]∥Structural, Syntactic, and Statistical Pattern Recognition, Berlin,Germany, 2006: 163-172.
[24]	Kuhn H W. The Hungarian method for the assignment problem[J]. Naval Research Logistics Quarterly, 1955, 2(1/2): 83-97.
[25]	Riesen K, Bunke H. Approximate graph edit distance computation by means of bipartite graph matching[J]. Image and Vision Computing, 2009, 27(7): 950-959.
[26]	Fankhauser S, Riesen K, Bunke H. Speeding up graph edit distance computation through fast bipartite matching[C]∥Graph-Based Representations in Pattern Recognition: The 8th IAPR-TC-15 International Workshop, Berlin,Germany, 2011: 102-111.
[27]	Jonker R, Volgenant T. A shortest augmenting path algorithm for dense and sparse linear assignment problems[J]. Computing, 1987, 38(4): 325-340.
[28]	Defferrard M, Bresson X, Vandergheynst P. Convolutional neural networks on graphs with fast localized spectral filtering[J]. Advances in Neural Information Processing Systems, 2016, 29: 3844-3852.

Related Articles 15

[1]	Shu-shan CHAI,Zhi-qiang ZHOU,Hai-tao LI,Jiong-yang XU. Real-time road network traffic anomaly incident detection based on graph spatial-temporal pattern learning network [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(7): 2145-2161.
[2]	Feng-feng ZHOU,Zhe GUO,Yu-si FAN. Feature representation algorithm for imbalanced classification of multi⁃omics cancer data [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(6): 2089-2096.
[3]	Jian WANG,Chen-wei JIA. Trajectory prediction model for intelligent connected vehicle [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(6): 1963-1972.
[4]	Xiang-jiu CHE,Yu-peng SUN. Graph node classification algorithm based on similarity random walk aggregation [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(6): 2069-2075.
[5]	Xiao-dong CAI,Qing-song ZHOU,Yan-yan ZHANG,Yun XUE. Social recommendation based on global capture of dynamic， static and relational features [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(2): 700-708.
[6]	Xiang-jiu CHE,Yu-ning WU,Quan-le LIU. A weighted isomorphic graph classification algorithm based on causal feature learning [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(2): 681-686.
[7]	Xi-jun ZHANG,Guang-jie YU,Yong CUI,Ji-yang SHANG. Short-term traffic flow prediction based on clustering algorithm and graph neural network [J]. Journal of Jilin University(Engineering and Technology Edition), 2024, 54(6): 1593-1600.
[8]	Li-ming LIANG,Long-song ZHOU,Jiang YIN,Xiao-qi SHENG. Fusion multi-scale Transformer skin lesion segmentation algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2024, 54(4): 1086-1098.
[9]	Dondrub LHAKPA,Duoji ZHAXI,Jie ZHU. Tibetan text normalization method [J]. Journal of Jilin University(Engineering and Technology Edition), 2024, 54(12): 3577-3588.
[10]	Yu-xin YE,Luo-jia XIA,Ming-hui SUN. Gesture input method based on transparent keyboard in augmented reality environment [J]. Journal of Jilin University(Engineering and Technology Edition), 2024, 54(11): 3274-3282.
[11]	Na CHE,Yi-ming ZHU,Jian ZHAO,Lei SUN,Li-juan SHI,Xian-wei ZENG. Connectionism based audio-visual speech recognition method [J]. Journal of Jilin University(Engineering and Technology Edition), 2024, 54(10): 2984-2993.
[12]	Ya-hui ZHAO,Fei-yu LI,Rong-yi CUI,Guo-zhe JIN,Zhen-guo ZHANG,De LI,Xiao-feng JIN. Korean⁃Chinese translation quality estimation based on cross⁃lingual pretraining model [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(8): 2371-2379.
[13]	Shan XUE,Ya-liang ZHANG,Qiong-ying LYU,Guo-hua CAO. Anti⁃unmanned aerial vehicle system object detection algorithm under complex background [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(3): 891-901.
[14]	Zhen WANG,Xiao-han YANG,Nan-nan WU,Guo-kun LI,Chuang FENG. Ordinal cross entropy Hashing based on generative adversarial network [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(12): 3536-3546.
[15]	Feng-feng ZHOU,Zhen-wei YAN. A model for identifying neuropeptides by feature selection based on hybrid features [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(11): 3238-3245.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

	方法	MSE	ρ	τ	p@10	p@20
快速近似算法	Beam	12.090	0.609	0.463	0.481	0.493
	Hungarian	25.296	0.510	0.378	0.360	0.392
	VJ	29.157	0.517	0.383	0.310	0.345
GNN方法	SimpleMean	3.115	0.633	0.480	0.269	0.279
	HierarchicalMean	3.046	0.681	0.629	0.246	0.340
	HierarchicalMax	3.396	0.655	0.505	0.222	0.295
	AttDegree	3.338	0.628	0.478	0.209	0.279
	AttGlobalContext	1.472	0.813	0.653	0.376	0.473
	AttLearnableGC	1.340	0.825	0.667	0.400	0.488
	SimGNN	1.189	0.843	0.690	0.421	0.514
	PGSC （pool-hist）	2.266	0.859	0.686	0.442	0.521
	PGSC	2.154	0.861	0.689	0.468	0.550

	方法	MSE	ρ	τ	p@10	p@20
快速近似算法	Beam	9.268	0.827	0.714	0.973	0.924
	Hungarian	29.805	0.638	0.517	0.913	0.836
	VJ	63.863	0.581	0.450	0.287	0.251
GNN 方法	SimpleMean	16.950	0.020	0.016	0.432	0.465
	HierarchicalMean	6.431	0.430	0.525	0.750	0.618
	HierarchicalMax	6.575	0.879	0.740	0.551	0.575
	AttDegree	8.064	0.742	0.609	0.427	0.460
	AttGlobalContext	3.125	0.904	0.781	0.874	0.864
	AttLearnableGC	2.055	0.916	0.804	0.903	0.887
	SimGNN	1.509	0.939	0.830	0.942	0.933
	PGSC （pool-hist）	0.678	0.978	0.882	0.950	0.943
	PGSC	0.429	0.981	0.887	0.961	0.945

	方法	MSE	ρ	τ	p@10	p@20
	SimpleMean	3.749	0.774	0.644	0.547	0.588
	HierarchicalMean	5.019	0.456	0.378	0.567	0.553
	HierarchicalMax	6.993	0.455	0.354	0.572	0.570
GNN方法	AttDegree	2.144	0.828	0.695	0.700	0.695
	AttGlobalContext	3.555	0.684	0.553	0.657	0.656
	AttLearnableGC	1.455	0.835	0.700	0.732	0.742
	SimGNN	1.264	0.878	0.770	0.759	0.777
	PGSC （pool-hist）	0.910	0.899	0.779	0.841	0.831
	PGSC	0.736	0.904	0.784	0.839	0.841

Graph similarity measurement algorithm combining global and local fine-grained features

RICH HTML

PDF (PC)