When Is a Graph Enough? Recovery and Removal of Multiway Interactions by Dr Chenghao Guo

Abstract

Graphs are a convenient way to represent relational data, but many interactions are intrinsically multiway. A meeting among several people, for example, may be recorded only through pairwise links among participants. This simplification raises a fundamental question: after replacing higher-order relational data with a graph, what information and computational tasks are preserved? The study first investigates whether a graph retains sufficient information to recover the original multiway interactions. By modeling these interactions as hyperedges, efficient reconstruction algorithms are developed and sharp recovery thresholds are identified. Below the threshold, the graph can be efficiently inverted; above it, recovery becomes information-theoretically impossible.

The work then examines planted clique detection, a key inference problem in high-dimensional statistics. Unlike classical models that assume independent background edges, real-world data often contain local interactions that violate this assumption. The study shows that these background multiway interactions act as noise that can obscure the planted clique. Remarkably, even when reconstructing the original multiway interactions is impossible, the proposed algorithm can remove their induced correlations while preserving the planted signal. Theoretical results demonstrate that planted clique detection under dependent background noise is computationally equivalent to detection under independent noise. Together, these findings clarify when multiway interactions should be reconstructed and when their effects can instead be removed.

Biography

Chenghao Guo is a researcher whose work lies at the intersection of theoretical computer science, statistics, and machine learning. He earned his Ph.D. in Electrical Engineering and Computer Science from the Massachusetts Institute of Technology (MIT), where he was advised by Guy Bresler and Yury Polyanskiy, following undergraduate studies in the Yao Class at Tsinghua University. His research focuses on the computational foundations of high-dimensional statistical inference and optimization, with particular interests in average-case complexity, smoothed complexity, random graphs, and signal recovery.