تعلم الرسوم البيانية2019متوسط11 دقيقة قراءة
ما مدى قوة الشبكات العصبية البيانية؟
How Powerful Are Graph Neural Networks?
Xu, K. · Hu, W. · Leskovec, J. · Jegelka, S. — ICLR
المشكلة
بحلول عام 2018، كانت الشبكات العصبية البيانية تحقق أفضل النتائج في مهام تصنيف العقد وتصنيف الرسوم البيانية. لكن المشكلة أن تصميم البنيات الجديدة كان يسير بالحدس والتجريب، دون سند نظري يشرح لماذا تتفوق بنية على أخرى أو ما الأنماط البنيوية التي تستطيع شبكة معيّنة التقاطها وتلك التي تغفلها. بدون إطار كهذا ظلّ التصميم أقرب إلى التخمين، ولم يكن واضحاً ما إذا كانت الشبكات الموجودة قريبة من حدودها النظرية أم بعيدة عنها كل البعد.
الإسهام
إطار نظري صارم يربط الشبكات العصبية البيانية لتماثل الرسوم البيانية. تُثبت الورقة أن أي شبكة تعتمد لا يمكن أن تتجاوز في قوتها التمييزية اختبار 1-WL، ثم تحدّد الشروط اللازمة لبلوغ هذا السقف: أن تكون دالة متباينة على المجموعات المتعددة. كذلك تُبيّن أن GCN (المبنية على المتوسط) وGraphSAGE (المبنية على القيمة العظمى) لا تستوفيان هذا الشرط، فتعجزان عن تمييز بنى بيانية بعينها. وبناءً على هذا التحليل يقترح المؤلفون شبكة تماثل الرسوم البيانية (GIN) التي تجمع بالجمع ثم تمرّر الناتج عبر مُدرِك متعدد الطبقات، فتبلغ قوة تمييزية مكافئة لاختبار 1-WL بشكل مُبرهَن.
الأثر
أرست هذه الورقة الأساس النظري لتحليل تعبيرية الشبكات العصبية البيانية، وحوّلت تسلسل وايسفيلر-ليمان إلى المقياس المرجعي لقوة هذه الشبكات. ألهم هذا العمل موجة من الشبكات الأعلى رتبة (k-WL وk-IGN) وتصاميم واعية بالتعبيرية مثل Graphormer، وصارت شبكة GIN نفسها خطاً مرجعياً أساسياً في معايير التعلم على الرسوم البيانية. أما الفكرة الجوهرية — أن طريقة التجميع هي التي تحدّد — فقد غيّرت طريقة تصميم بنيات الرسوم البيانية وتقييمها في المجتمع البحثي.
تخيّل حيَّين مختلفين في مدينة واحدة، كل حيّ فيه عشرة منازل متصلة ببعضها عبر شوارع. تأتي موظفة إحصاء وتزور كل منزل وتسأل: «مَن جيرانك؟» ثم تلخّص كل حيّ في بطاقة واحدة.
لو حسبت الموظفة متوسط دخل جيران كل منزل، ستحصل على البطاقة ذاتها لحيَّين مختلفين تماماً — حيّ يكسب فيه الجميع 50 ألفاً، وآخر نصف سكانه يكسبون 20 ألفاً والنصف الآخر 80 ألفاً. المتوسط 50 ألفاً في كلتا الحالتين. ببساطة: الموظفة ضيّعت معلومات جوهرية حين اكتفت بالمتوسط.
لكن لو سجّلت القائمة الكاملة لدخول الجيران — أي — لاستطاعت دائماً التفريق بين الحيَّين. هذه الورقة تُثبت أن الشيء نفسه يحدث داخل : الطريقة التي تُجمَّع بها سمات الجيران هي التي تقرّر ما إذا كانت الشبكة قادرة على التمييز بين الهياكل المختلفة، أو محكوماً عليها بالعمى عنها.
ماذا يعني أن تكون الشبكة العصبية البيانية «قوية»؟
تعمل الشبكات العصبية البيانية بوصفة بسيطة تُعرف بـتجميع الجوار — ويُشار إليها أيضاً بـ. في كل طبقة تنظر كل عقدة إلى جيرانها وتجمع متجهات سماتهم عبر دالة تجميع ما (جمع أو متوسط أو قيمة عظمى)، ثم تُحوِّل الناتج. بعد k طبقات يصبح تمثيل كل عقدة يعكس بنية جوارها حتى مسافة k قفزات.
لكن السؤال الجوهري هو: هل تستطيع الشبكة التمييز بين رسمين بيانيَّيْن مختلفَيْن؟ إذا أنتج رسمان مختلفان متطابقة، فإن الشبكة تعاملهما وكأنهما شيء واحد — حتى لو كانت بنيتاهما مختلفتين كلياً. «قوة» الشبكة العصبية البيانية تعني قدرتها على إعطاء الرسوم البيانية المختلفة تضمينات مختلفة. وكلما كانت الشبكة أقوى استطاعت التفريق بين عائلة أوسع من الرسوم البيانية غير المتماثلة.
لهذا المفهوم نظير كلاسيكي في نظرية الرسوم البيانية هو اختبار وايسفيلر-ليمان (WL) لتماثل الرسوم البيانية: إجراء يُنقّح ألوان العقد تكرارياً بناءً على ألوان جيرانها. الرسمان اللذان يعجز اختبار WL عن التمييز بينهما يُسمَّيان «متكافئين بحسب WL». والبصيرة المركزية في هذه الورقة أن آلية تجميع الجوار داخل الشبكات العصبية البيانية مُطابقة بنيوياً لعملية تنقيح الألوان في اختبار WL. يترتب على ذلك أن أي شبكة عصبية بيانية لا يمكن أن تكون أقوى من اختبار WL — ويصير السؤال: أيّ الشبكات تصل فعلاً إلى هذا السقف؟
اختبار WL والشبكات العصبية البيانية: وجهان لعملة واحدة
لنبدأ بفهم آلية اختبار وايسفيلر-ليمان أحادي البُعد. تنطلق كل عقدة بلون ابتدائي (قد يكون تسميتها أو درجتها). في كل تكرار يجمع الاختبار المجموعة المتعددة من ألوان جيران العقدة، ثم يُمرِّر لون العقدة مع تلك المجموعة عبر دالة تجزئة (hash) فيولّد لوناً جديداً يُسنَد إلى العقدة. بعد عدد كافٍ من التكرارات، إذا اختلفت مجموعات الألوان بين رسمين بيانيَّين نستنتج أنهما غير متماثلين.
قارن ذلك الآن مع طبقة شبكة عصبية بيانية عامة: كل عقدة تجمع سمات جيرانها (تجميع)، ثم تدمجها مع سماتها الخاصة (دمج)، ثم تُمرِّر الناتج عبر دالة لاخطية. التوازي بين العمليتين دقيق: كلتاهما تُنقّحان تمثيلات العقد تكرارياً بناءً على الجوار المحلي. الفرق الوحيد أن اختبار WL يستخدم دالة تجزئة متباينة بطبيعة بنائها، أما الشبكة العصبية فتستخدم دالة عصبية مُتعلَّمة قد تكون وقد لا تكون.
تُصيغ الورقة هذا رسمياً في المبرهنة الأولى: إذا كانت دالة التجميع في الشبكة متباينة — بمعنى أنها لا تُعطي مُخرَجاً واحداً لمجموعتين متعددتين مختلفتين — فالشبكة تُعادل اختبار WL تماماً في قوتها التمييزية. أما إذا لم تكن متباينة فالشبكة أضعف حتماً.
لماذا يُضيع التجميع بالمتوسط والقيمة العظمى المعلومات
تفحص الورقة ثلاث دوال تجميع وترتّبها بحسب مقدار ما تحتفظ به من معلومات المجموعة المتعددة.
الجمع يلتقط المجموعة المتعددة كاملةً. خذ مجموعة مثل 3: الجمع يعطي 7. مجموعة أخرى 4 تعطي 7 أيضاً — لكن مع تحويل عصبي مناسب يُطبَّق قبل الجمع يمكن جعله دالةً متباينة. النقطة الجوهرية أن الجمع يحفظ هوية كل عنصر وعدد تكراراته معاً.
المتوسط يلتقط نسبة توزيع العناصر لكنه يفقد العدد. المجموعتان 2 و2 لهما المتوسط نفسه (4/3)، فالمتوسط عاجز عن التمييز بينهما. بكلمات أخرى: المتوسط أعمى عن حجم الجوار — عقدة بثلاثة جيران متوسط سماتهم 5 تبدو مطابقة لعقدة بثلاثمئة جار متوسط سماتهم 5 كذلك.
القيمة العظمى لا تلتقط سوى وجود العناصر المميزة وتفقد التكرار كلياً. المجموعتان 3 و3 غير قابلتين للتمييز بالقيمة العظمى لأن max = 3 في الحالتين بغض النظر عن التكرارات. القيمة العظمى لا تعرف كم مرة ظهرت كل سمة.
التسلسل واضح: الجمع > المتوسط > القيمة العظمى من حيث القدرة التمييزية. شبكة GCN تستخدم المتوسط، والنسخة القائمة على القيمة العظمى من GraphSAGE تستخدم القيمة العظمى. لا واحدة منهما تستطيع بلوغ سقف WL.
شبكة تماثل الرسوم البيانية (GIN): بلوغ السقف
الآن وقد عرفنا الشرط الذي يجعل الشبكة العصبية البيانية بالغة القوة — أن يكون التجميع متبايناً على المجموعات المتعددة — يبقى السؤال العملي: كيف نبني شبكة تحقّق هذا الشرط؟ الورقة تُبيّن أن متبوعاً بـ (MLP) يكفي لتحقيق ذلك.
الحدس وراء ذلك واضح: مبرهنة التقريب الشامل تُخبرنا أن المُدرِك متعدد الطبقات يستطيع تقريب أي دالة مستمرة. الورقة توسّع هذه النتيجة لتشمل المجموعات المتعددة: بالنسبة لفضاء مدخلات قابل للعدّ، توجد دالة f بحيث يكون تركيبها مع عملية الجمع متبايناً على جميع المجموعات المتعددة ذات الحجم المحدود. والمُدرِك متعدد الطبقات قادر على تعلّم هذه الدالة f. النتيجة إذن: MLP ∘ جمع تشكّل دالة متباينة على المجموعات المتعددة — وهذا بالضبط ما نحتاج إليه.
قاعدة تحديث GIN الكاملة تأخذ سمات العقدة نفسها وتضيفها إلى مجموع سمات جيرانها بعد ضربها في مُعامِل قابل للتعلّم (1 + ε)، ثم تمرّر الكل عبر MLP. المُعامِل ε يمنح الشبكة حرية تعلّم التوازن بين وزن العقدة المركزية ووزن جيرانها — وهذه درجة حرية ضرورية تضمن أن الدالة المُركَّبة تبقى متباينة.
القراءة على مستوى الرسم البياني: الجمع بين كل الطبقات
في مهمة نحتاج إلى متجه واحد يمثّل الرسم البياني بأكمله، وليس العقد كلاً على حدة. أبسط طريقة هي أخذ التمثيلات من الطبقة الأخيرة فقط، لكن ذلك يُضيع معلومات قيّمة: الطبقات الأولى تلتقط البنية المحلية كالأضلاع والمثلثات، بينما الطبقات العميقة تلتقط الأنماط الشاملة. تجاهل التمثيلات المبكرة أشبه بقراءة خاتمة كتاب دون فصوله.
تتبنّى GIN نهج الذي يستفيد من كل طبقة. في كل طبقة k تُجمَع سمات جميع العقد للحصول على متجه يمثّل الرسم البياني عند ذلك المقياس، ثم تُربَط متجهات جميع الطبقات بعضها ببعض. بهذا تُحفَظ المعلومات البنيوية عند كل مقياس — من الجيران المباشرين وصولاً إلى قُطر الرسم البياني بالكامل.
GIN في الشيفرة البرمجية
مبسَّط لإظهار الفكرة — ليس التنفيذ الحقيقي.
import torch import torch.nn as nn
class GINLayer(nn.Module):
"""طبقة واحدة من شبكة تماثل الرسوم البيانية."""
def __init__(self, in_dim, out_dim, eps_init=0.0):
super().__init__()
# MLP: طبقتان مع تسوية الدُّفعات (كما في الورقة)
self.mlp = nn.Sequential(
nn.Linear(in_dim, out_dim),
nn.BatchNorm1d(out_dim),
nn.ReLU(),
nn.Linear(out_dim, out_dim),
nn.BatchNorm1d(out_dim),
nn.ReLU(),
)
# إبسيلون قابل للتعلّم (يُثبَّت عند 0 في نسخة GIN-0)
self.eps = nn.Parameter(torch.tensor(eps_init))
def forward(self, h, adj):
# adj: مصفوفة التجاور (N × N)
# h: سمات العقد (N × in_dim)
neighbor_sum = torch.matmul(adj, h) # تجميع بالجمع
out = (1 + self.eps) * h + neighbor_sum # دمج العقدة مع جيرانها
return self.mlp(out) # تحويل عبر MLPالتحقق التجريبي
يختبر المؤلفون نظريتهم على 9 معايير لتصنيف الرسوم البيانية تغطي المعلوماتية الحيوية (MUTAG وPTC وPROTEINS وNCI1) والشبكات الاجتماعية (COLLAB وIMDB-BINARY وIMDB-MULTI وREDDIT-BINARY وREDDIT-MULTI-5K).
تبرز نتيجتان محوريتان. أولاً، دقة التدريب تُؤكّد التعبيرية: تبلغ GIN دقة تدريب شبه مثالية على جميع مجموعات البيانات، في حين تعاني نسخ GCN وGraphSAGE من نقص واضح في الملاءمة. هذا يصادق النظرية مباشرة — النموذج الأكثر تعبيرية يستطيع التقاط أنماط بنيوية أعقد في بيانات التدريب.
ثانياً، دقة الاختبار ترتبط بالنظرية: نسخة GIN-0 (بقيمة ε ثابتة عند 0) ونسخة GIN (بقيمة ε مُتعلَّمة) تتفوقان باستمرار على النسخ الأقل تعبيرية أو تعادلانها. وعلى مجموعات بيانات الشبكات الاجتماعية — حيث بنية الرسم البياني وليس سمات العقد هي الإشارة الرئيسية — تتجلّى أفضلية تجميع الجمع بوضوح خاص.
تسلسل القدرة التعبيرية
ترسم الورقة تسلسلاً واضحاً لأنواع الشبكات العصبية البيانية بحسب قوتها التمييزية.
في القمة تقف GIN (واختبار WL)، القادرة على تمييز أي زوج من الرسوم البيانية غير المتماثلة التي تختلف في مجموعاتها المتعددة من أنماط الأشجار الفرعية. في الوسط تأتي الشبكات المبنية على المتوسط (كـGCN) التي تلتقط توزيع السمات لكنها تفقد معلومات العدد. وفي الأسفل تقع الشبكات المبنية على القيمة العظمى التي تلتقط مجموعة السمات الموجودة فحسب، فاقدةً العدد والتوزيع معاً.
لهذا التسلسل تفسير بديهي جميل. تخيّل أن جوار كل عقدة كيسٌ من الكرات الملوّنة. الشبكات المبنية على الجمع تسجّل الجرد الكامل: «3 حمراء و2 زرقاء وواحدة خضراء.» الشبكات المبنية على المتوسط تسجّل النسب: «50% حمراء و33% زرقاء و17% خضراء» — ستحصل على القراءة ذاتها سواءً كان الكيس يحوي 6 كرات أو 60. أما الشبكات المبنية على القيمة العظمى فلا تسجّل إلا الألوان الموجودة: «أحمر وأزرق وأخضر» — القراءة ذاتها لأي كيس يحتوي هذه الألوان مهما كان عددها.
ما بعد GIN: التعبيرية الأعلى رتبة
تصل GIN إلى سقف 1-WL، لكن اختبار 1-WL نفسه له حدود. فهو عاجز عن تمييز رسوم بيانية منتظمة معيّنة (كرسمين غير متماثلين منتظمين من الدرجة 3 على 8 عقد)، ولا يستطيع عدّ البنى الفرعية كالمثلثات والحلقات. لكن إدراك هذه الحدود بالذات هو ما فتح أبواب بحثية واسعة.
اختبارات WL الأعلى رتبة (k-WL) تعمل على مجموعات مؤلّفة من k عقدة بدلاً من عقد مفردة، مما يمنحها قوة تمييزية أكبر بصرامة. بنيات مثل k-IGN وGraphormer تتخطى سقف 1-WL بدمج ترميزات موضعية شاملة أو تفاعلات أعلى رتبة أو آليات تلتقط ضمنياً معلومات بنيوية أغنى.
الإسهام الأبقى لورقة GIN ليس شبكة GIN بحدّ ذاتها — بل الإطار النظري. حين ربط المؤلفون الشبكات العصبية البيانية بتسلسل WL، منحوا المجتمع البحثي لغة مشتركة للحديث عن التعبيرية، وحوّلوا تصميم البنيات من فنّ يعتمد الحدس إلى علم له أدواته.
2017
GCN وإطار تمرير الرسائل
قدّم كيبف وويلينغ شبكات الطيّ البيانية مستخدمَين تجميع المتوسط. وفي الوقت ذاته وحّد غيلمر وزملاؤه أنواع الشبكات العصبية البيانية تحت إطار شبكات تمرير الرسائل (MPNN).
2017
GraphSAGE: تعلّم بياني قابل للتوسّع
اقترح هاميلتون ويينغ وليسكوفيك نموذج GraphSAGE الذي يجمع بين أخذ العينات وخيارات تجميع متعددة (متوسط وLSTM وقيمة عظمى) لإجراء تعلّم استقرائي على رسوم بيانية كبيرة.
2019
GIN: حين التقت النظرية بالتصميم
برهن شو وزملاؤه إطار تكافؤ WL واقترحوا GIN — أول شبكة عصبية بيانية يُبرهَن أنها تعادل اختبار 1-WL في القوة التمييزية. هذه هي الورقة الحالية.
2020
ظهور شبكات أعلى رتبة
دفعت بنيات مثل k-IGN وتجميع الجوار الرئيسي (PNA) حدود التعبيرية إلى ما بعد سقف 1-WL عبر استخدام تفاعلات بين مجموعات عقدية أعلى رتبة ومُجمِّعات متعددة.
2021
Graphormer: المحوِّلات في عالم الرسوم البيانية
أظهر يينغ وزملاؤه أن المحوِّلات المزوّدة بترميزات بنيوية تستطيع تجاوز شبكات تمرير الرسائل في التعبيرية، وحققت الفوز في تحدي OGB واسع النطاق.
المرجعXu, Hu, Leskovec, Jegelka. How Powerful Are Graph Neural Networks?. ICLR, 2019.
مصطلحات هذه الورقة
- الشبكات العصبية الرسومية (البيانية)Graph Neural Network (GNN)
- تشابُه البيانات البيانيةGraph Isomorphism
- اختبار وايسفيلر-ليمانWeisfeiler-Lehman Test
- تمرير الرسائلMessage Passing
- التجميعAggregation
- المجموعة المتعددةMultiset
- الدالة المتباينةInjective Function
- دالة القراءةReadout Function
- القدرة التعبيريةExpressivity
- تجميع الجوارNeighborhood Aggregation
- تصنيف البيانات البيانيةGraph Classification
- تضمين العُقدNode Embedding
- تجميع الجمعSum Aggregation
- التجميع بالقيمة القصوىMax Pooling