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

Jialin Liu

cs.LGSep 28, 2026

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

Authors: Jialin Liu

Abstract

Recurrent and equilibrium graph neural networks (GNNs) often enforce a unique fixed point or use one training target per graph. Yet many combinatorial and scientific problems admit multiple valid solutions, with no preferred one. A designated target can then impose an arbitrary selection rule. For tasks invariant to node relabeling, a symmetric graph may have a symmetric solution set but no symmetric solution. We show that multiple equilibria enable one weight-tied message-passing GNN to represent set-valued equivariant maps: different initializations approach different valid solutions. Under stated regularity assumptions, we first construct globally Lipschitz, permutation-equivariant dynamics that converge almost surely to valid solutions and reach every solution branch with positive probability. We then establish approximate realization by recurrent message passing with continuous component maps, with arbitrarily small update and limiting errors and arbitrarily high probability. This goes beyond standard universality arguments: although message passing alone cannot distinguish symmetric nodes, the evolving state keeps nodes distinguishable at every finite step without auxiliary node identifiers. Such dynamics can be learned without solution labels using problem-specific energies. On Ising ground states, structural module detection in protein graphs, and chemical reaction steady states, the learned updates produce multiple high-quality predictions with high numerical convergence rates. They achieve better average solution quality than the tested unique-equilibrium, single-target, and feedforward baselines, while remaining competitive with much larger diffusion-based solvers.

Figures & tables

Figure 1. Different initializations can lead to different equilibria under the same recurrent GNN update, with the graph and model parameters held fixed.

Figure 2. One graph, three valid solutions to single-source diffusion. Left: the input graph, with edge weights labeled. Right: each choice of source gives a solution

f_{k}(G)=[H_{G}^{-1}e_{k}\ \ e_{k}]

. Node labels show

(u_{i},b_{i})

, with diffusion values rounded to four decimal places; orange marks the selected source (

b_{i}=1

). All three outputs are valid for the same input, which specifies no source.

Figure 3. Different initial states can approach different solutions under the same learned update. Each blue point represents one of 128 trajectories, plotted in source coordinates $((b_{t})_{1},(b_{t})_{2},(b_{t})_{3})$ ; magenta circles mark the three valid source indicators $e_{1},e_{2},e_{3}$ . Columns show recurrent steps $t=0,2,4,6,8$ . The multi-attractor model (top) forms three clusters near these targets, whereas the single-target-supervised (middle) and contractive (bottom) controls each concentrate away from them. All rows use the same held-out graph (test graph 0), training seed 1, and initial states.

Method	$\bar{e}\downarrow$	Hit10 $\uparrow$	$C_{200}\uparrow$	$D_{20}\uparrow$	$G_{20}\uparrow$
Ours	$-1.0794\pm 0.0028$	$83.98\pm 0.93$	$99.96\pm 0.02$	$2.16\pm 0.23$	$68.73\pm 5.19$
Single-target Supervision	$0.2077\pm 0.5878$	$9.45\pm 4.37$	$10.11\pm 3.38$	$0.10\pm 0.05$	$0.80\pm 0.99$
IGNN adapter (H16)	$-0.4581\pm 0.2538$	$5.20\pm 3.31$	$100.00\pm 0.00$	$0.03\pm 0.02$	$0.00\pm 0.00$
IGNN adapter (H32)	$-0.7516\pm 0.0185$	$8.00\pm 0.71$	$100.00\pm 0.00$	$0.06\pm 0.00$	$0.00\pm 0.00$
IGNN adapter (H64)	$-0.7954\pm 0.0143$	$13.20\pm 2.14$	$100.00\pm 0.00$	$0.08\pm 0.01$	$0.00\pm 0.00$
Feedforward ( $\times 1$ )	$-0.9720\pm 0.0035$	$36.13\pm 0.75$	–	$1.31\pm 0.03$	$36.67\pm 1.23$

Table 1. Ising results on 500 test graphs with 20 candidates per graph (mean

\pm

standard deviation over three training seeds).

\bar{e}

: mean energy per node (lower is better); Hit10: percentage of candidates within 10% of the certified minimum energy;

C_{200}

: percentage of trajectories converged by step 200;

D_{20}

: mean number of distinct optimal configurations found per graph, counting global spin flips separately;

G_{20}

: percentage of graphs with at least two such configurations, up to numerical tolerance. Details in Appendix E .

Method	$\overline{Q}_{G}\uparrow$	Hit10 $\uparrow$	$C_{200}\uparrow$	$D^{.10}_{20}\uparrow$	$G^{.10}_{20}\uparrow$
Ours	$0.5560\pm 0.0024$	$77.49\pm 2.06$	$88.05\pm 2.23$	$5.83\pm 0.38$	$80.78\pm 0.42$
Single-target Supervision	$0.4911\pm 0.0114$	$41.28\pm 7.16$	$50.81\pm 10.84$	$1.11\pm 0.08$	$33.03\pm 2.25$
IGNN (H16)	$0.4147\pm 0.0079$	$8.11\pm 2.65$	$100.00\pm 0.00$	$0.20\pm 0.04$	$0.00\pm 0.00$
IGNN (H32)	$0.4196\pm 0.0044$	$11.71\pm 2.21$	$100.00\pm 0.00$	$0.22\pm 0.03$	$0.00\pm 0.00$
IGNN (H64)	$0.4235\pm 0.0121$	$8.41\pm 2.36$	$100.00\pm 0.00$	$0.22\pm 0.06$	$0.00\pm 0.00$
Feedforward ( $\times 1$ )	$0.4436\pm 0.0048$	$16.52\pm 2.22$	–	$1.35\pm 0.23$	$30.93\pm 6.26$

Table 2. Structural module detection on 111 PROTEINS test graphs with 20 candidates per graph.

\overline{Q}_{G}

averages modularity over candidates and then graphs. For optimal modularity

Q_{G}^{\star}

, Hit10 is the percentage of candidates with relative gap

(Q_{G}^{\star}-Q_{G}(z))/|Q_{G}^{\star}|\leq 0.10

D^{.10}_{20}

: mean number of distinct partitions per graph with absolute gap

Q_{G}^{\star}-Q_{G}(z)\leq 0.10

;

G^{.10}_{20}

: percentage of graphs with at least two such partitions;

C_{200}

: percentage of trajectories numerically converged at

t=200

. Results: mean

\pm

standard deviation over training seeds 0/1/2 on the same test set. Full protocol in Appendix F .

Method	$\overline{E}_{\rm res}\downarrow$	Hit ${}_{10^{-3}}\uparrow$	$C\uparrow$	$D_{20}^{\rm raw}\uparrow$	$G_{20}^{\rm raw}\uparrow$
Ours	0.0188 $\pm$ 0.0046	83.77 $\pm$ 3.44	91.99 $\pm$ 0.35	3.506 $\pm$ 0.314	41.67 $\pm$ 17.01
Single-target Supervis.	0.0373 $\pm$ 0.0059	18.78 $\pm$ 3.88	88.48 $\pm$ 4.29	1.371 $\pm$ 0.137	11.30 $\pm$ 0.72
IGNN (H16)	0.1214 $\pm$ 0.0823	0.00 $\pm$ 0.00	100.00 $\pm$ 0.00	0.000 $\pm$ 0.000	0.00 $\pm$ 0.00
IGNN (H32)	0.1180 $\pm$ 0.0709	0.00 $\pm$ 0.00	100.00 $\pm$ 0.00	0.000 $\pm$ 0.000	0.00 $\pm$ 0.00
IGNN (H64)	0.0960 $\pm$ 0.0056	0.00 $\pm$ 0.00	100.00 $\pm$ 0.00	0.000 $\pm$ 0.000	0.00 $\pm$ 0.00
Feedforward ( $\times 1$ )	0.1082 $\pm$ 0.0081	0.00 $\pm$ 0.00	—	0.000 $\pm$ 0.000	0.00 $\pm$ 0.00

Table 3. Chemistry results on 236 test graphs with 20 candidates per graph.

\overline{E}_{\rm res}

: mean Huber penalty on the mass-action residual (lower is better); Hit

{}_{10^{-3}}

: percentage of final states with normalized physical residual

R\leq 10^{-3}

;

C

: percentage of recurrent trajectories with next-step log-concentration RMS change below

10^{-3}

T=200

;

D_{20}^{\rm raw}

: mean number of distinct accepted prediction clusters per graph;

G_{20}^{\rm raw}

: percentage of graphs with at least two. These count separated accepted predictions, not certified distinct roots. Entries: mean

\pm

population standard deviation over training seeds 0/1/2.

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4. $u$ -counterpart of Figure 3 : the same test graph, seed, 128 trajectories, methods, and time steps. Blue points show $[(u_{t})_{1},(u_{t})_{2},(u_{t})_{3}]$ ; magenta circles mark the three true solutions.

Level	Nodes	Mean nodes	Edges	Mean edges
Compact	6–55	26.972	9–135	61.068
Medium	136–253	189.174	360–693	510.918
Large	561–990	770.580	1584–2838	2195.904
Extra-large	2016–3916	2965.198	5859–11484	8667.174

Appendix

Table 4. Graph sizes.

Model	$H$	$L$	Parameters	LR	Epochs
Ours	16	3	3,153	$10^{-3}$	200
Single-target Supervision	16	3	3,153	$10^{-3}$	2000
IGNN adapter (H16)	16	3	2,851	$10^{-3}$	200
IGNN adapter (H32)	32	3	10,819	$10^{-3}$	200
IGNN adapter (H64)	64	3	42,115	$10^{-3}$	200
Feedforward ( $\times 1$ )	16	3	3,153	$10^{-3}$	200

Appendix

Table 5. Learned configurations.

H

: hidden width;

L

: total learned message passing depth.

$t$	$C_{t}$ (%)	Period 2–10 (%)	Unclassified (%)
5	$3.3733\pm 0.6370$	—	—
10	$32.5833\pm 2.0956$	—	—
20	$77.2733\pm 2.0129$	$0.0000\pm 0.0000$	$22.7267\pm 2.0129$
50	$97.7400\pm 0.2617$	$0.0000\pm 0.0000$	$2.2600\pm 0.2617$
100	$99.7100\pm 0.0638$	$0.0000\pm 0.0000$	$0.2900\pm 0.0638$
200	$99.9633\pm 0.0170$	$0.0000\pm 0.0000$	$0.0367\pm 0.0170$

Appendix

Table 6. Ising test-time dynamics. Percentages are means

\pm

population standard deviations across three training seeds.

Medium
Method	$\bar{e}\downarrow$	Best ${}_{20}\downarrow$	Hit10 (%) $\uparrow$	$V_{20}^{10\%}\uparrow$
Ours	$-1.2431$	$-1.2862$	$96.88$	$19.376$
Single-target Supervision	$1.5248$	$1.2913$	$0.00$	$0.000$
IGNN adapter (H16)	$0.5713$	$0.5713$	$0.00$	$0.000$
IGNN adapter (H32)	$-0.7917$	$-0.7917$	$0.00$	$0.000$
IGNN adapter (H64)	$0.0052$	$0.0052$	$0.00$	$0.000$

Appendix

Table 7. Scaling to larger Ising graphs with fixed model capacity. The proposed model retains its width-16 architecture and 3,153 parameters across medium, large, and extra-large datasets, each containing 500 test graphs. Metrics use 20 candidates per graph:

\bar{e}

and Best 20 are mean and best-of-20 energies per node; Hit10 is the percentage of candidates within 10% of the certified optimum; and

V_{20}^{10\%}

is the mean number of distinct configurations meeting this threshold. † marks training capped at 30 hours; OOM denotes a memory failure. ‡ marks supervised methods omitted because of training-labeling costs.

Split	Graphs	Nodes	Undirected edges
Train	891	4 / 36.53 / 24 / 620	5 / 67.98 / 46 / 1049
Validation	111	5 / 52.56 / 31 / 504	6 / 98.33 / 61 / 894
Test	111	8 / 45.84 / 32 / 285	16 / 86.15 / 57 / 424

Appendix

Table 8. Graph statistics. Entries for nodes and edges are min/mean/median/max.

Model	$H$	$L$	Parameters	LR	Updates
Ours	32	3	35,784	$3\cdot 10^{-4}$	3,500
Single-target Supervision	32	3	35,784	$3\cdot 10^{-4}$	3,500
IGNN (H16)	16	3	11,340	$3\cdot 10^{-4}$	3,500
IGNN (H32)	32	3	39,564	$3\cdot 10^{-4}$	3,500
IGNN (H64)	64	3	146,700	$3\cdot 10^{-4}$	3,500
Feedforward ( $\times 1$ )	32	3	35,784	$3\cdot 10^{-4}$	3,500

Appendix

Table 9. Learned configurations on PROTEINS.

H

: hidden width;

L

: total untied depth.

$t$	$C_{t}$ (%)	Period 2-10 (%)	Unclassified (%)
10	$3.83\pm 1.78$	–	–
20	$16.65\pm 3.45$	–	–
50	$47.18\pm 1.92$	–	–
100	$68.72\pm 0.82$	–	–
200	$88.05\pm 2.23$	$0.02\pm 0.02$	$11.94\pm 2.25$
500	$97.51\pm 0.45$	$0.39\pm 0.28$	$2.10\pm 0.34$

Appendix

Table 10. PROTEINS test-time dynamics. Metrics are the same as in Appendix E , Table 6 .

Split	Atom attempts	Joshi attempts	Atom feasible	Joshi feasible	Retained	Reactions
Train	790	2560	771	621	1242	6–19
Validation	180	570	172	133	266	6–18
Test	300	600	293	118	236	6–18

Appendix

Table 11. Dataset construction. Balance is enforced within each split after feasibility filtering. Every retained instance has two constructed witnesses.

Model	$H$	$L$	Parameters	LR	Epochs
Ours	32	3	35,716	$2\cdot 10^{-3}$	50
Single-target Supervision	32	3	35,716	$2\cdot 10^{-3}$	50
IGNN (H16)	16	3	10,273	$2\cdot 10^{-3}$	50
IGNN (H32)	32	3	37,441	$2\cdot 10^{-3}$	50
IGNN (H64)	64	3	142,465	$2\cdot 10^{-3}$	50
Feedforward ( $\times 1$ )	32	3	35,716	$2\cdot 10^{-3}$	50

Appendix

Table 12. Learned configurations for chemistry.

H

: hidden width;

L

: total untied depth.

$t$	$C_{t}$ (%)	Oscillatory (%)	Unresolved (%)
10	2.26 $\pm$ 0.65	—	—
20	13.77 $\pm$ 3.72	—	—
50	63.11 $\pm$ 2.05	—	—
100	83.99 $\pm$ 0.79	—	—
200	91.99 $\pm$ 0.35	1.75 $\pm$ 1.50	6.26 $\pm$ 1.27
500	95.20 $\pm$ 1.72	2.23 $\pm$ 1.70	2.56 $\pm$ 0.54

Appendix

Table 13. Chemistry test-time dynamics, mean

\pm

population SD across three training seeds.

C_{t}

is the fraction with next-step species log-state RMS change below

10^{-3}

. Oscillatory denotes detected approximate periods

2

–

64

among trajectories failing that criterion; unresolved is the remainder. All percentages use the full trajectory population, and the three categories partition that population for

t\geq 200

, up to rounding. Dashes denote unperformed early-horizon oscillation tests.

Explore similar work

Recurrent GraphNeural NetworkswithSet-BasedAggregation
Sep 14, 2026Blai BonetReachability Neural Network Verification
Universidad Simón Bolívar Caracas, Venezuela
Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks
Mar 16, 2026Eran RosenbluthMessage Passing Neural Networks Graph Neural Networks
RWTH Aachen University
Universality and Approximation Rates of Graph Neural Networks with Random Features
Jul 29, 2026Lukas Gonon, Thilo Meyer-Brandis, Niklas WeberGraph Neural Networks Atom-Averaged Features
School of Computer Science University of St. Gallen St. Gallen, 9000, Switzerland · Department of Mathematics LMU Munich Munich, 80333, Germany

Sep 14, 2026, cs.AIJ/K move · Enter open · S save

Recurrent GraphNeural NetworkswithSet-BasedAggregation

Blai Bonet

Universidad Simón Bolívar Caracas, Venezuela

Reachability Neural Network Verification Equivalence

Open paper AskPDF arXiv

Recurrent GNNs iterate message passing to convergence, and their logical characterizations to date rely on multi-set aggregation, graded (counting) logics, and halting or acceptance conditions that cannot be verified from the network's parameters. We study recurrent GNNs with set-based aggregation and identify sufficient conditions checkable from the weights for networks to compile into formulas and formulas into networks. The main result is an effective, two-directional equivalence between a class of networks and the Boolean closure of reachability and safety properties, the fragment B

Σ^{\circ}_1

of the modal

μ

-calculus. The fragment is not an artifact: it is the exact expressive level of stabilization over finite vocabulary, which supports fixed points of a single polarity and Boolean combinations thereof, but not the composition of fixed points of opposite polarities. The correspondence needs no counting logic, no external halting signal, and no non-effective acceptance condition, yielding a verifiable path from weights to symbolic explanations for networks meeting the conditions.

Abstract

Explore similar work

Recurrent GraphNeural NetworkswithSet-BasedAggregation

Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks

Universality and Approximation Rates of Graph Neural Networks with Random Features