Source-linked AI summary
A General Multi-Graph Matching Approach via Graduated Consistency-regularized Boosting
Junchi Yan, Minsu Cho, Hongyuan Zha, Xiaokang Yang, Stephen Chu
TL;DR
The paper addresses multi-graph matching by combining pairwise affinity with global matching consistency while avoiding early error propagation. It proposes iterative boosting with gradually infused consistency regularization and reports competitive accuracy, including improved cost-effectiveness under arbitrary noise.
Problem
Existing methods either enforce consistency early, risking error propagation across iterations and graphs, or optimize from initial pairwise matchings without using affinity information.
Method
The proposed algorithms iteratively boost affinity scores while gradually incorporating matching consistency, with variants that elicit inlier-associated affinity and consistency.
Results
The main method generally outperforms the baseline and state-of-the-art methods, while inlier-eliciting variants improve ISB cost-effectiveness, especially on real image data with arbitrary noise.
Takeaways & Limitations
Matching consistency can regularize affinity optimization, and additional graphs generally improve accuracy while helping dismiss local ambiguity.
Takeaways & Limitations
The iterative method does not guarantee full consistency, and enforcing full consistency can degrade performance when considerable outliers are unmatchable.
Abstract
from arXiv · showhide
This paper addresses the problem of matching $N$ weighted graphs referring to an identical object or category. More specifically, matching the common node correspondences among graphs. This multi-graph matching problem involves two ingredients affecting the overall accuracy: i) the local pairwise matching affinity score among graphs; ii) the global matching consistency that measures the uniqueness of the pairwise matching results by different chaining orders. Previous studies typically either enforce the matching consistency constraints in the beginning of iterative optimization, which may propagate matching error both over iterations and across graph pairs; or separate affinity optimizing and consistency regularization in two steps. This paper is motivated by the observation that matching consistency can serve as a regularizer in the affinity objective function when the function is biased due to noises or inappropriate modeling. We propose multi-graph matching methods to incorporate the two aspects by boosting the affinity score, meanwhile gradually infusing the consistency as a regularizer. Furthermore, we propose a node-wise consistency/affinity-driven mechanism to elicit the common inlier nodes out of the irrelevant outliers. Extensive results on both synthetic and public image datasets demonstrate the competency of the proposed algorithms.
1 INTRODUCTION
Multi-graph matching seeks correspondences across collections of related graphs, extending graph matching beyond isolated pairs. The paper builds on graph matching’s use of unary and second-order structural affinities while targeting global matching across graphs.
- Applications: Graph matching supports correspondence tasks in bioinformatics, data fusion, graphics, information retrieval, and computer vision.Computer vision examples include object recognition, shape matching, object tracking, and image labeling.
- Graph matching formulation: Unlike point-based matching, graph matching combines unary node-to-node and second-order edge-to-edge structural similarity.This structural encoding is intended to improve robustness for correspondence problems.
- Computational setting: Because graph matching is NP-complete, existing methods generally seek approximate solutions or exact polynomial-time solutions for restricted graph classes.Examples of restricted classes include planar, bounded-valence, and tree graphs.
- Graph matching formulation: Pairwise graph matching is commonly formulated as a quadratic assignment problem combining individual node matches with pairs of matches.The formulations include Koopmans-Beckmann’s and Lawler’s QAP variants.
- Multi-graph matching: Collections of related graphs provide context for finding global matchings across graphs rather than correspondences between only one pair.Applications include multi-source sensor fusion, multi-view shape analysis, topic alignment, clustering, classification, and indexing.
2 RELATED WORK AND MODELS
The paper situates multi-graph matching between affinity-driven and consistency-driven approaches, then formulates pairwise matching through assignment matrices and quadratic affinities. It motivates a graduated strategy because existing consistency handling can propagate errors or discard affinity information, while standard formulations assume graphs contain only common inliers.
- Pairwise graph matching: Lawler’s QAP represents pairwise matching with vec(X)^T K vec(X), where K encodes unary and second-order edge affinities.The assignment matrix contains binary entries indicating whether a node in one graph matches a node in the other.
- Pairwise graph matching: Pairwise graph matching uses an assignment matrix X to establish one-to-one node correspondences while maximizing unary and edge compatibility.The associated affinity matrix encodes node and edge-pair similarities, and the problem is expressed as a two-way constrained QAP.
- Graph-size handling: Unequal-sized graphs can be converted to equal-sized graphs by adding dummy nodes or slack variables, enabling permutation-based multi-graph methods.This preprocessing is intended to handle superfluous nodes and supports matching common inliers of equal sizes.
- Multi-graph matching: Multi-graph matching methods are commonly divided into affinity score-driven and pairwise matching consistency-driven approaches.Affinity-driven methods optimize overall pairwise affinity, while consistency-driven methods typically apply global synchronization after pairwise matching.
- Limitations of prior approaches: Existing approaches either enforce consistency early, risking error propagation across iterations and graphs, or improve initial matchings without using affinity information.This division motivates combining affinity optimization with consistency regularization.
- Outliers and proposed direction: The standard formulation assumes every graph contains exactly the common inlier nodes, which fails when unmatchable outliers are present.The paper therefore introduces flexible treatment of outliers through node-wise affinity- and consistency-driven inlier elicitation.
- Outliers and proposed direction: The proposed procedure boosts affinity scores while gradually regularizing them with overall matching consistency.Affinity is treated as more informative early in boosting, whereas consistency becomes useful as accuracy improvement saturates and noise biases affinity.
3 PROPOSED ALGORITHMS
The proposed algorithms iteratively replace pairwise matchings by compositions that improve affinity, then incorporate matching consistency as a graduated regularizer. Variants provide broader search, inverse regularization, efficient node-level proxies, convergence guarantees, and optional full-consistency post-processing.
- Iterative affinity score/consistency boosting: ISB iteratively replaces an existing pairwise matching with a composition of matchings along intermediate graphs when the composition improves the affinity score.The method searches for appropriate compositional replacements without knowing the true matching accuracy.
- Proposed algorithms: ISB, ISB2nd, and ISBcst provide baseline alternatives, while ISB-GC introduces graduated consistency regularization and ISB-GC-U/P provide efficient variants.The algorithms are presented as a baseline, comparison variants, a highlighted graduated method, and unary/pairwise efficient implementations.
- Convergence and post-processing: ISB is guaranteed to converge to a stationary configuration, and ISB-GC-U is likewise stated to converge, whereas full consistency may reduce performance with many outliers.The paper optionally applies a post-processing step for full consistency, but notes that unmatchable outliers can cause degeneration.
- Iterative affinity score/consistency boosting: The 2nd-order variant expands the search from O(N) to O(N^2) while providing greater exploration capability than the first-order method.Its score-boosting property also ensures convergence.
- Graduated consistency-regularized boosting: ISB-GC treats matching consistency as a regularizer for affinity maximization, using affinity early and increasing consistency influence as accuracy lifting saturates.The method is motivated by affinity becoming less informative after early-stage improvement and consistency helping with corrupted graphs and outliers.
- Graduated consistency-regularized boosting: ISB-GC outperforms ISB-GCinv in the reported comparison, supporting the proposed direction of gradually increasing consistency regularization rather than reversing the roles.ISB-GCinv instead drives updates by consistency and gradually increases affinity weight.
4 EXPERIMENTS AND DISCUSSION
Experiments evaluate the proposed methods on synthetic and real-image data under varied noise, outlier, density, coverage, and graph-count settings. ISB-GC generally improves matching accuracy, while node-wise eliciting mechanisms improve robustness to outliers and graduated consistency is particularly useful under larger noise.
- Experimental settings: Experiments vary deformation noise, outliers, edge density, initial matching coverage, viewing angles, scales, and shapes across synthetic and real-image data.Accuracy is averaged over pairwise matches using ground-truth correspondences, counting only common inliers.
- Comparing methods: The proposed ISB-GC generally outperforms baseline ISB and state-of-the-art methods on synthetic random graphs and real images, except the coverage test.In the coverage test, many initial pairwise matches are random, making a consistent solution biased toward true accuracy.
- Comparing methods: Matching accuracy generally increases as the number of graphs N grows, although fluctuations occur, especially for the car image sequence.The relative improvement over RRWM also increases with N, consistent with more graphs helping dismiss local ambiguity.
- Comparing methods: For partial-similarity CMU-POSE data, omitting full consistency is more effective than enforcing it, supporting graduated consistency regularization over two-step hard synchronization.The comparison is shown in the bottom row of Fig.4.
- Outlier handling: Node-wise consistency- and affinity-driven eliciting methods generally outperform state-of-the-art methods when their top-node hitting rates exceed 0.8.Affinity-driven selection is robust to outlier count for face images because facial landmarks form a distinctive structure.
- Outlier handling: Eliciting mechanisms improve accuracy over original algorithms without outlier discrimination and remain relatively smooth around the exact inlier count n_i = 10.This indicates robustness when the number of common inliers is only roughly estimated.
- Runtime and baselines: ISB-GC* has greater runtime cost, while MatchLift is heavier because it requires more iterations and underperforms with a majority of outliers.The MatchLift comparison is reported for the synthetic and real-image evaluations.
- Outlier handling: Affinity-driven eliciting performs better for deformation ε < .05, whereas consistency-driven eliciting performs better when ε > .05 with fixed outlier count.The reported crossover supports using consistency under larger noise and few outliers.
5 CONCLUSION
The paper proposes iterative boosting algorithms that combine affinity scores with matching consistency for multi-graph matching. Outlier-tolerant variants use inlier-associated affinity and consistency, with experiments reporting competitive accuracy and improved cost-effectiveness under noise.
- The proposed algorithms jointly incorporate affinity scores and matching consistency through an iterative approximate boosting procedure.
- Outlier-tolerant variants elicit affinity and consistency associated with inlier nodes.
- ISB-GC generally achieves more competitive accuracy than state-of-the-art methods.
- ISB-GC-U/P generally improve ISB's cost-effectiveness on real image data under arbitrary noises.