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

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

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

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

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

[1] Vector Embedding

[1] Random Walk

[2] feature

[3] DeepWalk

[4] Multilabel classification

[1] Graph embedding

[2] embeddings