Skip to content
بازگشت به نتایج جست‌وجو

شبکه عصبی گراف — GCN / GAT / GraphSAGE

سال
2017–2018 (major variants)
نوع
Deep learning on graph-structured data

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

یک شبکه عصبی گراف (GNN) یک معماری یادگیری عمیق است که مستقیماً بر روی داده‌های ساختاریافته گراف با ترکیب ویژگی‌های گره با اطلاعات ساختاری از طریق انتشار پیام همسایگی تکراری عمل می‌کند. سه نوع اصلی — شبکه عصبی کانولوشنال گراف (GCN) معرفی شده توسط کیپف و ولینگ در سال ۲۰۱۷، شبکه عصبی توجه گراف (GAT) معرفی شده توسط ولیچکوویچ و همکاران در سال ۲۰۱۸، و GraphSAGE — در نحوه تجمیع اطلاعات همسایگان متفاوت هستند: GCN یک کانولوشن طیفی را بر روی کل مجاورت اعمال می‌کند، GAT همسایگان را با امتیازات توجه آموخته شده وزن‌دهی می‌کند، و GraphSAGE محله‌های محلی را به صورت استقرایی نمونه‌برداری و تجمیع می‌کند و امکان تعمیم به گره‌های دیده‌نشده را فراهم می‌سازد.

شهود پشت روش

هر گره در یک گراف را مانند فردی در یک شبکه اجتماعی در نظر بگیرید. آن فرد پروفایل (ویژگی‌های) خود را دارد، اما اینکه چه کسانی را می‌شناسد نیز اطلاعات زیادی درباره او می‌گوید. یک GNN به هر گره اجازه می‌دهد تا پیام‌هایی را از همسایگان خود به طور مکرر جمع‌آوری کند، آن پیام‌ها را با اطلاعات خود ترکیب کند و نمایش خود را — لایه به لایه — به‌روزرسانی کند. پس از چند دور از این تبادل به سبک شایعه‌پراکنی، نمایش هر گره نه تنها خود گره، بلکه زیرگراف محلی اطراف آن را منعکس می‌کند. GCN این کار را با میانگین‌گیری متقارن ثابت همسایگان انجام می‌دهد؛ GAT با یادگیری وزن‌های توجه تصمیم می‌گیرد به کدام همسایگان بیشتر اعتماد کند؛ GraphSAGE زیرمجموعه ثابتی از همسایگان را نمونه‌برداری کرده و یک تابع تجمیع را یاد می‌گیرد که می‌تواند برای گره‌هایی که قبلاً هرگز ندیده است، اعمال شود.

تاریخ

پایه‌های اعمال شبکه‌های عصبی بر روی گراف‌ها توسط Scarselli و همکاران (۲۰۰۹) گذاشته شد، اما دوران مدرن GNN با شبکه عصبی کانولوشنال گراف (۲۰۱۷) کیپف و ولینگ آغاز شد، که کانولوشن طیفی گراف را به یک تقریب مرتبه اول کارآمد با استفاده از ضرب ماتریس مجاورت نرمال‌شده متقارن ساده کرد. یک سال بعد، Veličković و همکاران (۲۰۱۸) شبکه‌های عصبی توجه گراف را معرفی کردند و میانگین‌گیری ثابت GCN را با ضرایب توجه قابل یادگیری بر روی هر یال جایگزین کردند — به مدل اجازه می‌داد همسایگان را به طور انتخابی وزن‌دهی کند. همزمان، Hamilton و همکاران (۲۰۱۷) GraphSAGE را پیشنهاد کردند، یک چارچوب استقرایی که همسایگی‌های با اندازه ثابت را نمونه‌برداری کرده و توابع تجمیع قابل انتقال به گره‌های دیده‌نشده را یاد می‌گیرد، که GNNها را برای گراف‌های بزرگ و پویا عملی می‌سازد. این سه مقاله، پارادایم پیام‌رسانی را که اکنون زیربنای اکثر تحقیقات GNN است، ایجاد کردند.

چه زمانی استفاده شود

زمانی از GNN استفاده کنید که داده‌های شما به طور طبیعی ساختار گراف دارند — شبکه‌های اجتماعی، شبکه‌های استنادی، گراف‌های مولکولی، گراف‌های دانش، یا هر محیطی که در آن روابط بین موجودیت‌ها سیگنال پیش‌بینی‌کننده حمل می‌کنند. شما به یک ماتریس ویژگی گره و یک لیست یال نیاز دارید. حداقل حدود ۵۰ گره برای آموزش معنی‌دار لازم است. GNNها برای طبقه‌بندی گره (پیش‌بینی یک برچسب برای هر گره)، پیش‌بینی پیوند (استنتاج یال‌های گمشده) و طبقه‌بندی گراف (اختصاص یک برچسب به کل گراف) کاربرد دارند. فرض هموفیلی — گره‌های متصل تمایل به اشتراک‌گذاری برچسب یکسان دارند — به طور ضمنی توسط GCN و GAT استاندارد مورد بهره‌برداری قرار می‌گیرد؛ اگر گراف شما هتروفیلیک است، معماری‌های طراحی شده برای آن محیط را در نظر بگیرید. برای گراف‌های بزرگ، آموزش دسته‌ای کامل از نظر حافظه غیرممکن است و نمونه‌برداری همسایگی دسته‌ای کوچک (سبک GraphSAGE) مورد نیاز است. اگر گراف شما کمتر از ۲۰ گره دارد، معیارهای مرکزیت سنتی انتخاب مناسب‌تری هستند.

محدودیت‌ها و ملاحظات

  • هموارسازی بیش از حد: انباشت لایه‌های زیاد GNN تمام نمایش‌های گره را به سمت یک مقدار مشترک سوق می‌دهد و عمق مؤثر را در عمل به ۲ تا ۴ لایه محدود می‌کند.
  • مقیاس‌پذیری: GCN و GAT دسته‌ای کامل نیاز به نگهداری کل ماتریس مجاورت و ماتریس ویژگی در حافظه دارند، که برای گراف‌های بسیار بزرگ بدون نمونه‌برداری یا پارتیشن‌بندی غیرممکن است.
  • فرض هموفیلی که در تجمیع استاندارد گنجانده شده است، عملکرد را بر روی گراف‌های هتروفیلیک که در آن همسایگان تمایل به داشتن برچسب‌های متفاوت دارند، کاهش می‌دهد.
  • حداقل اندازه نمونه حدود ۵۰ گره لازم است؛ گره‌های کمتر، سیگنال کافی برای یادگیری نمایش‌های معنی‌دار به مدل نمی‌دهند.

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

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

کاربردها

  • طبقه‌بندی گره در شبکه‌های استنادی — پیش‌بینی موضوع یک مقاله بر اساس محتوا و پیوندهای استنادی آن.
  • کشف دارو — پیش‌بینی خواص مولکولی با در نظر گرفتن اتم‌ها به عنوان گره و پیوندهای شیمیایی به عنوان یال.
  • سیستم‌های توصیه‌گر — مدل‌سازی کاربران و اقلام به عنوان یک گراف دو بخشی و پیش‌بینی تعاملات کاربر-اقلام از طریق پیش‌بینی پیوند.
  • تشخیص تقلب در شبکه‌های تراکنش مالی — شناسایی گره‌های ناهنجار بر اساس ویژگی‌ها و ساختار همسایگی آن‌ها.
  • تکمیل گراف دانش — استنتاج روابط گمشده بین موجودیت‌ها در پایگاه‌های دانش در مقیاس بزرگ.

چگونه کار می‌کند

چگونه کار می‌کند

1

گراف با یک ماتریس ویژگی گره X (یک سطر برای هر گره، یک ستون برای هر ویژگی) و یک لیست یال (یا ماتریس مجاورت) A تعریف می‌شود. یال‌های بدون جهت برای GCN و GAT استاندارد هستند؛ GraphSAGE از گراف‌های جهت‌دار نیز پشتیبانی می‌کند. حلقه‌های خودی معمولاً به A اضافه می‌شوند تا هر گره در تجمیع خود گنجانده شود.

2

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

3

هر لایه GNN با تجمیع ویژگی‌های همسایگان یک گره و ترکیب آن‌ها با ویژگی‌های خود گره از طریق یک ماتریس وزن قابل یادگیری و یک تابع فعال‌سازی غیرخطی، نمایش جدیدی از گره را محاسبه می‌کند. GCN ضرب ماتریس مجاورت نرمال‌شده (کانولوشن طیفی) را اعمال می‌کند؛ GAT ضرایب توجه سافت‌مکس را برای هر یال محاسبه می‌کند تا همسایگان تأثیرگذارتر مشارکت کنند؛ GraphSAGE یک همسایگی با اندازه ثابت را به صورت تصادفی نمونه‌برداری کرده و یک تجمیع‌کننده قابل افتراق (میانگین، LSTM، یا پولینگ) را اعمال می‌کند. انباشت L لایه اجازه می‌دهد اطلاعات تا فاصله L هاپ جریان یابد، اما انباشت لایه‌های زیاد باعث هموارسازی بیش از حد می‌شود، که در آن تمام نمایش‌های گره به یک مقدار همگرا می‌شوند.

4

نمایش‌های نهایی گره به یک سر مخصوص وظیفه تغذیه می‌شوند. برای طبقه‌بندی گره، یک لایه سافت‌مکس احتمالات کلاس را به هر گره اختصاص می‌دهد. برای پیش‌بینی پیوند، یک ضرب داخلی یا MLP احتمال وجود یک یال بین دو نمایش گره را امتیازدهی می‌کند. برای طبقه‌بندی گراف، یک پولینگ سراسری (جمع، میانگین، یا سلسله مراتبی) تمام نمایش‌های گره را قبل از لایه طبقه‌بندی به یک بردار سطح گراف واحد تجمیع می‌کند.

5

عملکرد مدل بر روی یک مجموعه آزمون نگه‌داشته شده با استفاده از معیارهای مناسب برای وظیفه اندازه‌گیری می‌شود: دقت یا F1 برای طبقه‌بندی گره و گراف، AUC-ROC برای پیش‌بینی پیوند. از آنجایی که مجموعه داده‌های گراف اغلب اندازه محدودی دارند، ارزیابی تراداکتیو (ماسک‌های آموزش/اعتبارسنجی/آزمون بر روی همان گراف) یا تقسیم‌بندی‌های استقرایی (زیرگراف‌های مجزا) باید با سناریوی استقرار مطابقت داشته باشند.

دام‌های رایج

  • افزودن لایه‌های GNN بیش از حد باعث هموارسازی بیش از حد می‌شود: تمام نمایش‌های گره همگرا شده و مدل قدرت تمایز خود را از دست می‌دهد. تعداد لایه‌ها را ۲ تا ۴ نگه دارید و واریانس نمایش را نظارت کنید.
  • آموزش بر روی کل گراف بدون دسته‌بندی کوچک از نظر حافظه برای شبکه‌های بزرگ غیرممکن است؛ برای گراف‌های با بیش از چند هزار گره از نمونه‌برداری همسایه به سبک GraphSAGE یا پارتیشن‌بندی گراف استفاده کنید.
  • اعمال GCN آموزش‌دیده به صورت تراداکتیو به گره‌های جدید و دیده‌نشده در زمان استنتاج نادرست است؛ اگر استقرار شما نیاز به تعمیم به گره‌های جدید دارد، از یک روش استقرایی مانند GraphSAGE استفاده کنید.
  • نادیده گرفتن فرض هموفیلی بر روی گراف‌های هتروفیلیک نتایج ضعیفی تولید می‌کند؛ قبل از انتخاب یک نوع استاندارد GNN، ضریب همبستگی گراف را بررسی کنید.
  • با کمتر از ۲۰ گره، آموزش GNN نمایش‌های غیرقابل اعتماد تولید می‌کند؛ در آن رژیم، تحلیل مرکزیت متعارف را ترجیح دهید.

پرسش‌های متداول

کدام نوع GNN را باید شروع کنم — GCN، GAT، یا GraphSAGE؟

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

هموارسازی بیش از حد چیست و چگونه از آن اجتناب کنم؟

هموارسازی بیش از حد زمانی رخ می‌دهد که لایه‌های زیاد GNN باعث همگرایی تمام نمایش‌های گره به یک مقدار واحد شده و اطلاعات تمایزدهنده را از بین می‌برد. در عمل، ۲ تا ۴ لایه معمولاً بهینه است. تکنیک‌هایی مانند اتصالات باقی‌مانده، شبکه‌های دانش پرشی، و DropEdge می‌توانند در صورت نیاز به معماری‌های عمیق‌تر کمک کنند.

آیا GNNها به داده‌های برچسب‌دار برای همه گره‌ها نیاز دارند؟

خیر. GCN و GAT معمولاً در تنظیمات نیمه‌نظارتی استفاده می‌شوند که در آن تنها کسری کوچک از گره‌ها دارای برچسب هستند؛ ساختار گراف اطلاعات را از گره‌های برچسب‌دار به گره‌های بدون برچسب منتشر می‌کند. GraphSAGE بسته به وظیفه می‌تواند به صورت کاملاً نظارتی یا بدون نظارت نیز آموزش داده شود.

گراف چقدر باید بزرگ باشد؟

حداقل حدود ۵۰ گره برای آموزش معنی‌دار GNN لازم است. با کمتر از ۲۰ گره، مدل نمی‌تواند نمایش‌های قابل اعتماد را یاد بگیرد و تحلیل مبتنی بر مرکزیت متعارف مناسب‌تر است. برای گراف‌های با میلیون‌ها گره، نمونه‌برداری همسایگی دسته‌ای کوچک (مانند GraphSAGE) یا روش‌های پارتیشن‌بندی گراف برای قابل مدیریت نگه داشتن مصرف حافظه مورد نیاز است.

روش‌های مرتبط

منابع

  1. Kipf, T.N. & Welling, M. (2017). Semi-Supervised Classification with Graph Convolutional Networks. International Conference on Learning Representations (ICLR).

    باز کردن مرجع DOI
    کپی شد.
  2. Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., & Bengio, Y. (2018). Graph Attention Networks. International Conference on Learning Representations (ICLR).

    باز کردن مرجع DOI
    کپی شد.
  3. Hamilton, W.L. (2020). Graph Representation Learning. Morgan & Claypool.

    باز کردن مرجع DOI
    کپی شد.