acceptodds
Under review as a conference paper at ICLR 2027

Weisfeiler–Leman for embedded graphs: Topological message passing on surfaces

Abstract

We study message passing architectures for graphs embedded on surfaces and thereby connect graph machine learning with topological graph theory. While previous Topological Deep Learning methods study the intrinsic topology of graphs/complexes determined by their combinatorics, we make use of the topology of their embeddings and position our approach between the abstract combinatorial and the explicit geometric settings. This is relevant for many application areas such as drug design. On the one hand, the pure connectivity information of molecules is often not sufficient for chemically interesting predictions; on the other hand, the full 3D structure is not needed and can in many cases hinder learning. For graphs on surfaces, we propose three methods to exploit the embedding via its induced rotation system. We prove the following: (i) Sparse cyclic aggregations identify all embedded trees, (ii) Dense, with a ternary relations on the vertices identify all embedded graphs at dimension three and not below, (iii) Binary relations on the oriented edges achieve the same result already at dimension two. Finally, we fully characterize how these methods compare in expressivity. We propose graph neural networks motivated by these results and evaluate them on topological property prediction tasks and chirality-sensitive molecular tasks. Our experiments show that our approach is not only theoretically interesting but also practically relevant.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Topological, Weisfeiler Leman, WL, embedded, graphs, pebble game, graph neural network, logics, relational structure, chirality

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_RZ1fOpenReview ↗
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

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, a GNN based on 2-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.

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.

Reviewer_hGYaOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

THe paper describes an extension of the WL tests for graphs derived from manifolds. Those graphs carry euclidean geometric information in additon to the connectivity. Hence the WL test need to be extended to cater to this extend in information. The paper shows how embedded trees can be detected, which dimension is needed to detect embedded graphs and finally the expressivity contribution of oriented edges. Those theoretical results are then also evaluated experimentally.

Critical strengths
  1. theoretical contribution: CWL identifies all embedded trees, vertex-based WL has exact dimension three for embedded graphs, and the dart representation achieves completeness at dimension two. It also characterises the relative expressivity of the proposed methods. For example, the comparison between CWL, 2-TWLR, and 2-TWLD clarifies the additional expressive power each representation provides.

  2. Experiments support the theory. The synthetic benchmarks are grouped according to which WL test can distinguish them, and the learned models largely reproduce the predicted hierarchy. MANTRA and ChIRo show that improvements come from embedding information rather than simply greater model capacity. For example, TGN achieves 97.7% on the 2-TWLR group while CGN remains near baseline, as it was shown in the theoretical part.

Critical weaknesses

The strongest theory is not realized practically. The implemented TGN corresponds only to the incomplete 2-TWLR method; it does not implement either the complete 3-TWLR or the complete 2-TWLD. TGN also requires dense (O(n^3C)) computation, while the experiments use very small graphs—5–20 vertices synthetically and at most 10 vertices on MANTRA. Experiments on larger meshes or molecular graphs would make the practical significance of the theoretical completeness results more convincing.

I do not think the MANTRA result supports the theory as stated. The theory assumes oriented surfaces, but MANTRA contains non-orientable triangulations. The paper assigns directions to the vertex links using vertex indices, and Table 6 shows that this convention matters: TGN obtains 100% balanced accuracy with these canonical directions, but only 54–55% when the directions are randomized during training. The two directions describe the same vertex link, so the 100% result does not show that TGN has learned orientability independently of the encoding. The paper should address this with a link-reversal-invariant model or a theoretical treatment of non-orientable surfaces.

Questions for authors

The strongest completeness results concern 3-TWLR and 2-TWLD, but the experiments implement only the incomplete 2-TWLR-based TGN. Could the authors discuss whether the complete methods can be implemented efficiently and how they would scale to substantially larger graphs?

The theoretical framework assumes oriented surfaces, whereas MANTRA includes non-orientable surfaces and requires arbitrary choices of local link direction. Could the authors clarify how this encoding relates to the theory and whether the model could be made invariant to these direction choices?

3 comments

Dear reviewer, thank you for your review and your constructive feedback. Below, we answer your questions and address the weaknesses you pointed out.

Q1) A GNN based on one of the complete tests.

We implemented TGN$^{\mathcal{D}},amodelbasedon2−TWL, a model based on 2-TWL^{\mathcal{D}}$, the more efficient of our two complete tests on graphs of bounded genus. In point 1 of the general response, we discuss its accuracy and how its training time grows with the size of the graphs, up to 80 vertices, compared with CGN and TGN.

Q2) 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.

W1) TGN scalability.

We address this question together with Q1). 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.

Reviewer_hGYaOpenReview ↗

Response to the review

I thank the authors for the rebuttal and for answering my questions. All my concerns are resolved, and I support accepting the paper. I would be happy to raise my score to 4 if I can review the updated manuscript. Please also leave a brief general comment once you upload the revised version, so I won't miss it.

Thank you for the encouraging feedback and for your help in improving our paper, happy to hear we addressed all your concerns! We uploaded the revised version and marked all changes in blue.

Reviewer_nvevOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper looks at WL refinement for graphs cellularly embedded on oriented surfaces. The authors use vertex rotation systems and directed darts to represent the embeddings. They show that 3-TWL on rotations and 2-TWL on darts are complete, and give counterexamples showing why the lower-dimensional versions are not. They also test neural models based on weaker WL refinements.

Critical strengths

The exact WL bounds are the main reason I'm positive about this paper. The authors prove completeness at both levels and provide examples that the weaker tests cannot distinguish. I also found the CWL result on embedded trees interesting. The synthetic experiments generally follow the theory, and shuffling the rotation information largely removes the improvements.

Critical weaknesses
  1. Neither of the complete WL tests is implemented as a trainable model. TGN is built around the weaker 2-TWL rotation refinement, leaving both complete 3-TWL on rotations and 2-TWL on darts at the theoretical level. Appendix F.1 contains only three pairs of non-equivalent embeddings that require the complete tests. That's a rather small test of this part of the theory. I was also curious why the authors didn't try a dart-based architecture, given that 2-TWL on darts is already complete.

  2. MANTRA includes non-orientable surfaces, outside the scope of the main theorems. I also found the orientation experiment in Table 6 a bit puzzling. When TGN is trained with canonical directions, reversing the link directions at a random half of the test vertices still gives 96.2–97.2% balanced accuracy. But when the directions are randomized during training, balanced accuracy drops to around 54–55%, with AUROC around 90%, similar to the graph-only baselines. The paper shows this difference quite clearly, though it's hard to tell why the choice of training directions matters so much.

  3. For ChIRo, the cyclic neighbor order comes from 3D molecular geometry rather than a cellular surface embedding (Appendix H). The authors do provide a more closely matched ChiENN† comparison on the original dataset without RWPE. CGN gets 75.4% ranking accuracy, compared with 73.7% for ChiENN† (Table 3b). This is a reasonable way to test the model on geometry-derived orderings. It doesn't directly test the WL completeness results, though.

Minor Comments

A dart-marked refinement baseline would be worth trying. Most of the identification graphs have 5–20 vertices, while the separate embedded-tree experiments go up to 40. It would also be worth mentioning MeshCNN and HalfedgeCNN in the related work, since both deal with ordered neighborhoods or halfedges.

Questions for authors
  1. Could the authors say more about implementing complete 2-TWL on darts as a trainable model? How would it compare with TGN or dart-marked refinement?
  2. Why does randomizing local orientations during MANTRA training hurt performance so much, when the model can still handle reversing half of the directions at test time?
3 comments

Dear reviewer, thank you for your review and your constructive feedback. Below, we answer your questions and address the weaknesses you pointed out.

Q1) A GNN based on 2-TWL$^{\mathcal{D}}$.

We implemented TGN$^{\mathcal{D}},aGNNbasedon2−TWL, a GNN based on 2-TWL^{\mathcal{D}}$, and we discuss its accuracy and runtime in point 1 of the general response.

Q2) MANTRA, choice of link direction.

We investigated this phenomenon in depth. As discussed in point 3 of the general response, with a setting found by a broader hyperparameter search, TGN reaches ~100% balanced accuracy even with random (coin-flipped) directions in both training and test. The full study will be in App. G.

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.

W3) ChIRo: rotation system from 3D molecular geometry rather than a cellular embedding.

We agree that the ChIRo tasks do not directly test our completeness results. Still, we also wanted to test our methods on popular benchmarks slightly beyond the scope of our theory (see also point 2 of the general response). For every molecular graph in ChIRo, the rotation system computed from the 3D geometry determines a cellular embedding in an orientable surface of genus up to 4. In other words, we view each molecule as a graph embedded on a surface, and two enantiomers correspond to two different embeddings of the same graph, since the cyclic order at the stereocenter is reversed. We will add this discussion to App. H.

Minor comments:

a) Identification graphs have 5–20 vertices, while trees have 11–40.

Consistency: While we acknowledge the difference in vertex counts, we point out that a tree with n vertices has n-1 edges, while a general graph can have up to n(n-1)/2, and a rotation system is a permutation of the darts, two per edge. Measured by the number of edges, the two experiments have similar sizes: the trees have 10 to 39 edges, and the identification graphs have 9 to 55 edges. Complexity: We also measured how the training time grows with the number of vertices, from 10 to 80 (second table in point 1 of the general response). Despite its cubic complexity, TGN takes 4.0 seconds per epoch at 80 vertices, about five times as long as at 10 vertices.

b) Thank you for pointing out further related work. We will discuss MeshCNN (Hanocka et al., 2019) and HalfedgeCNN (Ludwig et al., 2023) in the revised manuscript.

Thank you for the detailed responses, which have addressed many of my concerns. I'll keep my positive score accordingly.

Thanks again for your help in improving our paper and for engaging during the rebuttal!

Comments on the paper

3 comments
AuthorsOpenReview ↗

General response (1/2)

Dear reviewers, thank you for the positive evaluation of our paper and for highlighting our theoretical contributions. Below, we address the common points and then answer each review separately. We will also incorporate the additional results mentioned in our replies into the revised manuscript in the next few days, and we are happy to address any remaining questions during the discussion period.

1) A GNN based on one of the complete tests:

We implemented TGN$^{\mathcal{D}},aGNNbasedon2−TWL, a GNN based on 2-TWL^{\mathcal{D}},themoreefficientofourtwocompletetestsongraphsofboundedgenus.Herearetheresultsonthesynthetictasks,whichcompleteTables2and4ofthesubmittedmanuscript.AssuggestedbyreviewersnvevandRZ1f,weextendedthe3−TWL, the more efficient of our two complete tests on graphs of bounded genus. Here are the results on the synthetic tasks, which complete Tables 2 and 4 of the submitted manuscript. As suggested by reviewers nvev and RZ1f, we extended the 3-TWL^{\mathcal{R}}$ group, which among our models only TGN$^{\mathcal{D}}$ can solve, from 3 to 440 pairs of embeddings.

ModelParamsCWL group2-TWL$^{\mathcal{R}}$ group3-TWL$^{\mathcal{R}}$ groupTreesGenus
Graph-only upper bound–27.628.937.850.042.8
CGN127,055100.0 ± 0.011.1 ± 1.337.8 ± 0.096.3 ± 1.252.0 ± 0.8
TGN219,339100.0 ± 0.097.7 ± 1.340.5 ± 0.0100.0 ± 0.092.8 ± 1.5
TGN$^{\mathcal{D}}$175,563100.0 ± 0.0100.0 ± 0.0100.0 ± 0.099.3 ± 1.299.1 ± 0.1

Test accuracy (%), mean ± std over three seeds; parameters on the CWL group. The first row is the highest accuracy a model blind to the rotation system can reach (see Table 4 in the submission manuscript).

On the 3-TWL$^{\mathcal{R}}$ group, the expressivity of 2-TWL$^{\mathcal{R}}$ limits TGN to 40.5%, while TGN$^{\mathcal{D}}$ reaches 100%.

We measure the training time of our three models CGN, TGN and TGN$^{\mathcal{D}}$ on graphs with n vertices and 2n edges for n=10,20,40,80, testing the scalability to bigger graphs. In every epoch, the models process 1,600 graphs and runtimes are measured on a single NVIDIA RTX 3080 GPU.

Modeln=10n=20n=40n=80
CGN0.400.410.430.41
TGN0.760.831.424.01
TGN$^{\mathcal{D}}$1.645.4021.15110.30

Training time in seconds per epoch.

As shown in the two tables above, the results with TGN$^{\mathcal{D}}$ align with the theory as the model correctly classifies all graphs in all three identification groups. However, its runtime is high as it operates on pairs of darts instead of pairs of vertices. We therefore focus on CGN and TGN for MANTRA and ChIRo, where these cheaper models already outperform or approach the best existing models at a fraction of the training time.

AuthorsOpenReview ↗

General response (2/2)

2) Application of our models to non-orientable surface embeddings of MANTRA:

Our synthetic experiments confirm our theoretical findings. In addition, we wanted to test our methods on popular benchmarks slightly beyond the scope of the theory. We will clarify this distinction in the revised manuscript. For MANTRA, we can also theoretically explain the high predictive performance of TGN on triangulations in terms of the expressivity of 2-TWL$^{\mathcal{R}}$. As suggested by reviewer hGYa, we will add this theoretical finding to App. G.

We extend our setting to cellular embeddings on any closed surface, orientable or not. Such an embedding is determined up to homeomorphism by a rotation system π\pi obtained from a local orientation at every vertex as in the oriented case, together with a sign on every edge that records whether the local orientations at its two ends are coherent (Mohar & Thomassen, 2001, Sec. 3.3). On a triangulation, the local orientation at a vertex is a direction of its link and the signs can be omitted since the directed links determine them (details will be in App. G). We choose an arbitrary direction for every link and we prove that 2-TWL$^{\mathcal{R}}$ applied to this structure determines the homeomorphism type of the surface, and hence its orientability and Betti numbers for every choice of link directions. This gives a theoretical justification for the ~100% accuracy of TGN on all three MANTRA tasks: the labels (orientability, Betti numbers and homeomorphism type) are a function of the 2-TWL$^{\mathcal{R}}$ stable coloring, independently of the chosen link directions.

3) MANTRA: dependence on link directions:

Our theoretical result above ensures that 2-TWL$^{\mathcal{R}}$ determines the orientability independently of the chosen link directions. However, Table 6 of the submitted manuscript shows that TGN trained on random directions did not perform better than the graph-only models. We systematically investigate whether the results of TGN depend on the choice of directions by training and testing it with three choices of link directions, from deterministic to fully random. Our extended study and a broader hyperparameter search show that TGN reaches ~100% balanced accuracy even in the most general case, with random directions (called coin-flipped) in both training and test. Below is our main result; the full study will be included in App. G in the next few days.

TrainingTestBal. acc.AUROC
coin-flipped (random)coin-flipped (random)99.9 ± 0.1 / 100.0 ± 0.0100.0 ± 0.0 / 100.0 ± 0.0

TGN on MANTRA orientability, mean ± std over five seeds, in %. The two values in each cell come from two independent draws of the coin-flipped test directions.

Dear reviewers, thank you for the thoughtful feedback. We have uploaded a revised version of the paper that incorporates all changes outlined in our rebuttal, highlighted in blue. In particular, we address the main concerns as follows:

  • In Appendix F, we present TGND\text{TGN}^{\mathcal{D}}, the complete method based on the 2-TWLD2\text{-TWL}^{\mathcal{D}} test, and we discuss the scalability of our three models.
  • In Appendix E, we present the extension of our theory to non-orientable surfaces, which provides the theoretical foundations for our experiments on MANTRA.
  • In Appendix H.5, we present our empirical study of the dependence on the chosen link directions in the MANTRA triangulations. We show that, even with randomized link directions, TGN achieves perfect accuracy.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.