Beyond expressiveness in pairwise and higher-order models
Abstract
The debate over pairwise and higher-order models is often framed as a contest of expressive power. This framing is misleading. A graph with arbitrary multivariate node functions can reproduce the node-level dynamics of many hypergraph models, but the hypergraph's grouping information does not thereby disappear: it may simply move from the structure to the rule. We separate four notions frequently conflated here: structural representation, functional representability, statistical identifiability, and mechanistic adequacy. We then prove that interaction order, the number of variables that must act jointly in some term of any additive decomposition of a node's update, is the same in every exact representation: no change of structural language can lower it. As a description-length problem, at the unrestricted algorithmic level a fixed compiler redistributes information between structure and rule at constant overhead, so expressiveness alone cannot privilege either language. Preferences arise only relative to explicit model classes, code families, and data. This yields an operational minimum-description-length criterion combining structural cost, conditional rule cost, and imperfect fit. Within it, for M disjoint groups of size k, the clique projection's edge list is asymptotically k−1 times longer than the hyperedge list it replaces: the projection encodes the same grouping at higher cost. Examples from diffusion, Boolean dynamics, ecology, and ambiguous projections give graph-preferred, hypergraph-preferred, and unresolved cases; for bipartite and multilayer lifts, cost, fit, and identifiability tie, and the choice turns on which entities are posited as primitive. The position is symmetric: higher-order structure should not be inferred from phenomenology alone, nor does a graph's ability to emulate a system make it the most parsimonious or adequate description.
Related
- Higher-order adaptive behaviors outperform pairwise strategies in mitigating contagion dynamics
- Beyond city pairs: Higher-order information in urban growth across borders
- Beyond the Binary Hull: Higher-Order Thermodynamic Stabilization in Inorganic Ternary Compounds
- Exact AdS and pp-waves in multi-gravity beyond pairwise interactions
- Quantum Representation Learning Beyond Pairwise Fidelity
BibTeX
@misc{rommens2026beyond,
title = {{Beyond expressiveness in pairwise and higher-order models}},
author = {Cyril Rommens and Pietro Traversa and Guilherme Ferraz de Arruda and Yamir Moreno},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.26031},
eprint = {2609.26031},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.26031},
}
RIS
TY - UNPB
TI - Beyond expressiveness in pairwise and higher-order models
AU - Cyril Rommens
AU - Pietro Traversa
AU - Guilherme Ferraz de Arruda
AU - Yamir Moreno
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2609.26031
UR - https://arxiv.org/abs/2609.26031
AB - The debate over pairwise and higher-order models is often framed as a contest of expressive power. This framing is misleading. A graph with arbitrary multivariate node functions can reproduce the node-level dynamics of many hypergraph models, but the hypergraph's grouping information does not thereby disappear: it may simply move from the structure to the rule. We separate four notions frequently conflated here: structural representation, functional representability, statistical identifiability, and mechanistic adequacy. We then prove that interaction order, the number of variables that must act jointly in some term of any additive decomposition of a node's update, is the same in every exact representation: no change of structural language can lower it. As a description-length problem, at the unrestricted algorithmic level a fixed compiler redistributes information between structure and rule at constant overhead, so expressiveness alone cannot privilege either language. Preferences arise only relative to explicit model classes, code families, and data. This yields an operational minimum-description-length criterion combining structural cost, conditional rule cost, and imperfect fit. Within it, for M disjoint groups of size k, the clique projection's edge list is asymptotically k−1 times longer than the hyperedge list it replaces: the projection encodes the same grouping at higher cost. Examples from diffusion, Boolean dynamics, ecology, and ambiguous projections give graph-preferred, hypergraph-preferred, and unresolved cases; for bipartite and multilayer lifts, cost, fit, and identifiability tie, and the choice turns on which entities are posited as primitive. The position is symmetric: higher-order structure should not be inferred from phenomenology alone, nor does a graph's ability to emulate a system make it the most parsimonious or adequate description.
ER -