ملخص تقني: طريقة تقسيم النطاق بأسلوب AdaGrad بمستويين للتدريب القابل للتوسع لشبكات الرسم البياني العصبية (GNNs)

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

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

• خطوات تحسين مكلفة: تتطلب عملية تمرير الرسائل (MP) تجميع المعلومات عبر بنية الرسم البياني بأكملها.
• متطلبات ذاكرة عالية: تتطلب عملية الانتشار العكسي (Backpropagation) تخزين تمثيلات العقد والارتباطات الوسيطة، وهو ما يتناسب مع $O(L |V| d')$ مع عمق الشبكة $L$، وحجم الرسم البياني $|V|$، وعرض الطبقة الخفية $d'$.
• عبء الاتصالات: في الإعدادات الموزعة، تسبب هياكل الرسم البياني غير المنتظمة وتوزيع درجات العقد غير المتساوي اختلالًا في توازن عبء العمل وتعيق التداخل بين الاتصال والحوسبة، مما يجعل تكاليف المزامنة غالبًا هي العامل المهيمن في وقت التدريب.

تعمل الحلول الحالية، مثل أخذ عينات العقد/الطبقات أو تقسيم الدفعات الصغرى القائم على المخططات الفرعية (مثل Cluster-GCN و GraphSAINT)، على إعادة تنظيم أو تقريب الحسابات، ولكنها قد تغير دالة الخسارة أو تفشل في معالجة بنية الاعتماد العالمي بشكل كامل. وبينما تُعد طرق تقسيم النطاق (Domain Decomposition - DD) معيارًا في حل المعادلات التفاضلية الجزئية (PDEs)، فإن تطبيقها على تدريب GNN كآلية مسبقة غير خطية (nonlinear preconditioning) للمحسنات لا يزال غير مستكشف بشكل كافٍ.

2. المنهجية

يقترح المؤلفون خوارزميتين جديدتين، DD-AG2m و 2DD-AG2m، تقومان بتكييف محسن AG2m (وهو متغير من AdaGrad معزز بمعلومات الانحناء من الدرجة الثانية والزخم) مع إطار عمل تقسيم النطاق.

2.1 المحسن الأساسي: AG2m

الأساس هو AG2m، وهو طريقة تحسين خالية من دالة الهدف (OFFO). تعمل هذه الطريقة دون الحاجة لتقييم صريح لدالة الهدف، بالاعتماد على التدرج ومعلومات تقريب الهيسيان (Hessian). وتشمل الميزات الرئيسية ما يلي:

• أوزان AdaGrad: يتم تحديث الأوزان لكل إحداثي $w_k$ بناءً على مربعات التدرجات المتراكمة لتحديد أنصاف أقطار منطقة الثقة (TR) التكيفية.
• معلومات الانحناء: يتم حساب خطوة حجم $\gamma_k$ من الدرجة الثانية باستخدام تقريب الهيسيان $B_k$ لضبط مقياس اتجاه التدرج المبتور.
• الزخم (Momentum): يتم دمج حد الزخم لتسريع التقارب، بحيث يكون محددًا بحدود منطقة الثقة.

2.2 تقسيم النطاق أحادي المستوى (DD-AG2m)

يعامل DD-AG2m الرسم البياني المدخل $G=(V, E)$ كنطاق يجب تقسيمه.

• التقسيم: يتم تقسيم مجموعة العقد $V$ إلى $P$ من النطاقات الفرعية المنفصلة $\{V_1, \dots, V_P\}$، مما ينتج عنه مخططات فرعية $G_p$. يتم حذف الحواف بين النطاقات لضمان التحسين المحلي.
• تدفق الخوارزمية:
  1. الخطوة العالمية: يقوم AG2m بإجراء $K_G$ من الخطوات على الرسم البياني الكامل $G$ لنشر المعلومات العالمية.
  2. خطوات النطاق الفرعي: بالتوازي، يقوم AG2m بإجراء $K_p$ من الخطوات على كل مخطط فرعي $G_p$ باستخدام دالات خسارة محلية $L_p$. يبدأ التحسين من المعلمات العالمية ويستخدم أوزان AdaGrad العالمية للحد من أحجام الخطوات الأولية (لضمان الاتساق).
  3. التجميع: يتم حساب متوسط التصحيحات المحلية $s^p_k = \theta^p_k - \theta_{global}$ وتطبيقها لتحديث النموذج العالمي.
• الآلية: ينظر هذا النهج إلى تقسيم الرسم البياني كمحسن مسبق غير خطي، مما يسمح بعمليات تحسين محلية مستقلة يتم التوفيق بينها دوريًا مع الحالة العالمية.

2.3 تقسيم النطاق ثنائي المستوى (2DD-AG2m)

لتقليل تكلفة الخطوات العالمية المتسلسلة بشكل أكبر، يقدم 2DD-AG2m مستوى خشنًا (coarse level).

• التقليص (Coarsening): يتم إنشاء رسم بياني خشن $G_C$ عن طريق أخذ عينات عشوائية من العقد داخل كل نطاق فرعي. يتم إسقاط مصفوفة التجاور عبر إسقاط غاليركين (Galerkin projection) حيث $A_C = R A R^\top$، و $R$ هو مؤثر التقييد.
• تدفق الخوارزمية: تتناوب التكرارات الخارجية بين:
  1. خطوات عالمية على الرسم البياني الدقيق.
  2. خطوات خشنة على الرسم البياني المختصر $G_C$ (باستخدام نفس بنية GNN ولكن مع العمل على بيانات مخفضة).
  3. خطوات النطاق الفرعي المتوازية على التقسيمات الدقيقة.
• الفائدة: تنقل الخطوات الخشنة المعلومات العالمية بتكلفة حسابية أقل بكثير من خطوات الرسم البياني الكامل، مما يعمل كمسرع متعدد المستويات.

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

1. إطار عمل DD جديد لـ GNNs: يقدم البحث أول تطبيق لطرق تقسيم النطاق المصممة خصيصًا لتدريب GNN، حيث يصيغ تقسيم الرسم البياني كآلية تحسين مسبق لمحسن AdaGrad.
2. خوارزميات DD-AG2m و 2DD-AG2m: يقترح المؤلفون ويفصلون خوارزميتين تجمعان بين خطوات التحسين العالمية والخشنة والنطاق الفرعي. ويضمنان الاتساق باستخدام أوزان AdaGrad العالمية للحد من الخطوات المحلية وتجميع التصحيحات عبر المتوسط.
3. القابلية للتوسع والكفاءة: تم تصميم الطرق لاستغلال التوازي في حسابات النطاق الفرعي مع الحفاظ على التماسك العالمي، مما يعالج اختناقات الاتصال والذاكرة في تدريب GNN الموزع القياسي.

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

قيم المؤلفون الطرق على ثلاثة اختبارات متنوعة:

• CIFAR10 (تصنيف الرسم البياني): رسوم بيانية تعتمد على "النقاط الفائقة" (Super-pixel) باستخدام GCN.
• AirfRANS (انحدار العقد): بيانات ديناميكا السوائل الحسابية (CFD) باستخدام GraphSAGE.
• METR-LA (التنبؤ الزماني المكاني): بيانات حركة المرور باستخدام DCRNN.

النتائج الرئيسية:

• تقليل التكلفة الحسابية: تحقق طرق DD المقترحة نفس الأداء التنبئي لنموذج AG2m المرجعي بـ 4 إلى 8 مرات أقل من خطوات التحسين (مقاسة بخطوات الرسم البياني العالمي المكافئة).
• تحسين الأداء: بالنسبة لتكلفة حسابية ثابتة، تحسن DD-AG2m و 2DD-AG2m الأداء التنبئي بنسبة تصل إلى 22% مقارنة بـ AG2m المرجعي.
• القابلية للتوسع: لا يتدهور أداء DD-AG2m مع زيادة عدد التقسيمات $P$، مما يثبت القابلية للتوسع الخوارزمي.
• ميزة المستويين: يتضح عمومًا أن 2DD-AG2m يتقارب بشكل أسرع من DD-AG2m في مراحل التدريب المبكرة ويحقق دقة نهائية أعلى في CIFAR10، مما يؤكد فائدة الخطوات الخشنة.
• تأثير الزخم: أدى تضمين الزخم (AG2m مقابل AG2) إلى تحسين التقارب باستمرار عبر جميع المهام.

5. الأهمية والادعاءات

يزعم البحث أن الطرق المقترحة تقدم تقدمًا كبيرًا في التدريب القابل للتوسع لـ GNNs من خلال:

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

يخلص المؤلفون إلى أنه بينما التنفيذ الحالي يعمل على جهاز واحد (باستخدام عقد GPU)، فإن المنهجية تعد مرشحًا قويًا لتطبيقات الذاكرة الموزعة لتحقيق تسريع في زمن التنفيذ (wall-clock speedups). كما حددوا أعمالًا مستقبلية في تداخل النطاقات الفرعية، واستراتيجيات التقليص البديلة، والنسخ غير المتزامنة.