HyperSearch: Prediction of New Hyperedges through Unconstrained yet Efficient Search Hyunjin Choo, Fanchen Bu, Hyunjin Hwang Young-Gyu Yoon, Kijung Shin Abstract 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 naïve 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 anti-monotonic) 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. I Introduction In many complex real-world systems, groups of entities engage simultaneously, forming higher-order interactions (HOIs), e.g., scientific collaborations (coauthorship among multiple researchers) [ 1 ] , multi-protein complexes in biological systems [ 2 ] , and multi-user communications [ 3 ] . Hypergraphs , which extend ordinary (pairwise) graphs by allowing hyperedges to connect multiple nodes, offer a natural framework for modeling HOIs. Unlike graphs, where an edge links exactly two nodes, hyperedges capture arbitrary-sized relationships, providing a more expressive representation of complex multi-way interactions. This enables the discovery of structural patterns and behaviors that are often obscured in pairwise frameworks [ 1 , 4 , 5 ] . Given a hypergraph, hyperedge prediction aims to identify hyperedges that are missing or to emerge in the future based on observed data. This task is essential for improving predictive capabilities in systems where HOIs play a crucial role. Hyperedge prediction has broader applications, including: • Group recommendation : In social networks, hyperedge prediction enables the recommendation of groups, each consisting of users sharing common interests or behaviors, enhancing user experience in social media platforms and improving the effectiveness of targeted marketing [ 6 , 7 ] . • Collaboration prediction : In academic and industrial networks, hyperedge prediction helps identify potential collaborations among researchers or companies with shared interests or expertise, optimizing team formation [ 8 , 9 ] . • Drug discovery : In protein and gene networks, hyperedge prediction aids in forecasting functional protein complexes or interacting gene groups, providing insights into disease mechanisms and facilitating drug discovery [ 10 , 11 ] . However, the problem of hyperedge prediction is computationally challenging. The number of potential hyperedges is \mathcal{O}(2^{n}) for n nodes, making exhaustive enumeration infeasible for even medium-sized hypergraphs with hundreds of nodes. While various methods have been proposed to efficiently identify promising hyperedges [ 12 , 13 , 14 , 15 , 16 ] , they suffer from two fundamental limitations: • Constrained candidate sets : Most deep learning-based methods (e.g., Hyper-SAGNN [ 13 ] and NHP [ 16 ] ) frame hyperedge prediction as a binary classification task, distinguishing between existing (positive) and nonexistent (negative) hyperedges. Since enumerating all potential hyperedges is computationally infeasible, negative hyperedges are typically sampled heuristically . Consequently, the performance of such methods strongly depends on the quality of these samples, and how to sample desirable negative hyperedges is a challenging problem itself (see, e.g., AHP [ 15 ] ). Alternatively, MHP [ 14 ] assumes a given query node set Q and predicts hyperedges by initializing hyperedges with nodes in Q and filling the missing nodes. However, the predictions by MHP are constrained by the choice of the query node set Q , and selecting Q is non-trivial in practice, limiting its flexibility and generalizability. • Unjustified structural assumptions : HPRA [ 12 ] constructs candidate hyperedges by adding “similar” nodes based on resource allocation scores. However, these scores strongly depends on observed structures and assume specific local connectivity patterns (e.g., the similarity between two nodes is proportional to the number of neighbors they share), without sufficient justification . Such assumptions make the method less flexible and generalizable, particularly when discovering new hyperedges connecting nodes with low structural similarity. Moreover, HPRA is limited to predicting hyperedges consisting only of nodes within the same connected component, as the similarity between nodes in different components is zero. This constraint limits its applicability in sparse or disconnected hypergraphs. To address these limitations, we propose HyperSearch, a search-based algorithm for hyperedge prediction. HyperSearch is (1) empirically justified , i.e., grounded in real-world observations rather than ad-hoc heuristics, enabling generalization beyond observed structures, and (2) unconstrained yet efficient , i.e., efficiently explores the vast hyperedge search space without being constrained by predefined or sampled subsets. • Empirically justified scores based on observations : The scoring function in HyperSearch is designed based on our observations in real-world datasets. Specifically, we observe that ground-truth hyperedges have significant overlap with observed hyperedges, and we thus assign each candidate hyperedge a score based on the number of observed hyperedges it significantly overlaps with. Additionally, when node features or timestamps are available, we incorporate node feature similarity to prioritize candidates consisting of nodes with similar features, and apply time weighting to emphasize recent hyperedges when computing overlaps, based on our observations. • Efficient search with an anti-monotonic upper bound : The original scoring function is not anti-monotonic, i.e., a subset may have a lower score than its supersets, rendering naïve pruning strategies ineffective. To address this challenge, we derive an anti-monotonic upper bound of the original scoring function. This allows us to efficiently explore the search space with theoretical guarantees, ensuring that discarded candidates are never better than the kept ones w.r.t. the original scoring function. We conduct extensive experiments on 10 real-world hypergraphs across five domains, which demonstrate the empirical superiority of HyperSearch: • Predictive accuracy : HyperSearch consistently outperforms all baseline methods, including deep learning-based and rule-based ones, across diverse datasets, achieving higher accuracy in predicting new hyperedges. • Computational efficiency : HyperSearch achieves faster runtime than deep learning-based methods in most cases, while maintaining near-linear scalability with respect to the input hypergraph size. • Component effectiveness : Ablation studies empirically validate that each component of HyperSearch contributes meaningfully to performance. Reproducibility: The code, datasets, and appendix are available at https://github.com/jin-choo/HyperSearch . The remainder of this paper is organized as follows. In Sect. II , we review related work. In Sect. III , we introduce preliminary concepts and describe the datasets. In Sect. IV , we present empirical observations from real-world datasets. In Sect. V , we detail our proposed method. In Sect. VI , we review our experiments. In Sect. VII , we conclude the paper. II Related Work II-A Similarity-Based Methods Early approaches to hyperedge prediction are mainly based on node similarity measures [ 17 , 18 ] . They either extend node similarity measures to hypergraphs or project hypergraphs into pairwise graphs to apply node similarity measures. HPRA [ 12 ] , for example, constructs hyperedges by selecting a seed node via preferential attachment (i.e., high-degree nodes are more likely to be chosen) and incrementally adding structurally similar nodes, guided by resource allocation scores. Limitations. While such methods are computationally efficient, they primarily depend on local structural similarity (e.g., pairwise similarity) and are limited in capturing the complex higher-order dependencies inherent in real-world hypergraphs. II-B Deep Learning-Based Methods To overcome the limitations of similarity-based approaches, deep learning models have been employed to learn higher-order representations in hypergraphs. DHNE [ 19 ] proposes an MLP-based framework for k -uniform hypergraphs. Hyper-SAGNN [ 13 ] extends this approach by incorporating a self-attention mechanism with graph neural networks, enabling non- k -uniform hyperedge prediction. NHP [ 16 ] further generalizes hyperedge prediction to directed hypergraphs and extends it to inductive settings. Limitations. While these methods demonstrate strong performance, they typically rely on predefined candidate sets and require negative sampling strategies for effective training, as described below. II-C Negative Sampling on Hyperedges Hyperedge prediction is commonly framed as a binary classification task, where the model distinguishes between observed (positive) and nonexistent (negative) hyperedges. Given the combinatorial explosion of potential hyperedges, 1 1 1 The number of potential hyperedges is \mathcal{O}(2^{n}) for n nodes. negative sampling plays a crucial role in defining meaningful training samples, and different negative sampling strategies introduce varying levels of difficulty, directly impacting prediction performance [ 20 ] . To address this challenge, AHP [ 15 ] introduces a generative adversarial training approach that dynamically generates negative samples during training, mitigating the dependence on heuristics. In contrast, MHP [ 14 ] proposes a novel masking-based approach that eliminates the need for explicit negative sampling by formulating hyperedge prediction as a masked node prediction task given a query node set and target size. Limitations. However, they still depend on external constraints, such as the choice of query set in MHP, that inherently limit the candidate space. Consequently, their ability to explore hyperedge candidates remains limited, especially when compared to approaches like ours that search the full space without predefined candidates. (a) Obs. 1. There is significant structural overlap between new hyperedges and observed hyperedges. (b) Obs. 2. Overlap increases as the time difference decreases. Fig. 1: Observations. (a) The average proportion of ground-truth new hyperedges with overlap ratios with low threshold ( >0 ) is comparable to that of the random ones. However, for high thresholds ( \geq 2/3 , \geq 3/4 , and 1 ), the gaps between ground-truth and random ones become significant, suggesting ground-truth new hyperedges are more likely to substantially overlap with existing hyperedges than random hyperedges are . (b) Structural overlap between hyperedges declines as the time gap increases, suggesting new hyperedges tend to overlap more substantially with recent existing ones than with earlier ones . III Preliminaries and Datasets III-A Concepts and Problem Statement III-A 1 Hypergraphs A hypergraph H=(V,E) is defined by its node set V=\{v_{1},v_{2},\ldots,v_{|V|}\} and hyperedge set E=\{e_{1},e_{2},\ldots,e_{|E|}\} . Each hyperedge e_{j} is a non-empty subset of nodes (i.e., \emptyset\neq e_{j}\subseteq V ), and its edge size |e_{j}| is the number of nodes in it. Each hyperedge e_{j} can also be associated with an edge timestamp t_{j} , if such information is available. III-A 2 Problem Definition (Hyperedge Prediction) • Given: 1. a (partially) observed hypergraph H=(V,E) (optionally with edge timestamps t_{j} ’s), 2. the target number k of hyperedges to predict, • To find: a set E^{\prime} of k predicted new hyperedges (i.e., E^{\prime}\subseteq 2^{V}\setminus(E\cup\{\emptyset\}) with |E^{\prime}|=k ), • Aim to: Accurately predict hyperedges that are missing or are to emerge in the future in H . III-B Datasets We use 10 real-world hypergraphs from five different domains, summarized in Table I . 2 2 2 Source 1: https://www.cs.cornell.edu/~arb/data Source 2: https://github.com/HyunjinHwn/SIGIR22-AHP Among them, the Email, Contact, and Tags datasets contain edge timestamps. • Co-citation (Citeseer, Cora) : Each hyperedge consists of publications (nodes) cited by the same paper. • Authorship (Cora-A, DBLP-A) : Each hyperedge consists of publications (nodes) by the same author. • Email (Eu, Enron) : Each hyperedge consists of the sender (node) and all receivers (nodes) of an email. • Contact (High, Primary) : Each hyperedge includes people (nodes) in a group interaction recorded by wearable sensors. • Tags (Math.sx, Ubuntu) : Each hyperedge consists of the set of tags (nodes) added to the same question. TABLE I: Summary of real-world hypergraph datasets. Domain Dataset # Nodes # Hyperedges Timestamps Co-citation Citeseer 1,457 1,078 Cora 1,434 1,579 Authorship Cora-A 2,388 1,072 DBLP-A 39,283 16,483 Email Enron 143 10,883 ✓ Eu 998 234,760 Contact High 327 172,035 ✓ Primary 242 106,879 Tags Math.sx 1,629 822,059 ✓ Ubuntu 3,029 271,233 IV Observations This section highlights our key observations in real-world hypergraphs. We shall later design the scoring function in the proposed method (see Sect. V ) based on these observations. IV-A Significant Overlap between Hyperedges Our first observation is about the overlap between new hyperedges (which we aim to predict) and observed (training) hyperedges. We define the overlap ratio between a new hyperedge e^{\prime} and an observed hyperedge e as OverlapRatio(e^{\prime},e):={|e^{\prime}\cap e|}/{|e|} . Setup: We randomly split the hyperedge set E in each dataset into two subsets: observed hyperedges E_{1} ( 80\% of E ) and (ground-truth) new hyperedges E_{2} (remaining 20\% of E ), using five random seeds. For each new hyperedge in E_{2} , we compute the proportion of observed hyperedges in E_{1} with different overlap-ratio thresholds: >0 , \geq 2/3 , \geq 3/4 , and 1 , and report the values averaged over all hyperedges in E_{2} . As a baseline for comparison, we computed the same statistics on random hyperedges generated by a generalized Chung-Lu (CL) model [ 21 ] , which preserves both node-degree and hyperedge-size distributions of the ground-truth E_{2} . Specifically, in each hyperedge, nodes are replaced with randomly drawn nodes, where each node is selected independently with probability proportional to its degree. Observations: As shown in Fig. 1 (a), the proportions of overlapping observed hyperedges for low threshold ( >0 ) show no significant difference between ground-truth hyperedges and the random ones. However, for higher thresholds ( \geq 2/3 , \geq 3/4 , and =1 ), ground-truth hyperedges exhibit significantly more overlap with observed hyperedges than the random ones. This indicates that new hyperedges are more likely to substantially overlap with existing hyperedges than random hyperedges are, and this difference is statistically significant. 3 3 3 At a higher threshold (spec., \geq 2/3 ), the Kolmogorov–Smirnov (KS) distance between the overlap-ratio distributions of ground-truth and random hyperedges is statistically significant ( KS=0.26 , p<0.01 ), confirming that the two distributions are clearly distinguishable with high confidence. IV-B Temporal Bias in Structural Overlap Our second observation is about the impact of edge timestamps on structural overlap between hyperedges. Setup: We partition the hyperedges E evenly into five equal-sized groups based on their timestamps, arranged in temporal order, where the first group G_{1} contains the earliest hyperedges, the last group G_{5} contains the most recent (latest) ones, etc. For each pair of groups G_{i} and G_{j} with i 2 days). TABLE III: Q1. Accuracy. HyperSearch performs better than all the baselines in most settings. We report the Recall @\mathcal{K} across the six datasets with edge timestamps (no standard deviation since there is only one chronological split). For each setting, the best and second-best methods are highlighted in green and yellow , respectively. Dataset Enron Eu High Primary Ubuntu Math-sx Method ( \downarrow ) / \mathbf{\mathcal{K}} ( \rightarrow ) 1\times 2\times 5\times 1\times 2\times 5\times 1\times 2\times 5\times 1\times 2\times 5\times 1\times 2\times 5\times 1\times 2\times 5\times HyperSearch (Proposed) 16.1 25.6 33.1 12.4 17.3 26.8 14.8 18.3 27.3 7.3 11.8 20.8 12.0 15.4 20.6 12.1 17.3 24.5 CNS 10.3 16.4 29.7 5.1 10.9 22.0 12.6 13.8 18.1 4.5 7.3 11.9 1.6 2.9 6.7 3.4 6.0 11.7 HPRA 1.7 5.8 9.2 3.5 5.8 10.2 9.0 14.8 28.1 4.7 8.1 20.4 1.1 2.0 4.4 2.2 3.9 8.1 MHP 0.3 0.6 3.6 0.3 1.0 3.4 0.9 2.9 7.4 4.3 7.7 21.1 - - - - - - MHP-C 7.6 14.9 22.0 7.4 14.1 22.7 4.3 5.7 8.3 4.1 5.7 9.6 - - - - - - SAGNN-C 6.0 8.2 14.6 8.6 16.0 24.5 7.2 8.5 9.9 5.1 7.9 11.9 2.3 4.3 8.7 4.7 7.9 14.5 NHP-C 13.3 20.3 29.8 8.1 14.9 23.3 9.7 11.6 13.7 5.3 8.5 13.1 1.8 3.5 7.1 3.6 6.1 11.2 MHP-H 4.6 5.4 9.5 4.4 6.5 14.2 9.1 16.3 31.8 5.4 11.4 22.6 - - - - - - SAGNN-H 2.8 3.4 7.1 5.4 8.1 17.8 10.2 18.1 34.1 4.5 9.4 19.5 2.0 3.5 - 3.7 6.5 - NHP-H 4.5 5.2 9.5 4.6 6.7 14.2 12.4 16.6 32.7 6.0 11.7 22.5 1.6 2.8 - 2.6 4.6 - -: out-of-time ( > 2 days). VI-A 1 Datasets We used 10 real-world hypergraphs across five domains, as introduced in Sect. III-B (see Tab. I ). For datasets with edge timestamps (i.e., the email, contact, and tags datasets), we split the datasets chronologically. Specifically, the earliest 80% of hyperedges were used as observed (training) hyperedges E_{1} , while the most recent 20% hyperedges were used as new (test) hyperedges E_{2} we aim to predict. For the other datasets (i.e., the co-citation and authorship datasets), hyperedges were randomly split into 80% observed (training) hyperedges E_{1} and 20% new (test) hyperedges E_{2} , using five different random seeds. For hyperparameter tuning, (the most recent or random) 20% of training hyperedges (i.e., 16% of the total) were set aside for validation. For the splits, we make sure that the same hyperedge does not appear in both E_{1} and E_{2} (which is possible when repeated hyperedges exist). We also make sure that every node in E_{2} also appears in E_{1} , i.e., there are no unseen nodes in E_{2} . The Cora, High, Primary, Ubuntu, and Math datasets contain only hyperedges of size up to 5. For computational efficiency, in the other datasets, only hyperedges up to size 10 were retained before splitting into E_{1} and E_{2} . Additionally, hyperedges with rarely occurring hyperedge sizes ( <1 %) were removed. Details are provided in Sect. B of the online appendix [ 24 ] . VI-A 2 Method Setups All hyperparameters of HyperSearch ( {\epsilon}_{v} , {\epsilon}_{e} , {\epsilon}_{t} , \tau , and \alpha ) were tuned based on validation performance for each dataset, and we used HyperSearch with the fine-tuned hyperparameters to predict new hyperedges in testing. Specifically, we tuned the hyperparameters through a grid search based on the performance w.r.t. Recall @1\times (refer to Sect. VI-A3 ) on the validation set. We considered 27 combinations of the relaxation ratios ( {\epsilon}_{v} , {\epsilon}_{e} , {\epsilon}_{t} ) where each ratio was set to one of \{(\frac{1}{3},\frac{1}{4},\frac{1}{5})\} and additionally {\epsilon}_{v}={\epsilon}_{e}={\epsilon}_{t}=0. In addition, the hyperparameters related to node feature similarity ( \alpha ) and time weighting ( \tau ) were each selected from the candidate set \{0,0.1,1,10\} . We evaluated competing methods, including (1) clique negative sampling (CNS), the strongest sampling-based method from [ 20 ] , (2) HPRA [ 12 ] , and (3) MHP [ 14 ] . The number of predicted hyperedges was set to \{1,2,5\}\times|E_{2}| (see also Sect. VI-A3 for evaluation metrics). • CNS [ 20 ] : It generates hyperedges by (1) randomly selecting an observed hyperedge e , (2) randomly choosing a node in v\in e , and (3) replacing v with another node that has common neighbors with all the other nodes in e . • HPRA [ 12 ] : It generates hyperedge by (1) randomly selecting an initial node v_{0} , (2) iteratively adding nodes with high similarity scores with the already added nodes, based on resource allocation principles (e.g., based on the number of common neighbors). • MHP [ 14 ] : It generates hyperedges by (1) starting from an empty query set, (2) selecting the first node via Preferential Attachment (i.e., high-degree nodes are likely to be chosen), and (3) iteratively adding nodes based on probabilities predicted by a trained model. Note that CNS and HPRA have no hyperparameters to tune. S ee Sect. II for more details and discussions of these baselines. For the baselines that do not use Hypergraph Neural Networks (HNNs), i.e., CNS and HPRA, we further extended them by applying HNNs as a post-processing step to refine hyperedge candidates generated by them. We used different HNN models: MHP [ 14 ] , AHP [ 15 ] , Hyper-SAGNN [ 13 ] , and NHP [ 16 ] . For each HNN model, the suffix “-C” was added when the model was applied to CNS, and the suffix “-H” was added when the model was applied to HPRA. For example, MHP-C refers to the approach where MHP is applied to refine hyperedge candidates generated by CNS, while AHP-H indicates that AHP is used to filter hyperedges predicted by HPRA. In these extended two-stage models, all HNN models were initially trained for the hyperedge prediction task using their respective loss functions in their original implementation. In Sect. C of the online appendix [ 24 ] , we provide a summarizes the hyperparameter search spaces used for the HNN models employed in our experiments. After training, they were applied as a post-processing step to rank and refine the hyperedge candidates generated in the first stage. Specifically, we first used CNS or HPRA to generate twice the target number (i.e., 2k ) of predicted hyperedges, and then used an HNN model to select the top- k ones. VI-A 3 Evaluation Metrics To evaluate prediction performance, we used Recall @\mathcal{K} , a widely adopted metric in (hyper)edge prediction tasks. Recall @\mathcal{K} measures the proportion of ground-truth new hyperedges that are correctly included in the predicted set when \mathcal{K} hyperedges are predicted. In this study, the parameter \mathcal{K} is set to represent a multiple of the number of hyperedges in E_{2} . For instance, if \mathcal{K}=2\times , the number of predicted hyperedges is 2\times|E_{2}| . In addition to Recall @\mathcal{K} , we also evaluated prediction accuracy using the average F1 score [ 25 ] , which considers the similarity between predicted and ground-truth hyperedges. The formal definition and the experimental results using the metric are provided in Sect. D of the online appendix [ 24 ] . VI-B Q1. Accuracy (Tables II & III ) We evaluated the accuracy of HyperSearch and baselines, and the results are presented in Tables II and III . Notably, HyperSearch consistently outperformed all baselines, including deep learning-based models and rule-based approaches (e.g., CNS and HPRA), across most datasets and experimental settings. The only exceptions were in Recall @5\times on the Contact domain datasets (High and Primary), where HyperSearch did not achieve the highest performance. Based on our analysis, this is likely because for those datasets, not enough promising (e.g., those with high overlap with the observed ones) candidates are available. A detailed analysis of these cases is provided in Sect. E of the online appendix [ 24 ] . It is also worth noting that HPRA exhibited scalability limitations, particularly in datasets where the observed hyperedges are divided into multiple connected components (see Sect. I ), performing worse than even simple negative sampling methods (e.g., CNS). In contrast, HyperSearch guaranteed flexible exploration of all promising candidates, regardless of the presence of disconnected components. As shown in Sect. D of the online appendix [ 24 ] , the results were consistent in terms of average F1 score. Case Studies. To qualitatively evaluate the semantic coherence of nodes within predicted hyperedges, we conducted case studies on the two tag datasets, Math and Ubuntu, where the identities of the nodes (tags) are available. For each hyperedge size from 2 to 5, we selected the top-scoring predicted hyperedge generated by HyperSearch, which are: • Math examples : [ring-theory, noetherian], [matrices, vectors, vector-spaces], [group-theory, finite-groups, field-theory, abstract-algebra], [calculus, sequences-and-series, real-analysis, integration, convergence] • Ubuntu examples : [drivers, xorg], [boot, grub2, btrfs], [dual-boot, boot, live-usb, grub2], [partitioning, grub2, 16.04, dual-boot, boot] The results show that HyperSearch effectively identifies groups (hyperedges) of semantically related tags (nodes). (a) Without edge timestamps (b) With edge timestamps (c) Fig. 3: Q2. Runtime comparison. HyperSearch achieves lower runtime than deep learning-based methods (shown in green) in most cases. For each dataset, we report the running time of HyperSearch and baselines. (a) Relaxed overlap count (Sect. V-B1 ) (b) Time weight (Sect. V-B2 ) (c) Feature weight (Sect. V-E ) (d) Fig. 4: Q3. Ablation studies. Each component of HyperSearch meaningfully contributes to its predictive performance. HyperSearch consistently achieves superior or comparable accuracy compared to its variants with some component missing. Fig. 5: Q2. Scalability of HyperSearch. The runtime of HyperSearch scales nearly linearly with the input hypergraph size, with a regression slope of 1.05, indicating strong scalability. In the plot, we report the number of hyperedges and the running time of HyperSearch on each dataset VI-C Q2. Speed and Scalability (Figs. 3 & 5 ) We evaluated the runtime of the proposed method HyperSearch and baselines, and analyzed how HyperSearch scales with the size of the input hypergraph. The results, presented in Fig. 3 and Fig. 5 , reveal the following key observations: • HyperSearch runs faster than deep learning-based methods (highlighted in green in Fig. 3 ) in most cases, demonstrating its superior computational efficiency across diverse datasets. • The runtime of HyperSearch scales almost linearly with the number of hyperedges in the input hypergraph, with a regression slope of 1.05 (Fig. 5 ). This suggests that HyperSearch maintains scalability as the data size increases. In Sect. G of the online appendix [ 24 ] , we show that this scalability persisted on larger synthetic hypergraphs, generated by replicating each original hypergraph up to five times. VI-D Q3. Ablation Studies (Fig. 4 ) We conducted ablation studies on (1) relaxed overlap count in Sect. V-B1 , (2) time weight in Sect. V-B2 , and (3) feature weight in Sect. V-E to assess their impact on performance. Specifically, we compared Recall @1\times between HyperSearch and its variants without each component: (1) HyperSearch-R without relaxation (i.e., \epsilon_{v}=\epsilon_{e}=\epsilon_{t}=0 ), (2) HyperSearch-T without time weight (i.e., \tau=0 ) , and (3) HyperSearch-N without feature weight (i.e., \alpha=0 ). As shown in Fig. 4 , HyperSearch consistently achieves superior or comparable performance compared to its variants, demonstrating that each component meaningfully contributes to its prediction accuracy. VI-E Q4. Hyperparameter Sensitivity (Fig. 6 ) We analyzed the sensitivity of all hyperparameters in HyperSearch, including the relaxation ratios ( {\epsilon}_{v} , {\epsilon}_{e} , {\epsilon}_{t} ), the feature weight ( \alpha ), and the time weight ( \tau ). Specifically, we evaluated Recall @1\times by varying ( {\epsilon}_{v} , {\epsilon}_{e} , {\epsilon}_{t} ) across 28 combinations described in Sect. VI-A2 and by varying \alpha and \tau in \{0,0.1,1,10\} , for each dataset. As shown in Figs. 6 (a) and (b), the optimal relaxation ratios ( {\epsilon}_{v} , {\epsilon}_{e} , {\epsilon}_{t} ) vary across datasets. Fig. 6 (c) shows that, in most cases, HyperSearch achieves peak accuracy at specific \alpha\in\{0.1,1\} for most datasets. On the other hand, as shown in Fig. 6 (d), increasing \tau\in\{0,0.1,1,10\} monotonically improves the accuracy of HyperSearch in 5 out of 6 datasets. These results suggest that the impact of hyperparameters depends on dataset characteristics, as different datasets benefit from varying degrees of relaxation, time weight, and feature weight. Notably, in our experiments, via validation, we found hyperparameters that gave competitive performance, making HyperSearch outperform baselines in most cases. (a) Relaxation ratio \epsilon ’s (Without edge timestamps) (b) Relaxation ratio \epsilon ’s (With edge timestamps) (c) Feature coefficient \alpha (d) Time coefficient \tau Fig. 6: Q4. Hyperparameter sensitivity. The best hyperparameter choices vary from dataset to dataset. The trends of the accuracy of HyperSearch across different hyperparameters ( {\epsilon}_{v} , {\epsilon}_{e} , {\epsilon}_{t} ), \alpha , and \tau . VI-F Additional Experiments Due to the page limit, we provide extra experimental results in the online appendix [ 24 ] , summarized as follows: • Combination with neural networks (Sect. F): We tried applying a filtering step using hypergraph neural networks to refine the predictions of HyperSearch, similar to what we have done for CNS and HPRA (see Sect. VI-A2 ). However, this combination did not consistently improve the performance of HyperSearch, indicating that its score function based on the patterns in real-world hypergraphs (see Sect. IV ) is already effective. • Scalability w.r.t. the number of predictions (Sect. H): The running time of HyperSearch scaled nearly linearly with the number of predictions it produced. • Failure analysis (Sect. E): We investigated potential reasons for the relatively poor performance of HyperSearch on the Contact domain datasets. • Additional metric (Sect. D) and large-scale synthetic datasets (Sect. G) : We confirmed that our results remained consistent in terms of average F1 score, and across large-scale synthetic datasets created by replicating hypergraphs. VII Conclusion and Discussion In this work, we studied the problem of hyperedge prediction. We identified two key limitations of existing methods (Sect. I ). We analyzed and discussed several observations in real-world hypergraphs on structure and timestamps (Sect. IV ). We proposed a novel method, HyperSearch, for hyperedge prediction, consisting of two key components: (1) a scoring function based on our observations to evaluate candidate hyperedges, and (2) an efficient search scheme using an anti-monotonic upper bound of the scoring function (Sect. V ). We conducted extensive experiments on 10 real-world hypergraphs across five domains to validate the empirical superiority of HyperSearch regarding both accuracy and efficiency (Sect. VI ). Discussion on Limitations. While HyperSearch demonstrates strong empirical efficiency, its theoretical complexity is high due to reliance on integer programming [ 22 ] . Moreover, for hypergraphs with features, incorporating the average Jaccard index compromises the anti-monotonicity, as discussed in Sect. V-E , where we discussed a workaround for theoretical rigor (i.e., use 1 as a trivial upper bound of the average Jaccard index). We would like to explore theoretically sound and empirically effective upper bounds when additional information (e.g., node features) is available, as a future direction. Reproducibility. Our code, datasets, and appendix are publicly available at https://github.com/jin-choo/HyperSearch/ .