Oʻzbekcha
NP-QIYIN KOMBINATORIK MASALALARNI YECHISHDA SUN'IY NEYRON TARMOQLARINI (GNN VA GCN) QO‘LLASH USULLARI
Journal
Priority areas for applying artificial intelligence to pedagogical education
Issue
Priority areas for applying artificial intelligence to pedagogical education
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.
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)
Русский
МЕТОДЫ ПРИМЕНЕНИЯ ИСКУССТВЕННЫХ НЕЙРОННЫХ СЕТЕЙ (GNN И GCN) В РЕШЕНИИ NP-ТРУДНЫХ КОМБИНАТОРНЫХ ЗАДАЧ
В данной статье анализируются методы машинного обучения для решения таких NP-трудных задач, как «Максимальное независимое множество» (Maximum Independent Set) и «Раскраска графа» (Graph Coloring), которые являются сложными задачами логистики и прикладной математики. Целью работы является повышение скорости решения задач путем применения архитектур графовых нейронных сетей (GNN) и графовых сверточных сетей (GCN) взамен традиционных алгоритмов.
графовые нейронные сети (GNN)
графовые сверточные сети (GCN)
NP-трудные задачи
комбинаторная оптимизация
максимальное независимое множество
раскраска графа
передача сообщений (message-passing)
English
METHODS FOR APPLYING ARTIFICIAL NEURAL NETWORKS (GNN AND GCN) TO SOLVING NP-HARD COMBINATORIAL PROBLEMS
This paper analyzes machine learning methods for solving NP-hard problems such as Maximum Independent Set (MIS) and Graph Coloring, which are challenging problems in logistics and applied mathematics. The goal of the paper is to improve the speed of problem solving by applying graph neural network (GNN) and graph convolutional network (GCN) architectures to replace traditional algorithms.
graph neural networks (GNN)
graph convolutional networks (GCN)
NP-hard problems
combinatorial optimization
maximum independent set
graph coloring
message passing
1. 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.
2. Wolsey L. A., Nemhauser G. L. Integer and Combinatorial Optimization. – New York : Wiley-Interscience, 1999. – 784 p.
3. 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.
4. 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.
5. 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.
6. Lewis R. A Guide to Graph Colouring: Algorithms and Applications. – Cham : Springer Nature, 2021. – 282 p.
7. Kipf T. N., Welling M. Semi-supervised classification with graph convolutional networks // International Conference on Learning Representations (ICLR). – 2017. – 15 p.
8. Lemos H., Rossi R. A., Matrosov A. [et al.] Graph colouring with graph neural networks // arXiv preprint arXiv:2002.04692. – 2020. – 12 p.