BiQAP: Neural Bi-level Optimization-based Framework for Solving Quadratic Assignment Problems

Q1: "The implicit optimization problem appears crucial, as described by the author in lines 280-285 (290-295 in revised version). Including a baseline where FormulaNet produces an optimal transportation problem could provide a more robust validation and enhance readers' understanding."

A1. Thank you for your reminder. We will discuss the implicit optimization further in our paper, which actually serves as the inner optimization in our framework. In fact, as discussed in [1,2], many layers (e.g., Softmax, tanh, Sigmoid, Sinkhorn) can be understood as solving operators for their implicit optimization, and many papers have attempted to improve learning by designing and solving these implicit optimizations. (We provide an example with Softmax in the related work section of the updated version) When the layer is used as the final network layer for output, the entire learning process can be viewed as solving the implicit optimization based on the features derived from the neural network. From this perspective, the work of NGM [3] using Sinkhorn activation essentially solves an entropically regularized transport problem:

$$\min_{\mathbf{X1}=\mathbf{1},\mathbf{X^\top1}=\mathbf{1}} \langle \mathbf{C}^\theta,\mathbf{X} \rangle- \epsilon H(\mathbf{X}) \qquad (a)$$

where $\mathbf{C}^\theta$ represents the cosine distance learned from the neural network. In contrast, we employ a more complex implicit optimization as the inner optimization:

$$\min_{\mathbf{X}} -\text{tr}(\mathbf{X}^\top\mathbf{F}_1^{\theta}\mathbf{X}\mathbf{F}_2^{\theta})-\text{tr}({\mathbf{K}_p^{\theta}}^\top\mathbf{X})-\epsilon H(\mathbf{X}), \qquad (b)$$ $$\text{ s.t. }\mathbf{X1}=\mathbf{1},\mathbf{X}^{\top}\mathbf{1}\leq\mathbf{1}$$

Since the QAP problem we are solving (see Eq. 2) typically has a non-convex objective, the convex optimization objective in Eq. (a) may be too simple, limiting its ability to fit Eq. 2, thus resulting in suboptimal performance. In this paper, instead of the entropic optimal transportation objective, we employ a more complex non-convex optimization, i.e., the entropic QAP, which better approximates the objective of QAP. Of course, using other more complex optimization problems to approximate QAP or other combinatorial optimization objectives could yield better results, which is an area of further research for us.

[1] Regularized Optimal Transport Layers for Generalized Global Pooling Operations. TPAMI, 2023.

[2] Implicit deep learning. SIAM Journal on Mathematics of Data Science 3.3 (2021): 930-958.

[3] Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching. TPAMI, 2021.

Q2: "The author should clarify the choice of randomly generated datasets over publicly available ones, as the latter might be more convincing."

A2. Yes, we should indeed clarify the origins of the datasets we use, specifying whether they are publicly available real datasets, publicly available generated datasets, or datasets we generated ourselves:

• The graph matching datasets mentioned in [2] are publicly available; however, as explained in lines 63–72 of our paper, "the ground-truth matching in supervised data may not necessarily be the optimal solution in the context of QAP optimization." Therefore, we cannot use visual graph matching datasets, which may contain errors for QAP optimization. Following the approach in [1] and [2], we conduct QAP-based graph matching experiments. While these papers provide methods for generating QAP-based graph matching datasets, they do not release the datasets. As a result, we followed the methods in [1] and [2] to generate our own graph matching datasets.

• The Graph Edit Distance (GED) datasets are publicly available, real datasets that have been used in previous works such as [3] and [4].

• The Large Random Datasets (L500/750/1000) are generated datasets containing extremely large instances, created specifically to evaluate the capability of our model. To our knowledge, no publicly available datasets of this size currently exist, so we generate them ourselves.

• QAPLIB ([2], [5]) is a publicly available real dataset.

• The Traveling Salesman Problem (TSP) datasets are publicly available generated datasets, and we use the same generation code in [1] and [6].

[1] Towards Quantum Machine Learning for Constrained Combinatorial Optimization: a Quantum QAP Solver. ICML, 2023.

[2] Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching. TPAMI, 2021.

[3] Computing Graph Edit Distance via Neural Graph Matching. VLDB, 2023.

[4] Noah: Neural-optimized A* Search Algorithm for Graph Edit Distance Computation. ICDE, 2021.

[5] QAPLIB - A Quadratic Assignment Problem Library - Problem instances and solutions.

[6] The Transformer Network for the Traveling Salesman Problem.

Dear Reviewer,

Thank you for your valuable response. As the discussion deadline approaches, we kindly request your feedback of our response to the concerns you previously raised. We are also open to any further questions or suggestions that you may have.

We sincerely appreciate your time and attention. Your guidance is truly invaluable to our research.

Best regards,

The Authors

Q1: "What is the theoretical justification for using Gumbel noise to sample the initial $X^{(0)}$?"

A1. The choice of sampling method has little impact on the relationships in our QAP solver. Our goal is to ensure that various initializations of the latent space consistently move toward minimizing the loss. Inspired by the application of Gumbel sampling in the Sinkhorn algorithm (Gumbel Sinkhorn, [1]), we adopt Gumbel sampling within our framework. Notably, the first outer iteration in our QAP solver can be viewed as a Gumbel Sinkhorn step, which motivates our choice of Gumbel sampling.

Additionally, we have tested alternative initialization methods, such as Gaussian sampling and uniform sampling. The experimental results on Graph Matching dataset GM-I are as follows:

We observe that these sampling strategies have almost no significant effect on the final performance of the model. Thus, we select gumbel sampling as the initialization method.

[1] Learning Latent Permutations with Gumbel-Sinkhorn Networks. ICLR 2018.

Q2: "I assume the time measurements in the tables and plots are given in seconds? Unless I missed it, this information should be added in."

A2. Yes, the time measurements are indeed in seconds. This is clarified in Section 4.1, "Evaluation" paragraph, where we state: "Time(sec/100it) is the average time taken to solve 100 instances." This explanation indicates that all subsequent time measurements represent the time required to solve 100 instances in seconds.

However, as this clarification appears only once, readers might overlook it. To address this, we will include additional explanations in the revised version to ensure clarity and prevent any misunderstanding.

Q3: "The paper lacks theoretical analysis of the bi-level optimization problem formulation (3) (Eq. 4 in revised version)."

A3. Thank you for your suggestion. We have further expanded the discussion on bi-level optimization in the updated version of our paper. Specifically, our bi-level optimization is essentially a loss design used for learning QAP. In the inner optimization, we first input the original QAP parameters $\mathbf{F}_1, \mathbf{F}_2,$ and $\mathbf{K}_p$ into the neural network, to obtain a new entropic regularized QAP with parameters $\mathbf{F}_1^{\theta}, \mathbf{F}_2^{\theta},$ and $\mathbf{K}_p^{\theta}$ ：

$$\min_{\mathbf{X}} -\text{tr}(\mathbf{X}^\top\mathbf{F}_1^{\theta}\mathbf{X}\mathbf{F}_2^{\theta})-\text{tr}({\mathbf{K}_p^{\theta}}^\top\mathbf{X})-\epsilon H(\mathbf{X}),$$ $$\text{ s.t. }\mathbf{X1}=\mathbf{1},\mathbf{X}^{\top}\mathbf{1}\leq\mathbf{1}$$

This optimization is the inner optimization in Eq. 3 (Eq. 4 in revised version), where the Gromov-Sinkhorn algorithm (see Algorithm 1) is applied as a differentiable solver to solve the new entropic regularized QAP and obtain the solution $\mathbf{X}^\theta$. Note that the differentiable solver acts as an activation layer similar to softmax or Sinkhorn, allowing gradient backpropagation. Finally, given the calculated solution $\mathbf{X}^\theta$, we minimize the negative objective of the original QAP in the outer optimization, which serves as the loss function:

$$\min_\theta -\text{tr}\big(({\mathbf{X}^{\theta}})^\top\mathbf{F}_1\mathbf{X}^{\theta}\mathbf{F}_2\big)-\text{tr}(\mathbf{K}_p^\top\mathbf{X}^{\theta})$$

Certainly, the real learning process involves the random sampling of the inner optimization, which we will not discuss further. For more specific details, please refer to Section 3.2.

Q4: "Especially figure 1 seems misleading, because using QAP for visual keypoint matching is not what is done in this work, instead machine learning is used to improve the QAP solving itself. The presentation could be improved here."

A4. No, Figure 1 is crucial as it highlights the distinction between our work and previous graph matching approaches ([1], [2], [3]), while also clarifying why we do not directly compare our method with these works. Through an example, Figure 1 demonstrates that the ground truth matching in graph matching studies may result in a lower objective value, whereas visually incorrect matches obtained via Gurobi can achieve a higher objective value. As a result, visual graph matching differs significantly from solving QAP in combinatorial optimization.

For a detailed explanation, please refer to lines 63–72 of our paper.

[1] Graph-Context Attention Networks for Size-Varied Deep Graph Matching. CVPR, 2022.

[2] Deep Learning of Partial Graph Matching via Differentiable Top-K. CVPR, 2023.

[3] Learning deep graph matching with channel-independent embedding and Hungarian attention. ICLR, 2020.

Dear Reviewer,

Thank you for your valuable response. As the discussion deadline approaches, we kindly request your feedback of our response to the concerns you previously raised. We are also open to any further questions or suggestions that you may have.

We sincerely appreciate your time and attention. Your guidance is truly invaluable to our research.

Best regards,

The Authors

Thank you for providing a thorough answer to my review. The additional experimental results resolve my corresponding concerns and will make a good addition to the manuscript.

Regarding Q4 I still have a followup question. As I understand, the point the authors want to make is that visual graph matching focuses on learning the feature extraction, whereas QAP in combinatorial optimization focuses on solving individual difficult instances.

I am not convinced that Figure 1 serves this purpose well, but if you really want to use it to make this point, I think you should at least explicitly state somewhere that the mismatch in Fig. 1 is a consequence of the particular choice of weighted adjacency matrix (is it euclidean distance in the particular example?), whereas in visual graph matching the weights would be given as the output of a learnable model that gets the visual features as input.

Q1: "In the numerical experiments, are the numbers of outer and inner iterations different for training and testing? If so, how crucial is this for the performance of the BiQAP?"

A1. Yes, it is different. As illustrated in Section 4.1, "Training Setup" paragraph, "The number of outer and inner iterations is set to 10 and 15 during training, and 20 and 25 during testing." This configuration is based on experimental findings, which show several advantages of using fewer iterations during training and slightly more during testing:

• During training, fewer iterations mitigate numerical issues such as gradient vanishing and explosion, which may occur in practical training scenarios with large iteration counts. Moreover, smaller iteration counts reduce the forward computation time of our differentiable QAP solver, enhancing training efficiency. But excessively small iterations may compromise the accuracy of the QAP solver. Based on these considerations, 10 and 15 are chosen for the outer and inner iterations, respectively.

• During testing, increasing the iteration count compared to training often yields better results. In Appendix B and Table 7 of our paper, we conduct an ablation study comparing different settings for outer/inner iterations: 10/15, 20/25, and 30/35. The results indicate that the configuration of 20/25 achieves superior performance compared to the other two settings. Nevertheless, the performance differences among these results remain minimal.

Overall, within a certain range, variations in outer and inner iteration counts have limited impact on the overall results.

Q2: "Numerous existing studies focus on algorithms for solving bilevel optimization models. How does the proposed BiQAP framework relate to these studies, and could insights from this literature potentially enhance the BiQAP framework?"

Q3: "The paper lacks a review of relevant literature on bilevel optimization, as well as a discussion on why the bilevel optimization model in Eq. 3 (Eq. 4 in revised version) is preferable to directly solving the original QAP."

A2-A3. Thank you for pointing out the shortcomings in our paper. In the updated version, we have added a discussion on the application of bi-level optimization in deep learning. Here, we briefly introduce the main idea we followed, which is based on bi-level optimization to design the loss function. This forms the basis of our preparation for answering Q4.

We mainly follow [1] that understanding or designing the loss via bi-level optimization:

$$\min_\theta KL({Y}\mid P^\theta), s.t. {P}^\theta = \arg \min_{P1=1} \langle {C}^\theta,{P} \rangle- \epsilon H({P})$$

where ${C}^\theta$ represents the cosine distance for the batch features with parameters $\theta$, and ${Y}$ is the known supervision for learning. As proven in [1], $H({P}) = -\langle{P}, \log {P} - {1}\rangle$ is the entropic regularization with coefficient $\epsilon$. The inner optimization is exactly equivalent to the softmax activation, while the outer optimization corresponds to cross-entropy. Thus we can find the above bi-level optimization equals to InfoNCE loss:

$$\min_\theta \mathcal{L} = \sum_{i,j}Y_{ij}\log (\frac{e^{-C^\theta_{ij}/\epsilon}}{\sum_{k}e^{-C^\theta_{ik}/\epsilon}})$$

Thus, bi-level optimization is fundamentally a method for designing activation layers or loss functions. In [1,2], modifications to the inner optimization improve the loss. Our work follows this learning framework, but we modify the inner optimization to use an entropic QAP, solving it with the Gromov-Sinkhorn algorithm to obtain the predicted probability matching matrix. The outer optimization is adjusted to use the original QAP objective as the loss, resulting in an unsupervised learning framework.

[1] Understanding and generalizing contrastive learning from the inverse optimal transport perspective. ICML2023.

[2] OT-CLIP: Understanding and generalizing clip via optimal transport. ICML2024.

Dear Reviewer,

Thank you for your valuable response. As the discussion deadline approaches, we kindly request your feedback of our response to the concerns you previously raised. We are also open to any further questions or suggestions that you may have.

We sincerely appreciate your time and attention. Your guidance is truly invaluable to our research.

Best regards,

The Authors

Dear Reviewer UsqU,

Thank you for your time and effort! Regarding your concern about the clarity of our theoretical explanation, we would like to reiterate the following points:

• In the above response and A2-A4, we have provided a detailed explanation of "the relationship between the QAP and bilevel optimization" and introduced related work to help readers better understand the context of our approach. This part has been updated in our revised version.
• We would like to emphasize that we have provided a formal proof of Eq. 6, i.e., the inner optimization, in Appendix D (Appendix C of the original version).
• Similarly, in the above response and A2-A5, we have explained from multiple angles "why the bilevel optimization model enhances the performance of the proposed method."

We believe that our theoretical explanation is clear, and we have sufficiently demonstrated the effectiveness of our bilevel framework.

We kindly ask you to reconsider our response and the revised version of the paper. If you still feel that our theoretical explanation is lacking or if there are any misunderstandings, we would appreciate it if you could raise specific questions, and we would be happy to discuss them with you.

Once again, thank you for your time and valuable insights!