تعلم الرسوم البيانية2021متقدم11 دقيقة قراءة
هل المحوِّلات فعلاً ضعيفة في تمثيل البيانات البيانية؟
Do Transformers Really Perform Bad for Graph Representation?
Ying, C. · Cai, T. · Luo, S. · Zheng, S. · Ke, G. · He, D. · Shen, Y. · Liu, T.-Y. — NeurIPS
المشكلة
بحلول عام 2021 كان قد فرض هيمنته على معالجة اللغة الطبيعية والرؤية الحاسوبية، لكنه ظلّ يتخلّف عن بنيات الشبكات العصبية البيانية الرائجة مثل GIN وGCN وGAT في مهام التنبؤ على مستوى البيان الكامل. جوهر المشكلة أن البيانات البيانية تفتقر إلى الترتيب التسلسلي أو الشبكي الذي يستغلّه المحوِّل طبيعياً. العقد تقع في فضاء غير إقليدي ومتصلة بأضلاع بلا ترتيب معياري. ما لم يُحقن هذا الهيكل البنيوي في النموذج، يتعامل مع كل زوج من العقد بالتساوي — متجاهلاً الطوبولوجيا والمسافات وأهمية العقد. السؤال كان: هل يمكن لمحوِّل قياسي أن يُضاهي الشبكات العصبية البيانية أو يتفوّق عليها إن أُمِدَّ بالترميز البنيوي المناسب؟
الإسهام
قدّمت الورقة Graphormer — محوِّل قياسي مُعزَّز بثلاث ترميزات بنيوية: (1) يُضيف متجهات قابلة للتعلّم بناءً على درجة العقدة إلى المدخلات، ليُخبر النموذج بأهمية كل عقدة. (2) يُضيف انحيازاً قابلاً للتعلّم مبنياً على إلى مصفوفة الانتباه، مانحاً النموذج إحساساً بطوبولوجيا البيان. (3) يُجمِّع سمات الأضلاع على طول أقصر المسارات كانحياز إضافي للانتباه. بهذه الترميزات، أثبت المؤلفون رياضياً أن Graphormer يشمل GIN وGCN وGraphSAGE كحالات خاصة، ويستطيع تمييز بيانات لا يميّزها اختبار فايسفيلر-ليمان الأول. حصل Graphormer على المركز الأول في تحدّي OGB واسع النطاق وسجّل أفضل النتائج على معايير MolHIV وMolPCBA وZINC.
الأثر
أثبت Graphormer أن المحوِّلات قادرة على التفوّق في تعلّم تمثيل البيانات البيانية حين تُزوَّد بالترميزات البنيوية المناسبة، منهياً الافتراض السائد بأن الشبكات العصبية البيانية متفوّقة بطبيعتها في مهام البيانات. أصبحت ترميزات المركزية والمكان تقنيات أساسية تبنّتها محوِّلات البيانات اللاحقة. أثّر العمل مباشرة في AlphaFold2 الذي استعار أفكاراً مماثلة لترميز بنية البروتينات. وأطلق Graphormer موجة من الأبحاث في محوِّلات البيانات للبيانات البيانية وتطبيق بنيات المحوِّل على التنبؤ بخصائص الجزيئات واكتشاف الأدوية.
تخيّل قاعة مؤتمر مليئة بالحضور. التقليدية تعمل كـلعبة الهاتف: كل شخص لا يستطيع الكلام إلا مع جاره المباشر، وكلّما انتقلت الرسالة عبر وسطاء أكثر ازداد تشوّهها.
المُحوِّل يأخذ منهجاً مختلفاً تماماً: يضع الجميع في قاعة مفتوحة يستطيع فيها أيّ شخص مخاطبة أيّ شخص آخر مباشرة. المشكلة أنه بدون شارات تعريف أو مخطط جلوس أو لافتات ممرّات، يتحوّل النقاش إلى فوضى — لا أحد يعرف من الشخص المهم، ومن القريب منه، وما العلاقة التي تربط أيّ شخصين.
هنا يأتي دور Graphormer بثلاث أدوات: (1) شارة على صدر كل شخص تكشف مدى شعبيته (كم اتصالاً يملك)، (2) بطاقة توضّح كم مصافحة تفصل بين أيّ شخصين، (3) لافتات على كل ممرّ تصف طبيعة العلاقة بين طرفيه. بهذه الأدوات يتحوّل الحوار المفتوح إلى نقاش منظَّم — ويتفوّق بفارق كبير على لعبة الهاتف.
الفجوة: لماذا عانت المحوِّلات مع البيانات البيانية
في معالجة اللغة الطبيعية، الكلمات مرتّبة في تسلسل واضح — الموضع 1 ثم 2 ثم 3 — والمُحوِّل يستخدم الترميز الموضعي ليعرف مكان كل رمز. وفي الرؤية الحاسوبية، البكسلات موزّعة على شبكة ثنائية الأبعاد منتظمة. لكن في البيانات البيانية الوضع مختلف تماماً: لا يوجد ترتيب طبيعي بين العقد. العقدة 5 ليست «بعد» العقدة 4 — فقد تكون على بُعد ثلاث قفزات، أو متصلة بها مباشرة، أو في جزء معزول تماماً من البيان.
الشبكات العصبية البيانية القياسية تتعامل مع هذا التحدّي بتقييد نطاق التواصل: في آلية ، كل عقدة لا تجمع معلومات إلا من جيرانها المباشرين. بعد طبقة، تكون العقدة قد اطّلعت على جوارها حتى مسافة قفزة. هذا الأسلوب يحترم بنية البيان بطبيعته، لكنه يُقيّد — فالعقد البعيدة تحتاج طبقات كثيرة حتى تتبادل المعلومات، والشبكات العميقة تقع في مشكلة حيث تتقارب تمثيلات العقد تدريجياً وتفقد ما يميّز بعضها عن بعض.
في المقابل، الانتباه الذاتي في المُحوِّل يمنح كل عقدة حقلاً استقبالياً شاملاً من طبقة واحدة فقط. لكن المشكلة أنه بدون معلومات بنيوية، يتعامل الانتباه مع جميع أزواج العقد بالتساوي — لا يدرك أن العقدتين 3 و7 متجاورتان بينما العقدتين 3 و42 تفصلهما خمس قفزات. ولهذا بالتحديد فشل التطبيق المباشر للمحوِّلات على البيانات البيانية.
الترميز الأول: المركزية — إخبار النموذج بأهمية كل عقدة
في أيّ بيان، ليست كل العقد متساوية في الأهمية. خذ مثلاً شبكة اجتماعية: شخصية مشهورة بملايين المتابعين تختلف بنيوياً اختلافاً جذرياً عن مستخدم عادي. وفي الجزيئات الكيميائية، الذرة المرتبطة بعدة ذرات أخرى تؤدّي دوراً كيميائياً مختلفاً تماماً عن ذرة طرفية. لكن الانتباه الذاتي القياسي يحسب التشابه اعتماداً على سمات العقد فحسب — ولا يملك أيّ فكرة عن عدد اتصالات كل عقدة.
الحل الذي يقدّمه Graphormer هو ترميز المركزية: لكل عقدة، يسترجع النموذج متجه قابل للتعلّم يعتمد على درجة العقدة (أي عدد اتصالاتها)، ويُضيفه مباشرة إلى سمات العقدة عند طبقة الإدخال. تخيّل الأمر وكأنك تعلّق «شارة شهرة» على صدر كل عقدة قبل أن ينطلق الحوار.
في البيانات الموجَّهة يُستخدم تضمينان منفصلان: واحد للدرجة الداخلة وآخر للخارجة. أمّا في البيانات غير الموجَّهة، فتكفي درجة واحدة. اللافت أن هذا التصميم بسيط للغاية — ورغم ذلك تكشف أنه من أكثر المكوّنات إسهاماً في تحسين الأداء.
الترميز الثاني: المكان — إخبار النموذج بمن يجاور من
في التسلسلات، يعرف المُحوِّل أن الرمز 3 أقرب إلى الرمز 4 منه إلى الرمز 100 بفضل الترميز الموضعي. البيانات البيانية تحتاج آلية مشابهة، لكن مفهوم «الموضع» في البيان يختلف جوهرياً — هنا المقصود هو المسافة الطوبولوجية بين العقد، لا مجرد ترتيب رقمي.
الترميز المكاني في Graphormer يعتمد على مسافة أقصر مسار بين أيّ عقدتين كمقياس للبنية. الفكرة بسيطة: لكل قيمة مسافة ممكنة يوجد انحياز عددي قابل للتعلّم يُضاف مباشرة إلى قبل تطبيق . فإذا كانت عقدتان على بُعد قفزة واحدة، تحصلان على الانحياز ؛ وإن فصلتهما 3 قفزات تحصلان على ؛ وإن لم تكونا متصلتين أصلاً تحصلان على انحياز خاص .
الجميل في هذا التصميم أنه يُدخِل مرناً: إن تعلّم النموذج أن ، فسيُعطي أولوية للعقد القريبة — وكأنه يحاكي المحلية التي تجعل الشبكات العصبية البيانية فعّالة. لكن بإمكانه أيضاً تعلّم أنماط مختلفة: ربما يتعلّم في بعض الرؤوس أن ، فيلتقط العلاقات بعيدة المدى التي تعجز عنها الشبكات البيانية تماماً.
الترميز الثالث: الأضلاع — وضع لافتات على الممرّات
كثير من البيانات الحقيقية تحمل أضلاعها معلومات غنية. في البيانات الجزيئية مثلاً، كل ضلع يمثّل رابطة كيميائية لها نوع محدّد (أحادية أو ثنائية أو عطرية)، وفي بيانات المعرفة يحمل كل ضلع تسمية العلاقة بين الكيانين. الشبكات العصبية البيانية السابقة كانت ترمّز سمات الأضلاع بطريقتين محدودتين: إما بإضافتها إلى سمات العقد المتصلة، أو باستخدامها أثناء خطوة من الجيران. المشكلة أن كلتا الطريقتين لا توصل معلومات الضلع إلا للعقد المتجاورة مباشرة.
ترميز الأضلاع في Graphormer يأخذ منحى مختلفاً. لأيّ زوج من العقد ، يبحث النموذج عن أقصر مسار بينهما — أي سلسلة الأضلاع — ثم يحسب متوسط الجداء النقطي بين متجه سمات كل ضلع على هذا المسار ومتجه وزن قابل للتعلّم، ويُضيف الناتج كانحياز إضافي إلى درجة الانتباه.
النتيجة أنه حتى بالنسبة للعقد غير المتجاورة، يأخذ النموذج بعين الاعتبار المسار الكامل الذي يصل بينها وسمات كل ضلع على طول هذا المسار. تخيّل الأمر وكأنك تقرأ كل لافتة في الممرّات بين قاعتَي مؤتمر، بدلاً من الاكتفاء بقراءة لافتة الباب فقط.
البنية: العقدة الافتراضية وطبقات Graphormer
حين نريد التنبؤ بخاصية تخصّ البيان بأكمله — لا عقدة بعينها — نحتاج آلية تُجمّع تمثيلات جميع العقد في متجه واحد يختصر البيان كله. الشبكات العصبية البيانية السابقة اعتمدت على دوال قراءة (كالجمع أو المتوسط أو التجميع المُتعلَّم). Graphormer يستعير فكرة ذكية من BERT: يُضيف ([VNode]) متصلة بكل عقدة في البيان، تؤدّي الدور نفسه الذي يؤدّيه رمز [CLS] في BERT.
تُشارك [VNode] في الانتباه الذاتي كأيّ عقدة حقيقية، لكن ترميزها المكاني يستخدم قيمة عددية قابلة للتعلّم مستقلة — لتمييز الاتصالات «الافتراضية» عن أضلاع البيان الفعلية. وبعد مرور البيانات عبر جميع طبقات المُحوِّل، يصبح التمثيل النهائي لهذه العقدة الافتراضية هو المُخرج الذي يمثّل البيان بأكمله.
من حيث البنية الداخلية، كل طبقة في Graphormer تتبع نمط المُحوِّل القياسي مع تسوية مُقدَّمة: أولاً قبل ، ثم ، ثم تسوية الطبقة مرة أخرى قبل ، ثم اتصال بقائي آخر. وتستخدم الشبكة الأمامية نفس البُعد ، ممّا يُبقي البنية بسيطة ومعيارية.
القدرة التعبيرية: Graphormer يشمل الشبكات البيانية الرائجة
السؤال المنطقي هنا: هل هذه الترميزات تجعل Graphormer أقوى تعبيرياً من الشبكات العصبية البيانية الحالية، أم أنه مجرد بديل مختلف؟ الإجابة يقدّمها المؤلفون بإثبات رياضي صريح: باختيار أوزان مناسبة، تستطيع طبقة واحدة من Graphormer محاكاة خطوة التجميع والدمج في كلٍّ من GIN وGCN وGraphSAGE.
الفكرة المحورية أن الترميز المكاني يُمكِّن الانتباه الذاتي من التفريق بين الجيران () وغير الجيران (). وحين يُدمَج مع ترميز المركزية (الذي يوفّر معلومة الدرجة)، يصبح النموذج قادراً على حساب المجموع أو المتوسط أو الأقصى على مجموعة الجيران — وهذا تحديداً ما تفعله دوال التجميع في الشبكات البيانية.
لكن القصة لا تتوقف هنا. شبكات تمرير الرسائل القياسية محدودة رياضياً بقدرة الأول على تمييز — بمعنى أن هناك بيانات غير متماثلة تعجز هذه الشبكات عن التفريق بينها. المؤلفون يقدّمون مثالاً ملموساً يستطيع فيه Graphormer، بالاعتماد على مسافات أقصر المسارات، التمييز بين بيانات يعجز الاختبار عن تمييزها، لأن هذه المسافات تلتقط أنماطاً بنيوية على المستوى الشامل لا تصل إليها آليات التمرير المحلي.
النتائج: تصدُّر معايير البيانات البيانية
اختُبر Graphormer على أربعة معايير رئيسية. في تحدّي OGB واسع النطاق (PCQM4M-LSC) الذي يضمّ أكثر من 3.8 مليون بيان جزيئي، حقّق خطأً مطلقاً متوسطاً قدره 0.1234 — أي تحسّن نسبي بنسبة 11.5% مقارنة بأفضل نتيجة سابقة لـ GIN-VN (0.1395). وعلى MolHIV بلغ 80.51% في AUC، وعلى MolPCBA سجّل 31.39% في AP، وعلى ZINC حقّق أفضل نتيجة جديدة بخطأ 0.122 متفوّقاً على SAN الذي وصل إلى 0.139.
النقطة الأهم هنا أن المبسَّط (GT) الذي اقترحه دويفيدي وبريسون — والذي يعتمد ترميزاً موضعياً لابلاسياً — لم يتفوّق على GIN-VN حتى بعد تكبيره إلى 83 مليون معامل. وهذا دليل واضح على أن المُحوِّل وحده لا يكفي؛ العبرة في كيفية حقن المعلومات البنيوية. ترميزات Graphormer الثلاث هي ما يصنع الفارق بين الفشل وتصدُّر النتائج.
دراسة الاجتزاء: كل ترميز يستحقّ مكانه
دراسة الاجتزاء توضّح بدقة مقدار إسهام كل مكوّن. نبدأ من محوِّل مجرّد بدون أيّ ترميز بنيوي (خطأ 0.2276). بإضافة الترميز المكاني ينخفض الخطأ إلى 0.1427. ثم بإضافة ترميز المركزية ينخفض أكثر إلى 0.1396. وأخيراً، ترميز الأضلاع عبر انحياز الانتباه يُوصله إلى 0.1304.
هناك مقارنة تستحقّ التوقف عندها: الترميز الموضعي اللابلاسي (0.1483) أضعف بوضوح من الترميز المكاني (0.1427) رغم أن كليهما يرمّز العلاقات بين العقد. السرّ أن الترميز المكاني يقدّم معلومات زوجية — أي المسافة بين كل عقدتين — على هيئة انحياز في مصفوفة الانتباه، بينما الترميز اللابلاسي يقدّم معلومات لكل عقدة على حدة تُضاف إلى المدخلات. الفرق جوهري: النهج الزوجي يتحكّم مباشرة في أيّ أزواج العقد يتواصل بعضها مع بعض بقوة، فيمنح النموذج تحكّماً بنيوياً أدقّ بكثير.
الشيفرة: الانتباه بالترميزات البنيوية
مبسَّط لإظهار الفكرة — ليس التنفيذ الحقيقي.
import torch
import torch.nn as nn
class GraphormerAttention(nn.Module):
def __init__(self, d_model, n_heads, max_dist=20):
super().__init__()
self.n_heads = n_heads
self.d_k = d_model // n_heads
self.W_Q = nn.Linear(d_model, d_model)
self.W_K = nn.Linear(d_model, d_model)
self.W_V = nn.Linear(d_model, d_model)
# ترميز مكاني: انحياز قابل للتعلّم لكل مسافة ولكل رأس
self.spatial_bias = nn.Embedding(max_dist + 2, n_heads)
# ترميز أضلاع: وزن قابل للتعلّم لكل موقع في المسار
self.edge_proj = nn.Linear(d_edge, n_heads)
def forward(self, x, dist_matrix, edge_encoding):
# x: (دفعة، عدد_العقد، بُعد_النموذج)
Q = self.W_Q(x) # إسقاط الاستعلام
K = self.W_K(x) # إسقاط المفتاح
V = self.W_V(x) # إسقاط القيمة
# درجات الانتباه القياسية
attn = (Q @ K.transpose(-2, -1)) / (self.d_k ** 0.5)
# إضافة الانحياز المكاني من مسافات أقصر المسارات
spatial = self.spatial_bias(dist_matrix)
attn = attn + spatial.permute(0, 3, 1, 2)
# إضافة انحياز ترميز الأضلاع
attn = attn + edge_encoding
# softmax والمجموع الموزون
attn = torch.softmax(attn, dim=-1)
return attn @ V
الخط الزمني: صعود محوِّلات البيانات البيانية
2017
المحوِّل (فازواني وآخرون)
قدّم الانتباه الذاتي للتسلسلات. حقل استقبالي شامل من طبقة واحدة، لكنه صُمّم للبيانات التسلسلية مع ترميز موضعي.
2018
GAT — شبكات الانتباه البيانية
طبّق الانتباه على البيانات البيانية لكن مقصوراً على الجيران — أوزان الانتباه تستبدل التجميع الثابت لكن الحقل الاستقبالي يبقى محلياً.
2019
GIN — ما مدى قوة الشبكات العصبية البيانية؟
أثبتت أن الشبكات العصبية البيانية محدودة باختبار فايسفيلر-ليمان الأول. GIN يبلغ هذا الحدّ بتجميع المجموع، مُرسياً السقف النظري لشبكات تمرير الرسائل.
2021
Graphormer (هذه الورقة)
ثلاث ترميزات بنيوية تجعل محوِّلاً قياسياً يتصدّر معايير البيانات. يشمل GIN وGCN وGraphSAGE ويتجاوز اختبار فايسفيلر-ليمان الأول. فاز بتحدّي OGB-LSC.
2021
AlphaFold2
استخدم أفكار الترميز المكاني الزوجي المشابهة لـ Graphormer للتنبؤ ببنية البروتينات. فاز بمسابقة CASP14 وأحدث ثورة في علم الأحياء البنيوي.
2022
موجة محوِّلات البيانات البيانية
GPS وTokenGT وGraphGPS وغيرها بنت على أفكار Graphormer. أصبحت محوِّلات البيانات البيانية اتجاهاً بحثياً رئيسياً مع ترميزات موضعية وبنيوية متخصّصة.
المرجعYing, Cai, Luo, Zheng, Ke, He, Shen, Liu. Do Transformers Really Perform Bad for Graph Representation?. NeurIPS, 2021.
مصطلحات هذه الورقة
- الشبكات العصبية الرسومية (البيانية)Graph Neural Network (GNN)
- الانتباه الذاتيSelf-Attention
- الترميز الموضعيPositional Encoding
- مصفوفة التجاورAdjacency Matrix
- تمرير الرسائلMessage Passing
- التجميعAggregation
- تشابُه البيانات البيانيةGraph Isomorphism
- الانتباه المتعدد المساراتMulti-Head Attention
- التسوية الطبقيةLayer Normalization
- الوصلة التجاوزيةResidual Connection
- التضمينEmbedding
- سوفت ماكسSoftmax
- درجات الانتباه البينيةAttention Score
- تعلّم تمثيلات الرسوم البيانيةGraph Representation Learning
- الانحياز الاستقرائي المسبقInductive Bias