مختبر الخوارزميات
GNN Algorithms Lab
سبع خوارزميات أساسية: GCN وGraphSAGE وGAT وGIN وR-GCN وGAE وVGAE، لكل منها التعريف والفكرة والبنية والمعادلات بالعربية وآلية العمل والمميزات والقيود ومراجعها الأصلية، مع تجربة تُدرَّب فعلياً في متصفحك.
تختلف خوارزميات GNN أساساً في ثلاثة أسئلة: كيف نزن رسائل الجيران (ثابت أم متعلَّم)، وكيف نجمعها (مجموع أم متوسط أم انتباه)، وكيف نعامل أنواع الروابط. افتح صفحة أي خوارزمية لقراءة شرحها الكامل وتشغيلها على بيانات حقيقية صغيرة أو مصطنعة معلنة.
الخوارزميات
مقارنة سريعة بين الخوارزميات
مقارنة وصفية من محتوى المختبر. للمقارنة التجريبية بإعدادات متطابقة استخدم مختبر المقارنة.
| الخوارزمية | التجميع (Aggregation) | الانتباه (Attention) | العقد الجديدة | التعقيد |
|---|---|---|---|---|
| GCN | مجموع موزون بالتطبيع المتماثل | لا يوجد | الصيغة الأصلية تحويلية، لكن الأوزان W لا تعتمد على هوية العقدة، فيمكن تطبيقها على عقد جديدة إذا أُعيد حساب الم… | تقريباً O(|E|·F·F') لكل طبقة، حيث |E| عدد الروابط وF أبعاد الدخل وF' أبعاد الخرج، بفضل ضرب المصفوفات المتفرقة. |
| GraphSAGE | متوسط أو حد أقصى أو مجموع (قابل للاختيار) | لا يوجد | استقرائي بالتصميم: الدالة المتعلَّمة تُطبق على أي عقدة لها خصائص وجيران. | لكل عقدة O(∏_k S_k) حيث S_k حجم العيّنة في الطبقة k، مستقلة عن حجم الرسم. |
| GAT | مجموع موزون بالانتباه | نعم: انتباه متعدد الرؤوس على الجيران | استقرائي: معاملات الانتباه تُحسب من محتوى العقد، فتُطبق على رسوم جديدة. | O(|V|·F·F' + |E|·F') لكل رأس، مضروبة في عدد الرؤوس K. |
| GIN | مجموع (Sum) غير مطبّع | لا يوجد | استقرائي: الدوال نفسها تُطبق على أي رسم جديد. | O(|E|·F + |V|·F·F') لكل طبقة، مع MLP لكل عقدة. |
| R-GCN | متوسط لكل علاقة ثم جمع | لا يوجد | الأوزان مرتبطة بأنواع العلاقات لا بالعقد، فتُطبق على كيانات جديدة لها علاقات معروفة. | O(|R|·|E_r|·F·F') تقريباً، وتنخفض بالتحليل بالأساس. |
| GAE | مجموع موزون (GCN) | لا يوجد | المشفّر GCN، فيمكن تطبيقه على عقد جديدة إذا عُرفت خصائصها وروابطها. | المشفّر O(|E|·F·d)؛ تقييم k زوجاً O(k·d). |
| VGAE | مجموع موزون (GCN) | لا يوجد | كما في GAE. | ضعف تكلفة رأس GAE الأخير تقريباً، مع حساب KL الخطي في عدد العقد. |
مفاهيم هذه الوحدة
أسئلة شائعة
ما الفرق بين GCN وGraphSAGE؟
GCN يجمع الجيران مع العقدة نفسها بأوزان ثابتة من التطبيع ويحتاج الرسم كاملاً عادة. GraphSAGE يفصل تمثيل العقدة عن تجميع جيرانها (يدمجهما بالوصل)، ويدعم أخذ عينة من الجيران، فيصلح للرسوم الكبيرة وللتعميم على عقد جديدة لم ترها أثناء التدريب (التعلم الاستقرائي).
ماذا يضيف الانتباه في GAT؟
بدل أوزان ثابتة لكل جار، يتعلم GAT معاملاً لكل رابط من تمثيلي طرفيه (عبر softmax على الجيران)، فيمنح بعض الجيران أهمية أكبر. الرؤوس المتعددة تثبّت التعلم. معاملات الانتباه لا تساوي تفسيراً سببياً للقرار.
لماذا يُقال إن GIN أقوى نماذج انتقال الرسائل؟
أثبت Xu et al. (2019) أن قدرة نماذج انتقال الرسائل على التمييز بين الرسوم لا تتجاوز اختبار Weisfeiler-Lehman (WL)، وأن GIN، بتجميع بالمجموع ودالة تحديث MLP حقنية، يبلغ هذا الحد. المتوسط والحد الأقصى أضعف تمييزاً.
متى أستخدم R-GCN؟
حين تكون الروابط من أنواع متعددة يحمل كل منها معنى مختلفاً، كما في الرسوم المعرفية. يخصص R-GCN مصفوفة أوزان لكل علاقة، ويستخدم التفكيك الأساسي (Basis decomposition) لتقليل المعاملات عند كثرة العلاقات.
ما الفرق بين GAE وVGAE؟
GAE مشفر GCN ينتج تمثيلاً محدداً لكل عقدة، وفاكّ تشفير يحسب احتمال الرابط بـ sigmoid(z_i·z_j). VGAE يجعل التمثيل توزيعاً غاوسياً (متوسط وتباين) ويضيف حد KL إلى الخسارة، فيصبح نموذجاً احتمالياً توليدياً. على الرسوم الصغيرة الفرق بينهما غالباً ضمن التباين بين البذور.
لماذا أقارن دائماً بـ MLP؟
MLP يرى خصائص العقدة فقط ويتجاهل الرسم. إن لم يتفوق GNN عليه، فالرسم لا يضيف معلومة مفيدة للمهمة (أو هناك عدم تجانس). هذه المقارنة أبسط اختبار لقيمة البنية.
أي نموذج أبدأ به؟
ابدأ بـ GCN بطبقتين كخط أساس مع MLP. جرّب GraphSAGE إن كان الرسم كبيراً أو ستضاف عقد جديدة، وGAT إن كان للجيران أهمية متفاوتة، وGIN لتصنيف الرسوم، وR-GCN للعلاقات المتعددة، وGAE/VGAE للتنبؤ بالروابط دون تسميات.
كيف تصنّف GNN رسماً كاملاً؟
بعد طبقات انتقال الرسائل نجمع تمثيلات كل العقد في متجه واحد بدالة قراءة (Readout) مثل المجموع أو المتوسط أو الحد الأقصى، ثم نمرره إلى مصنف. كل رسم مثال تدريب مستقل، كما في MUTAG.
كل الخوارزميات تُدرَّب فعلياً في المتصفح بمصفوفات كثيفة، لذلك تعمل حتى بضع مئات من العقد. الأرقام المنشورة في الأوراق لا تُعرض إلا مع البيانات والإعداد والمصدر.
المراجع
- Kipf, T. N., & Welling, M. (2017). Semi-Supervised Classification with Graph Convolutional Networks. International Conference on Learning Representations (ICLR). arXiv: 1609.02907الورقة الأصلية لـ GCN ومصدر التطبيع المتماثل للمصفوفة.
- Hamilton, W. L., Ying, R., & Leskovec, J. (2017). Inductive Representation Learning on Large Graphs. Advances in Neural Information Processing Systems (NeurIPS). arXiv: 1706.02216الورقة الأصلية لـ GraphSAGE والتعلم الاستقرائي بالعيّنات من الجوار.
- Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., & Bengio, Y. (2018). Graph Attention Networks. International Conference on Learning Representations (ICLR). arXiv: 1710.10903الورقة الأصلية لـ GAT والانتباه متعدد الرؤوس على الجيران.
- 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.
- Schlichtkrull, M., Kipf, T. N., Bloem, P., van den Berg, R., Titov, I., & Welling, M. (2018). Modeling Relational Data with Graph Convolutional Networks. The Semantic Web (ESWC 2018), Lecture Notes in Computer Science, Springer. DOI: 10.1007/978-3-319-93417-4_38 · arXiv: 1703.06103الورقة الأصلية لـ R-GCN على رسوم المعرفة متعددة العلاقات.
- Kipf, T. N., & Welling, M. (2016). Variational Graph Auto-Encoders. NIPS Workshop on Bayesian Deep Learning. arXiv: 1611.07308الورقة الأصلية لـ GAE وVGAE في التنبؤ بالروابط.
- Chiang, W.-L., Liu, X., Si, S., Li, Y., Bengio, S., & Hsieh, C.-J. (2019). Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. DOI: 10.1145/3292500.3330925تدريب GCN على رسوم كبيرة بتقسيمها إلى عناقيد.
- Ying, Z., You, J., Morris, C., Ren, X., Hamilton, W., & Leskovec, J. (2018). Hierarchical Graph Representation Learning with Differentiable Pooling. Advances in Neural Information Processing Systems (NeurIPS). arXiv: 1806.08804تجميع هرمي قابل للتعلم لتصنيف الرسوم (DiffPool).
- Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., & Yu, P. S. (2021). A Comprehensive Survey on Graph Neural Networks. IEEE Transactions on Neural Networks and Learning Systems. DOI: 10.1109/TNNLS.2020.2978386مسح شامل لأنواع GNN وتطبيقاتها.
- Hamilton, W. L. (2020). Graph Representation Learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool. DOI: 10.2200/S01045ED1V01Y202009AIM046كتاب تعليمي شامل في تمثيل الرسوم وانتقال الرسائل.
