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

Authors: Liangliang Shi, Haoran Zhang, Shuheng Shen, Changhua Meng, Weiqiang Wang, Junchi Yan
Primary area: other topics in machine learning (i.e., none of the above)
Keywords: Quadratic Assignment Problems, Entropic Regularization, Differential Gromov-Wasserstein Solver, Unsupervised Learning

Abstract:
Quadratic Assignment Problem (QAP) has attracted lasting attention for its wide applications and computational challenge. Despite the rich literature in machine learning for QAP, most works often address the problem in the setting of image matching, whereby deep networks could play a vital role in extracting useful features for the subsequent matching. While its power on pure numerical QAP instances is limited in node embedding, often with a vanilla graph neural network. This paper tries to tap the potential of deep nets for QAP, specifically by modifying the input instance which is orthogonal to previous efforts. Specifically, we develop a bi-level  unsupervised framework, where the inner optimization involves trying to solve the modified instance with entropic regularization that can be solved iteratively using the Sinkhorn algorithm without affecting backpropagation by truncating gradients during training. The outer minimization deals with the quadratic objective function of the original QAP. In particular, seeing the intractable scale of the most general form i.e. Lawler's QAP and the practical utility of the more efficient Koopmans-Beckmann QAP (KBQAP) form for solving other graph and combinatorial problems like TSP and graph edit distance, we embody our network on the KBQAP, and show its strong performance on various benchmarks in our experiments. Source code will be made publicly available.

Decision: reject
Reviewer scores: 5, 6, 6

Reviews and discussion:
<thread>
creation date:
1730279621029

thread_type:
official_review

<thread_object>
creator: reviewer_wmps

<content>
summary:
This paper presents an unsupervised learning approach to solve QAPs. The proposed method includes two main components: a "FormulaNet" that generates a new QAP and a differentiable solver utilizing the Sinkhorn algorithm to solve this generated QAP. Experimental results show certain advantages over the baseline methods.

strengths:
1. The paper is well-written, with a logical flow.
2. Unlike existing graph-matching methods, which use optimal transportation as the implicit optimization problem, the proposed approach aims to solve a new QAP. This is novel.
3. Extensive experiments are conducted, covering different types of QAPs and various exsting baseline methods.

weaknesses:
I don't see any major weaknesses, but a few improvements could enhance this paper:

1. The implicit optimization problem appears crucial, as described by the author in lines 280-285. Including a baseline where FormulaNet produces an optimal transportation problem could provide a more robust validation and enhance readers' understanding.
2. The author should clarify the choice of randomly generated datasets over publicly available ones, as the latter might be more convincing.

questions:
See weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730537626752

thread_type:
official_review

<thread_object>
creator: reviewer_l8oe

<content>
summary:
This paper proposes BiQAP, a procedure for solving Koopmans-Beckmann Quadratic Assignment Problems. The method formulates a bi-level optimization procedure, where the inner problem solves an entropy-regularized QAP. The problem data of the inner problem is predicted from the original problem data using a sequence to sequence neural network that is invariant to the size of the involved matrices. This neural network can be trained in an unsupervised manner, which removes the need for access to expensive gold solutions. The inner problem is solved with a differentiable approximate Gromov-Wasserstein Sinkhorn solver.
The method is tested on a wide set of experimental setups, including synthetically generated graph matching instances and more realistic graph edit distance (formulated as QAP) and QAP instances. Throughout the extensive evaluation, BiQAP produces strong results both in terms of achieved objective values of the computed solution as well as the required computation time, outperforming all of the other compared methods.

strengths:
- The paper has a thorough experimental evaluation with strong results, and substantially advances the state of the art in multiple experimental setups.
- The experimental setup and evaluation are well-described and easy to follow.
- The approach taken (bi-level problem with entropy-regularized inner problem on predicted parameters) seems more widely applicable and could serve as a new paradigm in solving difficult non-convex and combinatorial problems.

weaknesses:
- The paper lacks theoretical analysis of the bi-level optimization problem formulation (3).
- In the first part of the paper, I found the language used often imprecise and a bit confusing. 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.
- The ablation study on the number of samples in Fig 3 shows that in this setting the results are not very sensitive to this hyperparameter. This hyperparameter will be important for a practitioner so this ablation study should be repeated on a different experiment where it potentially makes a difference, e.g. on the GED experiment.
- The regularization strength $\epsilon$ of the inner problem is most likely an important hyperparameter (affecting the inner solution and its differentiation), it should be discussed and experimentally tested. What happens when it is set to very large or very small values?
- No ablation for different architectures of the FormulaNet is included. It would be important to see how the SSM compares to GNN or Transformer-based architectures.

questions:
- What is the theoretical justification for using Gumbel noise to sample the initial $X^{(0)}$?
- I assume the time measurements in the tables and plots are given in seconds? Unless I missed it, this information should be added in.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730563407028

thread_type:
official_review

<thread_object>
creator: reviewer_usqu

<content>
summary:
This paper proposes an unsupervised learning framework, BiQAP, based on a bilevel optimization model, to solve the Koopmans-Beckmann Quadratic Assignment Problem (KBQAP). In this framework, the outer level objective corresponds to the original QAP objective, while the inner level is a differentiable Gromov-Sinkhorn QAP solver applied to new QAP instances generated by a neural network, FormulaNet. FormulaNet is trained by minimizing the original QAP objective. Extensive experiments across five tasks demonstrate its effectiveness and efficiency compared to both non-learning and learning-based methods.

strengths:
1. The bilevel optimization formulation used to design an unsupervised learning framework for solving KBQAP is novel, contributing to a clearer understanding of the proposed framework's methodology.

2. The comprehensive experimental results highlight the notable effectiveness and efficiency of BiQAP in comparison to existing methods.

weaknesses:
1. The core concept behind the proposed BiQAP framework appears counterintuitive. If understood correctly, the primary idea is to train a neural network that takes the original QAP instance as input and outputs a modified QAP instance. This network is trained so that, when the Gromov-Sinkhorn algorithm is applied to the generated QAP instance, the resulting solution yields a lower objective value for the original QAP. However, it is unclear why solving a modified QAP instance should yield better results than directly solving the original QAP. No discussion, theoretical analysis, or explanation is provided to justify why this approach would be effective for solving the KBQAP.

2. Although the proposed BiQAP framework is based on a bilevel optimization model, 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 is preferable to directly solving the original QAP.

3. This work presents a practical method but lacks theoretical analysis or discussion. For example, it does not clarify the relationship between the bilevel optimization model in Eq. 3 and the original QAP, nor does it discuss whether the solution to Eq. 3 can approximate or recover a solution to the original QAP. Additionally, the paper does not establish any properties or guarantees regarding the quality of outputs generated by the proposed BiQAP framework.

questions:
1. 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?

2. 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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732169986035

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Paper Update and Reminder

comment:
Dear Area Chair and Reviewers,

We have updated our revised PDF based on the reviewers' suggestions, with specific changes highlighted in blue. The updates we made are as follows:

- **(Reviewer UsqU, L8oe and WMpS)** To better explain the design of our bi-level framework and implicit optimization, we added related work on bi-level optimization for softmax/InfoNCE. Additionally, we elaborated on the design of our proposed bi-level framework in Section 3.1, incorporating this related work to enhance clarity for readers.
- **(Reviewer L8oe)** As mentioned in our response, we have conducted additional experiments on sampling tests.
- **(Reviewer L8oe)** Since our time metric in seconds was mentioned only once in Section 4.1 ("Evaluation" paragraph), it was easy for readers to overlook. To address this, we updated all table labels to "Time(s)" to avoid confusion.
- Minor formatting adjustments were made to improve the paper's layout.

We have addressed all comments from the reviewers and **look forward to further discussions with each reviewer**.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732885729681

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
Dear PCs, SACs, ACs,

We sincerely thank all the reviewers for their valuable insights and feedback, which have significantly helped us improve our work. We have addressed each reviewer's concerns and believe we have effectively resolved most of them, receiving positive acknowledgments in return. As the author-reviewer discussion phase comes to a close, we would like to provide a general summary of the reviews and outline the efforts we have made during the discussion phase.

---

## **Reviewer Acknowledgments**

- Our bilevel optimization framework for solving KBQAP is novel and applicable (Reviewers UsqU, WMpS), offering a new paradigm for tackling non-convex and combinatorial problems (Reviewers L8oe).
- The experiments are comprehensive and demonstrate the notable effectiveness and efficiency of our approach (Reviewers UsqU, L8oe, WMpS).
- Our paper is well-structured, logical, and easy to follow (Reviewers L8oe, WMpS).

---

## **Issues Addressed in the Rebuttal**

- **Reviewer UsqU (Rating: 5)**:  
  - We clearly explained the impact of the number of outer and inner iterations (A1) and why our approach achieves strong performance from multiple perspectives (A5).
  - We added relevant works on Softmax/InfoNCE to clarify the loss design and its derivation within our bilevel framework (A2-A3). We also strengthened the theoretical explanation of the relationship between our bilevel framework and the original QAP (A4). We revised the paper based on A2-A4 to improve clarity.   
  - We greatly appreciate Reviewer UsqU's questions, which have helped us clarify our work. However, despite our thorough explanations, the reviewer still finds the relationship between QAP and bilevel optimization unclear (Q4), as well as the reasons why our model enhances performance (Q5), without providing specific points to highlight any shortcomings in our response. **We believe there may be a misunderstanding and would appreciate it if the reviewer could point out specific areas where our response was insufficient.** In our subsequent responses, we provided clearer and more concise explanations and are happy to engage in further discussion. However, no follow-up was provided by the reviewer.

- **Reviewer L8oe (Rating: 6)**:  
    - We addressed concerns related to Gumbel initialization (A1) and provided minor clarifications (A2). Additionally, we included a theoretical analysis of the bilevel framework (A3) and expanded our sampling tests/analysis (A5). We also clarified the role and effect of the parameter $\epsilon$ (A6) and explained the selection of FormulaNet (A7).
    - Regarding A4 (the explanation of related work on visual graph matching), the reviewer provided valuable insights. After a thorough discussion, reviewer L8oe stated that while there is still room for improvement, the response was acknowledged, and the reviewer confirmed that "this will make the takeaway of the figure clearer."
    - Overall, we believe our rebuttal addressed most of the concerns raised by Reviewer L8oe, and we greatly appreciate the valuable feedback.

- **Reviewer WMpS (Rating: 6)**:  
  
    - We provided a clearer explanation of the implicit optimization problem as requested by Reviewer WMpS. The reviewer acknowledged our clarifications, and we appreciate the reviewer's positive feedback.

---

## **Brief Summary of Our Paper**

Our paper introduces a **novel unsupervised bilevel framework** for solving the general KBQAP problem, applicable to **various combinatorial optimization tasks**. Comprehensive experiments demonstrate **strong results**, with state-of-the-art performance across multiple datasets. Our approach represents a conceptual shift, transforming multiple tasks into the KBQAP formula and optimizing it from a unified perspective. To our best knowledge, this is **the first work to optimize the KBQAP formula on these tasks**. Our success motivates us to explore similar optimization strategies for other problems, such as integer linear programming. We have also provided the code in the supplementary materials.

Best regards,

The Authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
The Quadratic Assignment Problem (QAP) is a computationally challenging problem with applications in areas like image matching. This paper addresses the Koopmans-Beckmann Quadratic Assignment Problem (KBQAP), and it proposed a bi-level unsupervised framework that modifies the input instance with entropic regularization, allowing for iterative solution using the Sinkhorn algorithm while preserving backpropagation.  The outer-level objective aligns with the original QAP objective, while the inner-level involves a differentiable Gromov-Sinkhorn QAP solver applied to new QAP instances generated by FormulaNet. Experimental results suggest that the new method BiQAP is effective on various benchmarks.

This paper addresses an important problem and is overall well written.  The empirical results are also promising.  However, more theoretical discussions are needed to motivate, justify, and support the bilevel optimization approach.  So far, there is little theoretical analysis, leaving it difficult to conclude the effectiveness of BiQAP.