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

قبل GNN: الميزات اليدوية ونوى الرسوم والتمثيلات السطحية

Before GNNs: Hand-crafted Features, Graph Kernels and Shallow Embeddings

يعرض الدرس الطرق التي سبقت الشبكات العصبية البيانية وما زالت خطوط أساس قوية: ميزات العقد اليدوية، ونوى الرسوم مثل Weisfeiler-Lehman، والتمثيلات السطحية بالمسارات العشوائية (DeepWalk وnode2vec)، ولماذا تجاوزتها GNN في التعميم ودمج الخصائص.

أسس الرسوم البيانيةمتوسط25 دقيقة قراءةالدرس 4 من 23

أهداف الدرس

  • بناء ميزات يدوية للعقد والروابط
  • فهم خوارزمية تلوين Weisfeiler-Lehman ونواتها
  • شرح DeepWalk وnode2vec وعلاقتهما بنموذج Skip-gram
  • تحديد قيود التمثيلات السطحية: التحويلية وعدم استخدام الخصائص

1 الميزات اليدوية

قبل التعلم العميق كان الباحث يصمم بنفسه ميزات تصف موقع العقدة في الرسم: الدرجة، ومعامل التجمع، والمركزيات، وعدد المثلثات، وعدّ الرسوم الصغيرة (Graphlets) حول العقدة. ولمهام الروابط استُخدمت مقاييس تشابه مثل عدد الجيران المشتركين ومعامل Jaccard ومؤشر Adamic-Adar. ثم تُغذّى هذه الميزات إلى مصنف تقليدي. ما زالت هذه المقاييس خطوط أساس صعبة في التنبؤ بالروابط، ويقارن بها مختبر التنبؤ بالروابط هنا.

\text{AA}(u,v)=\sum_{w\in N(u)\cap N(v)}\frac{1}{\log d_w}
مؤشر Adamic-Adar: الجار المشترك النادر (درجته صغيرة) أكثر دلالة من المحور الشائع.

2 اختبار Weisfeiler-Lehman ونواته

خوارزمية Weisfeiler-Lehman (1-WL) تعطي كل عقدة لوناً ابتدائياً (مثلاً حسب نوعها)، ثم تكرر: اللون الجديد لكل عقدة هو تجزئة (Hash) للونها الحالي مع المجموعة المتعددة (Multiset) لألوان جيرانها. بعد بضع تكرارات يصبح لون العقدة بصمة لجوارها. إذا اختلفت مدرجات الألوان بين رسمين فهما غير متشاكلين بالتأكيد؛ وإذا تطابقت فقد يكونان متشاكلين أو لا.

نواة WL (WL Subtree Kernel) تقارن رسمين بعدّ الألوان المشتركة عبر التكرارات، وكانت أقوى طريقة لتصنيف الرسوم قبل GNN. الأهم أن هذه الخوارزمية هي بالضبط ما تقلّده GNN القائمة على انتقال الرسائل، وسترى في درس قوة التعبير أن GIN تبلغ قوتها التمييزية.

c_v^{(t+1)} = \operatorname{HASH}\!\left(c_v^{(t)},\;\{\!\{c_u^{(t)} : u\in N(v)\}\!\}\right)
تحديث لون العقدة في 1-WL من لونها ومجموعة ألوان جيرانها المتعددة.
t = 0t = 1HASH
اختبار WL: كل عقدة تأخذ لوناً جديداً من لونها ولون جيرانها، حتى تستقر الألوان.

3 التمثيلات السطحية بالمسارات العشوائية

DeepWalk (2014) فكرته بسيطة: أطلق مسارات عشوائية قصيرة من كل عقدة، وعامل كل مسار كجملة وكل عقدة ككلمة، ثم درّب نموذج Skip-gram من word2vec ليتعلم متجهاً لكل عقدة بحيث تتنبأ العقدة بالعقد التي تظهر قربها في المسارات. العقد التي تتشارك سياقات المسارات تحصل على متجهات متقاربة.

node2vec (2016) عمّم ذلك بمسار عشوائي منحاز بمعاملين: p يتحكم في احتمال العودة إلى العقدة السابقة، وq يتحكم في الابتعاد. قيم q الصغيرة تجعل المسار يستكشف بعيداً (يشبه البحث بالعمق) فيلتقط مجتمعات العقد، وقيم q الكبيرة تبقيه قريباً (يشبه البحث بالعرض) فيلتقط الأدوار البنيوية.

\max_{\Phi}\sum_{v\in V}\sum_{u\in \mathcal{N}_{\text{walk}}(v)} \log \frac{\exp(\Phi_u^{\top}\Phi_v)}{\sum_{w\in V}\exp(\Phi_w^{\top}\Phi_v)}
هدف Skip-gram على المسارات: تعظيم احتمال سياق كل عقدة، ويُقرَّب المقام بأخذ عيّنات سلبية.
12345walk: 1 → 2 → 3 → 5skip-gramword2vecz1z2z3z4z5
التمثيلات الضحلة: مسارات عشوائية تُعامل جملاً، ثم Skip-gram يتعلم متجهاً لكل عقدة.

4 لماذا جاءت GNN؟

مع ذلك، تبقى التمثيلات السطحية مفيدة حين لا تتوفر خصائص، وكثيراً ما تُستخدم متجهات node2vec خصائص ابتدائية لنموذج GNN.

  • التمثيل السطحي جدول بحث: لكل عقدة متجه مستقل، فعدد المعاملات يساوي n×d ولا يمكن تمثيل عقدة جديدة دون إعادة التدريب (تحويلي).
  • لا يستخدم خصائص العقد (نصوص الأوراق، أنواع الذرات) إلا بإضافتها لاحقاً.
  • لا يتشارك المعاملات بين العقد، فلا يعمم إلى رسوم جديدة.
  • GNN تتعلم دالة مشفّرة (Encoder) مشتركة تأخذ الخصائص والجوار، فتعمل على عقد ورسوم جديدة.
from torch_geometric.nn import Node2Vec

model = Node2Vec(data.edge_index, embedding_dim=128, walk_length=20,
                 context_size=10, walks_per_node=10, p=1.0, q=0.5,
                 num_negative_samples=1, sparse=True)
loader = model.loader(batch_size=128, shuffle=True)
# p = q = 1 يعطي مسارات DeepWalk غير المنحازة

خلاصة الدرس

  • المقاييس اليدوية (Adamic-Adar وغيرها) خطوط أساس قوية للروابط
  • خوارزمية 1-WL هي الأصل النظري لانتقال الرسائل
  • DeepWalk وnode2vec يتعلمان متجهاً لكل عقدة من المسارات العشوائية
  • التمثيلات السطحية تحويلية ولا تدمج الخصائص، وهذا ما عالجته GNN

تحقّق من فهمك

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

ما أثر تصغير المعامل q في node2vec؟

يشجع المسار على الابتعاد عن العقدة البادئة (سلوك يشبه DFS)، فتلتقط المتجهات بنية المجتمعات.

إذا أعطت خوارزمية 1-WL مدرجين متطابقين لرسمين، هل هما متشاكلان؟

ليس بالضرورة؛ 1-WL شرط ضروري لا كافٍ، وهناك رسوم غير متشاكلة لا يميزها.

تابع التعلّم

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

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

طبّق في المختبر: مستكشف تمثيلات العقد

المراجع

  1. Perozzi, B., Al-Rfou, R., & Skiena, S. (2014). DeepWalk: Online Learning of Social Representations. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. DOI: 10.1145/2623330.2623732تمثيلات العقد بالمسارات العشوائية (ليست GNN).
  2. Grover, A., & Leskovec, J. (2016). node2vec: Scalable Feature Learning for Networks. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. DOI: 10.1145/2939672.2939754تعميم DeepWalk بمسارات منحازة (ليست GNN).
  3. Adamic, L. A., & Adar, E. (2003). Friends and neighbors on the Web. Social Networks. DOI: 10.1016/S0378-8733(03)00009-1مصدر مقياس Adamic-Adar.
  4. Liben-Nowell, D., & Kleinberg, J. (2007). The link-prediction problem for social networks. Journal of the American Society for Information Science and Technology. DOI: 10.1002/asi.20591دراسة مرجعية لمقاييس التشابه الكلاسيكية (Common Neighbors وJaccard وAdamic-Adar).
  5. 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.
  6. 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.