Dynamics of neural networks over undirected graphs

Area of Science:

• Computational Neuroscience
• Graph Theory
• Dynamical Systems

Background:

• Neural networks with {0,1} weights are modeled using undirected graph incidence matrices.
• Network updates can be synchronous, sequential, or block-sequential.

Purpose of the Study:

• To fully characterize the attractors (fixed points or cycles) of these neural networks.
• To establish conditions for convergence to fixed points based on graph properties.

Main Methods:

• Analysis of dynamical behavior based on graph structure (G=(V,E)).
• Characterization of attractors by examining network update schemes.
• Introduction of a parameter α(G) related to graph properties like loops, edges, vertices, and bipartiteness.

Main Results:

• Convergence to fixed points is established when α(G')<0 for all subgraphs G'.
• The presence of cycles is indicated when the condition α(G')<0 is not met.
• For specific majority functions and block-sequential updates, cycles with non-polynomial periods were observed.

Conclusions:

• The dynamical behavior of these neural networks is completely determined by their underlying graph structure.
• The parameter α(G) provides a clear criterion for predicting convergence or the emergence of cycles.
• The study highlights the complex dynamics, including long-period cycles, possible in simple network configurations.