Scalable Topology-Preserving Graph Coarsening: Concepts and Algorithms

ملخص تقني: التقليص المتدرج للرسوم البيانية المحافظ على الطوبولوجيا والقابل للتوسع (STPGC)

بيان المشكلة
يهدف تقليص الرسوم البيانية (Graph coarsening) إلى تقليل حجم الرسم البياني مع الحفاظ على خصائص محددة لتسهيل التحليل الفعال، لا سيما لشبكات الأعصاب الرسومية (GNNs). تركز الطرق الحالية بشكل أساسسب على الحفاظ على الخصائص الطيفية (القيم والناقلات الذاتية لمصفوفة لابلاس) أو الخصائص المكانية (الاتصال المحلي، وانتشار التأثير). وبينما تشير الأبحاث الحديثة إلى أن الحفاظ على الميزات الطوبولوجية (الاتصال، الحلقات، والفراغات من رتب أعلى) أمر بالغ الأهمية للحفاظ على أداء شبكات GNN، فإن النهج الحالي للحفاظ على الطوبولوجيا يعاني من مشكلات شديدة في القابلية للتوسع. وتحديداً، تعتمد طريقة "انهيار الرسم البيئي الأساسي" (GEC)، وهي الأحدث في هذا المجال، على تعداد الكليكات (clique enumeration) لتحديد الهياكل القابلة للاختزال، مما يؤدي إلى تعقيد زمني أسّي في أسوأ الحالات يصل إلى $O(3^{n/3})$. وهذا يجعل GEC غير عملية للرسوم البيانية الضخمة. علاوة على ذلك، فإن الحل البديل الذي تتبعه GEC عبر تقسيم الرسوم البيانية يؤدي إلى تعطيل الميزات الطوبولوجية العالمية، والتي لا يمكن استعادتها أثناء عملية إعادة البناء.

المنهجية
يقترح المؤلفون إطار عمل التقليص المتدرج للرسوم البيانية المحافظ على الطوبولوجيا والقابل للتوسع (STPGC)، وهو إطار يوسع مفاهيم مستمدة من الطوبولوجيا الجبرية — وتحديداً الانهيار القوي (strong collapse) وانهيار الحافة (edge collapse) — لتطبيقها على مجال الرسوم البيانية. وبخلاف GEC، يتجنب STPGC عملية تعداد الكليكات المكلفة من خلال تحديد الهياكل القابلة للاختزال عبر احتواء الجوار (neighborhood inclusion).

يتكون إطار العمل من ثلاث خوارزميات أساسية:

1. GStrongCollapse: تعمل بشكل تكراري على تحديد "العقد المهيمنة". تُعتبر العقدة $u$ مهيمنة من قبل $v$ إذا كان جوارها المغلق مجموعة جزئية من الجوار المغلق لـ $v$ ($N[u] \subseteq N[v]$). تقوم الخوارزمية بإزالة العقد المهيمنة وحوافها، ودمجها في عقد فائقة (supernodes).
2. GEdgeCollapse: تعمل بشكل تكراري على تحديد "الحواف المهيمنة". تُعتبر الحافة $(x, y)$ مهيمنة من قبل العقدة $v$ (حيث $v \notin \{x, y\}$) إذا كان الجوار المغلق للحافة هو مجموعة جزئية من الجوار المغلق لـ $v$ ($N[x, y] \subseteq N[v]$). إن إزالة هذه الحواف يكسر حالات الجمود الهيكلية، مما يكشف عن عقد مهيمنة جديدة.
3. NeighborhoodConing: للتعامل مع السيناريوهات التي لا توجد فيها عقد أو حواف مهيمنة في البداية، تقوم هذه الخوارزمية بإدراج "حواف مهيمنة" بين جيران العقدة المستهدفة $u$ لإنشاء عقدة مهيمنة جديدة. هذه العملية، التي يتم صياغتها كعملية "تكوين مخروطي" (coning)، تسمح بمزيد من الاختزال مع الحفاظ على التكافؤ الهوموتوبي (homotopy equivalence).

الضمانات النظرية
يثبت البحث أن الجمع بين هذه العمليات يحافظ على التكافؤ الهوموتوبي بين الرسم البياني الأصلي والرسم البياني المختزل. وهذا يضمن الحفاظ على الثوابت الطوبولوجية، مثل المكونات المتصلة، والحلقات، والفراغات، وأرقام بيتي (Betti numbers). علاوة على ذلك، يوضح المؤلفون أن هذه العمليات تحافظ على المجال الاستقبالي لشبكة GNN. وتحديداً:

• لا تؤدي عمليات GStrongCollapse و NeighborhoodConing إلى زيادة المسافة الأقصر بين أي زوج من العقد.
• تزيد عملية GEdgeCollapse المسافة الأقصر بمقدار 1 على الأكثر.
  يضمن هذا الحفاظ على مسافات المسار الأقصر بقاء نطاق تجميع المعلومات لشبكات GNN سليماً إلى حد كبير.

ولمعالجة القصور المتمثل في أن الحفاظ الدقيق على الطوبولوجيا قد لا يحقق نسب تقليص تعسفية (بسبب الطبيعة الصعبة (NP-hard) لاختزال الرسم البياني إلى جوهره الأدنى)، يقدم المؤلفون استراتيجية ApproximateCoarsening. تعتمد هذه الاستراتيجية ذات المرحلتين على إجراء تقليص دقيق أولاً، ثم تطبيق $r$-relaxed strong collapse، والتي تسمح بغياب ما يصل إلى $r$ من العقد في شرط احتواء الجوار، مما يتيح نسب اختزال مرنة.

المساهمات الرئيسية

1. مفاهيم وخواروات مبتكرة: تقديم مفاهيم وخوارزميات الانهيار القوي والانهيار للحواف في الرسوم البيانية المستمدة من الطوبولوجيا الجبرية، والتي تم تنفيذها عبر ثلاث خوارزميات قابلة للتوسع (GStrongCollapse، GEdgeCollapse، NeighborhoodConing) والتي تلغي الهياكل المهيمنة دون تعقيد أسي.
2. التطبيق على تدريب GNN: إثبات أن STPGC يحافظ على المجال الاستقبالي لـ GNN، مقترناً باستراتيجية تقليص تقريبية لموازنة الدقة الطوبولوجية مع القابلية للتوسع لتسريع التدريب.
3. أداء يضاهي أحدث المعاياي: أدلة تجريبية تظهر تفوق STPGC على النماذج المرجعية التسعة، بما في ذلك الطرق الطيفية والمكانية، في مهام تصنيف العقد مع تقديم تحسينات كبيرة في وقت التشغيل.

النتائج التجريبية
أُجريت التجارب على خمس مجموعات بيانات مصنفة (Cora, Citeseer, DBLP, ogbn-arXiv, ogbn-products) لتصنيف العقد، وأربع مجموعات بيانات ضخمة غير مصنفة لتقييم القابلية للتوسع.

• الدقة: تفوق STGC باستمرار على تسعة نماذج مرجعية، بما في ذلك الطرق الطيفية والمكانية. حقق متوسط تحسن في الدقة بنسبة 1.73% عن GEC عبر خمس مجموعات بيانات. وتبرز النتائج أن الطرق المحافظة على الطوبولوجيا (STPG و GEC) تتفوق عموماً على النماذج غير المحافظة على الطوبولوجيا.
• الكفاءة: أظهر STPF كفاءة فائقة في وقت التشغيل والذاكرة مقارنة بجميع النماذج المرجعية. والجدير بالذكر أنه حقق سرعة في وقت التشغيل تصل إلى 37 ضعفاً مقارنة بـ GEC. وفي مجموعة بيانات DBLP عند نسبة تقليص 0.1، كان STPF أسرع من GEC بأكثر من 15 مرة.
• الحفاظ على الطوبولوجيا: أظهر تحليل أرقام بيتي أن STPF يحافظ بدقة على عدد الميزات الطوبولوجية حتى انتهاء مرحلة التقليص الدقيق، بينما تفقد الطرق الأخرى (بما في ذلك GEC) الميزات الطوبولوجية في وقت مبكر من العملية بسبب تقسيم الرسم البياني أو نقص الحفاظ العالمي.
• القابلية للتوسع: في مجموعات البيانات واسعة النطاق (LiveJournal, Youtube, cit-Patent, Flixster)، أظهر STPF قابلية توسع شبه خطية في وقت التشغيل ونمواً رتيباً في الذاكرة، مما يؤكد قابليته للتطبيق على الرسوم البيانية الضخمة.

الأهمية والادعاءات
يزعم البحث أن STPGC يوفر حلاً قابلاً للتوسع ومبنياً على أسس نظرية لتقليص الرسوم البيانية، حيث يحافظ بدقة على الميزات الطوبية، وهي قدرة كانت محدودة سابقاً بسبب التعقيد الحسابي. ومن خلال ضمان التكافؤ الهوموتوفي والحفاظ على المجال الاستقبالي لـ GNN، يتيح STPF تدريب شبكات GNN على رسوم بيانية أصغر بكثير دون التضحية بالأداء على البيانات الأصلية. ويضع المؤلفون STPF كـ "وحدة معالجة مسبقة جاهزة للاستخدام" (plug-and-play) مستقلة عن بنيات GNN اللاحقة.

يساهم هذا العمل في "الذكاء الاصطناعي الأخضر" (Green AI) من خلال تقليل الموارد الحسابية واستهلاك الطاقة المطلوب لتدريب شبكات GNN على الرسوم البيانية واسعة النطاق. ويقر المؤلفون بوجود قيود، مثل استخدام متوسط الميزات التجريبي وتجميع تسميات التصويت بالأغلبية للعقد الفائقة، والتي قد لا تكون مثالية لبعض المهام، ويقترحون أعمالاً مستقبلية في تطبيق هذه الأساليب على مجالات أوسع مثل ضغط البيانات البيولوجية لاكتشاف الأدوية.