Beyond Pairwise Interactions: Unveiling the Role of Higher-Order Interactions via Stepwise Reduction
arXiv:2411.05685 · doi:10.1038/s42005-025-02157-3
Abstract
Complex systems, such as economic, social, biological, and ecological systems, usually feature interactions not only between pairwise entities but also among three or more entities. These multi-entity interactions are known as higher-order interactions. Hypergraph, as a mathematical tool, can effectively characterize higher-order interactions, where nodes denote entities and hyperedges represent interactions among multiple entities. Meanwhile, all higher-order interactions can also be projected into a number of lower-order interactions or even some pairwise interactions. Whether it is necessary to consider all higher-order interactions, and whether it is with little loss to replace them by lower-order or even pairwise interactions, remain a controversial issue. If the role of higher-order interactions is insignificant, the complexity of computation and the difficulty of analysis can be drastically reduced by projecting higher-order interactions into lower-order or pairwise interactions. We use link prediction, a fundamental problem in network science, as the entry point. Specifically, we evaluate the impact of higher-order interactions on link predictive accuracy to explore the necessity of these structures. We propose a method to decompose the higher-order structures in a stepwise way, thereby allowing to systematically explore the impacts of structures at different orders on link prediction. The results indicate that in some networks, incorporating higher-order interactions significantly enhances the accuracy of link prediction, while in others, the effect is insignificant. Therefore, we think that the role of higher-order interactions varies in different types of networks. Overall, since the improvement in predictive accuracy provided by higher-order interactions is significant in some networks, we believe that the study of higher-order interactions is both necessary and valuable.
14 pages, 6 figures
References in corpus (23)
- Emergence of scaling in random networks
- The structure of scientific collaboration networks
- Link Prediction in Complex Networks: A Survey
- Who is the best connected scientist? A study of scientific coauthorship networks
- Clustering and preferential attachment in growing networks
- Predicting Missing Links via Local Information
- Networks beyond pairwise interactions: structure and dynamics
- How to project a bipartite network?
- The physics of higher-order interactions in complex systems
- Scale-free networks are rare
- Simplicial models of social contagion
- Simplicial Closure and higher-order link prediction
- Dynamics on higher-order networks: A review
- What are higher-order networks?
- Evaluating Link Prediction Methods
- Higher-order interactions shape collective dynamics differently in hypergraphs and simplicial complexes
- Uncovering collective listening habits and music genres in bipartite networks
- Inference of hyperedges and overlapping communities in hypergraphs
- Empirical analysis of web-based user-object bipartite networks
- How Much and When Do We Need Higher-order Information in Hypergraphs? A Case Study on Hyperedge Prediction
- A Survey on Hypergraph Neural Networks: An In-Depth and Step-By-Step Guide
- HPRA: Hyperedge Prediction using Resource Allocation
- Discriminating abilities of threshold-free evaluation metrics in link prediction