حول التكافؤ بين اختبار تطابق الرسوم البيانية وتقريب الدوال باستخدام الشبكات العصبية الرسومية (GNNs)

حققت شبكات العصبونات الرسومية (GNNs) نجاحًا كبيرًا في التعامل مع البيانات ذات الهيكل الرسومي. وفي ضوء هذا النجاح، ازداد الاهتمام بدراسة قوة تعبيرها. هناك خطان من البحث يركزان على قدرة شبكات العصبونات الرسومية: الأول يدرس قدرتها على تقريب الدوال الثابتة تحت التبديل في الرسوم البيانية، والثاني يركز على قوتها كاختبارات للترابط الرسومي (isomorphism). يعمل بحثنا على ربط هذين المنظورين وإثبات مساواتهما. كما نطور إطارًا لقوة تعبير شبكات العصبونات الرسومية يدمج هذين المنظورين باستخدام لغة الجبر السيمائي (sigma-algebra)، من خلاله نقارن قوة التعبير لأنواع مختلفة من شبكات العصبونات الرسومية مع اختبارات الترابط الرسومي الأخرى. بشكل خاص، أثبتنا أن شبكة العصبونات الرسومية الثابتة من الدرجة الثانية (second-order Invariant Graph Network) لا تستطيع تمييز الرسوم البيانية المنتظمة غير المتطابقة التي لها نفس الدرجة. ثم، قمنا بتوسيع هذا الإطار إلى معمارية جديدة تُسمى Ring-GNN، والتي تنجح في تمييز هذه الرسوم البيانية وتحقيق أداء جيد على مجموعات بيانات حقيقية.