Learning graph matching

Area of Science:

• Computer Science
• Pattern Recognition
• Artificial Intelligence

Background:

• Graph matching is crucial for pattern recognition across diverse fields like computer vision and computational biology.
• The problem is often formulated as a quadratic assignment problem, which is NP-hard, necessitating approximate solutions.
• Existing research focuses on efficient algorithms for solving the quadratic assignment problem.

Purpose of the Study:

• To develop a method for learning graph matching compatibility functions.
• To enable graph matching solutions to align with human-provided matches.
• To improve the performance of graph matching algorithms through learned parameters.

Main Methods:

• A supervised learning framework for graph matching is proposed.
• Training data consists of pairs of graphs with corresponding human-generated matches as labels.
• Compatibility functions are estimated based on these training examples.

Main Results:

• Learned graph matching significantly enhances the performance of standard algorithms.
• A simple linear assignment method with learning outperforms a state-of-the-art quadratic assignment relaxation algorithm (Graduated Assignment with bistochastic normalisation).
• Experimental results demonstrate substantial performance gains due to the learning approach.

Conclusions:

• Learning compatibility functions is an effective strategy to improve graph matching.
• This approach offers a promising direction for developing more accurate and human-aligned graph matching systems.
• The proposed learning method provides a practical alternative to traditional optimization techniques for graph matching.