كم هي قوية شبكات العصب الرسمية؟

شبكات العصبونات الرسومية (GNNs) هي إطار فعّال لتعلم تمثيل الرسوم البيانية. تتبع شبكات العصبونات الرسومية مخطط تجميع الجوار، حيث يتم حساب متجه التمثيل لعقدة من خلال تجميع وتغيير متجهات التمثيل للعقد المجاورة لها بشكل متكرر. قد تم اقتراح العديد من نسخ شبكات العصبونات الرسومية وحققت نتائجًا رائدة في مهام تصنيف العقد والرسوم البيانية. ومع ذلك، على الرغم من ثورة شبكات العصبونات الرسومية في تعلم تمثيل الرسوم البيانية، فإن الفهم المحدود لخصائصها التمثيلية وقيودها لا يزال قائماً. هنا، نقدم إطارًا نظريًا لتحليل قوة التعبير عن شبكات العصبونات الرسومية في التقاط مختلف الهياكل الرسمية. تحدد نتائجنا القوة التمييزية لأنواع شائعة من شبكات العصبونات الرسومية مثل شبكات الالتفاف الرسومي (Graph Convolutional Networks) وGraphSAGE، وتبين أن هذه الأنواع لا تستطيع تعلم كيفية تمييز بعض الهياكل البسيطة للرسوم البيانية. ثم نطور بنية بسيطة يمكن إثبات أنها الأكثر تعبيرًا بين فئة شبكات العصبونات الرسومية وأنها بنفس قوة اختبار الاشتقاق البنيوي لـ Weisfeiler-Lehman للرسوم البيانية. نتحقق من صحة نتائجنا النظرية بشكل تجريبي على عدد من مقاييس تصنيف الرسوم البيانية، ونظهر أن نموذجنا يحقق أداءً رائدًا في هذا المجال.