تشاكل الرسوم واختبار WL
Graph Isomorphism & WL Test
رسمان متشاكلان إذا أمكن إعادة ترقيم أحدهما ليطابق الآخر؛ واختبار Weisfeiler-Lehman طريقة تقريبية لتمييزهما.
الشرح
اختبار 1-WL يلوّن العقد ثم يحدّث لون كل عقدة من مجموعة ألوان جيرانها، تكراراً. أثبت Xu وزملاؤه أن نماذج انتقال الرسائل لا تميّز أكثر من هذا الاختبار، وأنها تبلغ قوته إذا كان التجميع والتحديث حقنيين، ومن هنا تصميم GIN.
المعادلة
c_v^{(k)}=\mathrm{HASH}\!\left(c_v^{(k-1)},\ \{\!\{c_u^{(k-1)}:u\in\mathcal{N}(v)\}\!\}\right)شرح الرموز
- c_v: لون العقدة
- {{ }}: مجموعة متعددة
المراجع
- Xu, K., Hu, W., Leskovec, J., & Jegelka, S. (2019). How Powerful are Graph Neural Networks?. International Conference on Learning Representations (ICLR). arXiv: 1810.00826الورقة الأصلية لـ GIN وربط قوة التمييز باختبار Weisfeiler-Lehman.
