ترجمه فارسی مقاله شبکه‌های عصبی گراف به عنوان الگوریتم‌های ابتکاری مرتب‌سازی برای رنگ‌آمیزی موازی گراف

چکیده

The graph coloring problem asks for an assignment of the minimum number of distinct colors to vertices in an undirected graph with the constraint that no pair of adjacent vertices share the same color. The problem is a thoroughly studied NP-hard combinatorial problem with several real-world applications. As such, a number of greedy heuristics have been suggested that strike a good balance between coloring quality, execution time, and also parallel scalability. In this work, we introduce a graph neural network (GNN) based ordering heuristic and demonstrate that it outperforms existing greedy ordering heuristics both on quality and performance. Previous results have demonstrated that GNNs can produce high-quality colorings but at the expense of excessive running time. The current paper is the first that brings the execution time down to compete with existing greedy heuristics. Our GNN model is trained using both supervised and unsupervised techniques. The experimental results show that a 2-layer GNN model can achieve execution times between the largest degree first (LF) and smallest degree last (SL) ordering heuristics while outperforming both on coloring quality. Increasing the number of layers improves the coloring quality further, and it is only at four layers that SL becomes faster than the GNN. Finally, our GNN-based coloring heuristic achieves superior scaling in the parallel setting compared to both SL and LF.

چکیده به فارسی (ترجمه ماشینی)

مشکل رنگ آمیزی نمودار از حداقل تعداد رنگ های مجزا به راس ها در یک نمودار بدون جهت استفاده می کند با این محدودیت که هیچ جفتی از راس های مجاور همان رنگ را به اشتراک نمی گذارد.مشکل یک مشکل ترکیبی NP سخت با چندین برنامه کاربردی در دنیای واقعی است.به همین ترتیب ، تعدادی از اکتشافات حریص پیشنهاد شده است که تعادل خوبی بین کیفیت رنگ آمیزی ، زمان اجرای و همچنین مقیاس پذیری موازی دارند.در این کار ، ما یک شبکه عصبی نمودار (GNN) مبتنی بر سفارش را معرفی می کنیم و نشان می دهیم که از اکتشافی های حریص موجود هم از نظر کیفیت و هم از نظر کیفیت و عملکرد بهتر است.نتایج قبلی نشان داده است که GNN ها می توانند رنگهای با کیفیت بالا را تولید کنند اما با هزینه زمان بیش از حد در حال اجرا.مقاله فعلی اولین کسی است که زمان اجرای آن را برای رقابت با اکتشافی های حریص موجود پایین می آورد.مدل GNN ما با استفاده از هر دو تکنیک تحت نظارت و بدون نظارت آموزش دیده است.نتایج تجربی نشان می دهد که یک مدل GNN 2 لایه می تواند زمان اجرای بین بزرگترین درجه اول (LF) و کوچکترین درجه آخرین (SL) سفارش را در حالی که از کیفیت رنگ آمیزی بالاتر است ، بدست آورد.افزایش تعداد لایه ها باعث افزایش کیفیت رنگ آمیزی می شود و فقط در چهار لایه است که SL سریعتر از GNN می شود.سرانجام ، اکتشافی رنگ آمیزی مبتنی بر GNN ما در مقایسه با SL و LF به مقیاس برتر در تنظیم موازی دست می یابد.