Higher order trade-offs in hypergraph community detection
Jiaze Li, Michael T. Schaub, Leto Peel, Department of Data Analytics and Digitalisation , Maastricht University, 6200 MD Maastricht, The Netherlands RWTH Aachen University, Aachen, Germany · 2026
Read Higher order trade-offs in hypergraph community detection by Jiaze Li, Michael T. Schaub, Leto Peel, Department of Data Analytics and Digitalisation , Maastricht University, 6200 MD Maastricht, The Netherlands RWTH Aachen University, Aachen, Germany (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-10502.txt.
Introduction
Jiaze Li, Michael Schaub, and Leto Peel find trade offs in group hunts on hypergraphs. A hypergraph links sets of nodes at once, not just pairs. Groups in such a net are sets that link more in than out. Past graph tools do not map clean to this case.
Sets in a hypergraph come in many sizes. A large set can span groups in ways a pair can not. That makes group sense less clear. The team work out the trade offs this brings. They show what must be lost or gained in each call. The work sets a base for group tools on rich nets.
Catalog record
| CREATOR | Jiaze Li, Michael T. Schaub, Leto Peel, Department of Data Analytics and Digitalisation , Maastricht University, 6200 MD Maastricht, The Netherlands RWTH Aachen University, Aachen, Germany |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 138 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-10502
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Higher order trade-offs in hypergraph community detection Jiaze Li, Michael T. Schaub, Leto Peel, Department of Data Analytics and Digitalisation , Maastricht University, 6200 MD Maastricht, The Netherlands RWTH Aachen University, Aachen, Germany Abstract Extending community detection from pairwise networks to hypergraphs introduces fundamental theoretical challenges. Hypergraphs exhibit structural heterogeneity with no direct graph analogue: hyperedges of varying orders can connect nodes across communities in diverse configurations, introducing new trade-offs in defining and detecting community structure. We address these challenges by developing a unified framework for community detection in non-uniform hypergraphs under the Hypergraph Stochastic Block Model. We introduce a general signal-to-noise ratio that enables a quantitative analysis of trade-offs unique to higher-order networks, such as which hypergedges we choose to split across communities and how we choose to split them. Building on this framework, we derive a Bethe Hessian operator for non-uniform hypergraphs that provides efficient spectral clustering with principled model selection. We characterize the resulting spectral detectability threshold and compare it to belief propagation limits, showing the methods coincide for uniform hypergraphs but diverge in non-uniform settings. Synthetic experiments confirm our analytical predictions and reveal systematic biases toward preserving higher-order and balanced-shape hyperedges. Application to empirical data demonstrates the practical relevance of these higher-order detectability trade-offs in real-world systems. Introduction Community detection is central to interpreting mesoscale network structure, revealing groups of nodes with similar connectivity patterns that provide a coarse-grained summary often aligned with functional organization [ 13 , 27 ] . In the classical setting of dyadic, or pairwise , networks, this intuition translates most commonly into identifying densely connected subgraphs, and a broad range of algorithmic and theoretical tools have been developed, including modularity maximization [ 7 ] , spectral clustering [ 38 ] , and probabilistic generative models such as the stochastic block model (SBM) [ 17 ] . The SBM has enabled a comparatively mature theoretical understanding of community detection, particularly in the case of sparse graphs. These theoretical contributions include sharp detectability thresholds, near-optimal inference algorithms and closely related efficient spectral methods based on the non-backtracking and the Bethe Hessian operators [ 11 , 18 , 30 ] . Yet, many complex systems cannot be faithfully represented by pairwise interactions alone. In domains ranging from scientific collaboration and human contact patterns to microbial consortia and chemical reaction networks, interactions regularly involve more than two entities at a time, reflecting intrinsic multiway dependencies [ 6 , 24 , 32 ] . Recognizing the importance of such higher-order interactions has led to growing interest in higher-order network representations and corresponding models and algorithms, with hypergraphs emerging as a natural and widely used framework; see, e.g., recent reviews [ 5 , 4 , 6 ] . Here we consider aspects of applying the established utility of community detection to the broadly applicable setting of hypergraphs. Transferring the notion of community structure from graphs to hypergraphs is far from straightforward. In dyadic networks community structure can be largely described by edge density: the strength of community structure corresponds to the relative difference in the density of edges within communities compared to across communities. Hyperedges connect varying numbers of nodes, and these multiway interactions can couple nodes from different communities in a variety of configurations. Figure 1 illustrates some examples of these different configurations in community partitions in graphs and hypergraphs. The resulting structural heterogeneity has no direct analogue in graphs and raises fundamental questions: how should community structure be defined and detected when interactions span multiple orders, and how do different hyperedge orders and “shapes” (i.e., how hyperedges split across communities) jointly influence the recoverability of planted structure? Unlike the graph setting, where detectability and algorithmic optimality are now relatively well understood, the theoretical understanding of community detection in hypergraphs remains much less developed. Figure 1: Different configurations of community structure in graphs and hypergraphs. (a) In dyadic networks, there is a single type of edge connecting pairs of nodes and edges can only be split across communities in one way. (b) In hypergraphs, hyperedges of different orders connect varying numbers of nodes and we must choose which order of hyperedge to split across communities, e.g., do we prefer to preserve the higher order 4-hyperedges or the lower order 2-hyperedges? (c) Hyperedges can connect more than two nodes and can be split across communities in multiple ways. Here, we consider two different shapes of a 4-hyperedge, a balanced shape and an imbalanced shape. In particular, higher-order interactions introduce new trade-offs in describing strength of community structure that have not been characterized systematically so far. Existing work has focused on extending graph-based community detection methods to hypergraphs without explicitly addressing these higher-order trade-offs. The study of hypergraph analogues of modularity maximization [ 9 ] , spectral methods based on hypergraph Laplacians [ 15 ] , non-backtracking operators [ 8 ] , and approximate-inference schemes derived from belief propagation [ 3 , 29 ] provide useful building blocks, but a more unified picture of detectability in general non-uniform hypergraphs is still lacking. In this work, we take an important step toward such a picture by studying the detectability of community structure in hypergraphs under the Hyper Stochastic Block Model (HSBM) [ 3 , 8 ] . In the HSBM nodes are assigned to latent communities and hyperedges of various orders are generated according to community-dependent probabilities. This framework generalizes the SBM to higher-order interactions and provides a clear link between observed hypergraph structure and latent communities, enabling principled evaluation of community detection methods via their ability to recover planted structure. Importantly, the HSBM also allows us to formulate and analyze detectability of communities in hypergraphs. Previous work has derived BP-based detectability thresholds for uniform HSBMs, where all hyperedges have the same order [ 3 ] , and for specific cases of non-uniform settings [ 8 , 29 ] . Here we generalize these results by introducing a unified signal-to-noise ratio (SNR) for hypergraphs that applies to arbitrary mixtures of hyperedge orders and any number of communities. This SNR quantifies the relative strength of different hyperedge orders and shapes, and thereby provides an important tool to analyze the novel trade-offs that arise in hypergraph communities. Our algorithmic approach builds on spectral clustering via the Bethe Hessian (BH) [ 30 ] . We derive a BH operator for non-uniform hypergraphs that serves as a symmetric, n\times n linearization of belief propagation for the HSBM and retains a spectral correspondence to the hypergraph non-backtracking operator [ 8 , 35 ] . This correspondence inherits principled model-order selection via negative BH eigenvalues and provides node-level embeddings via BH eigenvectors, while offering substantial computational advantages over non-backtracking operators. Using our BH formulation, we characterize a spectral detectability threshold in terms of our SNR and compare it to a more general theoretical detectability limit derived for the same HSBM family using belief propagation. We show that the two thresholds coincide in the uniform case, implying that BH-based spectral clustering reaches the theoretical limit, whereas for non-uniform HSBMs the BH spectral threshold is strictly weaker. Synthetic experiments confirm these analytical predictions and further highlight systematic biases in BH-based clustering according to the order and shape of hyperedges, which we can explain in terms of our