Source-linked AI summary
Generative hypergraph clustering: from blockmodels to modularity
Philip S. Chodrow, Nate Veldt, Austin R. Benson
TL;DR
Hypergraph clustering lacks models and algorithms that directly represent higher-order interactions and heterogeneous degrees and edge sizes. This paper introduces a Poisson degree-corrected hypergraph stochastic blockmodel with approximate maximum-likelihood inference and modularity-based Louvain algorithms. The methods exhibit distinct detectability regimes from dyadic projections, scale well in the AON case, and recover clusters in data with matched higher-order structure.
Problem
Hypergraph clustering has relatively few models and algorithms that directly accommodate higher-order interactions, heterogeneous node degrees, and varying hyperedge sizes.
Method
The paper proposes a Poisson degree-corrected hypergraph stochastic blockmodel and derives approximate maximum-likelihood modularity objectives with general and All-Or-Nothing Louvain algorithms.
Results
Hypergraph methods detect planted clusters beyond graph-based detectability limits and recover metadata-correlated clusters at higher rates when higher-order structure is appropriately matched.
Takeaways & Limitations
Matching the generative model to higher-order data is important for hypergraph clustering and reveals structure that dyadic methods may miss.
Takeaways & Limitations
The general symmetric modularity objective remains an avenue for future work, while the reported clustering heuristics can select among multiple local optima.
Abstract
from arXiv · showhide
Hypergraphs are a natural modeling paradigm for a wide range of complex relational systems. A standard analysis task is to identify clusters of closely related or densely interconnected nodes. Many graph algorithms for this task are based on variants of the stochastic blockmodel, a random graph with flexible cluster structure. However, there are few models and algorithms for hypergraph clustering. Here, we propose a Poisson degree-corrected hypergraph stochastic blockmodel (DCHSBM), a generative model of clustered hypergraphs with heterogeneous node degrees and edge sizes. Approximate maximum-likelihood inference in the DCHSBM naturally leads to a clustering objective that generalizes the popular modularity objective for graphs. We derive a general Louvain-type algorithm for this objective, as well as a a faster, specialized "All-Or-Nothing" (AON) variant in which edges are expected to lie fully within clusters. This special case encompasses a recent proposal for modularity in hypergraphs, while also incorporating flexible resolution and edge-size parameters. We show that AON hypergraph Louvain is highly scalable, including as an example an experiment on a synthetic hypergraph of one million nodes. We also demonstrate through synthetic experiments that the detectability regimes for hypergraph community detection differ from methods based on dyadic graph projections. We use our generative model to analyze different patterns of higher-order structure in school contact networks, U.S. congressional bill cosponsorship, U.S. congressional committees, product categories in co-purchasing behavior, and hotel locations from web browsing sessions, finding interpretable higher-order structure. We then study the behavior of our AON hypergraph Louvain algorithm, finding that it is able to recover ground truth clusters in empirical data sets exhibiting the corresponding higher-order structure.
1 introduction
Hypergraphs extend graphs by representing higher-order interactions among arbitrary numbers of nodes, motivating clustering methods that preserve such structure. The paper proposes a generative hypergraph model and scalable modularity-based algorithms, with experiments showing distinct detectability regimes and metadata-aligned cluster recovery.
- Motivation: Hypergraphs generalize graphs by allowing hyperedges to connect arbitrary numbers of nodes, rather than exactly two.Graphs are therefore a special case of hypergraphs.
- Motivation: Hypergraph clustering targets closely related or interconnected node groups and supports applications from parallel computation to higher-order network analysis.The cited applications include circuit design, image segmentation, semisupervised learning, gene expression, food webs, and online social communities.
- Motivation: Bipartite generative representations assume node memberships within a hyperedge are conditionally independent, which conflicts with all-or-nothing interactions in some data.Event co-attendance networks provide an example where group membership in an interaction is not naturally independent.
- Contributions: The paper proposes a degree-corrected hypergraph stochastic blockmodel that generates clustered hypergraphs with heterogeneous degree distributions and hyperedge sizes.Approximate maximum-likelihood estimation connects the model to a modularity objective and accompanying Louvain algorithms.
- Results: Hypergraph methods detect planted clusters in regimes where graph-based methods necessarily fail and recover metadata-correlated clusters more often when higher-order structure is matched.The results support matching generative assumptions to the higher-order structure of the data.
2 the degree-corrected hypergraph stochastic blockmodel
The DCHSBM models hyperedge counts with Poisson rates determined by node degrees and group memberships, then estimates parameters and hard node labels through approximate coordinate-ascent maximum likelihood. This formulation connects inference to modularity-style clustering objectives.
- Model: The DCHSBM extends degree-corrected graph blockmodels to hypergraphs with group labels, node-specific degree parameters, and unordered node tuples as possible hyperedges.Each node receives a group assignment and a parameter governing its degree.
- Model: Hyperedge multiplicities at each node tuple follow a Poisson distribution whose rate combines ordering multiplicity, degree parameters, and an affinity function of group memberships.The model permits weighted hyperedges with nonnegative integer multiplicities, accommodating repeated hyperedges on the same node set.
- Likelihood: The likelihood factors across possible node tuples, and inference estimates group labels, affinity parameters, and degree parameters from an observed weighted-hyperedge data set.The log-likelihood separates the term depending on labels and affinities from terms depending on degrees or only on the data.
- Inference: Coordinate ascent alternates between estimating affinity and degree parameters conditional on labels and estimating labels conditional on those parameters.The parameter estimates are conditioned on the current label estimate, while the label update optimizes the label-dependent likelihood term.
- Caveats: The affinity estimate is locally optimal conditional on current labels, and the framework remains approximate because greedy Louvain optimization can select among multiple local optima.The authors caution that failure to recover ground truth does not necessarily imply failure of the stated local likelihood objective.
- Inference: The label-estimation stage naturally produces modularity-type objectives for hypergraph clustering.The paper develops this connection as the basis for its clustering algorithms.
3 hypergraph modularities
Symmetric hypergraph modularities depend on the partition pattern of group memberships within each hyperedge, yielding generalized cut and volume terms. The All-Or-Nothing special case emphasizes hyperedge homogeneity while retaining tunable edge-size and resolution parameters.
- Symmetric modularities: Symmetric affinity functions treat hyperedges with the same partition vector alike, depending on group-membership repetition counts rather than specific group labels.The partition vector records group sizes in descending order, with ties broken arbitrarily.
- Symmetric modularities: Generalized cut terms count hyperedges split according to a specified partition pattern, while generalized volume terms aggregate products of group volumes for that pattern.Efficient combinatorial identities and update formulas are provided for evaluating these terms.
- Caveats: When group volumes vary, the conditional parameter estimates used in the modularity derivation are approximations, and optimizing the general symmetric objective remains future work.The authors relate this approximation to graph modularity’s tendency toward approximately equal-sized clusters.
- All-Or-Nothing modularity: The All-Or-Nothing affinity distinguishes whether a hyperedge lies entirely within one cluster and is suited to interactions whose occurrence depends strongly on group homogeneity.It is also emphasized for scalable computation.
- All-Or-Nothing modularity: AON hypergraph modularity penalizes hyperedges containing nodes from two or more clusters and reduces to standard dyadic modularity when all hyperedges have size two.The cut term for size k counts split hyperedges of that size.
- All-Or-Nothing modularity: Unlike strict modularity, the AON objective leaves edge-size weights and resolution parameters free, allowing emphasis on selected hyperedge sizes and preferred cluster sizes.These parameters can be adaptively estimated rather than specified in advance.
4 hypergraph maximum-likelihood louvain
The paper develops general and specialized Louvain-style algorithms for hypergraph modularity objectives. HMLL greedily updates cluster assignments, while the AON variant simplifies computation and improves scalability, with cluster-count control remaining indirect.
- Symmetric HMLL: HMLL optimizes the symmetric hypergraph modularity objective through Louvain-style greedy updates to cluster labels.The algorithm evaluates objective changes from moving clusters to adjacent clusters and accepts the largest positive improvement until none remains.
- Symmetric HMLL: Nodes begin in singleton clusters, and the algorithm repeatedly moves prior clusters as units without collapsing hyperedges or discarding their structure.This preserves hyperedge sizes and partition information during agglomerative updates.
- Symmetric HMLL: The general update function computes volume changes combinatorially but must evaluate affinity values across all incident hyperedges for cut changes.This makes general HMLL implementation substantially more involved than the specialized AON procedure.
- All-Or-Nothing HMLL: AON HMLL checks only whether each edge lies wholly within one cluster, enabling simplified data structures, supernode collapsing, memory savings, and rapid objective updates.The method stores edge sizes and focuses on hyperedges spanning multiple supernodes.
- Limitations: HMLL does not directly control the number of returned clusters, and optimizing the general symmetric modularity objective remains future work.Users can tune affinity parameters, but experimentation may be required and an exact cluster count may be unattainable.
5 experiments with synthetic data
Synthetic experiments compare hypergraph and dyadic Louvain methods on runtime, cluster recovery, and detectability. Hypergraph inference can exploit edge sizes that dyadic projections pool together, but neither method dominates in every regime.
- Runtime: HMLL outperforms Graph MLL on smaller synthetic instances by adjusted Rand index, while recovery becomes comparable on larger instances.
- Runtime: HMLL and Graph MLL have nearly indistinguishable runtimes, indicating that dyadic clique projections are unnecessary for accuracy or performance in this experiment.
- Runtime: A two-stage procedure using GMLL to initialize HMLL produces the strongest recovery results in the reported synthetic experiment.The procedure first generates an intermediate partition with GMLL and then refines it with HMLL.
- Dyadic projections and the detectability threshold: Graph-based Louvain detects much, but not all, of the assortative regime and entirely fails in the disassortative detectable region shown in Figure 2.The gap from the theoretical threshold reflects the stagewise greedy algorithm’s lack of optimality guarantees.
- Dyadic projections and the detectability threshold: AON HMLL detects planted partitions in parameter regimes where GMLL does not, including cases where some edge sizes are predominantly between-cluster.It can use both 2-edges and 3-edges when 2-edges are largely between-cluster, while showing limited detection when both sizes are between-cluster.
- Dyadic projections and the detectability threshold: GMLL can detect planted partitions in combinations of p2 and p3 where HMLL cannot, so pooling edge sizes through dyadic projection is useful in some regimes.Neither algorithm is optimal inference, and an optimal hypergraph method could extend the detectable regime.
6 experiments with empirical data
The paper evaluates hypergraph clustering on empirical contact, congressional, purchasing, and browsing-derived data, comparing affinity models and clustering algorithms. Results show that model-data alignment governs recovery: AON HMLL excels when homogeneous-edge structure is plausible, while dyadic methods can perform better under pairwise structure.
- Empirical data: The study analyzes school contact, congressional bill and committee, purchasing, and hotel-browsing hypergraphs with node labels providing ground-truth or metadata comparisons.School hyperedges represent jointly proximate people; congressional hyperedges represent bill sponsor–cosponsor groups or committees; purchasing hyperedges represent products bought together; browsing hyperedges represent hotels viewed in sessions.
- Model comparison: No single affinity function has the lowest BIC across all data sets, indicating distinct higher-order structures.Relative Plurality is preferred for both congressional committee data sets, while an edge-homogeneity affinity is preferred elsewhere.
- Contact hypergraphs: AON HMLL correctly recovers the supplied class partitions in both primary-school and high-school contact networks.Graph Louvain conflates or splits classes, while Graph MLL perfectly recovers primary-school student labels but misclassifies three high-school students.
- Large hyperedges: AON HMLL performance depends strongly on whether the AON affinity is a plausible generative mechanism for the data.It outperforms dyadic variants on trivago-clicks, where AON has the lowest BIC, but performs much worse on walmart-purchases, where Pairwise is preferred.
- Large hyperedges: In congressional bill data, Pairwise has lower or comparable BIC than AON, and dyadic methods outperform AON HMLL in both House and Senate cases.Unnormalized GMLL performs best for house-bills and senate-bills, whereas normalized GMLL is preferable in walmart-purchases.
- Interpretation and limitations: Community-detection results are limited by implicit structural assumptions, sparsity, and greedy Louvain optimization that samples only local optima.Failure to recover ground truth does not necessarily mean failure at local likelihood maximization; domain expertise is needed to assess whether DCHSBM-AON assumptions fit the data.
7 discussion
The paper connects hypergraph clustering to a degree-corrected generative model, derives modularity-like objectives and scalable Louvain algorithms, and identifies methodological and theoretical limitations for future work.
- Contributions: The DCHSBM yields a symmetric modularity-like objective that includes All-Or-Nothing modularity as a special case.This links hypergraph modularity to tunable modeling assumptions.
- Contributions: Louvain-like algorithms optimize these objectives and are highly scalable for the AON affinity function.The paper embeds this heuristic in an alternating approximate maximum-likelihood scheme.
- Limitations: The inference framework is limited by an NP-hard optimization step, possible local estimation bias, and Louvain-style affinity restrictions.The approximation is exact only when clusters are of roughly equal sizes, and the agglomerative approach is limited to affinity functions promoting within-edge homogeneity.
- Future directions: Detectability theory for the more flexible DCHSBM remains substantially more complex than for the dyadic DCSBM.
FUNDING
The research received support from multiple governmental and industry funders, and the authors reported no competing interests; reproducibility materials are available.
- Funding: The research was supported by ARO, ARO MURI, NSF, and JP Morgan Chase & Co.
- Competing interests: The authors declare that they have no competing interests.
- Data and software: Software and data sufficient to reproduce and extend the experiments and analysis are available in a repository.
- Data and software: The data are also hosted in packaged format.
SUPPLEMENTARY INFORMATION
The supplementary material details parameter identifiability, degree-related maximum-likelihood calculations, and an algebraic derivation involving ordered node tuples and affinity terms.
- Parameter identifiability: Without normalization, degree parameters and affinity functions are not identifiable because infinitely many parameter choices yield the same likelihood.A normalization condition selects one parameterization from this family.
- Parameter estimation: The weighted number of hyperedges containing each node defines its degree parameter in the maximum-likelihood calculation.The derivation establishes that the maximum-likelihood estimate is θ̂ = d when the stated identity holds.
- Parameter estimation: After enforcing normalization, the likelihood objective's second term becomes independent of θ, allowing θ to be estimated by maximizing K(θ).
- Parameter estimation: The first-order optimality conditions determine the maximizing θ_i under the normalization constraint.
- Algebraic derivation: The derivation introduces ordered node tuples, hyperedge-size-specific tuple sets, cluster-label vectors, and degree-parameter vectors.Each unordered hyperedge corresponds to b_R ordered tuples, supporting the subsequent identity calculation.
- Algebraic derivation: The supplementary calculation proceeds by inserting the relevant expression into Q, isolating constant-affinity terms, and solving the resulting first-order condition for ω.The derivation concludes with the stated result.
d derivation of (14)
The derivation applies a previously established identity to obtain the third line of the displayed calculation.
- Derivation of (14): The third line follows by applying identity (21).
e fast evaluation of volume terms
The paper reduces volume-moment calculations by grouping label vectors according to distinct partition vectors, then updates the resulting quantities efficiently as nodes move between clusters.
- Moment computation: The moments of cluster volumes, µ_k = P¯ℓ vol(ℓ)^k, can be computed in O(n^k) time.
- Partition-vector simplification: Proposition 1 expresses each U_p using one representative term for every equivalence class of cluster label vectors under index permutations.For a partition vector p, the number of nonzero elements is r = ∥p∥0.
- Recursive derivation: Peeling off the rth product term provides the recursive step used in the proof of Proposition 1.
- Dynamic updates: Proposition 1 yields an efficient recursive update for U_p when the label vector changes after moving nodes between clusters.The update is obtained by applying the proposition to the original and modified label vectors.
- Dynamic updates: The set of U_p values can be computed once from scratch and then updated during optimization rather than recomputed at every step.
f derivation of (15)
The derivation specializes the affinity function to the all-or-nothing case and simplifies the resulting modularity objective using ordered tuples, volume products, and the hypergraph cut function.
- All-or-nothing affinity: For a size-k hyperedge, the all-or-nothing log affinity equals log ω_k^0 plus δ(z_R)β_k.Here β_k = log ω_k^1 − log ω_k^0.
- Tuple representation: The derivation distinguishes unordered k-tuples R_k from ordered k-tuples T_k and uses π(v) for products of vector entries.
- Objective simplification: Using θ_R = d_R and the definition of cut_k(z), the all-or-nothing modularity objective is reduced to a simplified form.
g all-or-nothing hypergraph
The all-or-nothing specialization supports a faster Louvain procedure that repeatedly collapses and expands the hypergraph while evaluating node moves through simple cut-status changes.
- Algorithmic specialization: The AON special case enables a considerably faster Louvain algorithm using a supernode strategy and simpler data structures than the original adjacency hyperarray.
- Collapse-and-expand loop: Each outer iteration collapses the current clustering into a reduced hypergraph, performs a Louvain step, and expands the reduced clustering back.
- Node-move optimization: During the Louvain step, the algorithm evaluates the objective change from moving each collapsed node to candidate clusters.
- Node-move optimization: Candidate clusters for a node are its adjacent clusters, and the algorithm selects the move with maximum modularity change.
- Fast evaluation: AON evaluations are faster because volume updates require only power-sum updates, while cut updates inspect whether incident hyperedges switch between cut and uncut.