Unifying Offline and Online Multi-Graph Matching via Finding Shortest Paths on Supergraph

Area of Science:

• Computer Science
• Graph Theory
• Artificial Intelligence

Background:

• Multiple Graph Matching (MGM) is a fundamental problem in computer vision and machine learning.
• Existing MGM methods often struggle with scalability and performance in both offline and online settings.

Purpose of the Study:

• To develop a unified and efficient framework for solving the MGM problem in both offline and online scenarios.
• To introduce the concept of cycle-consistency over pairwise matchings for improved MGM accuracy.

Main Methods:

• Formulating MGM as finding an optimal composition path on a supergraph.
• Leveraging theoretical analysis to convert offline MGM to all-pairs shortest paths and online MGM to single-source shortest paths.
• Employing the Floyd algorithm for offline and the Shortest Path Faster Algorithm (SPFA) for online MGM.

Main Results:

• The proposed methods demonstrate superior performance compared to state-of-the-art MGM algorithms like CAO, MISM, and IMGM.
• Experimental results validate the effectiveness of the cycle-consistency approach in both offline and online settings.
• The framework provides a significant advancement in solving complex graph matching tasks.

Conclusions:

• The cycle-consistency based supergraph approach offers a robust and efficient solution for multiple graph matching.
• This work advances the field by providing a theoretically grounded and experimentally validated method for MGM.
• Publicly available source code will facilitate further research and application of these MGM techniques.