More Like this

1. Nerve Theorems for Fixed Points of Neural Networks

   https://doi.org/10.1007/978-3-030-95519-9_6  

   Santander, D. E.; Ebli, S.; Patania, A.; Sanderson, N.; Burtscher, F.; Morrison, K.; Curto, C. (May 2022, Association for Women in Mathematics series)

   Gasparovic, E.; Robins, V.; Turner, K. (Ed.)

   Nonlinear network dynamics are notoriously difficult to understand. Here we study a class of recurrent neural networks called combinatorial threshold-linear networks (CTLNs) whose dynamics are determined by the structure of a directed graph. They are a special case of TLNs, a popular framework for modeling neural activity in computational neuroscience. In prior work, CTLNs were found to be surprisingly tractable mathematically. For small networks, the fixed points of the network dynamics can often be completely determined via a series of graph rules that can be applied directly to the underlying graph. For larger networks, it remains a challenge to understand how the global structure of the network interacts with local properties. In this work, we propose a method of covering graphs of CTLNs with a set of smaller directional graphs that reflect the local flow of activity. While directional graphs may or may not have a feedforward architecture, their fixed point structure is indicative of feedforward dynamics. The combinatorial structure of the graph cover is captured by the nerve of the cover. The nerve is a smaller, simpler graph that is more amenable to graphical analysis. We present three nerve theorems that provide strong constraints on the fixed points of the underlying network from the structure of the nerve. We then illustrate the power of these theorems with some examples. Remarkably, we find that the nerve not only constrains the fixed points of CTLNs, but also gives insight into the transient and asymptotic dynamics. This is because the flow of activity in the network tends to follow the edges of the nerve. 

   more » « less
2. Diversity of Emergent Dynamics in Competitive Threshold-Linear Networks

   https://doi.org/10.1137/22M1541666  

   Morrison, Katherine; Degeratu, Anda; Itskov, Vladimir; Curto, Carina (March 2024, SIAM Journal on Applied Dynamical Systems)

   Threshold-linear networks consist of simple units interacting in the presence of a threshold nonlinearity. Competitive threshold-linear networks have long been known to exhibit multistability, where the activity of the network settles into one of potentially many steady states. In this work, we find conditions that guarantee the absence of steady states, while maintaining bounded activity. These conditions lead us to define a combinatorial family of competitive threshold-linear networks, parametrized by a simple directed graph. By exploring this family, we discover that threshold-linear networks are capable of displaying a surprisingly rich variety of nonlinear dynamics, including limit cycles, quasi-periodic attractors, and chaos. In particular, several types of nonlinear behaviors can co-exist in the same network. Our mathematical results also enable us to engineer networks with multiple dynamic patterns. Taken together, these theoretical and computational findings suggest that threshold-linear networks may be a valuable tool for understanding the relationship between network connectivity and emergent dynamics. 

   more » « less
3. Integrability of generalised skew-symmetric replicator equations via graph embeddings

   https://doi.org/10.1088/1751-8121/ad996e  

   Visomirski, Matthew; Griffin, Christopher (December 2024, Journal of Physics A: Mathematical and Theoretical)

   Abstract It is known that there is a one-to-one mapping between oriented directed graphs and zero-sum replicator dynamics (Lotka–Volterra equations) and that furthermore these dynamics are Hamiltonian in an appropriately defined nonlinear Poisson bracket. In this paper, we investigate the problem of determining whether these dynamics are Liouville–Arnold integrable, building on prior work in graph decloning by Evripidouet al(2022J. Phys. A: Math. Theor.55325201) and graph embedding by Paik and Griffin (2024Phys. Rev.E107L052202). Using the embedding procedure from Paik and Griffin, we show (with certain caveats) that when a graph producing integrable dynamics is embedded in another graph producing integrable dynamics, the resulting graph structure also produces integrable dynamics. We also construct a new family of graph structures that produces integrable dynamics that does not arise either from embeddings or decloning. We use these results, along with numerical methods, to classify the dynamics generated by almost all oriented directed graphs on six vertices, with three hold-out graphs that generate integrable dynamics and are not part of a natural taxonomy arising from known families and graph operations. These hold-out graphs suggest more structure is available to be found. Moreover, the work suggests that oriented directed graphs leading to integrable dynamics may be classifiable in an analogous way to the classification of finite simple groups, creating the possibility that there is a deep connection between integrable dynamics and combinatorial structures in graphs. 

   more » « less
4. On the Role of Interconnection Directionality in the Quadratic Performance of Double-Integrator Networks

   https://doi.org/10.1109/TAC.2021.3135358  

   Oral, Hasan Giray; Mallada, Enrique; Gayme, Dennice (December 2021, IEEE Transactions on Automatic Control)

   This paper provides a framework to evaluate the performance of single and double integrator networks over arbitrary directed graphs. Adopting vehicular network terminology, we consider quadratic performance metrics defined by the L2-norm of position and velocity based response functions given impulsive inputs to each vehicle. We exploit the spectral properties of weighted graph Laplacians and output performance matrices to derive a novel method of computing the closed-form solutions for this general class of performance metrics, which include H2-norm based quantities as special cases. We then explore the effect of the interplay between network properties (such as edge directionality and connectivity) and the control strategy on the overall network performance. More precisely, for systems whose interconnection is described by graphs with normal Laplacian L, we characterize the role of directionality by comparing their performance with that of their undirected counterparts, represented by the Hermitian part of L. We show that, for single-integrator networks, directed and undirected graphs perform identically. However, for double-integrator networks, graph directionality -expressed by the eigenvalues of L with nonzero imaginary part- can significantly degrade performance. Interestingly, in many cases, well-designed feedback can also exploit directionality to mitigate degradation or even improve the performance to exceed that of the undirected case. Finally we focus on a system coherence metric -aggregate deviation from the state average- to investigate the relationship between performance and degree of connectivity, leading to somewhat surprising findings. For example, increasing the number of neighbors on a ω-nearest neighbor directed graph does not necessarily improve performance. Similarly, we demonstrate equivalence in performance between all-to-one and all-to-all communication graphs. 

   more » « less
5. DYREP: Learning Representations Over Dynamic Graphs

   Trivedi, Rakshit; Farajtabar, Mehrdad; Biswal, Prasenjeet; Zha, Hongyuan (January 2019, International Conference on Learning Representation)

   Representation Learning over graph structured data has received significant attention recently due to its ubiquitous applicability. However, most advancements have been made in static graph settings while efforts for jointly learning dynamic of the graph and dynamic on the graph are still in an infant stage. Two fundamental questions arise in learning over dynamic graphs: (i) How to elegantly model dynamical processes over graphs? (ii) How to leverage such a model to effectively encode evolving graph information into low-dimensional representations? We present DyRep - a novel modeling framework for dynamic graphs that posits representation learning as a latent mediation process bridging two observed processes namely – dynamics of the network (realized as topological evolution) and dynamics on the network (realized as activities between nodes). Concretely, we propose a two-time scale deep temporal point process model that captures the interleaved dynamics of the observed processes. This model is further parameterized by a temporal-attentive representation network that encodes temporally evolving structural information into node representations which in turn drives the nonlinear evolution of the observed graph dynamics. Our unified framework is trained using an efficient unsupervised procedure and has capability to generalize over unseen nodes. We demonstrate that DyRep outperforms state-of-the-art baselines for dynamic link prediction and time prediction tasks and present extensive qualitative insights into our framework. 

   more » « less