تعلم الرسوم البيانية2017متوسط11 دقيقة قراءة

التصنيف شبه المُوجَّه باستخدام الشبكات الالتفافية الرسومية

Semi-Supervised Classification with Graph Convolutional Networks

Kipf, T. N. · Welling, M. — ICLR

المشكلة

بحلول 2016، كان في الرسوم البيانية (مثل تصنيف الأوراق البحثية في شبكة اقتباسات) يتطلب إما استخراج سمات يدوية من بنية الرسم البياني، أو اللجوء إلى أساليب طيفية مُكلِفة حسابياً تحلّل بالكامل. وُجدت طرق تعمل بعدد قليل من التسميات، لكنها لم تستطع الاستفادة من بنية الروابط وسمات العُقد في آنٍ واحد. السؤال المطروح كان: هل يمكن بناء شبكة عصبية تُجري التفافاً مباشراً على بنية الرسم البياني، وتتوسّع بكفاءة إلى رسوم بيانية كبيرة، وتتعلم من حفنة صغيرة فقط من العُقد المُعلَّمة؟

الإسهام

الشبكة الالتفافية الرسومية (GCN): قاعدة انتشار طبقية مُشتقّة من تقريب من الدرجة الأولى للالتفافات الطيفية على الرسوم البيانية. في كل طبقة، تجمع كل سماتها مع سمات جيرانها عبر المُعاد تسويتها، ثم تُطبَّق عملية تحويل خطي ودالة تنشيط لاخطية. شبكة GCN من طبقتين فقط، مع بضع عشرات من العُقد المُعلَّمة لكل فئة، تفوّقت على منظومات معالجة متعددة المراحل (انتشار التسميات + استخلاص السمات + التصنيف) في شبكات الاقتباسات الأكاديمية، بتعقيد حسابي خطّي بعدد الروابط.

الأثر

تُعدّ GCN البنية التأسيسية الحديث على الرسوم البيانية. أثبتت أن النظرية الطيفية يمكن أن تُنتج قاعدة مكانية بسيطة وقابلة للتوسّع، وألهمت ظهور GAT وGraphSAGE وGIN ونموذج بأكمله. واليوم تُستخدم تنويعات GCN في اكتشاف الأدوية وأنظمة التوصية وتحليل الشبكات الاجتماعية والتنبؤ بحركة المرور والتنبؤ بخصائص الجزيئات.

تخيّل قرية فيها بيوت، لكل بيت لون يميّزه (). عدد قليل فقط من البيوت يحمل لوحة اسم (تسمية). كل صباح، يطّلع كل بيت على ألوان جيرانه، ويمزجها مع لونه، ثم يعيد طلاء نفسه باللون الناتج. بعد صباحين فقط، حتى البيوت التي لم تحمل لوحة اسم تكون قد جمعت معلومات كافية من محيطها لتخمين ما ينبغي أن تقوله لوحتها.

شبكة GCN هي هذا الروتين الصباحي بصيغة رياضية: كل عقدة تحسب متوسط سمات جيرانها، وتحوّل النتيجة بتحويل خطي و، ثم تكرّر العملية. جولتان عادةً تكفيان.

لماذا تحتاج الرسوم البيانية إلى شبكات عصبية خاصة بها

الصور مبنية على شبكة منتظمة من البكسلات، والنصوص تسير في تسلسل خطّي. التقليدية تستغل هذا الانتظام: تُمرّر مرشّحاً ثابت الحجم فوق الشبكة أو التسلسل. لكن الشبكة الاجتماعية أو الجزيء أو شبكة الاقتباسات لا تملك بنية منتظمة — فكل عقدة قد يكون لها جار واحد أو ألف جار، ولا يوجد ترتيب طبيعي من اليسار إلى اليمين.

قبل GCN، كانت هناك عائلتان من الأساليب:

هندسة السمات + مُصنِّف. تُصمَّم يدوياً إحصاءات من بنية الرسم البياني (الدرجة، المركزية، PageRank)، وتُتجاهل السمات الخام على العُقد، ثم تُغذّى لمُصنِّف مثل SVM. المشكلة أن هذا يُهدر المعلومات الغنية المخزّنة على كل عقدة.
الأساليب الطيفية. يُحلَّل لابلاسيان الرسم البياني لتعريف تحويل فورييه عليه، ثم يُجرى الالتفاف في . الفكرة أنيقة رياضياً، لكن تحليل يكلّف $O(n^3)$ ، والمرشّحات مرتبطة بالرسم البياني الذي دُرّبت عليه — أي لا يمكن نقلها إلى رسم بياني آخر.

السؤال الذي طرحه Kipf وWelling: هل نستطيع أن نأخذ الفكرة الجوهرية من النظرية الطيفية — وهي أن الالتفاف على الرسم البياني يكافئ الضرب في الفضاء الذاتي للابلاسيان — ثم نبسّطها حتى نحصل على قاعدة مكانية قابلة للتوسّع؟

افتح في المختبر

بدِّل بين المنظور الطيفي (تحليل القيم الذاتية للابلاسيان) والمنظور المكاني (حساب متوسط الجيران) لترى كيف تربط GCN بينهما.

تستيقظ التجربة عند وصولك…

من الالتفاف الطيفي إلى قاعدة مكانية في سطر واحد

الانتقال من الالتفاف الطيفي الكامل إلى قاعدة انتشار GCN يمرّ بثلاث خطوات. في كل خطوة نتنازل عن شيء من العمومية الرياضية مقابل سرعة حسابية أكبر، حتى نصل في النهاية إلى قاعدة بسيطة يمكن كتابتها في سطر برمجي واحد.

الخطوة الأولى — الالتفاف الطيفي على الرسوم البيانية. لدينا رسم بياني من $N$ عقدة ومصفوفة تجاور $A$ . نعرّف لابلاسيان الرسم البياني المُسوَّى بالصيغة: $L = I_N - D^{-1/2}AD^{-1/2}$ ، حيث $D$ هي . التحليل الذاتي $L = U\Lambda U^T$ يعطينا أساس فورييه على الرسم البياني. المرشّح الطيفي $g_\theta$ يُجري التفافاً على إشارة $x$ بالضرب في المجال الترددي: $g_\theta \star x = U \, g_\theta(\Lambda) \, U^T x$ . هذا التعبير دقيق، لكنه يكلّف $O(N^2)$ لكل عملية ضرب ويتطلب حساب جميع — وهذا غير عملي للرسوم البيانية الكبيرة.

الخطوة الثانية — تقريب تشيبيشيف. اقترح Defferrard وآخرون (ChebNet) تقريب $g_\theta(\Lambda)$ بـ من الدرجة $K$ ، فأصبح المرشّح محلياً بمدى $K$ قفزات، وانخفضت التكلفة إلى $O(K \cdot |\mathcal{E}|)$ — أي خطّية بعدد الروابط. لكن $K$ يجب اختياره، ومعاملات كثير الحدود تحتاج إلى تعلّم.

الخطوة الثالثة — الدرجة الأولى + إعادة التسوية (GCN). اختار Kipf وWelling $K{=}1$ ، فأصبح المرشّح يرى كل عقدة وجيرانها المباشرين فحسب. ثم طبّقا : أضافا ( $\tilde{A} = A + I_N$ ) وأجريا تسوية متناظرة ( $\hat{A} = \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$ ). النتيجة هي قاعدة انتشار واحدة نظيفة لكل طبقة.

H^{(l+1)} = \sigma\!\Bigl(\tilde{D}^{-1/2}\,\tilde{A}\,\tilde{D}^{-1/2}\;H^{(l)}\,W^{(l)}\Bigr)

قاعدة الانتشار الطبقية لـ GCN — في كل طبقة، تُحدّث كل عقدة تمثيلها عبر جمع المعلومات من جيرانها ومن نفسها. تُسوَّى هذه المساهمات لمراعاة الفروق في عدد الاتصالات بين العقد، ثم تُحوَّل بمعاملات قابلة للتعلّم وتُمرَّر عبر دالة تنشيط لاخطية. ومع تكرار هذه العملية عبر الطبقات، تنتشر المعلومات في الرسم البياني تدريجياً، فتبني كل عقدة تمثيلاً أغنى لبيئتها المحلية.

افتح في المختبر

شاهد كيف تُثبّت إضافة الحلقات الذاتية وإعادة تسوية مصفوفة التجاور نطاقَ القيم الذاتية وتغيّر سلوك الانتشار.

تستيقظ التجربة عند وصولك…

شبكة GCN من طبقتين لتصنيف العُقد

لإجراء تصنيف العُقد بأسلوب التعلم شبه المُوجَّه، بنى Kipf وWelling شبكة من طبقتين فقط. الطبقة الأولى تستقبل سمات العُقد الخام $X \in \mathbb{R}^{N \times C}$ (مثل متجه كيس الكلمات لكل ورقة بحثية)، وتحوّلها إلى فضاء ببُعد $H$ ، ثم تمرّرها عبر . الطبقة الثانية تأخذ هذا التمثيل الخفي وتُسقطه على عدد الفئات، ثم تُطبّق للحصول على توزيع احتمالي.

تخيّل الأمر كمحادثة من جولتين: في الجولة الأولى، تجمع كل عقدة سمات جيرانها وتبني فهماً أغنى لبيئتها المحلية. في الجولة الثانية، تجمع تلك التمثيلات المُثراة من الجيران — التي باتت تحمل معلومات بمدى قفزتين — وتتخذ قرار التصنيف.

يُحسب على العُقد المُعلَّمة فقط، لكن يتدفق عبر الرسم البياني بأكمله لأن تمثيل كل عقدة يعتمد على جيرانها، سواء أكانت مُعلَّمة أم لا. هذا هو جوهر التعلم شبه المُوجَّه على الرسوم البيانية: البنية ذاتها تنقل إشارة الإشراف.

Z = \text{softmax}\!\Bigl(\hat{A}\;\text{ReLU}\bigl(\hat{A}\,X\,W^{(0)}\bigr)\,W^{(1)}\Bigr)

شبكة GCN من طبقتين للتصنيف — التمرير الأمامي الكامل: تُضرب السمات X في مصفوفة التجاور المُسوّاة مرتين (مرة لكل طبقة)، مع مصفوفة أوزان قابلة للتعلّم ودالة ReLU بينهما، وسوفت ماكس في النهاية.

\mathcal{L} = -\sum_{i \in \mathcal{V}_L}\sum_{f=1}^{F} Y_{if}\,\ln Z_{if}

فقد الإنتروبيا التقاطعية (على العُقد المُعلَّمة فقط) — التدريب المُوجَّه يقتصر على العقد ذات التسميات المعروفة. يقارن النموذج تنبؤاته لهذه العقد بالقيم الحقيقية ويحدّث معاملاته لتقليل الخطأ. وعلى الرغم من أن العقد غير المُعلَّمة لا تُسهم مباشرةً في حساب الفقد، فإنها تؤثّر في عملية التعلّم لأن المعلومات تنتقل عبر روابط الرسم البياني، فتُشكّل تمثيلات تنعكس على تنبؤات العقد المُعلَّمة المجاورة.

افتح في المختبر

استكشف بنية GCN ذات الطبقتين. انقر على كل مرحلة لمعرفة الأبعاد والعمليات وكيفية تدفق المعلومات من السمات المُدخلة إلى تنبؤات الفئات.

تستيقظ التجربة عند وصولك…

الانتشار عملياً: تتبُّع تدفق السمات

لبناء الحدس، لنأخذ مثالاً على شبكة اقتباسات: كل ورقة بحثية هي عقدة، وكل اقتباس رابط، وسمات كل ورقة هي متجه كيس الكلمات الخاص بها. نفترض أننا نُعلِّم 20 ورقة فقط لكل فئة من بين آلاف الأوراق.

الطبقة الأولى. كل ورقة تحسب متوسط متجه كلماتها مع متجهات الأوراق التي تقتبسها أو تقتبس منها. ورقة في تعلّم الآلة محاطة بأوراق في معالجة اللغة الطبيعية ستمتصّ مفردات ذلك الحقل في تمثيلها. مصفوفة $W^{(0)}$ تتعلم أي تركيبات من سمات الجيران مفيدة — فتضغط مثلاً 1433 كلمة إلى 16 بُعداً خفياً.

الطبقة الثانية. الآن كل ورقة تحسب متوسط التمثيلات المُثراة سابقاً لجيرانها. ورقة تبعد قفزتين عن ورقة مُعلَّمة بفئة «التعلم العميق» باتت تحمل شيئاً من تأثير تلك التسمية في تمثيلها. مصفوفة الأوزان $W^{(1)}$ تُسقط الأبعاد الخفية الستة عشر على عدد الفئات، ثم تُنتج سوفت ماكس توزيعاً احتمالياً.

العُقد المُعلَّمة هي مرتكزات إشارة المتدرِّج. ولأن الرسم البياني الحسابي يربط كل عقدة بجوارها، فإن المتدرِّج من كل عقدة مُعلَّمة يتموّج نحو الخارج عبر مسارات من قفزتين، دافعاً تمثيلات العُقد غير المُعلَّمة برفق نحو الفئات الصحيحة.

افتح في المختبر

شاهد السمات وهي تنتشر عبر رسم بياني صغير للاقتباسات. العُقد المُعلَّمة تنشر اللون (معلومات الفئة) إلى جيرانها عبر طبقتي GCN.

تستيقظ التجربة عند وصولك…

قوة التعلم شبه المُوجَّه: تسميات قليلة، رسم بياني كامل

الفكرة الجوهرية هي أن GCN لا تُفرّق بين العُقد المُعلَّمة وغير المُعلَّمة أثناء التمرير الأمامي — جميع العُقد تشارك في كل خطوة انتشار. الفرق الوحيد يظهر عند حساب الفقد: ينطلق المتدرِّج من العُقد المُعلَّمة، لكنه ينتشر عكسياً عبر بنية الرسم البياني المشتركة ليحدّث جميع مصفوفات الأوزان.

على مجموعة بيانات Cora (2,708 ورقة بحثية، 7 فئات)، باستخدام 20 عقدة مُعلَّمة لكل فئة فقط (140 إجمالاً، نحو 5%)، حققت شبكة GCN ذات الطبقتين دقة 81.5%. قارن ذلك بانتشار التسميات (68.0%) أو DeepWalk (%67.2) أو Planetoid (%75.7). قدرة GCN على التعلم المشترك من السمات والبنية هي ما يجعلها فعالة جداً حتى مع عدد ضئيل من التسميات.

لماذا ينجح هذا الأسلوب؟ تخيّل عقدتين متصلتين برابط لكن بسمات أولية مختلفة. إذا كانتا تنتميان إلى الفئة نفسها، تتعلم GCN مصفوفات أوزان تُنتج تمثيلات خفية متقاربة لكلتيهما رغم اختلاف مدخلاتهما. بنية الرسم البياني هنا تلعب دور : العُقد المتصلة ينبغي أن تحمل تمثيلات متشابهة، وهذا بالضبط افتراض النعومة الذي يقوم عليه التعلم شبه المُوجَّه على الرسوم البيانية.

افتح في المختبر

ابدأ بعدد قليل من العُقد المُعلَّمة وراقب كيف تنشر GCN معلومات الفئة عبر الرسم البياني. غيّر عدد التسميات لترى أثر ذلك على الدقة.

تستيقظ التجربة عند وصولك…

فخ العمق: لماذا لا يكون الأعمق دائماً أفضل

في المخصصة للصور، العمق يعني قوة — بنى مثل VGG وResNet تتجاوز 100 طبقة. فلماذا يبلغ أداء GCN ذروته عند 2–3 طبقات فقط؟

الجواب هو . كل طبقة GCN تحسب متوسط تمثيل العقدة مع تمثيلات جيرانها. بعد $K$ طبقة، يتأثر تمثيل كل عقدة بجميع العُقد الواقعة ضمن $K$ قفزة منها. وفي الرسوم البيانية ذات خاصية «العالم الصغير» (مثل شبكات الاقتباسات)، يكفي 6–7 قفزات للوصول إلى معظم العُقد. النتيجة: بعد طبقات كثيرة، تتقارب تمثيلات جميع العُقد نحو قيمة واحدة — وتُمحى كل المعلومات المميّزة لكل عقدة.

تخيّل أنك تمزج ألوان دهان. مزجة واحدة تخلط الألوان المتجاورة بشكل جميل. مزجتان تصنعان تدرّجاً أنيقاً. لكن عشر مزجات؟ ستحصل على لون بُنّي موحّد. هذا بالضبط ما يحدث في الإفراط في التنعيم.

وجد Kipf وWelling أن 2–3 طبقات تحقق الأداء الأمثل على مقاييسهم المرجعية. هذا ليس قيداً على الشبكات الرسومية عموماً — فأعمال لاحقة مثل GATv2 وJKNet وGCNII أضافت لتمكين بناء شبكات رسومية أعمق — لكنه خاصية جوهرية في GCN الأصلية يجب على الممارسين مراعاتها.

افتح في المختبر

حرِّك عدد الطبقات من 1 إلى 10 وراقب كيف تصبح تمثيلات العُقد غير قابلة للتمييز بعد طبقات كثيرة.

تستيقظ التجربة عند وصولك…

GCN برمجياً: بساطة مدهشة

شبكة GCN من طبقتين بأقل كود ممكن في PyTorchpython

مبسَّط لإظهار الفكرة — ليس التنفيذ الحقيقي.

import torch, torch.nn as nn, torch.nn.functional as F

class GCNLayer(nn.Module):
    """طبقة انتشار GCN واحدة: Â X W + انحياز، ثم تنشيط."""
    def __init__(self, in_dim, out_dim):
        super().__init__()
        self.W = nn.Linear(in_dim, out_dim, bias=True)

    def forward(self, A_hat, X):
        # A_hat: مصفوفة التجاور المُسوّاة المحسوبة مسبقاً
        # تجميع الجيران ثم التحويل الخطي
        return self.W(A_hat @ X)


class GCN(nn.Module):
    def __init__(self, n_features, n_hidden, n_classes, dropout=0.5):
        super().__init__()
        self.layer1 = GCNLayer(n_features, n_hidden)
        self.layer2 = GCNLayer(n_hidden, n_classes)
        self.dropout = dropout

    def forward(self, A_hat, X):
        # الطبقة الأولى: تجميع + تحويل + ReLU + إسقاط عشوائي
        H = F.relu(self.layer1(A_hat, X))
        H = F.dropout(H, self.dropout, training=self.training)
        # الطبقة الثانية: تجميع + تحويل + سوفت ماكس
        return F.log_softmax(self.layer2(A_hat, H), dim=1)

النتائج: تفوّق على المنظومات المعقدة

اختبر Kipf وWelling النموذج على ثلاث مجموعات بيانات لشبكات الاقتباسات — Cora وCiteseer وPubmed — إضافة إلى الرسم البياني المعرفي NELL. في كل مجموعة، لم تُستخدم سوى حفنة من التسميات لكل فئة أثناء .

على Cora (2,708 عقدة، 5,429 رابط، 7 فئات): حققت GCN دقة 81.5% بـ 140 عقدة مُعلَّمة فقط. أقرب منافس، Planetoid، لم يتجاوز 75.7%.

على Citeseer (3,327 عقدة، 4,732 رابط، 6 فئات): بلغت GCN 70.3%، متفوّقة على 64.7% لـ Planetoid.

على Pubmed (19,717 عقدة، 44,338 رابط، 3 فئات): سجّلت GCN 79.0%، متجاوزة 77.2% لـ Planetoid.

وتوسّعت GCN بشكل خطّي أيضاً: زمن التدريب نما بتناسب مع عدد الروابط لا مع مربّع عدد العُقد. وعلى رسوم بيانية عشوائية تصل إلى مليون رابط، ظل الزمن الفعلي مقبولاً على وحدة معالجة رسوميات واحدة.

افتح في المختبر

قارن دقة GCN مع الأساليب المرجعية عبر مقاييس Cora وCiteseer وPubmed.

تستيقظ التجربة عند وصولك…

الأثر الذي أحدثته GCN

أثبتت GCN أن تبسيطاً منهجياً للنظرية الطيفية يمكن أن يُنتج بنية عملية قابلة للتوسّع. هذه الرؤية وحدها فتحت الباب أمام موجة واسعة من أبحاث .

2017
GCN — الشبكة الالتفافية الرسومية
ربط Kipf وWelling بين التعلم الطيفي والمكاني على الرسوم البيانية بتقريب من الدرجة الأولى وحيلة إعادة التسوية. طبقتان وحفنة تسميات حققت نتائج متفوّقة.
2017
GAT — شبكات الانتباه الرسومية
استبدل Veličković وآخرون أوزان الجيران الثابتة في GCN (المستمدّة من مصفوفة الدرجات) بدرجات انتباه مُتعلَّمة، بحيث تقرّر كل عقدة مقدار اهتمامها بكل جار على حدة.
2017
GraphSAGE — أخذ العيّنات والتجميع
جعل Hamilton وآخرون الشبكات العصبية الرسومية استقرائية: بدلاً من الحاجة إلى الرسم البياني الكامل، يُؤخذ عدد ثابت من الجيران ويُجمَّع. وبذلك يمكن تصنيف عُقد جديدة دون إعادة تدريب.
2017
MPNN — شبكة تمرير الرسائل العصبية
وحّد Gilmer وآخرون GCN وGAT وغيرها ضمن إطار عمل واحد: كل عقدة ترسل رسائل إلى جيرانها، تُجمَّع هذه الرسائل ثم تُستخدم لتحديث حالة العقدة.
2019
GIN — شبكة التماثل الرسومي
أثبت Xu وآخرون أن GCN القياسية أقل تعبيرية من اختبار Weisfeiler-Lehman، واقترحوا GIN التي تبلغ ذلك الحد الأعلى وتُعظّم القدرة التمييزية.
2020
الشبكات العصبية الرسومية لاكتشاف الأدوية
نماذج مبنية على GCN تتنبأ بخصائص الجزيئات عبر تمثيل الذرات كعُقد والروابط الكيميائية كأضلاع في الرسم البياني، مما يُسرّع الغربلة الافتراضية في الأبحاث الصيدلانية.

الإسهام الأبقى لـ GCN ليس رقماً على لوحة نتائج — بل هو إثبات أن الرسوم البيانية نوع بيانات من الدرجة الأولى في التعلم العميق. قبل هذه الورقة، كانت أساليب الرسوم البيانية متخصصة ومكلفة. بعدها، أصبحت الشبكات العصبية الرسومية أداة أساسية في عدّة الباحث، طبيعية كـالالتفاف للصور و للتسلسلات.

المرجعKipf, Welling. Semi-Supervised Classification with Graph Convolutional Networks. ICLR, 2017.

مصطلحات هذه الورقة

الشبكات العصبية الرسومية (البيانية)Graph Neural Network (GNN)
الالتفاف الرسوميGraph Convolution
التعلم شبه المُوجَّهSemi-Supervised Learning
مصفوفة التجاورAdjacency Matrix
لابلاسيان الرسم البيانيGraph Laplacian
المجال الطيفيSpectral Domain
تمرير الرسائلMessage Passing
الإفراط في التنعيمOver-Smoothing
حيلة إعادة التسويةRenormalization Trick
تصنيف العُقدNode Classification