ملخص تقني: اختبار "وايسفيلر-ليمان" غير مكتمل على الرسوم البيانية ذات الطيف البسيط، لذا يجب معايرتها معيارياً

بيان المشكلة

تُستخدم الشبكات العصبية الرسومية (GNNs) على نطاق واسع للتعلم على البيانات ذات البنية الرسومية، ومع ذلك فإن قدرتها التعبيرية غالباً ما تكون محدودة بتسلسل "وايسفيلر-ليمان" (WL). من النتائج المعروفة أن اختبار "وايسفيلر-ليمان" ذو البعد $k$ ($k$-WL) لا يستطيع التمييز بين جميع الرسوم البيانية غير المتماثلة. ومع ذلك، فإن فئة محددة من الرسوم البيانية — وهي تلك التي تمتلك طيفاً بسيطاً (حيث تمتلك مصفوفة التجاور قيماً ذاتية متميزة) — تسم old اختبار التماثل في زمن قدره $O(n^3)$. ورغم هذه القدرة النظرية على المعالجة، ظل التساؤل مفتوحاً عما إذا كان تسلسل WL، الذي يضع حداً أعلى لقدرة التعبير للعديد من الشبكات العصبية الرسومية، قادراً على التمييز بين جميع الرسوم البيانية ذات الطيف البسيط.

علاوة على ذلك، بينما يتم دمج الترميزات الموضعية الطيفية (مثل المتجهات الذاتية لـ Laplacian) في الشبكات العصبية الرسومية لتعزيز القدرة التعبيرية، إلا أنها تعاني من غموض متأصل: غموض الإشارة للطيف البسيط، وغموض القاعدة للقيم الذاتية المتكررة. الطرق الموجودة لمعالجة حالات الغموض هذه (مثل SignNet وMAP وOAP) غير مكتملة بشكل مثبت على الرسوم البيانية ذات الطيف البسيط، حيث تفشل في التمييز بين بعض الأزواج غير المتماثلة. هذا النقص في الاكتمال يحد من قدرة الشبكات العصبية الرسومية الطيفية على تحقيق التقريب الشامل لهذه الفئة من الرسوم البيانية.

المنهجية

1. إثبات عدم اكتمال WL على الأطياف البسيطة

أثبت المؤلفون أولاً أن تسلسل WL بأكمله غير مكتمل على الرسوم البيانية ذات الطيف البسيط.

• البناء: استخدموا بناء "كاي-فورير-إيمرمان" (CFI)، الذي يولد أزواجاً من الرسوم البيانية غير المتماثلة التي لا يمكن تمييزها بواسطة $k$-WL.
• الترميز: بما أن رسوم CFI القياسية لا تمتلك طيفاً بسيطاً، فقد قدم المؤلفون آلية ترميز تكاملية مبتكرة. قاموا بخرائط أنماط تجاور CFI إلى مصفوفة متعامدة $\tilde{X}$ تتكون من مدخلات صحيحة.
• تكوين الرسم متعدد الرسوم (Multigraph): باستخدام هذه المصفوفة المتعامدة ومصفوفة قطرية من القيم الذاتية الصحيحة المتميزة، قاموا ببناء زوج من الرسوم البيانية المتماثلة متعددة الرسوم ($A_{G,0}$ و $A_{G,1}$) ذات أطياف بسيطة.
• النتيجة: أثبتوا أن هذه الرسوم البيانية متعددة الرسوم المصنوعة ذات الطيف البسيط تظل غير قابلة للتمييز بواسطة اختبار $k$-WL، مما يوضح أن أي مستوى من تسلسل WL لا يمكنه حل مشكلة التماثل لهذه الفئة، رغم أن المشكلة قابلة للحل في زمن قدره $n^3$.

2. PRiSM: معايرة معيارية كاملة

لمعالجة قيود الطرق الطيفية الحالية، اقترح المؤلفون PRiSM (التقسيم، الصقل، الحل، المطابقة)، وهو إجراء معايرة معيارية كامل ومثبت لفك التحلل الطيفي للرسوم البيانية ذات الطيف البسيط.

• المدخلات: مصفوفة متعامدة عمودياً $U$ من المتجهات الذاتية.
• مجموعة الغموض: يتعامل الإجراء مع مجموعة الغموض $S_n \times \{-1, 1\}^k$ (التبديلات وقلب الإشارات).
• أربع مراحل:
  1. التقسيم (Partition): يتم تجميع الرؤوس بناءً على توقيعاتها الثابتة للإشارة (القيم المطلقة لمدخلات المتجه الذاتي).
  2. الصقل (Refine): يتم تطبيق نسخة طيفية من إجراء صقل الألوان الخاص بـ WL على التقسيم. يقوم هذا الإجراء بتكرار صقل فئات الرؤوس باستخدام المجموعة متعددة العناصر لسمات الحواف المعرفة بضرب عناصر المتجهات الذاتية ($U_v \odot U_u$) حتى يستقر التقسيم.
  3. الحل (Solve): يحدد التقسيم المستقر نظاماً من المعادلات الخطية عبر الحقل $\mathbb{Z}_2$. يفرض النظام أن يحتوي كل قسم في التقسيم على صف واحد على الأقل بمدخلات غير سالبة. يحدد حل هذا النظام الإشارات المعيارية الفريدة للمتجهات الذاتية (حتى بالنسبة لتماثلات الرسم البياني).
  4. المطابقة (Match): بمجرد تثبيت الإشارات، يتم ترتيب الصفوف أبجدياً (lexicographically) لحل غموض التبديل، مما ينتج عنه مصفوفة معيارية فريدة.
• التوسيع: بالنسبة للرسوم البيانية ذات القيم الذاتية المتكررة (غير البسيطة)، تم توسيع PRiSM بشكل تجريبي. حيث يطبق الإجراء الأساسي على كتلة الطيف البسيط ($m=1$) ويستخدم تحليل QR واختيار المحور لحل الفضاءات الذاتية من الرتب الأعلى ($m > 1$).

3. الضمانات النظرية

• الاكتمال: ثبت أن PRiSM هو إجراء معايرة صالح، مما يعني أنه ينتج نفس المخرجات للرسوم البيانية المتماثلة ومخرجات مختلفة للرسوم البيانية غير المتماثلة.
• التقريب الشامل: من خلال دمج PRiSM مع شبكة مجموعة عالمية (مثل DeepSets أو Transformers)، تحقق الشبكة الناتجة تقريباً شاملاً لأي دالة ثابتة التماثل على الرسوم البيانية ذات الطيف البسيط، مما يحل المشكلة المفتوحة المتعلقة بتحقيق الاكتمال للشبكات العصبية الرسومية الطيفية في هذه الفئة.

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

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

• النظرية 1: لكل عدد طبيعي $k$، توجد رسوم بيانية متعددة الرسوم ذات طيف بسيط وغير متماثلة بعدد عقد $\Theta(k)$ لا يمكن تمييزها بواسطة خوارزمية $k$-WL. وهذا يعني أن جميع عائلات GNN المتوافقة مع $k$-WL (بما في ذلك PPGN و $k$-GNNs و Graph Transformers) غير مكتملة على الرسوم البيانية ذات الطيف البسيط.
• النظرية 2: يوفر PRiSM معايرة معيارية صالحة لفك التحلل الطيفي للرسوم البيانية ذات الطيف البسيط.
• النظرية 3: تحقق النماذج المكونة من PRiM وشبكات المجموعة العالمية تقريباً شاملاً على الرسوم البيانية ذات الطيف البسيط.

الأداء التجريبي

قيم المؤلفون PRiSM على ثلاث معايض:

1. معيار BREC للتعبيرية: تفوق PRiSM على عمليات المعايرة المنافسة (MAP, OAP) في التمييز بين أزواج الرسوم البيانية غير المتماثلة، خاصة في فئتي Regular و Extension. لقد ميز بشكل صحيح 212/360 زوجاً مقارنة بـ 199/360 لـ MAP/OAP.
2. التنبؤ بالخصائص الجزيئية (ZINC, OGB-Mol): حقق PRism أداءً يضاهي أو يتفوق على أفضل النتائج في مهام الانحدار الجزيئي (ZINC) والتصنيف (MOLTOX21, MOLPCBA) باستخدام هياكل GatedGCN و PNA.
3. هياكل Transformer (OGB, Alchemy): عند استخدامه كترميز موضعي لـ Graph Transformers، تفوق PRiSM على جميع الخطوط المرجعية (LPE, MAP, OAP) عبر جميع مجموعات البيانات الأربع (MOLHIV, MOLCLINTOX, MOLBBBP, ALCHEMY). ويعزو المؤلفون ذلك إلى أن PRiSM يوفر ترتيباً عقدياً حتمياً بالإضافة إلى المتجهات الذاتية المصححة الإشارة، وهو أمر بالغ الأهمية لآليات الانتباه في الـ Transformers.

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

يدعي البحث أنه يحل فجوة أساسية في الفهم النظري لقدرة التعبير في GNN والأسالط الطيفية:

1. عدم اكتمال WL: أثبت بشكل نهائي أن تسلسل WL، رغم قوته المتزايدة، لا يمكنه التمييز بين جميع الرسوم البيانية ذات الطيف البسيط، وهي فئة يسهل فيها اختبار التماثل نظرياً.
2. أول معايرة معيارية كاملة: يُقدم PRiSM كأول عملية معايرة معيارية كاملة للإشارات لفك التحلل الطيفي للرسوم البيانية ذات الطيف البسيط، متجاوزاً قيود الطرق السابقة مثل MAP وOAP.
3. التقريب الشامل: يثبت العمل أن الشبكات العصبية الرسومية الطيفية يمكنها تحقيق تقريب شامل على الرسوم البيانية ذات الطيف البسيط إذا اقترنت بمعايرة كاملة مثل PRiSM، مما يبرر استخدام ترميزات Laplacian الموقعة معيارياً.
4. الفائدة العملية: تجريبياً، تُظهر الطريقة أن حل الغموض الطيفي بشكل كامل يؤدي إلى تحسينات ملموسة في المهام النهائية، متفوقة على مناهج المعايرة وتصحيح الإشارة الموجودة.

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