NP-QIYIN KOMBINATORIK MASALALARNI YECHISHDA SUN'IY NEYRON TARMOQLARINI (GNN VA GCN) QO'LLASH USULLARI
Keywords:
Graflar neyron tarmoqlari (GNN), Graflar konvolyutsion tarmoqlari (GCN), NP-qiyin masalalar, kombinatorik optimallashtirish, eng katta mustaqil to'plam, grafni bo'yash, xabarlar uzatish (message-passing).Abstract
Ushbu maqolada logistika va amaliy matematikaning murakkab masalalaridan bo'lgan "Eng katta mustaqil to'plam" (Maximum Independent Set) va "Grafni bo'yash" (Graph Coloring) kabi NP-qiyin masalalarni yechishda mashinali o'rganish usullari tahlil qilinadi. An'anaviy algoritmlar o'rniga Graflar neyron tarmoqlari (GNN) hamda Graflar konvolyutsion tarmoqlari (GCN) arxitekturalarini qo'llash orqali masalalarning yechim tezligini oshirish maqsad qilingan.
References
Garey M. R., Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. – San Francisco : W. H. Freeman & Co, 1979. – 340 p.
Wolsey L. A., Nemhauser G. L. Integer and Combinatorial Optimization. – New York : Wiley-Interscience, 1999. – 784 p.
Wu Z., Pan S., Chen F. [et al.] A comprehensive survey on graph neural networks // IEEE Transactions on Neural Networks and Learning Systems. – 2020. – Vol. 32, No. 1. – P. 4–24.
Bengio Y., Lodi A., Prouvost A. Machine learning for combinatorial optimization: a methodological tour d’horizon // European Journal of Operational Research. – 2021. – Vol. 290, No. 2. – P. 405–421.
Li Z., Chen Q., Koltun V. Combinatorial optimization with graph convolutional networks and guided tree search // Advances in Neural Information Processing Systems (NeurIPS). – 2018. – Vol. 31. – P. 539–548.
Lewis R. A Guide to Graph Colouring: Algorithms and Applications. – Cham : Springer Nature, 2021. – 282 p.
Kipf T. N., Welling M. Semi-supervised classification with graph convolutional networks // International Conference on Learning Representations (ICLR). – 2017. – 15 p.
Lemos H., Rossi R. A., Matrosov A. [et al.] Graph colouring with graph neural networks // arXiv preprint arXiv:2002.04692. – 2020. – 12 p.
