فهم الازدحام الزائد والقيود في الرسوم البيانية من خلال الانحناء

تُستخدم معظم شبكات التعلم العصبي الرسومية (GNNs) نموذج نقل الرسائل، حيث يتم نقل ميزات العقد على الرسم البياني المدخل. أشارت أعمال حديثة إلى تشويه المعلومات التي تتدفق من العقد البعيدة باعتباره عاملًا يحد من كفاءة نقل الرسائل في المهام التي تعتمد على التفاعلات على مسافات طويلة. ويُعرف هذا الظاهرة بـ"الضغط الزائد" (over-squashing)، وقد تم تفسيرها بشكل تجريبي على أنها ناتجة عن "ممرات ضيقة" في الرسم البياني، حيث يزداد عدد الجيران على بعد $k$ خطوات بشكل سريع مع زيادة $k$. نقدم وصفًا دقيقًا لظاهرة الضغط الزائد في شبكات التعلم العصبي الرسومية، ونحلل كيف تنشأ هذه الظاهرة من الممرات الضيقة في الرسم البياني. ولتحقيق ذلك، نُقدّم منحنى توليفيًا جديدًا يعتمد على الحواف، ونُثبت أن الحواف ذات المنحنيات السلبية هي المسؤولة عن مشكلة الضغط الزائد. كما نقترح ونختبر تجريبيًا طريقة لإعادة توصيل الرسم البياني تعتمد على المنحنيات لتخفيف ظاهرة الضغط الزائد.