- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This work studies WL tests for graphs embedded on surfaces. Specifically it proposes encoding the embedding as a rotation system (cyclic order of neighbors around each node). Authors show that by Edmonds’ theorem this captures the embedding up to orientation-preserving homeomorphism. In this sense, the setting sits between abstract graphs and geometric GNNs.
Authors propose three tests: CWL (1-WL with cyclically ordered neighbor tuples), k-TWLR (k-WL with a “next neighbor” relation), and k-TWLD (k-WL on darts with two binary relations). CGN and TGN (GIN and PPGN augmented with the rotation system) match the theory on synthetic pairs, TGN solves MANTRA orientability at 100% where baselines sit at ~50-58, and CGN is competitive with specialized chirality models on ChIRo at much lower runtime.
Critical strengths
-
The paper pins the WL dimension of embedded graphs at 3, improving on the previous bound of 4. This result is supported by a clearly explained hierarchy: CQL fails to distinguish a planar pair, 2-TWLR fails on a cube pair, and 3-TWLR/2-TWLD is complete. The tree result requires a non-obvious proof as well, making this a strong contribution to understanding WL expressivity.
-
I particularly liked the pebble game strategy of tracing a word that loops on one structure but not the other, and its reuse in both completeness proofs. The setup makes these arguments easy to follow: Edmonds’ theorem reduces the topology to combinatorics, and Lemma 3.4 gives three equivalent representations.
-
The CGN/TGN results follow the theoretical predictions, with synthetic pairs grouped by the weakest test that separates them. The shuffled-rotation ablations and the genus task on unseen graphs also provide evidence that the models use the proposed rotation system. Overall, the experiments are well aligned with the theory and support its claims.
Critical weaknesses
-
No model implements the complete test. Although 2-TWLD is presented as an efficient complete test, no corresponding dart-based GNN is evaluated. The models implement CWL and incomplete 2-TWLR, and the G3-TWLR group contains only 3 graphs / 12 instances.
-
TGN’s O(n^3) complexity also raises scalability concerns that are not discussed.
-
I am not sure what the MANTRA experiment is doing here. It seems to me that the theory assumes oriented surfaces, but 92% of MANTRA test surfaces are non-orientable. Their extracted cyclic orders therefore describe a different (orientable) surface, making it unclear what TGN detects. In G.5, random link directions fail while canonical directions give 100%, which suggests to me some sort of reliance?This result needs explanation.
Minor issues
- G.2 ends mid-sentence (“We refer to this”).
- Table 4: TGN with shuffled rotation systems gets 30.1% on the 2-TWLR group, above the stated graph-only ceiling of 28.9%. are the random orders fixed per instance and leaking the class?
- Proposition D.3 is proven by “a direct computation” with nothing shown.... Also the AI use statement says generative AI provided “critical ingredients” for the proofs and it seems like the Appendix D proofs are terse and should be checked carefully.
Questions for authors
Clarifications
Regarding the MANTRA weakness above: can you explain what TGN is actually using to reach 100% on non-orientable surfaces, and how the oriented-surface theory applies there?
For atoms with 4+ neighbors, the rotation system depends on reference neighbors chosen by RDKit canonical ranking. How sensitive are the ChIRo results to this choice? does reflecting the coordinates correspond to reversing all cyclic orders under this construction?
Regarding the missing complete model above: is there an obstacle to building a GNN on the dart structure, or was this just a scoping decision?
Regarding the Table 4 shuffled result above: are the shuffled orders fixed per instance across train and test? I am wondering if they could be leaking the class.
3 comments
I thank the authors for their detailed response and additional results. I second hGYa's response that I would be inclined to raise my score if/when the updated paper is provided.
Thanks again for your help in improving our paper and for engaging during the rebuttal! We uploaded the revised version and marked all changes in blue.
Dear reviewer, thank you for your review and your constructive feedback. Below, we answer your questions and address the weaknesses you pointed out.
Q1) MANTRA: non-orientability and choice of link directions.
In points 2 and 3 of the general response, we explain how our encoding extends to non-orientable surface embeddings. For triangulations, we prove that 2-TWL$^{\mathcal{R}}$ determines the homeomorphism type of the surface independently of the chosen link directions (to be added to App. G). Our experiments also show that TGN is robust to these choices. The full study on the dependence on the link directions will be in App. G.
Q2) ChIRo rotation encoding.
Reflecting the coordinates reverses exactly the cyclic orders at the atoms of degree 4 (maximum degree present in the dataset) and at the non-planar atoms of degree 3 (where the atom and its three neighbors do not lie in the same plane), which include the labeled stereocenter, while it leaves unchanged the orders at the planar atoms of degree 3 (atoms of lower degree have a single cyclic order).
To answer the question about the sensitivity to the RDKit canonical atom ordering, we retrained CGN, our faster and best-performing model on ChIRo, on the R/S and Ranking tasks without re-tuning its hyperparameters, replacing the RDKit ordering with three other atom orderings:
(i) the reverse of the RDKit ordering,
(ii) the InChI canonical atomnumbering (Heller et al., 2015),
(iii) the canonical graph labeling of nauty (McKay & Piperno, 2014).
The test accuracy of CGN changes by at most 0.2 points on R/S and 0.9 on ranking, so the results are not sensitive to this choice (details will be in App. H).
Q3) A GNN based on 2-TWL$^{\mathcal{D}}$.
We implemented TGN$^{\mathcal{D}},aGNNbasedon2−TWL^{\mathcal{D}}$, and we discuss its accuracy and runtime in point 1 of the general response.
Q4) Shuffled TGN on the 2-TWL$^{\mathcal{R}}$ group.
As in the expressivity benchmarks CSL (Dwivedi et al., 2023) and BREC (Wang & Zhang, 2024), all splits contain relabeled copies of the same embeddings, but never the same copy (ten copies per class, split 6/2/2). In the shuffled control, each copy receives its own random rotation system, drawn once at loading time, so the orders are fixed per instance but never shared between training and test. Given the graph, the shuffled rotation system of a test instance is thus independent of its class, and no model can exceed the graph-only upper bound of 28.9% in expectation. The 30.1% is within uncertainty (standard deviation of about 3 points); in the revised version, shuffled TGN scores 26.8 ± 0.9% on this group.
W1) Size of the 3-TWL$^{\mathcal{R}}$ (complete) group in the synthetic tasks.
We extended this group from 3 to 440 pairs of embeddings of 28 graphs. As the theory predicts (first table of point 1 of the general response), CGN and TGN stay at the upper bounds of their tests, while TGN$^{\mathcal{D}}$ reaches 100%. Details will be in App. F.
W2) TGN scalability.
We address this question in point 1 of the general response. Although the cost of TGN is cubic in the number of nodes, its training time increases only from 0.76 to 4.01 seconds per epoch from 10 to 80 nodes, a factor of 5.3 against 512 for a cubic cost.
Minor issues:
In the revised version, the proofs in App. D, already checked by us at submission time, are written out in full. For Propositions D.1 and D.2, we expanded the inductions that were only sketched. For Proposition D.3, we replaced the "direct computation" with an explicit one: a figure shows the refinements on the two pairs, iteration by iteration, and the proof explains them step by step; these computations can also be reproduced with twl-compare in our implementation. We will upload the revised manuscript in the next few days.