More Like this

1. Higher-Order Networks Representation and Learning: A Survey

   https://doi.org/10.1145/3682112.3682114  

   Tian, Hao; Zafarani, Reza (July 2024, ACM SIGKDD Explorations Newsletter)

   Network data has become widespread, larger, and more complex over the years. Traditional network data is dyadic, capturing the relations among pairs of entities. With the need to model interactions among more than two entities, significant research has focused on higher-order networks and ways to represent, analyze, and learn from them. There are two main directions to studying higher-order networks. One direction has focused on capturing higher-order patterns in traditional (dyadic) graphs by changing the basic unit of study from nodes to small frequently observed subgraphs, called motifs. As most existing network data comes in the form of pairwise dyadic relationships, studying higher-order structures within such graphs may uncover new insights. The second direction aims to directly model higher-order interactions using new and more complex representations such as simplicial complexes or hypergraphs. Some of these models have long been proposed, but improvements in computational power and the advent of new computational techniques have increased their popularity. Our goal in this paper is to provide a succinct yet comprehensive summary of the advanced higher-order network analysis techniques. We provide a systematic review of the foundations and algorithms, along with use cases and applications of higher-order networks in various scientific domains. 

   more » « less
2. BScNets: Block Simplicial Complex Neural Networks

   https://doi.org/10.1609/aaai.v36i6.20583  

   Chen, Yuzhou; Gel, Yulia R.; Poor, H. Vincent (June 2022, Proceedings of the AAAI Conference on Artificial Intelligence)

   Simplicial neural networks (SNNs) have recently emerged as a new direction in graph learning which expands the idea of convolutional architectures from node space to simplicial complexes on graphs. Instead of predominantly assessing pairwise relations among nodes as in the current practice, simplicial complexes allow us to describe higher-order interactions and multi-node graph structures. By building upon connection between the convolution operation and the new block Hodge-Laplacian, we propose the first SNN for link prediction. Our new Block Simplicial Complex Neural Networks (BScNets) model generalizes existing graph convolutional network (GCN) frameworks by systematically incorporating salient interactions among multiple higher-order graph structures of different dimensions. We discuss theoretical foundations behind BScNets and illustrate its utility for link prediction on eight real-world and synthetic datasets. Our experiments indicate that BScNets outperforms the state-of-the-art models by a significant margin while maintaining low computation costs. Finally, we show utility of BScNets as a new promising alternative for tracking spread of infectious diseases such as COVID-19 and measuring the effectiveness of the healthcare risk mitigation strategies. 

   more » « less
3. Simplicial cascades are orchestrated by the multidimensional geometry of neuronal complexes

   https://doi.org/10.1038/s42005-022-01062-3  

   Kilic, Bengier Ülgen; Taylor, Dane (December 2022, Communications Physics)

   Abstract Cascades over networks (e.g., neuronal avalanches, social contagions, and system failures) often involve higher-order dependencies, yet theory development has largely focused on pairwise-interaction models. Here, we develop a ‘simplicial threshold model’ (STM) for cascades over simplicial complexes that encode dyadic, triadic and higher-order interactions. Focusing on small-world models containing both short- and long-range k -simplices, we explore spatio-temporal patterns that manifest as a frustration between local and nonlocal propagations. We show that higher-order interactions and nonlinear thresholding coordinate to robustly guide cascades along a k -dimensional generalization of paths that we call ‘geometrical channels’. We also find this coordination to enhance the diversity and efficiency of cascades over a simplicial-complex model for a neuronal network, or ‘neuronal complex’. We support these findings with bifurcation theory and data-driven approaches based on latent geometry. Our findings provide fruitful directions for uncovering the multiscale, multidimensional mechanisms that orchestrate the spatio-temporal patterns of nonlinear cascades. 

   more » « less
4. Topological clustering of multilayer networks

   https://doi.org/10.1073/pnas.2019994118  

   Yuvaraj, Monisha; Dey, Asim K.; Lyubchich, Vyacheslav; Gel, Yulia R.; Poor, H. Vincent (May 2021, Proceedings of the National Academy of Sciences)

   null (Ed.)

   Multilayer networks continue to gain significant attention in many areas of study, particularly due to their high utility in modeling interdependent systems such as critical infrastructures, human brain connectome, and socioenvironmental ecosystems. However, clustering of multilayer networks, especially using the information on higher-order interactions of the system entities, still remains in its infancy. In turn, higher-order connectivity is often the key in such multilayer network applications as developing optimal partitioning of critical infrastructures in order to isolate unhealthy system components under cyber-physical threats and simultaneous identification of multiple brain regions affected by trauma or mental illness. In this paper, we introduce the concepts of topological data analysis to studies of complex multilayer networks and propose a topological approach for network clustering. The key rationale is to group nodes based not on pairwise connectivity patterns or relationships between observations recorded at two individual nodes but based on how similar in shape their local neighborhoods are at various resolution scales. Since shapes of local node neighborhoods are quantified using a topological summary in terms of persistence diagrams, we refer to the approach as clustering using persistence diagrams (CPD). CPD systematically accounts for the important heterogeneous higher-order properties of node interactions within and in-between network layers and integrates information from the node neighbors. We illustrate the utility of CPD by applying it to an emerging problem of societal importance: vulnerability zoning of residential properties to weather- and climate-induced risks in the context of house insurance claim dynamics. 

   more » « less
5. The dynamic nature of percolation on networks with triadic interactions

   https://doi.org/10.1038/s41467-023-37019-5  

   Sun, Hanlin; Radicchi, Filippo; Kurths, Jürgen; Bianconi, Ginestra (December 2023, Nature Communications)

   Abstract Percolation establishes the connectivity of complex networks and is one of the most fundamental critical phenomena for the study of complex systems. On simple networks, percolation displays a second-order phase transition; on multiplex networks, the percolation transition can become discontinuous. However, little is known about percolation in networks with higher-order interactions. Here, we show that percolation can be turned into a fully fledged dynamical process when higher-order interactions are taken into account. By introducing signed triadic interactions, in which a node can regulate the interactions between two other nodes, we define triadic percolation. We uncover that in this paradigmatic model the connectivity of the network changes in time and that the order parameter undergoes a period doubling and a route to chaos. We provide a general theory for triadic percolation which accurately predicts the full phase diagram on random graphs as confirmed by extensive numerical simulations. We find that triadic percolation on real network topologies reveals a similar phenomenology. These results radically change our understanding of percolation and may be used to study complex systems in which the functional connectivity is changing in time dynamically and in a non-trivial way, such as in neural and climate networks. 

   more » « less