seyed hossein Tafakh
seyed hossein Tafakh
خواندن ۱۱ دقیقه·۴ سال پیش

graphSage

سلام .
در این آموزش ما قصد داریم درباره یک موضوع و روش نگرش صحبت بکنیم . موضوعی که برای زمان بسیار زیادی مغز بعضی از ریاضی دانان و quantative reaserch های زیادی را در زمینه گراف به خود مشغول کرده .
embedding
شاید در نگاه اول بیاید که خب عملیات امبدینگ یا نشانه گذاری دیتا ها در مکان های مختلف در حالتی که بتوانند اطلاعات خود را نشان بدهند یا به ارث ببرند زیاد دارای اجر و غربتی در میان دوست داران هوش مصنوعی نیست چرا که در دنیای که زندگی میکنند دیتا هایی که اماده میکنند هم اکنون بسیاری از مشکلات را حل میکنند و این پیشنیاز ها در غالب اطلاعات در دست قرار میگیرند که این به خودی خودی ایده بدیعی نیست که بخواهیم اطلاعات را عوض بکنیم و آنها را به عدد تبدیل بکنیم برای آنالیز اطلاعات .
اما نکته برای گراف ها اینجا متوقف نمیشود . چرا که گراف ها دارای ابعاد نیستند و بعد برای هر داده در گراف اندازه ای صفر دارد که این مسئله را دو چندان سخت میکند و تنها اطلاعات موجود در گراف راه ارتباط با همسایگان است. گراف همین هست یک هزار تو که از هر راس به راس دیگر راه های زیادی هست و همه اینها در دنیایی هست که بعد معنا ندارد .
در سال های اخیر به دلیل افزایش محبوبیت در بین شرکت های آیتی به دلیل خوبی هایی که ارائه میدهند . و به دلیل استفاده از این مبحث و زیاد شدن کار برای این زیمنه بعضی دانشمندان راه راهی بسیار جالبی ارائه داده اند که نگاه به این مسائل باید بسیار جالب باشد .
1- classification

https://snap-stanford.github.io/cs224w-notes/machine-learning-with-networks/message-passing-and-node-classificationure:
https://snap-stanford.github.io/cs224w-notes/machine-learning-with-networks/message-passing-and-node-classificationure:


در این چلنج مطرح شده که رنگ نود های خاکستری را حدث بزنید.
2- prediction

هدف از این چلنج شناخت احتمال برقراری ارتباط بین نود های دیگر است .
برای این دو سوال و چلنج راه های کمی تا بحال ارائه شده و دلیلش هم معلومه ، تازه بودن فیلد graph data science .
دو روش شبیه به هم که توسط دانشمندان هوش مصنوعی متن و زبان شناس ارائه شد و در این روش سعی شده که به گراف ها حالت توالی یا sequence بدن و بفرستن در مدل های که در معروفی مثل skip-gram .
در این نوشته بیشتر توضیح دادم مدل های DeepWalk , Node2Vec


گراف نورال نتورک یا GNN

گراف نورال نتورک ها نوعی از شبکه های عصبی هستند که مستقیم بر روی ساختار گراف کار میکنند و نیازی به روش های مختلف استخراج دیتا از گراف ندارند و به عنوان یک روشی که هم خوبی های شبکه عصبی و هم عدم نیاز به تغییر استراکچر دیتای اولیه را ارائه میداد توجه بسیاری را به خود جلب کرد .
در این روش کار میتواند ساده شروع بشود و با توجه به نیاز ها و سوال هایی که بانک اطلاعاتی یا هرف پروژه ارائه میکند این روش میتواند متغیر باشد ، و بیشتر شبیه یک مدل بسیار ماجولار میماند تا یک فریمورک عبوث که فقط یک نوع روش را میشناسد و این ماجول ها دارای دامنه بزرگی از فانکشن های ریاضی هستند از عملیات نقشه برداری لاپلاسین-Nonlinear dimensionality reduction - گرفته تا جمع ساده .
یکی از استفاده های این گراف ها node classification هست و در واقع در این جا سوال اینگونه مطرح میشود که :

هر نود دارای لیبل یا نوعی دیتا هست و ما میخواهیم لیبل نود مورد نظر را حدث بزنیم بدون داشتن ground truth یا داده مرجع .


اگر بخواهیم گراف نورال نتورک را مسقیم از پیپر توضیح بدهیم باید بگوییم که :
در گراف نود با حالت طبیعی و ارتباطی که با نود های اطراف دارد خود را توضیح میدهد. و هدف GNN شناخت حالت embed شده h_v که دارنده اطلاعات از نود های اطراف و همسایه برای هر نود . در استیت یا حالت امبدین h_v دارای ماتریس s بعدی برای ارائه نود v است که از این میتوان برای استخراج o_v استفاده کرد . که لیبل نود را میتوان توسط فانکشن F که نوعی فاکشن پارامتریک است که با اسم local transition function شناخته میشود و اطلاعات این فانکشن بین تمام نود ها مشترک است - shared - و حالت نود را با توجه به نود های همسایه اپدیت میکند. g فانکشنی است که به اسم local output function شناخته میشود ، که توصیف میکند چگونه خروجی تولد شده است .
h_v و o_v به روش های زیر ارائه میشوند.

https://www-cs-faculty.stanford.edu/people/jure/pubs/graphsage-nips17.pdf
https://www-cs-faculty.stanford.edu/people/jure/pubs/graphsage-nips17.pdf
https://www-cs-faculty.stanford.edu/people/jure/pubs/graphsage-nips17.pdf
https://www-cs-faculty.stanford.edu/people/jure/pubs/graphsage-nips17.pdf



که x_v , x_co[v] , h_nw[v] , x_ne[v], خواصی از نود v هستند
x_v : داده ی پایه .
x_co[v] : اطلاعات لبه های اطراف (edge )
h_ne[v]: اطلاعات امبد شده نود های همسایه.
x_ne[v] : اطلاعات همسایه های نود .

توجه که H,O,X و X_N حاصل جمع شدن و انباشته کردن تعداد حالت ها - state - ، تمام خروجی ها ، تمام خواص ها و تمام خواص نود با احترام- respect to - به همسایه های نود .

https://www-cs-faculty.stanford.edu/people/jure/pubs/graphsage-nips17.pdf
https://www-cs-faculty.stanford.edu/people/jure/pubs/graphsage-nips17.pdf
https://www-cs-faculty.stanford.edu/people/jure/pubs/graphsage-nips17.pdf
https://www-cs-faculty.stanford.edu/people/jure/pubs/graphsage-nips17.pdf

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

https://www-cs-faculty.stanford.edu/people/jure/pubs/graphsage-nips17.pdf
https://www-cs-faculty.stanford.edu/people/jure/pubs/graphsage-nips17.pdf

که بر اساس روش گرادیانت دسنت است که p تعداد نود های سوپروایزر است . و در حاصل اختلاف بین حالت فعلی با حالت حقیق محض داده مرجع .
البته این روش محدودیت هایی دارد که تحقیقاتی هم برای بهتر شدن این روش محاسبه خطا ارائه شده اند که خواص بهتری دارند .
خب...

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

2- نوعی محاسبه برای پیدا کردن یک ماتریکس وزن weight matrix یا همان ترین کردن یک شبکه عصبی پرسپتران معمولی و محاسبه loss با توجه به ارائه ای که از دیتا بیس داریم و اختلاف ان با پیشبینی شبکه و آموزش بر اساس این روش .

و اگر بخواهیم بصورتی از بالا نگاه کنیم این یک بلاک از شبکه های عصبی گرافی است که با تغییر دادن بلاک ها به روش های مختلف یا تغیر دادن فانکشن های مختلف در پروسه دانشمندان و محققان باعث بهبود یافت این علم میشوند . مثلا از فانکشنهایی مثل lstm , relu و ... استفاده میکنن و اگر شما راهی میشناسید برای بهبود این نوع شبکه ها بهتر است سریعتر دست به قلم بشوید و paper خود را بنویسید .

GraphSage

https://dsgiitr.com/blogs/graphsage/
https://dsgiitr.com/blogs/graphsage/


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

https://www-cs-faculty.stanford.edu/people/jure/pubs/graphsage-nips17.pdf
https://www-cs-faculty.stanford.edu/people/jure/pubs/graphsage-nips17.pdf

تعداد لوپ نشاندهنده تعداد ایتریتور های اپدیت است . یا به فارسی تعداد دفعاتی که مدل را اموزش میدهیم. درحالی که h^k_v نشان دهنده اخرین وکتور ارائه دهنده حالت نود v در شماره ترین یا اپدیت k .
h^k_v در هر بار تکرار توسط فانکشنی اپدیت میشود که به آن aggregation function میگوییم. که بر اساس ورودی هایی از اطلاعات خود و نود های همسایه در دوره k-1 سعی در ارائه بهتری از ماتریس وزن یا weight matrix دارد و ماتریس را با W^k نشان میدهیم .
سه تا از aggregation function هایی که توسط خود پیپر ارائه شده .

یک - Mean aggregator

در این فانکشن اطلاعات را بر اساس متوسط مقادیر ارائه شده توسط نود های همسایه محاسبه میکند

https://www-cs-faculty.stanford.edu/people/jure/pubs/graphsage-nips17.pdf
https://www-cs-faculty.stanford.edu/people/jure/pubs/graphsage-nips17.pdf

دو - LSTM aggregator

شاید در نگاه اول عجیب باشد چرا که ما برای انجام محاسبات بر روی نود های همسایه باید روشی را ارائه بدهیم که چینش در ان مهم نباشید ولی لایه های lstm باید نظم ورودی داشته باشند . ولی بعد از چند تحقیق مشخص شد که lstm توانایی حدث زدن دیتا های بینظم را هم دارد و تاثیری در نتیجه که نشان دهنده بد بودن مدل باشد نبود .

سه - Pooling aggregator

این روش دارای دو نوع روش pooling است اولی max pooling و دومی mean pooling ولی در پیپر از روش max pooling استفاده شده .

https://www-cs-faculty.stanford.edu/people/jure/pubs/graphsage-nips17.pdf
https://www-cs-faculty.stanford.edu/people/jure/pubs/graphsage-nips17.pdf

موضوع مکس پولینگ کمی پیچیده به نظر میرسد ولی سعی میکنم پستی درمورد این فانکشن بنویسم.

نتیجه گیری :

در روش های ارائه شده روش GraphSage با قدرت بسیار بیشتری در چلنج ها ظاهر شد.

https://www-cs-faculty.stanford.edu/people/jure/pubs/graphsage-nips17.pdf
https://www-cs-faculty.stanford.edu/people/jure/pubs/graphsage-nips17.pdf

چرا که نسخه با روشی ساده ولی زیرک توانست اطلاعات بیشتری جمع بکند و یک متغیر به نام k معرفی کرد که در واقع نشان دهنده مقدار عمقی است که ما میرویم و k باید عدد تک رقمی باشد چرا که اگر عدد 7 را انتخاب کنیم ما در هر دوره اموزش یا ترین کل اطلاعات گراف را به شبکه عصبی انتقال میدهیم و این باعث تبدیل شدن همه لایه امبدین به یک است و امبدینگ از بین میرود . پس در انتخاب k دقت کنید .

https://www-cs-faculty.stanford.edu/people/jure/pubs/graphsage-nips17.pdf
https://www-cs-faculty.stanford.edu/people/jure/pubs/graphsage-nips17.pdf


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

یا موفقیت های که در شبکه های اجتماعی داشته . برای مثال شبکه پینترست ریکامندر فوق العاده خود را مدیون این نوع شبکه عصبی است . همینطور لینکدن و جدیدن شرکت DeepMind از این محاسبات برای تحقیق بر روی ساختار مولکولی شیشه استفاده میکنن . لینک

امیدوارم که این نوشته مورد استفاده شدما قرار بگیره . اگر سوالی داشتید من رو در تویتر فالو بکنید تا بتونیم بیشتر با هم صحبت کنیم .

پایان.

graph sagedeepmindgnngcndata science
شاید از این پست‌ها خوشتان بیاید