SimGNN: نهج الشبكات العصبية لحساب التشابه بين الرسوم البيانية بسرعة

بحث التشابه بين الرسوم البيانية هو من أهم التطبيقات القائمة على الرسوم البيانية، مثل العثور على المركبات الكيميائية الأكثر تشابهاً مع مركب استعلامي. حساب التشابه بين الرسوم البيانية، مثل مسافة تعديل الرسم البياني (Graph Edit Distance - GED) ورسم الفرع المشترك الأكبر (Maximum Common Subgraph - MCS)، هو العملية الأساسية لبحث التشابه بين الرسوم البيانية والعديد من التطبيقات الأخرى، ولكنه يكلف الكثير في الممارسة. مستوحاة من النجاحات الحديثة للشبكات العصبية في العديد من التطبيقات القائمة على الرسوم البيانية، مثل تصنيف العقد أو الرسوم البيانية، نقترح نهجًا جديدًا قائمًا على الشبكات العصبية لمعالجة هذه المشكلة التقليدية والمعقدة في الرسوم البيانية، بهدف تخفيف العبء الحسابي مع الحفاظ على أداء جيد.النهج المقترح، الذي يُطلق عليه اسم SimGNN، يجمع بين استراتيجيتين. أولاً، نصمم دالة تمثيل قابلة للتعلم تقوم بتحويل كل رسم بياني إلى متجه، مما يوفر ملخصًا عالميًا للرسم البياني. يتم اقتراح آلية انتباه جديدة لتسليط الضوء على العقد الهامة بالنسبة لمقياس تشابه معين. ثانياً، نصمم طريقة للمقارنة الزوجية بين العقد لتكميل التمثيلات العالمية للرسوم البيانية بمعلومات دقيقة على مستوى العقد. يحقق نموذجنا تعميمًا أفضل على الرسوم البيانية غير المرئية سابقًا، وفي الحالة الأسوأ يعمل في وقت تربيعي بالنسبة لعدد العقد في رسومين بيانيين. كمثال على حساب MGED (مسافة تعديل الرسم البياني)، تظهر النتائج التجريبية على ثلاثة مجموعات بيانات حقيقية فعالية وكفاءة نهجنا. تحديداً، يحقق نموذجنا معدل خطأ أقل وتخفيض كبير في الوقت بالمقارنة مع سلسلة من الأساليب المرجعية، بما في ذلك عدة خوارزميات تقريبية لحساب MGED (مسافة تعديل الرسم البياني) والعديد من النماذج القائمة على الشبكات العصبية للرسوم البيانية الموجودة حالياً. وفقًا لأفضل علم لنا، فإننا من أوائل الذين يستخدمون الشبكات العصبية لنمذجة التشابه بشكل صريح بين رسومين بيانيين، مما يقدم اتجاهًا جديدًا للأبحاث المستقبلية حول حساب التشابه بين الرسوم البيانية وبحث التشابه بينها.