تحسين تعبير الشبكة العصبية الرسومية من خلال عد التماثل الجزئي للرسومات

على الرغم من أن الشبكات العصبية الرسومية (GNNs) حققت نتائج مميزة في مجموعة واسعة من التطبيقات، كشفت دراسات حديثة عن عيوب مهمة في قدرتها على استكشاف البنية الأساسية للرسم البياني. وقد أُثبت أن القوة التعبيرية للشبكات العصبية الرسومية القياسية محدودة باختبار التماثل الرسومي ويسفيلر-ليمان (WL)، مما يرث منه قيودًا مثبتة، مثل عدم القدرة على اكتشاف وحساب البنى الفرعية للرسم البياني. من ناحية أخرى، هناك أدلة تجريبية قوية، مثل تلك التي تظهر في علوم الشبكات والبيولوجيا الحسابية، تشير إلى أن البنى الفرعية غالبًا ما تكون مرتبطة بشكل وثيق بالمهام النهائية. وللإجابة على هذا التحدي، نقترح ما يُعرف بـ "شبكات البنية الفرعية للرسم البياني" (GSN)، وهي خوارزمية تبادل الرسائل مُستندة إلى ترميز البنية الفرعية، وتتميّز بالوعي بالبنية الطوبولوجية. ونُحلّل نظريًا قوة التعبير في معمارية لدينا، ونُظهر أن قوتها التعبيرية تفوق اختبار WL بشكل صارم، ونُقدّم شروطًا كافية لتحقيق الكونية (universality). وبشكل مهم، لا نسعى إلى الالتزام بالهرمية المتبعة في اختبار WL، مما يسمح لنا بالحفاظ على العديد من الخصائص الجذابة للشبكات العصبية الرسومية القياسية، مثل المحلية (locality) وتعقيد الشبكة الخطي، في حين نكون قادرين على التمييز بين حالات صعبة جدًا لتماثل الرسوم البيانية. أجرينا تقييمًا تجريبيًا موسّعًا على مهام تصنيف وانحدار الرسوم البيانية، وحققنا نتائج متميزة على مستوى الحالة الحالية (state-of-the-art) في بيئات واقعية متنوعة، تشمل الرسوم البيانية الجزيئية والشبكات الاجتماعية. يُمكن الوصول إلى الكود مفتوح المصدر عبر الرابط: https://github.com/gbouritsas/graph-substructure-networks.