acceptodds
Under review as a conference paper at ICLR 2027

The Width Wall: An Expressivity Framework for Hypergraph Neural Networks

Abstract

Hypergraphs provide a natural framework for modeling 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 structural distinctions their representations preserve. We study this question through homomorphism densities, which measure how often finite patterns map into a hypergraph. Combining homomorphism-count completeness with invariant approximation, we show that finite pattern densities generate a dense algebra of continuous hypergraph invariants and organize them into a filtration indexed by generalized hypertree width. This yields the notion of a Width Wall: when an architecture is provably restricted to width- information, no increase in hidden dimension, readout complexity, or optimization can recover distinctions erased beyond that representation. Our framework precisely characterizes information lost by clique expansion, with a Steiner–Pasch construction giving an explicit width-2 separator. We further study exact pattern-alignment invariants and introduce DensNet-D, which augments an incidence-based backbone with Monte Carlo estimates of local pattern densities. Experiments on four real-world node-classification benchmarks show that these structural features can recover information lost by projection and improve a matched AllDeepSets backbone.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Hypergraph Neural Networks, Hypergraph Expressivity, Invariant Representation Learning, Graph Neural Networks

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_tw7ROpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper proposes a framework to characterize which structural information hypergraph neural networks can capture, based on homomorphism densities of small patterns. The authors first show that, for hypergraphs with a fixed number of nodes, these densities are sufficient to approximate any continuous invariant, and then group them according to the generalized hypertree width of the patterns. This grouping defines the Width Wall: a model that can only access patterns up to a given width cannot distinguish hypergraphs that differ only in more complex patterns, regardless of its size or training. They also show that clique expansion already discards information visible at width 2. On the practical side, they describe a proof-of-concept architecture based on pattern alignment (InvNet) and evaluate DensNet-D, which adds Monte Carlo estimates of local pattern densities to an AllDeepSets backbone and improves it on four node-classification benchmarks.

Critical strengths

None

Critical weaknesses

The paper was not always easy for me to follow. At times the main ideas are hard to identify in the main text, and some details that would help understand the method are only given in the appendix. I think a clearer presentation of the key results in the main text would make the paper more accessible.

It is also not clear to me what InvNet is in practice and how it relates to DensNet-D. Section 4 introduces InvNet as the proposed architecture, which compares the input hypergraph with learned templates through a soft alignment of its nodes, but then describes it as a proof of concept, and it is never evaluated. The experiments use DensNet-D instead, which adds local pattern densities to an AllDeepSets backbone and is only briefly said to be derived from the principles behind InvNet. Since the two models rely on different families of features, optimization-based alignment with global templates and count-based local pattern densities, I would like the authors to explain how they are related, which of them should be seen as the main contribution, and why InvNet is not part of the experiments.

My main concern is that the Width Wall remains a definition and the paper never shows that an existing hypergraph neural network actually faces such a wall. The authors themselves decline to assign a width level to the models they discuss, so the framework does not yet tell us anything new about these architectures.

I also feel the experiments are only loosely connected to the theory. The theoretical results concern distinguishing hypergraphs from their structure alone, while the experiments are node classification on citation datasets with rich node features, where even an MLP performs well. For this reason, they cannot show that the proposed features recover information lost by clique expansion, as claimed in the abstract. I think the paper would benefit from an evaluation that directly tests its theoretical claims.

Questions for authors

Width level of existing architectures. Can the authors show that any existing hypergraph neural network faces a Width Wall at a specific level? Even a result for a standard incidence-based message-passing model would make the framework more concrete.

InvNet and DensNet-D. How exactly are the two models related, and which of them should be seen as the main contribution? Could the authors report results for InvNet, at least on the synthetic separation experiments?

Evaluation of the theory. Could the authors evaluate the framework on tasks closer to their theoretical results, for example graph-level classification of hypergraphs without node features, where the structural information captured by the patterns can be tested directly?

Reviewer_vNTfOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper proposes an expressivity framework for HGNNs, based on homomorphism densities and generalized hypertree width. The main idea is to characterize which structural information can be preserved by a hypergraph representation and which distinctions cannot be recovered by a neural architecture once that information has been lost. The authors also introduce an explicit example showing the information loss caused by clique expansion and propose architectures that incorporate additional structural information.

Critical strengths
  • The paper addresses an interesting and relevant problem in the context of hypergraph representation learning, i.e., understanding which structural information can actually be captured by HGNNs
  • The theoretical framework appears mathematically well founded. However, while I am familiar with HGNNs, I am less familiar with some of the mathematical tools used in the paper, so I cannot claim to have fully verified the theoretical results.
  • I appreciate that the authors carefully distinguish between the theoretical expressivity of a representation and the actual capabilities of a specific neural architecture. In particular, they acknowledge that their results do not automatically establish expressivity bounds for existing HGNNs.
  • Although well known in the field, the explicit example showing how clique expansion can discard higher-order structural information is interesting and helps illustrate the theoretical discussion.
  • In the appendix, the authors include a controlled comparison with the AllDeepSets backbone, showing consistent, although relatively small, improvements across the considered datasets.
Critical weaknesses
  • As I indicated above, the paper is quite difficult to read. While the overall organization is reasonable, the presentation is extremely dense and mathematically heavy. I found it difficult at times to follow the main argument and, more importantly, to distinguish the actual novel contributions from the mathematical background on which the framework is built. I believe the paper would benefit from a more intuitive explanation of the framework, possibly supported by running examples, and a clearer discussion of what is genuinely new.
  • As a consequence of the previous point, I am not fully convinced by the novelty of the theoretical contribution. Several of the underlying observations are already well established. For instance, the fact that clique expansion loses higher-order information is well known. Similarly, the theoretical framework builds on existing results concerning homomorphism counts and generalized hypertree width. While combining these concepts into a unified framework is interesting, I believe the authors should better clarify what new theoretical understanding is provided beyond existing work.
  • The empirical evaluation is not particularly convincing. The improvements obtained by DensNet-D over the matched AllDeepSets backbone are relatively modest, and the evaluation is limited to four node-classification benchmarks. Moreover, I am not sure that the experiments establish a clear connection with the theoretical results. It is unclear whether the additional structural features allow the proposed architecture to overcome any of the expressivity limitations discussed in the paper, or simply provide useful additional information to the classifier.
  • Reproducibility is another (minor) concern. The code is not publicly available, and the authors state that they plan to release it upon acceptance.
Questions for authors
  • Q1. Could the authors clarify which theoretical results should be considered the main novel contributions of the paper?
  • Q2. What is the practical advantage of the Width Wall framework for understanding or designing existing HGNN architectures?
  • Q3. How are the structural patterns used by DensNet-D selected, and how do they relate to the theoretical framework?
1 comment

We thank the reviewer for detailed feedback.

Presentation and novelty.

We will improve the paper’s presentation by adding examples, explaining results intuitively before formal statements, and explicitly articulating contributions. This paper studies which higher-order structural distinctions hypergraph representations and neural architectures preserve, and which remain impossible to recover regardless of model size or training.

To answer this question, we make the following contributions.

  • We describe structural information through pattern measurements based on homomorphism and invariant-approximation methods (Theorem 2.4; Lemma A.2). We use pattern densities to measure how often a small hypergraph pattern maps into the input. For a fixed number of vertices, these measurements can approximate any continuous, permutation-invariant structural property. This provides a complete reference against which restricted representations can be assessed.
  • We identify a specific structural distinction lost by pairwise projection (Theorem 3.6; Lemma A.4; Proposition 3.7). We organize pattern measurements by generalized hypertree width and identify a width-2 Pasch density that distinguishes two hypergraphs with identical clique expansions. Our analysis certifies the separator’s exact width and proves separation for ordinary homomorphism densities, accounting for non-injective maps. The result therefore specifies both what information is lost and which structural measurement detects it. Lemma A.4 and Proposition 3.7 explain how such indistinguishability translates into limits on continuous model outputs.
  • We connect the Width Wall to existing models through an architecture-specific result. In the revision, we will include a width-1 bound for structure-only incidence message passing on unweighted inputs, covering the stated forms of AllDeepSets, HNHN and UniGNN under constant initialization and without additional structural inputs or preprocessing. We show that these models cannot distinguish inputs agreeing on every width-1 density. Our framework identifies a concrete structural property these models cannot represent, regardless of depth or hidden dimension.
  • We explain how additional structural features can supply missing distinctions (Theorem 4.1). We study template alignment as a mechanism for adding information unavailable to a restricted backbone. This leads to the design criterion that an added feature must distinguish inputs that the backbone merges; increasing capacity alone cannot resolve that information loss.

Experimental results and connection to theoretical analysis.

Our experiments examine whether explicitly estimated local pattern densities improve a matched HGNN backbone on established node-classification tasks.

While the improvements are modest, they are consistent across different settings (Appendix D.4). Under the same backbone hidden dimension, training configuration and ten data splits, DensNet-D improves over AllDeepSets on Cora, Citeseer, PubMed and Cora-CA, respectively. This comparison isolates the addition of the density branch and supports its practical usefulness in the tested setting.

The four chosen benchmarks provide an established setting for evaluating practical usefulness. Cora, Citeseer, PubMed and Cora-CA come from existing HGNN benchmark protocols, enabling comparisons with representative graph-reduction and incidence-based models. They include co-citation and co-authorship relations and provide node features that are not constructed from target labels. Their role is to evaluate whether structural density features help on conventional prediction tasks. Because all four are citation-related benchmarks, they provide limited evidence about generalization across application domains; we will make this scope explicit.

The connection to the theory is through the structural measurements supplied to the classifier (Appendix G). The framework identifies pattern densities as coordinates of hypergraph structure. DensNet-D uses this principle by estimating a finite set of pattern densities in each node’s incident-star subhypergraph and combining them with the backbone embedding. In principle, such augmentation overcomes a backbone’s expressivity limitation only if an added feature distinguishes inputs that the backbone necessarily maps to the same representation. The experimental results show that the features provide useful additional predictive information. This does not necessarily indicate that DensNet-D crosses a Width Wall or recovers the specific information lost by clique expansion. We will revise the paper to clarify.

Pattern selection.

DensNet-D uses a small collection of hypergraph patterns, selected heuristically using dataset statistics such as hyperedge sizes and average node degree. For each node, it estimates how often these patterns occur among the hyperedges containing that node, then combines these measurements with the backbone’s embedding.

Reviewer_BeEtOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper develops a theoretical framework for analyzing the expressivity of hypergraph neural networks (HGNNs) using homomorphism densities and generalized hypertree width. It establishes a universality result for continuous permutation-invariant functions on fixed-size weighted hypergraphs and organizes structural invariants into a hierarchy based on generalized hypertree width, termed the Width Wall framework. The paper also constructs a pair of non-isomorphic 13-vertex 3-uniform hypergraphs with identical clique expansions but different densities for a width-2 pattern, illustrating the structural information that can be lost through clique expansion. The paper further introduces INVNET, which combines a local incidence-based backbone with a global pattern-alignment mechanism based on Birkhoff relaxation and finite-step Sinkhorn normalization. The experimental study compares representative HGNNs on four node-classification benchmarks: Cora, Citeseer, PubMed, and Cora-CA. It also evaluates DENSNET-D, which augments an AllDeepSets backbone with explicitly estimated local pattern-density features, and compares it with AllDeepSets under matched experimental configurations.

Critical strengths
  1. A principled theoretical framework for HGNN expressivity. The paper uses homomorphism densities to characterize permutation-invariant structural information and generalized hypertree width to organize these invariants into a hierarchy. Theorem 2.4 establishes a universality result for continuous invariant functions on fixed-size weighted hypergraphs.
  2. A concrete construction illustrating information loss under clique expansion. The paper presents a pair of non-isomorphic 13-vertex 3-uniform hypergraphs with identical clique expansions but different densities for a width-2 pattern. The explicit construction and the associated Pasch-configuration counts provide a concrete demonstration of the role of higher-order structural information.
  3. A formal treatment of permutation-invariant pattern alignment. Theorem 4.1 characterizes the invariance and continuity properties of exact alignment scores and their Birkhoff and finite-Sinkhorn variants under the stated assumptions. The exact alignment family also provides a theoretical mechanism for distinguishing distinct hypergraph permutation orbits.
  4. Controlled evaluation of local pattern-density features. Appendix D.4 compares DENSNET-D with an AllDeepSets backbone under matched configurations across four datasets and ten splits. DENSNET-D achieves higher mean test accuracy on all four benchmarks, with improvements of 1.4 percentage points on Cora, 1.8 on Citeseer, 0.6 on PubMed, and 0.8 on Cora-CA.
Critical weaknesses
  1. The Width Wall framework is not sufficiently connected to concrete HGNN architectures. The paper defines a hierarchy based on generalized hypertree width, but the architecture-specific expressivity implications for representative models such as HNHN, UniGNN, and AllDeepSets remain insufficiently established. Proposition 3.7 provides a conditional result: an architecture's invariant functions can be assigned to Hr\mathcal H_r if the required indistinguishability condition is proved. However, this condition is not established for the representative architectures in a way that yields concrete width bounds. The paper would benefit from a specific architecture-level result or a clearer characterization of which claims are currently conditional. In addition, the proof of the width filtration would benefit from explicitly stating and justifying the disjoint-union property of generalized hypertree width used to establish algebraic closure.
  2. The guarantees for exact alignment do not establish equivalent guarantees for finite learned-template INVNET. Theorem 4.1 shows that the family of exact alignment scores separates distinct permutation orbits. The implemented model, however, uses a finite template family, learned score maps, and finite-step Sinkhorn normalization. Continuity and permutation invariance alone do not imply that the resulting features distinguish all non-isomorphic hypergraphs. Remark A.6 acknowledges that a finite number of templates does not guarantee orbit separation. The distinction between the theoretical capability of exact alignment and the structural discrimination capability of the implemented model therefore needs to be made more explicit.
  3. The synthetic INVNET experiments are insufficiently reported, including for the central Steiner pair. Appendix D.3 describes synthetic alignment experiments and specifies settings such as template counts, Sinkhorn iteration counts, and temperature annealing, but does not report numerical outcomes. The Steiner pair is particularly relevant because the paper uses it to demonstrate the information lost by clique expansion. Appendix E.1 establishes that exact alignment separates this pair, but this theoretical result does not show that finite learned-template INVNET does so in practice. Reporting the existing synthetic results, especially finite-implementation alignment scores for the Steiner pair, would help establish how the theoretical construction relates to the proposed model.
  4. The real-data experiments do not directly validate INVNET, and the statistical evidence is limited. The main node-classification experiments evaluate DENSNET-D, which augments AllDeepSets with explicitly estimated local pattern-density features, rather than directly evaluating INVNET's global pattern-alignment mechanism. The results therefore support the usefulness of local density features in the tested setting but do not independently validate INVNET's central alignment mechanism. Moreover, the comparisons in Table 1 use different hidden dimensions and experimental protocols for some models. Although Appendix D.4 provides a matched comparison between AllDeepSets and DENSNET-D, pairwise statistical significance tests are not reported. The empirical conclusions should be framed in accordance with the scope of the reported comparisons.
Questions for authors
  1. Architecture-specific expressivity guarantees: Can the authors provide a concrete example of a representative HGNN architecture for which the assumptions of Proposition 3.7 can be verified, yielding a justified inclusion in some Hr\mathcal{H_r}? Could the authors also explicitly state and justify the disjoint-union property of generalized hypertree width used to establish algebraic closure?
  2. Finite alignment versus exact separation: Could the authors clarify which theoretical guarantees hold for the finite learned-template implementation beyond continuity and permutation invariance? Do the authors claim that finite INVNET separates distinct hypergraph permutation orbits, or is this guarantee restricted to the exact alignment family?
  3. Existing synthetic results and the Steiner pair: Appendix D.3 specifies the settings for synthetic INVNET alignment experiments, but numerical results are not reported. Could the authors provide the existing results, including finite-implementation alignment scores for the Steiner pair discussed in Appendix E.1, and clarify whether the implemented model distinguishes this pair? If the Steiner pair was not evaluated using finite-step INVNET, could the authors clarify the distinction between the exact theoretical result and the empirical behavior of the implementation?
  4. Interpretation of real-data improvements: Could the authors clarify which comparisons in Table 1 use matched experimental configurations and whether pairwise significance tests were conducted for AllDeepSets versus DENSNET-D in Appendix D.4? This would help establish the strength of the empirical evidence for local density features independently of the unreported INVNET alignment results.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.