الشبكات العصبية الرسومية المضمنة

إن نجاح شبكات العصب الرسومية (GNN) في تصنيف الرسوم البيانية مرتبط ارتباطًا وثيقًا بخوارزمية Weisfeiler-Lehman (1-WL). من خلال تجميع خصائص العقد المجاورة بشكل متكرر إلى عقدة مركزية، يحصل كل من 1-WL و GNN على تمثيل للعقدة يشفر شجرة جذرية حول العقدة المركزية. يتم بعد ذلك تجميع هذه التمثيلات الشجرية الجذرية إلى تمثيل واحد لتمثيل الرسم البياني بأكمله. ومع ذلك، فإن التمثيلات الشجرية الجذرية محدودة في قدرتها على تمثيل رسم بياني غير شجري. لمعالجة هذا الأمر، نقترح شبكات العصب الرسومية المضمنة (NGNNs). تقوم NGNN بتمثيل الرسم البياني باستخدام الرسوم البيانية الفرعية الجذرية بدلاً من الأشجار الفرعية الجذرية، بحيث يكون الرسمان البيانيان اللذان يشتركان في العديد من الرسوم البيانية الفرعية المتطابقة (بدلاً من الأشجار الفرعية) أكثر تشابهًا في تمثيليهما. المفتاح هو جعل كل تمثيل للعقدة يشفر رسمًا بيانيًا فرعيًا حولها أكثر من شجرة فرعية. لتحقيق هذا، تستخرج NGNN رسمًا بيانيًا فرعيًا محليًا حول كل عقدة وتطبق GNN أساسية على كل رسم بياني فرعي لتعلم تمثيل للرسم البياني الفرعي. يتم الحصول على التمثيل الكامل للرسم البياني بعد ذلك بتجميع هذه التمثيلات الرسومية الفرعية. نقدم تحليلًا نظريًا دقيقًا يظهر أن NGNN أقوى بكثير من 1-WL. بشكل خاص، أثبتنا أن NGNN يمكنها تمييز معظم الأشكال r-منتظمة، حيث تفشل 1-WL دائمًا. بالإضافة إلى ذلك، على عكس شبكات العصب الرسومية الأخرى الأكثر قوة، فإن NGNN تضيف تعقيد زمني أعلى بمقدار ثابت فقط مقارنة بشبكات GNN القياسية. تعد NGNN إطار عمل يمكن استخدامه بسهولة مع مختلف شبكات GNN الأساسية. قمنا باختبار NGNN مع شبكات GNN الأساسية المختلفة على عدة مجموعات بيانات مرجعية. تحسن NGNN أدائها بشكل موحد وتظهر أداءً تنافسيًا للغاية على جميع المجموعات البيانات.