Computational and topological properties of neural networks by means of graph-theoretic parameters

Abstract

A neural network is a computer system modeled on the nerve tissue and nervous system. In this sense, neural networks refer to systems of neurons, either organic or artificial in nature. Neural networks have diverse applications in computer graphics, artificial intelligence (AI), machine & deep learning, chemistry, material science, among others. Research on structural properties and their classification of favorable or unfavorable for neural networks has been started recently. Employing tools from mathematics and specifically graph theory has been a key research direction in this area. Different graph-theoretic parameters have potential applications in studying topological properties of neural networks. In this paper for the first time, we study some nondeterministic polynomial-time (NP)-complete and NP-hard problems on various neural networks by considering their graphs. We consider classes of 3- and 4-layered probabilistic neural networks (PNNs), cellular neural networks (CNNs), and Tickysym spiking neural networks (TSNNs). In order to study their topological properties, we study their structures of maximal cliques, minimal colorings, maximal independent sets, maximal and perfect matchings, and minimum dominating sets. Computational results on the clique number, chromatic number, independence number, matching ratio and the domination number are reported. For instance, the clique number of the probabilistic neural networks is 2, the Tickysym spiking neural network is 3, whereas, for the cellular neural network, it is 4. These numerical results quantify the incoming/outgoing traffic in these architectures. Similarly, the independence number of 25-nodal 3-layered probabilistic neural network is 15, whereas, the independence number of 25-nodal cellular neural network is just 9. Moreover, the asymptotic matching ratio for PNNs (resp. CNNs) is [Formula presented] (resp. [Formula presented]), whereas, it is [Formula presented] for the case of TSNNs. This gives probabilistic neural networks a significant priority in controllability over cellular neural networks. Some open problems are proposed in the end to further this research area.