على العلاقة بين MPNN وGraph Transformer

أظهرت نموذج التحويل الرسومي (Graph Transformer - GT) مؤخرًا كنمط جديد لخوارزميات التعلم الرسومي، حيث تفوق نموذج الرسوم البيانية السابق المُسمى شبكة التمرير الرسومي (Message Passing Neural Network - MPNN) في عدة معايير تقييمية. أظهرت الدراسات السابقة (كيم وآخرون، 2022) أنه مع استخدام تضمين موقعي مناسب، يمكن لـ GT تقريب MPNN بدقة غير محدودة، مما يدل على أن GT لا يقل قوة عن MPNN. في هذا البحث، ندرس العلاقة العكسية ونُظهر أن MPNN المُزوّد بعقدة افتراضية (Virtual Node - VN)، وهي تقنية شائعة الاستخدام لكنها تفتقر إلى فهم نظري عميق، قادرة بالفعل على تقريب طبقة الانتباه الذاتي في GT بشكل غير محدود.بشكل خاص، نُظهر أولًا أن إذا اعتبرنا نوعًا معينًا من التحويلات الخطية، والمعروف بـ "المنفذ/المحول الخطي" (Performer/Linear Transformer) (كورومانسكي وآخرون، 2020؛ كاثاروبولوس وآخرون، 2020)، فإن MPNN + VN بعمق ثابت O(1) وعرض ثابت O(1) يمكنه تقريب طبقة الانتباه الذاتي في هذا النموذج. ثم، من خلال ربط MPNN + VN مع نموذج DeepSets، نُثبت أن MPNN + VN بعرض O(n^d) وعمق O(1) يمكنه تقريب طبقة الانتباه الذاتي بدقة غير محدودة، حيث يمثل d بعدًا ميزة الإدخال. أخيرًا، ضمن بعض الافتراضات، نُقدّم بناءً صريحًا لنموذج MPNN + VN بعرض O(1) وعمق O(n) قادر على تقريب طبقة الانتباه الذاتي في GT بدقة غير محدودة.من الناحية التجريبية، نُظهر أن: 1) MPNN + VN يُعد أساسًا مُدهش القوة، حيث يتفوق على GT في مجموعة بيانات LRGB (مقياس الرسوم البيانية طويلة المدى) التي تم اقتراحها حديثًا؛ 2) يُحسّن MPNN + VN أداء النسخة المبكرة من النموذج على طيف واسع من مجموعات بيانات OGB؛ 3) يتفوق MPNN + VN على كل من المحول الخطي (Linear Transformer) وMPNN في مهمة نمذجة المناخ.