Past Networks Seminar

Combining physics with machine learning is a rapidly growing field of research. Thereby, most work focuses on leveraging machine learning methods to solve problems in physics. Here, however, we focus on the reverse direction of leveraging structure of physical systems (e.g. dynamical systems modeled by ODEs or PDEs) to construct novel machine learning algorithms, where the existence of highly desirable properties of the underlying method can be rigorously proved. In particular, we propose several physics-inspired deep learning architectures for sequence modelling as well as for graph representation learning. The proposed architectures mitigate central problems in each corresponding domain, such as the vanishing and exploding gradients problem for recurrent neural networks or the oversmoothing problem for graph neural networks. Finally, we show that this leads to state-of-the-art performance on several widely used benchmark problems.

Chimera states have attracted significant attention as symmetry-broken states exhibiting the coexistence of coherence and incoherence. Despite the valuable insights gained by analyzing specific systems, the understanding of the physical mechanism underlying the emergence of chimeras has been incomplete. In this presentation, I will argue that an important class of stable chimeras arise because coherence in part of the system is sustained by incoherence in the rest of the system. This mechanism may be regarded as a deterministic analog of noise-induced synchronization and is shown to underlie the emergence of so-called strong chimeras. These are chimera states whose coherent domain is formed by identically synchronized oscillators. The link between coherence and incoherence revealed by this mechanism also offers insights into the dynamics of a broader class of states, including switching chimera states and incoherence-mediated remote synchronization.

Synchronization, epidemic processes and information spreading are natural processes that emerge from the interaction between people. Mathematically, all of them can be described by models that, despite their simplicity, they can predict collective behaviors. In addition, they have in common a very interesting feature: a phase transition from an active state to an absorbing state. For example, the spread of an epidemic is characterized by the infection rate, the control parameter, which basically determines whether the epidemic will spread in the network or, if this rate is very low, few people become infected and the system falls into an absorbing state where there are no more infected people. In this presentation we will present the analytical and computational approaches used to investigate these classical models of statistical physics that present phase transitions and we will also show how the network topology influences such dynamical processes. The behavior of such dynamics can be much richer than we imagine.

Co-occurrence networks formed by bipartite projection are widely studied in many contexts, including politics (bill co-sponsorship), bibliometrics (paper co-authorship), ecology (species co-habitation), and genetics (protein co-expression). It is often useful to focus on the backbone, a binary representation that includes only the most important edges, however many different backbone extraction models exist. In this talk, I will demonstrate the "backbone" package for R, which implements many such models. I will also use it to compare two promising null models: the fixed degree sequence model (FDSM) that imposes hard constraints, and the stochastic degree sequence model (SDSM) that imposes soft constraints, on the bipartite degree sequences. While FDSM is more statistically powerful, SDSM is more efficient and offers a close approximation.

In this talk I will present network-theoretic tools [1-2] to filter information in large-scale datasets and I will show that these are powerful tools to study complex datasets. In particular I will introduce correlation-based information filtering networks and the planar filtered graphs (PMFG) and I will show that applications to financial data-sets can meaningfully identify industrial activities and structural market changes [3-4].

It has been shown that by making use of the 3-clique structure of the PMFG a clustering can be extracted allowing dimensionality reduction that keeps both local information and global hierarchy in a deterministic manner without the use of any prior information [5-6]. However, the algorithm so far proposed to construct the PMFG is numerically costly with O(N3) computational complexity and cannot be applied to large-scale data. There is therefore scope to search for novel algorithms that can provide, in a numerically efficient way, such a reduction to planar filtered graphs. I will introduce a new algorithm, the TMFG (Triangulated Maximally Filtered Graph), that efficiently extracts a planar subgraph which optimizes an objective function. The method is scalable to very large datasets and it can take advantage of parallel and GPUs computing [7]. Filtered graphs are valuable tools for risk management and portfolio optimization too [8-9] and they allow to construct probabilistic sparse modeling for financial systems that can be used for forecasting, stress testing and risk allocation [10].

Filtered graphs can be used not only to extract relevant and significant information but more importantly to extract knowledge from an overwhelming quantity of unstructured and structured data. I will provide a practitioner example by a successful Silicon Valley start-up, Yewno. The key idea underlying Yewno’s products is the concept of the Knowledge Graph, a framework based on filtered graph research, whose goal is to extract signals from evolving corpus of data. The common principle is that a methodology leveraging on developments in Computational linguistics and graph theory is used to build a graph representation of knowledge [11], which can be automatically analysed to discover hidden relations between components in many different complex systems. This Knowledge Graph based framework and inference engine has a wide range of applications, including finance, economics, biotech, law, education, marketing and general research.

[1] T. Aste, T. Di Matteo, S. T. Hyde, Physica A 346 (2005) 20.

[2] T. Aste, Ruggero Gramatica, T. Di Matteo, Physical Review E 86 (2012) 036109.

[3] M. Tumminello, T. Aste, T. Di Matteo, R. N. Mantegna, PNAS 102, n. 30 (2005) 10421.

[4] N. Musmeci, Tomaso Aste, T. Di Matteo, Journal of Network Theory in Finance 1(1) (2015) 1-22.

[5] W.-M. Song, T. Di Matteo, and T. Aste, PLoS ONE 7 (2012) e31929.

[6] N. Musmeci, T. Aste, T. Di Matteo, PLoS ONE 10(3): e0116201 (2015).

[7] Guido Previde Massara, T. Di Matteo, T. Aste, Journal of Complex networks 5 (2), 161 (2016).

[8] F. Pozzi, T. Di Matteo and T. Aste, Scientific Reports 3 (2013) 1665.

[9] N. Musmeci, T. Aste and T. Di Matteo, Scientific Reports 6 (2016) 36320.

[10] Wolfram Barfuss, Guido Previde Massara, T. Di Matteo, T. Aste, Phys.Rev. E 94 (2016) 062306.

[11] Ruggero Gramatica, T. Di Matteo, Stefano Giorgetti, Massimo Barbiani, Dorian Bevec and Tomaso Aste, PLoS One (2014) PLoS ONE 9(1): e84912.

Pair combination repurposing of drugs is a common challenge faced by researchers in the pharmaceutical industry. Network biology and molecular machine learning based drug pair scoring techniques offer computation tools to predict the interaction, polypharmacy side effects and synergy of drugs. In this talk we overview of three things: (a) the theory and unified model of drug pair scoring (b) a relational machine learning model that can solve the pair scoring task (c) the design of large-scale machine learning systems needed to tackle the pair scoring task.

ArXiv links: https://arxiv.org/abs/2111.02916, https://arxiv.org/abs/2110.15087, https://arxiv.org/abs/2202.05240.

ML library: https://github.com/AstraZeneca/chemicalx

Random walks are a common model for the exploration and discovery of complex networks. While numerous algorithms have been proposed to map out an unknown network, a complementary question arises: in a known network, which nodes and edges are most likely to be discovered by a random walker in finite time? In this talk we introduce exposure theory, a statistical mechanics framework that predicts the learning of nodes and edges across several types of networks, including weighted and temporal, and show that edge learning follows a universal trajectory. While the learning of individual nodes and edges is noisy, exposure theory produces a highly accurate prediction of aggregate exploration statistics. As a specific application, we extend exposure theory to better understand human learning with its typical mental errors, and thus account for distortions of learned networks.

This talk is based on https://arxiv.org/abs/2202.11262

In this talk we will look at the different ways to define city boundaries, and the relevance to consider socio-demographic and spatial connectivity in urban systems, in particular if interventions are to be considered.

Data that have an intrinsic network structure are becoming increasingly common in various scientific applications. Compressing such data for storage or transmission is an important problem, especially since networks are increasingly large. From an information theoretic perspective, the limit to compression of a random graph is given by the Shannon entropy of its distribution. A relevant question is how much of the information content of a random graph pertains to its structure (i.e., the unlabelled version of the graph), and how much of it is contained in the labels attached to the structure. Furthermore, in applications in which one is interested only in structural properties of a graph (e.g., node degrees, connectedness, frequency of occurrence of certain motifs), the node labels are irrelevant, such that only the structure of the graph needs to be compressed, leading to a more compact representation. In this talk, I will consider the random geometric graph (RGG), where pairs of nodes are connected based on the distance between them in some latent space. This model captures well important characteristics of biological systems, information networks, social networks, or economic networks. Since determination of the entropy is extremely difficult for this model, I will present upper bounds we obtained for the entropy of the labelled RGG. Then, we will focus on the structural information in the one-dimensional RGG. I will show our latest results in terms of the number of structures in the considered model and bounds on the structural entropy, together with the asymptotic behaviour of the bounds for different regimes of the connection range. Finally, I will also present a simple encoding scheme for one-dimensional RGG structures that asymptotically achieves the obtained upper limit on the structural entropy.

arXiv link: https://arxiv.org/abs/2107.13495

The non-backtracking matrix and its eigenvalues have many applications in network science and graph mining. For example, in network epidemiology, the reciprocal of the largest eigenvalue of the non-backtracking matrix is a good approximation for the epidemic threshold of certain network dynamics. In this work, we develop techniques that identify which nodes have the largest impact on the leading non-backtracking eigenvalue. We do so by studying the behavior of the spectrum of the non-backtracking matrix after a node is removed from the graph, which can be thought of as immunizing a node against the spread of disease. From this analysis we derive a centrality measure which we call X-degree, which is then used to predict which nodes have a large influence in the epidemic threshold. Finally, we discuss work currently in progress on connections with eigenvector localization and percolation theory.

Measures of discrete curvature are a recent addition to the toolkit of network analysts and data scientists. At the basis lies the idea that networks and other discrete objects exhibit distinct geometric properties that resemble those of smooth objects like surfaces and manifolds, and that we can thus find inspiration in the tools of differential geometry to study these discrete objects. In this talk, I will introduce how this has lead to the development of notions of discrete curvature, and what they are good for. Furthermore, I will discuss our latest results on a new notion of curvature on graphs, based on the effective resistance. These new "resistance curvatures" are related to other well-known notions of discrete curvature (Ollivier, Forman, combinatorial curvature), we find evidence for convergence to continuous curvature in the case of Euclidean random graphs and there is a naturally associated discrete Ricci flow.

A preprint on this work is available on arXiv: https://arxiv.org/abs/2201.06385

A metapopulation model, composed of subpopulations and pairwise connections, is a particle-network framework for epidemic dynamics study. Individuals are well-mixed within each subpopulation and migrate from one subpopulation to another, obeying a given mobility rule. While different mobility rules in metapopulation models have been studied, few efforts have been made to compare the effects of simple (i.e., unbiased) random walks and more complex mobility rules. In this talk, we study susceptible-infectious-susceptible (SIS) dynamics in a metapopulation model, in which individuals obey a second-order parametric random-walk mobility rule called the node2vec. We transform the node2vec mobility rule to a first-order Markov chain whose state space is composed of the directed edges and then derive the epidemic threshold. We find that the epidemic threshold is larger for various networks when individuals avoid frequent backtracking or visiting a neighbor of the previously visited subpopulation than when individuals obey the simple random walk. The amount of change in the epidemic threshold induced by the node2vec mobility is generally not as significant as, but is sometimes comparable with, the one induced by the change in the diffusion rate for individuals.

arXiv links: https://arxiv.org/abs/2006.04904 and https://arxiv.org/abs/2106.08080

In this talk we will show the application of (multilayer) network science to a wide spectrum of problems related to the ongoing COVID-19 pandemic, ranging from the molecular to the societal scale. Specifically, we will discuss our recent results about how network analysis: i) has been successfully applied to virus-host protein-protein interactions to unravel the systemic nature of SARS-CoV-2 infection; ii) has been used to gain insights about the potential role of non-compliant behavior in spreading of COVID-19; iii) has been crucial to assess the infodemic risk related to the simultaneous circulation of reliable and unreliable information about COVID-19.

References:

Assessing the risks of "infodemics" in response to COVID-19 epidemics
R. Gallotti, F. Valle, N. Castaldo, P. Sacco, M. De Domenico, Nature Human Behavior 4, 1285-1293 (2020)

CovMulNet19, Integrating Proteins, Diseases, Drugs, and Symptoms: A Network Medicine Approach to COVID-19
N. Verstraete, G. Jurman, G. Bertagnolli, A. Ghavasieh, V. Pancaldi, M. De Domenico, Network and Systems Medicine 3, 130 (2020)

Multiscale statistical physics of the pan-viral interactome unravels the systemic nature of SARS-CoV-2 infections
A. Ghavasieh, S. Bontorin, O. Artime, N. Verstraete, M. De Domenico, Communications Physics 4, 83 (2021)

Individual risk perception and empirical social structures shape the dynamics of infectious disease outbreaks
V. D'Andrea, R. Gallotti, N. Castaldo, M. De Domenico, To appear in PLOS Computational Biology (2022)

In the first part of the seminar I will introduce shallow neural-networks from a statistical-mechanics perspective, focusing on simple cases and on a naive scenario where information to be learnt is structureless. Then, inspired by biological information processing, I will enrich this framework by accounting for structured datasets and by making the network able to perform challenging tasks like generalization or even "taking a nap”. Results presented are both analytical and numerical.

Identifying novel drug-target interactions (DTI) is a critical and rate limiting step in drug discovery. While deep learning models have been proposed to accelerate the identification process, we show that state-of-the-art models fail to generalize to novel (i.e., never-before-seen) structures. We first unveil the mechanisms responsible for this shortcoming, demonstrating how models rely on shortcuts that leverage the topology of the protein-ligand bipartite network, rather than learning the node features. Then, we introduce AI-Bind, a pipeline that combines network-based sampling strategies with unsupervised pre-training, allowing us to limit the annotation imbalance and improve binding predictions for novel proteins and ligands. We illustrate the value of AI-Bind by predicting drugs and natural compounds with binding affinity to SARS-CoV-2 viral proteins and the associated human proteins. We also validate these predictions via auto-docking simulations and comparison with recent experimental evidence. Overall, AI-Bind offers a powerful high-throughput approach to identify drug-target combinations, with the potential of becoming a powerful tool in drug discovery.

arXiv link: https://arxiv.org/abs/2112.13168

We consider spectral methods that uncover hidden structures in directed networks. We establish and exploit connections between node reordering via (a) minimizing an objective function and (b) maximizing the likelihood of a random graph model. We focus on two existing spectral approaches that build and analyse Laplacian-style matrices via the minimization of frustration and trophic incoherence. These algorithms aim to reveal directed periodic and linear hierarchies, respectively. We show that reordering nodes using the two algorithms, or mapping them onto a specified lattice, is associated with new classes of directed random graph models. Using this random graph setting, we are able to compare the two algorithms on a given network and quantify which structure is more likely to be present. We illustrate the approach on synthetic and real networks, and discuss practical implementation issues. This talk is based on a joint work with Desmond Higham and Konstantinos Zygalakis. 

Article link: https://royalsocietypublishing.org/doi/10.1098/rsos.211144

Trophic coherence, a measure of a graph’s hierarchical organisation, has been shown to be linked to a graph’s structural and dynamical aspects such as cyclicity, stability and normality. Trophic levels of vertices can reveal their functional properties, partition and rank the vertices accordingly. Trophic levels and hence trophic coherence can only be defined on graphs with basal vertices, i.e. vertices with zero in-degree. Consequently, trophic analysis of graphs had been restricted until now. In this talk I will introduce a novel  framework which can be defined on any simple graph. Within this general framework, I'll illustrate several new metrics: hierarchical levels, a generalisation of the notion of trophic levels, influence centrality, a measure of a vertex’s ability to influence dynamics, and democracy coefficient, a measure of overall feedback in the system. I will then discuss what new insights are illuminated on the topological and dynamical aspects of graphs. Finally, I will show how the hierarchical structure of a network relates to the incidence rate in a SIS epidemic model and the economic insights we can gain through it.

Article link: https://www.nature.com/articles/s41598-021-93161-4

We are confronted with signals defined on the nodes of a graph in many applications.  Think for instance of a sensor network measuring temperature; or a social network, in which each person (node) has an opinion about a specific issue.  Graph signal processing (GSP) tries to device appropriate tools to process such data by generalizing classical methods from signal processing of time-series and images -- such as smoothing, filtering and interpolation -- to signals defined on graphs.  Typically, this involves leveraging the structure of the graph as encoded in the spectral properties of the graph Laplacian.

In other applications such as traffic network analysis, however, the signals of interest are naturally defined on the edges of a graph, rather than on the nodes. After a very brief recap of the central ideas of GSP, we examine why the standard tools from GSP may not be suitable for the analysis of such edge signals.  More specifically, we discuss how the underlying notion of a 'smooth signal' inherited from (the typically considered variants of) the graph Laplacian are not suitable when dealing with edge signals that encode flows.  To overcome this limitation we devise signal processing tools based on the Hodge-Laplacian and the associated discrete Hodge Theory for simplicial (and cellular) complexes.  We discuss applications of these ideas for signal smoothing, semi-supervised and active learning for edge-flows on discrete (or discretized) spaces.

TBA

In the event of food-borne disease outbreaks, conventional epidemiological approaches to identify the causative food product are time-intensive and often inconclusive. Data-driven tools could help to reduce the number of products under suspicion by efficiently generating food-source hypotheses. We frame the problem of generating hypotheses about the food-source as one of identifying the source network from a set of food supply networks (e.g. vegetables, eggs) that most likely gave rise to the illness outbreak distribution over consumers at the terminal stage of the supply network. We introduce an information-theoretic measure that quantifies the degree to which an outbreak distribution can be explained by a supply network’s structure and allows comparison across networks. The method leverages a previously-developed food-borne contamination diffusion model and probability distribution for the source location in the supply chain, quantifying the amount of information in the probability distribution produced by a particular network-outbreak combination. We illustrate the method using supply network models from Germany and demonstrate its application potential for outbreak investigations through simulated outbreak scenarios and a retrospective analysis of a real-world outbreak.

Many real world graphs have edges correlated to the distance between them, but, in an inhomogeneous manner. While the Chung-Lu model and geometric random graph models both are elegant in their simplicity, they are insufficient to capture the complexity of these networks. For instance, the Chung-Lu model captures the inhomogeneity of the nodes but does not address the geometric nature of the nodes and simple geometric models treat names homogeneously.

In this talk, we develop a generalized geometric random graph model that preserves many graph-theoretic aspects of these models. Notably, each node is assigned a weight based on its desired expected degree; nodes are then adjacent based on a function of their weight and geometric distance. We will discuss the mathematical properties of this model. We also test the validity of this model on a graphical representation of the Drosophila Medulla connectome, a natural real-world inhomogeneous graph where spatial information is known.

This is joint work with Susama Agarwala, Johns Hopkins, Applied Physics Lab.

arXiv link: https://arxiv.org/abs/2109.00061

We propose a decentralised “local2global" approach to graph representation learning, that one can a-priori use to scale any embedding technique. Our local2global approach proceeds by first dividing the input graph into overlapping subgraphs (or “patches") and training local representations for each patch independently. In a second step, we combine the local representations into a globally consistent representation by estimating the set of rigid motions that best align the local representations using information from the patch overlaps, via group synchronization.  A key distinguishing feature of local2global relative to existing work is that patches are trained independently without the need for the often costly parameter synchronisation during distributed training. This allows local2global to scale to large-scale industrial applications, where the input graph may not even fit into memory and may be stored in a distributed manner.

arXiv link: https://arxiv.org/abs/2107.12224v1

Model reduction is one of the most used tools to characterize real-world complex systems. A large realistic model is approximated by a simpler model on a smaller state space, capturing what is considered by the user as the most important features of the larger model. In this talk we will introduce a new information-theoretic criterion, called "autoinformation", that aggregates states of a Markov chain and provide a reduced model as Markovian (small memory of the past) and as predictable (small level of noise) as possible. We will discuss the connection of autoinformation to widely accepted model reduction techniques in network science such as modularity or degree-corrected stochastic block model inference. In addition to our theoretical results, we will validate such technique with didactic and real-life examples. When applied to the ocean surface currents, our technique, which is entirely data-driven, is able to identify the main global structures of the oceanic system when focusing on the appropriate time-scale of around 6 months.
arXiv link: https://arxiv.org/abs/2005.00337

“The Royal Swedish Academy of Sciences has today decided to award the 2021 Nobel Prize in Physics for ground-breaking contributions to our understanding of complex physical systems”

Last Tuesday this announcement got many in our community very excited: never before had the Nobel prize been awarded to a topic so closely related to Network Science. We will try to understand the contributions that have led to this Nobel Prize announcement and their ties with networks science. The presentation will be held by Erik Hörmann, who has been lucky enough to have had the honour and pleasure of studying and working with one of the awardees, Professor Giorgio Parisi, before joining the Mathematical Institute.