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.
References
Theory, 1981, Vol. 27, No. 5, pp. 533-547.
2. Mézard M., Montanari A. Information, Physics, and Computation. Oxford Graduate Texts,
2009, 569 p.
3. Tanner R., et al. LDPC block and convolutional codes based on circulant matrices, IEEE
Transactions on Information Theory, 2004, Vol. 50, No. 12, pp. 2966-2984.
4. Sukar L.E. Veroyatnostnye grafovye modeli. Printsipy i prilozheniya [Probabilistic graph
models. Principles and applications]. Moscow: DMK Press, 2021, 338 p.
5. Stan Z. Li. Markov Random Field Modeling in Image Analysis. Springer London, 2009, 362 p.
6. Usatyuk V., Sapozhnikov D., Egorov S. Spherical and Hyperbolic Toric Topology-Based
Codes on Graph Embedding for Ising MRF Models: Classical and Quantum Topology Machine
Learning, 2023, 71 p. Available at: https://arxiv.org/abs/2307.15778.
7. Yi T., et al. Long Range Arena: A Benchmark for Efficient Transformers. ICLR, 2021, 15 p.
8. Koen M.I. Prikladnaya lineynaya algebra dlya issledovateley dannykh [Applied linear algebra
for data scientists]. Moscow: DMK Press, 2023, 328 p.
9. Eckart C., Young G. The Approximation of One Matrix by Another of Lower Rank,
Psychometrika, 1936, Vol. 1, No. 3, pp. 211-218.
10. Fomin F. V., et al. Approximation schemes for low-rank binary matrix approximation problems,
ACM Transactions on Algor., 2019, Vol. 16, No. 1, pp. 12:1-12:39.
11. Camilli F., Mezard M. Matrix factorization with neural networks, American Physical Society,
Phys. Rev. E., 2023, Vol. 107, No. 6.
12. Khalitov R., et al. Sparse factorization of square matrices with application to neural attention
modeling, Neural Networks, 2022, Vol. 152, pp. 160-168.
13. Stoica I., et al. Chord: A scalable peer-to-peer lookup service for internet applications, ACM
SIGCOMM Computer Communication Review, 2001, Vol. 31, No 4, pp. 149-160.
14. Hu Xiao-Yu, Eleftheriou E., Arnold D. M. Regular and irregular progressive edge-growth tanner
graphs, IEEE Transactions on Information Theory, 2005, Vol. 51, No. 1, pp. 386-398.
15. Tian Tao, Jones C. R., Villasenor J. D., Wesel R. D. Selective avoidance of cycles in irregular
LDPC code construction, IEEE Transactions on Communications, 2004, Vol. 52, No. 8,
pp. 1242-1247.
16. Usatyuk V.S., Egorov S.I. Postroenie kvazitsiklicheskikh nedvoichnykh nizkoplotnostnykh
kodov na osnove sovmestnoy otsenki ikh distantnykh svoystv i spektrov svyaznosti [Construction
of quasi-cyclic non-binary low-density codes based on a joint assessment of their distant
properties and connectivity spectra], Telekommunikatsii [Telecommunications], 2016, No. 8,
pp. 32-40.
17. Usatyuk V.S., Egorov S.I. Ustroystvo dlya otsenki kodovogo rasstoyaniya lineynogo blochnogo
koda metodom geometrii chisel [Device for estimating the code distance of a linear block code
using the geometry of numbers method], Izvestiya Yugo-Zapadnogo gosudarstvennogo
universiteta. Seriya: Upravlenie, vychislitel'naya tekhnika, informatika. Meditsinskoe
priborostroenie [News of the South-West State University. Series: Management, computer technology,
computer science. Medical instrumentation], 2017, No. 4 (25), pp. 24-33.
18. Usatyuk V., Egorov S., Svistunov G. Construction of Length and Rate Adaptive MET
QC-LDPC Codes by Cyclic Group Decomposition, 2019 IEEE East-West Design & Test Symposium
(EWDTS). Batumi, Georgia, 2019, pp. 1-5.
19. Usatyuk V., Vorobyev I. Simulated Annealing Method for Construction of High-Girth
QC-LDPC Codes, Intern. Conf. on Telecom. and Signal Proc., 2018, pp. 1-5.
20. Usatyuk V.S. Matlab implementation of TSVD, SF Chord, LDPC PEG+ACE, QC-LDPC
SA+EMD (MET) codes sparse factorization. Available at: https://github.com/Lcrypto/ Classical-
and-Quantum-Topology-ML-toric-spherical.
