Abstract
Hypergraphs are the gold standard for representing group interactions, but their complexity often leads researchers to simplify them into standard pairwise graphs. This paper introduces the $n$-projected graph ($G_n$) framework to quantify how much higher-order information is actually needed for accurate hyperedge prediction. Evaluating 15 real-world datasets, we find that while 3-way interactions ($n=3$) provide a massive performance boost over pairwise models, further increasing the order yields diminishing returns.
Introduction
In data science, relationships are typically modeled as graphs with pairwise edges. However, many real-world interactions—such as scientific collaborations or protein complexes—occur in groups. Hypergraphs naturally capture these dynamics, but they are computationally expensive. Researchers often resort to "clique expansion," reducing hyperedges to pairwise links, which discards higher-order nuances. This study investigates the fundamental engineering trade-off: is a simple pairwise approximation enough, or must we model every possible group interaction?
Methodology
The authors propose the $n$-projected graph ($G_n$) framework. $G_2$ represents standard pairwise interactions. $G_3$ models 3-way interactions by treating pairs of nodes from the original hypergraph as nodes in the projected graph. By stacking these representations, the authors can incrementally add higher-order information to a logistic regression classifier to perform hyperedge prediction.
Datasets
The framework was tested on 15 datasets across 8 domains, including communication (Email-Enron), social proximity (Contact-Primary-School), and coauthorship (DBLP). These datasets vary in scale from 1,000 to 2.5 million hyperedges.
Key Results and Insights
The study identifies the "Power of Three": moving from $n=2$ to $n=3$ improves AUC-PR by an average of 61% for size-4 hyperedges and 94% for size-5 hyperedges. In contrast, moving from $n=3$ to $n=4$ for size-5 hyperedges only yielded a 6% average improvement.
Higher-order information is particularly critical for distinguishing true hyperedges from "cliques"—groups where members are connected pairwise but don't act as a cohesive unit. The authors used conditional entropy to show that when 3-way interactions are "surprising" (not easily predicted by pairwise links), the benefit of using $G_3$ is maximized.
Conclusion
While higher-order information is essential for capturing the nuances of group interactions, there is a clear point of diminishing returns. For most hyperedge prediction tasks, $n=3$ represents the optimal balance between complexity and accuracy. Future work will explore if deep learning models can better exploit $n > 3$ information and if these patterns hold for other tasks like community detection.
Summary updated