Hyperedge Entanglement in High-Order Multilayer Networks

Alessandro Muscoloni, Ilyes Abdelhamid, Julius L. Decano, Edwin Souza, Enrico Maiorino, Masanori Aikawa, Edwin K. Silverman, Amitabh Sharma, Carlo Vittorio CannistraciPreprints.org 2020 · DOI

TL;DR

This paper introduces "hyperedge entanglement" (HE) and a prediction framework (HEP) to uncover hidden relationships in complex, multi-layered networks, even when communities aren't clearly defined. This approach successfully predicts gene associations with diseases, validated by biological experiments, offering new insights into disease mechanisms.

What Problem Does This Paper Address?

Many real-world systems, like social networks or biological pathways, are incredibly complex and can't be fully understood by looking at simple pairwise connections (dyadic links). They often have "high-order metadata" – information that describes relationships involving more than two entities at once. While community detection has been a popular way to analyze these systems, real-world networks often lack clear, pre-defined communities. This leaves a gap in our ability to analyze high-order metadata without making assumptions about community structure. The authors aim to bridge this gap by proposing a new way to think about these relationships: "hyperedge entanglement."

Methods

The core innovation is the concept of hyperedge entanglement (HE). Imagine a hyperedge as a group of nodes sharing a common property (like genes involved in a disease). HE associates an "entangled hyperedge" to this original hyperedge. This entangled hyperedge contains nodes that have a significant "interaction at distance" with the original hyperedge's members, even if they aren't directly connected.

To predict this entanglement, they introduce Hyperedge Entanglement Prediction (HEP). This involves:

  1. Node2Hyperedge Entanglement (N2HE): A necessary condition (ENC) checks if a node is not part of a hyperedge and not directly linked to its members. A sufficient condition (ESC) then uses a "topological entanglement operator" (TEO) based on link prediction to assess the significance of the interaction.
  2. HEP Algorithm: This algorithm iterates through hyperedges, identifies candidate nodes using N2HE, and predicts which nodes belong to the entangled hyperedge. They explore various link prediction methods (L2 and L3 based), averaging operators (mean, median, mode), and p-value correction strategies.

Datasets

The authors evaluated their HEP framework on:

  • Three real social networks: Football, Opsahl_10, and Polbooks. These have non-overlapping hyperedges representing group memberships.
  • Two large biological networks: S. cerevisiae PPI (protein-protein interaction) and E. coli metabolic networks. These have overlapping hyperedges representing biological annotations.
  • Synthetic networks: Generated using the nonuniform popularity-similarity-optimization (nPSO) model to mimic real-world network properties like clustering and community structure.
  • Human Protein Interactome: Used for a case study on Chronic Obstructive Pulmonary Disease (COPD).

Key Insights and Ideas

  • Beyond Communities: The framework doesn't rely on pre-defined communities, making it applicable to networks where community structure is unclear or absent. This is crucial for real-world data.
  • "Interaction at Distance": The concept of hyperedge entanglement captures subtle, indirect relationships that might be missed by traditional methods.
  • Biological Validation: The successful experimental validation of predicted gene-disease associations is a strong indicator of the framework's utility in biomedicine.
  • L3 Link Predictors Shine: For many network types, especially social ones, link prediction methods based on paths of length three (L3) outperformed those based on length two (L2) in the HEP context. This suggests that longer paths can capture more relevant indirect connections for hyperedge entanglement.
  • Local vs. Global: Local link prediction methods are favored for efficiency in HEP, as they can adapt computational time to specific queries without needing to analyze the entire network.

Key Results

  • HEP demonstrated significant performance over random prediction across various real and synthetic networks.
  • In the COPD case study, HEP successfully predicted gene entanglements with the COPD disease hyperedge.
  • Experimental validation (co-immunoprecipitation and gene silencing) confirmed predicted interactions between MFAP5 and genes like ELN and TGFB2, shedding light on COPD mechanisms.
  • The analysis revealed enriched pathways (platelet degranulation, elastic fibers) associated with COPD and highlighted potential links to aortic aneurysm comorbidity.
  • L3-based link predictors generally showed superior performance in HEP tasks, particularly on social networks.

Limitations and Future Work

  • Computational Complexity: While local link predictors improve efficiency, the overall complexity of HEP can still be significant, especially for very large networks.
  • Choice of Link Predictor: The performance of HEP is influenced by the choice of link prediction algorithm, and further research could explore more advanced or specialized predictors.
  • Generalizability: While tested on diverse networks, exploring HEP's applicability to other types of high-order multilayer systems (e.g., temporal networks, networks with different metadata structures) would be valuable.
  • Entanglement Operator Design: The paper focused on topological entanglement operators (TEO) but suggests that integrating geometrical (GEO) or hybrid (TGEO) operators could offer further insights.
  • Further Biological Validation: While the COPD case study was experimentally validated, applying HEP to other diseases and validating predictions would strengthen its impact in biomedicine.

Summary updated

Abstract

Many real complex systems present multilayer structure where high-order metadata on one layer refers to dyadic data on a lower layer. Significant progresses to analyse high-order metadata under the assumption of community organization have been done. However, there are no planted communities in real-world networks, and the necessity of new frameworks to analyze high-order metadata regardless of community organization has been raised.Here, we propose to adopt hyperedge organization. Predicting ‘entanglements’ between a hyperedge and nodes scattered in the rest of the network might suggest structural or functional liaisons, without assumption of any community organization. We introduce a novel concept: hyperedge entanglement (HE), which associates to each hyperedge an entangled hyperedge, by means of a network operator that predicts significant ‘interactions at distance’ between network nodes and existing hyperedges. We also introduce a new challenge termed hyperedge entanglement prediction (HEP), and an algorithm to perform this task. We evaluated HEP performance on social, biological and synthetic data where, given only topology and hyperedges (such as communities or functional modules), the goal is to predict whether nodes not connected to a certain hyperedge might be candidates for a significant entanglement. Finally, as real application in diseasome systems biomedicine, we perform HEP on the human protein interactome to predict unknown gene entanglements with the COPD disease gene hyperedge. HEP predictions are validated by biological experiments, enlarging our understanding of molecular mechanisms behind COPD/aneurysm comorbidity.
BibTeX
@misc{muscoloni2020hyperedge,
  author = {Alessandro Muscoloni and Ilyes Abdelhamid and Julius L. Decano and Edwin Souza and Enrico Maiorino and Masanori Aikawa and Edwin K. Silverman and Amitabh Sharma and Carlo Vittorio Cannistraci},
  title = {{Hyperedge Entanglement in High-Order Multilayer Networks}},
  year = {2020},
  doi = {10.20944/preprints202012.0500.v1},
  howpublished = {Preprints.org},
}
Figure