Cross-order Consensus Graph Matching

Graph matching aims to establish node correspondences while preserving both unary appearance compatibility and pairwise structural consistency. Recent deep graph matching methods have achieved strong empirical performance, but many of them either compress edge information into node embeddings before matching or rely on surrogate optimization signals for quadratic objectives. These design choices can weaken structural discrimination and may lead to optimization directions that are not aligned with the relaxed quadratic assignment problem (QAP). We propose Cross-order Consensus Graph Matching (CCGM), a framework that explicitly couples first-order node assignment and second-order edge assignment. CCGM constructs line graphs to convert edge matching into a node matching problem, learns node and edge affinities in parallel, and refines them through a Cross-order Consensus Solver motivated by the exact gradient of the factorized relaxed QAP. We further introduce Cross-order Alignment Regularization to encourage agreement between node-induced edge assignments and edge-induced node support during training. Experiments on standard visual graph matching benchmarks show that CCGM consistently improves matching accuracy over competitive baselines.