acceptodds
Under review as a conference paper at ICLR 2027

Capacity Counts: Learning to Predict Hyperedges

12 views

Abstract

Hyperedge prediction scores a candidate node set from observed group interactions. Historical hyperedges may repeatedly rely on the same members, so their count can overstate the support that admits distinct representatives. We introduce CapacityDegree, which represents this assignable support through capacity-constrained matching. A recursive rule assigns node support levels while bounding how many hyperedges each member can represent. For a candidate, matching rank measures available support, and deletion responses identify individual and joint dependencies. A compact readout combines the rank profile with degrees of the pair-response matrix. We prove that capacity levels retain information beyond pairwise projections and satisfy a sharp member-removal bound. We also characterize the deletion responses and prove that the degree branch strictly enlarges the model's function class even when all other inputs, including the rank profile, agree. Across seven datasets, CapacityDegree outperforms eight baselines in AP and AUC, improving macro AP by 9.26 percentage points over the strongest baseline.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Hyperedge prediction, Hypergraph neural networks, Capacity-constrained matching, Structural representation learning, Higher-order interactions

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_uvEgOpenReview ↗
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?

1 comment

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.

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

This paper presents whether a given hyperedge is plausible or not based on the metric called the capacity degree.The key idea behind the capacity degree is counting unique, distinguishing hyperedges that consist of the same members. The method first identifies the assignment of each member to a hyperedge, such that a member can be a representative of a maximum of b hyperedges, and each hyperedge can only have one representative. By solving the matching problem, one can count how many unique hyperedges a node belongs to, as well as its members. These counts are used to calculate the features of each node and the given hyperedge, which are then fed into a neural network to calculate a single score. The neural network is trained on a contrastive learning objective, likely the binary entropy loss (not written). The method was tested on nine datasets and compared against eight baseline methods, confirming that the proposed method outperformed the baseline methods on all datasets.

Critical strengths

The most critical strength of the paper is its departure from counting duplicate hyperedges to counting unique hyperedges consisting of unique members. This idea was formulated as a matching algorithm on top of the conventional k-core composition for hyperedges. By constraining the maximum number of hyperedges each member can attend to, when a node attends to multiple hyperedges many times, those duplicated edges are not reflected in the final judgment. This differs from previous methods, which simply count the number of hyperedges each member has attended before. The author formulates this idea using matroids, and the formulation is well suited for the computation of J and delta, which is interpretable and has more practical values. The fact that this unique hyperedge counting idea outperforms simple counting without discounting duplicates is an important finding that provides a new direction for this problem.

Critical weaknesses
  1. The actual gain of using Capacitydegree is, albeit positive, very small and only shown for two datasets (Table 3). Since this is the proposed metric, it is crucial to test the gain by testing whether CapacityDegree is consistent and significant, and to what extent. In the current form, most of the performance gap from the baseline methods is attributed to the author's architecture, not the CapacityDegree. It could be that the performance is reaching to the ceiling and more gap might be able to be observed for harder tasks.

  2. The second weakness is the clarity of the paper. Some equations use notations that are defined later. For example, ν in Eq. 2 is not defined before this equation, and ν in this equation takes four arguments (b, v, x, k) while the same notation is used in Section 3.3 as ν_v(U), which has its own meaning in this section. Another example is x. Variable x is used to represent a tentative level value in Section 3.1 but then used to represent a normalized degree of the Ks (Section 3.3). I was confused a lot by the same kind of notation abuse (e.g., (c, C, c_S), (U, U^e _{v}(x,k)), (h^(\ell), h_u), (D_v, D_V)) and read back and forth many times to figure out. At this current form, I cannot endorse this paper for publication at ICLR. I strongly suggest authors to revise the presentation of the results, especially making sure that all notations are defined before being used (or right after used), avoid using the same or a similar notation for semantically different concepts. Please also provide the intent of each transformation of the variable such as (h/(1+h), ((BC)^2)_uu), which greatly improves the readability.

  3. The third weakness is the mismatch of what was labeled and what was claimed in Theorems 1 and 5. These two theorems only show an existence of specific cases, where information is added. The label of the theorems, however, are quite general (Information beyond a pairwise projection and Information added by the degree branch ), which overgeneralize what the theorems actually show.

  4. On a minor note, the numbering and references. There are no theorem 3 and 4 and the numbering jumps from theorem 2 to theorem 5. Furthermore, Table 3 is not referenced at all, and there are other tables that are not referenced. Please make sure to reference all the tables and provide explanations.

Questions for authors
  • What are the key novelty of the proposed CapacityDegree in light of the existing k-core decomposition for hypernetworks (e.g., (k,s)-core)
  • What are the contributions of the architecture and type of input feature (coverage and/or CapacityDegree)?
  • Are the gain significant enough that justifies the use of CapacityDegree?
1 comment

How much capacity adds. We fixed the 74,306-parameter predictor and compared matching with all-count on two new held-out splits of all seven datasets. The macro test AP gains were 0.107 and 0.349 percentage points, with matching ahead on 3/7 and 5/7 datasets. Primary gained 1.445 and 2.947 points. Senate gained 0.248 and 0.088. High favored counting by 0.371 and 0.374. On Enron the original validation advantage (+0.871) reversed on both new test sets (−0.378 and −0.282). Primary gives the clearest empirical case for computing matching features. Figure 4 shows the paired differences, and Table 18 gives both models’ absolute AP. Both splits used the same training initialization. A significance test across initializations would require independent training seeds. Architecture, input and task difficulty. The original 9.26-point macro test AP gain over S3Hyper compares complete predictors. The new two-arm comparison holds the architecture fixed and varies the structural inputs. On the original seven validation sets, changing just the candidate profile to coverage raised macro AP by 0.013 points, while changing all capacity inputs to counts lowered it by 0.120. Estimating the architecture's share of the S3Hyper margin would require an architecture-only comparison. Testing for a ceiling effect would require varying task difficulty. Relation to hypergraph cores. With zero lag, unlimited member capacity and at least two retained members per historical edge, the vertices reaching level k form the vertex set of the indexed (k,2) incidence core. Finite capacity couples the choices of representatives across incident edges. If three distinct eligible edges have the same sole eligible peer, their coverage count is three and their unit-capacity assignment size is one. The experiments use lag one, which permits a representative at level k−1 when testing a root at level k. Notation and the running example. Section 3 now defines the node-level assignment size before the level update and uses a separate symbol for the candidate matching rank. Trial node levels and normalized candidate degree also have distinct symbols. The map h/(1+h) compresses large response strengths while preserving their order. The diagonal entries of the squared and cubed normalized coverage matrix sum weighted closed walks of length two and three. Figure 1(c) shows the pair-response matrix for the three peers of root v. For the full four-member candidate, two roots each contribute ½ to each pair, giving every pair weight one and every member degree three. Figure 1(e) shows where this degree enters the readout. The experiments specify binary cross-entropy and list the seven datasets. Theorem scope and numbering. Theorem 1 gives an explicit separation at equal pairwise projections and count levels. Theorem 5 constructs an explicit pair separated by the degree readout with the other inputs held fixed. Their titles now state the existence claims. Theorem 2 gives the member-removal bound, followed by Propositions 3 and 4 in the shared numbering sequence. The experiments now introduce the original two-dataset comparison in the text and explain what the matched control rows measure.

Reviewer_uRNCOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes essentially a structural feature-construction method coupled with a neural hyperedge predictor. The key idea is to check whether the group’s connections to observed hyperedges are spread across different members, or repeatedly depend on the same members. It computes structural features describing these connections, and how they change when members are removed, combined with a neural predictor. Experiments show improvements over eight baselines on seven datasets.

Critical strengths
  1. The structural analysis in this paper is solid. It gives the representation a precise interpretation. The theory further shows that the proposed features can distinguish structures that ordinary counts miss.
  2. The model performs well across seven datasets, with a careful setup that keeps target hyperedges out of its inputs.
Critical weaknesses
  1. It seems to me that the matching features offer not much improvement over simpler counting features in the two-dataset comparison. Removing the degree component also barely changes performance.
  2. I hope to see discussion on the complexity of the method, espeically time and memory needed to compute these features.
Questions for authors

Please see weaknesses.

1 comment

Matching versus counting. We extended the same-architecture comparison to seven datasets and two new held-out splits. Both models used the same architecture (74,306 parameters), initialization, training budget and candidates within each split. Matching gained 0.107 and 0.349 percentage points in seven-dataset macro test AP on splits 43 and 44, leading on 3/7 and 5/7 datasets, respectively. Primary had the largest gains (+1.445 and +2.947 points) and Senate also favored matching (+0.248 and +0.088). High favored counting by 0.371 and 0.374 points. Figure 4 gives all seven paired differences, and Appendix J.5, Table 18 gives the absolute AP values. Which inputs contribute? The all-count comparison measures the combined effect of recursive levels, eligibility, root budgets and candidate responses. On the original split, a second control retained the matching-based levels and degree and changed just the candidate profile. On its seven validation sets, the coverage profile led by 0.013 macro AP points, while the complete matching model led all-count by 0.120. Why removing the degree branch has little effect. Removing it raised five-dataset macro test AP by 0.005 points and lowered AUC by 0.017. For a two-member candidate, each root has just one peer, so every pair-deletion response is zero. Such candidates account for 60.76% of Primary and 70.40% of High on split 42 validation. Appendix J.5, Figure 10 locates the change in the held-out rankings. On Primary, changes in precision at the ranks of positive two-member candidates accounted for 94.2% and 81.5% of the two AP gains. A candidate can change rank through its node inputs and parameters learned across all training candidates even when its local pair response vanishes. Feature time and memory. For a root with t candidate peers and A active peer–resource incidences, the rank profile takes O(tA + t) time. Computing all pair responses takes O(tA + t²) time and O(A + t²) space. Recursive levels require integral flow queries. On an RTX 2060, assembling inputs from existing structural and query caches took 8.0 s on House and 690.4 s on Senate. A complete cached validation pass took 0.062 and 1.264 s, with peak allocated GPU memory of 26.6 and 21.0 MiB, respectively. In a separate CPU measurement on Enron split 43, both models started with empty feature caches. Preparing the training and validation inputs took 6.64 s for Full and 1.60 s for all-count. Within Full’s 6.64 s, building the two support structures took 4.10 s and computing the candidate pair-query blocks took 1.10 s. Peak resident memory of the Python process, sampled every 0.25 s and including memory already resident, was 288 MiB for Full and 289 MiB for all-count.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.