- Rating
- 4
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This work proposes a novel generative model for synthesizing hard UNSAT problems by masking non-core clauses in seed-instances and then training a variational graph autoencoder to generate new clauses to replace the masked ones.
Critical strengths
- The paper is exceptionally clear
- The paper's experimental procedure is generally in line with the previous work in the field
- The paper cites the appropriate related and previous work
Critical weaknesses
1.Some experimental details are left out 2. I don't think that its necessary to invoke hyper graphs for this work, the graph representation used is bi-partite, and the methodology seems to effectively build node-representations for the "hyper-edges" as well as for the literal nodes. 3. There are a couple experiments which might have enriched the paper.
The experimental clarifications I have asked for in the questions section should be simple enough to provide. I am assuming that no deal-breakers will come to light as the authors provide that information (and that they will indeed provide the asked for information). Given this assumption, I am rating this work as a clear accept. Of course, if these things are not provided the rating will necessarily decrease.
Questions for authors
Clarifications:
- What is the difference between your proposed graph-representation, which you call a hyper-graph, and the standard literal-clause graph used by a lot of the previous work you reference? While this may be a nitpick, it seems unnecessary to invoke hyper-graphs when the underlying representation is no different than the standard. As you say in line 186, H is the clause-literal graph. For example, “we construct a corrupted hypergraph G by masking the incidence pattern of selected clause hyperedges” would be more simply expressed as “we construct a corrupted graph G by masking out clauses”, which would just as aptly describe your procedure.
- How many distinct instances are in MDP and MP1 and MDP-Large?
- Table 1 - MP1 results: You indicate that 125% Avg. RH is better than 108.77%. Is this really the case? Presumably the goal is to generate instances which are as realistic as possible relative to the target distribution, as measured by hardness. Meaning that 100% is the ideal.
- How many instances were generated for augmentation in the downstream task experiment? Did you set a fixed computation budget, or a universal raw instance-count? When you do augmentation, do you only use training-instances as seeds for your generation procedure?
Nice-to-see new experiments I would ask for: 5. It would be nice to see sensitivity of performance improvement to the size of the augmentation set for Table 3. 6. It would be nice to see solver-specific hardness stats, or metrics on the solver-runtime-ranking distribution of your synthetic vs original datasets. 7. It would be nice to see mean/variance statistics on your rarity-predictor. Interpretable statistics for the membership predictor may be more complicated to present, but would also be nice.
6 comments
Response by Authors (2/2)
Q4: How many instances were generated for augmentation in the downstream task experiment? Did you set a fixed computation budget, or a universal raw instance-count? When you do augmentation, do you only use training-instances as seeds for your generation procedure?
- We generate 40 instances for augmentation in the downstream task experiment.
- We set a universal raw instance-count. All augmentation methods use the same number of generated instances.
- Data augmentation is performed only on the original instances in the training set, which serve as seeds for our generation procedure. Validation and test instances are never used as seeds or for data augmentation, and are kept separate from the training process.
We have added these details to Appendix B.2 of the revised manuscript to clarify the experimental setup.
Q5: It would be nice to see sensitivity of performance improvement to the size of the augmentation set for Table 3.
We have added a sensitivity analysis about the performance improvement to the size of the augmentation set. The results are in Table 1.
Table 1: Sensitivity of HyperGEN to augmentation set size on MP1. Training on original instances alone (augmentation size = 0) yields an MAE of 1376.53 s.
| Augmentation set size | 32 | 40 | 48 | 56 | 64 |
|---|---|---|---|---|---|
| MAE of Runtime Prediction (s) | 1200.95 | 1163.02 | 1279.91 | 1255.15 | 1208.75 |
We have added the sensitivity analysis to Appendix C.5 of the revised manuscript to enrich the paper.
Q6: It would be nice to see solver-specific hardness stats, or metrics on the solver-runtime-ranking distribution of your synthetic vs original datasets.
We have added the solver-specific hardness stats, including runtime, decisions and conflicts. The results are presented in Table 2 below. We have also included these results in Appendix C.6 of the revised manuscript.
Table 2: Solver-specific hardness of HyperGEN across different datasets. Values in parentheses indicate the relative hardness (RH), expressed as a percentage of the corresponding mean value for the original instances under the same solver.
| Dataset | Solver | Runtime (s) | Decisions | Conflicts | Avg. RH (%) |
|---|---|---|---|---|---|
| MDP | KISSAT-NEW | 39.81 (98.22%) | 2880765.06 (98.70%) | 2213111.44 (98.15%) | 98.35 |
| MDP | MOSS | 46.74 (92.68%) | 3164250.38 (91.95%) | 2574114.06 (92.28%) | 92.30 |
| MDP | UCB | 47.95 (92.55%) | 3228434.46 (92.92%) | 2616606.82 (92.69%) | 92.72 |
| MDP | ESA | 49.11 (96.99%) | 3277109.92 (96.31%) | 2658631.80 (96.16%) | 96.49 |
| MDP | MAB-GB | 48.50 (93.48%) | 3228216.74 (94.14%) | 2625765.58 (94.22%) | 93.94 |
| MP1 | KISSAT-NEW | 13.76 (117.00%) | 614086.92 (103.80%) | 387548.00 (105.88%) | 108.89 |
| MP1 | MOSS | 72.63 (135.06%) | 2742732.50 (120.30%) | 1825156.24 (121.37%) | 125.58 |
| MP1 | UCB | 71.86 (128.34%) | 2716149.08 (116.54%) | 1800661.02 (116.52%) | 120.46 |
| MP1 | ESA | 74.43 (150.43%) | 2790849.48 (132.34%) | 1866759.86 (134.73%) | 139.17 |
| MP1 | MAB-GB | 72.77 (131.12%) | 2724917.96 (116.77%) | 1815453.54 (118.79%) | 122.23 |
| MDP-Large | KISSAT-NEW | 221.37 (93.35%) | 11264950.34 (96.43%) | 8482680.69 (94.94%) | 94.90 |
| MDP-Large | MOSS | 323.75 (84.13%) | 13645409.40 (88.33%) | 10540598.89 (88.18%) | 86.88 |
| MDP-Large | UCB | 328.11 (102.46%) | 13804143.43 (97.73%) | 10661508.20 (98.10%) | 99.43 |
| MDP-Large | ESA | 354.32 (117.90%) | 14432577.63 (107.30%) | 11205427.80 (109.08%) | 111.43 |
| MDP-Large | MAB-GB | 338.29 (82.66%) | 14054590.43 (87.36%) | 10883484.20 (87.75%) | 85.92 |
Q7: It would be nice to see mean/variance statistics on your rarity-predictor. Interpretable statistics for the membership predictor may be more complicated to present, but would also be nice.
We have added the mean and variance statistics of the arity predictor to Appendix C.7 of the revised manuscript. Specifically, for MP1, the mean predicted clause arity is 2.59, with a population variance of ; for MDP, the corresponding values are 2.50 and , respectively. We do not provide additional statistics for the membership predictor, as interpretable statistics for this predictor are more complicated to present.
runtime hardness metric
With respect to runtime hardness, I don't find the authors' answer particularly satisfying. In the literature AND in the authors' own work, a specific empirical motivation is given for why we want to generate SAT problems. In the text's opening paragraph: " This creates a growing need for generative methods that can produce realistic and challenging SAT instances for solver evaluation and data augmentation." Such a motivation doesn't simply require arbitrarily hard instances, it requires realistically hard instances. I'm not sure why the authors are so resistant to this point, given that even the ``maintain hardness'' objective would still have the proposed method as the strongest performing one in 2/3 datasets on RH, and anyways it provides better downstream performance on runtime prediction.
Response by Authors (1/2)
Thank you for the valuable comments. We provide our responses below and sincerely hope that our rebuttal could address your concerns.
Weaknesses:
We have added the relevant experimental details to the revised manuscript, including the number of distinct instances in each dataset, the number of generated instances for downstream task augmentation, the augmentation budget, and the selection of seed instances.
Please refer to our response to Q1 below.
We have conducted the suggested experiments, including the sensitivity analysis of augmentation set size, solver-specific hardness stats, and statistical analysis of the arity predictor. The corresponding results have been added to the revised manuscript. Details are provided in our responses below.
Questions:
We would like to further clarify the motivation for adopting a hypergraph representation in our work and its relationship to the standard bipartite graph representation.
We have revised Section 4.1.1 to clarify the motivation for adopting the hypergraph formulation.
MP1 contains 567 instances, MDP contains 90 instances, and MDP-Large contains 7 instances. We have added the number of instances in each dataset to Appendix B.1 of the revised manuscript.
We have revised the relevant statements to improve the clarity of the manuscript.