Broad Spectrum Structure Discovery in Large-Scale Higher-Order Networks
John Hood, Caterina De Bacco, Aaron Schein · 2025
Read Broad Spectrum Structure Discovery in Large-Scale Higher-Order Networks by John Hood, Caterina De Bacco, Aaron Schein (2025) 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-2505-21748.txt.
Introduction
John Hood, Caterina De Bacco, and Aaron Schein introduce, in a 2025 paper, a model for finding structure in networks where groups, not pairs, interact. A drug trial, a group chat, a team: real systems run on multi-way ties, drawn as hypergraphs. Their clumping and scale defeat older tools. The team's key move is to group similar units into classes and let the classes themselves form a second, hidden hypergraph.
Observed interactions are then explained by ties among the classes, compressed into low-rank form so the math stays tractable and the structure stays identifiable. On real data, from drug networks to social ones, the model predicted missing links better than state-of-the-art rivals. It also returned structures a human can read at both the unit and class level. The authors aim to make large higher-order data a routine input to science.
Catalog record
| CREATOR | John Hood, Caterina De Bacco, Aaron Schein |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 131 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-21748
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Broad Spectrum Structure Discovery in Large-Scale Higher-Order Networks John Hood, Caterina De Bacco, Aaron Schein Abstract Complex systems are often driven by higher-order interactions among multiple units, naturally represented as hypergraphs. Understanding dependency structures within these hypergraphs is crucial for understanding and predicting the behavior of complex systems but is made challenging by their combinatorial complexity and computational demands. In this paper, we introduce a class of probabilistic models that efficiently represents and discovers a broad spectrum of mesoscale structure in large-scale hypergraphs. The key insight enabling this approach is to treat classes of similar units as themselves nodes in a latent hypergraph. By modeling observed node interactions through latent interactions among classes using low-rank representations, our approach tractably captures rich structural patterns while ensuring model identifiability. This allows for direct interpretation of distinct node- and class-level structures. Empirically, our model improves link prediction over state-of-the-art methods and discovers interpretable structures in diverse real-world systems, including pharmacological and social networks, advancing our ability to incorporate large-scale higher-order data into the scientific process. I Introduction Complex systems—social, biological, or technological, among other types—are often driven by higher-order interactions among potentially many nodes ( 1 ) . Such systems can be modeled as hypergraphs , which extend the traditional notion of graphs or networks from dyadic or pairwise interactions to those of higher order. Like traditional networks, real-world hypergraphs exhibit mesoscale structure ( 2 , 3 ) —i.e., patterns of interaction among groups of nodes. Broadly, modeling such structure reduces to clustering nodes into groups and characterizing how those groups interact, if at all. In doing so, one reduces the conceptual complexity of the system and the dimensionality of the data, potentially revealing real functional components and underlying mechanisms that drive observed interactions ( 4 ) . Mesoscale structure comes in many different forms, not all of which are tractably modeled. Perhaps the most commonly modeled structure is assortative structure wherein nodes form “communities” and interact mostly with other similar nodes within the same community. Recent work develops methods for efficient detection of these communities in hypergraph data ( 5 , 6 , 7 ) . However, many complex systems also exhibit some degree of disassortative structure, wherein similar nodes form “classes”, but may not interact within these classes. Within these classes, nodes have similar characteristics, but may (exclusively) interact with nodes in other classes. Predator-prey networks in ecology are one such example, wherein species take one of two classes (predator or prey) and interact mostly with species of the other. Even in traditional network settings, any degree of disassortativity (interaction between nodes of different classes) is generally difficult to model. This challenge stems from the baseline complexity required to model both how nodes form groups and how these combinations of groups interact. For hypergraphs, this complexity compounds: higher-order interactions among nodes introduce higher-order interactions within and between groups, resulting in a combinatoric explosion in the number of model parameters that makes estimation impossible. Recent work contends with this by developing models that surface highly restricted forms of disassortativity in hypergraphs, such as structure that can be modeled by a Bethe approximation ( 7 ) , or core-periphery structure wherein a dense core of tightly connected nodes can be distinguished from a sparse loosely connected periphery of nodes ( 8 , 9 ) . Figure 1 : Omni-Hype-SMT models a range of mesoscale structures by assigning nodes to classes and classes to communities. A schematic illustration detailing how Omni-Hype-SMT models a diverse range of mesoscale structure. a) Hypergraph data encodes higher-order interactions among entities, such as bill co-sponsorship (left). Each hyperedge captures a multi-way relationship among nodes. These interactions are represented as a multi-order adjacency tensor \mathcal{A}^{{(:)}} (right), where A^{{(d)}} denotes the order- d adjacency tensor capturing d -way interactions. Such a formulation enables the modeling of complex, non-pairwise relational structures. b) Two parameters \mathrm{\Theta} and \mathrm{W} govern interactions between nodes (e.g., Senators). The node-class membership matrix \mathrm{\Theta} soft clusters similar nodes to classes (e.g., political parties), while the class-community membership matrix \mathrm{W} models interactions between classes through communities (e.g., policy issues). Together, the matrix \mathrm{\Theta}\mathrm{W} captures assortative and disassortative activity between nodes through interactions within and between classes. c) The multi-tensor {\upmu}^{{(:)}} (left) models the observed higher-order adjacency tensors \mathcal{A}^{{(:)}} via symmetric low-rank tensor decomposition using a class affinity tensor \mathrm{\Lambda}^{{(d)}} and a node-class membership matrix \mathrm{\Theta} , shared over orders d . The class affinity multi-tensor \Uplambda^{{(:)}} (right) is further decomposed into community-order rates \gamma^{{(d)}}_{k} and the symmetric outer products of the columns of class-community membership matrix \mathrm{W} , enabling interpretable modeling of multi-way class interactions across different orders. While prior efforts have analyzed a wide range of hypergraph settings theoretically ( 5 , 10 , 11 , 12 , 13 , 14 ) , practitioners are limited to only a few options for modeling mesoscale structure in hypergraphs tractably, each of which has its own drawbacks. One approach restricts analysis to assortative (or similarly constrained) structure, risking mischaracterization of a non-assortative system. Another limits the data to a moderate number of small-order interactions (e.g., three- or four-way) to enable the application of one of the more flexible existing approaches which scale poorly to large, high-order hypergraphs. A third strategy reduces higher-order data to pairwise interactions, potentially discarding crucial structural information through data preprocessing steps ( 15 , 6 , 16 ) . Collectively, these limitations significantly hamper researchers’ ability to leverage large-scale data to draw reliable conclusions regarding the complex systems they study. Motivated by these challenges, this paper introduces a family of probabilistic generative models to tractably capture a wide range of mesoscale structure underlying large-scale hypergraphs. This family encompasses several existing models and spans an omniassortative spectrum of structural patterns, ranging from strictly assortative to highly disassortative. Where along this spectrum a given model falls is dictated by its parameter values. The key idea driving our approach is to jointly cluster nodes into classes and classes into communities . Each clustering is soft, permitting nodes to belong to multiple classes, and classes to multiple communities, as shown in Figure 1 b. The proposed model, which we refer to as Omni-Hype-SMT , avoids the combinatoric explosion associated with modeling all combinations of inter-class interaction by dictating that classes interact exclusively within communities. By clustering classes into communities, Omni-Hype-SMT allows for disassortative interactions between nodes. Since classes are made up of similar nodes, interactions between different classes yield disassortative interactions between nodes of those classes. It is through this framework that the proposed model captures rich and interpretable latent structure governing higher-order interactions among nodes. We leverage a principled framework of statistical inference to rigorously identify mesoscale structure in hypergraph data. Our proposed model is defined such that its parameters are provably identifiable from the data, enhancing the reliability and robustness of their interpretation. Beyond providing a rigorous proof of model identifiability, we derive efficient parameter updates by exploiting the probabilistic nature of the proposed model and conditional distributions within. It is this efficiency that enables large-scale, data-driven discovery of mesoscale structure in practice. We demonstrate how this efficiency enables the development of an extremely simple yet scalable algorithm for generating synthetic hypergraphs with tunable mesoscale structure—a capability largely