Dynamics of neural networks over undirected graphs
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 , i.e., the matrix’s entries, , are 0’s or 1’s according to whether the edge . 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, , such that the parallel updating scheme converges to fixed points if and only if for any subgraph of . 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 such that 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 , 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 .
Section snippets
Background
Let us consider an integer symmetric matrix , a threshold vector and the set of Heaviside functions: where Since the entries are integers, it is always possible to determine equivalent functions with thresholds , such that . We associate a dynamic to the previous functions by considering a partition of the set such that the nodes of the
Convergence to fixed points for undirected graphs
In this section we will study the convergence for neural networks defined by the incidence matrix of graphs (0’s and 1’s entries). Since we have to study each block (so, its incidence matrix) of the partition, we will first establish conditions and results for only one block, i.e., the network updated synchronously. After that, we will apply the results obtained for one block to every partition in the whole block-sequential updating scheme. In fact, given a incidence matrix of an undirected
Non-polynomial cycles associated to block-sequential updating
Contrary to the usual intuition (supported by simulations), in these networks the limit cycles, if they exist, have small periods for any updating scheme, in fact, there are even conjectures that the periods have length at most two (Mortveit, 2012). We will show evidence that supports the opposite, i.e., large cycles can appear. In this section we will prove that when the conditions on the partitions and the associated graph, presented in the previous section, do not hold, very large cycles
Illustrative example of different updating schemes, energy, and convergence
We present an example where the relation of the energy operator with our theorems and is illustrated. Let us consider the staircase of Fig. 9, with the majority function over each node as described in the previous section, and the initial configuration This initial configuration evaluated in (2) gives . Let us consider first the parallel update, in that case we have , then by Theorem 3.1 we have that cycles of period 2 appear. In fact,
Discussions and conclusions
In this paper we have studied the relationship between attractors (cycles or fixed points) of neural networks defined over an undirected finite graph (i.e., the entries of the interconnection matrix are 0’s and 1’s) and some characteristics of the graph like loops and circuits. From our study it can be deduced that the number of nodes, edges, loops and odd circuits are the relevant parameters in order to characterize the attractors. For the parallel dynamics we know from Goles and Olivos (1980)
Acknowledgments
The authors would like to thank Conicyt-Chile under grant Fondecyt 1140090 (E.G.), ECOS C12E05 (E.G.), Fondecyt 11110088 (G.A.R.), and Basal(Conicyt)-CMM for financially supporting this research.
References (35)
- et al.
On the robustness of update schedules in Boolean networks
BioSystems
(2009) - et al.
On the equivalence of Hopfield networks and Boltzmann machines
Neural Networks
(2012) - et al.
Discrete state neural networks and energies
Neural Networks
(1997) - et al.
The complexity of the bootstraping percolation and other problems
Theoretical Computer Science
(2013) - et al.
Disjunctive networks and update schedules
Advances in Applied Mathematics
(2012) - et al.
Periodic behavior of generalized threshold functions
Discrete Mathematics
(1980) - et al.
Decreasing energy functions as a tool for studying threshold networks
Discrete Applied Mathematics
(1985) - et al.
No polynomial bound for the period of the parallel chip firing game on graphs
Theoretical Computer Science
(1994) - et al.
A Hopfield neural network for combining classifiers applied to textured images
Neural Networks
(2010) - et al.
Dynamical and topological robustness of the mammalian cell cycle network: a reverse engineering approach
BioSystems
(2014)
Balancing robustness against the dangers of multiple attractors in a Hopfield-type model of biological attractors
PLoS One
Positive and negative circuits in discrete neural networks
IEEE Transactions on Neural Networks
On the computational complexity of ising spin glass models
Journal of Physics A
Boolean network models of cellular regulation: prospects and limitations
Journal of the Royal Society Interface
Statistical physics of social dynamics
Physical Review Letters
Boolean network model predicts cell cycle sequence of fission yeast
PLoS One
Computers and intractability: a guide to the theory of NP-completeness
Cited by (6)
Closeness centrality in neural and interconnection networks
2020, Journal of Combinatorial Mathematics and Combinatorial ComputingGradient and Hamiltonian coupled systems on undirected networks
2019, Mathematical Biosciences and EngineeringObservability of Automata Networks: Fixed and Switching Cases
2018, IEEE Transactions on Neural Networks and Learning Systems
- 1
Present address: Office 313, E Building, Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez, Av. Diagonal Las Torres 2640, Santiago, Chile. Tel.: +56 223311264.