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

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

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

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

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

معماری

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

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

   

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

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

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

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

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

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

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

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

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

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

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

ادغام Top-k

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

کاربردها

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

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

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

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

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

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

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

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

منابع

1. Scarselli, Franco; Gori, Marco; Tsoi, Ah Chung; Hagenbuchner, Markus; Monfardini, Gabriele (Winter 2009). "The Graph Neural Network Model". IEEE Transactions on Neural Networks. 20 (1): 61–80. doi:10.1109/TNN.2008.2005605. ISSN 1941-0093.
2. Sanchez-Lengeling, Benjamin; Reif, Emily; Pearce, Adam; Wiltschko, Alexander B. (2021-09-02). "A Gentle Introduction to Graph Neural Networks". Distill (به انگلیسی). 6 (9): e33. doi:10.23915/distill.00033. ISSN 2476-0757.
3. Cai, Chen; Wang, Dingkang; Wang, Yusu (2021-02-02). "Graph Coarsening with Neural Networks". arXiv:2102.01350 [cs].
4. Lee, Junhyun; Lee, Inyeop; Kang, Jaewoo (2019-06-13). "Self-Attention Graph Pooling". arXiv:1904.08082 [cs, stat].
5. Liu, Chuang; Zhan, Yibing; Li, Chang; Du, Bo; Wu, Jia; Hu, Wenbin; Liu, Tongliang; Tao, Dacheng (2022-04-15). "Graph Pooling for Graph Neural Networks: Progress, Challenges, and Opportunities". arXiv:2204.07321 [cs].
6. Navarin, Nicolò; Tran, Dinh Van; Sperduti, Alessandro (Summer 2019). "Universal Readout for Graph Convolutional Neural Networks". 2019 International Joint Conference on Neural Networks (IJCNN): 1–7. doi:10.1109/IJCNN.2019.8852103.
7. "Papers with Code - MPNN Explained". paperswithcode.com (به انگلیسی). Retrieved 2022-12-23.
8. Bronstein, Michael M.; Bruna, Joan; Cohen, Taco; Veličković, Petar (2021-05-02). "Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges". arXiv:2104.13478 [cs, stat].
9. Gao, Hongyang; Ji, Shuiwang (2019-05-11). "Graph U-Nets". arXiv:1905.05178 [cs, stat].
10. "DeepMind's protein-folding AI has solved a 50-year-old grand challenge of biology". MIT Technology Review (به انگلیسی). Retrieved 2023-01-30.
11. "Google's DeepMind predicts 3D shapes of proteins". the Guardian (به انگلیسی). 2018-12-02. Retrieved 2023-01-30.
12. Fan, Wenqi; Ma, Yao; Li, Qing; He, Yuan; Zhao, Eric; Tang, Jiliang; Yin, Dawei (2019-11-22). "Graph Neural Networks for Social Recommendation". arXiv:1902.07243 [cs].
13. «Computer Science». arxiv.org. دریافت‌شده در ۲۰۲۳-۰۱-۳۰.