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
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: https://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] | 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. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||