Perpustakaan Digital ITB

Untuk suatu graf tak-berarah dan terhubung G = (V,E), serta himpunan W = {w1,w2, . . . ,wk} ? V , representasi multiset dari titik v ? V terhadap W didefinisikan sebagai r?(v|W) = {d(v,wi) : wi ? W}, dengan d(u, v) menyatakan jarak antara u dan v. Himpunan W disebut himpunan pembeda multiset lokal jika untuk setiap pasangan titik u, v ? V yang bertetangga, berlaku r?(u|W) ?= r?(v|W). Kardinalitas minimum himpunan pembeda ini disebut dimensi multiset lokal dari graf G. Karena waktu dan iterasi pencarian nilai dimensi multiset lokal menyeluruh bersifat eksponensial terhadap banyak titik, penelitian ini mengusulkan pendekatan aproksimasi menggunakan Graph Neural Network, dengan dua skema pembelajaran: pembelajaran terarah dan pembelajaran penguatan. Model Graph Convolutional Network dan Graph Sample and Aggregate dilatih untuk memprediksi himpunan pembeda lokal dari dataset berisi 2.999 graf acak dengan n = 10 hingga 60 simpul dari enam jenis graf acak. Evaluasi dilakukan berdasarkan galat prediksi dan waktu komputasi.