RAwR: Role-Aware Rewiring via Approximate Equitable Partition

ملخص تقني: RAwR: إعادة التوصيل الواعي بالأدوار عبر التقسيم المتساوي التقريبي

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

المنهجية
يقدم المؤلفون RAwR (إعادة التوصيل الواعي بالأدوار)، وهو إطار عمل فعال حاسوبياً ومستقل عن النموذج، يعمل على تعزيز الرسم البياني المدخل برسم بيوت (quotient graph) مشتق من التقسيمات المتساوية التقريبية (AEPs).

1. التقسيمات المتساوية التقريبية (AEPs):

   • يقوم التقسيم المتساوي بتجميع العقد التي لها نفس عدد الجيران في كل كتلة من كتل التقسيم. وهذا يستحث رسماً بيوياً (quotient graph) يلخص بدقة التفاعلات من دور إلى آخر.
   • يستخدم RAwR ما يسمى بـ $\epsilon$-AEP، والذي يخفف من شرط التكافؤ الدقيق من خلال معامل تسامح $\epsilon$. وهذا يسمح بتجميع العقد ذات الأدوار الهيكلية المتشابهة (ولكن غير المتطابقة)، مما يجعل النهج قوياً تجاه الضجيج في الرسوم البيانية الواقعية.
   • يتم حساب التقسيم بكفاءة باستخدام خوارزمية $\epsilon$-BE في وقت حدودي (polynomial time).

2. متغيرات إعادة التوصيل:
   بفرض وجود رسم بياني مدخل $G=(V, E)$ وتقسيم $\epsilon$-AEP مع مصفوفة مؤشر $R$ ومصفوفة quotient $Q$، يقوم RAwR بإنشاء مصفوفة تجاور معززة. تم اقتراح متغيرين محددين:

   • RepNodes: يربط كل عقدة أصلية بعقدة ممثلة افتراضية واحدة (VN) تتوافق مع دورها الهيكلي. هذا يخلق مسارات تواصل من خطوتين (two-hop) بين العقد المتباعدة طوبولوجياً ولكنها متشابهة هيكلياً. يتم ضبط مصفوفة الـ quotient لتكون صفراً ($Q=0$).
   • RepEdges: بالإضافة إلى ربط العقد بممثلاتها، يقوم هذا المتغير بربط العقد الممثلة (VNs) ببعضها البعض وفقاً للرسم البيوت غير الموزون ($\bar{Q}$)، مما يسمح بالتواصل بين الأدوار المتفاعلة.

3. الأساس النظري (تحليل المعلم والتلميذ):
   يستخدم البحث نموذج "المعلم والتلميذ" للشبكات العصبية الرسومية الخطية لتحليل تأثير إعادة التوصيل.

   • الافتراض: يتم توليد التسميات الحقيقية بواسطة "معلم" (GNN) يعمل على بنية كامنة (الرسم البياني المعزز بواسطة RAwR)، بينما يحاول "تلميذ" (GNN) التعلم من الرسم البياني الملحوظ.
   • الرفع الدور الطيفي (SRL): يشتق التحليل حداً أعلى لخطأ التلميذ، مما يؤدي إلى صياغة SRL، وهو مقياس معرف كالتالي: $\text{SRL} = \rho \sum_{j=1}^k \omega_j \Delta_j^2$. حيث يقيس $\rho$ طاقة التسميات في الفضاء الدورِي، وتمثل $\Delta_j$ الفرق في القيم الذاتية ذات الصلة بالدور بين الرسم البياني الأصلي والمعاد توصيله، و$\omega_j$ هي أوزان الأدوار.
   • الاختيار الاستدلالي: تم اقتراح استدلال عملي، $^* \text{SRL}$، لاختيار معامل التسامح الأمثل $\epsilon$. وهو يجمع بين SRL ومقياس تشابه فئة الجار من خطوتين (2NCS) لمراعاة الحالات التي قد لا تقع فيها التسميات بدقة في الفضاء الدورِي.

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

1. إطار عمل RAwR: طريقة جديدة لإعادة التوصيل توجه المعلومات عبر مسارات ذات معنى هيكلي (الأدوار الهيكلية) بدلاً من مجرد تحسين الانتشار العالمي. وهو يستعيد تقنية "العقدة الرئيسية" كحالة حدية (التقسيم المنهار كلياً)، ولكنه يوفر دقة قابلة للتحكم عبر $\epsilon$.
2. الدليل الهيكلي: إثبات أن RAW يقلل من متوسط المقاومة الفعالة للرسم البياني المدخل، مما يوفر دليلاً هيكلياً على أنه يخفف من اختناقات الانتشار بعيد المدى بشكل مستقل عن بنية الـ GNN المستخدمة.
3. التحليل النظري: اشتقاق رسمي باستخدام نموذج المعلم والتلميذ يوضح كيف تعدل إعادة التوصيل القائمة على الأدوار الاستجابة الطيفية لنماذج تمرير الرسائل. ويؤدي هذا إلى مقياس SRL لاختيار التقسيمات المثلى.
4. التكامل: تقديم دليل على أن RAwR ليس منافساً فقط للحلول على مستوى البنية (مثل GRAIN) المصممة لمعالجة الضغط الزائد، بل هو مكمل لها أيضاً، حيث يحسن الأداء بشكل أكبر عند تطبيقه فوق تلك النماذج.

النتائج التجريبية
قيم المؤلفون RAwR على مجموعة متنوعة من الاختبارات المعيارية، بما في ذلك الرسوم المتجانسة (مثل Cora, Citeseer)، وغير المتجانسة (مثل Chameleon, Squirrel)، والبيانات الاصطناعية بعيدة المدى (ECHO).

• الأداء: حقق RAwR أفضل متوسط رتبة بين طرق إعادة التوصيل المقارنة (بما في ذلك BORF, FOSR, SDRF, JDR, ComFy, TRIGON, و Master Node) عبر مهام تصنيف العقد.
• المكاسب في المهام بعيدة المدى وغير المتجانسة: لوحظت أهم التحسينات في مجموعات البيانات غير المتجانسة وبعيدة المدى (مثل ECHO)، حيث يكون تمرير الرسائل المحلي غير كافٍ. على سبيل المثال، في مجموعة بيانات ECHO "Caterpillar" بدون سمات العقد، تحسنت الدقة من 38.82% (الأساس) إلى 76.47% باستخدام RepNodes.
• دراسات الاستئصال (Ablation Studies):
  • RepNodes مقابل RepEdges: أداء RepNodes كان أفضل عموماً في الاختبارات الواقعية، مما يشير إلى أن التواصل السريع داخل الدور هو المصدر الرئيسي للتحسن.
  • التقسيمات العشوائية: بمقارنة RAwR مع التقسيمات العشوائية التي تحتوي على نفس عدد العقد الافتراضية، تبين أن المكاسب مدفوعة بتعيين الدور الهيكلي، وليس مجرد إضافة عقد افتراضية. تفوق RAwR على الضوابط العشوائية بمتوسط +3.66 نقطة مئوية.
  • استدلال $^* \text{SRL}$: نجح استدلال $^* \text{SRL}$ في اختيار قيم $\epsilon$ تنافسية، وكانت قريبة غالباً من أفضل نتائج البحث الشبكي (grid-search)، خاصة في البيانات الواقعية.

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

حافظ المؤلفون على نبرة متواضعة فيما يتعلق بالقيود:

• التقييم الحالي مقتصر على الرسوم البيانية غير الموجهة وغير الموزونة، رغم أن الـ AEPs يمكن تعريفها للحالات الموجهة والموزونة.
• يفترض اشتقاق SRL وجود شبكات GNN خطية تعمل كمرشحات حدودية (polynomial filters)؛ لذا قد يكون الاستدلال أقل فائدة للنماذج مثل GAT أو GIN التي لا تتوافق بسهولة مع هذا النموذج.
• التركيز التجريبي ينصب على تصنيف العقد؛ وترك التوسع في مهام تعلم الرسوم البيانية الأخرى للعمل المستقبلي.

باختصار، يوفر RAwR نهجاً مبنياً على الأدوار لإعادة توصيل الرسوم البيانية، مما يحسن أداء GNN في المهام بعيدة المدى وغير المتجانسة عن طريق تقليل المقاومة الفعالة ومواءمة تمرير الرسائل مع الأدوار الهيكلية.