Towards Deep Graph Matching Via Embedding-based Approach

Graph matcing refers to finding node correspondence between two graphs,such that the structure similarity can be maxized.Graph matching problem is widely used in various fieds,such as computer vision,pattern recognition,computer graphics and bioinformatics.Different from the point-based mathing problem,the graph matching considers not only the consistency between node sets,but also keeps the consistency between edge sets.Thus,it is a quadratic assignment programming which is hard to find the global optimum,and most methods utilizing relaxation techniques to find an acceptable local optimum is needed.Recently,deep learning based graph matching solver have been proposed and achieved impressive performance.Among them,embedding based deep graph matching solver aimed to learn the node-to-node affinity scores with node features embedded with second-order structure information refined by graph neural networks.In this way,the graph matching problem can be relaxed into a first-order linear assignment problem that can be solved efficiently in polynomial time.However,such kind of pipeline ignore the edge-to-edge similarity in essence,which is limited to Koopmans-Beckmann's QAP.This thesis focus on this shortcoming of the embedding based deep graph matching,and puts forward two contribution to solve the problem.First,the thesis proposed a cross-graph embedding with edge-wise attention for deep graph matching.In this model,the edge similarity is regarded as the matching weight probability between two graphs.Through the node-edge incidence matrices transformation,the edge similarity can be transformed as a node-to-node attention matrix between two graphs and finally the cross graph embedding module is proposed.The experimental results show that our proposed module can benefit to the performance of the graph matching network.Second,the thesis proposed an embedding based approach for learning Lawler's quadratic assignment problem via factorized GCN.This model extended the embedding based method to learning the general Lawler's QAP.Through the mapping from two input graphs to dual assignment graphs,the GCN propogation under assignment graphs is caluculated to learn the intrinsic topology of graph matching problem.In the graph convolution module,a decomposition of GCN operation is proposed to accelerate the computation and reduce the memory consumption,which the computation complexity is reduced from O(n~4)to O(n~2).Experimental results show that the proposed method can effectively improve the performance of deep learning based graph matching,and hold the superiority of time and space complexity.In conlusion,this thesis is based on the overseas and domestic research status with thorough investigation on graph matching problem,and proposed effective solutions to existing shortcoming of the embedding based graph matching pipeline,resulting in the performance and efficiency of the proposed method improved.