Learning Multi-Order Block Structure in Higher-Order Networks
This work addresses the challenge of accurately characterizing mesoscale organization in higher-order networks for researchers in network science and data analysis, though it is incremental as it builds on existing stochastic block models.
The authors tackled the problem of modeling higher-order networks (hypergraphs) by proposing a multi-order stochastic block model that relaxes the universal assumption of single-order models, allowing different affinity patterns for distinct interaction orders. They found that this approach yields better predictive performance and uncovers more interpretable mesoscale organization in real-world networks, with concrete improvements over single-order models.
Higher-order networks, naturally described as hypergraphs, are essential for modeling real-world systems involving interactions among three or more entities. Stochastic block models offer a principled framework for characterizing mesoscale organization, yet their extension to hypergraphs involves a trade-off between expressive power and computational complexity. A recent simplification, a single-order model, mitigates this complexity by assuming a single affinity pattern governs interactions of all orders. This universal assumption, however, may overlook order-dependent structural details. Here, we propose a framework that relaxes this assumption by introducing a multi-order block structure, in which different affinity patterns govern distinct subsets of interaction orders. Our framework is based on a multi-order stochastic block model and searches for the optimal partition of the set of interaction orders that maximizes out-of-sample hyperlink prediction performance. Analyzing a diverse range of real-world networks, we find that multi-order block structures are prevalent. Accounting for them not only yields better predictive performance over the single-order model but also uncovers sharper, more interpretable mesoscale organization. Our findings reveal that order-dependent mechanisms are a key feature of the mesoscale organization of real-world higher-order networks.