Finding Graph Isomorphisms in Heated Spaces in Almost No Time

إليك ملخص تقني مفصل للورقة البحثية بعنوان "إيجاد تماثل الرسوم البيانية في الفضاءات المسخنة في وقت لا يكاد يُذكر" (Finding graph isomorphisms in heated spaces in almost no time) للباحثين سارة نجم وعامر إي. معوض.

1. بيان المشكلة

تتساءل مشكلة تماثل الرسم البياني (Graph Isomorphism - GI) عما إذا كان رسمان بيانيان منتهيان يتشاركان نفس البنية التوليفية (أي ما إذا كانت هناك تقابل بين مجموعتي رؤوسهما يحافظ على علاقة التجاور).

• الوضع التعقيدي: يحتل تماثل الرسم البياني مكانة فريدة في نظرية التعقيد؛ فهو ليس معروفاً كمسألة يمكن حلها في وقت حدودي (Polynomial time)، ولا هو مُثبت كمسألة NP-complete.
• التحدي الجوهري: يكمن الصعوبة الرئيسية في حل التماثل (Symmetry Resolution). ففي الرسوم البيانية عالية التماثل (مثل الرسوم البيانية منتظمة القوة أو رسوم كايلي)، غالباً ما تفشل طرق الصقل التوليفية البحتة (مثل طريقة وايزفيلر-ليميلر) في تمييز الرؤوس لأن الجوارات المحلية تكون غير قابلة للتمييز.
• محددات الطرق الحالية:
  • الطرق الطيفية (Spectral methods): رغم أن أطياف الرسوم البيانية هي ثوابت، إلا أن الرسوم غير المتماثلة قد تكون متساوية الطيف (تشترك في نفس القيم الذاتية).
  • الصقل التوليفي (Combinatorial refinement): يمكن أن يستقر على عائلات متماثلة دون القدرة على تمييز هويات الرؤوس.
  • النهج القائم على البحث: غالباً ما تعتمد على الاستدلالات (Heuristics) أو البحث الشامل، وتفتقر إلى الضمانات الهندسية الحتمية.

2. المنهجية

يقترح المؤلفون إطار عمل حتمياً مدفوعاً بالانتشار (Diffusion-driven framework) يعامل تحديد الرؤوس كعملية حل تدريجي للبنية الهندسية متعددة المقاييس. يدمج الخوارزمي الهندسة الطيفية، وعمليات الانتشار، والتعزيز الهيكلي المحكوم.

أ. المحرك الهندسي الأساسي: الانتشار والانحناء

بدلاً من الاعتماد فقط على القيم الذاتية، تحلل الطريقة السلوك قصير المدى لنواة الحرارة (Heat Kernel) على الرسم البياني.

• نواة الحرارة: تُعرف بـ $K(t) = e^{-tL}$، حيث $L$ هو لابلاتسيان الرسم البياني (Graph Laplacian). تمثل المدخلات القطرية $K(i,i,t)$ احتمالات عودة الحرارة.
• استخراج الانحناء: استناداً إلى التناظر مع الهندسة الريمانية، يتم نمذجة التوسع قصير المدى لنواة الحرارة كـ:
  $$K(i,i,t) \approx t^{-d_s/2} \sum_{k=0}^{N} u_k(i) t^k$$
  هنا، $d_s$ هو البعد الطيفي (يُقدر من كثافة القيم الذاتية)، وتعمل المعاملات $u_k(i)$ كـ بصمات تشبه الانحناء للرأس $i$.
• التحجيم الكسري (Fractional Scaling): لكسر التماثل في الرسوم البيانية عالية الانتظام، يقدم المؤلفون لابلاتسيان كسرياً ($L^s$). من خلال ضبط الأس $s$، يقومون بإعادة وزن النطاقات الطيفية (تضخيم الأنماط منخفضة التردد للحساسية بعيدة المدى أو الأنماط عالية التردد للاختلالات المحلية)، مما يسمح للرؤوس بالانفصال بناءً على هندسة الانتشار حتى عندما تفشل الإحصاءات التوليفية.

ب. تسلسل الهرمي للصقل (Refinement Hierarchy)

يسير الخوارزمي عبر حلقة حتمية من الدقة الهندسية المتزايدة:

1. بصمات انحناء BFS:

   • يتم تجميع معاملات الانحناء المحلية عبر جيران البحث بالعرض (BFS).
   • بالنسبة للرأس $v$، تتضمن البصمة متجه الانحناء الخاص به والمجموعات متعددة الأطقم المرتبة لمتجهات انحناء جيرانه عند المسافة 1، 2، إلخ.
   • هذا ينشئ بصمة هندسية متعددة المقاييس ثابتة تجاه إعادة تسمية الرؤوس.

2. التطبيع الهندسي (التقسيم - Subdivision):

   • إذا كانت الرسوم البيانية ذات أقطار صغيرة أو انتظام شديد يؤدي إلى خلط سريع للانتشار، يتم تقسيم الحواف (استبدالها بمسارات) لتنظيم المقياس الطيفي وضمان تقدير مستقر للانحناء.

3. الاستقصاء المهيكل (التعزيز المؤقت - Temporary Augmentation):

   • إذا فشلت بصمات BFS في فصل فئة من الرؤوس، يقوم الخوارزمي بـ استقصاء مؤقت.
   • الآلية: يتم تعزيز رؤوس مختارة مؤقتاً بـ "أدوات" (Gadgets) (مثل كليكات مشتركة، كليكات خاصة، ومسارات بأطوال محددة).
   • العملية: يحسب الخوارزمي التقسيمات المستحثة على هذه الرسوم البيانية المعززة. يتم تجميع الرؤوس حسب "ملفات الاستقصاء" الخاصة بها (كيفية تفاعلها مع الاتصال برؤوس أخرى).
   • التصعيد: يبدأ الخوارزمي بـ استقصاء الزوج (إرفاق الأدوات بزوج من الرؤوس). إذا فشل ذلك، ينتقل إلى استقصاء الثلاثي.

4. التفريد الحتمي (التعزيز الدائم - Permanent Augmentation):

   • إذا فشل الاستقصاء في حل فئات الرؤوس بالكامل، يقوم الخوارزمي بـ تعزيز هيكلي دائم.
   • يتم ربط الرؤوس المتطابقة في الرسمين البيانيين بشكل دائم بكليكات جديدة متزايدة الحجم ($q, q+1, \dots$).
   • هذا التراكم الرتيب لعدم التماثل الهيكلي يجبر هندسة الانتشار على تمييز الرؤوس في الدورات اللاحقة.

5. الإنهاء والتحقق:

   • تتوقف العملية عندما تصبح جميع فئات الرؤوس عناصر مفردة أو "فئات توأم" (True/False twins).
   • يتم إنشاء تقابل مرشح والتحقق منه صراحة مقابل الرسوم البيانية الأصلية غير المعدلة لضمان الصحة.

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

• النموذج الهندسي لـ GI: ينقل التركيز من الصقل التوليفي البحت إلى هندسة الانتشار، باستخدام تقاربات نواة الحرارة كمحرك أساسي لكسر التماثل.
• بصمات الانحناء: تقدم واصفاً جديداً للرأس يعتمد على التوسع قصير المدى لنواة الحرارة، والمقاس بالبعد الطيفي، والذي يلتقط المعلومات الهيكلية غير المرئية في القيم الذاتية الخام.
• إطار عمل حتمي: على عكس العديد من حلالات GI التجريبية، فإن هذا النهج حتمي بالكامل، ويعتمد على معاملات ثابتة وترتيب معياري، مما يضمن قابلية التكرار.
• استراتيجية صقل هجينة: يجمع بين الصقل الهندسي الذاتي (BFS-curvature)، والاستقصاء التشخيصي المؤقت، والتفريد الدائم في تسلسل هرمي واحد محدود.
• التحجيم الطيفي الكسري: يستخدم اللابلاتسيان الكسري للتكيف مع الأبعاد الجوهرية للرسم البياني، مما يعزز الحساسية للاختلافات الهيكلية.

4. النتائج التجريبية

تم اختبار الإطار على عائلات متنوعة من الرسوم البيانية والمعايير المرجعية:

• الرسوم البيانية العشوائية: نجح في حل الرسوم الهندسية العشوائية، ورسوم قانون القوة، ورسوم بلوك العشوائية (Stochastic Block)، ورسوم إيردوس-ريني، ورسوم واتس-ستروغاتس، ورسوم ألبرت-باراباسي.
• الرسوم البيانية عالية الانتظام: حل رسوم بالي (Paley graphs) والرسوم البيانية منتظمة القوة (Strongly Regular Graphs)، وهي رسوم صعبة للغاية بالنسبة للطرق الطيفية القياسية بسبب التماثل العالي.
• اختبارات الضغط المرجعية: نجح الخوارزمي في حل حالات من مستودع باليني (Pallini repository)، بما في ذلك:
  • رسوم كاي-فورير-إيمرمان (CFI): المصممة خصيصاً لهزيمة صقل وايزفيلر-ليميلر منخفض الأبعاد.
  • رسوم ميازاكي (Miyazaki): المعروفة باحتياجها لعمليات تبديل واسعة النطاق للتمييز.
  • رسوم الهندسة الأفينية، الشبكية (Grid)، هادامارد (Hadamard)، المربع اللاتيني (Latin Square)، والمستوى الإسقاطي (Projective Plane).
• الأداء: حلت الطريقة جميع الحالات المختبرة ضمن حدود الصقل المقررة. وبينما قد يكون التعقيد الزمني في أسوأ الحالات النظرية مرتفعاً ($O(n^{10})$)، إلا أن الأداء التجريبي على المعايير القياسية كان فعالاً.

5. الأهمية والخاتمة

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

باختصار، يقدم هذا العمل نهجاً جديداً متمحوراً حول الهندسة لمسألة تماثل الرسم البياني، يستفيد من فيزياء انتشار الحرارة لتفكيك التماثل بشكل منهجي، مما يوفر بديلاً قوياً للتقنيات التوليفية والطيفية التقليدية.