CS Paper Radar

Scalable detection of higher-order interactions in network data

Yingbang Zang, Yanting Zhang, Alec Kirkley

cs.SI ·submitted 2026-09-27 14:54 UTC · v2

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.

Comment
27 pages, 5 figures, 6 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Interpretable Hypergraph Learning via Neural Additive Models

cs.LG cs.SI ·2026-10-05 ·Shihan Feng, Xin Zheng, Shiyi Yang, Ren Wang, Chudi Zhong +1 more
benchmark similarity 0.62
Abstract · 16 pages, 8 figures, 13 tables

Hypergraphs offer a natural framework for modeling networked data, where dependencies among entities are governed by higher-order interactions. While hypergraph learning methods such as hypergraph neural networks have demonstrated remarkable predictive performance, most existing approaches rely on black-box message-passing architectures, making it difficult to disentangle the contributions of node attributes and higher-order structural information. To address this challenge, we introduce the hypergraph neural additive network (HGNAN), an inherently interpretable framework for learning on hypergraph-structured data. HGNAN extends classical neural additive models to higher-order relational data by integrating feature-wise nonlinear decomposition with hypergraph-aware structural aggregation, enabling transparent prediction for both node- and hyperedge-level tasks. Extensive experiments on benchmark datasets demonstrate that HGNAN achieves performance comparable with state-of-the-art hypergraph learning methods while providing intrinsic and meaningful interpretability.

0.13

The Power of Bidegeneracy for Hypergraph Data Structures

cs.DS cs.DBcs.DM ·2026-11-03 ·Marco Bressan, Stefano Clemente, Giacomo Fumagalli, Daniel Paul-Pena, C. Seshadhri
similarity 0.62
Abstract

A hypergraph $H = (V,E)$ describes a set system over a vertex universe $V$. Hypergraphs are increasingly popular in network science, as they represent interactions between subsets of vertices. A natural challenge is to design a data structure for $H$ to quickly answer basic questions about it, e.g. how many neighbors a vertex $v$ has or whether a hyperedge contains a vertex subset $S$. Such questions are trivial for graphs, for which we simply inspect the adjacency list. The gold standard, from a data structures perspective, would be near-linear time preprocessing and query answering in (poly)logarithmic time. Since this is unlikely for arbitrary $H$, we ask for well-motivated hypergraph properties that can make such a goal possible. We introduce bidegeneracy, a measure of hypergraph sparsity that strictly generalizes many other measures, including bounded degree, bounded rank, and bounded $\infty$-degeneracy. We show that bounded bidegeneracy yields fast hypergraph data structures. For a large set of fundamental queries, including their listing and sampling versions, we obtain near-linear preprocessing and (poly)logarithmic query time. Moreover, direct reductions from assumptions like the Orthogonal Vectors Conjecture suggest that, without assumptions on the input, these structures require almost-quadratic preprocessing or almost-linear query time. We use bidegeneracy to compute a compressed representation of $H$ and perform careful reductions to stabbing and searching problems in $\mathbb{R}^d$. Our framework significantly extends the well-studied "partial matching" problem of finding database entries through wildcard search. It also uncovers an intriguing connection between hypergraph sparsity, compression, and the complexity of hypergraph primitives. We also find remarkably low bidegeneracy in hypergraph datasets from the literature, suggesting practical consequences.

0.25

Unsupervised Multi-Scale Gromov-Wasserstein Hypergraph Alignment

cs.LG cs.SI ·2026-08-30 ·Lutz Oettershagen, Honglian Wang, Aristides Gionis
top venue similarity 0.61
Abstract · Accepted at ICDM 2026

We study unsupervised hypergraph alignment, where the goal is to infer node correspondences between two hypergraphs using only structural information, without node features, labels, seed matches, or side information. Direct higher-order formulations can represent hyperedge interactions faithfully, but they can be computationally demanding and cumbersome for non-uniform hypergraphs. Graph-reduction approaches introduce a different challenge: clique expansions keep the alignment problem on the original node set but collapse all hyperedge evidence into one pairwise graph, whereas bipartite expansions preserve incidence structure but enlarge the problem from nodes to nodes plus hyperedges. We introduce FALCON (Filtration-based hypergrAph aLignment via Cross-scale Optimal traNsport), an unsupervised optimal-transport framework for hypergraph alignment. Instead of representing each hypergraph by a single collapsed clique graph, FALCON constructs a filtration-induced sequence of clique-based co-occurrence dissimilarity matrices and jointly aligns all levels through one shared multi-scale Gromov--Wasserstein (GW) objective. The shared transport plan enforces a globally consistent node correspondence across filtration levels while avoiding the auxiliary hyperedge nodes introduced by bipartite expansion. Experiments on perturbation benchmarks derived from real-world hypergraphs show that FALCON is robust to structural noise and in almost all cases outperforms strong graph- and hypergraph-alignment baselines.

0.43

More Is Better? Exploring Latent Correspondence in Federated Hypergraph Learning

cs.LG cs.DC ·2026-10-29 ·Bo Yan, Siming Zhang, Siqi Li, Hang Yu
similarity 0.61
Abstract

Federated hypergraph learning with latent cross-client hyperedge correspondence poses fundamental identifiability and computational challenges, as the same local release can correspond to multiple global hypergraph structures. We characterize the tractability of recovering these latent correspondences, showing tractable pairwise assignment but generally intractable multi-client hyperedge matching. Building on this characterization, we derive a cross-entropy decomposition that reveals when local prediction can outperform predictors fitted with additional cross-client information. Motivated by this principle, we introduce Federated Adaptive Spectral Training with Representation Alignment (FedASTRA), which learns correspondence-invariant diffusion representations through adaptive heat diffusion and masked latent prediction while communicating model parameters only. We establish its asymptotic optimality with respect to the permitted local information and prove global population-risk convergence under explicit conditions on recovery, representation, and update alignment. Experiments on eight real-world datasets demonstrate the effectiveness of FedASTRA against identifier-free federated graph and hypergraph methods. On ogbn-papers100M, FedASTRA reaches the performance-communication Pareto frontier, achieving 50.07 Accuracy and 29.73 Macro-F1 while communicating only 59.60 MiB per round.

0.15

Uncovering higher-order interactions from memory in observed dynamics

cs.SI physics.soc-ph ·2026-10-14 ·Arthur Rondeau, Alain Barrat, Roland Bouffanais
similarity 0.58
Abstract

Many complex systems involve group interactions, which can readily be represented by higher-order structures such as hypergraphs. However, when observing a system's dynamical evolution, establishing whether that evolution actually results from higher-order interactions, or whether pairwise interactions suffice to explain the data, remains a challenge. Even in the simple case of a temporal sequence of nodes visited during a diffusion process, such a task is intricate. Indeed, group interactions leave their traces as memory on the observed nodes, while path dependence in a purely pairwise process can mimic that same footprint without any group structure. To resolve this, we propose an inference pipeline based on a hidden Markov model (HMM) that tests, directly from an observed sequence of nodes carrying no group labels, whether higher-order interactions are required to describe the dynamics. The HMM latent states represent higher-order interactions, seen as hyperedges of an unobserved hypergraph, so that their detection becomes a model selection problem between the HMM class and a class of null models without higher-order interactions. We first validate this approach on synthetic node sequences generated from random walks on graphs and hypergraphs, showing that it recovers both the number and the composition of the underlying hyperedges, while correctly rejecting them when the generating process is pairwise. As a second step, we consider a validation based on empirical data, namely empirical trajectories of ball possession in football matches. This application shows that the pipeline goes beyond providing statistical evidence of the presence of higher-order interactions, and yields interpretable underlying structures: the recovered hyperedges map directly onto recognizable tactical team formations.

0.26

Motifs in temporal hypergraphs

cs.SI cs.DSphysics.soc-ph ·2026-09-10 ·Quintino Francesco Lotito, Lorenzo Betti, Federico Battiston, Giuseppe Francesco Italiano
similarity 0.58
Abstract

Network motifs, recurrent local patterns of interactions in graphs, provide fundamental insights on the interplay between structure and functionality in complex systems. Many real-world systems are not well represented by traditional static pairwise networks, as interactions may involve groups of nodes, occur over time, or encode directionality. In this paper, we introduce temporal motifs for hypergraphs and directed hypergraphs, extending motif analysis to timestamped many-body interactions. We formalize the corresponding mining problem, study the combinatorial structure of these motifs, and develop exact algorithms for their enumeration. In particular, we propose a dynamic programming algorithm that substantially reduces the computational cost of motif mining, achieving orders of magnitude speedups on empirical datasets. We also introduce a null model for temporal hypergraphs to assess the statistical over- and under-expression of motifs. Applying the proposed framework to real-world datasets from different domains, including face-to-face contacts, scientific collaborations, e-mail exchanges, and Bitcoin transactions, we show that temporal hypergraph motifs reveal distinct forms of local organization across systems. Finally, we demonstrate their use as an exploratory tool through focused case studies on persistent patterns in scientific collaborations and e-mail communications.

0.22

Hypergraph Representation Learning with Hyperlink Random Effects

cs.LG stat.ML ·2026-10-03 ·Zimeng Li, Shihao Wu, Gongjun Xu, Ji Zhu
similarity 0.57
Abstract

Hypergraphs record multi-way interactions among entities. Extracting information from the combinatorial structure underlying observed multi-way interactions is a central task in many real-world problems. Existing methods face several limitations. First, many deep architectures for hypergraphs do not explicitly exploit the potential low-rank structure, which can sacrifice parsimony and interpretability in the learned representations. Second, many low-rank-based methods operate on tensor representations, which typically require hyperlinks to have uniform sizes and thus limit their applicability to general hypergraphs with non-uniform hyperlink sizes. Third, many methods ignore the fact that hyperlinks often arise from heterogeneous mechanisms. For example, medical symptoms may co-occur in the profiles of patients with very different conditions, and such heterogeneity should be incorporated into the learning process. In this work, we develop a general framework for hypergraph representation learning using hyperlink random effects while exploiting the low-rank structure in hypergraphs. The proposed framework accommodates latent heterogeneity in hyperlink formation while preserving entity interaction patterns. We establish identifiability of the model parameters and theoretical guarantees of representation-level recovery under this framework. The framework allows flexible specifications for the hyperlink random effects; in this paper, we study three choices: categorical, Gaussian mixture, and score-based effects, and develop corresponding estimation algorithms. Through simulation studies, we demonstrate the effectiveness of the proposed method in recovering latent structure and capturing heterogeneous interaction patterns. Empirical studies on real-world hypergraph datasets further illustrate the practical utility of our approach.

0.15

Theory-Driven Network Backbones for Bipartite Projections

cs.SI cs.DB ·2026-11-12 ·Nikos Salamanos, Paula Gheorghiade, Tom Brughmans, Michele Coscia
similarity 0.57
Abstract · 13 pages, 10 figures, 3 tables

Collecting data, including network data, is subject to measurement error. Network backboning is the process of statistically validating each edge in a network to estimate the probability that the edge is born of noisy measurements. The current backboning literature provides approaches in two classes: structural and statistical. The classes differ in many respects, but they share one commonality: the test used to determine whether to filter out noisy edges is data-agnostic; it does not take into account what the network is representing. However, the nodes and edges of all non-synthetic networks correspond to specific real-world entities, whose dynamics determine how the edge-generating process operates. In this paper, we propose the first in a new class of network backboning algorithms: a theory-driven backboning approach that allows us to encode known dynamics into the backboning process. The resulting backbone embeds the encoded theory and produces a network compatible with it, rather than one that obeys a data-agnostic network process, as in the structural and statistical backboning classes. We specifically focus on the case of projecting and backboning a bipartite structure. We do so by allowing users to specify an Agent-Based Model for the two types of agents (nodes) in the network and by performing Simulation-Based Inference to fit the observed bipartite structure and, as a result, reconstruct the true relationships between the two classes of agents. We test our framework both on synthetic data -- where we have perfect information about the edge-generating process -- and in a case study using archaeological data on amphorae retrieved from different archaeological sites. Our approach improves latent-edge recovery over conventional backboning methods in synthetic experiments and reveals interpretable archaeological patterns despite imperfect model fit.

0.44