Source-linked AI summary
Graphs are maximally expressive for higher-order interactions
Tiago P. Peixoto, Leto Peel, Thilo Gross, Manlio De Domenico
TL;DR
The paper addresses the claim that graphs cannot represent higher-order interactions and therefore must be replaced by hypergraphs. It separates graph structure from interaction functions, establishes that graph-based formulations are more general, and shows that hypergraph-attributed phenomena can also arise in graph models. The paper concludes that hypergraph generality and ubiquity are not supported as broad claims.
Problem
The paper examines the claim that graphs are limited to pairwise interactions and that hypergraphs are required for multibody interactions and richer phenomena.
Method
The paper uses conceptual, mathematical, and historical analysis to distinguish graph parameterizations from multivariate interaction functions and compare graph and hypergraph formulations.
Results
Graph-based models can represent multivariate interactions, hypergraph formulations are strict special cases of graph-based formulations, and hypergraph-attributed phenomena can be reproduced by locally tree-like graphs.
Takeaways & Limitations
Modeling multivariate interactions does not require hypergraphs; researchers should distinguish interaction functions from their graph parameterizations when choosing representations.
Takeaways & Limitations
Hypergraphs can still provide interpretable or parsimonious representations for particular systems, but their use requires explicit justification rather than being assumed by default.
Abstract
from arXiv · showhide
We demonstrate that graph-based models are fully capable of representing higher-order interactions, and have a long history of being used for precisely this purpose. This stands in contrast to a common claim in the recent literature on "higher-order networks" that graph-based representations are fundamentally limited to "pairwise" interactions, requiring hypergraph formulations to capture richer dependencies. We clarify this issue by emphasizing two frequently overlooked facts. First, graph-based models are not restricted to pairwise interactions, as they easily accommodate interactions that depend simultaneously on multiple adjacent nodes. Second, hypergraph formulations are strict special cases of more general graph-based representations, as they impose additional constraints on the allowable interactions between adjacent elements rather than expanding the space of possibilities. We show that key phenomenology commonly attributed to hypergraphs -- such as abrupt transitions -- can, in general, be recovered exactly using graph models, even locally tree-like ones, and thus do not constitute a class of phenomena that is inherently contingent on hypergraphs models. Finally, we argue that the broad relevance of hypergraphs for applications that is sometimes claimed in the literature is not supported by evidence. Instead it is likely grounded in misconceptions that network models cannot accommodate multibody interactions or that certain phenomena can only be captured with hypergraphs. We argue that clearly distinguishing between multivariate interactions, parametrized by graphs, and the functions that define them enables a more unified and flexible foundation for modeling interacting systems.
I. INTRODUCTION
The paper challenges the claim that hypergraphs are necessary for higher-order interactions, arguing that graphs support multivariate interactions and are more general than hypergraph formulations. It further shows that phenomenology attributed to hypergraphs can be reproduced by graph-based models.
- Motivation: Recent higher-order-network literature presents hypergraphs as necessary for group interactions and richer dependencies than graphs.The paper identifies this as a foundational claim motivating the universal replacement of graphs by hypergraphs.
- Graphs specify interaction domains: Graphs specify neighborhoods, while multivariate functions on those neighborhoods can depend nonlinearly on multiple adjacent nodes simultaneously.Thus, graph structure does not require interactions to decompose into independent pairwise terms.
- Expressiveness: Hypergraph formulations constrain interactions across fixed node sets, making them strict special cases of more general graph-based formulations.Every phenomenon observable in a hypergraph model is therefore also observable in a sufficiently general graph model.
- Phenomenology: Abrupt transitions and other phenomenology attributed uniquely to hypergraphs can be obtained identically with locally tree-like graph formulations.The paper examines synchronization, population dynamics, epidemic spreading, and equilibrium spin models.
- Scope and evidence: The paper argues that hypergraphs may be useful in particular cases, but claims of universal necessity require empirical support and explicit justification.It distinguishes potentially interpretable or parsimonious representations from assertions that hypergraphs are generally required.
- Graphs specify interaction domains: Ordinary graphs already support coordination, cooperation, threshold dynamics, and other interactions that cannot be classified as pairwise.Examples include bootstrap contagion, complex contagion, interdependent contagion, and triadic percolation.
III. HYPERGRAPHS CONSTRAIN RATHER THAN GENERALIZE INTERACTIONS
The paper argues that graph-based models support arbitrary multivariate interactions, while hypergraph formulations impose additional structural and functional constraints. Thus, hypergraphs are constrained subfamilies rather than generalizations of graph-based interaction models.
- Graphs define interaction domains through neighborhoods, while their node functions can remain arbitrarily complex and multivariate.The graph constrains which variables may appear as function arguments but does not determine the functional form.
- Every hypergraph model maps to a graph-based model, with the hypergraph adding projected-clique constraints rather than expanding the interaction space.The resulting graph model can retain the same multivariate dynamics without requiring the hypergraph parameterization.
- Hypergraph models require adjacent nodes and their functions to align into mutually shared, overlapping cliques.These constraints require a shared interaction function to appear consistently for every node in a hyperedge.
- Graph-based models permit connectivity patterns and multivariate couplings that violate hypergraph mutual-membership constraints.Even small changes in which variables enter node-specific couplings can make a model unavailable to hypergraph formulations while remaining graph-based.
- Calling one formulation “higher-order” and another “pairwise” is arbitrary when both use multivariate coupling functions.The distinction depends on the parameterization and functions together, not on adjacency structure alone.
- Without empirical evidence that real systems satisfy overlapping-clique constraints, the more general graph-based framework has no basis for replacement by hypergraphs.Hypergraph formulations may be useful in selected cases, but their additional constraints require explicit justification.
IV. MULTILAYER NETWORKS GENERALIZE HYPERGRAPHS
The paper shows that multilayer graphs can faithfully represent hypergraph structures and extend them beyond hypergraph constraints. This provides a graph-based representation that preserves hypergraph models while allowing broader structural decompositions.
- Multilayer graphs provide a strictly more general parametric framework in which any hypergraph can be faithfully represented.This extends the earlier functional argument by comparing the parameterizations themselves.
- Ordinary graph projections can lose hyperedge identity because existing cliques may induce additional cliques that are indistinguishable from nominal ones.This creates a non-unique mapping from hypergraphs to single-layer adjacency matrices.
- Edge annotations and layer separation restore a bijection by requiring cliques associated with a hyperedge to share a layer or color.A suitable layer decomposition can isolate hyperedge-specific edges and prevent induced cliques from creating ambiguity.
- Multilayer graphs can generalize each hyperedge from a monolithic unit into a subgraph with arbitrary shape and weight distribution.This adds representational flexibility beyond the original hypergraph grouping.
- Any multilayer hypergraph structure can itself be mapped to a multilayer graph, so hypergraph annotation does not add an unrepresentable structure.The mapping may be non-unique, especially for weighted systems, but remains graph-based.
V. PHENOMENOLOGY MISATTRIBUTED TO HYPERGRAPH MODELING
The paper examines claims that hypergraphs enable dynamics unavailable to graphs and shows that such behaviors can be reproduced by locally tree-like or multilayer graph models.
- Graph-based models can reproduce behaviors claimed to require hypergraph structure, including dynamics without cliques or hyperedges.
- Mean-field analyses do not distinguish hypergraph models from graph-based models for many claimed phenomena.
A. Unsuitability of mean-field calculations
Homogeneous mean-field calculations can erase structural distinctions between hypergraphs and graphs. Alternative graph formulations with the same multivariate functions can therefore produce identical mean-field behavior, including in locally tree-like sparse graphs.
- Hypergraph dynamical models with homogeneous multivariate functions are special cases of more general graph-based formulations.
- Mean-field analysis replaces adjacency variables with ensemble averages, often reducing the dynamics to a scalar self-consistency equation for a global order parameter.For significant classes of systems, this approximation becomes asymptotically exact as N →∞.
- Consequently, mean-field behavior attributed to hypergraph structure may instead reflect the multivariate interaction functions retained by the graph formulation.
- Graph models with multivariate neighborhood functions recover the same mean-field equations as hypergraph models after matching interaction coefficients.
- In sparse settings, these graph formulations are locally tree-like, yet their mean-field macroscopic behavior remains identical to the corresponding hypergraph models.
B. Abrupt transitions
Abrupt transitions commonly attributed to hypergraphs arise from multivariate coordination mechanisms that graph-based models can also represent. Bootstrap percolation, interdependent percolation, and related models generate saddle-node bifurcations and discontinuous transitions without requiring hyperedges.
- Multivariate functions of neighboring states, rather than hypergraph structure, can generate abrupt transitions through cooperative coordination.
- For k > 1, bootstrap percolation requires at least k neighbors to belong simultaneously to the infected cluster, producing a self-consistency equation for the steady state.
- An inflection in F(R) can create three fixed points, and saddle-point bifurcations then produce discontinuous transitions through a bistable regime.
- Interdependent percolation requires simultaneous support from at least one neighbor in each network layer, providing another graph-based coordination mechanism.
- Figure 5 compares saddle-point bifurcations and abrupt order-parameter transitions across bootstrap percolation, interdependent percolation, synchronization, and simplicial contagion.The caption states that the hypergraph and locally tree-like graph versions are identical when they use the same interaction functions.
1. Synchronization
Higher-order synchronization and contagion exhibit abrupt transitions that do not depend on hypergraph parameterization. The same mean-field behavior arises in tree-like graph models with multivariate interactions, while mean-field calculations omit structural correlations.
- 1. Synchronization: The synchronization model uses multivariate coupling terms and hyperedge-order-specific coupling strengths to define the dynamics.
- 1. Synchronization: When K2 + K3 > 0, the synchronization self-consistency function develops an inflection and a saddle-node bifurcation; varying K1 can produce a pitchfork bifurcation.
- 1. Synchronization: Replacing higher-order adjacency tensors with products of graph adjacency entries preserves the same mean-field after rescaling Kl → Kl(N/z)^l.
- 1. Synchronization: The resulting abrupt transition reflects simultaneous synchronization among multiple neighbors, not the presence of cliques, hyperedges, or simplices.
- 1. Synchronization: The paper limits its claim to many specific abrupt-transition results and calls for direct comparison with graph models having multivariate correlations.
- 2. Contagion: For contagion, infection occurs only when all neighbors within a hyperedge are infected, yet the same mean-field and qualitative bifurcation behavior can arise in graph-based models.
C. Stability of ecological systems
The examples distinguish multivariate effects from hypergraph representation: stability changes can arise from multibody functions, while equivalent graph or multilayer formulations remain available.
- Ecological population dynamics: Changing multivariate-term variance changes coexistence stability, while the mean-field dynamics remains invariant when hyperedges are replaced by graphs.The stability change is attributed to multiway products in the interaction function, not to hypergraph structure itself.
- Ecological population dynamics: A model parameterized by a dyadic matrix W is nevertheless frequently presented as a canonical example of higher-order effects.This exposes an ambiguity between higher-order functions and hypergraph parameterizations.
- Ecological population dynamics: The relevant biological comparison is between bivariate and trivariate functions, not between graph-based and hypergraph-based models.The cited studies do not necessarily endorse the pairwise-versus-higher-order dichotomy.
- Ecological population dynamics: Multivariate interactions are empirically relevant, but multivariate dependence does not by itself imply a need for hypergraph parameterization.The critique targets the representational inference, not the existence of multivariate effects.
- Equivalent representations: A broad class of order-resolved hypergraph dynamics can be reformulated with weighted graphs for linear cases or multilayer networks for nonlinear cases.These alternatives can reproduce the same node-level evolution, including settings used in synchronization and stability analyses.
- Equivalent representations: Hypergraph diffusion is exactly equivalent to diffusion on a weighted graph, while order-resolved layers can preserve interaction-cardinality contributions.The equivalence follows by matching the induced generator and decomposing weights by hyperedge size.
2. Nonlinear dynamics
The nonlinear construction lifts node-space dynamics into order-indexed layers and projects it back, preserving the original evolution while permitting infinitely many microscopic multiplex realizations.
- Order-resolved variational dynamics: The variational dynamics decomposes interaction orders into node-space operators multiplied by Jacobian factors evaluated on the synchronous manifold.Each operator corresponds to interactions of a specified order, with D denoting the maximum interaction order.
- Layered construction: The lifted representation introduces D copies of the node-space perturbation, one per interaction order, and projects their layer average back to δx.The projection treats the layers as a decomposition of one node-level perturbation rather than independent systems.
- Layered construction: Each layer contains one order-resolved coupling channel, while interlayer maps satisfy a zero-average constraint.The constraint allows internal channel exchanges without changing the projected mean.
- Exact recovery: Projecting the lifted synchronization dynamics yields δ ˙x = Aδx, exactly recovering the original node-space variational equation.The interlayer contribution vanishes under the gauge condition.
- Exact recovery: Because infinitely many admissible interlayer maps satisfy the constraint, the same node-level evolution has infinitely many multiplex realizations.Thus the projected equation does not identify a unique microscopic interpretation as higher-order or layered structure.
- Generalization: The same projection construction extends to a broad class of order-decomposable nonlinear hypergraph dynamics.Under a pointwise zero-average condition, projection recovers the original node-space equation while retaining infinitely many multiplex realizations.
VI. LACK OF EMPIRICAL GROUNDING
The paper argues that hypergraph usage lacks broad empirical grounding, while representation choice remains context dependent and hypergraph theory has fewer mature analytical tools.
- Representation choice: Network and hypergraph representations are conceptual abstractions, so choosing between them requires balancing versatility, interpretability, parsimony, and empirical support.A single real-world system may admit multiple mathematical representations.
- Representation choice: Graph-based formulations generally offer greater structural generality and a more mature analytical toolkit than hypergraph parameterizations.The paper contrasts classical graph ensembles, generating functions, and spectral methods with less-developed hypergraph counterparts.
- Representation choice: Hypergraphs may be more parsimonious for systems with overlapping groups engaged in symmetrical, reciprocal interactions, making the choice inherently empirical and context dependent.The paper does not treat greater tractability as decisive in every application.
- Evidence claims: The paper identifies toy models, bipartite-data reinterpretations, graph-to-hypergraph imputation, and time-series heuristics as common but inadequate forms of evidence for hypergraph ubiquity.These categories motivate the paper's examination of purported empirical support.
- Evidence claims: The critique concerns evidence for hypergraph formulations, not the substantial empirical evidence that multivariate interactions occur.The paper explicitly separates multivariate interactions from their proposed connection to hypergraph structures.
A. Toy models are not evidence
The paper argues that toy models and reconstruction procedures do not establish hypergraph necessity: equivalent graph descriptions, non-identifiability, and weak model comparison limit the empirical case.
- Toy models: Reproducing a macroscopic phenomenon with a hypergraph model does not establish that hypergraph structure is necessary or relevant to the underlying system.Multiple non-equivalent microscopic descriptions can produce the same observed behavior.
- Toy models: Hypergraph toy models show possible modeling choices, but not that hypergraphs are empirically warranted, uniquely informative, or required.The paper therefore rejects claims of hypergraph ubiquity based solely on the number of such models.
- Bipartite data: Recasting bipartite data as hypergraphs can amount to relabeling because the two representations are mathematically equivalent and preserve corresponding distributions.For example, degree distributions can be replaced by hyperedge-order distributions without changing the mathematical description.
- Bipartite data: Hypergraph algorithms for bipartite data often lack statistical evidence or systematic comparisons with graph and bipartite alternatives.The paper notes that explicit generative approaches remain limited in comparative evaluation.
- Bipartite data: No substantial empirical evidence currently shows that hypergraph-based models describe bipartite data better than alternatives that do not invoke hypergraphs.This is the paper's stated assessment of the available comparative evidence.
- Graph-to-hypergraph inference: Clique-based extraction is non-identifiable and cannot establish irreducible higher-order structure beyond what the projected graph already encodes.Different hypergraph configurations can generate the same graph, while maximal-clique hyperedges are reducible to edge superpositions.
- Time-series inference: Time-series reconstruction is limited by noisy, incomplete data, indirect correlations, model assumptions, and the absence of principled complexity-aware model comparison.The paper concludes that existing methods do not establish hypergraph support in empirical systems.
- Overall conclusion: The absence of hypergraph-only representability makes attempts to identify systems requiring hypergraphs likely futile, because graph representations can also represent them.The paper contrasts this with cases where graph representations may not be as restrictive as hypergraph ones.
VII. EXPRESSIVENESS, PARSIMONY, AND MODEL SELECTION
Graph-based models are more expressive than hypergraph formulations, which impose additional structural and functional constraints. Model selection should therefore compare representations using principled complexity and data-fit criteria rather than assuming hypergraphs are more general.
- Expressiveness: Hypergraph-based models are strict special cases of graph-based models, so many graph dynamics cannot be represented by any hypergraph.The mapping from graph-based functions to hypergraph-based functions is non-invertible.
- Parsimony: Graph-based descriptions can be at least as parsimonious as hypergraph descriptions, while hypergraphs may be more compressive only when their structural and functional constraints are admissible.Hypergraph parsimony is advantageous only in particular cases, such as symmetric mutual interactions.
- Model selection: Bayesian model selection or minimum description length compares data encoding and model encoding, making model complexity necessary for assessing plausibility.The most plausible model is the one that achieves the greatest compression of the data.
- Expressiveness: Some graph-based functions are not representable by hypergraphs, whereas admissible hypergraph functions can be translated into graph-based descriptions.The number of graph-based functions is strictly larger, and some hypergraph descriptions can nevertheless provide compact encodings when admissible.
- Parsimony: Hypergraph parameterizations can overfit when hyperedges overlap sufficiently, even when the hypergraph representation is admissible.In such cases, redundant hypergraph parameters can make the graph-based description more compressive.
- Model selection: Finite data can support multiple competitive explanations, so practical model selection may be nuanced and computationally demanding.The competing representations and interaction functions need not be mutually compatible, further complicating comparison.
VIII. REDUCIBILITY OF MULTIVARIATE INTERACTIONS
Multivariate interactions should not be classified as irreducible merely because they involve many arguments. Although mathematical decompositions into univariate terms exist, the resulting functions may remain highly complex and discontinuous.
- Reducibility: Function arity is only a limited proxy for complexity, because every multivariate function can be expressed as a sum of univariate terms.This mathematical reducibility does not by itself make the resulting representation simple or useful.
- Reducibility: A bijective reparameterization can represent a multivariate function through a univariate function, yielding pairwise contributions in a graph model.The bijection is not unique, and multiple univariate representations can provide the same generality.
- Limitations: Univariate representations may be widely discontinuous and arbitrarily complex despite having only one dimension.Alternative continuous representations retain generality but remain complex in the general case.
- Interpretation: The paper concludes that multivariate-function irreducibility should not be assumed.The practical usefulness of a representation depends on the complexity and regularity of its functions, not arity alone.
- Interpretation: The existence of a decomposition cannot by itself determine whether an interaction is low-order, high-order, reducible, or irreducible.Such decompositions may nevertheless be simple and useful in special cases.
- Applications: Univariate representations can support statistical inference because only the individual univariate functions need parameterization.This approach has already been used in machine learning and may aid network reconstruction when interaction shapes are unknown.
- Complexity: Useful functions are generally compressible because incompressible functions with many arguments require infeasibly large descriptions.The paper illustrates this with rapidly growing storage requirements for discrete functions of increasing arity.
IX. CONCLUSION
The paper concludes that graph models can represent multivariate interactions and are more general than hypergraph parameterizations. Phenomena attributed uniquely to hypergraphs can also arise in locally tree-like graphs, while empirical support for broad hypergraph generality remains limited.
- Conclusion: Graph parameterizations specify interaction neighborhoods while leaving interaction functions unconstrained, allowing coordination among multiple neighbors.Such interactions cannot reasonably be classified as merely pairwise.
- Conclusion: Hypergraph parameterizations impose additional constraints and therefore constitute strict special cases rather than extensions of graph-based models.The paper reverses the usual hierarchy: graph formulations are generically more general.
- Implications: The distinction between multivariate interactions and hypergraph representations matters for network reconstruction from time-series and other indirect data.The paper argues that relaxing constraints on latent node functions is sufficient for a maximally general approach.
- Phenomenology: Hypergraph-attributed phenomena can be reproduced by locally tree-like graph models lacking cliques, including abrupt transitions in cooperative dynamics.The paper argues that some analyses effectively disregard the hypergraph structure itself.
- Scope: Conflating multivariate interactions with hypergraphs can bias theories and methods built on the assumption that the concepts are inseparable.The paper presents this as a consequence of the mistaken belief that hypergraphs expand the space of interactions.
- Scope: Claims that hypergraphs are necessary or generically useful are not supported by the paper’s assessment of available empirical evidence.The authors also acknowledge useful, interpretable, or parsimonious hypergraph representations for specific systems.
Appendix A: Equilibrium models, Hamiltonians, and factor graphs
Equilibrium models can be formulated using Hamiltonians and factor graphs, with hypergraph formulations appearing as special cases of more general graph-based constructions. The appendix shows that the reverse conversion is not generally available.
- Hamiltonians: A Hamiltonian defines the joint distribution of system variables up to normalization.The appendix introduces this as the equilibrium-model starting point.
- Factor graphs: Factor graphs represent functions over subsets of variables and are mathematically equivalent to hypergraphs.This formulation supports message-passing algorithms that are exact on trees and accurate asymptotically on locally tree-like graphs.
- Expressiveness: Every factor-graph formulation can be represented by a more general graph-based formulation, but the reverse decomposition is not generally possible.The appendix explicitly identifies the graph-based formulation as maximally general for a given adjacency structure.
- Expressiveness: The graph-based formulation relies solely on adjacency structure, and merging factors incident on a node increases its effective adjacency.This is why the representation is described as maximally general for a fixed adjacency pattern.
- Multilayer formulation: A multilayer-network representation can recover the hypergraph formulation, but the converse does not hold in general.The appendix states that the multilayer formulation recovers the hypergraph equation but not vice versa.