Search

A central question in deep learning is how deep neural networks (DNNs) learn features. DNN layers progressively collapse data into a regular low-dimensional geometry. This collective effect of non-linearity, noise, learning rate, width, depth, and numerous other parameters, has eluded first-principles theories which are built from microscopic neuronal dynamics. Here we present a noise-non-linearity phase diagram that highlights where shallow or deep layers learn features more effectively. We then propose a macroscopic mechanical theory of feature learning that accurately reproduces this phase diagram, offering a clear intuition for why and how some DNNs are ``lazy'' and some are ``active'', and relating the distribution of feature learning over layers with test accuracy.

Brain-computer interfaces surged extraordinary developments in recent years, and a significant discrepancy now exists between the abundance of available data and the limited headway made in achieving a unified theoretical framework. This discrepancy becomes particularly pronounced when examining the collective neural activity at the micro- and meso-scale, where a coherent formalization that adequately describes neural interactions is still lacking. Here, we introduce a mathematical framework to analyze systems of natural neurons and interpret the related empirical observations in terms of lattice field theory, an established paradigm from theoretical particle physics and statistical mechanics. Our methods are tailored to interpret data from chronic neural interfaces, especially spike rasters from measurements of single neurons activity, and generalize the maximum entropy model for neural networks so that also the time evolution of the system is taken into account. This is obtained by bridging particle physics and neuroscience, paving the way to particle physics-inspired models of neocortex., Comment: 79 pages, 20 figures

Relational inference aims to identify interactions between parts of a dynamical system from the observed dynamics. Current state-of-the-art methods fit the dynamics with a graph neural network (GNN) on a learnable graph. They use one-step message-passing GNNs -- intuitively the right choice since non-locality of multi-step or spectral GNNs may confuse direct and indirect interactions. But the \textit{effective} interaction graph depends on the sampling rate and it is rarely localized to direct neighbors, leading to poor local optima for the one-step model. In this work, we propose a \textit{graph dynamics prior} (GDP) for relational inference. GDP constructively uses error amplification in non-local polynomial filters to steer the solution to the ground-truth graph. To deal with non-uniqueness, GDP simultaneously fits a ``shallow'' one-step model and a polynomial multi-step model with shared graph topology. Experiments show that GDP reconstructs graphs far more accurately than earlier methods, with remarkable robustness to under-sampling. Since appropriate sampling rates for unknown dynamical systems are not known a priori, this robustness makes GDP suitable for real applications in scientific machine learning. Reproducible code is available at https://github.com/DaDaCheng/GDP.

Graph neural networks (GNNs) excel in modeling relational data such as biological, social, and transportation networks, but the underpinnings of their success are not well understood. Traditional complexity measures from statistical learning theory fail to account for observed phenomena like the double descent or the impact of relational semantics on generalization error. Motivated by experimental observations of ``transductive'' double descent in key networks and datasets, we use analytical tools from statistical physics and random matrix theory to precisely characterize generalization in simple graph convolution networks on the contextual stochastic block model. Our results illuminate the nuances of learning on homophilic versus heterophilic data and predict double descent whose existence in GNNs has been questioned by recent work. We show how risk is shaped by the interplay between the graph noise, feature noise, and the number of training labels. Our findings apply beyond stylized models, capturing qualitative trends in real-world GNNs and datasets. As a case in point, we use our analytic insights to improve performance of state-of-the-art graph convolution networks on heterophilic datasets.

Previous studies show that recommendation algorithms based on historical behaviors of users can provide satisfactory recommendation performance. Many of these algorithms pay attention to the interest of users, while ignore the influence of social relationships on user behaviors. Social relationships not only carry intrinsic information of similar consumption tastes or behaviors, but also imply the influence of individual to its neighbors. In this paper, we assume that social relationships and historical behaviors of users are related to the same factors. Based on this assumption, we propose an algorithm to focus on social relationships useful for recommendation systems through mutual constraints from both types of information. We test the performance of our algorithm on four types of users, including all users, active users, inactive users and cold-start users. Results show that the proposed algorithm outperforms benchmarks in four types of scenarios subject to recommendation accuracy and diversity metrics. We further design a randomization model to explore the contribution of social relationships to recommendation performance, and the result shows that the contribution of social relationships in the proposed algorithm depends on the coupling strength of social relationships and historical behaviors., Comment: 28 pages, 7 figures

Fundamental laws of human mobility have been extensively studied, yet we are still lacking a comprehensive understanding of the mobility patterns of sharing conveyances. Since travellers would highly probably no longer possess their own conveyances in the near future, the interplay between travellers and sharing bikes is a central question for developing more sustainable transportation. Dockless bike-sharing systems that record detailed information of every trip provide us a unique opportunity for revealing the hidden patterns behind riding activities. By treating each bike as an individual entity, we reveal that distributions of mobility indicators of bikes are quite different from humans; and mobility patterns are even inconsistent across cities. All above discrepancies can be well explained by a choice model that is characterized by a universal scaling. Our model unveils that instead of choosing among the newest bikes, the distribution of rank values of selected bikes on usage condition manifests a truncated power-law and is quite stable across several cities despite various diversities. Our framework would have broad implications in sharing economy and contribute towards developing a greener, healthier, and more sustainable future city.

Graph neural networks achieve high accuracy in link prediction by jointly leveraging graph topology and node attributes. Topology, however, is represented indirectly; state-of-the-art methods based on subgraph classification label nodes with distance to the target link, so that, although topological information is present, it is tempered by pooling. This makes it challenging to leverage features like loops and motifs associated with network formation mechanisms. We propose a link prediction algorithm based on a new pooling scheme called WalkPool. WalkPool combines the expressivity of topological heuristics with the feature-learning ability of neural networks. It summarizes a putative link by random walk probabilities of adjacent paths. Instead of extracting transition probabilities from the original graph, it computes the transition matrix of a "predictive" latent graph by applying attention to learned features; this may be interpreted as feature-sensitive topology fingerprinting. WalkPool can leverage unsupervised node features or be combined with GNNs and trained end-to-end. It outperforms state-of-the-art methods on all common link prediction benchmarks, both homophilic and heterophilic, with and without node attributes. Applying WalkPool to a set of unsupervised GNNs significantly improves prediction accuracy, suggesting that it may be used as a general-purpose graph pooling scheme.

Interactions in biology and social systems are not restricted to pairwise but can take arbitrary sizes. Extensive studies have revealed that the arbitrary-sized interactions significantly affect the spreading dynamics on networked systems. Competing spreading dynamics, i.e., several epidemics spread simultaneously and compete with each other, have been widely observed in the real world, yet the way arbitrary-sized interactions affect competing spreading dynamics still lacks systematic study. This study presents a model of two competing simplicial susceptible-infected-susceptible epidemics on a higher-order system represented by simplicial complex and analyzes the model's critical phenomena. In the proposed model, a susceptible node can only be infected by one of the two epidemics, and the transmission of infection to neighbors can occur through pairwise (i.e., an edge) and high-order (e.g., 2-simplex) interactions simultaneously. Through a mean-field (MF) theory analysis and numerical simulations, we show that the model displays rich dynamical behavior depending on the 2-simplex infection strength. When the 2-simplex infection strength is weak, the model's phase diagram is consistent with the simple graph, consisting of three regions: the absolute dominant regions for each epidemic and the epidemic-free region. With the increase of the 2-simplex infection strength, a new phase region called the alternative dominant region emerges. In this region, the survival of one epidemic depends on the initial conditions. Our theoretical analysis can reasonably predict the time evolution and steady-state outbreak size in each region. In addition, we further explore the model's phase diagram both when the 2-simplex infection strength is symmetrical and asymmetrical. The results show that the 2-simplex infection strength has a significant impact on the system phase diagram., Comment: 12 pages, 7 figures

While links in simple networks describe pairwise interactions between nodes, it is necessary to incorporate hypernetworks for modeling complex systems with arbitrary-sized interactions. In this study, we focus on the hyperlink prediction problem in hypernetworks, for which the current state-of-art methods are latent-feature-based. A practical algorithm via topological features, which can provide understandings of the organizational principles of hypernetworks, is still lacking. For simple networks, local clustering or loop reflects the correlations among nodes; therefore, loop-based link prediction algorithms have achieved accurate performance. Extending the idea to hyperlink prediction faces several challenges. For instance, what is an effective way of defining loops for prediction is not clear yet; besides, directly comparing topological statistics of variable-sized hyperlinks could introduce biases in hyperlink cardinality. In this study, we address the issues and propose a loop-based hyperlink prediction approach. First, we discuss and define the loops in hypernetworks; then, we transfer the loop-features into a hyperlink prediction algorithm via a simple modified logistic regression. Numerical experiments on multiple real-world datasets demonstrate superior performance compared to the state-of-the-art methods.

The inverse problem of finding the optimal network structure for a specific type of dynamical process stands out as one of the most challenging problems in network science. Focusing on the susceptible-infected-susceptible type of dynamics on annealed networks whose structures are fully characterized by the degree distribution, we develop an analytic framework to solve the inverse problem. We find that, for relatively low or high infection rates, the optimal degree distribution is unique, which consists of no more than two distinct nodal degrees. For intermediate infection rates, the optimal degree distribution is multitudinous and can have a broader support. We also find that, in general, the heterogeneity of the optimal networks decreases with the infection rate. A surprising phenomenon is the existence of a specific value of the infection rate for which any degree distribution would be optimal in generating maximum spreading prevalence. The analytic framework and the findings provide insights into the interplay between network structure and dynamical processes with practical implications.

Identifying the most influential spreaders is important to understand and control the spreading process in a network. As many real-world complex systems can be modeled as multilayer networks, the question of identifying important nodes in multilayer network has attracted much attention. Existing studies focus on the multilayer network structure, while neglecting how the structural and dynamical coupling of multiple layers influence the dynamical importance of nodes in the network. Here we investigate on this question in an information-disease coupled spreading dynamics on multiplex networks. Firstly, we explicitly reveal that three interlayer coupling factors, which are the two-layer relative spreading speed, the interlayer coupling strength and the two-layer degree correlation, significantly impact the spreading influence of a node on the contact layer. The suppression effect from the information layer makes the structural centrality on the contact layer fail to predict the spreading influence of nodes in the multiplex network. Then by mapping the coevolving spreading dynamics into percolation process and using the message-passing approach, we propose a method to calculate the size of the disease outbreaks from a single seed node, which can be used to estimate the nodes' spreading influence in the coevolving dynamics. Our work provides insights on the importance of nodes in the multiplex network and gives a feasible framework to investigate influential spreaders in the asymmetrically coevolving dynamics., Comment: multiplex network, influential spreader, asymmetrically interacting dynamics, centrality measure

Promoting some typical spreading dynamics, for instance, the spreading of information, commercial message, vaccination guidance, innovation, and political movement, can bring benefits to all aspects of the socio-economic systems. In this study, we propose a strategy for promoting the spreading of the susceptible-infected-recovered model, which is widely applied to describe these common spreading dynamics in real life. Specifically, we first quantify the potential influence that the addition of each latent edge (that is, edges that do not exist before) could cause to the spreading dynamics. Then, we strategically add the latent edges to the original networks according to the potential influence of each latent edge. Numerical simulations verify the effectiveness of our strategy and demonstrate that our strategy outperforms several static strategies, namely, adding the latent edges between nodes with the largest degree or eigenvector centrality. This study provides an effective way of promoting the spreading of the susceptible-infected-recovered model by modifying the network structure slightly and helps in understanding what a better network structure for the spreading dynamics is. Besides, the theoretical framework established in this study provides inspirations for the further investigations of edge-based promoting strategies for other spreading models.

Numerous real-world systems, for instance, the communication platforms and transportation systems, can be abstracted into complex networks. Containing spreading dynamics (e.g., epidemic transmission and misinformation propagation) in networked systems is a hot topic in multiple fronts. Most of the previous strategies are based on the immunization of nodes. However, sometimes, these node--based strategies can be impractical. For instance, in the train transportation networks, it is dramatic to isolating train stations for flu prevention. On the contrary, temporarily suspending some connections between stations is more acceptable. Thus, we pay attention to the edge-based containing strategy. In this study, we develop a theoretical framework to find the optimal edge for containing the spreading of the susceptible-infected-susceptible model on complex networks. In specific, by performing a perturbation method to the discrete-Markovian-chain equations of the SIS model, we derive a formula that approximately provides the decremental outbreak size after the deactivation of a certain edge in the network. Then, we determine the optimal edge by simply choosing the one with the largest decremental outbreak size. Note that our proposed theoretical framework incorporates the information of both network structure and spreading dynamics. Finally, we test the performance of our method by extensive numerical simulations. Results demonstrate that our strategy always outperforms other strategies based only on structural properties (degree or edge betweenness centrality). The theoretical framework in this study can be extended to other spreading models and offers inspirations for further investigations on edge-based immunization strategies.

Epidemic spreading processes in the real world can interact with each other in a cooperative, competitive, or asymmetric way, requiring a description based on coevolution dynamics. Rich phenomena such as discontinuous outbreak transitions and hystereses can arise, but a full picture of these behaviors in the parameter space is lacking. We develop a theory for interacting spreading dynamics on complex networks through spectral dimension reduction. In particular, we derive from the microscopic quenched mean-field equations a two-dimensional system in terms of the macroscopic variables, which enables a full phase diagram to be determined analytically. The diagram predicts critical phenomena that were known previously but only numerically, such as the interplay between discontinuous transition and hysteresis as well as the emergence and role of tricritical points., Comment: 17 pages, 9 figures

Rumors flooding on rapidly-growing online social networks has geared much attention from many fronts. Individuals can transmit rumors via numerous channels since they can be active on multiple platforms. However, no systematic theoretical research of rumors containing dynamics on multiplex networks has been conducted yet. In this study, we propose a family of containing strategies based on the degree product $\mathcal{K}$ of each user on the multiplex networks. Then, we develop a heterogeneous edge-based compartmental theory to comprehend the containing dynamics. The simulation results demonstrate that strategies with preference to block users with large $\mathcal{K}$ can significantly reduce the rumor outbreak size and enlarge the threshold. Besides, better performance can be expected on heterogeneous multiplex networks with the increasing of preference intensity and degree heterogeneity. Moreover, take the inter-layer degree correlations $r_s$ into consideration, the strategy performs best on multiplex networks with $r_s=-1$, $r_s=1$ the second, and $r_s=0$ the last. On the contrary, if we prefer to block users with small $\mathcal{K}$ rather than large $\mathcal{K}$, the containing performance will be worse than that of blocking users randomly on most multiplex networks except for uncorrelated multiplex networks with uniform degree distribution. We found that the blocking preferences have no influence on the containing results on uncorrelated multiplex networks with uniform degree distribution. Our theoretical analysis can well predict the rumors containing results and performance differences in all the cases studied. The systematic theoretical research of rumors containing dynamics on multiplex networks in this study will offer inspirations for further investigations on this issue.

The numerous expanding online social networks offer fast channels for misinformation spreading, which could have a serious impact on socioeconomic systems. Researchers across multiple areas have paid attention to this issue with a view of addressing it. However, no systematical theoretical study has been performed to date on observing misinformation spreading on correlated multiplex networks. In this study, we propose a multiplex network-based misinformation spreading model, considering the fact that each individual can obtain misinformation from multiple platforms. Subsequently, we develop a heterogeneous edge-base compartmental theory to comprehend the spreading dynamics of our proposed model. In addition, we establish an analytical method based on stability analysis to obtain the misinformation outbreak threshold. On the basis of these theories, we finally analyze the influence of different dynamical and structural parameters on the misinformation spreading dynamics. Results show that the misinformation outbreak size $R(\infty)$ grows continuously with the effective transmission probability $\beta$ once $\beta$ exceeds a certain value, that is, the outbreak threshold $\beta_c$. A large average degrees, strong degree heterogeneity, or positive inter-layer correlation will reduce $\beta_c$, accelerating the outbreak of misinformation. Besides, increasing the degree heterogeneity or a more positive inter-layer correlation will both enlarge (reduce) $R(\infty)$ for small (large) values of $\beta$. Our systematic theoretical analysis results agree well with the numerical simulation results. Our proposed model and accurate theoretical analysis will serve as a useful framework to understand and predict the spreading dynamics of misinformation on multiplex networks, and thereby pave the way to address this serious issue.

Adding edges between layers of interconnected networks is an important way to optimize the spreading dynamics. While previous studies mostly focus on the case of adding a single edge, the theoretical optimal strategy for adding multiple edges still need to be studied. In this study, based on the susceptible-infected-susceptible (SIS) model, we investigate the problem of maximizing the stationary spreading prevalence in interconnected networks. For two isolated networks, we maximize the spreading prevalence near the critical point by choosing multiple interconnecting edges. We present a theoretical analysis based on the discrete-time Markov chain approach to derive the approximate optimal strategy. The optimal inter-layer structure predicted by the strategy maximizes the spreading prevalence, meanwhile minimizes the spreading outbreak threshold for the interconnected network simultaneously. Numerical simulations on synthetic and real-world networks show that near the critical point, the proposed strategy gives better performance than connecting large degree nodes and randomly connecting., Comment: 9 pages, 4 figures

Real-world systems, ranging from social and biological to infrastructural, can be modeled by multilayer networks. Promoting spreading dynamics in multilayer networks may significantly facilitate electronic advertising and predicting popular scientific publications. In this study, we propose a strategy for promoting the spreading dynamics of the susceptible-infected-susceptible model by adding one interconnecting edge between two isolated networks. By applying a perturbation method to the discrete Markovian chain approach, we derive an index that estimates the spreading prevalence in the interconnected network. The index can be interpreted as a variant of Katz centrality, where the adjacency matrix is replaced by a weighted matrix with weights depending on the dynamical information of the spreading process. Edges that are less infected at one end and its neighborhood but highly infected at the other will have larger weights. We verify the effectiveness of the proposed strategy on small networks by exhaustively examining all latent edges and demonstrate that performance is optimal or near-optimal. For large synthetic and real-world networks, the proposed method always outperforms other static strategies such as connecting nodes with the highest degree or eigenvector centrality., Comment: Physical Review E, In Press, 11 pages, 5 figures

In this paper we study the bipartite version of Sherrington-Kirkpatrick model. We prove that the free energy density is given by an analogue of the Parisi formula, that contains both the usual overlap and an additional new type of overlap. Following Panchenko, we prove the upper bound of the formula by Guerra's replica symmetry breaking interpolation, then the matching lower bound by Ghirlanda-Guerra identities and the Aizenman-Sims-Starr scheme. Based on this result we study the stability of the replica symmetric solution. A new phase exhibiting partial replica symmetry breaking is observed, where the broken phase is realized in the larger group only., Comment: We retired the paper after finding a major technical issue. In particular, the proposed partially RSB-broken scenario only represent a lower bound for the free energy and not a tight approximation

Inspired by practical importance of social networks, economic networks, biological networks and so on, studies on large and complex networks have attracted a surge of attentions in the recent years. Link prediction is a fundamental issue to understand the mechanisms by which new links are added to the networks. We introduce the method of robust principal component analysis (robust PCA) into link prediction, and estimate the missing entries of the adjacency matrix. On one hand, our algorithm is based on the sparsity and low rank property of the matrix, on the other hand, it also performs very well when the network is dense. This is because a relatively dense real network is also sparse in comparison to the complete graph. According to extensive experiments on real networks from disparate fields, when the target network is connected and sufficiently dense, whatever it is weighted or unweighted, our method is demonstrated to be very effective and with prediction accuracy being considerably improved comparing with many state-of-the-art algorithms.

Using network-based information to facilitate information spreading is an essential task for spreading dynamics in complex networks, which will benefit the promotion of technical innovations, healthy behaviors, new products, etc. Focusing on degree correlated networks, we propose a preferential contact strategy based on the local network structure and local informed density to promote the information spreading. During the spreading process, an informed node will preferentially select a contact target among its neighbors, basing on their degrees or local informed densities. By extensively implementing numerical simulations in synthetic and empirical networks, we find that when only consider the local structure information, the convergence time of information spreading will be remarkably reduced if low-degree neighbors are favored as contact targets. Meanwhile, the minimum convergence time depends non-monotonically on degree-degree correlation, and moderate correlation coefficients result in most efficient information spreading. Incorporating the informed density information into contact strategy, the convergence time of information spreading can be further reduced. Finally, we show that by using local informed density is more effective as compared with the global case., Comment: 14 pages, 10 figures

The degree-degree correlation is important in understanding the structural organization of a network and the dynamics upon a network. Such correlation is usually measured by the assortativity coefficient $r$, with natural bounds $r \in [-1,1]$. For scale-free networks with power-law degree distribution $p(k) \sim k^{-\gamma}$, we analytically obtain the lower bound of assortativity coefficient in the limit of large network size, which is not -1 but dependent on the power-law exponent $\gamma$. This work challenges the validation of assortativity coefficient in heterogeneous networks, suggesting that one cannot judge whether a network is positively or negatively correlated just by looking at its assortativity coefficient., Comment: 9 pages, 5 figures and 1 Table

Recently, Press and Dyson have proposed a new class of probabilistic and conditional strategies for the two-player iterated Prisoner's Dilemma, so-called zero-determinant strategies. A player adopting zero-determinant strategies is able to pin the expected payoff of the opponents or to enforce a linear relationship between his own payoff and the opponents' payoff, in a unilateral way. This paper considers zero-determinant strategies in the iterated public goods game, a representative multi-player evolutionary game where in each round each player will choose whether or not put his tokens into a public pot, and the tokens in this pot are multiplied by a factor larger than one and then evenly divided among all players. The analytical and numerical results exhibit a similar yet different scenario to the case of two-player games: (i) with small number of players or a small multiplication factor, a player is able to unilaterally pin the expected total payoff of all other players; (ii) a player is able to set the ratio between his payoff and the total payoff of all other players, but this ratio is limited by an upper bound if the multiplication factor exceeds a threshold that depends on the number of players., Comment: 10 pages, 6 figures