Detection and Reconstruction of a Random Hypergraph from Noisy Graph Projection

2025/06/21 by Gong, Shuyang, Li, Zhangsong, Xu, Qiheng
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2506.17527

Abstract

For a d-uniform random hypergraph on n vertices in which hyperedges are included i.i.d. so that the average degree in the hypergraph is n^δ+o(1), the projection of such a hypergraph is a graph on the same n vertices where an edge connects two vertices if and only if they belong to a same hyperedge. In this work, we study the inference problem where the observation is a noisy version of the graph projection where each edge in the projection is kept with probability p=n^-1+α+o(1) and each edge not in the projection is added with probability q=n^-1+β+o(1). For all constant d, we establish sharp thresholds for both detection (distinguishing the noisy projection from an Erdős-Rényi random graph with edge density q) and reconstruction (estimating the original hypergraph). Notably, our results reveal a detection-reconstruction gap phenomenon in this problem. Our work also answers a problem raised in \citeBGPY25+.

Citations

• Partial and Exact Recovery of a Random Hypergraph from its Graph Projection
• Thresholds for Reconstruction of Random Hypergraphs From Graph Projections
• Relational Learning in Pre-Trained Models: A Theory from Hypergraph Recovery Perspective
• Community detection in the hypergraph stochastic block model and reconstruction on hypertrees
• Optimal and exact recovery on general non-uniform Hypergraph Stochastic Block Model
• Weak Recovery Threshold for the Hypergraph Stochastic Block Model
• Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix
• Sparse random hypergraphs: Non-backtracking spectra and community detection
• The planted matching problem: Sharp threshold and infinite-order phase transition
• Partial Recovery in the Graph Alignment Problem
• Phase Transitions for Detecting Latent Geometry in Random Graphs
• Planting trees in graphs, and finding them back
• Random intersection graphs with communities
• The Price of Privacy in Untrusted Recommendation Engines
• Information-theoretic limits of selecting binary graphical models in high dimensions

Related

• Partial and Exact Recovery of a Random Hypergraph from its Graph Projection
• Thresholds for Reconstruction of Random Hypergraphs From Graph Projections
• Graph Reconstruction from Noisy Random Subgraphs
• Non-adaptive Learning of Random Hypergraphs with Queries
• Inferring Hidden Structures in Random Graphs