Deep Graph Matching under Quadratic Constraint

Abstract

Recently, deep learning based methods have demonstrated promising results on the graph matching problem, by relying on the descriptive capability of deep features extracted on graph nodes. However, one main limitation with existing deep graph matching (DGM) methods lies in their ignorance of explicit constraint of graph structures, which may lead the model to be trapped into local minimum in training. In this paper, we propose to explicitly formulate pairwise graph structures as a \textbf{quadratic constraint} incorporated into the DGM framework. The quadratic constraint minimizes the pairwise structural discrepancy between graphs, which can reduce the ambiguities brought by only using the extracted CNN features. Moreover, we present a differentiable implementation to the quadratic constrained-optimization such that it is compatible with the unconstrained deep learning optimizer. To give more precise and proper supervision, a well-designed false matching loss against class imbalance is proposed, which can better penalize the false negatives and false positives with less overfitting. Exhaustive experiments demonstrate that our method competitive performance on real-world datasets.

References in corpus (8)

• Very Deep Convolutional Networks for Large-Scale Image Recognition
• Semi-Supervised Classification with Graph Convolutional Networks
• Graph Neural Networks: A Review of Methods and Applications
• On the Global Linear Convergence of Frank-Wolfe Optimization Variants
• Ranking via Sinkhorn Propagation
• Training Deep Networks with Structured Layers by Matrix Backpropagation
• GLMNet: Graph Learning-Matching Networks for Feature Matching
• Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching