ملخص تقني: العمليات الغاوسية من نوع ماتيرن على الرسوم البيانية (Matérn Gaussian Processes on Graphs)

بيان المشكلة

تُعد العمليات الغاوسية (GPs) إطار عمل متعدد الاستخدامات لتعلم الدوال المجهولة من خلال ترميز المعلومات المسبقة، مثل القابلية للتفاضل أو الدورية، عبر نواوات التغاير (covariance kernels). وبينما تُعد هذه العمليات راسخة في الفضاءات الإقليدية ($\mathbb{R}^d$)، فإن تطبيقها على الرسوم البيانية غير الموجهة (undirected graphs) يظل محدوداً. فالنواوات الإقليدية القياسية القائمة على المسافة الإقليدية غالباً ما تكون غير مناسبة للبيانات ذات البنية الرسومية (مثل شبكات الطرق)، حيث لا تضمن القرب المكلي ضمان التشابه الوظيفي بسبب قيود الاتصال.

تعتمد النهج الحالية للعمليات الغاوسية على الرسوم البيانية، مثل الحقول العشوائية الماركوفية الغاوسية (GMRFs)، على افتراضات ماركوفية تحد من مرونة النموذج. وبدلاً من ذلك، فإن مجرد استبدال المسافة الإقليدية بالمسافة الرسومية في النواوات المستقرة غالباً ما يفشل في إنتاج بنى تغاير محددة بدقة. ونتيجة لذلك، هناك نقص في وجود فئة مرنة ومؤسسة نظرياً من النواوات للرسوم البيانية تحاكي الخصائص الغنية لعائلة "ماتيرن" (Matérn) واسعة الاستخدام في الإعدادات الإقليدية.

المنهجية

يقترح المؤلفون إطار عمل لـ العمليات الغاوسية الماتيرنية للرسوم البيانية من خلال تعميم توصيف المعادلات التفاضلية الجزئية العشوائية (SPDE) لنواوات ماتيرن من الإعدادات الإقليدية والمنوعات الريمانية إلى إعداد الرسوم البيانية.

1. توصيف الـ SPDE على الرسوم البيانية

في الإعداد الإقليدي، تُعرف عمليات ماتيرن الغاوسية بأنها حلول لمعادلات SPDE تتضمن مؤثر لابلاتس (Laplacian operator) $\Delta$. وقد قام المؤلفون بتكييف ذلك عبر:

• تعريف لابلاتس الرسم البياني $\Delta = D - W$ (حيث $D$ هي مصفوفة الدرجة و $W$ هي مصفوفة التجاور) كنموذج منفصل للمؤثر السالب للابلاتس.
• استخدام الحساب الوظيفي (functional calculus) لتعريف المؤثرات على الرسم البياني. بالنسبة للدالة $\Phi$، يتم تعريف المؤثر $\Phi(\Delta)$ عبر التفكيك الطيفي لـ $\Delta = U\Lambda U^T$ كـ $\Phi(\Delta) = U\Phi(\Lambda)U^T$.
• صياغة عملية ماتيرن للرسم البياني كحل للمعادلة:
  $$\left( \frac{2\nu}{\kappa^2} + \Delta \right)^{\frac{\nu}{2}} f = W$$
  حيث $W$ هو متجه غاوسي قياسي (مشابه للضوضاء البيضاء)، و$\nu$ هو معامل النعومة، و$\kappa$ هو مقياس الطول.
• ينتج عن ذلك عملية غاوسية بمصفوفة دقة (مقلوب التغاير) معطاة بـ $\left( \frac{2\nu}{\kappa^2} + \Delta \right)^{\nu}$.

2. الخصائص الرئيسية

تُظهر النواوات الناتجة عدة خصائص متميزة:

• التناثر (Sparsity): بالنسبة للقيم الصحيحة لـ $\nu$ والرسوم البيانية المتناثرة، تكون مصفوفات الدقة متناثرة، مما يسمح بحسابات فعالة تشبه GMRFs.
• التباين غير الموحد: على عكس النواوات الإقليدية المستقرة، يختلف التباين القبلي لعمليات ماتيرن للرسوم البيانية عبر الرؤوس، اعتماداً على البنية العالمية للرسم البياني (مثل أوقات العودة للمسارات العشوائية) وليس فقط درجات العقد المحلية.
• التقارب: تتقارب نواوات ماتيرن للرسوم البيانية نحو نواة الانتشار الرسومي (graph diffusion kernel) عندما $\nu \to \infty$. علاوة على ذلك، وتحت شروط انتظام مناسبة وتوزين للحواف، تتقارب هذه النواوات نحو نواوات ماتيرن الريمانية مع تحول الرسم البياني إلى تمثيل منفصل أدق للمنوع (manifold).

3. تقنيات التدريب القابلة للتوسع

لمعالجة التحديات الحسابية، يقترح البحث استراتيجيتين رئيسيتين للتدريب:

• تقريب سمات فوريه الرسومية (Graph Fourier Feature Approximation): يتم تقريب مصفوفة النواة باستخدام توسيع طيفي مبتور للابلاس الخاص بالرسم البياني. ويربط هذا العملية بنموذج انحدار خطي بايزي ذي سمات متعامدة، مما يسمح باستدلال فعال.
• مصفوفات الدقة المتناثرة: من خلال قصر قيمة $\nu$ على أعداد صحيحة صغيرة، يستغل المؤلفون تناثر مصفوفة الدقة، مما يسمح باستخدام خوارزميات استدلال GMRF الراسخة.
• الإعدادات غير المترافقة (Non-Conjugate Settings): للمهام مثل التصنيف حيث يكون التوزيع اللاحق غير غاوسي، يستخدم المؤلفون الاستدلال المتغير مزدوج العشوائية (doubly stochastic variational inference) باستخدام نقاط التحريض (inducing points). كما يناقشون استخدام متغيرات التحريض بين المجالات (interdomain inducing variables) باستخدام المتجهات الذاتية للنواة لتسريع التدريب بشكل أكبر.

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

1. تعريف نواوات ماتيرن للرسوم البيانية: يضع البحث تعريفاً صارماً لعمليات ماتيرن الغاوسية على الرسوم البيانية غير الموجهة عبر تعميم الـ SPDE، مما يوفر بديلاً مرناً للنواوات الرسومية الموجودة.
2. الخصائص النظرية: يثبت البحث أن هذه النواوات ترث الخصائص الجذابة من نظيراتها الإقليدية والريمانية، بما في ذلك التقارب نحو نواوات المنوع والارتباط بالمسارات العشوائية.
3. الاستدلال القابل للتوسع: يوفر العمل تقنيات عملية لتدريب هذه النماذج على رسوم بيانية كبيرة، بما في ذلك تقريبات سمات فوريه وطرق الجبر الخطي المتناثرة المتوافقة مع أطر الاستدلال المتغير القياسية (مثل نقاط التحريض).
4. التحقق التجريبي: يتحقق المؤلفون من نهجهم عبر مهمتين مختلفتين: الاستكمال الاحتمالي لبيانات تدفق حركة المرور في شبكة طرق، والتصنيف متعدد الفئات في شبكة استشهاد علمية.

النتائج

يقيم المؤلفون عمليات ماتيرن الغاوسية المقترحة مقابل نواكات الرسوم البيانية الأخرى، بما في ذلك نواة الانتشار، ونواة المسار العشوائي، ونواة جيب التمام العكسي.

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

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

يزعم البحث أن عمليات ماتيرن للرسوم البيانية توفر إطار عمل مرناً، وقابلاً للتفسير، وعالي الأداء للتعلم على الرسوم البيانية. ومن خلال الاستفادة من توصيف الـ SPDE، يجسّر المؤلفون الفجوة بين تعلم المنوع المستمر وتعلم الرسم البياني المنفصل.

تكمن الأهمية في جعل العمليات الغاوسية للرسوم البيانية أكثر سهولة للممارسين:

• يمكن تدريبها باستخدام طرق قياسية (مثل نقاط التحريض، والاستدلال المتغير) بدلاً من الخوارزميات المخصصة.
• تدعم التدريب بنظام الدفعات الصغيرة (mini-batch) والإعدادات غير المترافقة (مثل التصنيف)، والتي كان من الصعب تنفيذها سابقاً للعمليات الغاوسية للرسوم البيانية.
• توفر طريقة مبدئية لاستبدال نواكات ماتيرن للمنوعات عندما يتم تمثيل المنوع الأساسي كرسم بياني (على سبيل المثال، مخرجات خوارزميات تعلم المنوع).

ويخلص المؤلفون إلى أن هذه التقنيات تهدف إلى إلهام تبني أوسع للعمليات الغاوسية في تطبيقات تعلم الآلة التي تتضمن بيانات ذات بنية رسومية.