Fundamental limitations of network reconstruction from temporal data

Abstract

Inferring properties of the interaction matrix that characterizes how nodes in a networked system directly interact with each other is a well-known network reconstruction problem. Despite a decade of extensive studies, network reconstruction remains an outstanding challenge. The fundamental limitations governing which properties of the interaction matrix (e.g. adjacency pattern, sign pattern or degree sequence) can be inferred from given temporal data of individual nodes remain unknown. Here, we rigorously derive the necessary conditions to reconstruct any property of the interaction matrix. Counterintuitively, we find that reconstructing any property of the interaction matrix is generically as difficult as reconstructing the interaction matrix itself, requiring equally informative temporal data. Revealing these fundamental limitations sheds light on the design of better network reconstruction algorithms that offer practical improvements over existing methods.

Keywords: network reconstruction; networked systems; system identification.

Figure 1.

Two sources of indistinguishability. (a) The same dynamics can be characterized by two regressors with different coupling functions (purple and green), yielding indistinguishable networks that differ in their edge weights, sign patterns, connectivity patterns and degree sequences. (b) With the classical population dynamics described by the generalized Lotka–Volterra (GLV) model , the two different networks shown in the top panel produce identical node trajectories x(t) (bottom panel). Here, the growth rate vector is and initial abundance . (Online version in colour.)

Figure 2.

Indistinguishability of interconnection vectors. (a) Indistinguishable vectors due to unknown coupling functions can be transformed into each other using some transformation . Sets of those indistinguishable vectors are the partition of by the orbits of , here shown in different colours for and . Purple regions should be interpreted as points, and blue regions as lines. The grey region is another orbit. We can distinguish an interconnection vector in the blue orbit (e.g. v₂ with component ) from an interconnection vector in the orange orbit (e.g. v₁ or v₃ with component ), illustrating that we can distinguish the adjacency of the interconnection vector (i.e. whether a_ij is zero or not for ). Nevertheless, as v₁ and v₃ belong to the same orbit and hence are indistinguishable, but they have different degree sequences and sign or connectivity patterns, these properties cannot be reconstructed. (b) Owing to uninformative measured temporal data, the interconnection vector v₁ is indistinguishable from v₂ because , i.e. both vectors are joined by the red fibre. We can also separate the sets P_y1 and P_y2 with the particular orientation of the fibres. However, as there is no gap between these sets, any change in the orientation of the fibres will produce indistinguishable interconnection vectors that belong to different sets. This illustrates that the PE condition remains generically necessary if there is no gap between the sets in . Indistinguishable vectors in network reconstruction appear by combining both kinds of indistinguishable vectors, gluing together orbits of when they are intersected by a fibre of . In the left panel, as is not contained in low-dimensional orbits, all orbits are are glued and all vectors become indistinguishable (e.g. v₁ is indistinguishable from v₃). In the right panel, is contained in low-dimensional orbits. We can then distinguish between v₂ and v₃ and hence reconstruct the adjacency pattern of the interaction matrix. (Online version in colour.)