بازنمایی شبکه توسط یادگیری عمیق

مقدمه

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

ویژگی های گراف

گراف ها  ویژگی های هر گره را از طریق همسایگانش بازگو می کنند. به منظور تولید گراف از خوراک در گراف ورودی، خوراک را یک دَگ مد نظر می گیریم. دَگ ها گروهی از گراف های جهت دار غیرمدوَّر با حداکثر درجه خروجی 1 یک گراف جهت‌دار است که هیچ گرافِ دوری‌ای ندارد؛ یعنی هیچ مسیر جهت‌داری که رأس ابتدا و انتهای آن یکی باشد، وجود ندارد.

به منظور پیاده سازی در یک شبکه پیچیده بزرگ، یک استراتژی نمونه برداری قابل تنظیم توسط هایپرپارامتر به منظور نمونه برداری از زیرگراف های جهت دار غیرمُدَوَّر توسط الگوریتم DeepWalk درنظر گرفته می شود.

الگوریتم DeepWalk

هدف این است که چطوری گره‌های یک شبکه را به بردارهایی تبدیل کنیم که گره‌هایی که به هم شبیه هستند بردارهای شبیه به هم داشته باشند. الگوریتم DeepWalk (Prozzi, B, et al. 2012) اولین پژوهش در این زمینه بوده است که هر گره در گراف را به بردارهایی به طول ثابت تبدیل می‌کند. به طور دقیق‌تر، پژوهش DeepWalk یک قدم زدن تصادفی روی شبکه اعمال می کند و یک سری توالی از گرههای گراف تولید میکند. سپس این توالی‌ها را به الگوریتم Word2Vec میدهد و به ازای هر گره یک بردار به دست می‌آورد. بعد از این بردارها، به عنوان بردارهای ویژگی استفاده میکند و دسته‌بندی‌کننده‌ای را آموزش میدهد و سپس به ارزیابی میپردازد. ارزیابی مقاله DeepWalk از روی دسته بندی چندبرچسبی انجام شده است و حدس میزند که گره x در شبکه جز کدام کلاس قرار می‌گیرد. در مثال پژوهش DeepWalk،‌ از گراف BlogCatalog استفاده شده است. در BlogCatalog به ازای هر گره در گراف یک سری کلاس مشخص شده است. مثلا گره x در کلاسهای 1  و 2 قرار میگیرد.

در نمایش گراف، شکل بالا، ابتدا گره‌های گراف توسط الگوریتم DeepWalk به بردارهای به طول ۱۲۸ نگاشت شدند و سپس توسط الگوریتم TSNE در فضای دو بعدی نمایش داده شده‌اند. در پژوهشی های قبلی که گراف رو به بردارهای نهفته تبدیل میکردند، مانند DeepWalk یا Node2Vec اغلب به مساله نهفته سازی گراف به صورت اقلیدسی نگاه داشته اند، بدین صورت که معیاری که برای شباهت بین دو گره تعریف میشد به صورت خطی بود و به طور دقیق‌تر برای ذکر شباهت دو گره از مسائل موجود در هندسه اقلیدسی استفاده می کردند.