شبکه عصبی گراف

شبکه عصبی گراف (GNN) یک کلاس از شبکه‌های عصبی مصنوعی برای پردازش داده‌ها است که می‌تواند به صورت یک گراف نمایش داده شود.

در موضوع کلی‌تر "یادگیری ژرف هندسی"، برخی از معماری‌های شبکه عصبی خاص موجود را می‌توان به عنوان شبکه‌های عصبی گرافی که بر روی گراف‌های خوش‌تعریف عمل می‌کنند تفسیر کرد. شبکه‌های عصبی پیچشی، در زمینه بینایی کامپیوتری، می‌توانند به‌عنوان یک شبکه‌ عصبی گراف به اعمال شده روی گراف‌هایی که به‌صورت شبکه‌هایی از پیکسل‌ها ساخته شده‌اند، دیده شوند. ترنسفورمرها، در زمینه پردازش زبان‌های طبیعی، می‌توانند به‌عنوان شبکه‌های عصبی گرافی دیده شوند که برای گراف کاملی که گره‌های آن‌ها کلمات در یک جمله هستند اعمال می‌شوند.

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

حوزه های کاربرد شبکه‌های عصبی گراف شامل شبکه‌های اجتماعی، شبکه های استنادی، زیست‌شناسی مولکولی، شیمی، فیزیک و مسائل بهینه‌سازی ترکیبیاتی ان‌پی-سخت است.

معماری

در معماری یک شبکه عصبی گراف عمومی لایه‌های اساسی زیر پیاده‌سازی می‌شوند:

1. هم‌وردای جایگشتی: یک لایه هم‌وردای جایگشتی، نمایشی از یک گراف را به یک نمایش به‌روز شده از همان گراف نگاشت می‌کند. در مقالات، لایه‌های هم‌وردای جایگشتی از طریق ارسال پیام زوجی بین گره‌های گراف پیاده‌سازی می‌شوند. به طور شهودی، در یک لایه ارسال پیام، گره‌ها با جمع‌آوری پیام‌های دریافتی از همسایگان خود، نمایش خود را به‌روزرسانی می‌کنند. به این ترتیب، هر لایه ارسال پیام، میدان دریافتی شبکه‌ عصبی گراف را یک جهش افزایش می‌دهد.

   

   بلوک‌های اصلی ساختار یک شبکه عصبی گراف (GNN). $(1)$ لایه هم‌وردا به جایگشت. $(2)$ لایه ادغام محلی. $(3)$ لایه ادغام سراسری (یا بازخواندن). رنگ‌ها ویژگی‌ها را نشان می‌دهند.

2. ادغام محلی:‌ یک لایه ادغام محلی، گراف را از طریق نمونه‌کاهی، ناهموار می‌کند. از ادغام محلی برای افزایش میدان دریافتی یک شبکه عصبی گراف، به روشی مشابه لایه‌های ادغام در شبکه‌های عصبی پیچشی استفاده می‌شود. به عنوان مثال می‌توان به ادغام k-نزدیک‌ترین همسایه‌ها، ادغام top-k و ادغام توجه‌به‌خود اشاره کرد.
3. ادغام سراسری: یک لایه ادغام سراسری، که همچنین به عنوان لایه بازخوانی شناخته می شود، نمایشی با اندازه ثابت از کل گراف ارائه می‌دهد. لایه ادغام سراسری باید نسبت به تغییرات جایگشتی بدون تغییر بماند، به طوری که جایگشت در ترتیب گره‌ها و یال‌های گراف، خروجی نهایی را تغییر ندهد. مثال‌ها عبارتند از: مجموع، میانگین یا حداکثر عناصر.

لایه‌های ارسال پیام

به‌روزرسانی نمایش گره‌ها در لایه شبکه عصبی ارسال پیام. گره $\mathbf {x} _{0}$ پیام ارسال‌شده توسط تمام همسایه‌های مستقیمش یعنی $\mathbf {x} _{1}$ تا $\mathbf {x} _{4}$ را دریافت می‌کند. این پیام‌ها توسط تابع پیام $\phi$ محاسبه می‌شوند که توصیفی از هردوی فرستنده‌ها و گیرنده‌ها است.

لایه‌های انتقال پیام،‌ لایه‌های هم‌وردا نسبت به جایگشت هستند که یک گراف را به نمایش به‌روز شده‌ای از همان گراف نگاشت می‌کنند. در واقع، می‌توان این لایه‌ها را به عنوان شبکه‌های عصبی ارسال‌کننده پیام (MPNN) عنوان کرد.

فرض کنید $G=(V,E)$ یک گراف با مجموعه گره‌های $V$ و مجموعه یال‌های $E$ و $N_{u}$ همسایگی گره $u\in V$ باشد. همچنین فرض کنید $\mathbf {x} _{u}$ بردار ویژگی‌های گره $u\in V$ و $\mathbf {e} _{uv}$ بردار ویژگی‌های یال $(u,v)\in E$ باشد. یک شبکه عصبی ارسال‌کننده پیام می‌تواند به شکل زیر بیان شود:

$\mathbf {h} _{u}=\phi \left(\mathbf {x_{u}} ,\bigoplus _{v\in N_{u}}\psi (\mathbf {x} _{u},\mathbf {x} _{v},\mathbf {e} _{uv})\right)$

که $\phi$ و $\psi$ توابع دیفرانسیل‌پذیر و $\bigoplus$ یک عملگر تجمیع ناوردا نسبت به جایگشت است که می‌تواند تعداد دلخواهی ورودی را بپذیرد. توابع $\phi$ و $\psi$ اغلب به ترتیب توابع به‌روزرسانی و پیام می‌نامند. به طور شهودی،‌ یک بلوک محاسباتی شبکه عصبی ارسال‌کننده پیام، گره‌های گراف با تجمیع پیام‌های دریافت شده از همسایه‌هایشان،‌نمایش خود را به‌روز می‌کنند.

خروجی های یک یا چند لایه شبکه عصبی ارسال‌کننده پیام، نمایش‌های گره به فرم $\mathbf {h} _{u}$ برای هر گره $u\in V$ هستند. این نمایش‌های گره می‌توانند برای هر کار جریان پایین‌دست مانند طبقه‌بندی گر‌ه‌ها یا پیش‌بینی یال‌ها به‌کار روند.

لایه‌های ادغام محلی

لایه‌های ادغام محلی گراف را از طریق نمونه‌کاهی ناهموار می‌کنند. ما در اینجا دو استراتژی ادغام محلی قابل یادگیری را ارائه می‌کنیم. در هر مورد، ورودی یک گراف اولیه است که با ماتریس $\mathbf {X}$ به عنوان ماتریس ویژگی‌های گره‌ها و ماتریس مجاورت $\mathbf {A}$ نمایش داده می‌شود. خروجی نیز یک ماتریس ویژگی جدید$\mathbf {X} '$ و یک ماتریس مجاورت جدید $\mathbf {A} '$ است.

ادغام Top-k

ابتدا قرار می‌دهیم

$\mathbf {y} ={\frac {\mathbf {X} \mathbf {p} }{\Vert \mathbf {p} \Vert }}$

که $\mathbf {p}$ یک بردار پروجکشن قابل یادگیری است. بردار پروجکشن $\mathbf {p}$ یک مقدار پروجکشن اسکالر برای هر گره محاسبه می‌کند.

لایه ادغام Top-k را می‌توان به شکل زیر بیان کرد:

$\mathbf {X} '=(\mathbf {X} \odot {\text{sigmoid}}(\mathbf {y} ))_{\mathbf {i} }$

$\mathbf {A} '=\mathbf {A} _{\mathbf {i} ,\mathbf {i} }$

که $\mathbf {i} ={\text{top}}_{k}(\mathbf {y} )$ زیرمجموعه $k$ گره گراف با بالاترین مقدار پروجکشن و $\odot$ نشان‌دهنده ضرب نظیربه‌نظیر داریه‌های ماتریس است. به عبارت دیگر، گره‌هایی که بالاترین مقادیر پروجکشن را دارند، در ماتریس مجاورت جدید $\mathbf {A} '$ حفظ می‌شوند. تابع سیگموئید استفاده شده نیز باعث می‌شود بردار پروجکشن $\mathbf {p}$ از طریق پس‌انتشار(backpropagation) قابل یادگیری باشد؛ زیرا در غیر این‌صورت خروجی‌های گسسته تولید می‌شود.

ادغام توجه‌به‌خود

ابتدا قرار می‌دهیم

$\mathbf {y} ={\text{GNN}}(\mathbf {X} ,\mathbf {A} )$

که ${\text{GNN}}$ یک لایه هم‌وردای جایگشتی شبکه عصبی گراف است.

لایه ادغام توجه‌به‌خود را می‌توان به شکل زیر بیان کرد:

$\mathbf {X} '=(\mathbf {X} \odot \mathbf {y} )_{\mathbf {i} }$

$\mathbf {A} '=\mathbf {A} _{\mathbf {i} ,\mathbf {i} }$

که $\mathbf {i} ={\text{top}}_{k}(\mathbf {y} )$ زیرمجموعه $k$ گره گراف با بالاترین مقدار پروجکشن و $\odot$ نشان‌دهنده ضرب نظیربه‌نظیر داریه‌های ماتریس است.

لایه ادغام توجه‌به‌خود را می‌توان به عنوان افزونه‌ای بر لایه ادغام top-k در نظر گرفت. با این تفاوت که مقادیر محاسبه شده در لایه ادغام توجه‌به‌خود،‌ توصیفی از هردوی ویژگی‌های گره‌های گراف و توپولوژی آن است.

کاربردها

تاشدگی پروتئین

شبکه‌های عصبی گراف یکی از اصلی‌ترین بلوک‌های سازنده AlphaFold هستند؛ برنامه هوش مصنوعی طراحی شده توسط تیم دیپ‌مایند شرکت گوگل برای حل مسئله تاشدگی پروتئین در زیست‌شناسی.

شبکه‌های اجتماعی

شبکه‌های اجتماعی به دلیل نمایش طبیعیشان به شکل گراف‌های اجتماعی، یک حوزه کاربردی اصلی برایشبکه‌های عصبی گراف هستند. شبکه‌های عصبی گراف برای توسعه سامانه‌های توصیه‌گر بر اساس روابط اجتماعی و روابط آیتم‌ها استفاده می‌شوند.

بهینه‌سازی ترکیبیاتی

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

همچنین ببینید

• سامانه توصیه‌گر
• AlphaFold
• بهینه‌سازی ترکیبیاتی