Using covariance of node states to design early warning signals for network dynamics

Technical Summary: Using Covariance of Node States to Design Early Warning Signals for Network Dynamics

Problem Statement
Real-life complex systems, ranging from ecosystems to epidemic spreading, often undergo sudden regime shifts or critical transitions. Early warning signals (EWSs) are quantities designed to anticipate these shifts. While many systems are naturally modeled as dynamical systems on networks, not all nodes provide reliable EWSs, and observing every node is often impractical due to cost. Consequently, research focuses on selecting a subset of "sentinel nodes" to construct high-quality EWSs.

A prevalent EWS is the sample variance (or standard deviation) of node states over time. In network contexts, this is often aggregated by averaging the sample variances of selected sentinel nodes. However, it remains an open question whether incorporating the sample covariance between pairs of nodes (off-diagonal entries of the covariance matrix) improves the quality of EWSs compared to using variance alone (diagonal entries). Previous approaches, such as using the dominant eigenvalue of the sample covariance matrix, implicitly utilize both variance and covariance, but the specific utility of averaging covariances directly has not been rigorously isolated and tested against variance-based methods.

Methodology
The authors employ a combination of analytical calculations and extensive numerical simulations to evaluate EWSs constructed from sample covariances versus sample variances.

1. Dynamical Models: The study utilizes four distinct dynamical system models on networks:

   • Coupled double-well dynamics.
   • Mutualistic interaction dynamics.
   • Gene regulatory dynamics.
   • Susceptible-Infectious-Susceptible (SIS) epidemic dynamics.
     These systems are subject to stochastic noise and control parameters ($u$ or $D$) that are gradually varied to induce bifurcations (regime shifts).

2. Theoretical Framework:

   • The authors derive analytical expressions for the expectation and variance of the sample covariance matrix entries ($\hat{C}_{ij}$) for stochastic differential equations linearized around an equilibrium.
   • They define an index $d = \frac{|\mu_1 - \mu_2|}{\sqrt{var_1 + var_2}}$, where $\mu$ and $var$ represent the mean and variance of an EWS calculated at two different control parameter values (one far from and one near the bifurcation). A larger $d$ indicates a better ability to distinguish the pre-shift state from the critical state.
   • They prove two theorems regarding the Coefficient of Variation (CV) of EWSs, demonstrating that under certain conditions, the "diagonal" method (using only variances) yields a lower CV (less relative fluctuation) than methods incorporating off-diagonal covariances.

3. Entry Selection Methods:
   To construct EWSs, the authors compare four methods for selecting entries from the sample covariance matrix $\hat{C}$:

   • Diagonal: Selects $n$ diagonal entries (variances) uniformly at random.
   • Minor: Selects an $n \times n$ submatrix (minor) and averages all $n^2$ entries (variances + covariances).
   • Row: Selects one row and $n$ entries from it.
   • Random: Selects $n$ entries (on- or off-diagonal) uniformly at random from the upper triangular part.
   • Additional methods tested include "Upper Triangular" (excluding diagonals), "Edge" (selecting entries corresponding to network edges), and "Correlation Rank" (selecting pairs with highest initial correlation).

4. Performance Metrics:

   • Kendall's $\tau$: Measures the rank correlation between the EWS and the control parameter. High $\tau$ (ascending) or low $\tau$ (descending) indicates a good EWS.
   • Index $d$: Used to rank sentinel node sets based on their ability to maximize the signal-to-noise ratio between pre-shift and near-shift states.

Key Results

1. Analytical Findings on Small Networks:
   In analytical calculations on four-node networks (chain, star, and lollipop graphs) with varying noise strengths, the authors found that the combinations of covariance matrix entries that maximize the index $d$ predominantly consist of diagonal entries (variances). In the vast majority of cases, adding off-diagonal entries (covariances) to the selection did not improve $d$ and often degraded it.

2. Numerical Simulations on Large Networks:
   Simulations across 23 different networks (including empirical and synthetic topologies) and the four dynamical models confirmed the analytical findings:

   • The "Diagonal" method consistently produced the highest $\tau$ and $d$ values, outperforming all other methods.
   • The "Minor" method (which includes covariances) performed second best, likely because it includes the diagonal entries.
   • Methods relying primarily on off-diagonal entries ("Row", "Random", "Upper Triangular", "Edge", "Correlation Rank") performed significantly worse than the diagonal method.
   • Statistical analysis (ANOVA and Tukey's HSD tests) confirmed that the difference in performance between the "Diagonal" method and the others is statistically significant across all dynamical models.
   • The dominant eigenvalue method, which relies on the full covariance structure, also performed worse than the simple "Diagonal" method.

3. Robustness:
   These results held true regardless of whether the stress and noise were homogeneous or heterogeneous across nodes, and for both ascending and descending simulation directions.

Significance and Claims
The paper claims that the use of sample covariance between node pairs does not improve the quality of Early Warning Signals for network dynamics compared to the use of sample variance.

• Justification for Current Practice: The results support the predominant use of diagonal entries (variances) in EWS construction, validating previous strategies that rely on averaging sample variances of sentinel nodes.
• Design Implications: The findings suggest that for designing EWSs, particularly those based on sentinel node selection, one should prioritize variance over covariance. The authors note that while covariance-based features might be excluded from Machine Learning architectures for EWSs, this conclusion is specific to the linearized stochastic dynamics and equilibrium approaches studied here.
• Limitations and Future Work: The authors explicitly state that their results apply to dynamics asymptotically approaching an equilibrium (saddle-node bifurcations) and do not cover oscillatory dynamics (Hopf bifurcations). They also note that they did not optimize the sentinel node set selection for covariance-based EWSs; it remains theoretically possible that a carefully optimized covariance-based set could outperform variance-based sets, though random selection favors variance. Furthermore, the study distinguishes between temporal EWSs (using time-series of nodes) and spatial EWSs (using spatial statistics), noting that while spatial EWSs inherently use inter-node relations, the current results suggest that covariation may not be helpful even in that context, warranting further investigation.

In summary, the study provides theoretical and numerical evidence that, for the class of network dynamics examined, the sample variance is a superior and sufficient statistic for constructing early warning signals compared to sample covariance.