Min Generalized Sliced Gromov Wasserstein: A Scalable Path to Gromov Wasserstein

ملخص تقني: الحد الأدنى من مسافة غروموف-واسرشتاين المقطعة المعممة (min-GSGW)

بيان المشكلة

تعد مسافة غروموف-واسرشتاين (GW) أداة مركزية لمقارنة الفضاءات المترية والقياسية حيث لا يوجد فضاء محيط مشترك، كما هو الحال في تحليل الأشكال، ومطابقة الرسوم البيانية (graph matching)، وتكامل البيانات البيولوجية. تسعى هذه المسافة إلى إيجاد اقتران بين فضاءين يقلل من التباين بين هندستيهما الداخلية الزوجية. ومع ذلك، فإن حل مشكلة GW عملية مكلفة حاسوبياً: ففي الحالة المنفصلة، هي مسألة برمجة تربيعية غير محدبة، وهي عموماً مسألة صعبة (NP-hard)، حيث تتطلب التنفيذات البدائية عمليات بمقدار $O(n^4)$.

تعمل البدائل القابلة للتوسع الموجودة، ولا سيما مسافة غروموف-واسرشتاين المقطعة (SGW)، على تقليل التعقيد عن طريق إسقاط القياسات عالية الأبعاد على خطوط أحادية البعد وإجراء مطابقة رتيبة. ورغم كفاءتها ($O(n \log n)$)، إلا أن هذه الطرق تعاني من ثلاثة قيود حرجة:

1. المطابقة غير المثلى في البعد الواحد: المطابقة الرتيبة في المجال المسقط لا تحل بالضرورة مشكلة GW أحادية البعد بشكل دقيق؛ حيث تُظهر الأمثلة المضادة أن التبديلات المتطابقة أو التبديلات العكسية ليست دائماً مثالية.
2. عد عدم توافق الإسقاط: غالباً ما تستخدم الطرق الحالية إسقاطات مختارة بشكل مستقل للفضاءين، والتي قد تفشل في التقاط المحاذاة الهيكلية ذات المعنى.
3. موثوقية مخطط النقل: لا تقدم مخططات النقل الناتجة في الفضاء المسقط أي ضمانات للقرب من الاقتران الأمثل لـ GW الحقيقي عند رفعها مرة أخرى إلى الفضاءات المترية الأصلية. وبناءً على ذلك، تعمل طرق GW المقطعة السابقة كأهداف مسافة بديلة بدلاً من كونها مخصات مباشرة لتقليل خسارة GW.

المنهجية

يقترح المؤلفون الحد الأدنى من مسافة غروموف-واسرشتاين المقطعة المعممة (min-GSGW)، وهو إطار عمل يبني مخططات نقل صريحة عبر تعلم "قاطعات" (slicers) غير خطية مقترنة بدلاً من الاعتماد على إسقاطات خطية ثابتة.

الآلية الجوهرية:

1. القاطعات المعممة والرفع: بدلاً من التضمينات الخطية الصلبة، يتعلم min-GSGW خريطة رفع $h: X \to Y$ (تربط الفضاء الأقل أبعاداً بالفضاء الأعلى أبعاداً) وقاطعة غير خطية مشتركة $f: Y \to \mathbb{R}$.
2. الدفع للأمام والترتيب: تحسب الطريقة قيم الدفع للأمام لكل من نقاط المصدر المرفوعة ($f \circ h$) ونقاط الهدف ($f$).
3. الاقتران الرتيب: يتم ترتيب قيم البعد الواحد الناتية، ويتم تشكيل اقتران رتيب بين هذه المتتاليات المرتبة.
4. رفع المخطط: يتم رفع هذا الاقتران الرتيب أحادي البعد مرة أخرى إلى الفضاءات الأصلية لتشكيل مخطط نقل $\pi_{f,h}$.
5. التحسين: الهدف هو تقليل خسارة GW التي يتم تقييمها على الفضاءات الأصلية باستخدام هذا المخطط المرفوع:
   $$\text{min-GSGW}(\mu, \nu) := \inf_{f, h} L_{GW}(\mu, \nu, \pi_{f,h})$$
   ومن الأهمية بمكان أن عدم خطية القاطعات تسمح للاقترانات المستحثة بالوصول إلى مناطق في فضاء الاقتران لا يمكن الوصول إليها عبر الإسقاطات الخطية، مما يؤدي فعلياً إلى تقريب حل GW أحادي البعد من خلال إعادة ترتيب غير خطية متعلمة.

تفاصيل التنفيذ:

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

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

1. إطار عمل القاطعة المعممة: تقديم min-GSGW، الذي يربط بين قاطعتين عبر خريطة ورفع مشترك، مما يستحث مخططات نقل مباشرة في الفضاءات المترية الأصلية. وهذا يسمح للطريقة باستكشاف عائلة أغنى من الاقترانات مقارنة بالتقطيع الخطي.
2. الخصائص الهيكلية: إثبات ثبات الحركة الصلبة وتطوير تخفيف ترتيب قابل للتفاضل للتحسين.
3. التعلم المستهلك (Amortized Learning): تطوير متنبئ متعلم يستبدل التحسين لكل حالة، مما يتيح مطابقة فعالة لأزواج المدخلات الجديدة.
4. التحقق التجريبي: إثبات أن min-GSGW ينتج مواءمات هندسية وقيم هدف GW تنافس الحلول التكرارية المكلفة (مثل Frank-Wolfe وSinkhorn) بتكلفة حاسوبية أقل بكثير.

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

قيم المؤلفون min-GSGW في ثلاث مهام:

• مطابقة الأشكال الواقعية: في اختبار مرجعي لشبكات الحيوانات (حصان، فيل، قطة)، حقق min-GSGW أدنى خطأ جيوديسي (لقياس الدقة الهندسية مقابل الحقيقة الأرضية) عبر جميع الأزواج مع الحفاظ على أسرع وقت تشغيل (على سبيل المثال، ~0.08 ثانية مقابل 1.82 ثانية لـ POT-GW).
• استكمال (Interpolation) شبكة الحصان: ولّد المنهج تشوهات وسيطة سلسة ومتماسكة هندسياً بين شبكات الحصان. وبينما حقق POT-GW قيم هدف GW أقل، حافظت مخططات min-GSGW على البنية واسعة النطاق بفعالية، مما يشير إلى أن المثالية العالمية لـ GW لا تعني دائماً الفائدة الهندسية.
• تجزئة أجزاء ShapeNet: في وضع غير مُراقب ومستهلك، تنبأ المطابق المتعلم بمراسلات الأجزاء دون استخدام تسميات الأجزاء أثناء التدريب. حقق min-GSGW دقة أعلى في نقل تسميات الأجزاء (على سبيل المثال، 78.2% عند $N=256$) مقارنة بـ POT GW (68.9%) وSinkhorn، مع أوقات استدلال أمامية أسرع بعدة مراتب (2.66 مللي ثانية مقابل 75.3 مللي ثانية).

الأهمية والادعاءات

يزعم البحث أن min-GSGW يوفر "مساراً قابلاً للتوسع" نحو مسافة غروموف-واسرشتاين من خلال التقليل المباشر لهدف GW عبر عائلة من الاقترانات المستحثة بواسطة القاطعات. وتشمل الادعاءات الرئيسية ما يلي:

• التقليل المباشر لـ GW: على عكس طرق السلسلة المقطعة السابقة التي تحدد أهداف مسافة بديلة، يقوم min-GSGW بتقليل خسارة GW الأصلية، مما يوفر حداً علوياً صالحاً لمسافة GW الحقيقية.
• التعبير مقابل الكفاءة: باستخدام قاطعات غير خطية، تتغلب الطريقة على قيود الإسقاطات الخطية، محققةً اقترانات غالباً ما تكون منافسة أو متفوقة على الحلول التكرارية، رغم تعقيد استخراج المخطط البالغ $O(n \log n)$.
• المنفعة العملية: يتيح النسخة المستهلكة تطبيق المطابقة القائمة على GW للمشكلات عالية الدقة حيث يكون تحسين GW الكثيف مكلفاً للغاية، مما يجعل المطابقة الواعية بالبنية عملية لمهام مثل تحليل الأشكال وتكامل البيانات متعددة الوسائط.

يشير المؤلفون إلى أنه بينما تعتبر هذه الطريقة تقريبية، فإن القدرة التعبيرية للقاطعات المتعلمة تسمح بتضييق الحد، كما يضمن ثبات الحركة الصلبة المتانة للمهام الهندسية.