Certified Robustness on Visual Graph Matching via Searching Optimal Smoothing Range

Deep visual graph matching (GM) is a challenging combinatorial task that involves finding a permutation matrix that indicates the correspondence between keypoints from a pair of images. Like many learning systems, empirical studies have shown that visual GM is susceptible to adversarial attacks, with reliability issues in downstream applications. To the best of our knowledge, certifying robustness for deep visual GM remains an open challenge with two main difficulties: how to handle the paired inputs together with the heavily non-linear permutation output space (especially at large scale), and how to balance the trade-off between certified robustness and matching performance.