- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper introduces OmniSheaf, a framework for sheaf learning on hypergraphs through two-stage node-to-hyperedge and hyperedge-to-node aggregation. Learnable restriction maps align stalk features before multiset aggregation, avoiding explicit clique expansion. The authors develop DeepSets and Transformer instantiations, along with directed variants based on complex phases or separate tail/head processing. They present reductions to existing hypergraph and sheaf architectures and universal approximation results for suitable parameterizations. Experiments span 25 benchmarks, with notable gains on committee, directed, and molecular tasks.
Critical strengths
S1. A unified framework with practical computational benefits. OmniSheaf combines sheaf transport with incidence-based multiset aggregation, connecting AllSet, sheaf diffusion, and directed architectures. It preserves hyperedge identities and avoids explicit clique expansion, offering both conceptual value and potential savings on large hypergraphs.
S2. Broad evaluation with substantial gains. Experiments cover node classification, directionality tests, and molecular hyperedge classification, with variability reported over ten runs. Gains of 14.37 points on Senate and 4.11 on Roman-empire, alongside resource savings over DSHN at large scale, support the framework's practical value. The paper also acknowledges cases where simpler baselines perform better or cost less.
Critical weaknesses
W1. Linear complexity is not established for all instantiations. Theorem 4 counts incidence messages without accounting for aggregator costs. Yet Theorem 6 recovers SheafHyperGCN through pairwise distances within hyperedges, potentially requiring quadratic work. Please identify which instantiations remain linear and include stalk dimension, feature width, and aggregator size in the bound to clarify the scope of the efficiency claim.
W2. The headline speedup uses the wrong baseline. The abstract claims a 7.1x speedup over DSHNLight, but Table 3 supports this figure against DSHN. At d = 2, ODS is only about 1.12x faster than DSHNLight and uses more memory (5.20 vs. 2.99 GB). Since the best accuracy comes from costlier directed variants, please correct the attribution and compare accuracy and cost for the same configurations.
W3. The contribution of learned sheaf transport remains unclear. Comparisons with AllSet do not isolate gains from sheaf transport versus added capacity or other architectural changes. Please compare learned and fixed restriction maps under matched parameter and training budgets to establish whether stalk alignment drives the improvements.
Questions for authors
See weaknesses.
2 comments
Thank you for the authors' response. I appreciate the clarifications and encourage the authors to incorporate the relevant revisions into the revised manuscript. I will maintain my current score.
Response to Reviewer WpaK
W1. Linear Complexity
Comment: Theorem 4 counts incidence messages without accounting for aggregator costs. Yet Theorem 6 recovers SheafHyperGCN through pairwise distances within hyperedges, potentially requiring quadratic work. Please identify which instantiations remain linear and include stalk dimension, feature width, and aggregator size in the bound to clarify the scope of the efficiency claim.
Response: Thank you for pointing this out. The reviewer is right that the proof of Theorem 4 counts incidence messages: it states that each stage of OmniSheaf exchanges exactly K=∑e∈E∣e∣ messages, against O(∑e∣e∣2) for clique-based implementations, and does not include the cost of computing each message. We will make this scope explicit and add the following remark after Theorem 4.
Remark (cost per message). With stalk dimension d, feature width f and hidden widths O(f), one layer costs O(K⋅(cmap+cagg)) time and O(Kdf) memory. Here cmap=O(f2+df) for Diag and O(f2+d2f) for General and Ortho maps is the cost of predicting and applying one restriction map, and cagg is the cost of the multiset functions per element: O(df2) for row-wise DeepSets and O(d2f2) for PMA, where the number of seeds and heads adds a constant factor.
After factoring all the above, the cost remains linear in K whenever the multiset functions process each element at a cost independent of ∣e∣. This holds for all instantiations used in our experiments (ODS, OST, OCS, OCS-T, OPS and OPS-T), which pool or attend once over the members of each hyperedge, and for the reductions to AllSet, SheafHyperGNN, sheaf networks on graphs and DSHN (Theorems 5, 6, 7 and 11). The only exception is the reduction to SheafHyperGCN (Theorem 6). As stated in its proof, fV→E evaluates all pairwise distances within Ve, which costs O(∣e∣2df) per hyperedge. [If the maximal pair is selected after a random scalar projection, as in HyperGCN, this cost drops to O(∣e∣df).] We will state this exception by adding this remark and we will clarify Theorem 6 accordingly.
W2. Headline Speedup Claim
Comment: The abstract claims a 7.1x speedup over DSHNLight, but Table 3 supports this figure against DSHN. At d = 2, ODS is only about 1.12x faster than DSHNLight and uses more memory (5.20 vs. 2.99 GB). Since the best accuracy comes from costlier directed variants, please correct the attribution and compare accuracy and cost for the same configurations.
Response: We agree with the reviewer that the speedup claim is imprecise, we will clarify the attribution and compare accuracy and cost for the same configurations throughout the paper in the final version of the manuscript.
W3. Identity & Fixed Random Restriction Maps
Comment: Please compare learned and fixed restriction maps under matched parameter and training budgets to establish whether stalk alignment drives the improvements.
Response: Thank you for the suggestion. We ran this ablation with matched parameter counts and training budgets, comparing the learned maps of our main results with identity and fixed random orthogonal maps.
Table R2. Test accuracy (%). The “Learned” column shows the result reported in our Tables 1, 4 and 10. The identity and fixed random orthogonal variants keep the configuration of the learned model. Δ is relative to learned maps, while † marks learned maps significantly better than that variant (two-sided Welch t-test over 10 runs, Holm-Bonferroni over the 20 comparisons, p < 0.05).
Learned maps outperform both alternatives in all 10 settings, by up to 19.2 points against identity and 68.3 points against fixed random maps, and all 20 differences are significant (two-sided Welch t-test, Holm-Bonferroni, p < 0.05).
We will add this in the final version of the manuscript.