Research map / Graph learning / GNN architectures

The Cost of Symmetry: Universality and Hardness for Permutation-Invariant Neural Networks

NeurIPS 2026 · Graph learning › GNN architectures · approach: Physics-inspired GNNs

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Unifies permutation-invariant architectures (DeepSets, Set Transformers, GNNs, k-GNNs) under a complexity-theoretic framework of noisy symmetric circuits, characterizing their universality and hardness by interaction order k.

Problem

Permutation-invariant neural architectures are studied individually, with no unified theory of their expressive power and the cost of enforcing symmetry.

Approach

Proposes noisy symmetric circuits as a single complexity-theoretic framework in which each architecture sits at a level k of a hierarchy indexed by the order of interactions it captures, and uses it to characterize universality and hardness.

Experimental setup

Builds on: DeepSets Set Transformers k-GNNs

Closest papers by meaning

• Beyond the Permutation Symmetry of Transformers: The Role of Rotation for Model Fusion (ICML 2025 · similarity 0.89)
• On the hardness of learning under symmetries (ICLR 2024 · similarity 0.88)
• On Making $SE(2)$-Invariant Networks Optimal (NeurIPS 2026 · similarity 0.88)
• Symmetry Induces Structure and Constraint of Learning (ICML 2024 · similarity 0.87)
• On Universality Classes of Equivariant Networks (NeurIPS 2025 · similarity 0.86)
• When GNNs meet symmetry in ILPs: an orbit-based feature augmentation approach (ICLR 2025 · similarity 0.86)