Deep graph matching model based on self-attention network

doi:10.11772/j.issn.1001-9081.2022030345

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (4): 1005-1012.DOI: 10.11772/j.issn.1001-9081.2022030345

Special Issue: 人工智能

• Artificial intelligence • Previous Articles Next Articles

Deep graph matching model based on self-attention network

Zhoubo XU, Puqing CHEN(), Huadong LIU, Xin YANG

Guangxi Key Laboratory of Trusted Software （Guilin University of Electronic Technology），Guilin Guangxi 541004，China

Received:2022-03-22 Revised:2022-05-31 Accepted:2022-06-13 Online:2023-04-11 Published:2023-04-10
Contact: Puqing CHEN
About author:XU Zhoubo， born in 1976， Ph. D.， professor. Her research interests include symbolic calculation， intelligent planning， constraint solving.
LIU Huadong， born in 1978， M. S.， lecturer. His research interests include graph data representation.
YANG Xin， born in 1997， M. S. candidate. Her research interests include subgraph isomorphism， graph data mining， symbolic calculation.
Supported by:
National Natural Science Foundation of China(61762027);Natural Science Foundation of Guangxi(2017GXNSFAA198172)

基于自注意力网络的深度图匹配模型

徐周波, 陈浦青(), 刘华东, 杨欣

广西可信软件重点实验室（桂林电子科技大学），广西桂林 541004

通讯作者: 陈浦青
作者简介:徐周波（1976—），女，浙江奉化人，教授，博士，CCF会员，主要研究方向：符号计算、智能规划、约束求解；
刘华东（1978—），男，江西瑞金人，讲师，硕士，主要研究方向：图数据表示；
杨欣（1997—），女，四川资阳人，硕士研究生，主要研究方向：子图同构、图数据挖掘、符号计算。
基金资助:
国家自然科学基金资助项目(61762027);广西自然科学基金资助项目(2017GXNSFAA198172)

Abstract

Abstract:

Node feature representation was learned by Graph Convolutional Network （GCN） by deep graph matching models in the stage of node feature extraction. However， GCN was limited by the learning ability for node feature representation， affecting the distinguishability of node features， which causes poor measurement of node similarity， and leads to the loss of model matching accuracy. To solve the problem， a deep graph matching model based on self-attention network was proposed. In the stage of node feature extraction， a new self-attention network was used to learn node features. The principle of the network is improving the feature description of nodes by utilizing spatial encoder to learn the spatial structures of nodes， and using self-attention mechanism to learn the relations among all the nodes. In addition， in order to reduce the loss of accuracy caused by relaxed graph matching problem， the graph matching problem was modelled to an integer linear programming problem. At the same time， structural matching constraints were added to graph matching problem on the basis of node matching， and an efficient combinatorial optimization solver was introduced to calculate the local optimal solution of graph matching problem. Experimental results show that on PASCAL VOC dataset， compared with Permutation loss and Cross-graph Affinity based Graph Matching （PCA-GM）， the proposed model has the average matching precision on 20 classes of images increased by 14.8 percentage points， on Willow Object dataset， the proposed model has the average matching precision on 5 classes of images improved by 7.3 percentage points， and achieves the best results on object matching tasks such as bicycles and plants.

Key words: deep graph matching, graph matching problem, combinatorial optimization, deep learning, self-attention, integer linear programming

摘要：

现有深度图匹配模型在节点特征提取阶段常利用图卷积网络（GCN）学习节点的特征表示。然而，GCN对节点特征的学习能力有限，影响了节点特征的可区分性，造成节点的相似性度量不佳，最终导致模型的匹配精度受损。为解决这一问题，提出一种基于自注意力网络的深度图匹配模型。所提模型在节点特征提取阶段使用新的自注意力网络来学习节点特征，其原理是通过空间编码器和自注意力机制分别学习节点的空间结构以及所有节点之间的联系，从而改善节点的特征描述。此外，为了减小放松图匹配问题所带来的精度损失，将图匹配问题建模为整数线性规划问题，在图匹配问题的节点匹配基础上增加结构匹配约束，以及引入高效的组合优化求解器来计算图匹配问题的局部最优解。实验结果表明，在PASCALVOC数据集上，与PCA-GM相比，所提模型在20类图像上的匹配精度平均值提高了14.8个百分点；在Willow Object数据集上，所提模型在5类图像上的匹配精度平均值提高了7.3个百分点，并且在自行车、植物等目标匹配任务上达到了最佳的效果。

关键词: 深度图匹配, 图匹配问题, 组合优化, 深度学习, 自注意力, 整数线性规划

CLC Number:

TP391

Zhoubo XU, Puqing CHEN, Huadong LIU, Xin YANG. Deep graph matching model based on self-attention network[J]. Journal of Computer Applications, 2023, 43(4): 1005-1012.

徐周波, 陈浦青, 刘华东, 杨欣. 基于自注意力网络的深度图匹配模型[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1005-1012.

Figures/Tables 10

References 40

1	项英倬，谭菊仙，韩杰思，等. 图匹配技术研究［J］. 计算机科学， 2018， 45（6）：27-31， 45. 10.11896/j.issn.1002-137X.2018.06.004
	XIANG Y Z， TAN J X， HAN J S， et al. Survey of graph matching algorithms［J］. Computer Science， 2018， 45（6）： 27-31， 45. 10.11896/j.issn.1002-137X.2018.06.004
2	严骏驰. 图匹配问题的研究和算法设计［D］. 上海：上海交通大学， 2015： 170.
	YAN J C. Algorithmic studies and design on graph matching［D］. Shanghai： Shanghai Jiao Tong University， 2015： 170.
3	ULLMANN J R. An algorithm for subgraph isomorphism［J］. Journal of the ACM， 1976， 23（1）： 31-42. 10.1145/321921.321925
4	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. 10.1109/tpami.2004.75
5	ABU-AISHEH Z， RAVEAUX R， RAMEL J Y， et al. An exact graph edit distance algorithm for solving pattern recognition problems［C］// Proceedings of the 4th International Conference on Pattern Recognition Applications and Methods - Volume 1. Setúbal： SciTePress， 2015： 271-278. 10.5220/0005209202710278
6	CHEN X Y， HUO H W， HUAN J， et al. An efficient algorithm for graph edit distance computation［J］. Knowledge-Based Systems， 2019， 163： 762-775. 10.1016/j.knosys.2018.10.002
7	GAO X B， XIAO B， TAO D C， et al. A survey of graph edit distance［J］. Pattern Analysis and Applications， 2010， 13（1）： 113-129. 10.1007/s10044-008-0141-y
8	LEROUGE J， ABU-AISHEH Z， RAVEAUX R， et al. New binary linear programming formulation to compute the graph edit distance［J］. Pattern Recognition， 2017， 72： 254-265. 10.1016/j.patcog.2017.07.029
9	RIESEN K， EMMENEGGER S， BUNKE H. A novel software toolkit for graph edit distance computation［C］// Proceedings of the 2013 International Workshop on Graph-Based Representations in Pattern Recognition， LNCS 7877. Berlin： Springer， 2013： 142-151.
10	宁懿昕，谢辉，姜火文. 图神经网络社区发现研究综述［J］. 计算机科学， 2021， 48（11A）：11-16. 10.11896/jsjkx.210500151
	NING Y X， XIE H， JIANG H W. Survey of graph neural network in community detection［J］. Computer Science， 2021， 48（11A）： 11-16. 10.11896/jsjkx.210500151
11	WANG R Z， YAN J C， YANG X K. Learning combinatorial embedding networks for deep graph matching［C］// Proceedings of the 2019 IEEE/CVF International Conference on Computer Vision. Piscataway： IEEE， 2019： 3056-3065. 10.1109/iccv.2019.00315
12	KIPF T N， WELLING M. Semi-supervised classification with graph convolutional networks［EB/OL］. （2017-02-22）［2022-03-21］.. 10.48550/arXiv.1609.02907
13	YU T S， WANG R Z， YAN J C， et al. Learning deep graph matching with channel-independent embedding and Hungarian attention［EB/OL］. （2022-02-10）［2022-03-21］..
14	FEY M， LENSSEN J E， WEICHERT F， et al. SplineCNN： fast geometric deep learning with continuous B-spline kernels［C］// Proceedings of the 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition. Piscataway： IEEE， 2018： 869-877. 10.1109/cvpr.2018.00097
15	ROLÍNEK M， SWOBODA P， ZIETLOW D， et al. Deep graph matching via blackbox differentiation of combinatorial solvers［C］// Proceedings of 2020 European Conference on Computer Vision， LNCS 12373. Cham： Springer， 2020： 407-424.
16	JIANG B， SUN P F， LUO B. GLMNet： graph learning-matching convolutional networks for feature matching［J］. Pattern Recognition， 2022， 121： No.108167. 10.1016/j.patcog.2021.108167
17	MORRIS C， RITZERT M， FEY M， et al. Weisfeiler and leman go neural： higher-order graph neural networks［C］// Proceedings of the 33rd AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2019： 4602-4609. 10.1609/aaai.v33i01.33014602
18	ARVIND V， KÖBLER J， RATTAN G， et al. On the power of color refinement［C］// Proceedings of the 2015 International Symposium on Fundamentals of Computation Theory， LNTCS 9210. Cham： Springer， 2015： 339-350.
19	LI Q M， HAN Z C， WU X M. Deeper insights into graph convolutional networks for semi-supervised learning［C］// Proceedings of the 32nd AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2018： 3538-3545. 10.1609/aaai.v32i1.11604
20	XU K， LI C T， TIAN Y L， et al. Representation learning on graphs with jumping knowledge networks［C］// Proceedings of the 35th International Conference on Machine Learning. New York： JMLR.org， 2018： 5453-5462.
21	CHO M， ALAHARI K， PONCE J. Learning graphs to match［C］// Proceedings of the 2013 IEEE International Conference on Computer Vision. Piscataway： IEEE， 2013： 25-32. 10.1109/iccv.2013.11
22	BOURDEV L， MALIK J. Poselets： body part detectors trained using 3D human pose annotations［C］// Proceedings of the IEEE 12th International Conference on Computer Vision. Piscataway： IEEE， 2009： 1365-1372. 10.1109/iccv.2009.5459303
23	EVERINGHAM M， van GOOL L， WILLIAMS C K I， et al. The PASCAL Visual Object Classes （VOC） challenge［J］. International Journal of Computer Vision， 2010， 88（2）： 303-338. 10.1007/s11263-009-0275-4
24	LAWLER E L. The quadratic assignment problem［J］. Management Science， 1963， 9（4）： 586-599. 10.1287/mnsc.9.4.586
25	LOIOLA E M， DE ABREU N M M， BOAVENTURA-NETTO P O， et al. A survey for the quadratic assignment problem［J］. European Journal of Operational Research， 2007， 176（2）： 657-690. 10.1016/j.ejor.2005.09.032
26	LEORDEANU M， HEBERT M. A spectral technique for correspondence problems using pairwise constraints［C］// Proceedings of the 10th IEEE International Conference on Computer Vision - Volume 2. Piscataway： IEEE， 2005： 1482-1489. 10.1109/iccv.2005.20
27	ZANFIR A， SMINCHISESCU C. Deep learning of graph matching［C］// Proceedings of the 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition. Piscataway： IEEE， 2018： 2684-2693. 10.1109/cvpr.2018.00284
28	BUTLER D J， WULFF J， STANLEY G B， et al. A naturalistic open source movie for optical flow evaluation［C］// Proceedings of the 2012 European Conference on Computer Vision， LNCS 7577. Berlin： Springer， 2012： 611-625.
29	WEINZAEPFEL P， REVAUD J， HARCHAOUI Z， et al. DeepFlow： large displacement optical flow with deep matching［C］// Proceedings of the 2013 IEEE International Conference on Computer Vision. Piscataway： IEEE， 2013： 1385-1392. 10.1109/iccv.2013.175
30	KUHN H W. The Hungarian method for the assignment problem［J］. Naval Research Logistics， 1995， 2（1/2）：83-97.
31	FEY M， LENSSEN J E， MORRIS C， et al. Deep graph matching consensus［EB/OL］. （2020-01-27）［2022-03-21］..
32	SIMONYAN K， ZISSERMAN A. Very deep convolutional networks for large-scale image recognition［EB/OL］. （2015-04-10）［2022-03-21］..
33	SWOBODA P， KUSKE J， SAVCHYNSKYY B. A dual ascent framework for Lagrangean decomposition of combinatorial problems［C］// Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway： IEEE， 2017： 4950-4960. 10.1109/cvpr.2017.526
34	WANG R Z， YAN J C， YANG X K. Neural graph matching network： learning Lawler’s quadratic assignment problem with extension to hypergraph and multiple-graph matching［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2022， 44（9）： 5261-5279.
35	WANG T， LIU H， LI Y D， et al. Learning combinatorial solver for graph matching［C］// Proceedings of the 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition. Piscataway： IEEE， 2020： 7565-7574. 10.1109/cvpr42600.2020.00759
36	GAO P， ZHANG H. Bayesian deep graph matching for correspondence identification in collaborative perception［EB/OL］. ［2022-05-02］.. 10.15607/rss.2021.xvii.022
37	VASWANI A， SHAZEER N， PARMAR N， et al. Attention is all you need［C］// Proceedings of the 31st International Conference on Neural Information Processing Systems. Red Hook， NY： Curran Associates Inc.， 2017：6000-6010.
38	ADAMS R P， ZEMEL R S. Ranking via Sinkhorn propagation［EB/OL］. （2011-06-14）［2022-03-21］..
39	VLASTELICA M， PAULUS A， MUSIL V， et al. Differentiation of blackbox combinatorial solvers［EB/OL］. （2020-02-16）［2022-03-21］..
40	KINGMA D P， BA J. Adam： a method for stochastic optimization［EB/OL］. （2017-01-30）［2022-03-21］..

模型	图学习模块	亲和力度量	匹配问题	图匹配求解算法	损失函数
GMN^［27］	无	加权点积的指数	Lawler’s QAP	幂迭代	像素点偏移
PCA-GM^［11］	GCN+交叉图卷积	加权点积的指数	仅考虑节点匹配	Sinkhorn网络	二元交叉熵
CIE^［13］	边嵌入+交叉图卷积	加权点积的指数	仅考虑节点匹配	Sinkhorn网络	二元交叉熵+匈牙利注意力
DGMC^［31］	SplineCNN	加权点积的指数	节点匹配+邻域共识	Sinkhorn网络+同步消息传递网络	负对数似然
BB-GM^［15］	SplineCNN	加权内积（式（12））	节点匹配+边的匹配	DD-ILP	汉明距离
GSAN-GM	GSAN	加权内积（式（12））	严苛的图匹配	DD-ILP	汉明距离

模型	图学习模块	亲和力度量	匹配问题	图匹配求解算法	损失函数
GMN^［27］	无	加权点积的指数	Lawler’s QAP	幂迭代	像素点偏移
PCA-GM^［11］	GCN+交叉图卷积	加权点积的指数	仅考虑节点匹配	Sinkhorn网络	二元交叉熵
CIE^［13］	边嵌入+交叉图卷积	加权点积的指数	仅考虑节点匹配	Sinkhorn网络	二元交叉熵+匈牙利注意力
DGMC^［31］	SplineCNN	加权点积的指数	节点匹配+邻域共识	Sinkhorn网络+同步消息传递网络	负对数似然
BB-GM^［15］	SplineCNN	加权内积（式（12））	节点匹配+边的匹配	DD-ILP	汉明距离
GSAN-GM	GSAN	加权内积（式（12））	严苛的图匹配	DD-ILP	汉明距离

模型	飞机	自行车	鸟	船	瓶子	公交车	汽车	猫	椅子	牛	桌子	狗	马	摩托车	人	植物	羊	沙发	火车	显示器	平均值
GMN	31.1	46.2	58.2	45.9	70.6	76.5	61.2	61.7	35.5	53.7	58.9	57.5	56.9	49.3	34.1	77.5	57.1	53.6	83.2	88.6	57.9
PCA-GM	40.9	55.0	65.8	47.9	76.9	77.9	63.5	67.4	33.7	66.5	63.6	61.3	58.9	62.8	44.9	77.5	67.4	57.5	86.7	90.9	63.4
CIE	51.2	69.2	70.1	55.0	82.8	72.8	69.0	74.2	39.6	68.8	71.8	70.0	71.8	66.8	44.8	85.2	69.9	65.4	85.2	92.4	68.8
DGMC	50.4	67.6	70.7	70.5	87.2	85.2	82.5	74.3	46.2	69.4	69.9	73.9	73.8	65.4	51.6	98.0	73.2	69.6	94.3	89.6	73.2
BB-GM	59.6	73.6	75.3	76.6	86.9	93.9	90.3	81.0	59.3	78.2	64.8	79.6	74.9	79.7	66.0	97.5	75.5	86.7	98.3	94.7	79.6
GSAN-GM	45.2	74.5	74.3	75.0	87.7	94.1	86.3	78.1	54.1	75.6	95.4	75.0	76.2	75.9	56.3	98.1	73.1	82.2	97.4	95.3	78.5

模型	飞机	自行车	鸟	船	瓶子	公交车	汽车	猫	椅子	牛	桌子	狗	马	摩托车	人	植物	羊	沙发	火车	显示器	平均值
GMN	31.1	46.2	58.2	45.9	70.6	76.5	61.2	61.7	35.5	53.7	58.9	57.5	56.9	49.3	34.1	77.5	57.1	53.6	83.2	88.6	57.9
PCA-GM	40.9	55.0	65.8	47.9	76.9	77.9	63.5	67.4	33.7	66.5	63.6	61.3	58.9	62.8	44.9	77.5	67.4	57.5	86.7	90.9	63.4
CIE	51.2	69.2	70.1	55.0	82.8	72.8	69.0	74.2	39.6	68.8	71.8	70.0	71.8	66.8	44.8	85.2	69.9	65.4	85.2	92.4	68.8
DGMC	50.4	67.6	70.7	70.5	87.2	85.2	82.5	74.3	46.2	69.4	69.9	73.9	73.8	65.4	51.6	98.0	73.2	69.6	94.3	89.6	73.2
BB-GM	59.6	73.6	75.3	76.6	86.9	93.9	90.3	81.0	59.3	78.2	64.8	79.6	74.9	79.7	66.0	97.5	75.5	86.7	98.3	94.7	79.6
GSAN-GM	45.2	74.5	74.3	75.0	87.7	94.1	86.3	78.1	54.1	75.6	95.4	75.0	76.2	75.9	56.3	98.1	73.1	82.2	97.4	95.3	78.5

模型	汽车	鸭子	人脸	摩托车	酒瓶	均值
GMN^［27］	67.9	76.7	99.8	69.2	83.1	79.3
PCA-GM^［11］	87.6	83.6	100.0	77.6	88.4	87.4
BB-GM^［15］	96.1	89.6	100.0	100.0	97.1	96.5
GSAN-GM	93.7	85.4	100.0	96.7	97.6	94.7

Deep graph matching model based on self-attention network

基于自注意力网络的深度图匹配模型

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 40

Related Articles 15

Recommended Articles

Metrics

VGG16	GSAN		DD-ILP	精度/%
VGG16	空间编码器	自注意力	DD-ILP	精度/%
√	×	×	×	59.34
√	×	√	×	62.63
√	√	√	×	73.82
√	√	√	√	78.69

[1]	Yunchuan HUANG, Yongquan JIANG, Juntao HUANG, Yan YANG. Molecular toxicity prediction based on meta graph isomorphism network [J]. Journal of Computer Applications, 2024, 44(9): 2964-2969.
[2]	Yexin PAN, Zhe YANG. Optimization model for small object detection based on multi-level feature bidirectional fusion [J]. Journal of Computer Applications, 2024, 44(9): 2871-2877.
[3]	Jing QIN, Zhiguang QIN, Fali LI, Yueheng PENG. Diagnosis of major depressive disorder based on probabilistic sparse self-attention neural network [J]. Journal of Computer Applications, 2024, 44(9): 2970-2974.
[4]	Xiyuan WANG, Zhancheng ZHANG, Shaokang XU, Baocheng ZHANG, Xiaoqing LUO, Fuyuan HU. Unsupervised cross-domain transfer network for 3D/2D registration in surgical navigation [J]. Journal of Computer Applications, 2024, 44(9): 2911-2918.
[5]	Liting LI, Bei HUA, Ruozhou HE, Kuang XU. Multivariate time series prediction model based on decoupled attention mechanism [J]. Journal of Computer Applications, 2024, 44(9): 2732-2738.
[6]	Shunyong LI, Shiyi LI, Rui XU, Xingwang ZHAO. Incomplete multi-view clustering algorithm based on self-attention fusion [J]. Journal of Computer Applications, 2024, 44(9): 2696-2703.
[7]	Yuhan LIU, Genlin JI, Hongping ZHANG. Video pedestrian anomaly detection method based on skeleton graph and mixed attention [J]. Journal of Computer Applications, 2024, 44(8): 2551-2557.
[8]	Yanjie GU, Yingjun ZHANG, Xiaoqian LIU, Wei ZHOU, Wei SUN. Traffic flow forecasting via spatial-temporal multi-graph fusion [J]. Journal of Computer Applications, 2024, 44(8): 2618-2625.
[9]	Fan YANG, Yao ZOU, Mingzhi ZHU, Zhenwei MA, Dawei CHENG, Changjun JIANG. Credit card fraud detection model based on graph attention Transformation neural network [J]. Journal of Computer Applications, 2024, 44(8): 2634-2642.
[10]	Qianhong SHI, Yan YANG, Yongquan JIANG, Xiaocao OUYANG, Wubo FAN, Qiang CHEN, Tao JIANG, Yuan LI. Multi-granularity abrupt change fitting network for air quality prediction [J]. Journal of Computer Applications, 2024, 44(8): 2643-2650.
[11]	Yiqun ZHAO, Zhiyu ZHANG, Xue DONG. Anisotropic travel time computation method based on dense residual connection physical information neural networks [J]. Journal of Computer Applications, 2024, 44(7): 2310-2318.
[12]	Song XU, Wenbo ZHANG, Yifan WANG. Lightweight video salient object detection network based on spatiotemporal information [J]. Journal of Computer Applications, 2024, 44(7): 2192-2199.
[13]	Xun SUN, Ruifeng FENG, Yanru CHEN. Monocular 3D object detection method integrating depth and instance segmentation [J]. Journal of Computer Applications, 2024, 44(7): 2208-2215.
[14]	Zheng WU, Zhiyou CHENG, Zhentian WANG, Chuanjian WANG, Sheng WANG, Hui XU. Deep learning-based classification of head movement amplitude during patient anaesthesia resuscitation [J]. Journal of Computer Applications, 2024, 44(7): 2258-2263.
[15]	Huanhuan LI, Tianqiang HUANG, Xuemei DING, Haifeng LUO, Liqing HUANG. Public traffic demand prediction based on multi-scale spatial-temporal graph convolutional network [J]. Journal of Computer Applications, 2024, 44(7): 2065-2072.