Hypergraphs provide a natural way of representing group relations, whose complexity motivates an extensive array of prior work to adopt some form of abstraction and simplification of higher-order interactions. However, the following question has yet to be addressed: How much abstraction of group interactions is sufficient in solving a hypergraph task, and how different such results become across datasets? This question, if properly answered, provides a useful engineering guideline on how to trade off between complexity and accuracy of solving a downstream task. To this end, we propose a method of incrementally representing group interactions using a notion of n-projected graph whose accumulation contains information on up to n-way interactions, and quantify the accuracy of solving a task as n grows for various datasets. As a downstream task, we consider hyperedge prediction, an extension of link prediction, which is a canonical task for evaluating graph models. Through experiments on 15 real-world datasets, we draw the following messages: (a) Diminishing returns: small n is enough to achieve accuracy comparable with near-perfect approximations, (b) Troubleshooter: as the task becomes more challenging, larger n brings more benefit, and (c) Irreducibility: datasets whose pairwise interactions do not tell much about higher-order interactions lose much accuracy when reduced to pairwise abstractions.
하이퍼그래프는 그룹 관계를 표현하는 가장 기본적인 그래프 모델이다. 그룹 관계는 복잡한 고차 상호 작용 정보를 담고 있기 때문에 흔히 추상화되거나 단순화되어 사용되기 마련이다. 하지만 그룹 상호 작용에 관해서 아직 해결되지 않은 중요한 질문이 있다. 하이퍼그래프 과제를 해결할 때 그룹 상호 작용 정보가 얼마나 필요하며, 이러한 필요성이 서로 다른 데이터 세트에서 어떻게 다르게 나타나는가? 이 질문에 대한 답을 찾을 수 있다면 하이퍼그래프 과제를 해결할 때 복잡도와 정확도 사이에서 적절한 균형을 찾을 수 있도록 도와주는 유용한 지침서를 얻게 될 것이다. 이 질문에 접근하기 위해 본 논문에서는 크기가 n인 그룹 상호 작용 정보를 담는 방법으로 n-order projected graph 개념을 제안하여 하이퍼그래프를 점진적으로 정확하게 표현하고, n이 증가함에 따라 과제 해결의 정확도가 어떻게 변하는지 측정한다. 하이퍼그래프 과제로는 하이퍼엣지 예측을 사용한다. 하이퍼엣지 예측은 그래프 링크 예측을 하이퍼그래프에 적용한 것으로 그래프 모델의 정확도를 평가하기 위한 표준 수단이다. 실제 데이터 15 세트에서 얻은 실험 결과는 다음과 같은 세 가지 메시지로 요약된다. (a) 수익 감소: 작은 n으로도 충분히 완벽에 가까운 정확도를 얻을 수 있다. (b) 문제 해결사: 과제가 어려워질수록 큰 n이 도움이 된다. (c) 단순화 불가: 쌍별 상호 작용이 고차 상호 작용에 관한 정보를 적게 가지고 있는 데이터 세트는 쌍별 추상화로 단순화시킬 때 정확도가 현저히 감소한다.
