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%.
하이퍼그래프는 노드와 하이퍼엣지(노드의 부분집합)로 이루어져 있는 데이터로, 여러 재료들로 이루어진 레시피, 패션 아이템으로 이루어진 의상, 그리고 연구자들 간의 협업과 같은 그룹 관계를 자연스럽게 나타낼 수 있다. 하이퍼엣지 예측문제(HP)는 현재 누락되었거나 미래에 발생할 하이퍼엣지를 예측하는 것으로, 여러 응용 분야에서 주목을 받고 있다. 그러나 노드의 개수가 n일 때, 가능한 전체 하이퍼엣지의 수는 2^n으로 매우 많기 때문에, 전체 후보 집합 중 가장 유망한 하이퍼엣지를 찾아내는 것은 현실적으로 불가능하다. 따라서 기존 연구들은 이를 실제 하이퍼엣지와 가상으로 만든 하이퍼엣지에 대한 분류 문제로 재정의하여 학습 및 평가 과정을 간단하게 만들었다.
본 연구는 HP에 대해 세 가지 중요한 기여를 제시한다. 첫째, HP의 본질과 더 가깝고, 계산적으로 실행 가능하며, 다양한 응용 분야에 더 적합한 새로운 문제 정의를 제시한다. 둘째, 새로운 정의를 기반으로 몇가지 현상들을 관찰한다: (a) 분류 문제에서의 성능은 HP 성능을 정확하게 반영하지 않고 종종 음의 상관관계를 가지며, (b) 간단한 규칙 기반 방법이 고차원의 딥러닝 접근법보다 우수한 성능을 보인다. 마지막으로, 마스킹 기반 학습을 활용한 MHP라는 새로운 HP 방법을 제안하고, 기존의 모든 HP 방법보다 최대 약 66%까지 성능이 우수함을 입증한다.
