Invariant-Based Diagnostics for Graph Benchmarks

ملخص تقني: التشخيصات القائمة على الثوابت للمقارنات المرجعية للرسوم البيانية

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

المنهجية
يقترح المؤلفون إطار عمل تشخيصي يعتمد على "ثوابت الرسم البياني" (Graph Invariants): وهي واصفات هيكلية ثابتة التبديل، وغير مرتبطة بمهمة محددة، تعمل كـ "بصمات هيكلية" للرسوم البيانية. هذه الثوابت هي بدائل قابلة للحساب للبنية وتتطلب عدم وجود معاملات قابلة للتدريب.

• بناء الثوابت: تستخدم الدراسة مجموعة متنوعة من الثوابت، بما في ذلك مقاييس نظرية الرسم البياني الأساسية (مثل القطر، ورتبة الدورة)، والمقاييس القائمة على الإنتروبيا (مثل إنتروبيا فون نيومان)، والثوابت الهندسية والطوبولوجية (مثل التواء التحليل، وعدد التماثل)، والمؤشرات الجزيئية (مثل مؤشر وينر، ومؤشر بالابان). يتم دمج هذه العناصر في متجه سمات واحد لكل رسم بياني.
• النماذج: يستخدم المؤلفون عائلتين رئيسيتين من النماذج:
  1. مجموعات الأشجار المعززة بالتدرج (XGBoost): تُستخدم كمصنف أساسي للقواعد المرجعية القائمة على الثوابت. تم اختيار هذا الخيار عمداً لضمان الكفاءة الحسابية والتحسين المباشر للمعلمات عبر 26 مجموعة بيانات متنوعة.
  2. الشبكات العصبية للرسوم البيانية (GIN): تُستخدم في تجارب التعلم متعدد المهام لتحليل محاذاة التدرج والتباين الهيكلي.
• السيناريوهات التجريبية: تُطبق المنهجية في أربعة إعدادات تجريبية متميزة:
  1. تحليل القدرة التعبيرية: اختبار قدرة الثوابت على تمييز أزواج الرسوم البيانية غير المتماثلة في مجموعة بيانات BREC (الرسوم البيانية التي لا يمكن تمييزها بواسطة اختبار 1-Weisfeiler-Lehman).
  2. توصيف مجموعة البيانات: التعامل مع عضوية مجموعة البيانات كـ "مهمة تصنيف ميتا" لقياس التباين الهيكلي داخل وبين المجالات.
  3. التنبؤ بالأداء متعدد المهام: استقصاء الارتباط بين الاختلافات الهيكلية (المقاسة بدقة التصنيف الميتا القائمة على الثوابت) ومحاذاة التدرج/الأداء اللاحق في إعدادات التعلم متعدد المهام.
  4. المقارنة المرجعية: تقييم أربعة تكوينات للمدخلات — السمات القائمة على الجمع، والسمات القائمة على التجميع، والثوابت الكاملة، ومجموعة فرعية ذات قدرة تعبيرية دنيا من الثوابت — عبر 2ks 26 مجموعة بيانات لفصل أدوار السمات، وتمرير الرسائل، والقدرة التعبيرية، والبنية العالمية.

المساهمات الرئيسية والنتائج

1. القدرة التعبيرية للثوابت:

   • ثبت أن الثوابت أكثر قدرة تعبيرية من الشبكات العصبية التقليدية للرسوم البيانية في سياق مجموعة بيانات BREC. حيث يحقق مزيج بسيط من الثوابت (تحديداً مجموعة فرعية من أربعة) دقة بنسبة 73% في تمييز الأزواج غير المتماثلة، متفوقاً على معظم الأساليب القائمة على GNN ومماثلاً لأداء البنى الأكثر تعقيداً مثل N2.
   • يوضح المؤلفون أن القدرة التعبيرية العالية لا تتطلب المجموعة الكاملة من الثوابت؛ إذ يكشف الاختيار الجشع أن مجموعة فرعية صغيرة تكفي لالتقاط نفس القدرة التمييزية.

2. توصيف التباين الهيكلي:

   • تميز الثوابت مجموعات البيانات المرجعية الحالية بفعالية. حيث يحقق المصنف الميتا الذي يستخدم الثوابت دقة تبلغ حوالي 56% في تمييز 23 مجموعة بيانات من مجالات مختلفة وحوالي 93% في تمييز المجموعات داخل نفس المجال.
   • يشير هذا إلى وجود "انزياح في مجموعة البيانات" واضح، حيث تظهر الرسوم البيانية داخل نفس المجال بصمات هيكلية متميزة، مما يشير إلى أن المراجعات الحالية تفتقر إلى التجانس المطلوب للتعميم القوي.

3. التنبؤ بالأداء متعدد المهام:

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

4. التنافسية للنماذج القائمة على الثوابت:

   • تعد النماذج البسيطة القائمة على الثوابت (XGBoost المدرب على متجهات الثوابت) منافسة لنماذج الـ Transformer والأساليب المرجعية القائمة على تمرير الرسائل عبر 26 مجموعة بيانات، بل وتتفوق عليها في بعض الحالات.
   • بشكل ملحوظ، تجاوزت النماذج القائمة على الثوابت في مجموعات بيانات "Flow" أفضل النتائج المسجلة بفارق كبير.
   • تظهر الدراسة أن القدرة التعبيرية ليست المحرك الرئيسي للأداء التنبؤي. فالمجموعة الفرعية من الثوابت التي تمتلك نفس القدرة التعبيرية للمجموعة الكاملة غالباً ما تؤدي إلى أداء تنبؤي أقل، مما يشير إلى أن صلة الهيكل بمهام محددة أهم من قوة التمييز الخام.
   • في كثير من الحالات، يؤدي إضافة الثوابت إلى النماذج المرجعية القائمة على السمات إلى تحسين الأداء، ولكن بالنسبة لبعض المهام (مثل CIFAR10، الممثلة كشبكات بكسل)، لا تحقق الثوابت أي مكاسب، مما يشير إلى أن البنية تلعب دوراً هامشياً.

الأهمية والادعاءات
يفترض العمل أن القواعد المرجعية القائمة على الثوابت يجب أن تصبح المعيار لتقييم مقارنات الرسوم البيانية. يرى المؤلفون أن هذه القواعد المرجعية تؤدي وظيفتين حرجتين:

1. أداة تشخيصية: تساعد في تحديد ما إذا كانت مهمة معينة تتطلب حقاً بنية الرسم البياني. إذا كان نموذج بسيط قائم على الثوابت يؤدي بنفس مستوى نموذج GNN معقد، فقد لا تعتمد المهمة على المعلومات الهيكلية.
2. فحص المحاذاة: توفر "اختبار واقع" للكشف عن عدم المحاذاة بين النموذج والمهمة. إذا لم يتفوق نموذج معقد بشكل جوهري على نموذج مرجعي قائم على الثوابت، فإن العجز يعكس على الأرجح نقصاً في الضبط الدقيق أو فشلاً في استخراج بنية ذات معنى، وليس قصوراً أساسياً في البنية المعمارية.

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