- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
The paper proposes CapacityDegree, a method for hyperedge prediction that scores a candidate node set based on how its members can represent historical hyperedges. At the node level, it computes recursive support levels in which each hyperedge must be assigned to a distinct member, and each member can represent only a limited number of hyperedges. At the candidate level, it measures how much historical support the members can jointly represent and how much is lost when one or two members are removed, and it summarizes these quantities in a rank profile and a capacity degree used by the model's readouts. The authors show that these levels carry information beyond pairwise co-occurrences, bound how much a level can change when a member is removed, characterize the pair-deletion responses through matroid duality, and prove that the degree branch enlarges the model's function class. On seven datasets, CapacityDegree outperforms eight baselines in AP and AUC.
Critical strengths
The reason for replacing counts with capacity-constrained assignments is clear and sound. The theory also supports this choice. In particular, Theorem 2 shows that removing one member lowers a capacity level by at most its capacity b, while count levels can drop arbitrarily, which formalizes how much counting can depend on a single member.
Critical weaknesses
I found the paper very difficult to read and parse. Many symbols are introduced in quick succession, and I think the authors should introduce them more clearly to help the reader follow the method. Figure 1 does not help much in this respect either, as it packs many formulas. A running example followed through all steps of the method (possibly extended in the appendix), a simpler notation, and moving the less essential details to the appendix would make the paper much more accessible.
More importantly, I feel the experiments do not show that the capacity mechanism is responsible for the gains. Removing the degree branch does not change the results (Table 2), and in Appendix Table 11, some of the replacements that use coverage or counts instead of matching even give slightly higher scores than the full model. I would like the authors to comment on these results.
I also have some concerns about the evaluation. All baselines share a single training configuration, and no hyperparameter search is reported for them. Moreover, the results are based on a single data split and only two seeds, which makes it difficult to assess how robust the reported gains are.
Finally, the paper does not report running times, so it is unclear how the cost of the method compares with that of the baselines in practice. I would like the authors to include such a comparison.
Questions for authors
Contribution of the capacity mechanism. Removing the degree branch does not change the results (Table 2), and in Appendix Table 11, some of the replacements that use coverage or counts instead of matching give slightly higher scores than the full model. How do the authors interpret these results with respect to the main claim that capacity-constrained assignments are more informative than counts?
Computational cost. What are the running times of the method, including the computation of the capacity levels and the candidate queries, compared with the baselines?
What the replacements and ablations show. On the two original test datasets, the 69,890-parameter coverage-degree and count replacements exceeded the 74,306-parameter Full model by 0.040 and 0.025 macro AP points. These replacements omit the candidate rank-profile branch. The five-dataset ablation isolates the effect of removing one branch at a time. Removing the profile lowered macro AP by 0.657 points, while removing the degree branch raised it by 0.005. At fixed architecture and 74,306 parameters on the seven original validation sets, replacing just the matching profile with coverage raised macro AP by 0.013 points. These results support retaining a profile and distinguish its value from the choice of matching or coverage inside it. Robustness to the data split. Figure 4 and Appendix J.5 (Table 18) report the two new splits. We froze both model specifications, initialization seed 42 and the training protocol, then evaluated Full and all-count on two new partitions of all seven datasets. We selected all 28 checkpoints by validation AP before scoring the held-out candidates. Full gained 0.107 and 0.349 percentage points in macro test AP, leading on 3/7 and 5/7 datasets, respectively. Macro test AUC rose by 0.042 and 0.425 points. The clearest cross-split effect was on Primary (+1.445 and +2.947 AP points), while High favored counting twice. These figures quantify the joint effect of recursive and candidate capacity inputs. The ranking of external baselines comes from the original split under a shared training configuration without method-specific tuning. Running time. We timed all nine predictors on the same RTX 2060 over a common 200-update window with prepared inputs and 100 scheduled validation passes. On House, MLP, CapacityDegree and S3Hyper took 9.4, 45.5 and 83.1 s, respectively. On Senate, the corresponding times were 227.1, 1,007.8 and 1,931.8 s. Across seven datasets, CapacityDegree took 0.52–1.71 times as long as S3Hyper. Assembling CapacityDegree inputs from previously built level and query caches took 8.0 s on House and 690.4 s on Senate. On Enron split 43, a separate CPU run starting from empty feature caches took 6.64 s to prepare CapacityDegree’s training and validation inputs, including 4.10 s to build the two support structures and 1.10 s to compute the candidate pair-query blocks. Preparing the same inputs for the all-count model took 1.60 s. Appendix J.4 reports input preparation, cached inference and training times. Section 3 describes the recursive assignments and the time and space required for candidate queries. Reading the method. Figure 1(a)–(c) and the notation appendix follow one six-node example. The lower panels show how its structural inputs enter the predictor. At the illustrated root, deleting either of two peers leaves two assignments. Deleting both leaves one assignment because the remaining peer can represent one of the two historical edges. This produces a positive joint-deletion response. Section 3 follows the response through the candidate degree into its readout, and the appendix gives the full query algorithm.