The Width Wall: A Strict Expressivity Hierarchy for Hypergraph Neural Networks

Fengqing Jiang Yuetai Li Yichen Feng Kaiyuan Zheng, Luyao Niu Bhaskar Ramasubramanian Basel Alomair, Linda Bushnell Radha Poovendran · 2026

Read The Width Wall: A Strict Expressivity Hierarchy for Hypergraph Neural Networks by Fengqing Jiang Yuetai Li Yichen Feng Kaiyuan Zheng, Luyao Niu Bhaskar Ramasubramanian Basel Alomair, Linda Bushnell Radha Poovendran (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-13690.txt.

Description

Fengqing Jiang and eight colleagues show hyper-network power is ruled by which small patterns a design can detect and count. Joining hom-count fullness with fixed nearing, they show hom rates make all smooth hyper fixed traits, sorted in a strict ladder ranked by wide-tree width. That yields a Width Wall: no hidden size, training method or fixed-depth network can show fixed traits needing wider patterns. The frame joins 15 hyper designs, pinpoints info lost by clique growth, and motivates density-aware models beyond bounded-width message passing.

Catalog record

CREATORFengqing Jiang Yuetai Li Yichen Feng Kaiyuan Zheng, Luyao Niu Bhaskar Ramasubramanian Basel Alomair, Linda Bushnell Radha Poovendran
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE145951
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.13690

Browse the full library · About the Tower of Babel