Summary
This paper suggests using a symmetry breaking indexing for nodes in a graph. The argument is that for inverse problems, such as molecule design, graph isomorphism results in finding many equivalent solutions. The symmetry breaking indices are supposed to partially alleviate this redundancy. They use pre-trained GNN (based on GraphSage) for computer-aided molecule design (CAMD). During the design, they use Mixed-Integer Programming (MIP) (solved using Gurobi) to solve a set of constraints to make the molecules chemically realistic as well as constraints arising from their indexing scheme.
They conduct experiments on QM7 and QM9 and find that the symmetry breaking methods perform much better. They show more successful runs (i.e. producing molecules satisfying the constraints) and achieve this in a fraction of the time, compared to models without symmetry breaking.
Strengths
The paper makes a good case for how adding an ordering (indexing nodes in a specific manner) can dramatically improve inverse problems on graphs, e.g. designing molecules, solved using MIP.
The paper is well structured and discusses the literature in good depth. It explains the algorithm and experimental setup. The results are also very strong for the experiments.
Weaknesses
The experiments show that with the indexing, MIP converges much faster. Table 1 states that MIP find many feasible solutions for each setting and set of constraints. One thing I hope the authors can assess (maybe using a Weisfeiler-Lehman hash or similar; see questions below) is how much the symmetry breaking *actually* removes isomorphic solutions, compared to the runs without symmetry breaking. they could do it for a small setting, maybe QM9, N=3 or 4. The goal would be two fold:
1. To show that the symmetry breaking indeed removed many isomorphic molecules
2. to check how the diversity of solutions in the symmetry broken case compares with the diversity of molecule found in the vanilla algorithm.
I was also hoping some kind of baseline could be discussed, but I understand that to have a fair comparison they need to use the same pretrained GNNs with and without symmetry breaking.
Also, the claims about generality of the approach and applicability to other graph problems, though reasonable, lack any substantive evidence or hint as to how to do it concretely. I suggest wither softening the claims or giving some hints as to why that is.
In terms of structure, I think the proof of theorem 1 is not necessary to be in the main text and occupies too much space. Instead some version of the last two tables in the appendix could be more useful in the main text.
Questions
1. Table 1: In each row, is higher necessarily better? If we want less symmetry copies, should sometimes less be better?
2. How do we know that the solutions found with the symmetry broken model are as diverse as the one with symmetries? These are small molecules. Can you use a fast Weisfeiler-Lehman type hash to check isomorphism of found molecules at least in small N experiments? Maybe also use a measure of diversity, some kind of entropy or something.
### Minor questions:
line 75 “Directed to undirected” how?
line 106 A is now a multiset, not the adjacency matrix anymore?
line 183 (*) is not permutation invariant, as written. $w_{u\to v}$ is like a generalized Graph Attention (GAT).
line 187 Dense NN: do you mean a fully connected layer (no graph)?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
The authors discuss technical limitations, but I don't think there are immediate societal impacts, as the paper pertains to a technical method to speed up generative design in graph problems.