Latent Group Induction for Noisy Hypergraphs

A hypergraph records group interactions such as co-authored papers, shopping baskets, or co-sponsored bills. Each "hyperedge" is a set of nodes that acted together. Neural networks that run on hypergraphs treat these observed sets as ground truth. Most real hyperedges, though, are incomplete and noisy glimpses of a smaller number of stable underlying groups. A lab of eight people produces dozens of papers, each listing five or six of them. A household buys overlapping subsets of the same thirty products week after week. Current methods for cleaning up the hypergraph can delete connections or reweight them, but none of them ask the question that classical latent-variable learning asks of a dense cluster of correlations: is this cluster the footprint of one hidden cause?

We propose to answer that question directly. The method fits a sparse generative model in which each observed hyperedge is a noisy sample of members drawn from a latent group. It then runs hypergraph message passing over the inferred latent groups in place of the raw sets. Pruning can only remove structure. This model can also restore members that were dropped from individual observations, because it pools evidence across every hyperedge that samples the same group. It can shrink the number of hyperedge units a network has to process, and it decides how many groups to keep through a prior that controls sparsity separately from smoothing. The central empirical claim is falsifiable. Under member dropout, likelihood-based group induction should beat both pruning-based structure learning and simple overlap clustering, and its advantage should grow as dropout increases.

Core Claim

A dense family of heavily overlapping hyperedges plays the same role at higher order that a "semi-clique" plays for pairwise edges. Discovering Hidden Variables: A Structure-Based Approach showed that when a common cause is omitted from a Bayesian network, the observed variables form near-cliques. Replacing such a near-clique with a latent parent turned a dense structure into a star and cut parameters, from 59 to 17 in their example, while held-out likelihood improved. Towards Association Rules with Hidden Variables made the analogous point for rules: one hidden antecedent can subsume a whole family of pairwise rules.

Neither method operates on sets. Efficient Relational Learning with Hidden Variable Detection induces hidden concepts only for unary entity types. Our claim is that the same subsumption move, applied to hyperedges, gives a better input structure for hypergraph neural networks. The structure is better in three measurable ways. It recovers missing memberships, it reduces the number of hyperedge units, and it improves node classification on noisy and featureless hypergraphs.

Relation to Prior Work

Three structure-learning lines come closest, and each leaves the key operation undone.

The first is pruning with a shared training objective. Hypergraph Structure Learning for Hypergraph Neural Networks masks whole hyperedges using a differentiable discrete relaxation (Gumbel-Softmax) and adds or removes members by cosine similarity of their features. It keeps about 11% of CA-DBLP's connections without losing accuracy. Deep Hypergraph Structure Learning reweights incidence entries with attention under an information-bottleneck objective and thresholds weak weights. Both motivate our proposal, because they show that much observed structure is redundant. Both also constrain it. They never introduce a new hyperedge, and their decisions about membership come from node features. That leaves co-occurrence evidence unused when features are absent.

The second is latent type assignment. MC-HNN gives each hyperedge a soft mixture over a learned codebook of prototype types, and adds multiple message channels to avoid rank collapse. The codebook changes what a hyperedge means. It does not change who is in it. We take their finding that gains concentrate on featureless, heterophilic benchmarks as a pointer to where our method should matter most.

The third is latent hypergraph models from statistics. Disentangling Latent Risk Pathways via Bayesian Hypergraph Inference treats unobserved disease pathways as latent hyperedges, discourages redundant pathways with a repulsion prior, and scales to 277,291 patients. However, its hyperedges are driven by external risk factors through a linear model, and the observed data are node outcomes rather than hyperedges. Latent Space Modeling of Hypergraph Data models hyperedges as geometric intersections in a latent space. It becomes intractable beyond roughly 100 nodes, and its authors prove that the size of star motifs is capped by the latent dimension. That cap rules out geometric latent spaces for the large baskets and bill sponsorships we target.

Our generative model borrows its prior from Decoupling Sparsity and Smoothness in the Discrete Hierarchical Dirichlet Process. That paper showed that tying sparsity and smoothing to one hyperparameter produces hundreds of junk components (over 1,400 topics versus about 800 on NIPS). It fixed this with a spike-and-slab construction. We keep that fix.

Research Program

We treat the node-by-hyperedge incidence matrix the way a topic model treats a word-by-document matrix. Here hyperedges play the role of documents and latent groups play the role of topics. Each latent group $k$ carries a binary support indicator $b_{kv} \sim \text{Bernoulli}(\pi)$ for every node $v$, which says whether $v$ can belong to the group at all. It also carries an inclusion probability $q_{kv}$ for nodes in its support. Each observed hyperedge $e$ selects a group $z_e$ from a sparse mixture with weights $\theta$, and then includes each node independently:

$$P(v \in e \mid z_e = k) = b_{kv}\, q_{kv} + (1 - b_{kv})\, \rho,$$

where $\rho$ is a small background rate that absorbs spurious members. The spike $b$ controls how large each group is. A prior on the slab $q$ controls how reliably members appear. Keeping these two controls separate is the design decision taken from sparseTM. As a variant, we let a hyperedge be a union of two or three groups, for example a paper that bridges two labs.

The number of groups is inferred with a truncated nonparametric prior on $\theta$. We will also test the Modified Dirichlet of Modified Dirichlet Distribution: Allowing Negative Parameters to Induce Stronger Sparsity, whose negative parameters push unneeded groups to a floor that the data likelihood cannot easily override.

Inference uses stochastic variational updates over the sparse nonzero entries of the incidence matrix, so its cost scales with incidence size. To reduce the greedy-placement problem that affects Structural EM, we initialize from overlap clusters and then run split-merge moves scored by held-out likelihood of the incidence. A held-out hyperedge scores well only if the groups explain it.

The downstream network is AllSetTransformer from You are AllSet. It runs on a two-level structure in which nodes send messages to latent groups, weighted by their posterior membership. We compare running the network on the latent groups alone against running it on latent groups plus the observed hyperedges they fail to explain. The analysis side asks two questions. First, when does pooling across hyperedges identify groups that pairwise overlap cannot? Second, how does replacing many large hyperedges with fewer groups change first-layer over-squashing, the point where MC-HNN locates the information loss?

Baselines

The naive reference is AllSetTransformer on the raw observed hypergraph, tuned as in its paper. It isolates what any structure change buys. A pairwise GCN on the clique expansion (replacing each hyperedge with all pairwise edges among its members) is also reported. Hypergraph Convolution and Hypergraph Attention reports 61.7% for hypergraph convolution versus 57.0% for pairwise GCN on 20-Newsgroups, so we expect clique expansion to lose, and it serves only as a sanity floor.

The strongest structure-learning competitors are DeepHGSL and HSL. DeepHGSL reports 79.3% accuracy on Yummly10k and about 53.7% under 75% random edge deletion, where competing methods fell into the 30s and 40s. HSL reports 98.08% on Zoo, a near-ceiling result, so Zoo is only a sanity check, and it reports 11% connection retention on CA-DBLP. For DBLP we cite HNHN's 85.1% (HNHN).

For Walmart, House, and Senate, the file gives only relative gains (AllSetTransformer about +3% on Walmart; MC-HNN +10.7% on Senate and +4.7% on House over FrameHGNN). No reported absolute result was found on Lacuna for these datasets, so we will rerun MC-HNN and AllSetTransformer ourselves.

All methods share the same splits, the same backbone where applicable, and the same hyperparameter-search budget in trials and GPU-hours. For our method, the cost of inferring groups is counted inside that budget. Beating a baseline means a gain over the best baseline that exceeds the seed-to-seed standard deviation across ten splits, on at least the corrupted and featureless settings. On clean homophilic benchmarks, matching a baseline while using fewer hyperedge units counts as a parsimony win, not an accuracy win.

The ablation that isolates the key ingredient keeps the two-level network fixed and swaps out only how groups are induced. We compare three options: our likelihood-scored generative model, overlap clustering of hyperedges, and our model with a plain Dirichlet prior in place of the spike-and-slab.

Why not just…?

Why not just cluster hyperedges by overlap and add a node per cluster? This is the real threat. Clustering the dual graph, where hyperedges are linked by Jaccard similarity of their member sets, is cheap and may recover the same groups when observations are nearly complete. The argument against it is quantitative. If each member of a group is dropped independently at rate $d$, two observed samples of the same group share a given member with probability $(1-d)^2$, so their pairwise overlap shrinks quadratically. The generative model instead estimates each $q_{kv}$ from all hyperedges assigned to the group. The planted-group experiment below varies $d$ directly. If overlap clustering matches our model across the dropout range, we will report that the contribution reduces to the heuristic plus two-level message passing, and we will drop the generative machinery.

Why not just use MC-HNN's latent type codebook? Soft types give hyperedges extra semantic freedom, but the incidence matrix stays fixed. A member missing from a basket stays missing, and a thousand near-duplicate hyperedges remain a thousand units. We run MC-HNN at matched parameter count and also combine it with our induced structure, to test whether the two are complementary rather than redundant.

Why not just let HSL add and prune members? HSL can add nodes, but only by feature similarity. On House and Senate, where nodes have little or no feature information, that signal is weak. Co-occurrence across hyperedges is the only evidence available there. The featureless benchmarks and the member-dropout corruption are exactly where the two methods should come apart. If HSL matches us there, the co-occurrence argument fails.

Why not just use a standard Dirichlet or HDP prior? Wang and Blei's junk-topic result predicts that a single coupled hyperparameter will either split real groups or spawn many small noise groups. The prior ablation tests this through the number of inferred groups and the purity of recovered groups at matched held-out likelihood.

Proposed Experiments

The decisive check is synthetic. We plant $K$ groups with overlapping supports and heavy-tailed sizes. Observed hyperedges are generated as member subsets with dropout $d$ between 0 and 0.7, plus background noise nodes. Node labels depend on group membership, with no node features. We measure group recovery by F1 under optimal group matching, recovery of held-out memberships, and node classification. The prediction is that our model's recovery advantage over overlap clustering and HSL grows with $d$. The prediction fails if the gap stays flat.

On real data, we apply two controlled corruptions to Yummly10k, CA-DBLP, Walmart, House, and Senate. The first is DeepHGSL's random hyperedge deletion at 25%, 50%, and 75%. The second is independent member dropout, which pruning cannot undo. Metrics are node-classification accuracy and the number of hyperedge units the network processes. We also measure held-out hyperedge completion: given all but one member of a held-out hyperedge, rank the missing member.

The headline test is Yummly10k at 75% deletion against DeepHGSL's reported 53.7%, and member dropout on House and Senate against rerun MC-HNN and HSL. A secondary analysis checks whether the recovered groups on Walmart and CA-DBLP are coherent, using product categories and author affiliations as external references. Results are reported alongside the compression ratio of latent groups to observed hyperedges.