Dynamics of neural networks over undirected graphs

Abstract

In this paper we study the dynamical behavior of neural networks such that their interconnections are the incidence matrix of an undirected finite graph $G=(V,E)$ (i.e., the weights belong to $\{0,1\}$). The network may be updated synchronously (every node is updated at the same time), sequentially (nodes are updated one by one in a prescribed order) or in a block-sequential way (a mixture of the previous schemes). We characterize completely the attractors (fixed points or cycles). More precisely, we establish the convergence to fixed points related to a parameter $\alpha \left(G\right)$, taking into account the number of loops, edges, vertices as well as the minimum number of edges to remove from $E$ in order to obtain a maximum bipartite graph. Roughly, $\alpha \left(G^{\prime }\right)<0$ for any $G^{\prime }$ subgraph of $G$ implies the convergence to fixed points. Otherwise, cycles appear. Actually, for very simple networks (majority functions updated in a block-sequential scheme such that each block is of minimum cardinality two) we exhibit cycles with non-polynomial periods.

Introduction

Symmetric neural networks were first studied in the context of the majority functions and generalizations in Goles and Olivos (1980) as well as the application to associative memories in Hopfield (1982). The network’s dynamics on undirected graphs have been widely studied to model situations in physics, biology, sociology, as we will review later on. This model has been included as an important case of neural networks for associative memories (Hopfield networks), percolation problems, infection, segregation, and other social problems, therefore, there exists now a vast community interested both in theoretical results as well as applications of symmetric neural networks.

The principal updating modes considered in these networks are the parallel, the asynchronous, and the sequential one. For the parallel updating scheme it was proved that any symmetric neural network converges only to fixed points or two cycles (Goles & Olivos, 1980). The fixed point convergence for symmetric networks, with non negative loops, updated sequentially was proved in Goles (1982). The unique general result about arbitrary block-sequential updates was established in Goles-Chacc, Fogelman-Soulie, and Pellegrin (1985). Convergence results and generalizations can be seen in Goles and Martínez (1990), where the class of Heaviside functions is extended to the positive or cyclically-monotone functions. A general approach of an energy operator for this kind of networks can be seen in Goles (2003) and Goles and Martínez (1990). Further, in Cosnard and Goles (1997) a characterization of networks which admits an energy operator is done (roughly speaking energy operators are associated to quasi-symmetric matrices). The first studies related to different updating schemes appeared in the context of Boolean networks for the parallel and sequential updating schemes (Robert, 1986). More recently, such studies have been developed in Aracena, Goles, Moreira, and Salinas (2009) and Montalva (2011) where equivalent dynamics classes were established for different block-sequential updating schemes over Boolean networks. In Noual (2012) some theoretical results as well as biological considerations related with different updating schemes were developed. More recently, networks driven by Heaviside local functions have been used in statistical physics and social dynamics, like voter models (Castellano, Fortunato, & Loretto, 2009) and the Schelling’s segregation dynamics (Goles-Domic, Goles, & Rica, 2011). In biology, applications have been developed in the framework of regulatory networks. In this context, a general overview about the application of Boolean networks can be seen in Bornholdt (2008). More concerned with this paper, Heaviside functions have been used to model the yeast cell cycle (Davidich and Bornholdt, 2008, Li et al., 2004). From these works we characterized the network’s dynamics under every deterministic updating scheme (Goles, Montalva, & Ruz, 2013). In a similar way, the complete deterministic dynamic for the mammalian cell cycle network has been analyzed in Ruz, Goles, Montalva, and Fogel (2014). Further, for the specific threshold class of disjunctive networks, the dynamical behavior was characterized for arbitrary directed graphs (non necessarily symmetric) and defined complexity classes related with the obtained attractors (fixed points or cycles) (Goles & Noual, 2012). The relationship between the positive and negative circuits of the connection graph and the fixed points of discrete neural networks is studied in Aracena, Demongeot, and Goles (2004), obtaining necessary and sufficient conditions for the existence of fixed points in discrete neural networks. Recently, it has been studied and characterized some decision problems related with whether or not an arbitrary vertex of a network may change its state (from 0 to 1) for the majority networks (a particular case of a Heaviside function) under different updates (Goles and Montealegre-Barba, in press-a, Goles, Montealegre-Barba et al., 2013). In relation to applications using Hopfield networks, Maetschke and Ragan (2014) constructed Hopfield networks from cancer expression data and then used them to show that the resulting attractors correspond to cancer subtypes. The effect of removing the links of fully connected Hopfield networks and then analyzing the convergence to a designated attractor is presented in Anafi and Bates (2010). The results from that study were used to speculate about human diseases and how they may represent biological networks that converge to an abnormal attractor. In the context of machine learning, it has been shown that restricted Boltzmann machines, typically for classification and feature detection, are thermodynamically equivalent to a Hopfield network (Barra, Bernacchia, Santucci, & Contucci, 2012). A Hopfield neural network in Pajares, Guijarro, and Ribeiro (2010) is used to combine simple classifiers for classifying natural textures in images.

In this work we focus on networks such that their interconnections correspond to the incidence matrix of a finite undirected graph $G=(V,E)$, i.e., the matrix’s entries, $w_{ij}$, are 0’s or 1’s according to whether the edge $(j,i)\in E$. In this context, we characterize completely, for any updating scheme, the attractors of such networks.

The paper is organized as follows. Section  2 gives some definitions as well as theorems that will be useful throughout the paper. In Section  3 we introduce a parameter depending on the graph structure, $\alpha \left(G\right)$, such that the parallel updating scheme converges to fixed points if and only if $\alpha \left(G^{\prime }\right)<0$ for any subgraph $G^{\prime }$ of $G$. Otherwise, cycles appear. In particular we prove that it is enough to have in the graph two connected vertices without loops in order to find a subgraph $G^{\prime }$ such that $\alpha \left(G^{\prime }\right)\ge 0$ or, equivalently to have a two-cycle. Further, we characterize completely the attractor’s behavior for some classes of graphs like, forest, trees, bipartite and complete graphs with or without loops. We extend the previous result to any updating scheme over the network by considering for the analysis the subgraphs associated to each partition of the updating scheme. In this context we get as corollaries some convergence results for block-sequential updating schemes, taking into account the cardinality of each block. Roughly, by assuming $\mathrm{diag}\left(G\right)=\overrightarrow{1}$, we conclude that for partitions of size 3 the dynamics converge to fixed points. We also obtain a slightly similar convergence result by considering also partitions of size 4 and 5, where some specific subgraphs are forbidden.

In Section  4 we proved that there exist very simple block-sequential schemes (every partition composed of two connected vertices without loops) under majority local functions such that cycles with non-polynomial periods appear. The same construction allows to establish a similar non-polynomial behavior for the transient time. Comments on the range of the energy operator and how it relates to directed graphs as well as an example that illustrates the theorems developed in this paper are presented in Section  5. Finally, in Section  6, we present the general conclusions as well as some comments related to the complexity of the computation of the parameter $\alpha \left(G\right)$.