Scalable detection of higher-order interactions in network data

Abstract

Complex systems are routinely measured and represented through pairwise networks, even when the underlying interactions involve more than two units at once. Recovering this latent hypergraph structure from pairwise measurements is a fundamental inverse problem, but as the space of candidate hyperedges grows exponentially with system size, scalable hypergraph reconstruction at arbitrary interaction orders is out of reach for existing methods. Here we cast hypergraph reconstruction as a local signal-to-noise discrimination problem and use this locality to build a fast algorithm that reconstructs hypergraphs up to any interaction order. Across diverse synthetic and real-world systems our method achieves a high recovery accuracy of latent hypergraph structure while reconstructing hypergraphs up to orders of magnitude more quickly than current approaches. Our approach also yields an information-theoretic detectability boundary that sharply predicts which latent hyperedges are recoverable from pairwise measurements.