A scalable synergy-first backbone decomposition of higher-order structures in complex systems

The question of whether a complex system's "whole" is "greater than the sum of its parts" is central to complexity theory. Emergent, higher-order phenomena arising from interactions between lower-order elements are defining features of complex systems across various domains. Information theory provides a mathematically rigorous framework for exploring part-whole relationships in multivariate systems. "Synergy," information present in the joint state of the whole but not its parts, is a key statistic of emergent behaviors. Synergy's ubiquity has been observed in various systems, including neural networks, brain dynamics, climatological systems, social interactions, and even heart-rate dynamics. Its relevance to clinical processes like aging, brain injury, and the effects of drugs is also increasingly recognized. Despite synergy's significance, mathematical tools for exploring it in empirical data remain limited. Existing methods fall into two categories: those based on PID and those based on O-information and related measures. While powerful, PID-like approaches suffer from super-exponential scaling, making them impractical for systems with more than a few elements. Their redundancy-first approach also implicitly defines synergy, making the interpretation challenging. O-information-based methods scale better but provide only summary statistics, lacking detailed insight into the system's synergy structure. This paper addresses these limitations by proposing a novel approach.

The existing literature on measuring synergy in complex systems primarily centers around two major methodologies: Partial Information Decomposition (PID) and O-information. PID, and its variants like Partial Entropy Decomposition (PED), Integrated Information Decomposition (IID), and Generalized Information Decomposition (GID), aims to provide a complete decomposition of multivariate information into unique, redundant, and synergistic components. However, the computational complexity of PID grows super-exponentially with the number of variables, limiting its applicability to small systems. Additionally, PID's reliance on a redundancy-first approach makes the identification and interpretation of synergistic contributions less direct. Alternatively, O-information and similar measures offer a more heuristic approach. They efficiently assess whether redundancy or synergy dominates a system, but do not provide detailed information on the structural organization of synergistic contributions across different scales. They generally provide a less granular picture and may not capture the nuanced aspects of higher-order interactions present in complex systems. This paper aims to overcome the limitations of both approaches.

This paper proposes a new synergy-first decomposition method. It defines synergy as the information in the joint state of a set of elements that is lost when any single element is minimally perturbed. This definition is generalized to sets of elements, constructing a totally ordered "backbone" of partial synergy atoms that captures the system's structure across different scales. The methodology is built upon a series of steps: 1. **Defining Synergistic Information:** The paper formally defines synergistic information in a system X = {X₁, ..., Xk} as the information that would be lost if any single channel (Xᵢ) were to fail. This is mathematically represented using the minimum function (minᵢ [h(x) - h(xᵢ)]), where h(x) is the local entropy and h(xᵢ) is the entropy of all elements except Xᵢ. The expected synergy H¹¹(X) is then calculated as the average over all possible states x. 2. **The α-Synergy Backbone:** The concept is extended beyond single-element failures to consider the failure of sets of α elements. The α-synergy, h^α(x), is defined as the minimum information loss across all possible sets of α failures. The α-partial synergy function, ∂h_α(x), is then used to partition the local entropy into non-negative partial synergies, arranged in increasing order of robustness. The expected α-partial synergy, ∂H_α(X), is obtained by averaging over all realizations x. 3. **Generalization to Other Measures:** The α-synergy decomposition is extended beyond entropy to include the Kullback-Leibler (KL) divergence, using the relationship between KL divergence and entropy. This allows the application of the framework to other information-theoretic measures like negentropy, total correlation, and single-target mutual information. The α-synergy decomposition of the KL divergence results in local and expected α-synergistic divergences, offering insights into the changes in synergistic surprise between different probability distributions. 4. **Structural Synergy:** The concept is generalized beyond information theory. Any function f(X) on a set X can induce a structural synergy if it satisfies four criteria: localizability, symmetry, non-negativity, and monotonicity. This framework is applied to graph communicability, where α-synergy is computed by considering the loss of integration upon edge failures, giving insights into the robustness and synergy of network communication. The methodology's computational complexity scales with Bell numbers, making it more tractable than PID, although for extremely large systems, heuristic methods such as random sampling or optimization techniques (like simulated annealing) may be necessary. The paper notes potential challenges related to maintaining the monotonicity of the α-synergy function when employing these heuristic approaches.

The paper presents several key findings: 1. **A novel synergy-first decomposition:** The α-synergy decomposition provides a more scalable and interpretable alternative to existing methods for quantifying synergy in complex systems. It defines synergy directly, avoiding the implicit definition inherent in redundancy-first approaches. This method offers a more efficient way to explore synergistic structures in systems with numerous interacting elements. 2. **Application to various information-theoretic measures:** The decomposition is successfully applied to entropy, Kullback-Leibler divergence, total correlation, and single-target mutual information. This demonstrates its versatility and broad applicability in analyzing various aspects of information processing within complex systems. The resulting α-synergy atoms provide insights into different levels of synergistic information and their robustness to perturbation, offering a more comprehensive understanding of how information is shared among system components. 3. **Extension beyond information theory:** The framework is extended to non-information theoretic contexts. The concept of "structural synergy" is introduced and applied to graph communicability. This showcases the method's potential applications in studying other types of structures beyond information sharing, such as the robustness and integration of complex networks. Analyzing the α-synergistic communicability helps reveal the extent to which global integration relies on the joint presence of multiple edges in the graph, providing new insights into network resilience and emergent properties. 4. **Analysis of example systems:** The α-synergy decomposition is applied to several example systems (XOR, Giant Bit, W-distribution, and maximum entropy), illustrating its ability to reveal different types of synergy. This underscores the critical role of choosing appropriate parameters (measure and synergy function) in analyzing specific systems, highlighting the nuances that may arise when interpreting the results from different perspectives. 5. **Comparison with existing methods:** The paper provides a detailed comparison of the α-synergy decomposition with PID and O-information. It emphasizes the tradeoffs between scalability and the level of detail provided by each method, making a clear case for the α-synergy decomposition's position as a valuable addition to the existing toolkit for analyzing complex systems. This provides a comprehensive overview of the strengths and weaknesses of alternative methods, offering guidance to researchers on selecting the most appropriate approach based on the specific needs of their study.

The α-synergy decomposition presented in this paper provides a valuable contribution to the field of complex systems analysis. By offering a synergy-first, scalable approach that is readily generalizable across several information-theoretic and non-information-theoretic measures, it addresses crucial limitations of existing methods. The ability to decompose both directed and undirected information offers researchers a more nuanced understanding of information processing and system robustness. The extension to structural synergy opens new avenues for investigating the organization of complex networks and their resilience to perturbations. The results obtained from applying the α-synergy decomposition to various example systems highlight its ability to uncover unique insights into system structure and organization. However, the choice of the appropriate measure (entropy, total correlation, or mutual information) and synergy function (minimum, maximum, or average) remains critical for correct interpretation and must be guided by the specific research question. Future research should focus on refining the computational methods, particularly for large systems, while ensuring that the theoretical guarantees of the decomposition are maintained. The exploration of synergies in dynamical systems is another important area for future investigation.

The α-synergy decomposition offers a powerful and efficient method for analyzing synergistic information in complex systems. Its synergy-first approach, scalability, and generalizability across various information-theoretic and structural measures make it a significant advancement. The ability to reveal the distribution of synergy across different scales provides a richer understanding of system robustness and emergent properties. Further development of computational methods and application to dynamical systems will enhance its utility and broaden its impact on the study of complex systems.

While the α-synergy decomposition offers significant advantages over existing methods, it also has limitations. The computational complexity, though improved compared to PID, can still become challenging for extremely large systems. Employing heuristic approximations may compromise the strict mathematical properties of the decomposition. Additionally, the method homogenizes information across elements, providing summary statistics rather than element-specific details of synergistic contributions. Future research should address these limitations by developing more efficient algorithms and exploring ways to incorporate element-specific information into the analysis.