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

doi:10.11772/j.issn.1001-9081.2022030345

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (4): 1005-1012.DOI: 10.11772/j.issn.1001-9081.2022030345

所属专题：人工智能

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

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

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

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

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)

摘要/Abstract

摘要：

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

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

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

中图分类号:

TP391

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

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.

图/表 10

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

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 40

相关文章 15

编辑推荐

Metrics

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

[1]	黄云川, 江永全, 黄骏涛, 杨燕. 基于元图同构网络的分子毒性预测[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2964-2969.
[2]	潘烨新, 杨哲. 基于多级特征双向融合的小目标检测优化模型[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2871-2877.
[3]	李顺勇, 李师毅, 胥瑞, 赵兴旺. 基于自注意力融合的不完整多视图聚类算法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2696-2703.
[4]	秦璟, 秦志光, 李发礼, 彭悦恒. 基于概率稀疏自注意力神经网络的重性抑郁疾患诊断[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2970-2974.
[5]	王熙源, 张战成, 徐少康, 张宝成, 罗晓清, 胡伏原. 面向手术导航3D/2D配准的无监督跨域迁移网络[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2911-2918.
[6]	李力铤, 华蓓, 贺若舟, 徐况. 基于解耦注意力机制的多变量时序预测模型[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2732-2738.
[7]	刘禹含, 吉根林, 张红苹. 基于骨架图与混合注意力的视频行人异常检测方法[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2551-2557.
[8]	顾焰杰, 张英俊, 刘晓倩, 周围, 孙威. 基于时空多图融合的交通流量预测[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2618-2625.
[9]	杨帆, 邹窈, 朱明志, 马振伟, 程大伟, 蒋昌俊. 基于图注意力Transformer神经网络的信用卡欺诈检测模型[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2634-2642.
[10]	石乾宏, 杨燕, 江永全, 欧阳小草, 范武波, 陈强, 姜涛, 李媛. 面向空气质量预测的多粒度突变拟合网络[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2643-2650.
[11]	赵亦群, 张志禹, 董雪. 基于密集残差物理信息神经网络的各向异性旅行时计算方法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2310-2318.
[12]	徐松, 张文博, 王一帆. 基于时空信息的轻量视频显著性目标检测网络[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2192-2199.
[13]	孙逊, 冯睿锋, 陈彦如. 基于深度与实例分割融合的单目3D目标检测方法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2208-2215.
[14]	吴筝, 程志友, 汪真天, 汪传建, 王胜, 许辉. 基于深度学习的患者麻醉复苏过程中的头部运动幅度分类方法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2258-2263.
[15]	李欢欢, 黄添强, 丁雪梅, 罗海峰, 黄丽清. 基于多尺度时空图卷积网络的交通出行需求预测[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2065-2072.