تضمين الشبكة — Node2Vec، DeepWalk، LINE
- السنة
- 2014 (DeepWalk); 2016 (Node2Vec)
- النوع
- Representation learning / unsupervised network method
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
تضمين الشبكة هو عائلة من طرق تعلم التمثيل تقوم برسم كل عقدة في الرسم البياني إلى متجه كثيف منخفض الأبعاد مع الحفاظ على الخصائص الهيكلية للشبكة. تم تقنين هذا النهج لبيانات الشبكات الاجتماعية بواسطة بيروزي وآخرون في DeepWalk (2014)، والذي قام بتكييف نموذج Word2Vec skip-gram للمسارات العشوائية على الرسوم البيانية، وتم توسيعه بواسطة غروفر وليسكوفيك في Node2Vec (2016)، والذي قدم مسارًا عشوائيًا متحيزًا يوازن بين الاستكشاف واسع النطاق وعميق النطاق. هذه التضمينات تحول البيانات العلائقية إلى متجهات سمات يمكن لمصنفات التعلم الآلي القياسية وخوارزميات التجميع استهلاكها مباشرة.
الفكرة الحدسية وراء الطريقة
يتكون الرسم البياني من عقد وحواف، لكن معظم خوارزميات التعلم الآلي تتوقع جدولًا من الأرقام. تضمين الشبكة يحل مشكلة الترجمة. تمامًا كما يتعلم Word2Vec معاني الكلمات من خلال النظر إلى الكلمات التي تظهر بالقرب من بعضها البعض في الجمل، يتعلم DeepWalk معاني العقد من خلال النظر إلى العقد التي تظهر بالقرب من بعضها البعض في المسارات العشوائية عبر الرسم البياني. النتيجة هي إحداثي في فضاء متجهي - العقد المتشابهة هيكليًا أو التي تتم زيارتها بشكل متكرر تنتهي بالقرب من بعضها البعض. بمجرد أن يكون لكل عقدة متجه، يمكنك تغذية هذه المتجهات إلى مصنف، أو تجميعها باستخدام k-means، أو تصورها باستخدام UMAP، دون كتابة أي كود خاص بالرسم البياني.
التاريخ
تم تقديم فكرة تطبيق Word2Vec على البيانات ذات الهيكل البياني بواسطة بيروزي وآخرون في DeepWalk (KDD 2014)، والتي أظهرت أن المسارات العشوائية على رسم بياني اجتماعي يمكن أن تحل محل السمات المصممة يدويًا لتصنيف العقد. قام غروفر وليسكوفيك بتوسيع هذا في Node2Vec (KDD 2016) عن طريق تقديم مسار عشوائي متحيز من الدرجة الثانية يتم تحديده بالمعاملين p و q، مما يوفر تحكمًا صريحًا في المفاضلة بين الاستكشاف المجاور القائم على التجانس والقائم على التكافؤ الهيكلي. في نفس الفترة تقريبًا، اقترح تانغ وآخرون LINE (WWW 2015)، والذي يتعلم التضمينات عن طريق تحسين أهداف التقارب من الدرجة الأولى والثانية مباشرة بدلاً من المسارات العشوائية، مما يجعله مناسبًا للرسوم البيانية الكبيرة جدًا. معًا، أسست هذه الطرق الثلاث مجال تعلم تمثيل الشبكات وألهمت معماريات الشبكات العصبية البيانية اللاحقة.
متى تُستخدم
تضمين الشبكة مناسب عندما يكون لديك رسم بياني يحتوي على 50 عقدة على الأقل وتحتاج إلى سمات متجهية مستمرة للمهام اللاحقة مثل تصنيف العقد، أو التنبؤ بالروابط، أو تجميع العقد. تناسب الطريقة الرسوم البيانية غير الموزونة والموزونة، وتتعامل مع الهياكل الموجهة أو غير الموجهة. اختر DeepWalk عندما يكون خط الأساس البسيط للمسار العشوائي الموحد كافيًا. اختر Node2Vec عندما تريد ضبط التوازن بين التجانس والتكافؤ الهيكلي من خلال المعاملين p و q. إذا كنت بحاجة إلى تضمين عقد جديدة غير مرئية سابقًا في وقت الاستدلال دون إعادة التدريب، ففضل طريقة استقرائية مثل GraphSAGE؛ تضمين الشبكة في شكله القياسي استقرائي. الطريقة لا تتطلب سمات عقد موزعة طبيعيًا.
الحدود والاعتبارات
- استقرائي: لا يمكن للنموذج تضمين العقد التي لم تكن موجودة أثناء التدريب دون إعادة تدريب كاملة.
- حساسية المعاملات الفائقة: البعد التضميني، طول المسار، عدد المسارات، حجم النافذة، p، و q كلها تؤثر على جودة التضمين وتتطلب ضبطًا.
- المسارات العشوائية لا تلتقط بنية الرسم البياني ذات الرتب الأعلى (مثل، الحواف الفائقة أو الحواف متعددة العلاقات) دون توسيع.
- يتدهور الأداء على الرسوم البيانية الصغيرة جدًا (أقل من 50 عقدة) حيث تكون مجموعة المسارات متفرقة جدًا لتعلم إحصائيات موثوقة.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- يحول بيانات الرسم البياني العلائقية إلى متجهات ذات طول ثابت متوافقة مع أي خط أنابيب تعلم آلي قياسي.
- تسمح معاملات Node2Vec p و q للمحلل بضبط التوازن بين التضمينات الحساسة للمجتمع والحساسة للدور.
- يمكن دمج أوزان الحواف في احتمالات المسار، مما يلتقط قوة العلاقة دون خطوات نمذجة إضافية.
- يتوسع إلى الرسوم البيانية الكبيرة من خلال أخذ عينات فعالة للمسارات العشوائية وإجراء تدريب نموذج skip-gram.
التطبيقات
- تصنيف العقد في شبكات الاقتباس، أو المنصات الاجتماعية، أو رسوم بيانية للتفاعلات البيولوجية.
- التنبؤ بالروابط - تحديد الحواف المفقودة أو المستقبلية عن طريق مقارنة تشابه تضمينات العقد.
- اكتشاف المجتمعات عن طريق تجميع متجهات العقد باستخدام k-means أو الطرق الهرمية.
- اكتشاف الشذوذ - العقد التي تكون تضميناتها متطرفة في الفضاء المتجهي قد تمثل أدوارًا هيكلية غير عادية.
- أنظمة التوصية حيث يكون المستخدمون والعناصر عقدًا في رسم بياني ثنائي أو متعدد التفاعلات.
كيف يعمل
كيف يعمل
تبدأ العملية برسم بياني G حيث تكون العقد هي الكيانات وتمثل الحواف العلاقات. قد تكون الحواف موجهة أو غير موجهة وقد تحمل أوزانًا تؤثر لاحقًا على احتمالية الانتقال. إذا كانت أوزان الحواف موجودة، يتم تضمينها في احتمالات المسار؛ إذا كانت غائبة، تحصل جميع الحواف على وزن متساوٍ. في هذه المرحلة، يختار المحلل أيضًا متغير الخوارزمية - DeepWalk للمسارات العشوائية الموحدة، و Node2Vec للمسارات المتحيزة التي يتم التحكم فيها بالمعاملين p (العودة) و q (الداخل-الخارج)، أو LINE عندما يجب تعلم التقارب في الجوار من الدرجة الأولى والثانية بشكل منفصل. يعتمد الاختيار بين أنظمة معاملات Node2Vec على الخاصية المتوقعة للشبكة: التجانس (العقد المتشابهة تتصل، لذا يُفضل الاستكشاف واسع النطاق، q < 1) أو التكافؤ الهيكلي (العقد ذات الأدوار المتشابهة قد تكون بعيدة، لذا يُفضل الاستكشاف عميق النطاق، p < 1).
بدءًا من كل عقدة، تقوم الخوارزمية بمحاكاة سلسلة من المسارات العشوائية بطول ثابت (عادةً 30 خطوة) وتكررها عدة مرات (عادةً 200 مسار لكل عقدة). ينتج كل مسار تسلسلًا من معرفات العقد يشبه جملة من الكلمات. في DeepWalk، يتم اختيار العقدة التالية بشكل موحد من الجيران. في Node2Vec، يتم اختيار العقدة التالية وفقًا لاحتمالات الانتقال المتحيزة بواسطة p و q: يتم معاقبة العودة إلى العقدة السابقة بـ 1/p، ويبقى البقاء على نفس المسافة عند 1، ويتم التحكم في التحرك أبعد بـ 1/q. تشكل مجموعة كل المسارات مجموعة من تسلسلات العقد التي تشفر طوبولوجيا الرسم البياني.
يتم تغذية مجموعة تسلسلات العقد إلى نموذج skip-gram (نفس بنية Word2Vec). لكل عقدة في المسار، يتنبأ النموذج بعقد السياق المحيطة ضمن نافذة (عادةً 10 خطوات). من خلال الانحدار التدرجي العشوائي، يتعلم النموذج تمثيلًا متجهيًا كثيفًا ذا بعد ثابت - عادةً 64 أو 128 - لكل عقدة بحيث تكون العقد التي تتواجد معًا في المسارات لها متجهات متشابهة. البعد هو معامل فائق: الأبعاد الأكبر تلتقط المزيد من الهيكل ولكنها تزيد من الحساب والمخاطر من الإفراط في التخصيص على الرسوم البيانية الصغيرة.
بمجرد التدريب، يوفر النموذج متجه تضمين واحد لكل عقدة. تُستخدم هذه المتجهات كسمات لتصنيف العقد (تغذيتها إلى مصنف لوجستي أو عصبي)، أو التنبؤ بالروابط (مقارنة متجهات أزواج العقد المرشحة)، أو اكتشاف المجتمعات (تجميع المتجهات). التضمينات استقرائية: فهي ثابتة للعقد التي تمت رؤيتها أثناء التدريب. إذا كان يجب تضمين عقد جديدة بعد التدريب، فيجب استخدام طريقة استقرائية مثل GraphSAGE، حيث لا يمكن لنموذج Node2Vec أو DeepWalk القياسي التعميم على العقد غير المرئية دون إعادة التدريب.
الأخطاء الشائعة
- تطبيق نموذج Node2Vec على عقد جديدة لم تكن في الرسم البياني التدريبي - لن يكون لدى النموذج متجه لها؛ استخدم طريقة استقرائية (مثل GraphSAGE) عندما لا يكون التضمين الاستقرائي مقبولًا.
- استخدام القيم الافتراضية p=1، q=1 (مكافئ لـ DeepWalk) دون فحص ما إذا كانت الشبكة تتبع نمط التجانس أو التكافؤ الهيكلي - يمكن أن يؤدي ضبط p و q للنمط المتوقع إلى تحسين أداء المهمة اللاحقة بشكل كبير.
- معاملة البعد التضميني كثابت: على الرسوم البيانية الصغيرة، قد يؤدي البعد 64 أو 128 إلى الإفراط في التخصيص؛ ابدأ بقيمة أقل وتحقق من المهمة اللاحقة.
- تجاهل الحد الأدنى لمتطلبات العينة: الرسوم البيانية التي تحتوي على أقل من 50 عقدة تنتج مجموعات مسارات رقيقة جدًا لتدريب تضمينات موثوقة.
الأسئلة الشائعة
ما هو الفرق بين DeepWalk و Node2Vec و LINE؟
يستخدم DeepWalk المسارات العشوائية الموحدة ونموذج Word2Vec skip-gram - إنه أبسط خط أساس. يضيف Node2Vec مسارات عشوائية متحيزة يتم التحكم فيها بواسطة p و q، مما يسمح للمحلل بضبط ما إذا كان المسار يستكشف مثل البحث واسع النطاق (التجانس) أو البحث العميق (التكافؤ الهيكلي). LINE لا يستخدم المسارات العشوائية على الإطلاق؛ فهو يحسن أهداف التقارب من الدرجة الأولى والثانية مباشرة على قائمة الحواف، وهو أكثر قابلية للتوسع للرسوم البيانية الكبيرة جدًا ولكنه يضحي بإشارة الجوار القائمة على المسار.
كيف أختار معاملات p و q في Node2Vec؟
يتحكم p في احتمالية العودة إلى العقدة السابقة (p منخفض = تراجع أقل)، ويتحكم q في نصف قطر الاستكشاف (q < 1 يفضل الاستكشاف الخارجي، q > 1 يبقي المسار قريبًا من المصدر). إذا كنت تتوقع أن تكون العقد في نفس المجتمع متشابهة (التجانس)، اضبط q < 1 للسماح للمسار بالانتشار للخارج. إذا كنت تتوقع أن تكون العقد ذات الدور الهيكلي نفسه متشابهة حتى لو كانت بعيدة، اضبط p < 1 لتشجيع الاستكشاف العميق. تحقق من كلا النظامين على المهمة اللاحقة.
هل يمكنني تضمين عقد جديدة بعد التدريب دون إعادة تدريب النموذج بأكمله؟
Node2Vec و DeepWalk القياسي استقرائيان: مصفوفة التضمين تغطي فقط العقد التي تمت رؤيتها أثناء التدريب. للتعميم الاستقرائي على عقد جديدة غير مرئية سابقًا، استخدم طريقة شبكة عصبية بيانية استقرائية مثل GraphSAGE، والتي تتعلم دالة تجميع على جوار العقد يمكن تطبيقها على أي عقدة في وقت الاستدلال.
كم عدد الأبعاد التي يجب أن أستخدمها للتضمين؟
الاختيارات الأكثر شيوعًا هي 64 و 128، وهذه تعمل بشكل جيد للرسوم البيانية المتوسطة إلى الكبيرة. بالنسبة للرسوم البيانية الصغيرة (50-200 عقدة) ابدأ ببعد أقل (16 أو 32) لتجنب الإفراط في التخصيص، وقم بتقييم جودة التضمين عن طريق قياس أداء المهمة اللاحقة (مثل، دقة تصنيف العقد) بدلاً من خطأ إعادة البناء وحده.
طرق ذات صلة
المصادر
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 (KDD), 855-864.
افتح مرجع DOIتم النسخ.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 (KDD), 701-710.
افتح مرجع DOIتم النسخ.