محوّلات الرسوم والترميز الموضعي
Graph Transformers and Positional Encodings
كيف يُطبَّق المحوّل على الرسوم: الانتباه الشامل بين كل العقد يحل الانضغاط المفرط لكنه يفقد البنية، فتعود البنية عبر الترميز الموضعي والبنيوي (متجهات لابلاسيان الذاتية، المسارات العشوائية، المسافات، المركزية). يعرض الدرس محوّل Dwivedi وBresson وSAN وGraphormer وGraphGPS، وكلفة الانتباه التربيعية وحلولها.
أهداف الدرس
- شرح الفرق بين الانتباه المحلي (GAT) والشامل (المحوّل)
- بناء ترميز موضعي من متجهات لابلاسيان الذاتية ومعالجة غموض الإشارة
- فهم ترميزات Graphormer الثلاثة
- وصف معمارية GraphGPS الهجينة ومتى تُفضَّل
1 المحوّل رسم كامل
يمكن النظر إلى المحوّل على أنه GNN على رسم كامل: كل رمز يرسل رسالة إلى كل رمز، والانتباه هو أوزان الروابط. لذلك تطبيقه على الرسوم مباشر، وميزته أن كل عقدة ترى كل العقد في طبقة واحدة فيختفي الانضغاط المفرط. لكن المحوّل وحده لا يعرف البنية إطلاقاً: يعامل الرسم مجموعة عقد. في النصوص يحل الترميز الموضعي هذه المشكلة بموقع الكلمة؛ وفي الرسوم لا يوجد ترتيب طبيعي، فنحتاج ترميزات تعكس موقع العقدة في البنية ولا تخرق التكافؤ مع التبديل.
2 الترميز الموضعي والبنيوي
\Delta = I - D^{-\frac12}AD^{-\frac12}=U\Lambda U^{\top},\qquad \text{PE}_i=\big[U_{i,2},\dots,U_{i,k+1}\big]\text{RWSE}_i=\big[(D^{-1}A)_{ii},\,(D^{-1}A)^2_{ii},\,\dots,\,(D^{-1}A)^k_{ii}\big]- متجهات لابلاسيان الذاتية (LapPE): أول k متجه ذاتي غير تافه تعطي كل عقدة إحداثيات طيفية. مشكلتها غموض الإشارة (v و−v متجهان ذاتيان معاً) وغموض الأساس عند تكرار القيم الذاتية؛ تُعالج بقلب الإشارة عشوائياً أثناء التدريب أو بشبكات ثابتة تحت الإشارة.
- ترميز المسارات العشوائية (RWSE): احتمالات العودة إلى العقدة نفسها بعد 1 إلى k خطوة، [(RW)^1_ii, …, (RW)^k_ii]؛ ثابت تحت التبديل ولا غموض فيه، ويلتقط الحلقات.
- ترميز المسافة: أطوال أقصر المسارات بين الأزواج، تضاف انحيازاً في درجات الانتباه.
- ترميز المركزية: الدرجة تضاف إلى تمثيل العقدة.
3 Graphormer
فاز Graphormer (Ying وزملاؤه، 2021) بتحدي PCQM4M في OGB-LSC بثلاثة ترميزات: ترميز المركزية (تضمين للدرجة الداخلة والخارجة يُضاف إلى الخصائص)، وترميز مكاني (انحياز متعلَّم في الانتباه يعتمد على طول أقصر مسار بين العقدتين)، وترميز الروابط (متوسط خصائص الروابط على أقصر مسار). وأضاف عقدة افتراضية [VNode] متصلة بكل العقد لقراءة الرسم. ونجاحه مرتبط بالبيانات الكبيرة؛ على المجموعات الصغيرة يفرط في التخصيص.
A_{ij}=\frac{(h_iW_Q)(h_jW_K)^{\top}}{\sqrt{d}}+b_{\psi(i,j)}+c_{ij}4 GraphGPS: محلي وشامل معاً
اقترح Rampášek وزملاؤه (2022) وصفة عامة: في كل طبقة يُشغَّل بالتوازي نموذج انتقال رسائل محلي (مثل GatedGCN أو GINE) وانتباه شامل (محوّل كامل أو خطي مثل Performer)، ويُجمع الناتجان مع وصلات متبقية وتطبيع وMLP. يلتقط الجزء المحلي البنية الدقيقة، والجزء الشامل التفاعلات البعيدة، والترميزات الموضعية تُغذّى في المدخل. مع انتباه خطي تصبح الكلفة O(N + E) بدل O(N²)، فيعمل على رسوم بآلاف العقد.
X^{\ell+1}=\operatorname{MLP}\!\Big(\underbrace{\operatorname{MPNN}^{\ell}(X^{\ell},E^{\ell},A)}_{\text{local}}+\underbrace{\operatorname{GlobalAttn}^{\ell}(X^{\ell})}_{\text{global}}\Big)5 متى تستخدم محوّل الرسوم؟
المحوّلات قوية في مهام الرسوم الجزيئية ومهام التفاعلات البعيدة (LRGB)، خاصة مع بيانات كبيرة. وفي تصنيف العقد على رسوم ضخمة يصعب الانتباه الشامل، وغالباً تكفي GNN محلية جيدة الضبط، بل أظهرت دراسات لاحقة أن الفجوة بين المحوّلات وMPNN على LRGB تضيق كثيراً بضبط المعاملات جيداً. ابدأ بـ MPNN قوية مع ترميز RWSE، وانتقل إلى GPS حين تشير الأدلة إلى حاجة لتفاعلات بعيدة.
from torch_geometric.nn import GPSConv, GINEConv
import torch.nn as nn
import torch_geometric.transforms as T
transform = T.AddRandomWalkPE(walk_length=20, attr_name="pe") # RWSE
nn_ = nn.Sequential(nn.Linear(64, 64), nn.ReLU(), nn.Linear(64, 64))
conv = GPSConv(64, GINEConv(nn_), heads=4, attn_type="multihead")خلاصة الدرس
- المحوّل GNN على رسم كامل يحل الانضغاط ويفقد البنية
- الترميز الموضعي (LapPE) والبنيوي (RWSE) يعيدان البنية
- Graphormer: مركزية ومسافة وروابط في الانتباه
- GraphGPS يجمع محلياً وشاملاً، ومع الانتباه الخطي يصبح قابلاً للتوسع
تحقّق من فهمك
فكّر في الإجابة أولاً، ثم افتح السؤال لترى الجواب.
ما مشكلة غموض الإشارة في LapPE؟
إذا كان v متجهاً ذاتياً فإن −v كذلك، فقد يحصل الرسم نفسه على ترميزين مختلفين؛ تُعالج بقلب الإشارة عشوائياً أو بمعماريات ثابتة تحت الإشارة.
لماذا يُفضَّل RWSE أحياناً على LapPE؟
لأنه ثابت تحت التبديل بلا غموض إشارة أو أساس، ويلتقط بنى مثل الحلقات عبر احتمالات العودة.
تابع التعلّم
نماذج في هذا الدرس
مفاهيم مرتبطة
المراجع
- Dwivedi, V. P., & Bresson, X. (2021). A Generalization of Transformer Networks to Graphs. AAAI Workshop on Deep Learning on Graphs: Methods and Applications. arXiv: 2012.09699محوّل بياني بانتباه على الجيران وترميز موضعي من متجهات لابلاسيان الذاتية.
- Kreuzer, D., Beaini, D., Hamilton, W. L., Létourneau, V., & Tossou, P. (2021). Rethinking Graph Transformers with Spectral Attention. Advances in Neural Information Processing Systems (NeurIPS). arXiv: 2106.03893SAN: ترميز موضعي متعلَّم من الطيف الكامل للابلاسيان.
- Ying, C., Cai, T., Luo, S., Zheng, S., Ke, G., He, D., Shen, Y., & Liu, T.-Y. (2021). Do Transformers Really Perform Bad for Graph Representation?. Advances in Neural Information Processing Systems (NeurIPS). arXiv: 2106.05234Graphormer: ترميز المركزية والمسافة البنيوية وترميز الروابط.
- Rampášek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., & Beaini, D. (2022). Recipe for a General, Powerful, Scalable Graph Transformer. Advances in Neural Information Processing Systems (NeurIPS). arXiv: 2205.12454GraphGPS: طبقة MPNN محلية وانتباه شامل بالتوازي.
- Dwivedi, V. P., Rampášek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A. T., & Beaini, D. (2022). Long Range Graph Benchmark. Advances in Neural Information Processing Systems (NeurIPS), Datasets and Benchmarks. arXiv: 2206.08164LRGB: مهام تحتاج تفاعلات بعيدة المدى (Peptides وPascalVOC-SP وغيرها).
