Perpustakaan Digital ITB

Penelitian ini mengkaji pendekatan aproksimasi terhadap dimensi multiset lokal luar dengan menggunakan metode pembelajaran mesin. Dimensi multiset lokal luar merupakan salah satu konsep dalam teori graf yang menentukan himpunan simpul pembeda minimum untuk membedakan pasangan simpul bertetangga berdasarkan multiset jarak terhadap himpunan tersebut. Konsep ini memiliki relevansi luas dalam berbagai aplikasi, seperti penempatan sensor, deteksi simpul kritis dalam jaringan, dan verifikasi struktur topologi. Namun, perhitungan nilai dimensi multiset lokal luar secara menyeluruh merupakan masalah yang bersifat kompleks, sehingga tidak efisien diterapkan pada graf berukuran besar. Untuk mengatasi keterbatasan tersebut, penelitian ini menerapkan arsitektur graph neural networks (GNN), khususnya model graph isomorphism network (GIN) dan GraphSAGE. Dataset pelatihan terdiri dari ribuan graf yang merepresentasikan berbagai tipe dan ukuran graf, dengan nilai dimensi multiset lokal luar yang dihitung secara menyeluruh. Dua pendekatan pembelajaran diterapkan pembelajaran terarah untuk prediksi langsung kardinalitas dimensi multiset lokal luar, dan pembelajaran untuk konstruksi himpunan pembeda secara bertahap yang dilengkapi dengan strategi algoritma greedy. Hasil penelitian menunjukkan bahwa model berbasis GNN mampu menghasilkan aproksimasi dimensi multiset lokal luar dengan efisiensi waktu yang tinggi. Dibandingkan dengan metode pencarian menyeluruh yang memerlukan waktu komputasi signifikan, pendekatan berbasis GNN memberikan prediksi secara cepat dan tetap akurat. Temuan ini mengindikasikan bahwa pembelajaran mesin, khususnya GNN, merupakan pendekatan yang efisien dan skalabel untuk mengaproksimasi dimensi multiset lokal luar, serta berpotensi diterapkan pada berbagai skenario dunia nyata yang melibatkan graf kompleks.