GIN – شبكة تشاكل الرسوم
Graph Isomorphism Network (2019)
لتكون أقوى ما يمكن في تمييز البنى، اجمع الجيران بالمجموع (لا بالمتوسط ولا الأقصى) ومرّر النتيجة إلى MLP؛ فتبلغ قوة اختبار Weisfeiler-Lehman.
الحدس
لتكون أقوى ما يمكن في تمييز البنى، اجمع الجيران بالمجموع (لا بالمتوسط ولا الأقصى) ومرّر النتيجة إلى MLP؛ فتبلغ قوة اختبار Weisfeiler-Lehman.
الشرح التفصيلي
أثبت المؤلفون أن قوة MPNN محدودة بـ 1-WL، وأنها تبلغه إذا كانت دوال التجميع والتحديث حقنية على المجموعات المتعددة. المجموع مع MLP يحقق ذلك، والمعامل ε يميز تمثيل العقدة عن جيرانها. الـ MLP ضرورية: طبقة خطية واحدة لا تكفي للحقنية.
للرسوم: قراءة بالمجموع لكل طبقة ثم ضم كل الطبقات. أظهرت التجارب أن GIN تحقق دقة تدريب شبه كاملة على مجموعات TU، بينما تعجز GCN وSAGE-mean عن ملاءمة بعضها، وهو دليل على الفرق في القدرة التعبيرية. ونسخة GINE تضيف خصائص الروابط إلى الرسائل.
البنية المعمارية
5 طبقات GIN (MLP بطبقتين وBatchNorm) ← قراءة بالمجموع لكل طبقة ← ضم ← MLP ← تصنيف.
المعادلات
h_v^{(k)}=\operatorname{MLP}^{(k)}\Big((1+\epsilon^{(k)})h_v^{(k-1)}+\sum_{u\in N(v)}h_u^{(k-1)}\Big)h_G=\operatorname{CONCAT}\Big(\operatorname{SUM}\{h_v^{(k)}\}\;\big|\;k=0,\dots,K\Big)نقاط القوة
- أقصى قوة تمييز ممكنة لـ MPNN
- ممتازة في تصنيف الرسوم
- بسيطة التنفيذ
القيود
- لا تتجاوز 1-WL (لا تعد المثلثات عموماً)
- المجموع حساس للدرجات الكبيرة في تصنيف العقد
- قد تفرط في التخصيص على المجموعات الصغيرة
التعقيد الحسابي
O(|E|·F + n·MLP) لكل طبقة.
متى تستخدمه
تصنيف الرسوم وكل مهمة يعتمد فيها الوسم على البنية الدقيقة.
التنفيذ في PyTorch Geometric
torch_geometric.nn.GINConv / GINEConvشيفرة توضيحية للاستخدام المعتاد؛ راجع توثيق إصدار المكتبة الذي تستخدمه قبل تشغيلها.
تابع التعلّم
نماذج مرتبطة
دروس تشرحه
المراجع
- 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.
- Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., & Grohe, M. (2019). Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks. AAAI Conference on Artificial Intelligence. arXiv: 1810.02244تكافؤ MPNN مع اختبار 1-WL وتعميمه إلى k-GNN.
