# How Much and When Do We Need Higher-order Information in Hypergraphs? A Case Study on Hyperedge Prediction

arXiv: https://arxiv.org/abs/2001.11181 · HTML: https://mlsanity.com/paper/2001.11181/

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jan 2020.

## Built on by (most cited first, 30 of 31)

- [Double-Scale Self-Supervised Hypergraph Learning for Group Recommendation](https://mlsanity.com/paper/2109.04200/) (2021)
- [Learning Causal Effects on Hypergraphs](https://mlsanity.com/paper/2207.04049/) (2022)
- [A Survey on Hypergraph Neural Networks: An In-Depth and Step-By-Step Guide](https://mlsanity.com/paper/2404.01039/) (2024)
- [HypeBoy: Generative Self-Supervised Representation Learning on Hypergraphs](https://mlsanity.com/paper/2404.00638/) (2024)
- [Self-Organized Polynomial-Time Coordination Graphs](https://mlsanity.com/paper/2112.03547/) (2021)
- [Classification of Edge-dependent Labels of Nodes in Hypergraphs](https://mlsanity.com/paper/2306.03032/) (2023)
- [Neural Predicting Higher-order Patterns in Temporal Networks](https://mlsanity.com/paper/2106.06039/) (2021)
- [AHP: Learning to Negative Sample for Hyperedge Prediction](https://mlsanity.com/paper/2204.06353/) (2022)
- [Adaptive Neural Message Passing for Inductive Learning on Hypergraphs](https://mlsanity.com/paper/2109.10683/) (2021)
- [Hypergraph Pre-training with Graph Neural Networks](https://mlsanity.com/paper/2105.10862/) (2021)
- [A Survey on Hyperlink Prediction](https://mlsanity.com/paper/2207.02911/) (2022)
- [CHGNN: A Semi-Supervised Contrastive Hypergraph Learning Network](https://mlsanity.com/paper/2303.06213/) (2023)
- [HyGEN: Regularizing Negative Hyperedge Generation for Accurate Hyperedge Prediction](https://mlsanity.com/paper/2502.05827/) (2025)
- [Broad Spectrum Structure Discovery in Large-Scale Higher-Order Networks](https://mlsanity.com/paper/2505.21748/) (2025)
- [Enhancing Hyperedge Prediction with Context-Aware Self-Supervised Learning](https://mlsanity.com/paper/2309.05798/) (2023)
- [Hypergraph Node Representation Learning with One-Stage Message Passing](https://mlsanity.com/paper/2312.00336/) (2023)
- [Learning Higher-Order Interactions from Incomplete Spatiotemporal Data with Mixtures of Hypergraph Laplacians](https://mlsanity.com/paper/2605.17316/) (2026)
- [Understanding Higher-order Structures in Evolving Graphs: A Simplicial Complex based Kernel Estimation Approach](https://mlsanity.com/paper/2102.03609/) (2021)
- [SINGA-Easy: An Easy-to-Use Framework for MultiModal Analysis](https://mlsanity.com/paper/2108.02572/) (2021)
- [VisualTextRank: Unsupervised Graph-based Content Extraction for Automating Ad Text to Image Search](https://mlsanity.com/paper/2108.02725/) (2021)
- [Text is NOT Enough: Integrating Visual Impressions into Open-domain Dialogue Generation](https://mlsanity.com/paper/2109.05778/) (2021)
- [Discovering Personalized Semantics for Soft Attributes in Recommender Systems using Concept Activation Vectors](https://mlsanity.com/paper/2202.02830/) (2022)
- [Reinforced MOOCs Concept Recommendation in Heterogeneous Information Networks](https://mlsanity.com/paper/2203.11011/) (2022)
- [Explanation-Guided Fairness Testing through Genetic Algorithm](https://mlsanity.com/paper/2205.08335/) (2022)
- [Using Graph Neural Networks for Program Termination](https://mlsanity.com/paper/2207.14648/) (2022)
- [Tribe or Not? Critical Inspection of Group Differences Using TribalGram](https://mlsanity.com/paper/2303.09664/) (2023)
- [Tensor Convolutional Network for Higher-Order Interaction Prediction in Sparse Tensors](https://mlsanity.com/paper/2503.11786/) (2025)
- [MARIOH: Multiplicity-Aware Hypergraph Reconstruction](https://mlsanity.com/paper/2504.00522/) (2025)
- [Identifying Group Anchors in Real-World Group Interactions Under Label Scarcity](https://mlsanity.com/paper/2509.20762/) (2025)
- [HyperSearch: Prediction of New Hyperedges through Unconstrained yet Efficient Search](https://mlsanity.com/paper/2510.17153/) (2025)

## Abstract (arXiv)

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.