Graph neural networks find multiple valid solutions with different starts
Multi-Attractor GNNs: Set-Valued Expressivity Beyond Unique Equilibria
Machine LearningArtificial Intelligence
Summary
Many problems involving graphs can have multiple correct answers rather than just one. Existing graph neural networks usually find only a single solution, which can be limiting. The authors show that by letting the network settle into different stable states from different starting points, it can represent multiple valid solutions at once. Their method keeps the symmetry of graphs but can still distinguish nodes during processing without extra labels. They test this on real scientific problems and get several good answers that are better on average than methods that find only one.
What this means in practice
- •For software engineers for molecular modeling: Generate multiple plausible protein structure modules from the same input graph using a single trained graph neural network.
- •For chemical process simulation teams: Produce multiple valid predictions of chemical reaction steady states with better average quality than single-solution network approaches.
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.