Grafik neyron tarmoqlarida topologiyadan xabardorlikni tushunish: umumlashtirish va strukturaga ta'siri

Havolalar jadvali

Annotatsiya va 1 Kirish

2 Tegishli ish

3 Ramka

4 Asosiy natijalar

5 Eng qisqa yo'l masofasi bo'yicha amaliy ish

6 Xulosa va munozara va foydalanilgan adabiyotlar

7 1-teoremaning isboti

8 2-teoremaning isboti

9 Tenglamani yechish tartibi. (6)

10 ta qo'shimcha tajriba tafsilotlari va natijalari

11 Boshqa potentsial ilovalar

Abstrakt

Ko'pgina kompyuter ko'rish va mashinani o'rganish muammolari grafiklarda o'rganish vazifalari sifatida modellashtirilgan, bu erda grafik neyron tarmoqlari (GNN) grafik tuzilgan ma'lumotlarning tasvirlarini o'rganish uchun dominant vosita sifatida paydo bo'lgan. GNNning asosiy xususiyati ularning grafik tuzilmalaridan kirish sifatida foydalanishidir, bu ularga grafiklarning o'ziga xos topologik xususiyatlaridan foydalanishga imkon beradi - GNNning topologiyasi deb nomlanadi. GNNning empirik muvaffaqiyatlariga qaramay, topologiyadan xabardorlikning umumlashtirish samaradorligiga ta'siri o'rganilmagan bo'lib qolmoqda, ayniqsa ma'lumotlarning mustaqil va bir xil taqsimlangan (IID) farazlaridan ajralib turadigan tugun darajasidagi vazifalar uchun. GNNning topologiyasi haqida xabardorlikning aniq ta'rifi va tavsifi, ayniqsa turli topologik xususiyatlarga taalluqli, hali ham noaniq. Ushbu maqola har qanday topologik xususiyat bo'yicha GNNlarning topologiyadan xabardorligini tavsiflash uchun keng qamrovli asosni taqdim etadi. Ushbu asosdan foydalanib, biz topologiyadan xabardorlikning GNNni umumlashtirish samaradorligiga ta'sirini o'rganamiz. GNNning topologiyadan xabardorligini oshirish har doim foydalidir, degan keng tarqalgan e'tiqoddan farqli o'laroq, bizning tahlilimiz tanqidiy fikrni ochib beradi: GNNning topologiyasi haqida xabardorlikni oshirish, ba'zi bir stsenariylarda istalmagan bo'lishi mumkin bo'lgan tizimli guruhlar o'rtasida nohaq umumlashtirishga olib kelishi mumkin. Bundan tashqari, biz turli xil benchmark ma'lumotlar to'plamlarida ichki grafik ko'rsatkichi, eng qisqa yo'l masofasidan foydalangan holda amaliy tadqiqot o'tkazamiz. Ushbu amaliy tadqiqotning empirik natijalari bizning nazariy fikrlarimizni tasdiqlaydi. Bundan tashqari, biz tizimimizning amaliy qo'llanilishini grafik faol o'rganishda sovuq boshlash muammosini hal qilish uchun ishlatib ko'rsatamiz.

1 Kirish

Kompyuterni ko'rish va mashinani o'rganishdagi ko'plab muammolar grafiklarda o'quv vazifalari sifatida modellashtirilgan. Misol uchun, semantik segmentatsiyada grafiklar tasvirning turli hududlari o'rtasidagi munosabatlarni modellashtiradi, aniqlik va kontekstdan xabardor segmentatsiyani oshiradi. Grafik neyron tarmoqlari (GNN) grafik tuzilgan ma'lumotlarning tasvirlarini o'rganish uchun maxsus ishlab chiqilgan mashina o'rganish modellarining dominant sinfi sifatida paydo bo'ldi. Ular kimyo [10], biologiya [37], ijtimoiy tarmoq [6, 22], sahna grafigini yaratish [46, 51] va vizual aloqalarni aniqlash kabi turli sohalarda grafik bilan bog'liq keng ko'lamli muammolarni hal qilishda katta muvaffaqiyatlarga erishdi. [24,43,49]. GNNning o'ziga xos xususiyati - bu xususiyatlarni yig'ish uchun grafik tuzilmaga xabar yuborish orqali fazoviy yondashuvdan foydalanish. Bu GNN-larga asosiy grafik tuzilmasidan strukturaviy ma'lumot yoki bog'liqlikni (topologiyadan xabardorlik deb ataladi) saqlashga imkon beradi, bu esa ularni tugunlarni tasniflash kabi vazifalarda yuqori samarali bo'lishiga imkon beradi. 1-rasmda GNNning umumiy o'quv jarayoni tasvirlangan.

Amaliyligi va potentsialiga qaramay, GNNlar haqida nazariy tushunchalar mavjud emas, xususan, ma'lumotlar o'rtasidagi bog'liqliklar boshqa mashinani o'rganish modellaridan sezilarli darajada farq qiladigan yarim nazoratli tugunlarni tasniflashda [25]. Ushbu sozlamada maqsad, qolgan tugunlar uchun teglarni bashorat qilish uchun ma'lumotlar va kichik etiketli tugunlar to'plami o'rtasida grafik tuzilmasi tomonidan olingan munosabatlardan foydalanishdir. Mavjud GNN nazariy tadqiqotlarining aksariyati GNN ning xabarni uzatish mexanizmi va Weisfeiler-Lehman izomorfizm testi [19] o'rtasidagi bog'liqlikka qaratilgan bo'lib, GNNlarning o'rganilgan tasvirlarda turli xil grafik tuzilmalarini farqlash qobiliyatini tushunishga qaratilgan. GNNlarning ifoda kuchi sifatida. Ekspressivlikni o'rganishdan ilhomlangan holda, topologiyadan xabardorlikni oshirish universal foydali ekanligiga ishonishadi va ko'plab tadqiqotlar GNN-larga o'rganilgan vakillikda ko'proq strukturaviy xususiyatlarni saqlab qolish imkonini berishga qaratilgan [29, 33, 48].

Biroq, GNNlar kirish sifatida grafik tuzilmasiga ko'proq tayanishi va sezgir (xabardor) bo'lib qolganligi sababli, ular ma'lumotlar ichidagi ma'lum tarkibiy kichik guruhlarga (o'quv majmuasiga tizimli o'xshashlik bo'yicha guruhlangan alohida ma'lumotlar to'plamlari) nisbatan turli xil umumlashtirish ko'rsatkichlarini ko'rsatishi mumkin. Turli tarkibiy kichik guruhlar bo'yicha GNN umumlashtirishning miqdoriy ko'rsatkichi tizimli kichik guruhlarni umumlashtirish deb ataladi [25]. Bunday fikrlar GNNni qo'llash va ishlab chiqishda juda muhimdir. Masalan, oqsil-oqsil o'zaro ta'sir tarmoqlarida ushbu tarkibiy kichik guruhlar o'zaro ta'sirni bashorat qilishning to'g'riligiga ta'sir qiluvchi turli molekulyar komplekslarni ifodalashi mumkin. Xuddi shunday, o'qitish uchun namuna olish strategiyalarini ishlab chiqishda GNNning topologiyasi haqida xabardorligi umumlashtirishga qanday ta'sir qilishini tushunish muhimdir. Grafik ma'lumotlarning o'ziga xos strukturaviy xususiyatlari GNNning umumlashtirish ko'rsatkichlariga ta'sir qilish darajasi o'quv ma'lumotlar to'plamining tarkibini tanlashda hal qiluvchi ahamiyatga ega. Uning muhimligiga qaramay, GNNning topologiyasi haqidagi xabardorligi va uning tarkibiy kichik guruhlarini umumlashtirish o'rtasidagi bog'liqlikni tushunish hali ham mavjud emas. Bundan tashqari, GNN-larning topologiyadan xabardorligini tavsiflash, ayniqsa, turli sohalar va vazifalar alohida tuzilmaviy jihatlarga ustunlik berishi mumkinligini hisobga olsak, qiyinchilik tug'diradi. Shuning uchun, turli tuzilmalar bilan bog'liq holda GNN ning topologiyadan xabardorligini baholash uchun ko'p qirrali asos kerak.

Ushbu bo'shliqni bartaraf etish uchun ushbu maqolada biz yarim nazorat ostida tugunlarni tasniflash kontekstida GNNning tarkibiy kichik guruhlarini umumlashtirish va topologiya xabardorligi o'rtasidagi munosabatni o'rganish uchun taxminiy metrik o'rnatishga asoslangan yangi asosni taklif qilamiz. Taklif etilayotgan asos turli tarkibiy kichik guruhlarga nisbatan GNNning tarkibiy kichik guruhlarini umumlashtirishni o'rganishga imkon beradi. Aniqroq qilib aytganda, ushbu ishning asosiy hissalari quyidagicha umumlashtiriladi.

1. Biz GNNning tarkibiy kichik guruhlarini umumlashtirish va topologiyani bilish o'rtasidagi o'zaro bog'liqlikni tekshirish uchun taxminiy metrik o'rnatishdan foydalangan holda yangi, struktura-agnostik asosni taklif qilamiz. Ushbu ramka ko'p qirrali bo'lib, eng qisqa yo'l masofasi kabi turli xil tuzilmaviy choralarni o'z ichiga oladi va faqat mos keladigan tizimli o'lchovni talab qiladi. Asosiy omillarni baholashning soddaligi uni keng stsenariylar uchun qo'llash va umumlashtirish imkonini beradi.

2. Bizning doiramizdagi rasmiy tahlil orqali biz GNN topologiyasi xabardorligi va ularning umumlashtirish ko'rsatkichlari o'rtasida aniq bog'liqlikni o'rnatamiz (1-teorema). Shuningdek, biz topologiyadan xabardorlikni oshirish GNN ekspressivligini oshirishi bilan birga, umumlashtirishning notekis ishlashiga olib kelishi mumkin, bu esa o'quv majmuasiga tizimli ravishda o'xshash kichik guruhlarga yordam berishi mumkin (2-teorema). Bunday tuzilmaviy mulk stsenariyga qarab zararli (adolatsizlik bilan bog'liq muammolarni keltirib chiqaradi) yoki foydali (dizayn qarorlari haqida ma'lumot beruvchi) bo'lishi mumkin. Bu topologiyadan xabardorlikni oshirish GNN larga universal foyda keltiradi degan hukmron fikrni shubha ostiga qo'yadi [29, 33, 48], topologiyadan xabardorlik va umumlashtirish samaradorligi o'rtasidagi munosabatni ko'rib chiqish muhimligini ta'kidlaydi.

3. Biz o'z asosimizni eng qisqa yo'l masofasi bo'yicha amaliy tadqiqot orqali tasdiqlaymiz, uning amaliyligi va dolzarbligini ta'kidlaymiz. Natijalar bizning nazariy topilmalarimizni tasdiqlaydi, bu esa eng qisqa yo'l masofalari haqida yuqori ma'lumotga ega bo'lgan GNNlar o'quv majmuasiga yaqinroq cho'qqi guruhlarini tasniflashda ustunlik qilishini ko'rsatadi. Bundan tashqari, biz topilmalarimizni grafik faol o'rganishda sovuq boshlash muammosini yumshatish uchun qanday qo'llanilishi mumkinligini ko'rsatamiz [11,15], bizning asosimiz va natijalarimizning amaliy oqibatlarini ta'kidlaymiz.