شبكات عصبية مسارات: شبكات عصبية رسمية تعبيرية ودقيقة

أصبحت الشبكات العصبية الرسومية (GNNs) في الآونة الأخيرة النهج القياسي لتعلم البيانات ذات الهيكل الرسومي. وقد ساهمت الدراسات السابقة في الكشف عن الإمكانات التي تتمتع بها هذه النماذج، لكنها كشفت أيضًا عن حدودها. للأسف، أُثبت أن الشبكات العصبية الرسومية القياسية محدودة من حيث القوة التعبيرية. فهذه النماذج ليست أقوى من خوارزمية ويسلفيلر-ليمان ذات البعد الواحد (1-WL) في التمييز بين الرسوم البيانية غير المتماثلة. في هذه الورقة، نقترح نموذجًا يُسمى الشبكات العصبية للمسارات (PathNNs)، الذي يُحدِّث تمثيلات العقد من خلال تجميع المسارات المنطلقة من العقد. ونستنتج ثلاث نسخ مختلفة من نموذج PathNN تقوم بتجميع مسارات قصيرة واحدة، وجميع المسارات القصيرة، وجميع المسارات البسيطة ذات الطول حتى K. ونُثبت أن نسختين من هذه النماذج أقوى بشكل صارم من خوارزمية 1-WL، كما نتحقق تجريبيًا من نتائجنا النظرية. ونجد أن PathNNs قادرة على التمييز بين أزواج من الرسوم البيانية غير المتماثلة التي لا يمكن تمييزها بواسطة 1-WL، في حين أن أقوى نسخة من PathNN قادرة حتى على التمييز بين رسوم بيانية لا يمكن التمييز بينها بواسطة 3-WL. كما تم تقييم النسخ المختلفة من PathNN على مجموعات بيانات تصنيف الرسوم البيانية وانحدار الرسوم البيانية، حيث تفوقت في معظم الحالات على الطرق الأساسية.