السَّمْت

Graph Representation Learning2014متوسط10 دقيقة قراءة

DeepWalk: تعلّم التمثيلات الاجتماعية عبر الإنترنت

DeepWalk: Online Learning of Social Representations

Perozzi, B. · Al-Rfou, R. · Skiena, S. — KDD

المشكلة

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

الإسهام

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

الأثر

كان DeepWalk أول بحث يُثبت أنّ أدوات النمذجة اللغوية تصلح لتعلّم تمثيلات ذات معنى للشبكات. فتح هذا العمل مجال تعلّم تمثيلات الشبكات بالكامل، وألهم مباشرةً Node2Vec (بجولاته المنحازة) وLINE (بنمذجته الصريحة للقرب المباشر وغير المباشر) وGraphSAGE (بقدرته على التعميم لعُقَد لم يرها من قبل). ثنائية «الجولات العشوائية + Skip-gram» صارت القالب الذي بُني عليه جيل كامل من أساليب الشبكات. واليوم، كل شبكة عصبية بيانية مدينة مفاهيمياً لملاحظة DeepWalk الأساسية: أنماط الجوار المحلي في الشبكات تتصرّف كسياقات الكلمات في اللغة.

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

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

المشكلة: الشبكات غنية بالمعلومات لكنها لا تتوافق مع التعلّم الآلي

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

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

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

الملاحظة المحورية: الجولات العشوائية جُمَل

الفكرة المركزية في DeepWalk تقوم على تشبيه بسيط لكنه عميق: الجولة العشوائية القصيرة على الشبكة تشبه جملة في لغة طبيعية. في الجملة، الكلمات المتجاورة تتشارك السياق والمعنى. وفي الجولة العشوائية، العُقَد المتجاورة تتشارك الجوار البنيوي.

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

افتح في المختبر
قارن بين تكرار العُقَد في الجولات العشوائية (يساراً) وتكرار الكلمات في نص طبيعي (يميناً). كلاهما يتبع توزيع قانون القوة.
تستيقظ التجربة عند وصولك…

الخوارزمية: خطوتان بسيطتان

ما يميّز DeepWalk هو بساطته. الخوارزمية بأكملها تتكوّن من مكوّنين فقط:

الخطوة الأولى — مولِّد الجولات العشوائية. لكل عقدة vv في الشبكة، أطلق γ\gamma جولة عشوائية بطول tt. في كل خطوة، ينتقل المتجوّل إلى جار يُختار عشوائياً بانتظام. الناتج هو مجموعة من تسلسلات العُقَد، تُماثل مجموعة جمل في نصّ طبيعي.

الخطوة الثانية — متعلِّم Skip-gram. عامِل كل جولة كجملة وكل عقدة ككلمة. لكل عقدة viv_i في الجولة، حاول التنبؤ بعُقَد سياقها — أي العُقَد الواقعة ضمن نافذة بحجم ww على جانبيها. يتعلّم النموذج تضميناً Φ(vi)∈Rd\Phi(v_i) \in \mathbb{R}^d لكل عقدة يُعظّم احتمال ظهور جيرانها في السياق.

افتح في المختبر
انقر على عقدة لبدء جولة عشوائية. راقب المتجوّل وهو يقفز إلى جيران عشوائيين ويولّد تسلسلاً — هذا التسلسل هو «الجملة» التي سيتعلّم منها نموذج Skip-gram.
تستيقظ التجربة عند وصولك…

دالة الهدف هنا مطابقة تماماً لما يستخدمه Skip-gram في Word2Vec. إذا كانت لدينا جولة عشوائية W={v1,v2,…,vt}W = \{v_1, v_2, \ldots, v_t\}، فإنّ DeepWalk يسعى لتعظيم:

L=1∣W∣∑i=1∣W∣∑−w≤j≤wj≠0log⁡Pr⁡(vi+j∣Φ(vi))\mathcal{L} = \frac{1}{|W|}\sum_{i=1}^{|W|} \sum_{\substack{-w \le j \le w \\ j \neq 0}} \log \Pr(v_{i+j} \mid \Phi(v_i))
دالة هدف Skip-gram للجولات العشوائية — لكل عقدة في الجولة، عظّم لوغاريتم احتمال رؤية عُقَد سياقها ضمن النافذة w. الرمز Φ(vᵢ) هو التضمين الذي نتعلّمه. يُحسب الاحتمال عبر softmax الهرمي المبني على شجرة هافمان للعُقَد.

حساب العادي على جميع العُقَد ∣V∣|V| في كل خطوة مكلف جداً. لذلك يلجأ DeepWalk إلى : تُرتَّب العُقَد في ثنائية، فيصبح حساب Pr⁡(vi+j∣Φ(vi))\Pr(v_{i+j} \mid \Phi(v_i)) بتكلفة O(log⁡∣V∣)O(\log |V|) فقط بدلاً من O(∣V∣)O(|V|). الفكرة أنّ احتمال كل عقدة يُفكَّك إلى سلسلة من القرارات الثنائية على طول المسار من جذر الشجرة إلى ورقتها.

Pr⁡(vj∣Φ(vi))=∏l=1⌈log⁡∣V∣⌉σ ⁣(bl⋅Φ(vi) ⁣⊤Ψl)\Pr(v_j \mid \Phi(v_i)) = \prod_{l=1}^{\lceil\log |V|\rceil} \sigma\!\bigl(b_l \cdot \Phi(v_i)^{\!\top} \Psi_l\bigr)
تفكيك softmax الهرمي — كل مسار في شجرة هافمان يمرّ بـ⌈log|V|⌉ قرار ثنائي. عند كل عقدة داخلية l، تحدد دالة السيني σ الاتجاه يساراً أو يميناً باستخدام تضمين العقدة Φ(vᵢ) ومعامل الشجرة Ψₗ. الرمز bₗ يأخذ القيمة +1 أو −1 حسب الاتجاه المتّخذ.
افتح في المختبر
انقر على عقدة مستهدفة لترى المسار عبر شجرة هافمان. كل عقدة داخلية قرار ثنائي — التكلفة الإجمالية O(log n) بدلاً من O(n).
تستيقظ التجربة عند وصولك…

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

لنجمع الآن كل ما سبق. يحتاج DeepWalk أربعة فقط:

  • dd — التضمين (عادةً 64 أو 128)
  • γ\gamma — عدد الجولات العشوائية لكل عقدة
  • tt — طول الجولة
  • ww — حجم نافذة Skip-gram

تعمل الخوارزمية على γ\gamma دورة. في كل دورة، تُخلَط العُقَد ثم تُولَّد جولة عشوائية بطول tt من كل عقدة. كل جولة تُمرَّر فوراً إلى متعلِّم Skip-gram الذي يُحدِّث التضمينات عبر . ولأنّ الجولات تُولَّد وتُستهلَك واحدة تلو الأخرى، فالذاكرة المطلوبة لا تتعدّى حجم الشبكة نفسها مع مصفوفة التضمينات.

افتح في المختبر
تتبّع مراحل DeepWalk خطوة بخطوة: الشبكة → الجولات العشوائية → نوافذ Skip-gram → تحديث التضمينات.
تستيقظ التجربة عند وصولك…
الشيفرة الوصفية لـ DeepWalk بلغة Pythonpython

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

import random
# الخطوة 1: مولّد الجولات العشوائية def random_walk(graph, start_node, walk_length):
    walk = [start_node]
    for _ in range(walk_length - 1):
        neighbors = graph.neighbors(walk[-1])
        walk.append(random.choice(list(neighbors)))
    return walk

# الخطوة 2: حلقة DeepWalk الرئيسية def deepwalk(graph, d=128, gamma=80, t=40, w=10):
    # تهيئة التضمينات عشوائياً
    embeddings = init_embeddings(graph.nodes, d)
    # بناء شجرة هافمان لـ softmax الهرمي
    tree = build_huffman_tree(graph.nodes)

    for _ in range(gamma):               # γ تكرارات
        nodes = list(graph.nodes)
        random.shuffle(nodes)             # خلط من أجل SGD
        for node in nodes:
            walk = random_walk(graph, node, t)
            skipgram_update(walk, embeddings, tree, w)

    return embeddings

خصائص جوهرية: القابلية للتوسّع والتعلّم الفوري

يتميّز DeepWalk بخاصيتين تفصلانه عن الأساليب السابقة لتضمين الشبكات:

القابلية للتوسّع. الجولات العشوائية قابلة للتوازي بطبيعتها — يمكنك تشغيل آلاف المتجوّلين في آنٍ واحد على أنوية معالج مختلفة. كذلك يستخدم متعلِّم Skip-gram انحداراً تدريجياً عشوائياً غير متزامن، ما يسمح لعدة خيوط بتحديث مصفوفة التضمينات دون أقفال. التعقيد الحسابي الكلي هو O(γ⋅∣V∣⋅t⋅(w⋅log⁡∣V∣))O(\gamma \cdot |V| \cdot t \cdot (w \cdot \log |V|))، أي خطّي في عدد العُقَد وعدد الجولات.

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

التجارب: التصنيف متعدد التسميات على الشبكات الاجتماعية

اختُبر DeepWalk على مهام متعدد التسميات للعُقَد في ثلاث شبكات اجتماعية: BlogCatalog (10 آلاف عقدة، 334 ألف ضلع، 39 تسمية)، وFlickr (80 ألف عقدة، 5.9 مليون ضلع، 195 تسمية)، وYouTube (1.1 مليون عقدة، 2.9 مليون ضلع، 47 تسمية). الهدف: استخدام التضمينات المُتعلَّمة لتدريب مصنِّف يتنبأ بالمجموعات التي تنتمي إليها كل عقدة.

شملت خطوط الأساس أساليب مثل التعنقد الطيفي وEdgeCluster وطرق لابلاس التي تحتاج الوصول إلى الشبكة كاملة. دُرِّب DeepWalk بمعاملات d=128d = 128 وγ=80\gamma = 80 وt=40t = 40 وw=10w = 10.

النتائج كانت لافتة. حتى مع توفّر 10% فقط من التسميات للتدريب، حسّن DeepWalk مقياس Micro-F1 بمقدار 5-10% فوق خطوط الأساس. بل إنه في بعض الحالات تفوّق باستخدام 40% من البيانات المسمّاة على خطوط أساس استخدمت 100% منها. وكانت المكاسب أوضح ما تكون حين شحّت التسميات — وهو تحديداً الوضع الذي تبرز فيه قيمة التمثيلات الجيدة.

افتح في المختبر
اسحب شريط نسبة التسميات لترى كيف تتّسع ميزة DeepWalk كلما شحّت البيانات المسمّاة. المنطقة المظلّلة هي تحسّن F1 مقارنة بأفضل خط أساس.
تستيقظ التجربة عند وصولك…

القيود وما جاء بعدها

رغم أثره الكبير، في DeepWalk قيود واضحة عالجتها الأعمال اللاحقة:

جولات منتظمة. الجولات العشوائية في DeepWalk تختار كل جار باحتمال متساوٍ، فلا يملك المتجوّل أي تفضيل بين استكشاف الجوار القريب (كالبحث بالعرض) أو التوغّل نحو أجزاء بعيدة من الشبكة (كالبحث بالعمق). Node2Vec (2016) عالج ذلك بإضافة معاملين pp وqq يتحكّمان في ميل الجولة نحو العودة أو الاستكشاف، ما يتيح مزيجاً قابلاً للضبط بين تشابه الجوار والتكافؤ البنيوي.

لا أوزان ولا اتجاه للأضلاع. يُعامل DeepWalk كل الأضلاع بالتساوي ودون اتجاه، بينما الشبكات الحقيقية كثيراً ما تحمل أضلاعاً موزونة أو موجَّهة (كأعداد المتابعين أو اتجاه الاقتباس).

فحسب. لا يستطيع DeepWalk توليد تضمينات لعُقَد لم يصادفها أثناء التدريب. عالج GraphSAGE (2017) هذا القيد بتعلّم دوال تجميع على سمات الجيران، مما يُمكّن من التعميم على عُقَد جديدة لم تُرَ من قبل.

تجاهل سمات العُقَد. يعتمد DeepWalk على بنية الشبكة فقط ويتجاهل أي سمات مرتبطة بالعُقَد (كالنصوص أو الصور أو الخصائص). البنى المعمارية اللاحقة تدمج الطبولوجيا وسمات العُقَد معاً.

الأثر: ثورة تضمين الرسوم البيانية

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

  1. 2014

    DeepWalk

    أول أسلوب يطبّق Skip-gram من Word2Vec على جولات عشوائية في الشبكات. أثبت أنّ تقنيات معالجة اللغة تصلح لتحليل الشبكات.

  2. 2015

    LINE

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

  3. 2016

    Node2Vec

    أضاف جولات عشوائية منحازة بمعامل العودة p ومعامل الداخل والخارج q، مما يتيح استكشافاً مرناً بين البنية المحلية والشاملة.

  4. 2017

    GraphSAGE

    انتقل من التعلّم الاستنتاجي إلى الاستقرائي. يتعلّم دوال تجميع على سمات الجيران، فيمكن تضمين عُقَد جديدة دون إعادة التدريب.

  5. 2017

    GCN (الشبكات الالتفافية البيانية)

    طبّق Kipf وWelling عمليات الالتفاف على الشبكات، فانتشرت السمات وتجمّعت عبر الجوار. هذا العمل يُعدّ بداية الشبكات العصبية البيانية الحديثة.

  6. 2018

    GAT (شبكات الانتباه البيانية)

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

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

المرجعPerozzi, Al-Rfou, Skiena. DeepWalk: Online Learning of Social Representations. KDD, 2014.

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