كتب الذكاء الاصطناعيمشاريع الذكاء الاصطناعيمقالات الذكاء الاصطناعيمعجم الذكاء الاصطناعياسئلة واجوبة في الذكاء الاصطناعيأكاديمية الذكاء الاصطناعي للأطفالأكاديمية الذكاء الاصطناعيمدرسة رياضيات الذكاء الاصطناعيمختبر الذكاء الاصطناعيمختبر الخوارزميات المستوحاة من الطبيعةأطلس نماذج الذكاء الاصطناعيموسوعة تطبيقات الذكاء الاصطناعيمستكشف مجموعات البيانات للذكاء الاصطناعياختبارات الذكاء الاصطناعيالفايب كودينغدليل البرمجة بالذكاء الاصطناعيمولّد مشاريع الذكاء الاصطناعيمرصد الذكاء الاصطناعيدليل أدوات الذكاء الاصطناعي البحث والنشر الأكاديميمكتبة البرومبتات الأكاديميةمستودع الرسائل والأطاريح في الذكاء الاصطناعيحاسبة الترقية العلميةأكاديمية الوكلاء الذكيينمختبر أخلاقيات الذكاء الاصطناعي والعدالةساحة ألعاب الذكاء الاصطناعيعبقري الذكاء الاصطناعيمختبر التنبؤ بالسلاسل الزمنيةمتحف الذكاء الاصطناعيمختبر الرؤية الحاسوبيةموسوعة شبكات التعلم العميق الحديثةمختبر الشبكات العصبية البيانيةمختبر تحليل الصور الطبيةمختبر معالجة اللغة الطبيعيةمختبر الحوسبة الكمّيةخرائط طريق الذكاء الاصطناعيأكاديمية ماتلاب والذكاء الاصطناعيمصمم الشبكات العصبيةأكاديمية الذكاء الاصطناعي بدون برمجةمختبر الذكاء الاصطناعي الكمّي

قوة التعبير: اختبار Weisfeiler-Lehman وGIN وما بعدهما

Expressive Power: the WL Test, GIN and Beyond

سؤال نظري بنتائج عملية: ما الرسوم التي تستطيع GNN التمييز بينها؟ يربط الدرس انتقال الرسائل باختبار 1-WL، ويشرح لماذا يجب أن يكون التجميع حقنياً، وكيف صُممت GIN لتبلغ الحد الأعلى، ثم الطرق التي تتجاوزه: الشبكات عالية الرتبة، وعدّ البنى الفرعية، والخصائص العشوائية، والترميز الموضعي.

المعماريات الأساسيةمتقدم30 دقيقة قراءةالدرس 11 من 23

أهداف الدرس

  • صياغة مبرهنة تكافؤ MPNN مع 1-WL
  • شرح شرط الحقنية في التجميع والتحديث
  • اشتقاق طبقة GIN ومعنى المعامل ε
  • تعداد طرق تجاوز حد 1-WL وكلفتها

1 التمييز بين الرسوم

إذا أعطت GNN التمثيل نفسه لرسمين مختلفين فلن يستطيع أي مصنف بعدها التفريق بينهما. لذلك نسأل: ما أقوى قدرة تمييز ممكنة لنماذج انتقال الرسائل؟ أثبت Xu وزملاؤه (2019) وMorris وزملاؤه (2019) أن أي GNN تعتمد على تجميع الجيران لا يمكن أن تكون أقوى من اختبار 1-WL: إذا لم يميز 1-WL بين رسمين فلن تميزهما GNN. وتبلغ GNN قوة 1-WL تماماً إذا كانت دوال التجميع والتحديث والقراءة حقنية (Injective) على المجموعات المتعددة.

2 لماذا يفشل المتوسط والأقصى؟

دالة حقنية تعني أن مدخلين مختلفين يعطيان مخرجين مختلفين. المتوسط ليس حقنياً على المجموعات المتعددة: {a, b} و{a, a, b, b} متوسطهما واحد. والأقصى أسوأ: {a, b} و{a, a, a, b} لهما الأقصى نفسه. المجموع حقني على المجموعات المتعددة المعدودة إذا سبقته دالة مناسبة، وهذه النتيجة (من نظرية Deep Sets) هي أساس GIN. لهذا تفشل GCN وGraphSAGE-mean في تمييز بعض البنى البسيطة، مثل رسوم منتظمة لها الدرجة نفسها في كل العقد.

3 GIN: شبكة تشاكل الرسوم

تجمع GIN الجيران بالمجموع، وتضيف تمثيل العقدة مضروباً في (1 + ε) حتى تميز الذات عن الجيران، ثم تمرر النتيجة إلى MLP، لأن MLP بحسب مبرهنة التقريب الشامل تستطيع تمثيل الدالة الحقنية المطلوبة. ε قد يكون ثابتاً (عادة 0) أو متعلَّماً. لتصنيف الرسوم تُستخدم قراءة بالمجموع لتمثيلات كل الطبقات ثم تُضم، لأن الطبقات الأولى تحمل معلومات بنيوية أدق تضيع في الأعمق.

h_v^{(k)}=\operatorname{MLP}^{(k)}\!\Big(\big(1+\epsilon^{(k)}\big)\,h_v^{(k-1)}+\sum_{u\in\mathcal{N}(v)}h_u^{(k-1)}\Big)
طبقة GIN.
h_G=\Big\Vert_{k=0}^{K}\operatorname{SUM}\!\left(\{h_v^{(k)} : v\in G\}\right)
قراءة الرسم في GIN: مجموع كل طبقة ثم الضم.
v(1+ε)h_v + Σ h_uinjective sumMLP2 layersh⁽⁰⁾Σh⁽¹⁾Σh⁽²⁾ΣCONCATh_G
GIN: مجموع الجيران مع تمثيل العقدة موزوناً بـ (1+ε) ثم شبكة MLP، وقراءة بالمجموع لكل الطبقات.

4 ما لا يستطيع 1-WL تمييزه

المثال الكلاسيكي: حلقة C₆ مقابل مثلثين منفصلين. كل عقدة في الحالتين درجتها 2، فيعطي 1-WL كل العقد اللون نفسه في كل تكرار، رغم أن أحد الرسمين متصل والآخر لا.

  • رسمان منتظمان بالدرجة نفسها وعدد العقد نفسه (مثل حلقة بست عقد مقابل مثلثين منفصلين).
  • عدد المثلثات والحلقات القصيرة في الحالة العامة.
  • خصائص المسافة مثل القطر وبعض خصائص الاتصال.
  • التمييز بين العقد المتماثلة بنيوياً في روابط مختلفة (مهم في التنبؤ بالروابط).
C62 × C3≠WL: same colours
حدّ WL: حلقة من ست عقد ومثلثان منفصلان لهما الألوان نفسها، رغم أنهما غير متماثلين.

5 تجاوز حد 1-WL

القوة الأكبر ليست دائماً أفضل: نماذج أكثر تعبيراً قد تفرط في التخصيص وتكلف أكثر، وكثير من المجموعات الحقيقية لا تحتاج أكثر من 1-WL. القاعدة العملية: ابدأ بـ GIN في تصنيف الرسوم، وأضف ترميزاً بنيوياً إذا كانت المهمة تعتمد صراحة على الحلقات أو المسافات.

  • شبكات عالية الرتبة (k-GNN، k-WL): ترسل الرسائل بين k-مجموعات من العقد. أقوى لكن كلفتها O(n^k).
  • عدّ البنى الفرعية (GSN): إضافة عدد المثلثات أو الحلقات التي تشارك فيها كل عقدة خاصيةً.
  • الخصائص العشوائية أو المعرّفات: تكسر التماثل لكنها تضر بالثبات تحت التبديل ما لم تُعالَج بحذر.
  • الترميز الموضعي والبنيوي: متجهات لابلاسيان الذاتية أو المسارات العشوائية، شائع في محوّلات الرسوم.
  • شبكات الرسوم الفرعية (Subgraph GNNs): تطبيق GNN على رسوم فرعية متعددة (بحذف عقدة أو تمييزها) ثم التجميع.
  • وسم العقد في التنبؤ بالروابط (SEAL): تمييز العقدتين المستهدفتين يكسر التماثل.

خلاصة الدرس

  • قوة MPNN لا تتجاوز اختبار 1-WL
  • الحقنية تتطلب تجميعاً بالمجموع لا بالمتوسط أو الأقصى
  • GIN تبلغ قوة 1-WL بالمجموع وMLP وε
  • تجاوز 1-WL ممكن بالرتب العليا والبنى الفرعية والترميز الموضعي لكن بكلفة

تحقّق من فهمك

فكّر في الإجابة أولاً، ثم افتح السؤال لترى الجواب.

لماذا لا تميز GNN القياسية بين حلقة من 6 عقد ومثلثين منفصلين؟

لأن كل العقد في الرسمين درجتها 2 وجوارها المحلي متطابق، فيحصل كل منها على اللون نفسه في 1-WL في كل تكرار.

ما دور (1 + ε) في GIN؟

تمييز تمثيل العقدة نفسها عن مجموع جيرانها حتى يكون التحديث حقنياً على زوج (الذات، مجموعة الجيران).

تابع التعلّم

نماذج في هذا الدرس

مفاهيم مرتبطة

طبّق في المختبر: مختبر الخوارزميات

المراجع

  1. 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.
  2. 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.
  3. Sato, R. (2020). A Survey on The Expressive Power of Graph Neural Networks. arXiv preprint. arXiv: 2003.04078مسح لقوة التعبير وحدودها وطرق تجاوز 1-WL.
  4. Corso, G., Cavalleri, L., Beaini, D., Liò, P., & Veličković, P. (2020). Principal Neighbourhood Aggregation for Graph Nets. Advances in Neural Information Processing Systems (NeurIPS). arXiv: 2004.05718PNA: مجمّعات متعددة مع مقيّسات تعتمد على الدرجة.
  5. Zhang, M., & Chen, Y. (2018). Link Prediction Based on Graph Neural Networks. Advances in Neural Information Processing Systems (NeurIPS). arXiv: 1802.09691SEAL: تصنيف الرسم الفرعي المحيط بالزوج مع وسم المسافة.