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

doi:10.13229/j.cnki.jdxbgxb.20231143

摘要/Abstract

摘要：

由于计算两个图之间的精确相似度通常属于非确定性多项式时间难解（NP-hard）问题，因此需要解决精度和速度的权衡问题，本文提出了一种基于池化的图神经网络方法，有效地融合了图数据的全局粗粒度交互特征以及子图间节点的细粒度交互特征，在保证精度的前提下进一步降低了计算量。实验结果表明，本文方法在真实图数据集上表现出良好的性能，相较于现有方法，既提高了准确性，又提升了计算效率。

关键词: 计算机应用技术, 图神经网络, 图相似度计算, 图池化, 图编辑距离

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

中图分类号:

TP391.4

车翔玖,李良. 融合全局与局部细粒度特征的图相似度度量算法[J]. 吉林大学学报(工学版), 2025, 55(7): 2365-2371.

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.

图/表 6

图1

图2

表1

表2

表3

图3

参考文献 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.

相关文章 15

[1]	柴树山,周志强,李海涛,徐炅旸. 基于图时空模式学习网络的路网实时交通事件自动检测方法[J]. 吉林大学学报(工学版), 2025, 55(7): 2145-2161.
[2]	周丰丰,郭喆,范雨思. 面向不平衡多组学癌症数据的特征表征算法[J]. 吉林大学学报(工学版), 2025, 55(6): 2089-2096.
[3]	王健,贾晨威. 面向智能网联车辆的轨迹预测模型[J]. 吉林大学学报(工学版), 2025, 55(6): 1963-1972.
[4]	车翔玖,孙雨鹏. 基于相似度随机游走聚合的图节点分类算法[J]. 吉林大学学报(工学版), 2025, 55(6): 2069-2075.
[5]	蔡晓东,周青松,张言言,雪韵. 基于动静态和关系特征全局捕获的社交推荐模型[J]. 吉林大学学报(工学版), 2025, 55(2): 700-708.
[6]	车翔玖,武宇宁,刘全乐. 基于因果特征学习的有权同构图分类算法[J]. 吉林大学学报(工学版), 2025, 55(2): 681-686.
[7]	张玺君,余光杰,崔勇,尚继洋. 基于聚类算法和图神经网络的短时交通流预测[J]. 吉林大学学报(工学版), 2024, 54(6): 1593-1600.
[8]	梁礼明,周珑颂,尹江,盛校棋. 融合多尺度Transformer的皮肤病变分割算法[J]. 吉林大学学报(工学版), 2024, 54(4): 1086-1098.
[9]	拉巴顿珠,扎西多吉,珠杰. 藏语文本标准化方法[J]. 吉林大学学报(工学版), 2024, 54(12): 3577-3588.
[10]	叶育鑫,夏珞珈,孙铭会. 增强现实环境中基于假想键盘的手势输入方法[J]. 吉林大学学报(工学版), 2024, 54(11): 3274-3282.
[11]	车娜,朱奕明,赵剑,孙磊,史丽娟,曾现伟. 基于联结主义的视听语音识别方法[J]. 吉林大学学报(工学版), 2024, 54(10): 2984-2993.
[12]	薛珊,张亚亮,吕琼莹,曹国华. 复杂背景下的反无人机系统目标检测算法[J]. 吉林大学学报(工学版), 2023, 53(3): 891-901.
[13]	时小虎,吴佳琦,吴春国,程石,翁小辉,常志勇. 基于残差网络的弯道增强车道线检测方法[J]. 吉林大学学报(工学版), 2023, 53(2): 584-592.
[14]	王振,杨宵晗,吴楠楠,李国坤,冯创. 基于生成对抗网络的序列交叉熵哈希[J]. 吉林大学学报(工学版), 2023, 53(12): 3536-3546.
[15]	周丰丰,颜振炜. 基于混合特征的特征选择神经肽预测模型[J]. 吉林大学学报(工学版), 2023, 53(11): 3238-3245.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

	方法	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