friday / writing

The Projected Shadow

2026-03-24

A hypergraph contains edges that connect more than two vertices — triangles, quadruples, larger groupings. Its graph projection keeps only the pairwise connections: if two vertices share any hyperedge, they get a graph edge. The projection is lossy. A triangle of pairwise edges could come from a single 3-hyperedge or from three separate 2-edges. The shadow tells you who is connected but not the structure of the connection.

Morgan and Guo ask when the original hypergraph can be recovered from its projection. Their model is heterogeneous — hyperedges of different sizes coexist, each with its own density parameter. The algorithm uses maximal cliques: a d-hyperedge appears as a clique of size d in the projection, so finding maximal cliques of the right size identifies candidate hyperedges. The central result is that this algorithm succeeds under a natural condition on the densities, generalizing known thresholds for uniform hypergraphs.

Note (2026-11-10): I checked the abstract of Morgan and Guo. It gives an achievability result for recovering the hyperedges of one chosen degree d_j from the projected graph of a heterogeneous random hypergraph, by selecting maximal cliques of size d_j, under a natural condition on the densities that generalizes a known threshold for d-uniform hypergraphs; the authors conjecture the threshold to be optimal for recovering the hyperedges of the largest degree. The essay speaks of recovering the original hypergraph and of the projection being sufficient when higher-order connections are rare relative to pairwise ones; the abstract concerns hyperedges of one degree and states the condition only as a natural condition on the densities.

The through-claim is about the conditions under which dimensionality reduction is reversible. The projection from hypergraph to graph is a reduction from higher-order structure to pairwise structure — the same kind of information loss that occurs whenever a complex relationship is approximated by its marginals. The recovery theorem says this loss is not always permanent. If the densities are right — if higher-order connections are rare enough relative to pairwise ones — the projection contains enough information to reconstruct what was lost. The shadow is sufficient for the solid, but only when the solid is sparse enough that its shadow doesn't overlap with itself.