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

arXiv: https://arxiv.org/abs/2609.35274 · HTML: https://mlsanity.com/paper/2609.35274/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 70 references that are in the map.
- First posted on arXiv 28 Sep 2026.

## Builds on (most cited first, 18 of 18)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (2015)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Hopfield Networks is All You Need](https://mlsanity.com/paper/2008.02217/) (2020)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Neural Execution of Graph Algorithms](https://mlsanity.com/paper/1910.10593/) (2019)
- [Expressiveness and Approximation Properties of Graph Neural Networks](https://mlsanity.com/paper/2204.04661/) (2022)
- [Symmetry Breaking and Equivariant Neural Networks](https://mlsanity.com/paper/2312.09016/) (2023)
- [Annealed Training for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2207.11542/) (2022)
- [A simple yet effective baseline for non-attributed graph classification](https://mlsanity.com/paper/1811.03508/) (2018)
- [Neural Learning of One-of-Many Solutions for Combinatorial Problems in Structured Output Spaces](https://mlsanity.com/paper/2008.11990/) (2020)
- [Convergent Graph Solvers](https://mlsanity.com/paper/2106.01680/) (2021)
- [Equivariant Flow Matching for Symmetry-Breaking Bifurcation Problems](https://mlsanity.com/paper/2509.03340/) (2025)
- [Universality and Approximation Rates of Graph Neural Networks with Random Features](https://mlsanity.com/paper/2607.26699/) (2026)
- [Any-Subgroup Equivariant Networks via Symmetry Breaking](https://mlsanity.com/paper/2603.19486/) (2026)
- [Bifurcation Models: Learning Set-Valued Solution Maps with Weight-Tied Dynamics](https://mlsanity.com/paper/2605.07277/) (2026)

## Abstract (arXiv)

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.