Leave-One-Member-Out Tests for False Negatives in Hyperedge Prediction

Many real relationships involve groups rather than pairs: a team of co-authors, a recipe's ingredients, a shopping basket. Models that predict such groups, called hyperedges (a single relation that connects any number of nodes), are trained to tell real groups from fake ones. The strongest recent methods make the fake groups deliberately hard, using a learned generator that produces node sets the classifier cannot easily reject. Real group data is very sparse, though. Most valid groups have simply never been observed, such as authors who would collaborate but have not yet. A generator that gets good at producing plausible groups will therefore start producing some of these unobserved real ones. The classifier is then trained to reject them. In pairwise retrieval and recommendation this is a well-documented failure called false-negative noise, but for groups nobody has measured it or corrected for it.

We propose a test that is only possible because the candidate is a group. Remove one member at a time and re-score what is left. A fake group built near a real one usually contains a single "intruder", so removing that member makes the score jump while removing anyone else does not. An unobserved real group has no intruder, and its leave-one-out scores stay uniformly high. We turn this member-wise score profile into a per-sample weight that reduces the penalty on suspected false negatives during adversarial hyperedge training. We evaluate it with a protocol that hides known true hyperedges, so that false negatives become measurable.

Core Claim

Generative negative samplers for hyperedge prediction raise the false-negative rate in exactly the region they target, and pairwise remedies miss the group-level signature of these errors. AHP trains a generator against an HNHN-based discriminator that pools members with a max-minus-min "diversity" operation. SEHP instead diffuses positive hyperedge embeddings toward the decision boundary, conditioned on the local sub-hypergraph. Both treat every unobserved group as negative. The vision-language analogue suggests the effect is large: MAFA reports that aggressive hard mining raises the in-batch false-negative rate from about 3% to over 20%. Our claim is that the member-wise structure of a candidate group separates "real group, unobserved" from "real group plus intruder" better than signals that look only at the overall score or at score fluctuation over training. Down-weighting by this signal should improve both prediction accuracy and the model's ability to rank hidden true groups.

Concretely, let $s(e)$ be the discriminator's score for a candidate group $e = \{v_1,\dots,v_k\}$ with $k \ge 3$, and let $s(e \setminus v_i)$ be its score after removing member $v_i$. Define the intruder gap

$$g(e) = \max_i s(e \setminus v_i) - \operatorname{median}_i s(e \setminus v_i).$$

A large $g$ means one member is responsible for the group looking fake. A high $s(e)$ together with a small $g(e)$ is the signature of a likely false negative. Each generated negative receives a loss weight $w(e) = 1 - \pi(e)$, where $\pi(e)$ is a calibrated false-negative probability computed from $(s(e), g(e))$.

The scheme fits max-min pooling particularly well. Removing a member changes the pooled vector only in the dimensions where that member is the extreme. A single off-topic intruder therefore produces a sharp, localized change, while a coherent group shifts smoothly.

Research Program

The method builds on the AHP setup with an HNHN discriminator, chosen because HNHN treats hyperedges as nonlinear hidden units and handles variable-size groups natively. Node embeddings are computed once per step. The leave-one-out profile then costs $k$ extra applications of the cheap pooling and scoring head, not $k$ full message-passing passes.

The calibrator that maps $(s, g)$ to $\pi$ needs supervision we do not have, so we manufacture it from training data. We take observed positives as coherent examples. We take one-member-corrupted copies of those positives as known intruder examples, since replacing one member of a real group almost never yields another real group. A small logistic model is fit on these two kinds of example and refit every few epochs, so it tracks the evolving encoder. This replaces the single global class prior used by Robinson et al. and HDCCF with a per-candidate estimate. Both of those works report that a hand-tuned prior is fragile, and that fragility is what motivates the change.

For SEHP, the test requires discrete membership. This collides with SEHP's latent shortcut, which trains on continuous generated embeddings and is reported to be 20 to 71 times faster than decoding to node sets. We will apply the test to SEHP's decoded variant and measure what auditing costs. If the decoded variant with weighting cannot beat the shortcut at matched wall-clock time, that is a genuine negative result about where membership auditing pays off.

The evaluation protocol is a central contribution, because false negatives are invisible under standard splits. In the hidden-hyperedge protocol, a random 20% of true hyperedges are removed from the training hypergraph entirely, not just from the training labels. They then sit in the unlabeled pool as known false negatives. One hidden subset is used to tune hyperparameters and a disjoint subset is used for reporting. On DBLP we will additionally build a temporal split from publication years, with groups first appearing after the cutoff serving as natural false negatives. Timestamps are not part of the benchmark versions described in our sources, so this requires re-deriving the hypergraph from raw DBLP records.

Baselines

The naive reference point is an HNHN discriminator trained with heuristic negatives: random member replacement and the size-, motif-, and clique-based samplers (SNS, MNS, CNS) that AHP evaluates against. This shows how much hard generation helps at all.

The first strong competitor is AHP itself, run unmodified with its memory bank. AHP reports an "average AUROC 28.2% higher than the best existing method" on DBLP, but our sources give no absolute AUROC value for AHP on DBLP, so we will reproduce it.

The second strong competitor is SEHP, both with the latent shortcut and decoded. SEHP reports a "nearly 20% improvement in AUROC over previous generative methods like AHP" on Cora and a 34.5% AUROC gain over node-representation baselines on Recipe200k, where AHP ran out of memory. Our sources give no absolute AUROC value for SEHP either.

The pairwise remedies, ported to hyperedges, are the competitors that test our key ingredient. The first is an SRNS port: SRNS observes that false negatives keep stably high scores over training while true hard negatives fluctuate, so we weight negatives by their score variance across epochs using a memory bank. The second is a debiased loss with a global false-negative prior, following Robinson et al. and HDCCF, with the prior tuned on the tuning split. The third is a boundary-band filter in the spirit of SimANS, applied to the generator's outputs: keep negatives whose score lies in a band around the positive score and discard those above it. Because the generator supplies a small candidate set, the exponential candidate space no longer blocks this.

A structural heuristic tests whether any learning is needed. It down-weights candidates by the co-occurrence count of their member pairs in observed hyperedges, and also by maximum Jaccard overlap with any training hyperedge.

Ablations isolate the leave-one-out signal. We compare $s$ alone, $g$ alone, epoch variance plus $g$, and dropping the same number of negatives at random.

All methods share the HNHN encoder, the same generator architecture and training steps, and the same hyperparameter search budget (an equal number of configurations, selected on the tuning split). We report wall-clock time as well. Beating a baseline means a higher test AUROC averaged over the AHP negative mixtures, and a higher area under the curve for separating hidden true groups from generated true negatives. Both must hold over five seeds, by margins exceeding the seed standard deviation.

Why not just…?

Why not just use random negatives, since the $2^N$ space makes collisions negligible? Random negatives do avoid false negatives, but both AHP and SEHP show that models trained on easy negatives fail when tested on realistic negatives. The naive baseline will re-confirm this under our protocol. The question is not whether hard negatives help but whether their benefit is being partly cancelled. The rate at which generated negatives land on hidden hyperedges answers that directly.

Why not just port SRNS's training-time variance? This is the most serious threat. Epoch variance is cheap and has worked in pairwise recommendation. Two concerns follow from the setup. Generated negatives are produced fresh each step, so most have no score history unless a memory bank retains them. Epoch variance also mixes up "uncertain because an intruder is present" with "uncertain because the encoder is still moving". The leave-one-out profile is computed from a single model state and points to which member is at fault. We run SRNS-port, $g$ alone, and the two combined. If SRNS-port matches $g$ on false-negative detection, we will report the variance signal as sufficient and the group-specific test as unnecessary.

Why not just use a debiased loss with a class prior? A global prior subtracts the same expected false-negative mass from every negative. False negatives, however, concentrate among the hardest generated samples, which is exactly what MAFA's 3%-to-20% jump indicates. A uniform correction therefore under-corrects the hard tail and over-corrects the rest. The sensitivity of the prior baseline across its tuned range, compared with our per-sample weights, will show whether this matters.

Why not just filter by overlap with observed hyperedges? In co-authorship data, future teams often reuse past collaborators, so pair co-occurrence may already predict false negatives well. If this heuristic matches our method on DBLP's temporal split, the honest conclusion is that structure, not learned profiles, does the work there. Recipe200k, where ingredient co-occurrence is dense and less indicative of novel combinations, is where we expect the two to diverge.

Proposed Experiments

The experiments use DBLP, Cora, and CiteSeer co-citation hypergraphs and Recipe200k, under the hidden-hyperedge protocol, plus the DBLP temporal split. They begin with a measurement study. For AHP and SEHP we report the fraction of generated negatives that coincide with, or contain all but one member of, a hidden true hyperedge, and how this fraction grows over training. If it stays near the random baseline, the premise fails and we stop.

The decisive checks follow. First, $g(e)$ must separate hidden true hyperedges from generated true negatives with high discriminator score better than $s$ alone and better than epoch variance; this is measured as detection AUROC restricted to the top score decile, where false negatives live. Second, weighted training must raise test AUROC across the SNS, MNS, and CNS mixtures over unmodified AHP and SEHP. Third, weighted training must rank hidden hyperedges above heuristic negatives more often, which is the practical point of not suppressing real groups.

We also stratify results by group size. The test is undefined for size-2 groups and should be weakest for size-3 ones, so gains concentrated in larger groups would support the mechanism. Gains that are flat across sizes would suggest the weighting is acting as generic regularization.