Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem With Extension to Hypergraph and...

Area of Science:

• Computer Vision
• Artificial Intelligence
• Graph Theory

Background:

• Graph matching is a key problem in combinatorial optimization, often formulated as Lawler's Quadratic Assignment Problem (QAP).
• Existing deep matching methods typically focus on learning node/edge features independently for each graph.
• Directly learning from the affinity matrix for general QAP remains an underexplored area.

Purpose of the Study:

• To present a novel QAP network capable of directly learning from the affinity matrix for graph matching.
• To translate the graph matching problem into a constrained vertex classification task.
• To extend the network's applicability to hypergraph matching and multi-graph matching.

Main Methods:

• A QAP network is proposed that directly learns from the association graph (affinity matrix).
• The method employs an embedding network for vertex classification, followed by Sinkhorn normalization and cross-entropy loss for end-to-end training.
• Improvements include a Sinkhorn-based matching-aware constraint and dummy nodes for handling graphs of unequal sizes.

Main Results:

• The proposed network achieves competitive performance on pure QAP tasks, including the QAPLIB benchmark.
• It surpasses state-of-the-art graph matching and QAP solvers in terms of speed and accuracy on synthetic data.
• Experimental results on real-world images demonstrate the network's effectiveness.

Conclusions:

• This work presents one of the first networks to directly learn from the general Lawler's QAP formulation.
• The approach offers an efficient and effective solution for graph matching and related problems.
• The framework is extendable to hypergraph and multi-graph matching scenarios.