Feedback through graph motifs relates structure and function in complex networks

In physics, biology, and engineering, network systems abound. How does the connectivity of a network system combine with the behavior of its individual components to determine its collective function? We approach this question for networks with linear time-invariant dynamics by relating internal network feedbacks to the statistical prevalence of connectivity motifs, a set of surprisingly simple and local statistics of connectivity. This results in a reduced order model of the network input-output dynamics in terms of motif structures. As an example, the formulation dramatically simplifies the classic Erdős-Rényi graph, reducing the overall network behavior to one proportional feedback wrapped around the dynamics of a single node. For general networks, higher-order motifs systematically provide further layers and types of feedback to regulate the network response. Thus, the local connectivity shapes temporal and spectral processing by the network as a whole, and we show how this enables robust, yet tunable, functionality such as extending the time constant with which networks remember past signals. The theory also extends to networks composed from heterogeneous nodes with distinct dynamics and connectivity, and patterned input to (and readout from) subsets of nodes. These statistical descriptions provide a powerful theoretical framework to understand the functionality of real-world network systems, as we illustrate with examples including the mouse brain connectome.

Figure 1

A input signal $u\left(t\right)$ is sent to the network according to weights $B_i$, and a readout is formed by summing node activities with weights $C_j$.

Figure 2

(a) Examples of connectivity motifs; as we will show (for the basic case of Theorem t1), the network transfer function $G\left(s\right)$ is determined by the prevalence of chain motifs, given by the motif cumulants ${\kappa }_n$. (b) By decomposing motifs into smaller ones (shaded submotifs), the motif cumulants (${\kappa }_3$ in this example) isolate the “pure” higher-order connectivity structure from raw motif counts (${\mu }_3$ here).

Figure 3

The network transfer function for uniform degree networks and Erdős-Rényi networks are equivalent to proportional feedback around a single node.

Figure 4

(a) Complex networks may be organized by their motif cumulants ${\kappa }_j$; the first two cumulants are shown. We show two example networks with different motifs. Bar graphs show values of ${\kappa }_1$ through ${\kappa }_4$ (relative magnitude to powers of the connection probability, see details in Appendix pp6), for each network. (b) The motif content determines the strength of each pathway in the feedback hierarchy shown; this relationship is indicated by the green “slider” arrows.

Figure 5

Network transfer functions $G\left(s\right)$ for different networks, indicated by matching color/shade and numbering as the dots in Fig. 4 (see legends on top of each column); in the first column, networks have differing values of ${\kappa }_1$; in the second, differing values of ${\kappa }_2$. Here, the node filter is $h_{exp}$. Dashed lines are approximations by keeping leading terms (1 term in the left column and 3 terms for the right, see text); some are indistinguishable from the solid corresponding to actual filters with all terms.

Figure 6

Same as Fig. 5 except that the node filter is $h_{cos}$.

Figure 7

Comparison of numerical ($x$ axis) and analytical predictions ($y$ axis) of time constants in 100 SONETs (each network sample is a dot). The motif based prediction is from truncating after second order (a)) or third order ((b)) motif cumulants, using Theorem t4. The axes are in ${log}_{10}$ scale, and the values are normalized by the time constant of a single node (which corresponds to 0). All the networks have the same connection strength and approximately the same number of connections (connection probability 0.1) by construction, but have various extents of second order motif cumulants. For comparison, the time constant for an Erdős-Rényi network is labeled by a red plus sign.

Figure 8

Bode diagram showing convergence of network transfer functions in large networks; blue thin lines are 100 individual networks. The red thick lines in the middle correspond to uniform input and output weights. The shaded area shows the 90% confidence interval [Eq. (16)].

Figure 9

Schematic of the distribution of $G\left(s\right)$ around $\mathbf{E}\left[G\left(s\right)\right]$ for a fixed $s$ and the related decomposition into independent components.

Figure 10

Feedback diagram for a network with correlated input and output weight vectors $B,C$ (see text). Both chain and cycle motif cumulant give rise to a feedback link in the flow diagram. The circled numbers are additional constant weights for some feedback links.

Figure 11

Numerical examples showing the impact of ${\kappa }_2^c$ on $\mathbf{E}\left[G\left(s\right)\right]$ for correlated input and output weights $B,C$, for the node filter $h_{exp}\left(s\right)$ (left column) and decaying-oscillatory filter $h_{cos}\left(s\right)$ (right column) calculated using Eq. (17). Lines of blue-to-yellow colors (darker to lighter shades) correspond to ${\kappa }_2^c/0.09$ taking values from $-0.85$ to 0.9. The entries of $B$ and $C$ have mean 0 and $\rho {\sigma }^2=1/N$ (see text). The networks $W$ are generated as Gaussian random matrices with entries of variance 0.09 and size $N=400$ (Appendix pp9-s3). We scale the coupling strength of each $W$ to 40% of the critical maximum value.

Figure 12

Schematic for a network with multiple node types or population-wise patterned inputs and readouts; here, indicated by blue and pink node (dark and light shades).

Figure 13

Feedback diagram that gives the network transfer function matrix $G\left(s\right)$ for networks with two populations (different colors/shades). Various green triangles are feedbacks corresponding to population specific motif cumulants.

Figure 14

Feedback diagram for the expression of $G\left(s\right)$ using degree-corrected motif cumulants ${\kappa }_n^{\mathrm{deg}}$.

Figure 15

Stronger effect of the length-2 chain motif cumulant ${\kappa }_2$ on shaping the network transfer function $G\left(s\right)$, for networks with node filter $h_{exp}\left(s\right)$. The networks $W$'s are generated from the SONET random graph model (Appendix pp9-s2). Network size is $N=1000$, connection probability ${\kappa }_1=0.1$, and ${\kappa }_2/{\kappa }_1^2=-0.6,0,0.1$, respectively, for the three columns from left to right. Higher-order motif cumulants ${\kappa }_{n\ge 3}$ are small (see Appendix pp10). To emphasize the effect of ${\kappa }_2$, a global (negative) feedback is applied to all three networks to shift ${\kappa }_1$ to 0 without changing higher-order motif cumulants. The blue solid lines are calculated by directly solving the system (3) using entire connectivity matrix $W$. The red dashed lines are calculated using only the first two degree-corrected motif cumulants ${\kappa }_1^{\mathrm{deg}}$ and ${\kappa }_2^{\mathrm{deg}}$ (see Sec. 8), along with a formula analogous to Theorem t1. The same connection strength constant multiplies $W$ for the three networks. The value of this constant is set to be 90% of the maximum value under which all three networks are stable. The parameters used are detailed in Appendix pp10-s1.

Figure 16

Same as Fig. 15, but for networks with node filter being $h_{cos}\left(s\right)$.

Figure 17

Mesoscale mouse brain network dynamics. (a) Mouse brain mesoscale connectivity organized according to anatomical groups (Crbl: cerebellum, HyTh: hypothalamus, nuc.: nuclei); red dotted connections originate from 11 sensory thalamic nuclei; remaining connections are shaded proportional to connection strength, from [41]. (b) The network-wide motif cumulants magnitude (Appendix pp6) of the original network do not decay rapidly with order (size), resulting in a long timescale of the network transfer function (inset) for a global input and readout. (c) The impulse response function (red solid line, main and inset) exhibits multiple timescales. The input signal is sent uniformly to sensory thalamic nuclei and read out from all regions. Black dashed lines depict successive (improving) approximations to this response computed by considering additional motif cumulants up to order 3. Inset: When the network is modified by either performing a node-degree preserving shuffle (thin blue lines), or by setting every connection to a strength equal to the mean of the original log-normal weight distribution (red dashed line), the long-time memory capacity of the network is diminished. (d) Comparing timescales of the whole-brain responses to cortical signaling from higher level cortical areas (magenta, upper curve) and to input from sensory thalamus [green, lower curve, same as in (c)]. Inset is plotting in log-$y$ scale. (e) Estimations of time constant for the thalamic input response (c) by successively including higher-order motif cumulants. (f) Same as (e) except input is sent through higher level cortical areas.

Figure 18

Application to the C. elegans neuronal network and a power grid network. (a) The C. elegans network [5] shows long-timescale response (red solid line) that is much shortened when higher-order motif cumulants are removed (blue dashed line). (b) Similar as Figs. 17 (e) and 17; how motifs of various orders contribute to the extension of the time constant seen in (a). For the power grid network of western states in the U. S. (c)–(e) [5], when the stimulus is sent to all the nodes, the motifs has only small effects on the impulse response (c). In contrast, when input to only the hub nodes (4.2% of nodes with the highest degrees), the impulse response has a larger time constant and the effect of higher-order motifs become larger (d), (e). The original network with 4941 nodes is undirected. In the simulation, edges are made bidirectionals.

Figure 19

Comparison of degree-preserving shuffle and the theory of truncating motifs. Same as Fig. 17 but for the case of sending input to cortical areas.

Figure 20

Degree-distribution-preserving shuffling of network connectivity. The shuffling produces a random network by transforming the connectivity matrix for a network via a random row permutation followed by a random column permutation. The order of shuffling rows first and then columns (as depicted here) is arbitrary, and can be reversed.