# HyperSearch: Prediction of New Hyperedges through Unconstrained yet Efficient Search

arXiv: https://arxiv.org/abs/2510.17153 · HTML: https://mlsanity.com/paper/2510.17153/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 25 references that are in the map.
- First posted on arXiv 20 Oct 2025.

## Builds on (most cited first, 11 of 11)

- [Simplicial Closure and higher-order link prediction](https://mlsanity.com/paper/1802.06916/) (2018)
- [Hyper-SAGNN: a self-attention based graph neural network for hypergraphs](https://mlsanity.com/paper/1911.02613/) (2019)
- [Structural Deep Embedding for Hyper-Networks](https://mlsanity.com/paper/1711.10146/) (2017)
- [How Much and When Do We Need Higher-order Information in Hypergraphs? A Case Study on Hyperedge Prediction](https://mlsanity.com/paper/2001.11181/) (2020)
- [Link Prediction in Social Networks: the State-of-the-Art](https://mlsanity.com/paper/1411.5118/) (2014)
- [HyGNN: Drug-Drug Interaction Prediction via Hypergraph Neural Network](https://mlsanity.com/paper/2206.12747/) (2022)
- [A Survey on Hypergraph Mining: Patterns, Tools, and Generators](https://mlsanity.com/paper/2401.08878/) (2024)
- [AHP: Learning to Negative Sample for Hyperedge Prediction](https://mlsanity.com/paper/2204.06353/) (2022)
- [Group interactions modulate critical mass dynamics in social convention](https://mlsanity.com/paper/2103.10411/) (2021)
- [HPRA: Hyperedge Prediction using Resource Allocation](https://mlsanity.com/paper/2006.11070/) (2020)
- [Hypergraph patterns and collaboration structure](https://mlsanity.com/paper/2210.02163/) (2022)

## Abstract (arXiv)

Higher-order interactions (HOIs) in complex systems, such as scientific collaborations, multi-protein complexes, and multi-user communications, are commonly modeled as hypergraphs, where each hyperedge (i.e., a subset of nodes) represents an HOI among the nodes. Given a hypergraph, hyperedge prediction aims to identify hyperedges that are either missing or likely to form in the future, and it has broad applications, including recommending interest-based social groups, predicting collaborations, and uncovering functional complexes in biological systems. However, the vast search space of hyperedge candidates (i.e., all possible subsets of nodes) poses a significant computational challenge, making naive exhaustive search infeasible. As a result, existing approaches rely on either heuristic sampling to obtain constrained candidate sets or ungrounded assumptions on hypergraph structure to select promising hyperedges. In this work, we propose HyperSearch, a search-based algorithm for hyperedge prediction that efficiently evaluates unconstrained candidate sets, by incorporating two key components: (1) an empirically grounded scoring function derived from observations in real-world hypergraphs and (2) an efficient search mechanism, where we derive and use an anti-monotonic upper bound of the original scoring function (which is not antimonotonic) to prune the search space. This pruning comes with theoretical guarantees, ensuring that discarded candidates are never better than the kept ones w.r.t. the original scoring function. In extensive experiments on 10 real-world hypergraphs across five domains, HyperSearch consistently outperforms state-of-the-art baselines, achieving higher accuracy in predicting new (i.e., not in the training set) hyperedges.