ملخص تقني: الضياع في التجزئة: المقايضات الجوهرية في تجزئة الرسوم البيانية للمحولات (Transformers)

بيان المشكلة

برزت المحولات (Transformers) كبنية قوية لتعلم الرسوم البيانية (Graphs)، إلا أن تطبيقها على البيانات ذات البنية الرسومية يتطلب خطوة تمهيدية وهي: التجزئة (Tokenization). وخلافاً للتسلسلات أو الشبكات المنتظمة، تفتقر الرسوم البيانية إلى تنسيق مدخل مستمر معياري. وبناءً عليه، يجب اختيار خريطة (رسم بياني-إلى-رمز/توكن) لتحديد المعلومات الهيكلية التي سيتم كشفها للنموذج عند طبقة المدخلات.

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

المنهجية

يصيغ المؤلفون عملية تجزئة الرسم البياني كجزء لا يتجزأ من النموذج الحوسبي، حيث يحللون قدرة المحولات التعبيرية تحت قيود العمق ($L$)، والعرض ($m$)، والدقة ($p$) تحت ثلاث عائلات رئيسية من التجزئة:

1. تجزئة المصفوفة المجاورة (Adjacency Tokenization): تشفر الاتصال المحلي لكل عقدة عبر صف المصفوفة المجاورة الخاص بها. وهي عملية غير فاقدة للمعلومات (lossless) ولكنها تكشف فقط عن البنية المحلية.
2. التجزئة الطيفية (Spectral/Laplacian Tokenization): تشتق الرموز من التفكيك الذاتي لمصفوفة لابلاس للرسم البياني ($L = D - A$). وهي تلتقط الخصائص الطوبولوجية العالمية ولكنها متوافقة مع التبديل (permutation-equivariant).
3. تجزئة المسار العشوائي (Random-Walk Tokenization): تشفر احتمالات العودة للمسارات العشوائية من الطول $1$إلى$t(n)$. وهي تلتقط أنماط الانتشار ولكنها فاقدة للمعلومات بطبيعتها (lossy).

تجمع المنهجية بين التحليل القائم على تعقيد الحوسبة والتجارب المنضبطة.

• التحليل النظري: يضع المؤلفون حدوداً دنيا ونتائج الاستحالة عبر ربط مهام الرسم البياني بفئات التعقيد (مثل $TC^0$، $NC^1$، $L$). ويحللون كيفية سلوك مهام محددة (مثل اكتشاف المسارات المغلقة بطول $k$، الاتصال، عد المثلثات، والمستوية/Planarity) تحت تأثير تجزئات مختلفة، مع مراعاة قيود العمق المحدود والخصائص الرياضية لتمثيلات الرموز (مثل أرقام الحالة/condition numbers، وفقدان المعلومات).
• التحقق التجريبي: تُجرى التجارب على مهام اصطناعية (للتحقق من فوارق العمق) ومعايير حقيقية (GraphBench، Open Graph Benchmark، ZINC). وتقيم الدراسة المحولات باستخدام نسخ كاملة ومقتطعة من كل نوع من أنواع التجزئة، بالإضافة إلى التجزئات المدمجة، مقارنة بنماذج DeepSet وGIN الأساسية.

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

1. صياغة التجزئة كقيد حوسبي

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

2. فوارق العمق بين أنواع التجزئة

يثبت المؤلفون أن نفس عملية حساب الرسم البياني قد تتطلب أعماقاً متفاوتة تماماً اعتماداً على نوع التجزئة:

• المسار العشوائي مقابل المصفوفة المجاورة: اكتشاف مسار مغلق بطول $k$ يمكن حله بعمق $O(1)$ باستخدام تجزئة المسار العشوائي (لأن الإحصائيات صريحة)، ولكنه يتطلب عمقاً قدره $\Omega(\log k)$ باستخدام تجزئة المصفوفة المجاورة. وقد ثبت هذا عبر الاختزال من مشكلة الكلمة في زمرة التبديل $S_5$ (وهي مشكلة كاملة لـ $NC^1$) إلى طوبولوجيا الرسم البياني، مما يظهر أن المحولات ذات العمق الثابت ($TC^0$) لا يمكنها محاكاة التتبع المتسلسل للمسار المطلوب من رموز المصفوفة المجاورة.
• المصفوفة المجاورة مقابل الطيفية: حل مسألة الاتصال العالمي للرسم البياني يتطلب عمقاً قدره $\Omega(\log n)$ مع تجزئة المصفوفة المجاورة، بينما تحل التجزئة الطيفية هذه المسألة بعمق $O(1)$.

3. القيود الجوهرية وفقدان المعلومات

• تجزئة المسار العشوائي فاقدة للمعلومات بشكل مثبت: بغض النظر عن طول المسار، لا تستطيع تجزئة المسار العشوائي تحديد مستوية (planarity) الرسم البياني. وقد صاغ المؤلفون رسوماً بيانية مستوية وغير مستوية لها نفس توزيعات المسار العشوائي باستخدام تبديل Godsil-McKay (GM)، مما يثبت أنه لا يمكن لأي عمق أو عرض للمحول استعادة التمييز الطوبولوجي.
• الاقتطاع الطيفي هش (Brittle): إن اقتطاع طيف لابلاس (حتى لو بقيمة ذاتية واحدة) يمكن أن يجعل عد المثلثات مستحيلاً. يوضح المؤلفون أن إضافة حافة بين عقد متماثلة يغير قيمة ذاتية واحدة فقط؛ وإذا تم اقتطاع هذه القيمة، فلن يستطيع المحول التمييز بين الرسوم البيانية.
• اقتطاع المصفوفة المجاورة: يؤدي اقتطاع أبعاد رموز المصفوفة المجاورة (عبر الإسقاط العشوائي) إلى تدمير القدرة على حل مهام مثل عد المثلثات، وهو ما ثبت عبر حدود تعقيد الاتصال (Set Disjointness).

4. سوء حالة التجزئة الطيفية للمهام المحلية

بينما تلتقط التجزئة الطيفية الطوبولوجيا العالمية، فإنها رياضياً تعاني من سوء الحالة (ill-conditioned) للمهام المحلية مثل التنبؤ بالحواف. تستنتج الورقة حداً أدنى يظهر أن معايير المعلمات (parameter norms) المطلوبة لفك تشفير حافة محلية من طيف عالمي تتناسب مع الدرجة القصوى ($d_{max}$). وهذا يفرض مقايضة: إما أن يعاني النموذج من تشبع Softmax (تلاشي التدرج) أو يتطلب أوزاناً متفجرة، مما يجعل الأمثلة (optimization) صعباً.

5. استحالة التحويل عند العمق المحدود

تثبت الورقة أن التحويل بين عائلات التجزئة مستحيل بشكل عام عند عمق محدود.

• لا يمكن للمحول تحويل رموز المصفوفة المجاورة إلى إحصائيات المسار العشوائي بكفاءة (يتطلب ذلك عمقاً قدره $\Omega(\log k)$).
• لا يمكن للمحول استعادة تمثيلات المصفوفة المجاورة أو لابلاس الكاملة من رموز المسار العشوائي (بسبب فقدان المعلومات).
• التحويل بين الرؤى العالمية (الطيفية) والمحلية (المصفوفة المجاورة) يتضمن اختناقات حوسبية شديدة أو عدم استقرار في الأمثلة.

النتائج

النتائج النظرية:

• فوارق العمق: تؤكد التحققات التجريبية أن التجزئة الطيفية تحل مهام الاتصال بعمق $L=1$ عبر جميع أحجام الرسوم البيانية، بينما تنهار تجزئة المصفوفة المجاورة إلى أداء عشوائي للرسوم البيانية الكبيرة ($n \ge 128$).
• حدود الاستعادة: عند تدريب محول للتنبؤ باحتمالات عودة المسار العشوائي من رموز المصفوفة المجاورة، يزدما الخطأ مع طول المسار $k$، وهو ما يتوافق مع متطلب العمق $\Omega(\log k)$.
• المستوية (Planarity): تفشل النماذج التي تستخدم رموز المسار العشوائي في التمييز بين الرسوم البيانية المستوية وغير المستوية، حتى مع زيادة العمق، مما يؤكد نتيجة الاستحالة النظرية.

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

• اعتماد المهمة: لا توجد تجزئة واحدة تهيمن على الجميع.
  • المهام المحلية: تحقق تجزئة المصفوفة المجاورة أفضل أداء في المهام التي تحكمها قيود محلية صريحة (مثل Max Clique، وTopological Ordering).
  • المهام العالمية: تحقق التجزئة الطيفية (Laplacian) أفضل أداء في المهام المعتمدة على الهندسة العالمية (مثل التنبؤ بالخصائص الجزيئية لـ Tox21).
  • النهج المدمج: غالباً ما يؤدي دمج التجزئات المتكاملة (المصفوفة المجاورة + الطيفية + المسار العشوائي) إلى أفضل أداء، مما يسمح للنموذج بالاستفادة من إشارات هيكلية متميزة.
• آثار الاقتطاع: تؤدي التجزئات المقتطعة عموماً إلى تدهور الأداء، خاصة للمهام التي تتطلب استعادة هيكلية دقيقة (مثل عد المثلثات)، مما يؤكد "هشاشة" الاقتطاع النظرية.

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

تدعي الورقة أن تجزئة الرسم البياني هي مقايضة جوهرية وليست مجرد تفصيل للمعالجة المسبقة. إن اختيار التجزئة يحدد "الرؤية" التي يتلقاها المحول للرسم البياني، وبالتالي يحدد فئة التبعيات الهيكلية التي يمكن للنموذج التعبير عنها عند عمق محدد.

وتشمل النقاط الرئيسية التي أكدها المؤلفون ما يلي:

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

يخلص المؤلفون إلى أنه بينما يركز تحليلهم على تجزئة مستوى العقدة، فإن النتائج تشير إلى مبدأ أوسع: التمثيل المدخل هو محور حرج للتعقيد في تعلم الرسوم البيانية، ويجب أن يستكشف العمل المستقبلي تحديات الأمثلة وتجزئة مستوى الحواف.