CS Paper Radar

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

Jialin Liu

cs.LG cs.AI ·submitted 2026-09-28 14:29 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Improving fine-grained expressivity of graph neural networks

cs.LG cs.AI ·2026-11-15 ·Yonatan Sverdlov
similarity 0.66
Abstract

This thesis investigates the expressive power of neural networks for structured data, focusing on graph neural networks and symmetry-aware architectures. We present four main contributions. First, we characterize the generic expressive power of geometric message-passing neural networks on sparse graphs and introduce EGenNet, an architecture achieving the corresponding guarantees. Second, we use representation theory to characterize linear layers equivariant to multiple permutations, including wreath-product symmetries. Third, we study permutation-invariant set representations that preserve containment, establish dimensional bounds and impossibility results, and introduce MASNet. Finally, we propose FSW-GNN, a message-passing architecture combining strong expressivity and bi-Lipschitz stability guarantees with strong empirical performance on long-range graph-learning tasks. Together, these results provide a broader understanding of how neural architectures can preserve the geometric, algebraic, order-theoretic, and metric structure of their inputs.

0.09

Emergence of Fibrations, Compression, and Symmetry Breaking in Artificial Neural Networks

cs.LG ·2026-09-01 ·Osvaldo M Velarde, Lucas C Parra, Alireza Hashemi, Hernan A Makse
theory similarity 0.58
Abstract · 11 Figures

Artificial neural networks are often regarded as powerful yet opaque black boxes. Here, we demonstrate that learning in deep neural networks generates local symmetries known in graph theory as fibrations and coverings. We prove that covering symmetries are stable attractors of stochastic gradient descent. Consistent with this theory, we report the emergence of covering symmetries across major network architectures, including multilayer, convolutional, recurrent, and transformer networks. Exploiting these symmetries enables drastic model compression - reducing networks to 17% of their original size without sacrificing performance. Furthermore, controlled breaking of covering symmetry overcomes the loss of plasticity, achieving state-of-the-art performance in continual learning. The theoretical results provide a new foundation for AI systems based on symmetries that convert black boxes into interpretable colored graphs and enable more efficient inference and lifelong learning.

0.38

Recurrent Graph Neural Networks with Set-Based Aggregation

cs.AI ·2026-09-14 ·Blai Bonet
similarity 0.58
Abstract

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.

0.27

Columnar-Embedder: A Biologically Inspired Cortical Architecture for Binary Sparse Distributed Graph Representations

cs.NE ·2026-08-12 ·Mohamed Abidalrekab, Dan Hammerstrom
similarity 0.58
Abstract

Finding a representative description of graph entities that captures their structural roles and homophily is a challenging goal for graph embedding techniques due to the non-Euclidean nature of graphs. Traditionally, Graph embeddings achieve top performance via random-walk methods and graph neural networks. However, these methods are transductive and utilize an expensive global optimization via softmax or a dense representation trained in an end-to-end pipeline with gradient descent. Nonetheless, other variants of GNNs can map to unseen nodes; they still rely on iterative message passing and backpropagation, incurring high computational and memory costs. Conversely, the mammalian cortex solves structurally similar problems by learning to map its input stream of patterns into a compact representation for downstream regions. We present the biologically inspired Columnar-Embedder architecture for learning binary Sparse Distributed Representations (SDRs) of graph nodes. The learning is driven by a local Bienenstock-Cooper-Munro (BCM) Hebbian rule modulated by positive pointwise mutual information (PPMI) computed from online streams of random walks. Continuous learning from streaming random-walk pairs without labels, backpropagation, or supervision enables the architecture to exhibit natural resistance to catastrophic forgetting. Across five graph benchmarks, the performance of SDRs is competitive with that of real-valued dense embeddings on node classification and link prediction, while the architecture exhibits portability, resilience to noise, and robustness to data corruption.

0.04

Fixed Points Without Fixed Diffusion: Implicit Neural Sheaves for Convergent Test-Time Computation

cs.LG ·2026-08-12 ·Rémi Bourgerie, Šarūnas Girdzijauskas, Viktoria Fodor
publishedtheory similarity 0.57
Abstract · Accepted at the 5th Learning on Graphs Conference (LoG 2026)

Implicit Graph Neural Networks (IGNNs) define node representations as fixed points of graph neural operators, enabling effectively infinite-depth propagation, iteration-independent parameterization, and flexible test-time computation. Yet these benefits depend on the equilibrium being unique and reached by fixed-point iteration. Existing constructions often impose constraints on recurrent updates to obtain these guarantees, limiting the transformations available at equilibrium. This raises a central question: can IGNNs gain expressiveness through richer, edge-dependent transformations while retaining the inherent strengths of their equilibrium formulation? We introduce SheafDEQ, a subhomogeneous deep-equilibrium architecture with adaptive neural-sheaf propagation. Its learned, matrix-valued sheaf restriction maps can align, mix, or reverse neighbouring representations. Under mild regularity conditions, we prove that SheafDEQ admits a unique equilibrium reached globally by fixed-point iteration from any positive initial state. Contractivity further guarantees convergence under bounded communication staleness. We evaluate SheafDEQ on distributed-inference tasks requiring repeated nonlocal aggregation and on community detection whose rewiring increasingly favours cross-community interactions. SheafDEQ improves over implicit baselines on Sums, MNIST Terrain, and Coordinates, and on community detection as connectivity becomes increasingly heterophilic. SheafDEQ remains competitive with recurrent models without equilibrium guarantees. Continued-iteration diagnostics show decreasing residuals and retained test accuracy through 100 iterations, unlike the finite-horizon control, while delayed-update experiments show low sensitivity to bounded communication staleness.

0.49

On the Number of Observation Nodes in Recurrent Neural Networks with Linear Threshold and ReLU Functions

eess.SY ·2026-08-30 ·Liangjie Sun, Wai-Ki Ching, Tatsuya Akutsu
theory similarity 0.56
Abstract

This paper investigates how node update rules and admissible state domains affect the minimum number of observation nodes required for global finite-horizon observability in recurrent neural networks with linear-threshold and ReLU update functions. Over a common binary state domain, we construct a class of $K$-linear-threshold ($K$-LT) networks whose initial states can be uniquely reconstructed from the finite output trajectory of a single observation node. We further establish a dynamical equivalence between binary-valued $K$-ReLU networks and $K$-AND Boolean networks, which transfers existing class-level observation-node bounds to binary-valued $K$-ReLU networks. For nonnegative-valued ReLU networks, the observability problem reduces to the classical linear-system setting whenever the relevant pre-activations remain nonnegative. For general real-valued ReLU networks, we prove that global finite-horizon observability requires at least $n/2$ observation nodes when no restriction is imposed on the number of state variables involved in each node update. This lower bound is tight when $n=2K$, for which we construct a $K$-ReLU network observable from exactly $K$ nodes. These results show that both update rules and state domains fundamentally affect extremal observation requirements: temporal evolution can concentrate finite-state information into a single measured trajectory, whereas activation-induced rank loss creates an intrinsic sensor lower bound in continuous-state ReLU networks.

0.29

A Unifying Relational Perspective on Expressive Lottery Tickets

cs.LG stat.ML ·2026-08-19 ·Lorenz Kummer, Samir Moustafa, Anatol Ehrlich, Franka Bause, Marco Nennstiel +2 more
publishedtheory similarity 0.56
Abstract · ICML 2026

Graph neural networks (GNNs) are widely used, but how parameter sparsity affects the expressivity of relational (RGNNs) and temporal (TGNNs) variants is poorly understood. The Strong Expressive Lottery Ticket Hypothesis (SELTH) posits the existence of sparse GNNs that preserve Weisfeiler-Leman (WL) expressivity on static graphs. We generalize this existence result to a probabilistic statement for multi-relational and temporal domains via the relational WL (RWL). We prove that sufficiently parameterized RGNNs contain sparse subnetworks that maintain 1-RWL expressivity and derive a lower bound on the probability that a random pruning yields such a subnetwork. We show that common TGNNs and cross-graph message passing schemes admit RGNN reformulations such that they inherit these guarantees and, moreover, that the expressivity of a sparse RGNN is connected to its optimization behavior under common update regimes. Experiments instantiate the bound, compare it to empirical probabilities on synthetic data, and study how pre-training expressivity relates to optimization and prediction quality metrics on temporal and molecular benchmarks.

0.23

Temporal Geometry of Deep Networks: Hyperbolic Representations of Training Dynamics for Intrinsic Explainability

cs.LG cs.AIcs.NEphysics.data-an ·2026-10-02 ·Ambarish Moharil
top venue similarity 0.56
Abstract · Published as a main conference paper at ICLR 2026. 10 Main Pages, 22 pages of supplementary material

Intrinsic explainability remains a challenging problem, particularly in contexts where multilayer perceptrons (MLPs) require dynamic re-training within an optimization environment. This paper investigates how MLPs and their training dynamics can be represented and studied in non-Euclidean spaces; our representation features the Poincaré model of hyperbolic geometry. We aim to capture the geometric evolution of their weighted topology and self-organization over time. Instead of restricting the analysis to single checkpoints---as per established measure-based explainability methods---we construct temporal \textit{parameter graphs}, i.e., snapshots over time $T$ steps of the optimization/training process for MLPs. This reflects the view that neural networks encode information not only in their weights but also in the trajectory traced during training. Drawing on the idea that many complex networks admit embeddings in hidden metric spaces where distances correspond to connection likelihood, we present a geometric and temporal graph-based metalearning framework for obtaining dynamic hyperbolic representations of the underlying neural parameter graphs. Our model embeds temporal parameter graphs in the Poincaré model ball, and learns from them while maintaining equivariance to within-snapshot neuron permutations and invariance to permutations of past snapshots. In doing so, the approach preserves functional equivalence over time and recovers the latent evolving geometry of the network. Experiments on regression and classification tasks with trained MLPs show strong meta-network performance, accompanied by hyperbolic temporal representations. This reveals how the network structure emerges over time under specific training environments, thus providing insights into the network's self-organization.

0.55