- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper claims that a weight-tied message-passing GNN can represent set-valued equivariant maps. The author ran experiments on three scientific tasks and showed that training on problem-specific tasks can produce convergent trajectories.
Critical strengths
-
The problem is framed well. It is notable that, on symmetric graphs, selecting one arbitrary target may violate equivariance even though the full solution set is equivariant.
-
The authors conduct experiments on three different domains, showing the effectiveness of the proposed method.
-
The theoretical claim is broad, though I could not check all proofs.
Critical weaknesses
- The novelty seems limited. The author extends [1] to graph permutation symmetry and message passing.
- [1] Drop contraction to represent set-valued maps through attractor landscapes
-
The author claims that "there exists a continuous MP-GNN block". However, it is hard to be convinced that "a practically trainable neural GNN will learn this attractor structure".
-
Code is not provided, which makes it hard to reproduce the claims (even though it is a theoretical paper).
Questions for authors
Please see the above weaknesses
7 comments
Rebuttal (Part 2)
Why representing the solution set matters on graphs. As the reviewer notes, on a symmetric graph the solution set is equivariant, but a single selected solution may not be. When no solution is itself symmetric, as in the two-coloring example of Section 1, an equivariant single-valued selector does not exist at all: an equivariant GNN trained toward one designated solution is asked to output something it cannot represent. For equivariant GNNs on multi-solution tasks, the solution set itself must therefore be represented, which is what Theorems 1–2 achieve and what contraction rules out (Theorem 3).
Empirical contributions. Beyond the Ising benchmark of [1], we study chemical multistationarity built on the reaction networks of Yao et al. (2025), modularity maximization on the PROTEINS graphs, and a standard CO benchmark (MIS on IMDB-BINARY, from VAG-CO). [1] compares only against single-branch supervision; we compare against the state of the art for multi-solution problems, namely distributional and diffusion solvers (DIFUSCO, VAG-CO, DDPM/DDIM/DIS), including at matched wall-clock time (qRh5 W2–W3, D76A W2).
Together, our theory and experiments address the three aforementioned questions central to GNNs that [1] does not address: whether uniqueness can compromise solution validity, whether a multi-attractor representation can respect permutation symmetry, and whether one message-passing GNN can realize and learn such a representation on graphs. Theorems 1–3 establish the expressivity results, and our experiments demonstrate their practical significance: on the toy task, every contractive control recovers 0% of trajectories, while a single equivariant MP-GNN learns an update that matches the constructed operator (94.1% basin agreement) and finds all three solutions on 99.56% of 1,000 held-out graphs (Table 4, Appendix D.3). On the scientific and combinatorial benchmarks, our model, trained without solution labels, achieves both better mean quality and more distinct solutions than SOTA baselines at matched wall-clock time (Appendix J).
Rebuttal (Part 3)
W2.
"Hard to believe a practically trainable GNN learns this attractor structure."
What it means to learn an attractor structure, and where the paper shows it. A trained network has learned an attractor structure if, on the same graph, its trajectories (i) converge, (ii) end at several distinct valid solutions, and (iii) these endpoints are stable, i.e., nearby states are pulled back to them. The original paper already shows (i) and (ii):
- Fig. 3 (toy): under one learned update, 128 trajectories from different initial states split into three clusters at the three exact solutions, whereas the single-target and contractive controls each concentrate away from all of them.
- Tables 1–3 and Appendices E–G: on every task, the same trained network converges and returns several distinct valid solutions per graph:
| One trained network, 20 starts per graph | Ising | PROTEINS | Chemistry |
|---|---|---|---|
| Trajectories that eventually converge | 100% (Table 9) | 99.58% (Table 13) | 96.15% (Appendix G) |
| Distinct valid solutions per graph (, at ) | 2.16 exact ground states (Table 1) | 5.83 qualified partitions (Table 2) | 3.51 accepted steady states (Table 3) |
To further address the reviewer's concern, we added the following experiments:
New (1): the toy, where the learned structure is aligned with the theory's (Appendix D, pages 43–45). In the toy, the exact solution set and the theory's operator are known, so we can check not only that trajectories converge but that the learned dynamics has the same attractor structure as . Over 5 training seeds, 1,000 held-out graphs and 128 starts per graph, 99.86% of trajectories converge to an exact solution, and all 3 solutions are found on 99.56% of graphs. We then compare the learned update with at three levels:
- Where trajectories go: basins. The basin of a solution is the set of initial states whose trajectory converges to it. An attractor structure is exactly such a division of the state space: each attractor owns a region of initial states, and the boundaries between regions are where the reached solution switches. Comparing basins therefore compares the attractor structures themselves, not just a few endpoints. The theory's moves every state toward its nearest solution, so its basins are the nearest-solution (Voronoi) cells, separated by the switching sets of Definition 3. We color a grid of initial states (a 2D slice through all three solutions) by the solution each start reaches, under the learned update and under . The two basin maps agree on 94.1% of initial states, and all disagreements lie in a band one grid cell wide along a basin boundary (Fig. 6). The learned network thus has the same three attractors as the theory, and divides initial states among them in the same way.
- How trajectories move: update direction. moves each state straight toward its nearest solution : with a positive step size. The theory therefore predicts cosine 1 between the learned update and . Over the first three updates (afterwards both displacements are nearly zero), the mean cosine is 0.951, 0.900 and 0.950 for the three training seeds (Table 6). The learned update points almost exactly where the theory prescribes.
- Where trajectories stop: fixed points. The attracting fixed points of are the exact solutions; the learned fixed points lie within RMS of them.
New (2): all four tasks, local stability of the learned fixed points (Appendix I, Table 19, page 60). This tests (iii). At a fixed point of the learned update , a small deviation evolves as with Jacobian ; it shrinks to zero if and only if the spectral radius , the largest eigenvalue modulus, is below one. So means that is an attractor with its own basin, exactly the structure the theory constructs. We compute at the fixed points reached from random starts on the test sets:
| Property | Toy | Ising | PROTEINS | Chemistry |
|---|---|---|---|---|
| Locally attracting fixed points () | 100% | 100% | 100% | 99.2% |
| : median [min, max] | 0.06 [0.032, 0.113] | 0.36 [0.003, 0.998] | 0.76 [, 0.9999] | 0.90 [0.584, 1.00001] |
The other 6 fixed points are marginal ().
Together, (i)–(iii) hold on every task: trajectories settle, almost every endpoint is a stable attractor, and one network reaches several valid solutions per graph; in the toy, the learned attractor structure also matches the theory's in its basins, update directions and fixed points. Theorem 2 guarantees that a GNN with this structure exists; these results show that plain energy training finds one.
Rebuttal (Part 1)
We thank the reviewer for the comments. Our responses are below, and all revisions are marked in blue in the paper.
W1.
"Novelty is limited: an extension of [1] to permutation symmetry and message passing."
Motivations and questions. Recurrent, weight-tied and implicit GNNs have attracted increasing attention, and the common practice is to make the update a contraction so that every graph has a unique fixed point. We show that this practice has a fundamental limitation on tasks with several valid solutions: under suitable conditions, every continuous, permutation-equivariant, contractive update misses all valid solutions with positive probability, for any depth and width and regardless of training (Theorem 3). We then provide an alternative: a single recurrent message-passing GNN (MP-GNN) whose multiple attractors are the solutions, so that each run converges to a valid solution and different initializations reach different solutions (Theorems 1–2); it can be trained without solution labels (Section 3).
We assume [1] refers to Jore & Liu (2026), Bifurcation Models: Learning Set-Valued Solution Maps with Weight-Tied Dynamics; please correct us if not. [1] shows that a solution set can be represented by an attractor landscape. It does not answer the questions that are central for GNNs:
Technical contributions.
Theorem 1: equivariant set-valued representation. A single operator T:(G,y)↦TG(y), jointly globally Lipschitz in (G,y) and permutation equivariant, whose iteration converges almost surely to a valid solution on every regular graph G∈G⋆ and reaches every solution with positive probability. It generalizes the main result of [1] to the equivariant setting; to our knowledge, it is the first equivariant set-valued representation of this kind.
Theorem 2: one MP-GNN realizes the set-valued map. This requires new techniques.
(a) Combining [1] with GNN approximation is not enough. If one simply took the ideal operator TG (Theorem 1) and approximated it with a GNN through a standard universal-approximation result, as the review suggests, Theorem 2 would not follow: even an arbitrarily accurate approximation cannot guarantee that trajectories converge. For example (Appendix B), let T contract toward a solution s at rate 1−β. Near s, define F in polar coordinates: it maps the radius r to (1−β)r+δ and rotates by a small fixed angle (an irrational multiple of π); away from s, it equals T. Then F is uniformly O(δ)-close to T, yet every trajectory that comes near s circles forever on the circle of radius δ/β. We avoid this by realizing a different construction (Lemma 5): it follows TG until the state is close to its selected solution, and then contracts each node toward the center of its own small "address box". This construction is not taken from [1].
(b) The evolving state serves as its own node ID, and these IDs do not collide. A message-passing GNN applies the same function at every node, so two nodes with identical states and neighborhoods always receive identical updates. This is the fundamental expressivity limit of GNNs (Xu et al, 2019); standard universality results in the literature overcome it by giving each node an extra, typically random, ID. Our framework has no such ID: only the solution state yt is passed between iterations, so yt itself must play this role. We prove that almost surely no two nodes ever share the same state under the ideal dynamics (Lemma 6), and that this separation holds with uniform margins, so the GNN, which only approximates TG, inherits it (Lemma 7). This is hard: the IDs are generated by the network's own dynamics and change at every step, nodes interact, and the dynamics pull states toward solutions in which many nodes have equal values. To our knowledge, this is the first work in which (i) a GNN’s own output state serves as the node ID, and (ii) a recurrent, weight-tied GNN represents set-valued maps. This is not taken from [1].
Theorem 3: contraction fails, a phenomenon specific to graphs that [1] does not contain. The failure holds even when the graphs are almost surely asymmetric (independently weighted triangles; Theorem 6 in Appendix C gives the general version). Random initialization breaks symmetry only temporarily, contraction erases its effect, and continuity carries the failure from a symmetric graph to an open set of asymmetric graphs around it. Without equivariance, a unique equilibrium loses diversity; with it, it can lose validity altogether. This is not taken from [1].