ملخص تقني: طبقة تيكونوف المعممة لشبكات الرسم البياني العصبية القابلة للتفسير بالتصميم

بيان المشكلة

حققت شبكات الرسم البياني العصبية (GNNs) نجاحاً كبيراً في مهام تصنيف الرسوم البيانية والعقد من خلال تعلم تجميع الميزات عبر طوبولوجيا الرسم البياني. ومع ذلك، لا يزال التفسير يمثل تحدياً حرجاً. فخلافاً للشبكات العصبية التقليدية، يجب على شبكات (GNNs) أن تفسر ليس فقط كيفية تحويل الميزات المدخلة، بل وأيضاً كيفية استغلال طوبولوجيا الرسم البياني نفسها. تعتمد طرق التفسير الحالية غالباً على تقريبات لاحقة (Post-hoc) (مثل GNNExplainer، أو تدرج السالينسي/Saliency)، والتي تفتقر إلى ضمانات الأمانة (Faithfulness)، أو على بنيات ذات وحدتين حيث يتم فصل مستخرج التفسير عن المصنف، مما يسمح للمصنف بتجاهل التفسير أثناء تقليل الخسارة. علاوة على ذلك، تعاني شبكات (GNNs) العميقة من اعتلالات مثل "التنعيم المفرط" (Oversmoothing) (انهيار تمثيلات العقد) و"السحق المفرط" (Oversquashing) (الاضمحلال الأسي للحساسية بعيدة المدى).

المنهجية

يقترح المؤلفون طبقة تيكونوف (Tikhonov layer)، وهي طبقة لشبكة رسم بياني عصبية مصممة لتكون قابلة للتفسير من خلال البناء. يكمن الابتكار الجوهري في تقييد مصفوفة الانتشار في الرسم البياني $R$ بحل مغلق محدد مشتق من مسألة تنظيم تيكونوف للرسم البياني المعممة.

عامل الانتشار

بالنسبة لرسم بياني بـ "لابلاسيان" (Laplacian) معياري $L$، يكون مخرج الطبقة للميزات المدخلة $X$ هو:
$$X^{(k+1)} = \sigma \left( R X^{(k)} W \right)$$
حيث يتم تعريف مصفوفة الانتشار $R$ كالتالي:
$$R = (p(L) + Q)^{-1} Q$$
حيث:

• $L$ هو لابلاسيان الرسم البياني المعياري.
• $Q = \text{diag}(q_1, \dots, q_n)$ هي مصفوفة قطرية قابلة للتعلم من درجات أهمية العقد الإيجابية تماماً.
• $p(\cdot)$ هي متعددة حدود قابلة للتعلم تحقق $0 < p(\lambda) < 1$ لـ $\lambda \in [0, 2]$.
• $\sigma$ هي دالة غير خطية نقطية و $W$ هي مصفوفة أوزان.

التفسير التبايني

المؤثر $R$ هو المقلل الفريد ذو الشكل المغلق لمسألة تيكونوف المعممة:
$$R x = \arg \min_{z \in \mathbb{R}^n} \sum_{i \in V} q_i (x_i - z_i)^2 + z^\top p(L) z$$
هذه الصيغة توازن صراحةً بين دقة البيانات على مستوى العقدة (الموزونة بـ $q_i$) وبين التنظيم المدفوع بالطوبولوجيا (المحكوم بـ $p(L)$).

• $q_i$ كبيرة: تعتمد العقدة $i$ بشكل كبير على ميزاتها الخاصة؛ حيث يظل المخرج $z_i$ قريباً من $x_i$.
• $q_i$ صغيرة: تتخلى العقدة $i$ عن ميزاتها الخاصة لصالح حل مدفوع بطوبولوجيا الرسم البياني (النعومة أو الخصائص الطيفية المحددة لـ $p$).
• شكل $p(\lambda)$: يحدد طبيعة التأثير الطوبولوجي. الـ $p$ المتزايدة تعاقب الترددات العالية (تفضل التجانس/Homophily/النعومة)، بينما الـ $p$ المتناقصة تعاقب الترددات المنخفضة (تفضل التباين/Heterophily).

البنية والقدرة التعبيرية

للحفاظ على قدرة تعبيرية عالية دون التضحية بالتفسير، تستخدم البنية فصلاً للمهام (Separation of concerns):

1. شبكة Q (Q-Network): شبكة (GNN) مخصصة، قد تكون عميقة (مثل ChebNet أو ARMA)، تأخذ الرسم البياني $(G, X)$ كمدخل وتنتج درجات أهمية العقد $Q$. يتولى هذا المكون عملية التعلم التمثيلي المعقدة ويتكيف مع هياكل الرسم البياني والميزات المحلية.
2. طبقة تيكونوف (Tikhonov Layer): طبقة واحدة شفافة تطبق الانتشار $R$. لا تحتوي على عمليات تمرير رسائل معقدة أو عدم خطية مخفية؛ بارامتراتها هي معاملات متعدد الحدود لـ $p$ ومخرجات شبكة $Q$.
3. الرأس (Head): عملية تجميع عالمي (Global pooling) متبوعة بـ MLP للتنبؤ النهائي.

يدعم النموذج الامتدادات متعددة القنوات حيث تُستخدم عدة شبكات $Q$ ومتعددات حدود مستقلة، رغم أن التجارب تركز على حالة القناة الواحدة ($J=1$).

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

• الحوسبة: تتضمن عملية حساب $(p(L) + Q)^{-1}QX$ حل أنظمة خطية. يستخدم المؤلفون طريقة التدرج المترافق المسبق (PCG) مع مسبق شرط (Preconditioner) قطري (Jacobi) لتجنب تكلفة $O(n^3)$ للقلب الكثيف، محققين قابلية توسع قدرها $O(dTKm)$ حيث $T$ هو عدد التكرارات.
• الاشتقاق: لتجنب تخزين الرسم البيبع الحسابي للمحلل، يستخدم المؤلفون الاشتقاق الضمني (Implicit differentiation)، مما يتيد الحاجة إلى حل إضافي واحد لـ PCG في مرحلة التمرير الخلفي لحساب التدرجات بالنسبة لـ $Q$ و $p$.
• القيود: يتم تمثيل $p(\lambda)$ باستخدام كثيرات حدود بيرنشتاين (Bernstein polynomials) مع تفعيلات سيجمويد لفرض $0 < p(\lambda) < 1$ بصرامة. كما يتم تعيين درجات $q_i$ لقيم موجبة تماماً عبر دالة تقليم في الفضاء اللوغاريتمي (Log-space clamping).

المساهمات الرئيسية والخصائص النظرية

1. تفسير مدمج: تشكل الزوجة $\{ \{q_i\}_{i \in V}, p(\cdot) \}$ تفسيراً مباشراً وأميناً. تشير $q_i$ الكبيرة إلى الاعتماد على الميزات؛ بينما تشير $q_i$ الصغيرة إلى الاعتماد على الطوبولوجيا. يكشف شكل $p$ عن الانحياز الطيفي (التجانس، التباين، أو تمرير النطاق).
2. الاقتران الهيكلي: يثبت المؤلفون (Proposition 3.6) أن الخريطة $Q \mapsto R$ هي دالة حق (Injective). وخلافاً للطرق اللاحقة، فإن تغيير التفسير ($Q$) يغير بالضرورة عامل الانتشار ($R$)، مما يضمن أن التفسير أمين للحساب.
3. القدرة التعبيرية: يُظهر أن الطبقة كثيفة في فضاء المرشحات الطيفية المستمرة في الحالة المتجانسة. ومع وجود $Q$ غير متجانس، فإنها تتوسع بصرامة خارج المرشحات الطيفية التقليدية عبر كسر الثبات (Proposition 3.3).
4. تخفيف اعتلالات GNN:
   • التنعيم المفرط (Oversmoothing): يتم تجنبه باستخدام طبقة واحدة وعكسية $p(L) + Q$. يحدث انهيار العقد فقط إذا دفع النموذج عمداً جميع قيم $q_i \to 0$.
   • السحق المفرط (Oversquashing): يتم التحكم في معدل اضمحلال الحساسية بعيدة المدى $|R_{ij}|$ بواسطة معامل الشرط $\kappa$ للنظام، والذي يعتمد على $Q$ المتعلم. يمكن للنموذج تعلم تقليل $\kappa$ (عبر خفض قيم $q_i$ محددة) لتعزيز الحساسية بعيدة المدى عند الحاجة، مما يمثل مقايضة فعالة بين الدقة المحلية والوصول العالمي.

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

تم تقييم النموذج على مهام اصطناعية ومعايير قياسية، مما أظهر الأداء والتفسير معاً:

• مهام اصطناعية محكومة:
  • Colors-3: تعتمد المهمة كلياً على ميزات العقد. تعلم النموذج قيم $q_i$ كبيرة في كل مكان، متجاهلاً الطوبولوجيا بفعالية، وسلك سلوك الـ MLP، محققاً تحديداً صحيحاً بأن الميزات هي التي تقود التنبؤ.
  • Clique Distance: مهمة هيكلية بحتة. تعلم النموذج قيم $q_i$ صغيرة لعقد المسار (الاعتماد على الطوبولوجيا لاستشعار المسافة) وقيم $q_i$ كبيرة لعقد الـ Clique (المرتكزات)، محققاً دقة 100%.
  • Triangles: مهمة هيكلية لاكتشاف المثلثات. خصص النموذج قيم $q_i$ صغيرة بشكل عام ولكن قيم $q_i$ أكبر لقمم المثلثات، مما حدد النمط (Motif) دون إشراف.
• CSBM (نموذج الكتلة العشوائي السياقي): تتبع النموذج بنجاح عتبة الانتقال الطوري النظرية للاستعادة. انتقلت قيم $q_i$ المتعلمة بسلاسة من نظام يهيمن عليه الميزات (كبيرة $q_i$) إلى نظام تهيمن عليه الطوبولوجيا (صغيرة $q_i$)، مما حدد بدقة مصدر الإشارة في الأنظمة المختلطة.
• ECHO-diam (الانتشار بعيد المدى): في مهمة انحدار قطر الرسم البياني، حقق النموذج متوسط خطأ مطلق (MAE) قدره 1.17، متفوقاً على نماذج GNN العميقة (~1.6) ومقارباً أداء الـ Transformer (1.05). كشف التفسير أن النموذج خصص قيم $q_i$ كبيرة للعقد الطرفية (الأطراف) وقيم $q_i$ صغيرة للعقد الداخلية، مستخدماً التباين بين الأطراف المرتكزة والداخل المُنعم لتقدير القطر.

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

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

• الأمانة (Faithfulness): التفسير هو النموذج نفسه؛ لا يوجد رسم بياني فرعي منفصل أو تقريب.
• الدقة (Granularity): يوفر إجابة مستمرة وموزعة مكانياً (قيم $q_i$ متدرجة) بدلاً من الاختيار الثنائي للرسم البياني الفرعي.
• الأداء: يضاهي النموذج أو يتفوق على النماذج غير الشفافة (مثل GIN، GAT، وTransformers) في مهام متنوعة، مع توفير رؤى حول كيفية حل المهمة (مثل التمييز بين الاستدلال القائم على الميزات والاستدلال القائم على الطوبولوجيا).
• القيود: يقر المؤلفون بأن بعض التفسيرات قد تكون معقدة للبشر، وأن التكلفة الحسابية لـ PCG قد تكون عالية للمهام التي تتطلب تفاعلات بعيدة المدى (رغم اقتراحهم استخدام الجبر الخطي العددي العشوائي كاتجاه مستقبلي للتقريب).

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