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

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.