acceptodds
Under review as a conference paper at ICLR 2027

Multi-Attractor GNNs: Set-Valued Expressivity Beyond Unique Equilibria

39 views

Abstract

Recurrent and equilibrium graph neural networks (GNNs) are often designed to have a unique fixed point or trained against a single target per graph. Yet many combinatorial and scientific problems are inherently set-valued: several valid solutions coexist for the same graph, and nothing in the problem singles one out. Training against a single designated target then makes the model fit an artifact of how that target was picked, rather than the structure of the problem. For example, when a task is invariant to node relabeling, a symmetric graph has a symmetric solution set, yet may admit no symmetric solution; isolating a single target then imposes an arbitrary symmetry-breaking choice. In this paper, we show that multiple equilibria of recurrent GNNs are a resource rather than a defect: one weight-tied message-passing GNN can represent such set-valued equivariant maps through its attractor landscape, where different random initializations converge to different valid solutions. We establish this expressive power in two steps. First, we prove the existence of globally Lipschitz, permutation-equivariant multi-attractor dynamics that converge almost surely to valid solutions while reaching every solution branch with positive probability. Second, we establish a realization theorem proving that a recurrent message-passing GNN can approximate these dynamics and their limits with arbitrarily small error and arbitrarily high probability. This goes beyond standard universality arguments, since message passing cannot by itself distinguish symmetric nodes: we show that the evolving state keeps the symmetry broken at every step, without auxiliary node identifiers. In practice, such dynamics can be learned without solution labels from problem-specific energies. On three scientific tasks (ground states of Ising models, structural module detection in protein graphs, and steady states of chemical reaction networks), the learned updates reach multiple distinct, high-quality solutions through numerically convergent trajectories, outperforming matched unique-equilibrium, single-target, and feedforward baselines, while remaining competitive with far larger diffusion-based solvers.

Primary area:
learning theory
Keywords:
Graph neural networks, Scientific Machine Learning, Expressive power

Reviews

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

  2. The authors conduct experiments on three different domains, showing the effectiveness of the proposed method.

  3. The theoretical claim is broad, though I could not check all proofs.

Critical weaknesses
  1. 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
  1. 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".

  2. 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
AuthorsOpenReview ↗

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:

  • Is a unique equilibrium merely less diverse, or can it fail altogether on graphs? (Theorem 3)
  • Can such a landscape respect permutation symmetry? (Theorem 1)
  • Can one MP-GNN, which cannot tell apart nodes with identical states and neighborhoods, realize this landscape (Theorem 2)?

Technical contributions.

  1. Theorem 1: equivariant set-valued representation. A single operator T:(G,y)↦TG(y)T:(G,y)\mapsto T_G(y), jointly globally Lipschitz in (G,y)(G,y) and permutation equivariant, whose iteration converges almost surely to a valid solution on every regular graph G∈G⋆G\in\mathcal G^\star 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.

  2. 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 TGT_G (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 TT contract toward a solution ss at rate 1−β1-\beta. Near ss, define FF in polar coordinates: it maps the radius rr to (1−β)r+δ(1-\beta)r+\delta and rotates by a small fixed angle (an irrational multiple of π\pi); away from ss, it equals TT. Then FF is uniformly O(δ)O(\delta)-close to TT, yet every trajectory that comes near ss circles forever on the circle of radius δ/β\delta/\beta. We avoid this by realizing a different construction (Lemma 5): it follows TGT_G 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 yty_t is passed between iterations, so yty_t 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 TGT_G, 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].

  3. 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].

AuthorsOpenReview ↗

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 TGT_G (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).

AuthorsOpenReview ↗

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 graphIsingPROTEINSChemistry
Trajectories that eventually converge100% (Table 9)99.58% (Table 13)96.15% (Appendix G)
Distinct valid solutions per graph (DD, at t=200t=200)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 TGT_G are known, so we can check not only that trajectories converge but that the learned dynamics has the same attractor structure as TGT_G. 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 TGT_G 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 TGT_G 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 41×4141\times41 grid of initial states (a 2D slice through all three solutions) by the solution each start reaches, under the learned update and under TGT_G. 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. TGT_G moves each state straight toward its nearest solution P(y)P(y): TG(y)−y=β(G,y)(P(y)−y)T_G(y)-y=\beta(G,y) (P(y)-y) with a positive step size. The theory therefore predicts cosine 1 between the learned update GNNθ(G,yt)−yt\mathrm{GNN}_\theta(G,y_t)-y_t and P(yt)−ytP(y_t)-y_t. 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 TGT_G are the exact solutions; the learned fixed points lie within 1.7×10−41.7\times10^{-4} 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 y⋆y^\star of the learned update FF, a small deviation evolves as δt+1≈Jδt\delta_{t+1}\approx J\delta_t with Jacobian J=∂yF(y⋆)J=\partial_yF(y^\star); it shrinks to zero if and only if the spectral radius ρ(J)\rho(J), the largest eigenvalue modulus, is below one. So ρ<1\rho<1 means that y⋆y^\star is an attractor with its own basin, exactly the structure the theory constructs. We compute ρ\rho at the fixed points reached from random starts on the test sets:

PropertyToyIsingPROTEINSChemistry
Locally attracting fixed points (ρ<1\rho<1)100%100%100%99.2%∗^\ast
ρ\rho: median [min, max]0.06 [0.032, 0.113]0.36 [0.003, 0.998]0.76 [7⋅10−87\cdot10^{-8}, 0.9999]0.90 [0.584, 1.00001]

∗^\astThe other 6 fixed points are marginal (ρ−1≤9×10−6\rho-1\le9\times10^{-6}).

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.

Reviewer_D76AOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the expressivity of recurrent GNNs. Relying on the fact several scientific problems have multiple coexisting solutions, the convergence of traditional GNNs to a unique equilibria limits their capacity on such tasks. In this setting, they prove the existence of an equivariant multi-attractor dynamics, that can be realized by a weight-tied recurrent message-passing GNN. Using toy examples and scientific learning tasks, they justify the importance of models that are able to find set-valued equilibria: the proposed recurrent GNN architecture shows a superior performance and diversity of solutions than single-target, unique equilibrium, untied feedforward, and distributional models.

Critical strengths
  • The introduction of the paper draws a clear picture of the model studied and of the problem at hand.
  • The progression of the paper is well supported by examples/toy experiments, which helps the overall exposition of the paper.
  • The theorems are well presented and provide a clear contribution on the expressive power of recurrent GNNs.
  • The proposed model shows strong performance on the set of metrics considered, both on the loss score and on the diversity of solutions.
  • The design of the experiments is quite interesting and related to diverse scientific and practical questions.
  • The proofs in the Appendix are well structured and appear clear to me.
Critical weaknesses
  • Although the related work section is well furnished, it is not mentioned and only put at the end of the Appendix. This limits the capacity of the paper to pose the problem properly: when reading the main paper, it is not clear what the contribution relies on (apart from the toy problem of Fig1).
  • The experimental part is certainly well designed, but it feels like each of the experiments are built from scratch. While this is quite a contribution, it also prevents the comparison of your model with others on more typical learning tasks. Not asking for a whole new benchmark, but how does your recurrent GNN architecture behave in combinatorial optimization tasks that can be found in the VAG-CO or DIFUSCO papers ? In my opinion, there should be some transferability of your approach to existing experiments. Additionally, given the set of « diversity » metrics you are using, if you can showcase the superiority of your approach compared to that of others in their experimental environment, that would be a great plus.
Questions for authors
  • In Fig.3, how can you explain the fact that the single-target-supervised GNN representations converge to 0, even if it does not have any contraction? Is it due to some oversmoothing behavior ? If so, have you tried any oversmoothing mitigation strategy ?
  • How does the proposed model perform in more standard combinatorial optimization tasks ?
  • What motivates you to use the same distributional and diffusion-based models in the frustrated Ising task than in the PROTEINS task?
  • What is the order of magnitude of solutions in each of the experiments ? I am aware that these problems are usually (NP-)hard, but having this information would help confirm the statement that the recurrent GNN covers efficiently the diverse equilibria of the problem.
  • What happens when the multi-attractor GNN is trained on a task that has a single equilibrium? Even though it is not meant for it, it can serve as a sanity check and would provide some understanding on the propagation dynamics of such architecture.
  • Can the property of having initialization-dependent solutions be linked to some chaotic property of your recurrent GNN model?

Additional feedback

There a some references that are cited in their arXiv version, that have actually been published in journals or proceedings (eg Xu et al 2018, probably some other)

7 comments
AuthorsOpenReview ↗

Rebuttal (Part 1)

We thank the reviewer for the detailed and helpful comments, in particular the suggestions to position the work in the main text and to test on a standard CO benchmark, which we have followed. Our responses are below, and all revisions are marked in blue in the paper.

W1.

"Related work appears only at the end of the appendix."

Agreed. We added a short related-work paragraph to Section 1 (page 3) that positions the contribution in the main text; Appendix M remains the detailed version. The new paragraph reads:

Related work. GNN expressivity theory characterizes which single-valued maps G↦f(G)G\mapsto f(G) message passing can approximate, with random node features serving to tell nodes apart (Xu et al., 2019; Morris et al., 2019; Abboud et al., 2021; Sato et al., 2021; Rosenbluth & Grohe, 2026). Implicit GNNs and deep equilibrium models typically guarantee a unique fixed point through contraction or monotonicity (Scarselli et al., 2009; Bai et al., 2019; Gu et al., 2020; Liu et al., 2021); we show that this can miss every valid solution of a multi-solution task (Theorem 3). Jore & Liu (2026) introduced attractor-based representations of set-valued maps with nonparametric theory; we establish their realization by message-passing GNNs under permutation symmetry, where nodes must be told apart by the evolving state itself (Theorem 2). Distributional solvers instead learn a sampler (Karalias & Loukas, 2020; Sanokowski et al., 2023; Sun & Yang, 2023); we learn one autonomous update whose fixed points are the solutions, so each output can be checked by its residual, training needs no solution labels, and iterations can be extended at test time. Symmetry-breaking methods augment the input (Smidt et al., 2021; Dwivedi et al., 2022; Lawrence et al., 2025); our model needs no auxiliary input. Appendix M gives a detailed discussion.

W2 + Q2.

"Experiments seem built from scratch; how does the model do on standard CO tasks (VAG-CO / DIFUSCO)?"

Two of our three tasks are built on established data.

  • Chemistry uses the published reaction-network structures of Yao et al. (2025), with their original train/validation/test splits. Their dataset labels each network by whether it can admit several steady states; these labels give no rate constants and no steady-state concentrations. We instead predict the steady-state concentrations themselves for given rate constants, which is a harder task: each output can be checked against the steady-state equations, and two distinct outputs that both satisfy them give direct, checkable evidence of multistationarity, whereas a classification results (multi- or single-stationary) gives no steady state.
  • PROTEINS uses all 1,113 standard TUDataset graphs and replaces graph classification with modularity maximization (Newman, 2006).

New: a standard CO benchmark, run in its native environment (Appendix L, pages 61–62). Following your suggestion, we added maximum independent set (MIS) on IMDB-BINARY. MIS is the graph CO task shared by both papers you mention (VAG-CO and DIFUSCO), and IMDB-BINARY MIS is a VAG-CO benchmark with a released implementation. We could therefore run VAG-CO with its own code and recipe, and train DIFUSCO on the same split, instead of re-implementing either. These real-world graphs often have many maximum independent sets, so the benchmark also tests diversity directly; every reported solution is checked against the certified optimum.

MethodTraining signalParamsApprox. ratio (%) ↑\uparrowDistinct optimal sets D20D_{20} ↑\uparrowTime (ms/graph) ↓\downarrow
Oursenergy26k100.00016.961.89
DIFUSCO (large)optimal labels5.3M100.00015.24274
VAG-COenergy + entropy (RL)124k100.00011.139.23
DIFUSCO (small)optimal labels94k99.9999.9826.2
FF10 (untied control)energy464k100.0001.001.94

Most distinct optimal solutions, at the lowest cost. All methods reach essentially optimal set size, so the comparison is decided by diversity and cost. Ours finds the most distinct maximum independent sets, 16.96 among 20 candidates, versus 15.24 for the closest competitor (DIFUSCO large) and 11.13 for VAG-CO. It is about 145×145\times faster than DIFUSCO (large) and 4.9×4.9\times faster than VAG-CO, with about 200×200\times fewer parameters than DIFUSCO (large) and no labels.

AuthorsOpenReview ↗

Rebuttal (Part 2)

Q1.

"Fig. 3: why does the single-target model collapse without contraction? Is it oversmoothing?"

Short answer: it is not oversmoothing, and the cause is the training target, not the architecture (Section 3, page 5; Appendix D.2, page 44).

What the collapse looks like. In the toy task, each graph is a weighted triangle with exactly three valid solutions; in solution kk, the source sits at node kk, so its source coordinates are b=ekb=e_k (e1=(1,0,0)e_1=(1,0,0), e2=(0,1,0)e_2=(0,1,0), e3=(0,0,1)e_3=(0,0,1)). The single-target states do not shrink to 00. They converge to the average (centroid) of the three solutions: on the graph of Fig. 3, the source coordinates settle at b≈(0.332,0.335,0.331)≈(13,13,13)b\approx(0.332,0.335,0.331)\approx(\tfrac13,\tfrac13,\tfrac13). This point is not itself a solution, which is why Fig. 3 shows it visibly separated from all three.

Why the training target produces this point. Single-target supervision must commit to one solution per training graph and train the output toward it with mean squared error (MSE). When a graph has several equally valid solutions, nothing in the task says which one should be the label; in practice, it is whichever solution a solver happens to return. The control in Fig. 3 models this situation: for each training graph, one of its three solutions is drawn uniformly at random once and then kept fixed for all initializations and epochs.

From the network's point of view, the same graph is then labeled e1e_1, e2e_2 or e3e_3 with no rule linking the graph to the label, so the label cannot be predicted from the input. Under MSE, the best possible answer to an unpredictable label is its average: if the label is e1e_1, e2e_2 or e3e_3 with equal chance, the output that minimizes the expected squared error is 13(e1+e2+e3)=(13,13,13)\tfrac13(e_1+e_2+e_3)=(\tfrac13,\tfrac13,\tfrac13), exactly the observed endpoint. This best answer is the same for every initialization, so training produces a single attractor at the centroid, even though nothing in the architecture enforces a unique equilibrium.

How we tested this explanation. We kept the architecture (without contraction) and the MSE loss fixed, and changed only how the target is chosen:

  • Random (the Fig. 3 control): one of the three solutions, drawn uniformly once per training graph, as above.
  • Fixed rule: the target is always the solution whose source is the node of highest weighted degree. The label is now a deterministic function of the graph, so it can in principle be learned; however, the rule jumps from one solution to another wherever two degrees tie.
  • Any solution in the set: the loss is the squared distance to whichever of the three solutions is nearest to the model's output, so no single target is designated. This is also multi-attractor training, but it requires knowing the full solution set of every training graph.

We also added the two standard remedies against oversmoothing to the Fig. 3 control. Oversmoothing means that repeated neighborhood averaging makes all node features alike, and it is usually countered by carrying each node's own information forward: an identity recurrent skip adds the network output to the node's current state at every step, and hidden residual connections add each node's features to their update inside every layer.

Results (Appendix D.2, Table 5): same architecture without contraction; 1,000 held-out graphs, 128 random starts per graph, 3 training seeds. A trajectory recovers a solution if it settles within a small error of an exact solution.

Training targetTrajectory recovery (%)Graphs with all 3 solutions (%)
Random designated target (Fig. 3 control)0.000.00
\quad evaluated on its own training graphs0.000.00
\quad + identity recurrent skip0.000.00
\quad + hidden residual connections0.000.00
Fixed rule (source at the highest-degree node)32.40.00
Any solution in the set (multi-attractor, supervised)97.6595.97
Ours (multi-attractor, energy-trained, no labels)99.7199.40
AuthorsOpenReview ↗

Rebuttal (Part 3)

What the table shows:

  • It is not oversmoothing. If node states were becoming alike, the two remedies would restore distinct node states and hence the solutions. Recovery stays at 0%.
  • It is not a generalization problem. The control fails even on the graphs it was trained on.
  • Changing only the target fixes it. With the same MSE loss and the same architecture, accepting any solution instead of one designated solution gives 97.65% recovery, and all three solutions are found on 95.97% of graphs. The same network can therefore keep nodes apart and hold several attractors without difficulty; what prevents it is the requirement to select one solution.
  • The harder the selection, the worse the result. A random choice cannot be learned at all (0%). The deterministic but discontinuous highest-degree rule is learned by only one of three training seeds (32.4% recovery on average), which fails mainly near degree ties, and even that seed finds only one solution per graph. Accepting the whole set needs no selection and is learned reliably.

Take-away. This is the point made in Section 1: single-target training "arbitrarily favors one equally valid solution." Learning the solution set requires only information about the task, whereas a designated target additionally asks the network to learn which solution to output, and the less regular that choice, the harder it is to learn: recovery falls from about 98% when any solution is accepted, to 32% with the highest-degree rule, to 0% with a random choice.

Finally, "any solution in the set" is itself a multi-attractor objective, but it requires the full solution set of every training graph, which is rarely available in practice. This is why we train with an energy instead: it needs no labels and lets the model discover several solutions on its own.

Reviewer_qRh5OpenReview ↗
Rating
3(+1)
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper addresses the set-valued mapping problem in GNNs, where a single graph input may correspond to multiple valid solutions. In theory, this article proves the existence of equivalent multi-attractor dynamics, which can approximate the effective solution set from random initialization and provide an impossible result for the contraction model (Theorem 3). Based on experience, this method has been evaluated in terms of finding the ground state of the Ising model, detecting protein structural modules, and using problem-specific energy/residual functions for unsupervised training to identify chemical reaction steady states.

Critical strengths

This is a solid theory work.

Critical weaknesses
  1. The theoretical foundation (Theorems 1 and 2) relies on a non-smooth, hand-crafted operator construction involving a graph-dependent switching set, a nearest-solution selector, and a damping term. However, the paper lacks empirical evidence to show that the trained networks actually approximate these specific dynamics. The connection between the representational theory and the learned models relies on loose analogies. In addition, Theorem 2 requires the node state dimension to be $q \ge 2 $, but some experiments have evaluated scalar node states that are not supported by established theoretical frameworks.

  2. The empirical results do not support the claim that both quality and diversity have a unified advantage. For example, in the Ising and protein tasks, DIFUSCO (Large) found a more obvious solution than the proposed method (with optimal solutions of 2.60 and 2.16 per image, and qualified partitions of 11.02 and 5.83, respectively), despite the low average energy/modular cost. The results actually show a balance of quality diversity, not strict dominance.

  3. The proposed method used large inference time and ran 200 to 5000 iterations for unfolding, whereas the baseline did not. This unfair comparison makes the parameter efficiency statement of the paper not very solid (for example, claiming that 'the parameter is lower than $\sim155 \times $'). To verify these claims, a fair comparison is needed.

  4. This paper lacks an ablation study to determine the source of gain. The toy experiment is purely qualitative, evaluating only one graph and one training seed, which is not enough to prove that multi-attractor dynamics is the main driving force for success.

Questions for authors

Could you compare the models based on the actual computation time or the total number of calculations? For example, could you provide a graph that plots the model's performance against the actual running time (or computation cost), comparing your method directly with baselines like DIFUSCO?

9 comments
AuthorsOpenReview ↗

Rebuttal (Part 1)

We thank the reviewer for the careful reading and the constructive questions, in particular on runtime, on the link between theory and the trained models, and on ablations. They led to several new experiments; our responses are below, and all revisions are marked in blue in the paper.

Question + W3.

"200–5,000 iterations make the comparison unfair; please plot performance vs. actual runtime, comparing your method directly with baselines like DIFUSCO."

Long horizons verify convergence; they are not needed for performance. We would first like to clarify that the 200–5,000 iterations in the appendix serve only to meet a strict numerical convergence criterion: the state must change by less than a small tolerance between consecutive steps (e.g., RMS change <10−4<10^{-4} on Ising). These runs verify our theory, which concerns where the dynamics converge; they are not the best choice in practice. In practice, even t=5t=5 or 1010 already gives high-quality solutions.

New Figure 4: hit rate versus measured runtime. Following the reviewer's request, we added Figure 4 (page 10 of the revised paper), which plots hit rate against measured wall-clock time per graph for our method and every baseline, including DIFUSCO. The hit rate is the percentage of the MM candidates per graph that are high-quality solutions: within 10% of the optimal energy (Ising) or optimal modularity (PROTEINS), or with physical residual ≤10−3\le10^{-3} (chemistry). It therefore measures how reliably each random start yields a good solution, which is the relevant quantity for a solver that returns multiple candidates. For convenience, we summarize the three panels below (entries: hit rate @ time per graph):

TaskMethodTime / stept = 5t = 20Best over all t
IsingOurs2.9 ms62.8% @ 0.015 s82.2% @ 0.058 s83.8% @ 0.58 s (t=200)
DIFUSCO-matched3.1 ms24.0% @ 0.016 s37.9% @ 0.063 s41.8% @ 0.31 s (t=100)
DIFUSCO-large67 ms50.2% @ 0.34 s67.8% @ 1.3 s70.7% @ 6.7 s (t=100)
Best other baseline (Feedforward ×10)———70.9% @ 0.029 s
PROTEINSOurs33 ms60.9% @ 0.17 s73.8% @ 0.67 s78.0% @ 6.7 s (t=200)
DIFUSCO-matched38 ms17.9% @ 0.19 s38.0% @ 0.76 s41.9% @ 3.8 s (t=100)
DIFUSCO-large104 ms34.3% @ 0.52 s69.3% @ 2.1 s74.9% @ 10.4 s (t=100)
Best other baseline (Feedforward 15 MP)———54.7% @ 0.17 s
ChemistryOurs5.7 ms0.4% @ 0.030 s8.6% @ 0.11 s83.8% @ 1.1 s (t=200)
DDPM / DDIM / DIS-matched (best of 3)4.4–7.5 ms0.01% @ 0.024 s0.00% @ 0.09–0.15 s0.04% @ 1.5 s (DIS, t=200)
DDPM / DDIM / DIS-large (best of 3)7.5–12.7 ms0.00% @ 0.04–0.06 s0.01% @ 0.23 s0.02% @ 0.74 s (DIS, t=100)
Best other baseline (single-target recurrent)5.7 ms0.2% @ 0.029 s1.2% @ 0.11 s18.8% @ 1.1 s (t=200)

In all three tasks, a short horizon of ours already beats every baseline's best result over its entire sweep:

  • Ising: t=10t=10 gives 77.4% @ 0.029 s. This beats DIFUSCO-large's best (70.7% @ 6.7 s) with 230× less time, and Feedforward ×10 (70.9%) at the same time.
  • PROTEINS: t=50t=50 gives 76.5% @ 1.7 s, beating DIFUSCO-large's best (74.9% @ 10.4 s) with 6.2× less time. Already at t=5t=5 (0.17 s), ours beats the best of every baseline other than DIFUSCO-large.
  • Chemistry: t=50t=50 gives 52.6% @ 0.29 s, beating the strongest baseline's best (single-target, 18.8% @ 1.1 s) with 3.9× less time. Every DDPM / DDIM / DIS model stays at ≤ 0.04% at every step count, and every feedforward model at ≤ 0.66%.

The paper's t=200t=200 is therefore a conservative setting chosen for convergence diagnostics, not a source of advantage.

AuthorsOpenReview ↗

Rebuttal (Part 2)

W1(a).

"No evidence the trained networks approximate the hand-crafted operator; the link is a loose analogy."

We added two kinds of evidence that the trained networks behave as the construction prescribes: a direct comparison with TGT_G in the toy, where TGT_G is known explicitly (Part 1), and tests on all four tasks of the properties the theory predicts (Part 2).

Part 1. Direct comparison with the construction (Appendix D.3, pages 44–45).

Theorems 1–2 are expressivity results; they do not claim that training recovers the constructed operator TGT_G. The toy example lets us check directly how close training comes. Its solution set S(G)S(G) has exactly three elements in closed form, and the state is only six-dimensional, so TGT_G is known explicitly. We compare the learned update with TGT_G at three levels: where trajectories start, which direction they move, and where they stop.

  • Where trajectories start: basins. The basin of a solution is the set of initial states whose trajectory converges to that solution; a basin map colors each initial state by the solution it reaches. Our construction TGT_G moves every state toward its nearest solution, so its basins are the nearest-solution (Voronoi) cells. The boundaries between basins are exactly the switching sets. We draw the basin maps of the learned GNN and of TGT_G on a 2D slice of initial states that contains all three solutions (41×41 grid). The two maps agree on 94.1% of the 1,681 initial states, and all disagreements lie in a band one grid cell wide along a basin boundary (Figure 6, page 45). The learned GNN therefore divides initial states among the solutions as the construction does, with its switching boundaries in the same places up to grid resolution.

  • Which direction to move: update direction. TGT_G moves each state straight toward its nearest solution P(y)P(y): TG(y)−y=β(G,y)(P(y)−y)T_G(y)-y=\beta(G,y) (P(y)-y) with a positive step size β(G,y)\beta(G,y). The theory therefore predicts cosine 1 between the learned update GNNθ(G,yt)−yt\mathrm{GNN}_\theta(G,y_t)-y_t and P(yt)−ytP(y_t)-y_t. We measure this cosine along trajectories on the test set with 32 Gaussian starts per graph (Table 6, Page 45 for details):

Training seed012
Mean cos⁡(GNNθ(G,yt)−yt, P(yt)−yt)\cos\big(\mathrm{GNN}_\theta(G,y_t)-y_t,\ P(y_t)-y_t\big)0.9510.9000.950

In every seed, the learned update points almost exactly where the construction prescribes.

  • Where trajectories stop: fixed points. The attracting fixed points of TGT_G are the exact solutions. The learned fixed points lie within 1.7×10−41.7\times10^{-4} RMS of them (5 seeds, 1,000 test graphs) and are attracting: the Jacobian spectral radius is at most 0.113<10.113<1, so nearby states are pulled back.

In short, the learned GNN behaves as our theory describes: each trajectory commits early to a basin, moves toward the nearest valid solution, and settles at an attracting fixed point near that solution.

AuthorsOpenReview ↗

Rebuttal (Part 3)

Part 2. The trained networks have the properties the theory guarantees.

Why a direct comparison is possible only in the toy. The constructed operator TGT_G is defined through the entire solution set S(G)S(G): each step moves yy toward its nearest solution P(y)P(y), and the basins are the nearest-solution (Voronoi) cells of S(G)S(G). Comparing a learned update with TGT_G therefore requires (a) enumerating S(G)S(G) and (b) probing the update over the whole state space Rn×q\mathbb{R}^{n\times q}. In the scientific tasks, S(G)S(G) is not available in closed form, so TGT_G cannot be written down, and a toy-style comparison is not feasible.

What we test instead. The theory makes three predictions that can be checked without knowing TGT_G: (i) trajectories converge, (ii) their limits are stable attractors, and (iii) one network reaches several valid solutions. The original paper reported (i) and (iii) for the three main tasks; the revision adds (ii), a local-stability test of the learned fixed points on all four tasks (Appendix I, page 60).

Local stability test (new). At a fixed point y⋆y^\star of the learned update F(y)=GNNθ(G,y)F(y)=\mathrm{GNN}_\theta(G,y), a small deviation evolves as δt+1≈Jδt\delta_{t+1}\approx J \delta_t, where J=∂yF(y⋆)J=\partial_yF(y^\star) is the Jacobian. The deviation shrinks to zero if and only if the spectral radius ρ(J)=max⁡i∣λi(J)∣\rho(J)=\max_i|\lambda_i(J)| is below one. Hence ρ<1\rho<1 means that y⋆y^\star is locally attracting: an attractor with its own basin, as in our construction. We take the fixed points reached by converged trajectories from random starts on the test sets, refine each in float64 to residual ∥F(y⋆)−y⋆∥<10−10\|F(y^\star)-y^\star\|<10^{-10}, and compute ρ\rho from all eigenvalues of JJ.

PropertyToyIsingPROTEINSChemistry
(i) Converged trajectories100%100%99.5%96.1%
(ii) Locally attracting fixed points (ρ<1\rho<1)100%100%100%99.2%∗^\ast
ρ\rho: median [min, max]0.06 [0.032, 0.113]0.36 [0.003, 0.998]0.76 [7⋅10−87\cdot10^{-8}, 0.9999]0.90 [0.584, 1.00001]
(iii) Several solutions in one networkall 3 solutions on 99.56% of graphs≥ 2 distinct exact ground states on 68.7% of graphs≥ 2 distinct partitions within 0.10 of the optimal modularity on 80.8% of graphs≥ 2 distinct accepted predictions on 41.7% of graphs

∗^\astThe other 6 fixed points are marginal (ρ−1≤9×10−6\rho-1\le9\times10^{-6}). Sources: (i) and (ii) from Appendix I (Table 19); (iii) from Appendix D.1 and Tables 1–3.

Together, these results show the multi-attractor behavior the theorems describe: trajectories settle, almost every limit is a stable attractor, and one network reaches several valid solutions on most graphs. Since the distinct endpoints on a graph are attracting, they are distinct attractors of the same learned update, not artifacts of a finite horizon.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Revised paper uploaded

Dear Reviewers and AC,

We thank all reviewers for their constructive feedback. We have uploaded a revised version of the paper, with all changes marked in blue, and have responded to each reviewer individually. If our responses address your concerns, we would be grateful if you would consider updating your score; we are also happy to answer any further questions during the discussion period.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.