Graph Representation Learning2016متوسط12 دقيقة قراءة

node2vec: تعلُّم سمات قابلة للتوسُّع على الشبكات

node2vec: Scalable Feature Learning for Networks

Grover, A. · Leskovec, J. — KDD

المشكلة

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

الإسهام

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

الأثر

أظهر node2vec أنّ إستراتيجية جولة مرنة واحدة قادرة على التفوّق على الجولات المنتظمة في DeepWalk وعلى أسلوب LINE الجامد، محققاً تحسيناً يصل إلى 26.7% في و12.6% في . سرعان ما أصبح من أكثر أساليب الشبكات استشهاداً، وشكّل جسراً بين المقاربات الضحلة القائمة على الجولات والموجة اللاحقة من شبكات الرسوم البيانية العصبية مثل GraphSAGE. أفكاره الأساسية — التحكّم بأخذ العيّنات من الجوار وتركيب سمات الأضلاع من متجهات العُقد — تحوّلت إلى مبادئ تصميم راسخة في مجال تعلّم تمثيلات الشبكات.

تخيّل أنّ الشبكة مدينة. DeepWalk يستكشفها كسائح يرمي عملة معدنية عند كل تقاطع — كل اتجاه باحتمال متساوٍ، بلا تفضيل لشارع مألوف ولا لزقاق مجهول.

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

بضبط هذين المؤشرين، يستطيع المستكشف نفسه أن يرسم خريطة للأزقة الضيقة المتلاصقة أو يكتشف أنّ محورين بعيدين يلعبان الدور ذاته في حركة المدينة.

المشكلة: الجولات الجامدة تُضيع البنية

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

DeepWalk (2014) حقّقت نقلة نوعية حين عاملت على الشبكة وكأنّها «جُمَل» والعُقد وكأنّها «كلمات»، ثم غذّتها لنموذج من . لكنّ جولاتها منتظمة — في كل خطوة يختار الماشي جاراً عشوائياً باحتمال متساوٍ. الأمر أشبه باستكشاف مدينة بلا خريطة وبلا ذاكرة: لا توجيه نحو التفاصيل المحلية ولا نحو البنية الشاملة.

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

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

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

انقر على عقدة وقارن بين بحث العرض أولاً (يبقى في الجوار ويكشف الأدوار البنيوية) وبحث العمق أولاً (يتوغل بعيداً ويكشف المجتمعات). لا أحدهما وحده يعطيك الصورة كاملة.

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

نوعان من التشابه: التجانس مقابل التكافؤ البنيوي

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

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

معظم الشبكات الحقيقية تُظهر النوعين معاً. في شبكة تفاعل بروتين-بروتين مثلاً، بعض البروتينات تساعد جيرانها المباشرين (تجانس) بينما أخرى تؤدي وظائف مكمِّلة من مواقع بعيدة (تكافؤ بنيوي). الجولة الجامدة لا تخدم الاثنين — لكنّ الجولة القابلة للضبط تستطيع.

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

بدِّل بين عرض التجانس وعرض التكافؤ البنيوي. نفس الشبكة لكن بتلوين مختلف — لأنّ كل إستراتيجية جولة تكشف نوعاً مختلفاً من التشابه.

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

الحل: جولة عشوائية منحازة بمؤشرين

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

تخيّل أنّ الماشي انتقل للتوّ من العقدة t إلى العقدة v، والآن يريد اختيار العقدة التالية x من جيران v. يعتمد على المسافة بين t (العقدة السابقة) وx (العقدة المرشحة):

إذا كانت x = t (أي الرجوع للخلف): الوزن 1/p. قيمة p مرتفعة تثبّط التراجع وتدفع للأمام، وقيمة p منخفضة تشجّع البقاء محلياً.
إذا كانت x جارة لـ t أيضاً (البقاء على نفس المسافة): الوزن 1.
إذا لم تكن x جارة لـ t (الابتعاد أكثر): الوزن 1/q. قيمة q مرتفعة تثبّط الابتعاد وتُبقي الجولة محلية كبحث العرض، وقيمة q منخفضة تشجّع التوغل كبحث العمق.

هذه هي الآلية بأكملها: مُعاملان، ثلاث حالات، ومرونة غير محدودة بين بحث العرض وبحث العمق.

\alpha_{pq}(t, x) = \begin{cases} \frac{1}{p} & \text{if } d_{tx} = 0 \\ 1 & \text{if } d_{tx} = 1 \\ \frac{1}{q} & \text{if } d_{tx} = 2 \end{cases}

انحياز البحث α — بوصلة الجولة — المقدار d_tx يمثّل أقصر مسافة بين العقدة السابقة t والعقدة المرشحة x. أمّا احتمال الانتقال غير المُقيَّس فهو π_vx = α_pq(t,x) · w_vx. لا توجد سوى ثلاث حالات لأنّ x بالضرورة جارة لـ v.

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

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

اسحب شريطَي p وq وراقب كيف يتغيّر سلوك الجولة. قيم منخفضة للمُعاملين = استكشاف عميق، قيم مرتفعة = أخذ عيّنات محلية مركّزة.

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

دالة الهدف: تعظيم ترجيح الجوار

بعد توليد الجولات، يعاملها node2vec بالضبط كما يعامل Word2Vec الجُمل. لكل عقدة u نريد من تضمينها f(u) أن يتنبّأ بالعُقد التي ظهرت في جوارها المُستمَدّ من الجولة N_S(u). دالة الهدف تُعظّم اللوغاريتم الاحتمالي لرصد هؤلاء الجيران، مشروطاً بمتجه سمات العقدة المصدر.

فرضيتان تجعلان المسألة قابلة للحل عملياً. الأولى هي الاستقلال الشرطي: احتمال ظهور كل جار مستقل عن البقية ما دام f(u) معلوماً. والثانية هي التناظر: احتمال كون العقدة n_i جارة لـ u يعتمد على f(n_i) · f(u) بعد تمريره عبر . وهذه بالضبط بنية نموذج Skip-gram.

\max_{f} \sum_{u \in V} \left[ -\log Z_u + \sum_{n_i \in N_S(u)} f(n_i) \cdot f(u) \right]

دالة هدف Skip-gram مُكيَّفة للرسوم البيانية — Z_u هي دالة التقسيم الخاصة بكل عقدة (وتُقرَّب عملياً بأخذ العيّنات السلبية). f(u) هو التضمين ذو d بُعداً للعقدة u. الجولات هي التي تحدد الجوار المنحاز N_S(u).

السلسلة الكاملة: من الرسم البياني إلى التضمينات

يعمل node2vec عبر ثلاث مراحل متتالية، وكل منها قابلة للتنفيذ المتوازي بسهولة:

المرحلة 1 — المعالجة المسبقة. نحسب احتمالات الانتقال المنحازة π_vx لكل ضلع، بناءً على p وq وبنية الشبكة. يُجرى هذا الحساب مرة واحدة مسبقاً باستخدام جداول حتى تستغرق كل خطوة لاحقة في الجولة زمناً ثابتاً O(1).

المرحلة 2 — محاكاة الجولات. من كل عقدة u نُطلق r جولة عشوائية بطول l. في كل خطوة نختار العقدة التالية في O(1) عبر الجداول المحسوبة مسبقاً، فنحصل على r · |V| تسلسل جولة.

المرحلة 3 — الأمثَلة. نُمرّر الجولات إلى نموذج Skip-gram مع ، مع تحديد حجم k وبُعد التضمين d. تُحسَّن المُعامِلات بـ لحقبة واحدة.

النتيجة: مصفوفة بأبعاد |V| × d، حيث الصف u هو التضمين ذو d بُعداً للعقدة u.

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

تابع المراحل الثلاث لـ node2vec — المعالجة المسبقة، محاكاة الجولات، الأمثَلة.

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

ضبط p وq: المفاضلة بين الاستكشاف والاستغلال

أناقة node2vec تكمن في أنّ p وq يخلقان طيفاً متصلاً بين نقيضين:

p = 1، q = 1 → جولة عشوائية منتظمة — DeepWalk بالضبط. بلا أيّ انحياز.
p مرتفع، q مرتفع → سلوك شبيه ببحث العرض. الماشي يتجنّب التراجع ويتجنّب الابتعاد، فيتأرجح بين الجيران المباشرين. هذا يلتقط التكافؤ البنيوي — العُقد التي تتشابه في نمط اتصالها المحلي تحصل على تضمينات متقاربة.
p منخفض، q منخفض → سلوك شبيه ببحث العمق. الماشي مستعدّ للتراجع ومتحمّس للتوغل، فيُنتج جولات بعيدة المدى تلتقط التجانس — العُقد في نفس المجتمع تحصل على تضمينات متقاربة.

عملياً، تُضبط قيم p وq عبر بحث شبكي على جزء صغير من البيانات الموسومة (قد لا يتجاوز 10%)، ما يجعل node2vec أسلوباً شبه مُوجَّه.

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

اسحب p وq على الشبكة ثنائية الأبعاد وراقب تغيُّر عناقيد التضمينات. أعلى اليسار = تركيز على التجانس، أسفل اليمين = تركيز على التكافؤ البنيوي.

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

تضمينات الأضلاع: من متجهات العُقد إلى التنبؤ بالروابط

node2vec يتعلّم للعُقد المفردة، لكنّ كثيراً من المهام — وبخاصة التنبؤ بالروابط — تتعلّق بـأزواج من العُقد. فكيف نحصل على تضمين لضلع (u, v)؟

الفكرة بسيطة: نركّب f(u) وf(v) بعملية ثنائية. جرّب node2vec أربعة خيارات: المتوسط عنصراً بعنصر، جداء هادامار (عنصراً بعنصر)، مسافة L1 الموزونة، ومسافة L2 الموزونة. ومن بين هذه الخيارات تفوّق جداء هادامار — أي ضرب المتجهين بُعداً ببُعد — بأداء أفضل وأكثر ثباتاً على مختلف الشبكات.

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

g(u, v) = f(u) \odot f(v) \quad \text{where } [f(u) \odot f(v)]_i = f_i(u) \cdot f_i(v)

جداء هادامار — أفضل مُعامل لتضمين الأضلاع — كل بُعد في تضمين الضلع ناتج عن ضرب البُعد المقابل من العقدتين. بهذا الشكل تُلتقط أنماط التفاعل: الأبعاد التي تكون فيها كلتا العقدتين نشطتين تُسهم بالقدر الأكبر.

الفكرة في شيفرة برمجية

الجولة العشوائية المنحازة في node2vec — الآلية الجوهريةpython

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

import numpy as np
from collections import defaultdict

def compute_transition_probs(G, prev, curr, p, q):
    """احسب احتمالات الانتقال المنحازة من curr بمعرفة prev."""
    neighbors = list(G[curr])
    probs = []
    for x in neighbors:
        if x == prev:          # تراجع: المسافة 0
            probs.append(1.0 / p)
        elif x in G[prev]:     # جار لـ prev أيضاً: المسافة 1
            probs.append(1.0)
        else:                  # ابتعاد أكثر: المسافة 2
            probs.append(1.0 / q)
    probs = np.array(probs)
    return probs / probs.sum()  # تسوية

def node2vec_walk(G, start, length, p, q):
    """حاكِ جولة عشوائية منحازة واحدة بالطول المحدد."""
    walk = [start]
    if length == 1:
        return walk
    # الخطوة الأولى: اختيار منتظم بين الجيران
    first = np.random.choice(list(G[start]))
    walk.append(first)
    for _ in range(length - 2):
        curr = walk[-1]
        prev = walk[-2]
        probs = compute_transition_probs(G, prev, curr, p, q)
        nxt = np.random.choice(list(G[curr]), p=probs)
        walk.append(nxt)
    return walk

# بعد توليد الجولات، غذّها لنموذج Skip-gram من Word2Vec
# مع أخذ عيّنات سلبية — تماماً كما في DeepWalk، لكن
# بجولات أذكى. مُعاملتا p وq هما الفرق الوحيد.

قابلية التوسّع: ملايين العُقد في ساعات

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

أخذ العيّنات البديلة لاختيار العقدة التالية في زمن ثابت O(1) خلال الجولات.
إعادة استخدام الجولات: جولة بطول l تبدأ من العقدة u تولّد في الوقت نفسه جواراً لكل عقدة وسيطة فيها، فتتوزّع التكلفة.
الانحدار التدريجي العشوائي اللامتزامن مع أخذ عيّنات سلبية في مرحلة الأمثَلة، ممّا يتجنّب حساب المكلفة في softmax.

المراحل الثلاث — المعالجة المسبقة ومحاكاة الجولات والأمثَلة — كلها قابلة للتنفيذ المتوازي، وعملياً تعمل كل مرحلة في مجموعة خيوط مستقلة.

النتائج: المرونة تنتصر

اختُبر node2vec على مهمّتين أساسيتين: التصنيف متعدد التسميات (على BlogCatalog وPPI وWikipedia) والتنبؤ بالروابط (على Facebook وPPI وarXiv). أبرز ما أظهرته النتائج:

على BlogCatalog، حقق node2vec بإعدادات p=0.25 وq=0.25 تحسيناً قدره 22.3% في Macro-F1 على DeepWalk، وأكثر من 229% على LINE.
على Wikipedia، تفوّق بنسبة 21.8% على DeepWalk حين اكتشف أنّ شبكة التوارد اللفظي تستفيد من مزج الاستكشاف العميق بالمحلّي (p=4, q=0.5).
على PPI، كان الإعداد الأفضل (p=4, q=1) شبه مطابق للجولة المنتظمة في DeepWalk، ما يؤكد أنّه حين تكون الجولات المنتظمة هي الأنسب، ينزلق node2vec بسلاسة إليها بلا خسارة.
في التنبؤ بالروابط، حقق node2vec مع جداء هادامار تحسيناً يصل إلى 12.6% في مقارنة بأفضل معيار إرشادي (Adamic-Adar) على شبكة تعاون arXiv.

أظهرت الخوارزمية كذلك متانة أمام الأضلاع المفقودة والمُشوَّشة، حيث انخفض Macro-F1 بشكل خطي فقط مع إزالة الأضلاع.

الصورة الأكبر: من السمات اليدوية إلى شبكات الرسوم البيانية العصبية

2013
DeepWalk
طبّق بيروزي وزملاؤه نموذج Skip-gram من Word2Vec على جولات عشوائية منتظمة فوق الشبكات. كان أول أسلوب قابل للتوسّع لتضمين الشبكات، لكن جولاته تفتقر لأي آلية توجيه.
2015
LINE
تعلّم تانغ وزملاؤه التضمينات بأخذ عيّنات من جوار الخطوة الواحدة والخطوتين كلاً على حدة. سريع لكنه بحث عرض جامد لا يتجاوز نطاق خطوتين.
2016
node2vec
قدّم غروفر وليسكوفيك الجولات المنحازة بمُعاملَي p وq، ما أتاح الانتقال السلس بين بحث العرض وبحث العمق. تفوّقت على DeepWalk وLINE في مختلف المهام والمجالات.
2017
GraphSAGE
تجاوز هاميلتون ويينغ وليسكوفيك التضمينات القائمة على الجولات نحو تجميع الجوار القابل للتعلّم — أول شبكة رسوم بيانية عصبية استقرائية تستطيع تضمين عُقد لم تُشاهَد من قبل.
2017
GCN (كيبف ووِلينغ)
طبّقت شبكات الالتفاف على الرسوم البيانية التفافات طيفية بقاعدة انتشار بسيطة من طبقة لأخرى، وفتحت الباب أمام شبكات الرسوم البيانية العصبية الشاملة.
2020
شبكات الرسوم البيانية العصبية تنتشر
دخلت شبكات الرسوم البيانية العصبية مجالات اكتشاف الأدوية وأنظمة التوصية وكشف الاحتيال على نطاق واسع. كثير من هذه الأنظمة لا يزال يعتمد جولات على نمط node2vec للتدريب المسبق أو كمعايير مرجعية.

يقف node2vec في موقع محوري ضمن مسيرة : فقد أثبت أنّ إستراتيجية أخذ العيّنات لا تقل أهمية عن نموذج التضمين ذاته. هذه الرؤية — أنّ الطريقة التي ترى بها سياق العقدة تحدد ما تتعلّمه عنها — انتقلت مباشرةً إلى آلية تجميع الجوار في GraphSAGE وإلى الموجة الأوسع من .

المرجعGrover, Leskovec. node2vec: Scalable Feature Learning for Networks. KDD, 2016.

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