Pith Number

pith:ONZGOQM4

pith:2026:ONZGOQM42J6QA3OOYSABTUT3YR

not attested not anchored not stored refs resolved

The WidthWall: A Strict Expressivity Hierarchy for Hypergraph Neural Networks

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

Hypergraph neural networks cannot represent invariants beyond a fixed hypertree width.

arxiv:2605.13690 v1 · 2026-05-13 · cs.LG · cs.AI

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{ONZGOQM42J6QA3OOYSABTUT3YR}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

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.

C2weakest assumption

That homomorphism densities together with invariant approximation fully capture the continuous invariants relevant to HGNN expressivity and that the resulting hierarchy is strict for every architecture considered.

C3one line summary

Hypergraph neural networks obey a strict expressivity hierarchy indexed by hypertree width, creating a Width Wall that no fixed-depth model, hidden dimension, or training procedure can cross for wider patterns.

References

72 extracted · 72 resolved · 2 Pith anchors

[1] Absil, Robert Mahony, and Rodolphe Sepulchre.Optimization Algorithms on Matrix Manifolds 2008

[2] Ranking via sinkhorn propagation 1925 · arXiv:1106.1925

[3] Gupta, Stevan Rudinac, and Marcel Worring 2010

[4] Parameter-free hypergraph neural network for few-shot node classification.Advances in Neural Information Processing Systems (NeurIPS), 2025 2025

[5] Peter L. Bartlett, Dylan J. Foster, and Matus J. Telgarsky. Spectrally-normalized margin bounds for neural networks. InAdvances in Neural Information Processing Systems (NeurIPS), 2017 2017

Receipt and verification

First computed	2026-05-18T02:44:16.958155Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

737267419cd27d006dcec48019d27bc442a195006f56a37d51bef15cf9a0cf51

Aliases

arxiv: 2605.13690 · arxiv_version: 2605.13690v1 · doi: 10.48550/arxiv.2605.13690 · pith_short_12: ONZGOQM42J6Q · pith_short_16: ONZGOQM42J6QA3OO · pith_short_8: ONZGOQM4

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/ONZGOQM42J6QA3OOYSABTUT3YR \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: 737267419cd27d006dcec48019d27bc442a195006f56a37d51bef15cf9a0cf51

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "115e16bca46a1d3feb9a42ff7f73d7b13f09e8168534881910127ab29e941cf1",
    "cross_cats_sorted": [
      "cs.AI"
    ],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "cs.LG",
    "submitted_at": "2026-05-13T15:43:31Z",
    "title_canon_sha256": "0a9d963a621e306dae82d111ae450d6fe7b193e3fe13a55a231a5130ff9d1c1d"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.13690",
    "kind": "arxiv",
    "version": 1
  }
}