TY - JOUR
T1 - Determinant Regularization for Gradient-Efficient Graph Matching
AU - Yu, Tianshu
AU - Yan, Junchi
AU - Li, Baoxin
N1 - Funding Information:
Tianshu Yu and Baoxin Li were supported in part by a grant from ONR. Any opinions expressed in this material are those of the authors and do not necessarily reflect the views of ONR. Junchi Yan was partially supported by China Major State Research Development Program 2018AAA0100704, NSFC (61972250, U19B2035), and the Open Project Program of the National Laboratory of Pattern Recognition (NLPR), China.
Publisher Copyright:
© 2020 IEEE.
PY - 2020
Y1 - 2020
N2 - Graph matching refers to finding vertex correspondence for a pair of graphs, which plays a fundamental role in many vision and learning related tasks. Directly applying gradient-based continuous optimization on graph matching can be attractive for its simplicity but calls for effective ways of converting the continuous solution to the discrete one under the matching constraint. In this paper, we show a novel regularization technique with the tool of determinant analysis on the matching matrix which is relaxed into continuous domain with gradient based optimization. Meanwhile we present a theoretical study on the property of our relaxation technique. Our paper strikes an attempt to understand the geometric properties of different regularization techniques and the gradient behavior during the optimization. We show that the proposed regularization is more gradient-efficient than traditional ones during early update stages. The analysis will also bring about insights for other problems under bijection constraints. The algorithm procedure is simple and empirical results on public benchmark show its effectiveness on both synthetic and real-world data.
AB - Graph matching refers to finding vertex correspondence for a pair of graphs, which plays a fundamental role in many vision and learning related tasks. Directly applying gradient-based continuous optimization on graph matching can be attractive for its simplicity but calls for effective ways of converting the continuous solution to the discrete one under the matching constraint. In this paper, we show a novel regularization technique with the tool of determinant analysis on the matching matrix which is relaxed into continuous domain with gradient based optimization. Meanwhile we present a theoretical study on the property of our relaxation technique. Our paper strikes an attempt to understand the geometric properties of different regularization techniques and the gradient behavior during the optimization. We show that the proposed regularization is more gradient-efficient than traditional ones during early update stages. The analysis will also bring about insights for other problems under bijection constraints. The algorithm procedure is simple and empirical results on public benchmark show its effectiveness on both synthetic and real-world data.
UR - http://www.scopus.com/inward/record.url?scp=85089134296&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85089134296&partnerID=8YFLogxK
U2 - 10.1109/CVPR42600.2020.00715
DO - 10.1109/CVPR42600.2020.00715
M3 - Conference article
AN - SCOPUS:85089134296
SN - 1063-6919
SP - 7121
EP - 7130
JO - Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition
JF - Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition
M1 - 9157637
T2 - 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2020
Y2 - 14 June 2020 through 19 June 2020
ER -