Mini-Batch Class Composition Bias in Link Prediction

إليك ملخص تقني مفصل لورقة البحث بعنوان "تحيز تكوين الدفعة الصغيرة في التنبؤ بالروابط" (Mini-Batch Class Composition Bias in Link Prediction).

1. بيان المشكلة

تتناول الورقة فجوة حرجة بين مهام التنبيد بالروابط (Link Prediction) وتصنيف العقد (Node Classification) في الشبكات العصبية الرسومية (GNNs).

• الحدس: يُفترض عموماً أن نماذج GNN المدربة على التنبؤ بالروابط يجب أن تتعلم تمثيلات رسومية متسقة مع تلك التي تتعلمها لمهام تصنيف العقد. يستند هذا إلى فرضية أنه في الرسوم البيانية المتجانسة (homophilic graphs) -حيث تتصل العقد ذات الفئات المتشابهة- فإن الأنماط الهيكلية المستخدمة للتنبؤ بالروابط يجب أن تشفر بطبيعتها معلومات فئة العقد.
• الواقع: يوضح المؤلفون أن هذا الحدس غالباً ما يفشل في الممارسة العملية. فالعديد من نماذج التنبؤ بالروابط الشائعة تفشل في تعلم ميزات ذات معنى لفئات العقد. بدلاً من ذلك، تتعلم استدلالاً (heuristic) تافهاً يعتمد على الدفعة الصغيرة (mini-batch)، وهو أمر تتيحه طبقات التطبيع الدفعي (Batch Normalization - BN).
• آلية الفشل: يقوم تدريب التنبؤ بالروابط القياسي ببناء دفعات صغيرة ذات نسبة ثابتة من الروابط الإيجابية (الموجودة) والسلبية (غير الموجودة) (عادةً 50/50). تقوم طبقة التطبيع الدفعي (BN) بحساب الإحصائيات (المتوسط والتباين) عبر الدفعة. وبما أن توزيع الفئات ثابت، فإن طبقة BN تسمح للنموذج بـ "الغش" عبر تعلم خريطة بسيطة بناءً على تكوين الدفعة بدلاً من طوبولوجيا الرسم البياني الفعلية أو ميزات العقد. يؤدي هذا إلى تضخم مقاييس الأداء (مثل Hits@K) التي لا تعكس فهماً حقيقياً للخصائص الأساسية للرسم البياني.

2. المنهجية

أ. التحليل النظري للتحيز

قام المؤلفون باشتقاق رياضي لكيفية تسهيل التطبيع الدفعي لهذا التحيز:

1. في دفعة صغيرة قياسية تحتوي على $K_+$ من الروابط الإيجابية و $K_-$ من الروابط السلبية (حيث $K_+ \approx K_-$)، تقوم طبقة BN بتطبيع التنشيطات بناءً على متوسط الدفعة $\mu = K_+/K$ والتباين $\sigma^2 = K_+K_-/K^2$.
2. هذا التطبيع يؤدي إلى انهيار جميع الروابط الإيجابية إلى قيمة ثابتة واحدة، وجميع الروابط السلبية إلى قيمة ثابتة أخرى داخل الدفعة.
3. يمكن للتحويل الخطي اللاحق ($\gamma \hat{a} + \beta$) بسهولة فصل هاتين القيمتين الثابتتين، مما يسمح للنموذج بالتنبؤ بوجود الرابط بناءً فقط على تكوين الدفعة بدلاً من الميزات المتعلمة.

ب. الحل المقترح: التجميع المصحح للتحيز (Bias-Corrected Mini-Batching)

لإجبار النموذج على تعلم ميزات قوية (أي ميزات ذات صلة بفئة العقدة) بدلاً من استدلالات الدفعة، يقترح المؤلفون نظام تدريب جديد:

• تكوين فئات عشوائي: بدلاً من تثبيت نسبة الروابط الإيجابية إلى السلبية، يتم أخذ كسر الروابط الإيجابية ($p$) في كل دفعة صغيرة من توزيع منتظم: $p \sim U\{1, \dots, K-1\}$.
• الأثر: يضمن هذا التوزيع العشوائي أن إحصائيات الدفعة (المتوسط والتباين) التي تحسبها طبقة BN تتغير بشكل غير متوقع بين الدفعات. وبالتالي، يصبح قانون القرار القائم فقط على تكوين الدفعة غير مستقر وغير فعال، مما يجبر الشبكة على الاعتماد على ميزات الحواف وتضمينات العقد الفعلية لتقليل الخسارة.

ج. مقاييس التقييم

للتحقق من أن النماذج تتعلم ميزات فئة العقدة، قدم المؤلفون طرق تقييم محددة:

1. نسبة الأثر (Trace Ratio - TR): تُستخدم لقياس مدى قابلية فصل تضمينات الحواف بناءً على تسمية فئة العقدة المصدر. تشير نسبة TR الأعلى إلى توافق أفضل بين تمثيلات الحواف وفئات العقد.
2. تجميع تضمينات العقد (Node Embedding Aggregation): بما أن نماذج التنبؤ بالروابط تخرج تضمينات للحواف ($Z_2$)، يقوم المؤلفون بتجميعها مرة أخرى إلى العقد عن طريق متوسط تضمينات جميع الحواف المتصلة بعقدة معينة ($x'_v$).
3. التجميع و معلومات متبادلة (Clustering & NMI): يقومون بإجراء تجميع $k$-means على هذه التضمينات المجمعة للعقد ويقيسون المعلومات المتبادلة الموحدة (NMI) مقابل تسميات العقد الحقيقية. يشير NMI المرتفع إلى أن المتنبئ بالروابط قد تعلم تمثيلات مفيدة لتصنيف العقد.

3. المساهمات الرئيسية

1. تحديد تحيز خفي: كشفت الورقة أن نماذج التنبؤ بالروابط القياسية غالباً ما تستغل النسبة الثابتة للإيجابي/السلبي في الدفعات الصغيرة عبر التطبيع الدفعي، مما يؤدي إلى تعلم "طرق مختصرة" تتجاوز استخراج الميزات المعقدة.
2. إثبات نظري: توفير اشتقاق رياضي يوضح كيف تؤدي طبقات التطبيع الدفعي إلى انهيار التنشيطات إلى ثوابت تعتمد على الفئة عندما يكون تكوين الدفعة ثابتاً.
3. مخطط تدريب مصحح للتحيز: تقديم تعديل بسيط وغير مرتبط بالبنية (architecture-agnostic) (عن طريق عشوائية تكوين فئات الدفعة الصغيرة) والذي يلغي هذا الاستدلال.
4. التحقق التجريبي: إثبات أنه بينما قد يقلل هذا التصحيح قليلاً من دقة التنبؤ بالروابط الخام (Hits@K)، إلا أنه يحسن بشكل كبير من توافق التمثيلات المتعلمة مع ميزات فئة العقدة، مما يثبت أن النماذج كانت "تغش" سابقاً.

4. النتائج التجريبية

قيم المؤلفون ستة نماذج شائعة (BUDDY, ELPH, GCN, NCN, NEOGNN, GraphSAGE) عبر مجموعات بيانات متعددة (Cora, Citeseer, Pubmed, CS, Computers, Photo, ogbl-collab, ogbl-ppa).

• أداء التنبؤ بالروابط (Hits@100):

  • كما هو متوقع، أدى إزالة التحيز عموماً إلى انخفاض في درجات Hits@100.
  • مثال: في مجموعة بيانات ogbl-collab ، انخفض نموذج GCN من 42.0 إلى 16.3. وفي Computers ، انخفض نموذج BUDDY من 56.0 إلى 42.5.
  • التفسير: يؤكد هذا الانخفاض أن الأداء العالي الأصلي كان جزئياً بسبب الاستدلال القابل للاستغلال في الدفعة.

• توافق التمثيل (نسبة الأثر - Trace Ratio):

  • عبر جميع النماذج ومجموعات البيانات تقريباً، ارتفعت نسبة الأثر (TR) بشكل ملحوظ تحت مخطط التصحيح للتحيز.
  • مثال: في Cora ، ارتفعت TR لنموذج GCN من 0.039 إلى 0.165. وفي CS ، قفزت TR لنموذج BUDDY من 0.225 إلى 0.728.
  • التفسير: النماذج الآن تتعلم تمثيلات للحواف قابلة للفصل بشكل كبير حسب فئة العقدة.

• توافق تصنيف العقد (NMI):

  • عند تجميع تضمينات الحواف إلى العقد، تحسنت درجات NMI بشكل كبير مع تصحيح التحيز.
  • مثال: في CS ، ارتفع NMI لنموذج BUDDY من 0.218 إلى 0.621. وفي Cora ، ارتفع NMI لنموذج ELPH من 0.193 إلى 0.414.
  • التفسير: يؤكد هذا أن المتنبئات بالروابط، عندما تُدرب بشكل صحيح، يمكنها تعلم ميزات تنبؤية لفئات العقد، مما يدعم الحدس الأولي الذي كان محجوباً سابقاً بسبب التحيز.

• دراسة الاستئصال (Ablation Study):

  • عندما تمت إزالة طبقات التطبيع الدفعي تماماً، اختفت الفجوة في الأداء بين التدريب "الأصلي" و"المصحح للتحيز" (بقيت TR و Hits@K متشابهة). وهذا يؤكد أن التطبيع الدفعي هو المُمكّن للتحيز.

5. الأهمية والآثار المترتبة

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