arXiv:2605.13690cs.LGcs.AI2026-05

揭示超图神经网络表达能力的极限,提出宽度墙理论。

The WidthWall: A Strict Expressivity Hierarchy for Hypergraph Neural Networks

  • 用同态密度衡量结构模式出现频率,构建表达能力分级体系。
  • 发现任何固定深度模型都无法捕捉超过其宽度限制的高阶信息。
  • 适合研究超图建模、模型表达力分析的学者参考。

超图天然适用于建模科学、社交和生物系统中的高阶交互。超图神经网络(HGNN)旨在从这类数据中学习,但其能表示的高阶结构尚不明确。本文表明,超图表达能力取决于架构能否检测和计数小型结构模式。通过同态密度(homomorphism densities)量化结构基元在超图中的出现频率,结合经典同态计数完备性与不变量近似理论,我们证明同态密度可生成所有连续超图不变量,并按超树宽(hypertree width)组织成严格层级。由此得出“宽度墙”(Width Wall):无论隐藏维度多大、训练方式如何或层数固定,任何HGNN都无法表示需要更宽结构模式的不变量。本框架统一刻画了15种HGNN架构,精准识别出团展开(clique expansion)所丢失的信息,并启发设计密度感知模型以突破有限宽度消息传递的表达瓶颈。我们在真实世界超图节点分类任务套件上验证该发现,结果表明宽度墙能准确预测图简化基线失效的场景,以及密度特征带来提升的时机。

原文摘要 · Abstract (English)

Hypergraphs provide a natural framework to model higher-order interactions in scientific, social, and biological systems. Hypergraph neural networks (HGNNs) aim to learn from such data, yet it remains unclear which higher-order structures these models can represent. We show that hypergraph expressivity is governed by which small patterns an architecture can detect and count. We formalize this via homomorphism densities, which measure how often a structural motif appears in a hypergraph. Combining classical homomorphism-count completeness with invariant approximation, we show that homomorphism densities generate all continuous hypergraph invariants and organize them into a strict hierarchy indexed by hypertree width. This yields a Width Wall: a fundamental architectural limit beyond which no hidden dimension, training procedure or fixed-depth HGNN can represent invariants requiring wider patterns. Our framework provides a unified characterization of 15 HGNN architectures, precisely identifies information lost by clique expansion, and motivates density-aware models that extend expressivity beyond bounded-width message passing. We experimentally validate this finding on an APPLICATION NODE CLASSIFICATION SUITE of real-world hypergraphs, where the Width Wall predicts when graph-reduction baselines fail and when density features help.

超图神经网络表达能力结构模式宽度墙

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。