قوة التعبير: اختبار Weisfeiler-Lehman وGIN وما بعدهما
Expressive Power: the WL Test, GIN and Beyond
سؤال نظري بنتائج عملية: ما الرسوم التي تستطيع GNN التمييز بينها؟ يربط الدرس انتقال الرسائل باختبار 1-WL، ويشرح لماذا يجب أن يكون التجميع حقنياً، وكيف صُممت GIN لتبلغ الحد الأعلى، ثم الطرق التي تتجاوزه: الشبكات عالية الرتبة، وعدّ البنى الفرعية، والخصائص العشوائية، والترميز الموضعي.
أهداف الدرس
- صياغة مبرهنة تكافؤ 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)h_G=\Big\Vert_{k=0}^{K}\operatorname{SUM}\!\left(\{h_v^{(k)} : v\in G\}\right)4 ما لا يستطيع 1-WL تمييزه
المثال الكلاسيكي: حلقة C₆ مقابل مثلثين منفصلين. كل عقدة في الحالتين درجتها 2، فيعطي 1-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؟
تمييز تمثيل العقدة نفسها عن مجموع جيرانها حتى يكون التحديث حقنياً على زوج (الذات، مجموعة الجيران).
تابع التعلّم
نماذج في هذا الدرس
مفاهيم مرتبطة
المراجع
- 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.
- Sato, R. (2020). A Survey on The Expressive Power of Graph Neural Networks. arXiv preprint. arXiv: 2003.04078مسح لقوة التعبير وحدودها وطرق تجاوز 1-WL.
- 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: مجمّعات متعددة مع مقيّسات تعتمد على الدرجة.
- Zhang, M., & Chen, Y. (2018). Link Prediction Based on Graph Neural Networks. Advances in Neural Information Processing Systems (NeurIPS). arXiv: 1802.09691SEAL: تصنيف الرسم الفرعي المحيط بالزوج مع وسم المسافة.
