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

Sep 14, 2026cs.AI

Recurrent GraphNeural NetworkswithSet-BasedAggregation

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.

Blai Bonet

Universidad Simón Bolívar Caracas, Venezuela

Reachability Neural Network Verification Equivalence

Ask PDF

Mar 16, 2026cs.LG

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

We define an information-complexity property for aggregation functions, capturing a vast range of practical aggregations, and prove that any Message-Passing Graph Neural Network (MP-GNN) model with such aggregations induces only a polynomial number of equivalence classes on all graphs - while the number of non-isomorphic graphs is super-exponential (in number of vertices). Adding a familiar perspective, we observe that merely 2 iterations of Color Refinement (CR) induce at least an exponential number of equivalence classes, making the aforementioned MP-GNNs relatively infinitely weaker. Previous studies state that sum-aggregation MP-GNNs match full CR however they consider a weak, 'non-uniform', notion of distinguishing-power where each graph size may require a different MP-GNN to distinguish graphs up to that size. Our results concern both distinguishing between non-equivariant vertices and distinguishing between non-isomorphic graphs.

Eran Rosenbluth

RWTH Aachen University

Message Passing Neural Networks Graph Neural Networks Expressivity

Ask PDF

Jul 29, 2026cs.LG

Universality and Approximation Rates of Graph Neural Networks with Random Features

We investigate message-passing graph neural networks with random node features. Random node features are known to enhance the expressiveness of graph neural networks (GNNs) both theoretically and empirically. Here, we establish a novel universality result focusing on permutation-equivariant neural networks (PENNs), a class of GNNs built from feedforward neural network components that subsumes many prominent GNN architectures. We show that PENNs, combined with partially random node features, can approximate arbitrarily well in probability any measurable permutation-invariant or permutation-equivariant function on directed graphs of fixed size with multidimensional node and edge features. For

k

-times continuously differentiable functions,

k\geq 2

, we also derive upper bounds on the approximation rates, relating the complexity of the feedforward components of a PENN in terms of layer depth and number of nonzero weights to the desired approximation accuracy.

Lukas Gonon, Thilo Meyer-Brandis, Niklas Weber

School of Computer Science University of St. Gallen St. Gallen, 9000, Switzerland · Department of Mathematics LMU Munich Munich, 80333, Germany

Graph Neural Networks Atom-Averaged Features Neural Approximations Approximation Neural Network Equivariant Neural Networks+1

Ask PDF