Network reconstruction is the task of inferring the unseen interactions between elements of a system, based only on their behavior or dynamics. This inverse problem is in general ill-posed, and admits many solutions for the same observation. Nevertheless, the vast majority of statistical methods proposed for this task -- formulated as the inference of a graphical generative model -- can only produce a ``point estimate,'' i.e. a single network considered the most likely. In general, this can give only a limited characterization of the reconstruction, since uncertainties and competing answers cannot be conveyed, even if their probabilities are comparable, while being structurally different. In this work we present an efficient MCMC algorithm for sampling from posterior distributions of reconstructed networks, which is able to reveal the full population of answers for a given reconstruction problem, weighted according to their plausibilities. Our algorithm is general, since it does not rely on specific properties of particular generative models, and is specially suited for the inference of large and sparse networks, since in this case an iteration can be performed in time $O(N\log^2 N)$ for a network of $N$ nodes, instead of $O(N^2)$, as would be the case for a more naive approach. We demonstrate the suitability of our method in providing uncertainties and consensus of solutions (which provably increases the reconstruction accuracy) in a variety of synthetic and empirical cases.
Braneshop, and
the US National Science Foundation.
This manuscript by Lacasa contains a response to our current [preprint](https://arxiv.org/abs/2602.16937) that points out a fundamental conflation in the current literature of "higher-order networks" (HONs) between multivariate interactions and hypergraph parameterizations. We demonstrate that these concepts are separable, and that graph-based modes have been used to model multivariate interactions for decades. We also show that many of the phenomenology claimed to be unique to hypergraph parameterizations are exactly reproduced with tree-like graphs.
Our main argument is a refutation of the following claims that are made prominently and repeatedly in the HON literature:
1. Graphs encode only “pairwise interactions.”
1. Hypergraphs encode “group interactions,” indivisible interaction units with more than two elements that cannot be represented by graphs.
1. Many systems are better modeled with “group interactions,” and hence hypergraphs.
1. “Group interactions” give rise to new phenomenology not explainable by graph-based models.
We refute each of the above points in detail in our manuscript.
In Lacasa's manuscript, many points of agreement with our manuscipt are highlighted, in particular that our refutation of point 1 above is fundamentally correct.
However, none of the other points we raise are addressed. Instead, the author changes the subject, and seeks to demonstrate that particular cases of nonlinear, continuous dynamical systems can be expressed as linear systems (allegedly) on hypergraphs. This bears no direct relevance to our main points.
Nevertheless the author's arguments contain a certain number of inconsistencies and superficial, although invalid, criticisms of our work, which, in the interest of bringing clarity to this topic, I elucidate below.
1. When discussing our work, the author states: "Note that similar reservations had been raised before for particular cases [4, 5]."
This isn't actually true. The works cited show that particular kinds of multivariate interactions can be written as pairwise interactions on modified networks. These works do not address at all the conflation we point out between hypergraphs and multivariate interactions; on the contrary they accept the idea that for true multivariate interactions one needs hypergraphs. They just point out that sometimes these interactions can be decomposed into pairwise ones.
2. After equation 1 the author states: "As a first disclaimer, note that while this is simply a nonlinear system of coupled ordinary differential equations, observe that calling this a graph-based dynamics is already a modelling choice, fueled by the convenient notational choice of using $\partial i$ . In other words, ontologically there is no graph, but we choose to write the system in a convenient way that implicitly allows for such an interpretation."
This is incorrect and misleading. Once you separate which variables matter (i.e. have a non-zero partial derivative) from those that do, the graph manifests itself. It is there whether one wants it or not. It is *not* a modelling choice, nor mere notation, nor an ontological matter.
This is an evasive argument that omits the fact that our observation is a response to the claim that "graphs only encode pairwise iteractions". We demonstrate that this is not true. Even if were true (although it isn't) that this was a modelling choice, it would already be sufficient to rebuke the original claim.
(It is interesting that once one shows that graphs can and have been used to model multivariate interactions, arguments based on subjectivity crop up. Yet, no subjectivity was present when authors were adamantly claiming that graphs are "inherently limited" to pairwise interactions, despite obvious evidence to the contrary, such as models of bootstrap percolation, boolean networks, ecological models of apparent competition, etc)
3. The author insists that a model such as
$$\dot x_i = g(x_i) + \sum_jA_{ij}g(x_i, x_j)$$
shows "a more evident presence of a graph" than the more general formulation we consider. First, unlike point 2 above, this is in fact nothing more that a purely subjective claim, since it is not based on any formal argumentation at all. Furthermore, it goes against a very large number of network models have been developed over many decades, including, as already mentioned, boolean networks, neuronal dynamics, bootstrap percolation, etc. None of these kinds of models fit the pattern above, nor are they hypergraphs, and I find it both a revisionist and incoherent stance to imply that they are not evidently network models — especially considering that the alternative in this context are hypergraphs.
4. "Eq. 1 can also be encoded within a hypergraph notation"
This is not true. Hypergraph formulations require cliques to exist. This is a form of bias that graphs do not incorporate. As we show, multivariate interactions are separable from the fact that triads and larger groups of nodes all influence each other directly, and mutually. This important point seems to have been overlooked throughout the manuscript.
7. The points made about high dimensional lifting seem only valid for ODEs, while we make a much more general point valid in any setting, with dynamics based on discrete values and/or discrete time, probabilistic systems, static coupled equations, etc.
8. The lifted representations analysed are claimed to be defined on hypergraphs, but this manifestly not the case. As it's clear from Eqs 4 and 6 what are being described are linear graph models, parameterized via an adjacency matrix, where the lifted nodes are products of variable nodes. A hypergraph requires hyperedges, usually parameterized via a tensor, which is completely absent from these models. In fact, these arguments seem to show that some classes of nonlinear graphs models can be written as linear graphs models with an expanded node set. Hypergraphs do not come into the picture at all. The idiosyncratic hypergraph interpretation that follows in the text is unnecessary, and can be completely omitted without any loss.
8. The claim that a representation in an augmented space, possibly with infinite degrees of freedom, can be more parsimonious than a lower dimensional one is made without any elaboration. The author does not attempt to formalize the notion of parsimony, and treats it as something subjective. But in order for this concept to be scientifically meaningful, it needs to be formalized. This can be done, for example, according to the minimum description length (MDL) principle, or equivalently, via Bayesian model selection. I would be surprised if the author could show that this claim would hold under such criteria.
As discussed in the beginning, the above points are at most tangential to the ones we made in our manuscript. But since the field of HONs seems to thrive in confusion and obfuscation, I felt the above clarifications were necessary.
For a non-technical FAQ regarding our work please also see [here](https://manliodedomenico.com/structure_is_not_mechanism.php#FAQ).