ويسلر ولمان يصبحان عصبيين: شبكات عصبية للبيانات الرسمية من الرتبة الأعلى

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