- 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?
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.
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.