Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (4): 1005-1012.DOI: 10.11772/j.issn.1001-9081.2022030345
• Artificial intelligence •
Zhoubo XU, Puqing CHEN(), Huadong LIU, Xin YANG
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.Supported by:
通讯作者:
陈浦青
作者简介:
徐周波(1976—),女,浙江奉化人,教授,博士,CCF会员,主要研究方向:符号计算、智能规划、约束求解;基金资助:
CLC Number:
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.
Add to citation manager EndNote|Ris|BibTeX
URL: http://www.joca.cn/EN/10.11772/j.issn.1001-9081.2022030345
模型 | 图学习模块 | 亲和力度量 | 匹配问题 | 图匹配求解算法 | 损失函数 |
---|---|---|---|---|---|
GMN[ | 无 | 加权点积的指数 | Lawler’s QAP | 幂迭代 | 像素点偏移 |
PCA-GM[ | GCN+交叉图卷积 | 加权点积的指数 | 仅考虑节点匹配 | Sinkhorn网络 | 二元交叉熵 |
CIE[ | 边嵌入+交叉图卷积 | 加权点积的指数 | 仅考虑节点匹配 | Sinkhorn网络 | 二元交叉熵+匈牙利注意力 |
DGMC[ | SplineCNN | 加权点积的指数 | 节点匹配+邻域共识 | Sinkhorn网络+同步消息传递网络 | 负对数似然 |
BB-GM[ | SplineCNN | 加权内积( | 节点匹配+边的匹配 | DD-ILP | 汉明距离 |
GSAN-GM | GSAN | 加权内积( | 严苛的图匹配 | DD-ILP | 汉明距离 |
Tab. 1 Detailed information of several deep graph matching models
模型 | 图学习模块 | 亲和力度量 | 匹配问题 | 图匹配求解算法 | 损失函数 |
---|---|---|---|---|---|
GMN[ | 无 | 加权点积的指数 | Lawler’s QAP | 幂迭代 | 像素点偏移 |
PCA-GM[ | GCN+交叉图卷积 | 加权点积的指数 | 仅考虑节点匹配 | Sinkhorn网络 | 二元交叉熵 |
CIE[ | 边嵌入+交叉图卷积 | 加权点积的指数 | 仅考虑节点匹配 | Sinkhorn网络 | 二元交叉熵+匈牙利注意力 |
DGMC[ | SplineCNN | 加权点积的指数 | 节点匹配+邻域共识 | Sinkhorn网络+同步消息传递网络 | 负对数似然 |
BB-GM[ | SplineCNN | 加权内积( | 节点匹配+边的匹配 | DD-ILP | 汉明距离 |
GSAN-GM | GSAN | 加权内积( | 严苛的图匹配 | 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 |
Tab. 2 Accuracy comparison results of different models on 20 classes of images in PASCAL VOC dataset
模型 | 飞机 | 自行车 | 鸟 | 船 | 瓶子 | 公交车 | 汽车 | 猫 | 椅子 | 牛 | 桌子 | 狗 | 马 | 摩托车 | 人 | 植物 | 羊 | 沙发 | 火车 | 显示器 | 平均值 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
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[ | 67.9 | 76.7 | 99.8 | 69.2 | 83.1 | 79.3 |
PCA-GM[ | 87.6 | 83.6 | 100.0 | 77.6 | 88.4 | 87.4 |
BB-GM[ | 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 |
Tab. 3 Accuracy comparison results of different models on 5 classes of images in Willow Object dataset
模型 | 汽车 | 鸭子 | 人脸 | 摩托车 | 酒瓶 | 均值 |
---|---|---|---|---|---|---|
GMN[ | 67.9 | 76.7 | 99.8 | 69.2 | 83.1 | 79.3 |
PCA-GM[ | 87.6 | 83.6 | 100.0 | 77.6 | 88.4 | 87.4 |
BB-GM[ | 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 |
VGG16 | GSAN | DD-ILP | 精度/% | |
---|---|---|---|---|
空间编码器 | 自注意力 | |||
√ | × | × | × | 59.34 |
√ | × | √ | × | 62.63 |
√ | √ | √ | × | 73.82 |
√ | √ | √ | √ | 78.69 |
Tab. 4 Ablation experiment results on PASCAL VOC dataset
VGG16 | GSAN | DD-ILP | 精度/% | |
---|---|---|---|---|
空间编码器 | 自注意力 | |||
√ | × | × | × | 59.34 |
√ | × | √ | × | 62.63 |
√ | √ | √ | × | 73.82 |
√ | √ | √ | √ | 78.69 |
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].. |
[1] | Rongjun CHEN, Xuanhui YAN, Chaocheng YANG. Fusion imaging-based recurrent capsule classification network for time series [J]. Journal of Computer Applications, 2023, 43(3): 692-699. |
[2] | Yingmao YAO, Xiaoyan JIANG. Video-based person re-identification method based on graph convolution network and self-attention graph pooling [J]. Journal of Computer Applications, 2023, 43(3): 728-735. |
[3] | Jiangfeng ZHANG, Tao YAN, Bin CHEN, Yuhua QIAN, Yantao SONG. Multi-depth-of-field 3D shape reconstruction with global spatio-temporal feature coupling [J]. Journal of Computer Applications, 2023, 43(3): 894-902. |
[4] | Xuedong HE, Shibin XUAN, Kuan WANG, Mengnan CHEN. DeepLabV3+ image segmentation algorithm fusing cumulative distribution function and channel attention mechanism [J]. Journal of Computer Applications, 2023, 43(3): 936-942. |
[5] | Boyi FU, Yuncong PENG, Xin LAN, Xiaolin QIN. Survey of label noise learning algorithms based on deep learning [J]. Journal of Computer Applications, 2023, 43(3): 674-684. |
[6] | Li’an ZHU, Hong ZHANG. Nonhomogeneous image dehazing based on dual-branch conditional generative adversarial network [J]. Journal of Computer Applications, 2023, 43(2): 567-574. |
[7] | Qi WANG, Hang LEI, Xupeng WANG. Deep face verification under pose interference [J]. Journal of Computer Applications, 2023, 43(2): 595-600. |
[8] | Ping WANG, Nan CHEN, Lei LU. Fall detection algorithm based on scene prior and attention guidance [J]. Journal of Computer Applications, 2023, 43(2): 529-535. |
[9] | Youxin WANG, Bin CHEN. Print defect detection method based on deep comparison network [J]. Journal of Computer Applications, 2023, 43(1): 250-258. |
[10] | Yangping LIN, Jia LIU, Pei CHEN, Mingshu ZHANG, Xiaoyuan YANG. Semi-generative video steganography scheme based on deep convolutional generative adversarial net [J]. Journal of Computer Applications, 2023, 43(1): 169-175. |
[11] | Jun ZHANG, Pengli WU, Lukui SHI, Jin SHI, Bin PAN. Deep learning model for multi-station temperature prediction combined with MOD11A1 and surface meteorological station data [J]. Journal of Computer Applications, 2023, 43(1): 321-328. |
[12] | Keyou GUO, Xue LI, Min YANG. Real‑time detection method of traffic information based on lightweight YOLOv4 [J]. Journal of Computer Applications, 2023, 43(1): 74-80. |
[13] | Zhijun SHEN, Lina MU, Jing GAO, Yuanhang SHI, Zhiqiang LIU. Review of fine-grained image categorization [J]. Journal of Computer Applications, 2023, 43(1): 51-60. |
[14] | Jiaxuan WEI, Shikang DU, Zhixuan YU, Ruisheng ZHANG. Review of white-box adversarial attack technologies in image classification [J]. Journal of Computer Applications, 2022, 42(9): 2732-2741. |
[15] | Jinghu LI, Qianguo XING, Xiangyang ZHENG, Lin LI, Lili WANG. Noctiluca scintillans red tide extraction method from UAV images based on deep learning [J]. Journal of Computer Applications, 2022, 42(9): 2969-2974. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||