Prediction is NOT classification: on formulation and evaluation of hyperedge prediction

Abstract

A hypergraph, consisting of nodes and hyperedges (i.e., subsets of nodes), naturally represents group relations, such as recipes consisting of ingredients, outfits consisting of fashion items, and collaborations among researchers. The problem of hyperedge prediction (HP), which involves predicting future or missing hyperedges, has received considerable attention due to its applications, including recipes, outfits, and collaborator recommendations. However, due to the vast number of candidate hyperedges, which is about 2^n for n nodes, it is infeasible to identify the most promising ones among the entire candidate set. Thus, the problem has been reformulated as the classification of real hyperedges and artificially generated ones in order to simplify both training and evaluation. Our work offers three significant contributions regarding HP. First, we present a new formulation that is semantically aligned, computationally feasible, and better suited for various applications. Second, we make striking observations based on this new formulation: (a) the performance in the classification formulation does not accurately reflect HP performance and is often negatively correlated, and (b) simple rule-based methods outperform advanced deep-learning approaches. Lastly, we present MHP, a novel HP method that utilizes masking-based training and outperforms all competing HP methods by up to 66%.