NEURAL NETWORK ARCHITECTURE BASED ON GRAPH CODES

Abstract

One of the important achievements of the theory of error-correcting coding is the discovery of graph codes and their important subset - low-density parity check codes (LDPC codes). Using the parity check matrix of the code on the graph, one can obtain a Markov random field. LDPC code can be embedded in an Ising model (a type of Markov random field) by using a torus topology with negative curvature. In this case, codewords correspond to saddle points (extrema) in the model, and trappin sets correspond to local minima. The use of LDPC codes with an increased code distance allows for maximum separation of saddle points, and thus increases the noise resistance of the neural network and the representation power. At the same time, the block and sparse structure, characteristic of a torus of negative curvature, simplifies multiplexing and reduces the number of trainable parameters of the neural network. The aim of the research is to reduce the computational complexity and increase the accuracy of neural networks through the use of a priori structural (quasi-cyclic) sparse graphs for a wide class of machine learning problems on Markov random fields. The paper presents a new approach that allows the synthesis of neural network architectures based on graph codes. The proposed approach provides an effective representation of Markov random fields through the use of QC-LDPC matrices and tensors. The proposed approach allows us to reduce the number of trainable parameters and logarithmically reduce the complexity of tensor multiplexing. The proposed approach provided an accuracy of 94.95% (1.72% to first place) of the binary classification problem “Pathfinder” of the “Long Range Arena” competition, with more than 5 times fewer parameters (multiplications). Application of the proposed approach to factorization problems on dense graphs, network problems, surface meshes, covariance matrices made it possible to increase the accuracy of reconstruction using the Frobenius metric in individual problems by more than 8 orders of magnitude in combination with simplifying the structure of the multiplexer.