Fast method reveals hidden group interactions in network data
Scalable detection of higher-order interactions in network data
Social and Information Networks
Summary
Many complex systems are measured as pairs of connected parts, even when the true connections involve groups of parts working together. Detecting these hidden group interactions from pairwise data is very hard because the number of possible groups grows very fast as systems get bigger. The authors propose a fast method that detects group interactions of any size by looking for local signals that stand out from noise. Their method recovers hidden group connections accurately and much faster than existing techniques across many datasets.
What this means in practice
- •For network analysts: Identify complex group relationships beyond pairs in social, biological, or communication networks using observable pairwise interactions.
- •For cybersecurity teams: Detect coordinated multi-party attacks or interactions hidden within pairwise traffic data to improve threat detection accuracy and speed.
Authors
Yingbang Zang, Yanting Zhang, Alec Kirkley
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 higher-order interactions are recoverable from pairwise measurements.