Learning General Representations Across Graph Combinatorial Optimization Problems

We would like to express our sincere gratitude for thoroughly evaluating our paper and providing detailed and constructive feedback. We are genuinely committed to addressing your concerns and respond to your specific comments below.

W1&W4: Complexity of the framework and insufficient analysis of computational cost.

Thank you for your feedback. We have included detailed information on the training time and memory requirements in the revised PDF (in Appendix D.2). The computational cost of training CORAL is comparable to seperately training graph and SAT models.

From a conceptual standpoint, the design of our framework is clear and easy to implement. The reason we use separate models for each domain, particularly for GDPs, is that these problems often have strong dependencies on specific properties of the graphs. It is challenging to design a single, universal model that effectively captures all the necessary features across different problem domains. In order to create a model that can handle all types of problems, one would need to design domain-specific features for each problem, which requires significant expert knowledge and effort.

To resolve this challenge, our framework treats the graph problem instances as a mapping from graph to decision, allowing the neural network to automatically learn the relevant properties of the graphs needed to solve the problem. This approach eliminates the need for manually designing features for each specific problem. Thus, while each model is domain-specific, the framework unifies the problem-solving process for all domains.

W2: Limited comparison with alternative methods.

Thank you for your feedback. To the best of our knowledge, our work is the first to propose learning general representations across GDPs. During our literature review, we did not identify existing frameworks that could directly be adopted for comparison in the context of learning representations across GDPs. This uniqueness makes it challenging to compare our approach with prior works.

In our experiments, we unified the backbones used across our framework and the baseline models to ensure a fair evaluation. This allows us to isolate and verify the effectiveness of our framework, including its ability to improve accuracy and generalization compared to task-specific models.

To further strengthen the evaluation and assist in better understanding the performance of our method, we have included additional experiments in the revised PDF (in Appendix D.5, D.6, D.7, D.8, D.9).

W3: Scalability concerns with larger, real-world problem instances.

Thank you for your feedback. To address the scalability concerns, we have added a new experiment in the revised PDF. This experiment shows that models pre-trained on small, easy-to-handle instances using CORAL can be effectively generalized on large instances through fine-tuning, without the need for transformations of GDPs into SAT (in Appendix D.7.2), proving that our framework eliminates the need for transformations of GDPs into SAT representations and the training of multiple models for larger instances. The results demonstrate that our framework is scalable and can handle large-scale instances efficiently.

W5: Lack of ablation studies.

Thank you for your comment. We would like to clarify that the SAT transformation and contrastive learning are inherently interlinked in our framework. As such, it is not feasible to conduct an ablation study where these components are tested independently.

However, we do have conduct a new ablation study to validate the effectiveness of cross-domain information transfer in our framework and add it in the revised PDF (in Appendix D.9).

We hope this response could help address your concerns and wish to receive your further feedback soon.

Dear Reviewer,

This is a kind reminder that the discussion phase will be ending soon on November 26th. Please read the author responses and engage in a constructive discussion with the authors.

Thank you for your time and cooperation.

Best,

Area Chair

Dear Reviewer MBJq,

We extend our sincere appreciation for your time and the valuable insights you've provided. We are eager to ensure that our rebuttal adequately addresses all your concerns and are looking forward to engaging in a further discussion with you. Should any lingering questions persist or if further clarifications are needed, please don't hesitate to reach out.

Best regards,

The Authors

Dear Reviewer MBJq,

Thank you again for your valuable feedback on our submission. We appreciate the time and effort you’ve taken to evaluate our work.

We understand that reviewing can be a time-consuming process, and we want to kindly follow up regarding the rebuttal we submitted a week ago. If you have any further questions or need clarification from us, we would be happy to provide additional information. However, if there are no further concerns, we would kindly request that you reconsider the rating in light of the clarifications we’ve provided.

Thank you for your attention, and we look forward to hearing from you soon.

Best regards,

The Authors

We would like to express our sincere gratitude for thoroughly evaluating our paper and providing insightful and valuable feedback. We are genuinely committed to addressing your concerns and respond to your specific comments below.

Q1: What is the core difference between the method proposed in this paper and graph pre-training methods?

Thank you for your feedback. Our approach also contains pre-training on graphs. However, compared to typical graph pre-training methods, our approach does not focus on task design or the structure of the graph itself, but instead learns on a rich external representation (SAT) and relations among different tasks, thus unifying the representations learned across multiple tasks and forming higher-level representations that encapsulate the shared problem features of diverse GDP tasks.

To our understanding, the primary goal of graph pre-training is to extract informative knowledge from large-scale, unlabeled data using carefully designed pre-training (self-supervised) tasks and reduce the dependency on labeled data. For example, in graph pre-training for a GDP task, e.g., the k-clique problem, one might select self-supervised pre-training task combinations that may best align with this task, possibly including a pre-training task where the model predicts the size of the largest clique in a graph.

In contrast, the challenge with GDPs lies in the difficulty of encoding the task type itself (since it is more related to logical reasoning and each task has unique characteristics) and the weak supervision signals available. For instance, GDP instances only provide instance-level labels (e.g., a binary 0 or 1 for a graph), which is insufficient for graph models to effectively learn task-specific properties.

Our method addresses this issue by transforming all graph instances into unified SAT representations utilizing combinatorial optimization problem characteristics. The SAT representation explicitly encodes the logic of the problems, providing a rich source of information that allows the graph models to align. This alignment enables the graph models to better understand the task without requiring manually designed features or pre-training tasks, enabling the models to learn task-specific properties autonomously in a unified process. Also, aligning models for all tasks with the same SAT model enables the models to find and capture the relations among different tasks (similar to CLIP[1]) and unify the learned representations on different tasks, thereby forming higher-level representations that encapsulate the shared problem features.

[1] Radford A, Kim J W, Hallacy C, et al. Learning transferable visual models from natural language supervision[C]//International conference on machine learning. PMLR, 2021: 8748-8763.

Q2: Why using the contrastive loss to align the representation of the GDP and SAT modalities is a way to get a higher-level, abstract representation?

Thank you for your insightful question. The use of contrastive loss to align the representations of GDP and SAT modalities plays a central role in achieving a higher-level, abstract representation.

All GDP problems can be transformed into SAT representations, which reflects the fact that they share a common underlying structure. This structure can potentially be leveraged to create a unified and more efficient representation of these problems. Through contrastive loss, the representations of different GDP problems are aligned to their SAT counterparts, and we can effectively map all problem types into a shared latent space, which captures the essential commonalities between different GDP problem types and encapsulates the higher-level, abstract representation that unifies the various GDP problems.

Q3: Are there any other comparable works in the experiment?

Thank you for your feedback. To the best of our knowledge, our work is the first to propose learning general representations across GDPs. During our literature review, we did not identify existing frameworks that could directly be adopted for comparison in the context of learning representations across GDPs. This uniqueness makes it challenging to compare our approach with prior works.

In our experiments, we unified the backbones used across our framework and the baseline models to ensure a fair evaluation. This allows us to isolate and verify the effectiveness of our framework, including its ability to improve accuracy and generalization compared to task-specific models.

To further strengthen the evaluation and assist in better understanding the performance of our method, we have included additional experiments in the revised PDF (in Appendix D.5, D.6, D.7, D.8, D.9).

We hope this response could help address your concerns and wish to receive your further feedback soon.

We would like to express our sincere gratitude for thoroughly evaluating our paper and providing valuable and constructive feedback. We are genuinely committed to addressing your concerns and respond to your specific comments below.

W1: The model is limited to solving GDP problems.

Thanks for your feedback. The primary goal of our framework is to facilitate better representation learning for graph instances, which can then be applied to various downstream tasks. While the current focus of our work is on solving GDPs, the framework is not restricted to this specific task alone. By making appropriate modifications to the architecture of the output module, our approach can be adapted to solve other related tasks that are more directly aligned with practical CO problem-solving.

To address your concern, we have included additional experiments in the revised PDF where we evaluate our framework on two tasks that are related to GDPs but are more closely aligned with practical solutions to CO problems (in Appendix D.7.1). These additional tasks demonstrate the framework’s potential to generalize beyond pure GDP problem-solving.

W2: General SAT model significantly outperforms specific graph models.

Thank you for your insightful comment. The SAT model explicitly encodes the logical structure of the problem into the input representation, which provides direct features for learning. In contrast, the graph model’s input is limited to the raw graph instances without explicit features representing the problem itself. This is due to the fact that GDP problems are closely tied to specific graph properties, and designing features that are universally effective across all problems is highly challenging and requires extensive expert knowledge. Instead, we rely on the graph model to autonomously learn the graph characteristics needed to solve the problem, which inherently makes the problem-solving process more complex compared to the SAT model.

Despite the higher difficulty for the graph models, our experimental results validate the effectiveness of our framework. The consistent performance improvements across different GDPs demonstrate that the graph models can effectively learn the necessary properties for solving GDP problems through our framework.

To address your concern and further evaluate the expressiveness of the graph model, we have conducted additional experiments using two more powerful GNN backbones[1][2] (in Appendix D.5). The performance improvement is consistent regardless of the backbone model.

[1] Veličković P, Buesing L, Overlan M, et al. Pointer graph networks[J]. Advances in Neural Information Processing Systems, 2020, 33: 2232-2244.

[2] Rampášek L, Galkin M, Dwivedi V P, et al. Recipe for a general, powerful, scalable graph transformer[J]. Advances in Neural Information Processing Systems, 2022, 35: 14501-14515.

W3: Need case studies on model outputs for specific GDP and correponding SAT problems.

Thank you for your comment and suggestion. We have added case studies in the revised PDF (in Appendix B.3).

For GDP problems, the model’s output is a binary value (0 or 1) at the instance level. For example, in the case of the k-clique problem, the input is a graph, and the output indicates whether the graph contains a clique of size k. If such a clique exists, the output is 1; otherwise, it is 0.

Similarly, for the corresponding SAT problem (e.g., the k-clique problem transformed into a CNF formula), the output represents whether the formula is satisfiable. If the formula is satisfiable, the output is 1; otherwise, it is 0. The satisfiability result directly corresponds to the solution of the original GDP problem. For example, a satisfiable formula indicates that the original graph contains a clique of size k.

We hope this response could help address your concerns and wish to receive your further feedback soon.

W4.1 & Q2: The baseline model is very weak. The rationality and innovation of the model are insufficient.

Thank you for your thoughtful feedback. We would like to provide some clarifications to address your concerns.

1. For both the SAT and graph-based problems, we employed two different backbone models to demonstrate the robustness and effectiveness of our proposed framework. Importantly, the performance improvements we observe are consistent across these models, suggesting that the gains are not dependent on any specific model architecture.
2. For the SAT problems, we utilize the backbone model from G4SATBench[2], which has demonstrated high performance in SAT-based tasks. Our experimental results indicate that this model achieves close to 100% accuracy, which is a strong result, and the SAT model performance still benefits from our framework. Regarding the graph model, we adopt GCN and GraphSAGE because they are most widely used backbones in graph-based tasks. To address your concern, we also conducted experiments with the two models you referenced[3][4], which are more precise for combinatorial optimization (in Appendix D.5). The performance improvements we observed were consistent, further supporting the robustness of our framework, regardless of the specific model used.
3. We would like to emphasize that the key innovation of our work lies not in the individual models themselves but in the cross-domain optimization enabled by using SAT as a unifying bridge. This novel approach allows the models to learn higher-level representations and underlying structures shared among different domains, which we believe represents a significant contribution to the field of combinatorial optimization.

[2]Li Z, Guo J, Si X. G4satbench: Benchmarking and advancing sat solving with graph neural networks[J]. arXiv preprint arXiv:2309.16941, 2023.

[3] Veličković P, Buesing L, Overlan M, et al. Pointer graph networks[J]. Advances in Neural Information Processing Systems, 2020, 33: 2232-2244.

[4] Rampášek L, Galkin M, Dwivedi V P, et al. Recipe for a general, powerful, scalable graph transformer[J]. Advances in Neural Information Processing Systems, 2022, 35: 14501-14515.

W4.2 & Q3: Adopting different models for each domain increases the number of model parameters, affects the scalability and generalization capability to new domain problems.

Thank you for your insightful comment.

The reason we use separate models for each domain, particularly for GDPs, is that these problems often have strong dependencies on specific properties of the graphs. It is challenging to design a single, universal model that effectively captures all the necessary features across different problem domains. In order to create a model that can handle all types of problems, one would need to design domain-specific features for each problem, which requires significant expert knowledge and effort.

To solve this challenge, our framework treats the graph problem instances as a mapping from graph to decision, allowing the neural network to automatically learn the relevant properties of the graphs needed to solve the problem. This approach eliminates the need for manually designing features for each specific problem. Thus, while each model is domain-specific, the framework unifies the training and the problem-solving process for all domains.

We acknowledge that it is challenging to directly generalize the graph model to a completely new domain. However, we have added new experiments to assess the generalization ability of our graph models on related tasks (in Appendix D.7.1).

Moreover, for cross-domain generalization, the SAT model has shown significant improvements. Specifically, when we apply our pre-trained SAT model to data from unseen domains (or even transfer it to other tasks), we observe that fine-tuning the pre-trained model on this new data leads to faster convergence and higher accuracy compared to starting from scratch with a SAT model trained directly on the new domain. These results are consistent with our framework’s ability to generalize well across domains, and they demonstrate the benefits of the cross-domain transfer capability.

Q1: Justify the feasibility of constructing a cross-domain pre-training model for GDP problems based on GNN.

Thank you for your valuable comment and insightful suggestion. We would like to clarify this issue from the following points:

1. The SAT instances are represented as LCG/VCG graphs, where the logical reasoning involved in SAT problem-solving is explicitly encoded within the graph structure. This structure effectively captures the reasoning process needed to solve the SAT problem by converting the reasoning into feature learning on the graph.
2. The backbone we employed for the SAT model is specifically designed for SAT solving tasks and has demonstrated strong performance in related tasks. We add a new experiment to show that the SAT model is sensitive to minor change of the graphs (in Appendix D.8).
3. For GDPs, despite the limitations of GNN for capture such high-level features, our proposed contrastive learning framework, which align all graph models with the general, high-performance, and structure-sensitive SAT model, can effectively alleviate the limitations and enhance models' ability to handle the structural variations inherent in GDPs. We also evaluate the sensitivity of our graph models to minor change of the graphs (in Appendix D.8).

We hope this response could help address your concerns and wish to receive your further feedback soon.

We would like to express our sincere gratitude for thoroughly evaluating our paper and providing insightful and constructive feedback. We are genuinely committed to addressing your concerns and respond to your specific comments below.

W1.1: SAT is merely a format for problem representation rather than a modality.

Thank you for your valuable comment. We agree with your point that SAT can be seen as a representation format. However, we would like to clarify our use of the term "modality." In our context, we do not intend to imply that the problems are different modalities in the strict sense of the term, but rather that they represent different forms of a higher-level underlying difficulty. These instances—while rooted in SAT—can be viewed as different manifestations of a more general combinatorial optimization challenge, which is analogous to how multiple tasks in image and text domains are viewed as distinct modalities in current research. By framing these problems in this way, we hope to draw an analogy to the multi-modal models used in image and text, where the "modalities" are distinct but share a common underlying structure.

We have revised the PDF to further explain how we apply the term "modality" in this broader sense (in Sec. 3.2).

W1.2: The second claimed contribution of this paper does not hold.

Thank you for your comment. We would like to emphasize that the primary contribution of our paper is not merely about training a multi-distribution SAT model. Instead, our second key contribution focuses on using SAT as a bridge for information transfer across models from different problem domains.

By using SAT as a common format, we aim to capture a higher-level, generalizable representation that can improve the performance of solving various CO problems, rather than just converting individual instances.

W2: Not all CO problems can be transformed into SAT problems.

Thank you for your thoughtful comment. We fully acknowledge that the approach presented in our paper may not apply universally to all CO problem types. However, we would like to highlight that, of the 21 NP-complete problems identified by Karp (2010)[1], 10 are GDPs. These problems form the core of many challenges in the CO field.

Also, as mentioned in the Conclusion section of our paper, exploring additional methods to handle other types of CO problems—such as those involving continuous variables—is part of our future research agenda. We plan to extend the applicability of our framework in subsequent studies.

[1]Karp R M. Reducibility among combinatorial problems[M]. Springer Berlin Heidelberg, 2010.

W3 & Q4: The contrastive learning approach can easily generate false negatives as SAT formulas may differ structurally but be logically equivalent or share the same satisfiability status.

Thank you for your valuable feedback. We would like to provide some clarification.

1. While SAT instances can share the same satisfiability status (either satisfiable or unsatisfiable), this does not imply that these instances will have similar representations. There are only two satisfiability statuses, but the number of possible SAT instances is infinite, leading to a wide variety of structural differences within the same satisfiability status.
2. The likelihood of encountering logically equivalent SAT instances in our setup is very low. We ensure that all original graphs in the same domain have distinct structures, and the SAT instances we generate have hundreds to thousands of clauses. Logically equivalent SAT formulas are very rare in such a scale unless they are specifically constructed. Moreover, any potential issues arising from logically equivalent SAT instances would only affect training when these instances appear in the same batch. The occurrence of such situations is extremely rare and would have minimal impact.
3. We present additional experimental results to show the impact of the issue. We plot the contrastive loss curve (Figure 4), which demonstrates a smooth trajectory during training. Additionally, we have introduced a new experiment that avoid such false negative samples through filtering negative samples by their satisfiability status (in Appendix D.6). The results indicate that the impact from false negatives is minimal.

Dear Reviewer icFd,

We extend our sincere appreciation for your time and the valuable insights you've provided. We are eager to ensure that our rebuttal adequately addresses all your concerns and are looking forward to engaging in a further discussion with you. Should any lingering questions persist or if further clarifications are needed, please don't hesitate to reach out.

Best regards,

The Authors

Dear Reviewer,

This is a kind reminder that the discussion phase will be ending soon on November 26th. Please read the author responses and engage in a constructive discussion with the authors.

Thank you for your time and cooperation.

Best,

Area Chair

Dear Reviewer icFd,

Thank you again for your valuable feedback on our submission. We appreciate the time and effort you’ve taken to evaluate our work.

We understand that reviewing can be a time-consuming process, and we want to kindly follow up regarding the rebuttal we submitted a week ago. If you have any further questions or need clarification from us, we would be happy to provide additional information. However, if there are no further concerns, we would kindly request that you reconsider the rating in light of the clarifications we’ve provided.

Thank you for your attention, and we look forward to hearing from you soon.

Best regards,

The Authors