مبانی نظری ترانسفورمرهای گراف (GTs)

ترانسفورمرهای گراف (GTs) به عنوان یک جایگزین قدرتمند برای شبکه‌های عصبی گراف (GNN) برای وظایف یادگیری گراف ظاهر شده‌اند. مبانی نظری آنها ریشه در مفاهیمی مانند بیان، تعمیم و بهینه‌سازی دارد که به توضیح قابلیت‌ها و محدودیت‌های آنها کمک می‌کند. در زیر یک نمای کلی از زیربنای نظری GTها آورده است:

(1) بیانگر ترانسفورمرهای گراف

- مقایسه با GNNها: GTها محدودیت‌های کلیدی GNNها را برطرف می‌کنند، مانند هموارسازی بیش از حد (که در آن تعبیه گره‌ها در GNNهای عمیق غیرقابل تشخیص می‌شوند) و کم دسترسی (ناتوانی در گرفتن وابستگی‌های دوربرد) [1][3].

 - GTها از مکانیسم‌های خودتوجهی استفاده می‌کنند که به گره‌ها اجازه می‌دهد به تمام گره‌های دیگر در گراف توجه کنند و آنها را قادر می‌سازد تا روابط محلی و سراسری را به طور موثر ثبت کنند.

* تقریب تابع سراسری:

- GTها وقتی به رمزگذاری‌های ساختاری با حداکثر رسا، مانند فواصل کوتاه‌ترین مسیر یا ویژگی‌های گراف درجه بالاتر مجهز شوند، می‌توانند به حداکثر بیانی دست یابند. این باعث می‌شود که آنها تقریبگرهای تابع سراسری برای داده‌های گراف [1] باشند.

 - با این حال، این بیانگر بودن به کیفیت رمزگذاری‌های ساختاری بستگی دارد و GNN‌های با رمزگذاری‌های مشابه از نظر تئوری می‌توانند به قدرت بیانی قابل مقایسه دست یابند [1].

* ارتباطات با سلسله مراتب Weisfeiler-Lehman (WL):

 - ترانسفورمرهای گراف مرتبه بالاتر با سلسله مراتب k-WL تراز شده‌اند، که در آن ترانسفورمرهای k-order می‌توانند شبکه‌های ایزومورفیسم گراف مرتبه k (IGNs) را شبیه‌سازی کنند. این ارتباط توانایی آنها را در تشخیص ساختارهای پیچیده گراف برجسته می‌کند [1].

(2) تجزیه و تحلیل تعمیم

- پیچیدگی نمونه: یک مطالعه نظری بر روی GTهای کم عمق نشان می‌دهد که تعمیم به عواملی مانند کسر گره‌های متمایز (گره‌های مهم برای تعیین برچسب‌ها)، وضوح مرزهای تصمیم در بین این گره‌ها و کسری از برچسب‌های نویز بستگی دارد [2]. مکانیسم‌های توجه به خود و رمزگذاری‌های موقعیتی، تعمیم را با کوچک کردن نقشه‌های توجه و تمرکز بر همسایگی‌های اصلی در طول آموزش، افزایش می‌دهند [2].

- نقش رمزگذاری‌های موقعیتی: رمزگذاری‌های موقعیتی نسبی عملکرد GT را با تعبیه اطلاعات ساختاری مستقیماً در محاسبات توجه بهبود می‌بخشند و امکان بازنمایی و تعمیم بهتر ویژگی‌ها را فراهم می‌کنند [2].

- چالش‌های بهینه‌سازی: برهم‌کنش‌های غیر محدب در لایه‌ها و ساختارهای گراف بازگشتی، بهینه‌سازی در GTها را از لحاظ نظری پیچیده می‌کند. با این حال، نشان داده شده است که نزول گرادیان تصادفی (SGD) به خطای تعمیم صفر در شرایط خاص دست می‌یابد [2].

(3) رمزگذاری‌های ساختاری و موقعیتی

اهمیت رمزگذاری‌ها: رمزگذاری‌های ساختاری و موقعیتی برای آگاهی GTها از توپولوژی گراف حیاتی هستند. این رمزگذاری‌ها می‌توانند در سطوح محلی (به عنوان مثال، درجه گره)، نسبی (مثلاً فواصل کوتاه‌ترین مسیر)، یا سراسری (مانند ویژگی‌های طیفی) عمل کنند [1][3].

نمونه‌هایی از کدگذاری:

 - Graphormer فواصل کوتاه‌ترین مسیر و درجه گره را در مکانیسم توجه خود گنجانده است.

 - GRPE از تعاملات ضربی بین ویژگی‌های گره و لبه برای رمزگذاری موقعیتی نسبی استفاده می‌کند.

 - هسته‌های انتشار یا روش‌های مبتنی بر هسته حرارتی توجه را به سمت گره‌ها یا لبه‌های ساختاری مهم سوگیری می‌کنند [1][3].

(4) مکانیسم توجه در GTs

* توجه به خود: توجه به خود به GTها اجازه می‌دهد تا روابط زوجی دلخواه بین گره‌ها را مدل کنند و بر محدودیت‌های محلی GNNها غلبه کنند. مکانیسم‌های توجه پراکنده (به عنوان مثال، اکسفرمر) پیچیدگی محاسباتی را کاهش می‌دهد در حالی که مدل‌سازی زمینه سراسری را حفظ می‌کند[6].

* توجه به ساختار: توجه آگاه به ساختار، توپولوژی گراف را مستقیماً در مکانیسم توجه ادغام می‌کند، و تضمین می‌کند که سوگیری‌های ساختاری یادگیری را هدایت می‌کنند. به عنوان مثال می‌توان به هسته‌ها یا اصلاحات آگاه از لبه در توجه استاندارد اشاره کرد [1][3].

(5) محدودیت‌ها و چالش‌ها

وابستگی به سوگیری‌های ساختاری: در حالی که GTها با رمزگذاری‌های ساختاری مناسب بسیار گویا هستند، عملکرد آنها به شدت به کیفیت این کدگذاری‌ها بستگی دارد.

پیچیدگی محاسباتی: پیچیدگی درجه دوم مکانیزم‌های استاندارد توجه به خود، چالش‌های مقیاس‌پذیری را برای گراف‌های بزرگ ایجاد می‌کند. تکنیک‌های توجه پراکنده تا حدی به این موضوع می‌پردازند، اما ممکن است تا حدی بیانگر را از دست بدهند [6].

برابری نظری با GNNها: تحت شرایط خاص، GNNهای تقویت شده با گره‌های مجازی یا اتصالات مرتبه بالاتر می‌توانند رفتار GT را شبیه‌سازی کنند، که نشان می‌دهد GTها همیشه از نظر بیانی برتری ذاتی نسبت به GNNها ندارند [1].

نتیجه‌گیری

مبانی نظری ترانسفورمرهای گراف نقاط قوت آنها را در پرداختن به محدودیت‌های GNN از طریق مکانیسم‌های توجه سراسری، افزایش بیان از طریق رمزگذاری‌های ساختاری، و تعمیم بهبود یافته از طریق رمزگذاری‌های موقعیتی برجسته می‌کند. با این حال، وابستگی آن‌ها به سوگیری‌های ساختاری با کیفیت بالا و چالش‌های محاسباتی همچنان حوزه‌های فعال تحقیقاتی است. هدف کار آینده، بهینه‌سازی بیشتر معماری‌های GT در حین بررسی محدودیت‌های نظری آن‌ها نسبت به سایر پارادایم‌های یادگیری گراف است.

[1] https://openreview.net/pdf?id=HhbqHBBrfZ

[2] https://openreview.net/forum?id=aJl5aK9n7e

[3] https://arxiv.org/abs/2502.16533

[4] https://arxiv.org/html/2407.09777v1

[5] https://arxiv.org/html/2302.04181v3

[6] https://research.google/blog/exphormer-scaling-transformers-for-graph-structured-data/

[7] https://www.mdpi.com/2413-4155/5/4/46

[8] https://www.datacamp.com/tutorial/how-transformers-work