Vertex coloring by subgraph expansion in unsupervised graph neural networks: constructing a curriculum by iterative growth of subgraphs of an input graph
Denetimsiz grafik sinir ağlarında altgraf genişletmesiyle köşe boyaması: girdi grafının altgraflarının iteratif büyütülmesi yoluyla bir müfredat oluşturma
- Tez No: 972454
- Danışmanlar: PROF. CAN AKKAN
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Grafik sinir ağları, Graph neural networks
- Yıl: 2025
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Veri Bilimi Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Köşe boyaması, bir grafın her köşesine öyle renkler atamayı amaçlayan klasik bir kombinatoryel optimizasyon problemidir ki bitişik iki köşe aynı rengi paylaşmasın. Bir grafın $k$ renkle boyanabilir olup olmadığını belirlemenin NP-tam, çatışmasız en az renk sayısını bulmanın ise NP-zor olduğu bilinmektedir \citep{np_hard_complete}. Köşe boyaması; çizelgeleme, yazmaç tahsisi (register allocation), sınav programlama ve benzeri pek çok alanda önemli uygulamalara sahiptir. Son yıllarda Grafik Sinir Ağları (GNN) graf yapılı veriler üzerinde güçlü öğrenme modelleri olarak öne çıkmış, köşe boyaması problemini de gözetimsiz köşe sınıflandırma görevi biçiminde ele alabilmektedir. Özellikle \cite{schuetz_graph_coloring_2022}, geçerli boyamaları teşvik eden Potts-tabanlı bir kaybı eniyileyen fizik esinli yaklaşımların, klasik çözücülerle aynı hatta daha iyi performans sergilediğini ve milyonlarca köşeye kadar ölçeklenebildiğini göstermiştir. Bu tezde, gözetimsiz GNN'lerle köşe boyaması için müfredat-esinli yeni bir eğitim stratejisi öneriyorum. Yöntem, önce küçük bir altgraf üzerinde eğitimi başlatıp eğitim kümesini kademeli olarak tüm grafı kapsayacak biçimde genişletmektedir (katman-katman BFS, derece-öncelikli BFS veya rasgele yürüyüş genişlemesi). Böylece ağ, önceki aşamanın ön-eğitilmiş gömülerini ve model ağırlıklarını devralarak aşamalı bir öğrenme sürecine tabi tutulur. Sürekli Potts kaybıyla eğitilen iki GNN mimarisi (Graph Convolution Model ve GraphSAGE) uygulanmıştır. Yaklaşımımız, COLOR kıyaslama veri kümesinin bir alt kümesi (Mycielski grafları, n-queens grafları ve bir sosyal ağ grafı) üzerinde değerlendirilmiştir. Deneyler, altgraf genişletme yöntemlerinin—özellikle derece-öncelikli BFS varyantının—toplam eğitim süresini \%30–35 oranında azalttığını, buna karşın çatışma sayılarının istatistiksel olarak karşılaştırılabilir düzeyde kaldığını göstermektedir. Bu bulgular, müfredat benzeri artımlı eğitimin kombinatoryel grafik görevlerinde GNN'lerden yararlanmak için umut verici bir yön olduğunu düşündürmektedir.
Özet (Çeviri)
Vertex coloring is a classic combinatorial optimization problem in which each vertex of a graph must be assigned a color so that no two adjacent vertices share the same color. This problem is known to be NP-complete for determining whether a graph can be colored with $k$ colors, and finding the minimum number of colors without conflicts is NP-hard \citep{np_hard_complete}. It has important applications in scheduling, register allocation, timetabling, and other domains. In recent years, Graph Neural Networks (GNNs) have emerged as powerful models for graph-structured learning, and can tackle vertex coloring by framing it as an unsupervised node-classification task. In particular, \cite{schuetz_graph_coloring_2022} show that a physics-inspired approach optimized a Potts-based loss to encourage valid colorings. This GNN-based method has achieved performance on par with or better than classical solvers, even scaling to graphs with millions of vertices. In this thesis, I propose a novel curriculum-inspired training strategy for vertex coloring using unsupervised GNNs. The method begins by training on a small subgraph and incrementally expands the training set (through layer-by-layer BFS-based, Breadth-First-Search, expansion, degree-first BFS-based expansion, or random walk expansion) to cover the entire graph. This curriculum-like incremental training exposes the network learn in stages, leveraging pre-trained embeddings and pre-trained model weights from the subgraph of the previous stage. Two GNN architectures (a Graph Convolution model and a GraphSAGE model) were implemented and trained with a continuous Potts-based loss. We evaluated our approach on a subset of the COLOR benchmark dataset (including Mycielski graphs, n-queen graphs, and a social network graph). The experiments show that the subgraph expansion methods—especially the degree-first BFS variant—reduces total training time by 30–35\% while maintaining statistically comparable conflict counts. These results suggest that the curriculum-like incremental training is a promising direction for leveraging GNNs in combinatorial graph tasks.
Benzer Tezler
- Graflarda düğüm boyama problemi için kurbağa sıçrama algoritması tabanlı bir yaklaşım
An approach based on shuffled frog leaping algorithm for vertex coloring problem in graphs
MURAT ASLAN
Yüksek Lisans
Türkçe
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. NURDAN BAYKAN
- Vertex coloring of a graph
Çizgelerde köşe renklendirme
GÖKŞEN BACAK
Yüksek Lisans
İngilizce
2004
Matematikİzmir Yüksek Teknoloji EnstitüsüMatematik Ana Bilim Dalı
YRD. DOÇ. DR. ÜNAL UFUKTEPE
- Solving graph coloring problem by using an evolutionary algorithm
Başlık çevirisi yok
SERAP KORKMAZ
Yüksek Lisans
İngilizce
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ BETÜL DEMİRÖZ BOZ
- Introduction to vertex-coloring problem
Köşe renklendirme problemine giriş
MOHAMMED JABBAR ABDULLAH AL-SHAFEAY
Yüksek Lisans
İngilizce
2022
MatematikÇankırı Karatekin ÜniversitesiMatematik Ana Bilim Dalı
DR. ÖĞR. ÜYESİ CELALETTİN KAYA
- Malatya merkezilik algoritmasına dayalı graf renklendirme algoritmasının harita renklendirme ve ders çizelgeleme uygulamaları
Map coloring and course scheduling applications of the graph coloring algorithm based on the malatya centrality algorithm
CEZAYİR KARACA
Yüksek Lisans
Türkçe
2025
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİnönü ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ SELMAN YAKUT