Does Form Imply Function?

Data-processing Inequality

The data-processing inequality can be used to show that no clever manipulation of the data can improve the inferences made from that data (see for more detail [61]).

Definition

Random variables $X\rightarrow Y \rightarrow Z$ are said to form a Markov chain if the conditional distribution of $Z$ depends only on $Y$ and is conditionally independent of $X$. Specifically, $X,Y,Z$ form a Markov chain if the joint probability can be written as:

$$\begin{equation} \begin{split} p(x, y, z) = p(x) p(y \vert x) p(z \vert y) \end{split} \end{equation}$$

Theorem

(Data-processing inequality) If $X \rightarrow Y \rightarrow Z$, then $I(X; Y) \geq I(X; Z)$.

Proof: By the chain rule, the mutual information can be expanded in two different ways:

$$\begin{equation} \begin{split} I(X; Y; Z) &= I(X ; Z) + I(X; Y \vert Z)\\ &= I(X; Y) + I(X; Z \vert Y) \end{split} \end{equation}$$(B.2)

Since $X$ and $Z$ are conditionally independent given $Y$, we have $I(X; Z \vert Y) = 0$. Conversely, if $I(X; Y \vert Z) \geq 0$, this would give

$$\begin{equation} \begin{split} I(X; Y) \geq I(X; Z). \end{split} \end{equation}$$ Thus we only have equality if and only if $I(X; Y \vert Z) = 0$ for Markov chains. Similarly, one can prove that $I(Y; Z) \geq I(X; Z) \blacksquare$.

Corollary

If $Z = g(Y) \rightarrow I(X; Y) \geq I(X; g(Y))$

Proof: $X \rightarrow Y \rightarrow g(Y)$ forms a Markov chain $\blacksquare$.

This result implies that no function $g(Y)$ can increase the information about $X$.

Corollary

If $X \rightarrow Y \rightarrow Z$, then $I(X; Y \vert Z) \leq I(X; Y)$

From eq. (B.2) it is noted that $I(X; Z \vert Y) = 0$ due to the definition the Markov chain and $I(X; Z) \geq 0$. Therefore:

$$\begin{equation} \begin{split} I(X; Y \vert Z) \leq I(X; Y) \blacksquare \end{split} \end{equation}$$

The dependence of $X$ and $Y$ is decreased or remains unchanged by the observation of a “downstream” random variable $Z$. For any complex system in which the state distribution follows a Markov chain, i.e. $X^{t_0} \to X^{t_0+1} \to \dots \to X^{t_0+\infty}$. The mutual information $I(X^{t_0}; X^{t_0 + t})$ will always decay to zero as $t \to \infty$.

A Note on Causality and Mutual Information

Mutual Information and Causal Bivariate Interaction

Mutual information decays to causal interactions for simple bivariate interactions. For Markovian systems, the future state of the system is independent of its past given its present (eq. (2.2)). Therefore, we can write ([61])

$$\begin{equation} \begin{split} p(s_j^{t+1} | S^t) = p(s_j^{t+1} | s_i^t). \end{split} \end{equation}$$(B.5)

For any two nodes $s_i, s_j \in S$, the KL-divergence $D_{KL}(p(s_j^{t+1} | s_i^t) || p(s_j^t))$ reduces to $I(s_i^{t+1} ; s_j^t)$.

Theorem

$E_{s_i} [D_{KL}(p(s_j^{t + 1} | s_i^t) || p(s_j^t)] = I (s_i^{t + 1} ; s_j^t)$ when $s_i$ and $s_j$ have no common neighbors.

Proof:

$$\begin{equation} \begin{aligned} & E_{s_i^t}[D_{KL}(p(s_j^{t+1} | s_i^t) || p(s_j^t))] \\ &= E_{s_i^t} \left[ E_{s_j^{t+1} \mid s_i^t} \left[ \log \frac{ p(s_j^{t+1} \mid s_i^t)} { p(s_j^{t+1}) } \right]\right] \\ &= \sum_{s_i^t} p(s_i^t) \sum_{s_j^{t+1}} p(s_j^{t+1} \mid s_i^t) \log \frac{p(s_j^{t+1} \mid s_i^t)} { p(s_j^{t+1}) } \\ &= \sum_{s_i^t} p(s_i^t) \sum_{s_j} \log p(s_j^{t+1} \mid s_i^{t}) \log p(s_j^{t+1} \mid s_i^t) - \sum_{s_j^{t+1}} p(s_j^{t+1}) \log p(s_j^{t+1}) \\ &= H(s_j^{t+1}) - H(s_j^{t+1} \mid s_i^t) \\ &= I(s_j^{t+1} : s_i^t) \quad \blacksquare. \end{aligned} \end{equation}$$(B.6)

Mutual Information and Time Symmetry

The methods applied in the main text imply that the metric can be used symetrically. In this study time-delayed mutual information was performed in a ‘forward’ manner for pratical purposes. Namely, the system state was simulated for positive $t$ from some $t_0$. For undirected networks there is a symmetry with regard to where information flows. Information is not bounded by any directionality of edges (fig. B.II.1b).

It is important to emphasize that this (generally) is not the case for directed networks. For kinetic Ising models detailed balance is not guaranteed and as such mutual information may be conflated for integrated nodes (see B.II). If information is constricted to flow in one direction, the mutual direction of time simulation is crucial. Additionally, directed networks show that the metric can be applied for different purposed. This can be seen in fig. B.II.1a, where forward simulations gives ‘information sinks’ and backward simulation provides ‘information sources’. IMI in directed networks will provide information about what nodes receive the most information over time, i.e. the correlation of a node with “sending” information. In contrast, simulating backwards shows what nodes have most impact on the instantaneous state of the system. This dual-use of information will be the focus of future studies.

 

Integrated Mutual Information and Integrator nodes

As noted in B.II the driver node can only be determined for ergodic systems with symmetric edges, that is the interaction $J_{s_i,s_j} = J_{s_j,s_i} \forall s_i,s_j \in S$. For directed graphs (i.e. non-symmetric edge weights) integrated mutual information may be conflated and produce a wrong estimate for the driver node. These cases are, however, outside the scope of the manuscript, and undirected integrators can readily be identified by integrated mutual information.

Consider the system $S(t) = \{ s_1(t), s_2(t), \sigma(t)\}$ where integrator $\sigma(t) = \{\sigma_1(t-1), \sigma_1(t-1)\}$ with $\mathbb{H}(\sigma) = -J_{s_1, \sigma_1} s_1 \sigma_1 - J_{s_2, \sigma_2} \sigma_2 s_2$, and each node is governed by kinetic Ising spin dynamics (see figure B.II.2). The node $\sigma(t)$ is the integrator node that consists of two “sub-nodes” that connects to node $s_1, s_2$ separately. Note that the interaction weight $J$ can be adjusted. The traditional kinetic Ising spin dynamics are obtained for $J_{i,j}=1$ we obtain the traditional kinetic Ising spin dynamics, and as $J_{i,j} \to \infty$ the dynamics tend to a copy operator. In addition, the weights may be set such that a directed graph is obtained (see figure B.II.2 B).

We consider two cases. First the case where $\sigma$ contains no outgoing causal connections, that is $J_{\sigma_1, 1} = J_{\sigma_2, 2} = 0$. In the extreme case where the integrator is a copy operator ($J_{\sigma_1, 1} = J_{\sigma_2, 2} \to \infty$), the integrator $\sigma$ stores information the system, but has itself no causal impact. Integrated mutual information in this setting cannot be used as a driver node identification as the shared mutual information with the system is merely correlational.

For undirected edges, however, e.g. $J_{\sigma_1, 1} = J_{1, \sigma_1} = 1, J_{\sigma_2, 2} = J_{2, \sigma_2} = 1$ (fig B.II.2 A), integrator node will have the highest causal potential as the impact of an intervention on the integrator can percolate through the system. Integrated mutual information correctly identifies the driver node. Note that the size of the connection weights matters. As $J_{\sigma_i, i} = J_{i, \sigma_i} \to \infty$ the interaction the integrator node will tend to a copy operator. For a copy operator the dynamics of the system will degenerate. In this setting, the out-of-equilibrium dynamics will be non-existing as the dynamics of $s_i$ and $s_j$ will be frozen through the edge with the integrator. This will results that out-of-equilibrium, the system state will merely be copied and no transient dynamics will be possible. Information flows will not occur as the relative entropy will be zero. This setting violates detailed balance. Relaxing the interaction $J$, enables detailed balance and we see under these conditions the driver node is correctly identified (fig. B.II.2 A). The integrator node’s causal impact can flow due to the detailed balance.

In conclusion, directed edges violates detailed balance and consequently integrated mutual information will not be able to identify the driver node as the node with the highest mutual information through forward inference, i.e. $I(s_i^{t_0 + t}: S^{t_0}$). Nodes with the highest causal impact are correctly identified through integrated mutual information for kinetic Ising spin dynamics on undirected network structures where detailed balance is ensured.

Time Reversibility and Detailed Balance

In order to show that $I(s_i^{t+1} ; S^t) = I(s_i^{t-1} ; S^t)$, we have to show that $p(S^{t+1}_* | S^{t}_*) = p(S^{t-1}_* | S^{t})$.

Two-sided Markov Chains

For a positive recurring Markov chain $\{S^t : t \in \mathbb{N}\}$ with transition matrix $P$ and stationary distribution $\pi$, let $\{S^t_* : t \in \mathbb{N}\}$ a stationary version of this chain, i.e. $S^0 \sim \pi$. We can construct a two-sided extension of $S^t$ by defining a shift $k \ge 1$, extending the process $S$ backwards in time: $S^t_*(k) = S^{t-k}_*$ with $0 \leq k < \infty$. It is true that by stationarity $S^{t-k}_*$ has the same stationary distribution as $S^t$: we arrive at $\{S^t_* : t \in \mathbb{Z}\}$.

Detailed balance

Let $\{S^t_* : t \in \mathbb{Z}\}$ be a two-sided extension of a positive recurrent Markov chain with transition matrix $P$ and stationary distribution $\pi$. A transition from state $i$ to $j$ is denoted with notation $i \rightarrow j$.

$$\begin{equation} \label{} \begin{split} p(S^{1}_* = j | S^0 = i) &= p(S^{1}_*(k = 1) = j | p(S^{0}_* (k = 1)) = i)\\ &= p(S^{0}_* = j | S^{-1}_* = i)\\ &= \frac{p(S^{-1}_* = i | S^0_* = j) p(S^0_* =j)}{p(S^{-1}_* = i)}\\ &= \frac{\pi_{j}}{\pi_i}P_{i \rightarrow j} \end{split} \end{equation}$$

In other words the time-reverse Markov chain is a Markov chain with transition probabilities:

$$\begin{equation} \label{} \begin{split} P_{i \rightarrow j}\pi_{i} = \pi_j P_{j \rightarrow i} \end{split} \end{equation}$$

This is also known as detailed balance. In the manuscript, ergodic systems are used and therefore satisfy the time-symmetry. This results that $I(s_i^{t+1} ; S^t) = I(s_i^{t-1} ; S^t)$.

Data Correction and Fit Errors

To assess the accuracy of the Monte-Carlo simulations, we evaluated the model fit using mean-squared error. Double exponentials were fitted to estimate the curves before computing the are aunder the curve. For both the the random graphs and the psychosymptom system, the mean squared error was calculated. The results are shown in Figure B.III.1a and Figure B.III.1b.

Validation of Psychosymptoms

The results from this study imply that for low thermal noise not enough resolution was possible to reliably estimate the driver node. For medium to high noise levels, the ‘sad’ emerged as the driver node.

In the original study, the bereavement score was most affected by ‘lonely’, and showed weak negative associations with ‘happy’ and ‘effort’ (fig. B.IV.1 adopted from [86]). Consequently, it seems that medium to high thermal noise is most congruent with the original study. Fried and colleagues postulated that ‘lonely’ was the gateway from which information spreads through the network, i.e. bereavement was embodied mainly by ‘loneliness’ which then percolated its effect to the other symptoms. Since the nature of the data was cross-sectional, the comparison with the results from this study relies on the assumption that binary dynamics are representative of the absence and presence of psychological symptoms. If correct, the results from this study give a causal perspective on the associative results from [86]. The results from this study postulate that ‘depr’, ‘lonely’ and ‘sad’ have similar causal effect for moderate to high thermal noise.

It is important to emphasize that a quantification is given in terms of absolute effect size and not directed effects. This means that nudging for instance ‘sleep’ has some effect $X$ on the psycho-symptom network, in what direction that effect is, or whether it has a positive or negative effect on the bereavement score / cognitive load of the patient is not clear, and should be the subject of future studies.

As a final note, the field of psychometrics is concerned with relating how observables (e.g. behavior, responses on questionnaires, etc) relate to theoretical cognitive constructs such as intelligence or mental disorders. A common approach in understanding high level phenomena such as depression is to use a latent variable model, i.e. assuming some high abstract feature to be the cause of the observables (or vice versa). Only recently has this paradigm shifted from a latent variable model to a network based approach [59], [214], [215]. Marsman et al. recently reconciled these two approached by showing statistical equivalence between the Ising model and canonically used latent variable models in psychometrics [216]. The two approaches thus highlight different aspects in theory building; measurement invariance and correlation structure may be interesting from a common cause approach but not from a network perspective which is more interested in dynamical aspects of the system. Both approaches, however, aid in highlighting different aspects of the psychological constructs.

Code Manual

Accompanying this paper, we developed a general framework for analyzing discrete systems using IMI. The code is written in python 3.7.2 and uses cython 0.28.2 for c/c++ level performance. The code is freely available on cvanelteren.github.ioincludes the latest build instructions.hat follows here is a brief overview of the framework.

Structural Methods

Network analysis has traditionally resulted in analyzing the structure of the network. A fundamental concept within network science is centrality, and how to measure the centrality of nodes has become an essential part of understanding networked systems such as social networks, the internet, biological networks, traffic and ecological networks. At its core, a centrality measure quantifies the ‘importance’ of a node based on some structural property. It allows ranking nodes based on a real-valued function.

There is, however, a long-standing debate concerning what centrality metrics actually measure for networked systems [51], [91], [92], [217] . From a network theoretical perspective most centrality measures, e.g. betweenness, closeness, eigenvector and degree centrality, essentially classify the ‘walk structure’ of a network [91], [92]. A walk from node $i$ to node $j$ is a sequence of adjacent nodes that begins with $i$ and ends with $j$. The structure of walks can be divided along different criteria. For example a trail is a walk in which no edge (i.e. adjacent pair of nodes) is repeated. In contrast, a path is a trail in which no node is visited more than once. Similarly, one could define a walk structure by only using the shortest path from one node to another, or by using random movements between nodes (random walks).

Alternatively, from a complex systems perspective, centrality metrics implicitly assume dynamics on the network structure. Betweenness centrality for example, computes centrality based on how often a node acts as a bridge along the shortest path between two other nodes. If one assumes that the network has dynamics $D$ where information between nodes follows the shortest path, this metric may be a valid description to use and identify dynamically important nodes.

In the best case, a centrality metric is fully predictive for identifying important nodes a complex system. Consequently, the centrality metric can be used to understand the system. However, an issue with the use of centrality metrics is determining which centrality metric to use. Consider for example figure Figure 2.1; different centrality metrics can identify different nodes as most central. This has lead to the common observation that some centrality measures can ‘get it wrong’ when the aim is to predict dynamical important structure in networked systems. Additionally, the ranking produced through some centrality metric does not quantify inter-rank differences. This potentially leads to underestimation of nodal influence when used in dynamic context [51].

We will show how centrality measures have no meaningful prediction power of the most causal node in nodes dictated by the Gibbs measure. We are aware that centrality measures do not embody the full extent of what structural methods embody, or what network science in particular has to offer. However, many structural methods share the common characteristics listed above, i.e. they quantify the walk structure of a network. For our analysis, we used the weighted variants of degree centrality, betweenness centrality, information centrality, and eigenvector centrality. What follows is a brief description of commonly used centrality metrics.

Degree Centrality

Degree centrality is the best-known measure of all the centrality measures. It is often thought that degree centrality is indicative for the dynamic importance of a node. This intuition is based on the concept of flow: the more connection a node has, the more interaction potential that node has and therefore the more important a node must be. Freeman defined centrality measure as the count of the number of edges incident upon a given node [218]:

$$\begin{equation} c_i^{\text{deg}} = \sum_{j} a_{ij} \end{equation}$$(B.9) where $a_{ij}$ is the row/column of node $i$ in the adjacency matrix $A$ of the network. Please note that the entries $a_{ij}$ are weighted and not binary.

Betweenness Centrality

Betweenness centrality quantifies the number of times a node acts as a bridge along the shortest path between two other nodes. It was introduced as a measure for quantifying the control of communication among humans in social networks by Freeman [218]. Nodes that have a high probability to occur on a randomly chosen shortest path between two randomly chosen vertices have a high betweenness. Formally, this can be written as:

$$\begin{equation} \begin{split} c^{\text{betw}}_i = \sum_{j, k} \frac{\sigma(j, k \vert i)}{\sigma(j, k)} \end{split} \end{equation}$$(B.10)

where $\sigma(j, k)$ represents the number of shortest paths between node $j$ and $k$, and $\sigma(j, k \vert i)$ is the subset that goes through node $i$. We use the normalized version of betweenness that divides the betweenness score by the number of pairs of vertices (not including node $i$);

$$\begin{equation} \begin{split} c^{\text{betw}}_i &= \frac{1}{Z}\sum_{j, k} \frac{\sigma(j, k \vert i)}{\sigma(j, k)}\\ Z &= \frac{((n - 1) (n - 2))}{2} \end{split} \end{equation}$$(B.11)

Closeness Centrality

Closeness centrality is defined as the reciprocal sum of the length of the shortest paths between the node $i$ and all other nodes in the network $j \in N$:

$$\begin{equation} c^{\text{close}}_i= \frac{1}{\sum_j^N d(i, j)}. \end{equation}$$(B.12) From a complex system perspective it assumes that information is transferred along its shortest paths. A node with short distance to many other nodes will be able to quickly transfer its information to other nodes in the network.

Eigenvector Centrality

Eigenvector centrality is the most difficult centrality measure to give an intuitive feeling for. Where $A$ is the adjacency matrix of the system, eigenvector centrality of node $i$ is defined as:

$$\begin{equation} \begin{split} c^{\text{ev}}_{i} = \frac{1}{\lambda} \sum_{j} a_{ij} x_{j} \leftrightarrow Ax = \lambda x \end{split} \end{equation}$$(B.13)

For any square matrix of rank $n$, the matrix will have at most $n$ eigenvector-eigenvalues pairs. A common choice for eigenvector centrality is motivated by The Perron-Frobenius theorem, and involves choosing the eigenvector $x$ with the largest eigenvalue $\lambda$ [219], [220]. This has the desired property that if $A$ is irreducible, or equivalently if the network is strongly connected, that the eigenvector $x$ is both unique and positive.

The sign and size of the eigenvalue are important for the relation between the value and importance of a node. In linear differential equations negative eigenvalues correspond to non-oscillatory exponentially stable solutions. In contrast, in difference equations it indicates an oscillatory behavior. Geometrically speaking, negative eigenvector embodies a linear transformation across some axis.

Intuitively speaking, eigenvector centrality quantifies the influence of a node in the network. It assigns relatives scores to all nodes in the network based on the concept that connections to high-scoring nodes contribute more to the score of the node in question than equal connections to low-scoring nodes. A high eigenvector score implies that the node is connected to many other nodes that themselves have high scores. Google PageRank and Katz centrality are variants of eigenvector centrality [221]. A node with high eigenvector centrality is not necessarily a node that has many connection (incoming or outgoing). For example a node may have a high eigenvector centrality if it has few connections, but those connections are connected to nodes that are of high importance.

Bootstrap Distributions

A total of $\num{10000}$ bootstrap samples were conducted with replacement. For each nodal bootstrap distribution a gaussian kernel density was estimated. The node with the highest causal impact was chosen as the initial driver set $\Lambda$. Then the overlap $\phi$ between this driver node and the remaining nodes in the system was computed iteratively. We considered the overlap $\phi = 0.5$ or higher was sufficient for the node was to be considered causally similar to the driver node. Therefore, the proposed node will be included in the driver node set if $\phi \geq 0.5$. We will first outline the procedure after which we discuss the results from this procedure.

Numerical Procedure

The driver node detection algorithm is implemented in Python, with its core functionality illustrated in Algorithm B.VII.1. The algorithm employs a bootstrap-based approach to identify driver nodes through iterative distribution analysis. Starting with a data matrix of features and observations, the procedure generates bootstrap samples and fits normal distributions to analyze the relationships between nodes.

The algorithm first identifies the node with the highest mean value across bootstrap samples as an initial driver. Subsequently, it evaluates other nodes by comparing their distributions with the driver node’s distribution using an overlap criterion $\phi$. Nodes whose distributions overlap significantly with the driver (above the threshold $\phi$) are included in the driver set. Algorithm B.VII.1 provides a visual representation of the algorithm’s workflow, demonstrating the bootstrap sampling and distribution comparison processes.

This implementation leverages Python’s standard library components, specifically the statistics module for normal distribution calculations, ensuring computational efficiency and statistical robustness. The method is particularly effective for analyzing complex systems where traditional deterministic approaches might be insufficient.

Erdős-Rényi Networks

Bootstrap distributions using kernel density estimates are illustrated for Erdős-Rényi networks in Figure B.VII.2. The x-axis represents the area under the curve for either integrated mutual information ($\eta = 0$) or causal impact ($\eta > 0$), where $x$ indicates the area under the curve for either causal impact or integrated mutual information. A representative distribution from system 0 is shown here, as the distributions across different systems exhibit similar characteristics. The complete set of bootstrap distributions for all experimental conditions, including additional network configurations, can be found in the supplementary materials of [45].

Psycho Networks

Note $x$ here refers to the input variable which are the area under curves either for integrated mutual information ($\eta = 0$) or for causal impact $\eta > 0$.

Software

A general toolbox was developed for analyzing any discrete systems using IMI, e.g. Susceptible-Infected-Recovered [222], Random Boolean networks [223]. The core engine is written in 3.07a with python 3.9.4 and offers C/C++ level performance¹, for more information see https://github.com/cvanelteren/information_impact.