Certified Robustness on Visual Graph Matching via Searching Optimal Smoothing Range

Q2: It is advisable to conduct a comparison between the proposed method and other existing techniques for robust GM, such as ASAR[1] and COMMON [2]. Specifically, COMMON addresses robust graph matching by considering noisy correspondence during training, while ASAR takes adversarial attacks into account during training. Evaluating these methods alongside CR-OSRS would provide more comprehensive experimental insights. Furthermore, reporting the certified accuracy and average certified radius for these models is encouraged.

R2: We appreciate your valuable feedback. We have performed additional experiments based on your suggestions and further elaborated our proposed certified robustness method.

• The ASAR and COMMON methods you referred to are the recently proposed visual GM methods with relatively good results. We calculated CR (in link: https://anonymous.4open.science/r/Certified-Robustness-on-Visual-Graph-Matching-via-Searching-Optimal-Smoothing-Range-E5F0/Rebuttal/Figure/ASAR/ and https://anonymous.4open.science/r/Certified-Robustness-on-Visual-Graph-Matching-via-Searching-Optimal-Smoothing-Range-E5F0/Rebuttal/Figure/COMMON) and ACR (in table below) achieved by CR-OSRS and RS-GM on Pascal VOC under keypoint position perturbations for these two models. The results indicate that the certified robustness obtained by CR-OSRS is also superior on these two basic models. This result has been updated in the new version of the paper, please refer to Tab.1, Fig.6, Fig.7 and Appendix.E.1 in the paper.

Table: ACR achieved by CR-OSRS and RS-GM for six GM solvers on Pascal VOC under keypoint position perturbations.

• We offer more explanation on the difference between certified robustness and empirical robustness as well as the significance of CR-OSRS. The difference is that the results obtained by certified robustness are rigorously verifiable, that is, when the perturbation is within a certified range, the output is always invariant. However, empirical robustness does not have this theoretical guarantee, which means that it may have well defense capabilities against current attack methods, but it is highly susceptible to future unseen attacks. Therefore, the two types of robustness cannot be directly compared. This paper uses CR-OSRS to transform basic solvers into smoothed models with certified robustness for comparison and analysis. We also observe, in practice, that the better the matching performance of the basic model, the better the certified robustness and matching performance of the smoothed model will be. For instance, COMMON method enhances the model performance by leveraging noisy correspondence, which will make the smoothed models obtained by CR-OSRS more certifiably robust.

Q3: Since the author outlines four challenges in the Introduction, it would be beneficial to emphasize these points within the Method section, using C1 to C4.

R3: Thanks for your suggestion, which will improve the clarity of our paper. We have implemented the corresponding changes in the new version of the paper.

Q4: The choice of baseline methods and datasets in your evaluation appears somewhat dated (prior to 2021). Would it be possible to include the recent and popular Spair-71k [3] graph matching dataset in your experiments to provide more up-to-date and comprehensive results?

R4: We appreciate your suggestion, which will enhance the quality of our paper. We show the results on the dataset Spair-71k (in link: https://anonymous.4open.science/r/Certified-Robustness-on-Visual-Graph-Matching-via-Searching-Optimal-Smoothing-Range-E5F0/Rebuttal/Figure/SPair-71k). The figures show the CA achieved by CR-OSRS and RS-GM for NGMv2 on Spair-71k when perturbing keypoint positions. The figure displays the result for original $\sigma=0.5$, $s=0.9$ , $\beta=0.01$ and $n=2$. The curve of CR-OSRS is almost always above RS-GM, which implies greater certified robustness and matching accuracy. At the same time, it also illustrates that the proposed data augmentation and the regularization term are effective. This result has been updated in the new version of the paper, please refer to Fig.5 and Appendix.E.1 in the paper.

Q1: The paper lacks sufficient details regarding the implementation of the optimization algorithm for determining the optimal smoothing range, specifically the step 2 in Algorithm 1. Clarity is needed on the efficiency and scalability of this algorithm, especially in the context of larger-scale problems. Could you provide more details on the global optimization algorithm used to determine the optimal smoothing range? What is the computational complexity, and how scalable is this algorithm?

R1: Thank you for your question. We provide more details of the optimization algorithm below. We have also revised the paper accordingly, please refer to Appendix.C in the updated version for more details.

• We first elaborate on the motivation for designing the optimization algorithm. As described in Sec.4.2, we employ a smoothing distribution $\mathbf{B}$ with correlation to transform the basic GM model into a one with certified robustness. However, simply setting the values of $\mathbf{B}_1$ and $\mathbf{B}_2$ in advance may not achieve satisfactory results. Therefore, we propose to optimize $\mathbf{B}_1$ and $\mathbf{B}_2$ around the initial values to enhance the model’s certified robustness. We optimize $\sigma$ and $b$ for the dataset, irrespective of the network parameters which are kept constant here.
• Second, we describe the design rationale and implementation of the optimization algorithm. As mentioned in Sec.4.4, the proxy radius is a measure of the certified space, so our optimization algorithm aims to maximize the proxy radius on the dataset. Moreover, we enforce a constraint on $b$ in Eq.10, which is motivated by two main reasons. One is that $b$ has to be positive, since a negative b would invalidate the smoothing distribution; the other is to balance the trade-off between certified robustness and model performance. A natural solver for Eq.10 is stochastic gradient ascent with the expectation approximated by Monte Carlo samples. Thus, the gradient of the objective at the $k^{th}$ iteration can be estimated as follows:

In this work, $\underline{p}$ is estimated by the Monte Carlo sampling algorithm in the subsequent certification process, but we simplify its estimation in the optimization algorithm. Since we do not need a very precise $\underline{p}$ value here, but a favorable trend, we calculate it by sampling only once. This approach not only improves the efficiency of the optimization algorithm but also avoids the high variance in the gradient estimation caused by multiple sampling.

• In this work, we fix the number of iterations for all optimization algorithms to $K=10$, and the size of data used for optimization to 100. Therefore, the entire optimization process is relatively fast, with each optimization process taking less than 2 minutes on CPU (Intel(R) Core(TM) i7-7820X CPU @ 3.60GHz) and GPU (GTX 2080 Ti GPU). Consequently, the algorithm can be relatively easily applied to various visual GM models. We summarize the updates for optimizing by solving Eq.10 with $K$ steps of stochastic gradient ascent in Algorithm.2 in the paper, please refer to the revised version.

I appreciate the response from the authors. It would be beneficial if you could incorporate discussions on certified robustness, empirical robustness (model robustness?), and adversarial robustness (Point 2 of R2) into the paper. I'm happy to increase my rating.

Q1: In Eq. 10, the authors mentioned that a constraint on b is imposed in the optimization. However, how this constraint works is not well explained. The effectiveness of this constraint is not evaluated in the experiments. Please provide more details of the constraint in Eq. 10 as well as ablation studies.

R1: Thank you for your questions and suggestions. We will clarify the role of the constraint and its ablation study. We have also revised the paper accordingly, please refer to Appendix.C and Appendix.E.1 in the updated version for more details.

• We first explain the rationale behind the design of the optimization algorithm. As described in Sec.4.2, we employ a smoothing distribution $\mathbf{B}$ with correlation to transform the basic GM model into a one with certified robustness. However, simply setting the values of $\mathbf{B}_1$ and $\mathbf{B}_2$ in advance may not achieve satisfactory results. Therefore, we propose to optimize $\mathbf{B}_1$ and $\mathbf{B}_2$ around the initial values to enhance the model’s certified robustness. It is worthwhile to mention that we optimize $\sigma$ and $b$ on the dataset, regardless of the architecture and the training procedure of the basic model.
• As mentioned in Sec.4, the proxy radius is a measure of the certified robustness of the algorithm, so our optimization algorithm aims to maximize the proxy radius on the dataset as shown in Eq.10. Moreover, we enforce a constraint on the correlation parameter $b$, which is motivated by two main reasons. One is that $b$ has to be positive, since a negative $b$ would invalidate the smoothing distribution; the other is to balance the trade-off between certified robustness and model performance. A large $b$ may improve the matching performance but reduce the certified space.
• We have performed ablation experiments to examine the effect of parameter $\kappa$ on the certification results as in figures (https://anonymous.4open.science/r/Certified-Robustness-on-Visual-Graph-Matching-via-Searching-Optimal-Smoothing-Range-E5F0/Rebuttal/Figure/Ablation%20study%20of%20kappa/). The figures shows that $\kappa$ had little overall influence on the outcomes, but a larger $\kappa$ results in a larger $||\delta_{volume}||$ and $||\delta_{upper}||$ as well as a smaller $||\delta_{lower}||$. However, we still stress that the constraint plays a vital role in ensuring that the value of $b$ remains within a reasonable optimization range. This result has been updated in the new version of the paper, please refer to it in Appendix.E.1 and Fig.9.

Q2: The authors introduced a regularization in Eq. 11, however, the ablation study of the variant without this regularization is missing. Please provide the ablation study of the regularization in Eq. 11.

R2: Thank you for your question. We actually have presented the ablation study you referred to in Fig.2. We evaluate the certification results of RS-GM and CR-OSRS on the basic model, the model with data augmentation (AUG), and the model with data augmentation and the regularization term (AUG+REG). We also explain in Sec.5.2 that the regularization term is always related to data augmentation as shown in Eq.11. In the absence of data augmentation, the outputs corresponding to all copy data are identical and thus the regularization term is always zero. Fig.2 demonstrates that the proposed data augmentation and the regularization term are effective.

[1] Zanfir A, Sminchisescu C. Deep learning of graph matching[C]//Proceedings of the IEEE conference on computer vision and pattern recognition. 2018: 2684-2693.

[2] Wang R, Yan J, Yang X. Learning combinatorial embedding networks for deep graph matching[C]//Proceedings of the IEEE/CVF international conference on computer vision. 2019: 3056-3065.

[3] Yu T, Wang R, Yan J, et al. Learning deep graph matching with channel-independent embedding and hungarian attention[C]//International conference on learning representations. 2019.

[4] Wang R, Yan J, Yang X. Neural graph matching network: Learning lawler’s quadratic assignment problem with extension to hypergraph and multiple-graph matching[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021, 44(9): 5261-5279.

[5] Ren Q, Bao Q, Wang R, et al. Appearance and structure aware robust deep visual graph matching: Attack, defense and beyond[C]//Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2022: 15263-15272.

[6] Lin Y, Yang M, Yu J, et al. Graph matching with bi-level noisy correspondence[C]//Proceedings of the IEEE/CVF International Conference on Computer Vision. 2023: 23362-23371.

[7] Cohen J, Rosenfeld E, Kolter Z. Certified adversarial robustness via randomized smoothing[C]//international conference on machine learning. PMLR, 2019: 1310-1320.

[8] Levine A J, Feizi S. Improved, deterministic smoothing for L_1 certified robustness[C]//International Conference on Machine Learning. PMLR, 2021: 6254-6264.

[9] Chiang P, Curry M, Abdelkader A, et al. Detection as regression: Certified object detection with median smoothing[J]. Advances in Neural Information Processing Systems, 2020, 33: 1275-1286.

[10] Fischer M, Baader M, Vechev M. Scalable certified segmentation via randomized smoothing[C]//International Conference on Machine Learning. PMLR, 2021: 3340-3351.

[11] Jia J, Wang B, Cao X, et al. Certified robustness of community detection against adversarial structural perturbation via randomized smoothing[C]//Proceedings of The Web Conference 2020. 2020: 2718-2724.

[12] Lu H, Li Z, Wang R, et al. ROCO: A General Framework for Evaluating Robustness of Combinatorial Optimization Solvers on Graphs[C]//The Eleventh International Conference on Learning Representations. 2022.

W1/Q2: The presentation can be improved for better clarity, as it involves multiple areas ranging from graph matching (combinatorial optimization), robustness certification, visual recognition, etc. Can you add a table or figure to summarize and compare related methods from multiple aspects for better accessibility of readers?

R1: We appreciate your insightful suggestions. Our research draws on knowledge from multiple fields, and we aim to present and compare them more rigorously and clarify their relevance to this study according to your suggestions. We show the comparison of visual GM methods and certified robustness methods in Tab.1 and Tab.2 below. We have also revised the paper accordingly, please refer to Appendix.B in the updated version for more details.

• First, we provide a brief introduction to visual Graph Matching(GM). GM is a fundamental problem in combinatorial optimization that involves identifying node correspondences between graphs. As introduced in Sec.3, deep visual GM deals with images with keypoints as inputs and solves in an end-to-end manner. Visual GM consists of three components: keypoint feature extractor, affinity learning, and final correspondence solver. We introduce and compare the main visual GM methods used in this work in Tab.1 below, which we have added to the paper, please refer to Appendix.B for more details.

Table 1: Summary of main existing literature in learning GM.

• Second, we introduce the concept and methods of certified robustness, which aims to design solvers that can verify the consistency of their prediction for any input within a certified perturbation range. As discussed in Sec.2, various methods have been proposed to achieve certified robustness, but only the Randomized Smoothing (RS) class of methods can scale up to large models and ImageNet-level datasets. We present some of the representative RS-based methods in Tab.2, along with their applicable scenarios and features. We have added the comparison to the paper, please refer to Appendix.B in the updated version for more details. As analyzed in Sec.1, none of these methods can be directly applied to visual GM. Therefore, we propose the CR-OSRS method, which can transform any basic visual GM model (described in Tab.1) into a model with certified robustness.

Table 2: Summary of main existing literature in RS-type methods for robustness certification.

• Third, this work concentrates on the performance of the visual GM model, which only requires visual feature extraction, and not visual recognition. Visual recognition is beyond the scope of this work, so the visual recognition model will not be evaluated and discussed.

W2/Q1: The paper lacks some discussion for enlarging its potential impact to other combinatorial tasks or any limitation and difficulty to extend its adaption to other tasks. Have you explored the possibility of extending your approach to address problems beyond graph matching? Given the ubiquity of combinatorial optimization on graphs, a discussion on a potentially more general framework could be beneficial.

R2: We appreciate your valuable suggestions. Below we will discuss the challenges of extending certified robustness research to general combinatorial optimization (CO) problems. Then we will introduce the particularities of the visual graph matching (GM) problem that this work focuses on and its advancement for the general issue.

• First, we emphasize that robustness certification aims to provide a mathematical guarantee that the model output is bounded by a certain region when the input is slightly modified. We share your interest in developing a provably robust method that can be applied to a broader range of CO problems. However, we encounter several challenges in this direction. First, different CO problems may have different input and output formats. Therefore, it is necessary to devise a way to unify the diverse input and output formats. For instance, many CO problems can be represented as graph input forms, but there is no standard and unified format for the outputs, to the best of our knowledge. One possible solution is to use a general structured data format to unify the outputs. After unifying the input and output formats, we can design a general robustness certification method. Second, there is currently a lack of sufficient research on the robustness certification of complex models that take graphs as inputs and structured data as outputs. Most of the existing work can only handle simple classification problems. Third, we need to define the notion of certified robustness for CO problems clearly. The paper [12] proposes a heuristic robustness criterion for CO problems, but it does not guarantee the certified robustness of the model.
• Second, visual GM, as a special case of CO, has a distinctive input and output format, as described in Sec.1. The input consists of pairs of images and their corresponding keypoints, and the output is a matching matrix that indicates the correspondence between the keypoints. To address this task, we propose a novel method that designs a randomized smoothing distribution with correlation constraints and a subspace partitioning. This not only provides a theoretical guarantee for the robustness of visual GM, but also preserves the model performance and the rationality of the verification. In addition, we define the certified robustness of visual GM as the condition that when the perturbation is within the certified input space, the smoothed model always predicts the output within the output subspace. These address the above-mentioned challenges of CO robustness certification in the visual GM problem. Our work has implications for the robustness certification of general CO problems. Particularly, our method provides an effective solution for processing matrix output, which is also a special kind of structured data; our proposal of joint smoothing distribution may also be beneficial in inspiring the processing of constrained input formats in many CO problems; the data augmentation and the regularization term may suggest a similar approach to balancing certified robustness and model performance for general CO problems. However, the unification of input and output formats, the certification methods for complex graph tasks, and the reasonable certified robustness definitions are still pending to be solved.
• In conclusion, we attempt to solve a special case of the robustness certification problem for CO in this paper. We are working on addressing the challenges for general CO certification and will share our findings in the future.