تعبیه گره‌ها در گراف‌ها
. مقدمه
این ادامه سری وبلاگ‌های من در گراف‌ها است و پنجمین وبلاگ از این مجموعه است. این مقاله بر روی تعبیه گره‌ها تمرکز خواهد کرد. تا کنون، در مقاله‌های قبلی‌ام در سری‌های جاری در گراف‌ها، از یادگیری ماشینی سنتی در گراف‌ها صحبت می‌کردم که در آن ایده این بود که یک گراف ورودی داده شود: ما ویژگی‌های گره، پیوند و سطح گراف را استخراج می‌کنیم که ساختار توپولوژی شبکه اطراف گره، پیوند یا کل گراف را توصیف می‌کند. این اطلاعات توپولوژیکی را می‌توان با اطلاعات سطح ویژگی ترکیب کرد تا یک مدل یادگیری ماشینی مانند رگرسیون لجستیک یا ماشین بردار پشتیبانی را آموزش دهد
بنابراین، سناریویی که تاکنون وجود داشت این بود که با در نظر گرفتن یک گراف ورودی، مهندس یادگیری ماشین ویژگی‌های ساختاری این گراف را ایجاد کرد تا بتوان یک الگوریتم یادگیری را برای پیش‌بینی اعمال کرد. سناریو در شکل زیر نشان داده شده است.
شکل 1: یادگیری ماشین گراف با مهندسی ویژگی (سطح گره، سطح پیوند، ویژگی‌های سطح گراف)
یادگیری بازنمایی گراف:
همانطور که انتظار می‌رود، بیشتر تلاش در سناریوی توصیف شده به مهندسی ویژگی می‌رود که در آن دانشمند داده تلاش می‌کند تا ویژگی‌های ساختاری را از گراف داده شده استخراج کند تا اطلاعات بتواند برای کارهای پیش‌بینی پایین دستی مفید باشد. در ادامه، ایده اکنون این است که فرآیند را بیشتر از استخراج ویژگی‌های سطح گره، پیوند یا گراف ساده کنیم که شامل تلاش دستی برای هر گراف است. ایده این است - با توجه به گره‌های مجزا، هر گره را در یک فضای d بعدی ترسیم می‌کنیم و آن را بردار ابعاد d همانطور که در شکل زیر نشان داده شده است نشان می‌دهیم. این "یادگیری بازنمایی گراف" است.
شکل 2: یادگیری بازنمایی گراف به جای مهندسی ویژگی دستی
با در نظر گرفتن موارد فوق، این مقاله تلاش می‌کند تا پایه و اساس مفهوم تعبیه گره‌ها را در گراف‌ها قرار دهد و بنابراین به صورت زیر سازماندهی شده است:
· بخش 2 عمیق‌تر به مفهوم تعبیه (جاسازی) گره می‌رود و شباهت مفهومی تعبیه گره در گراف‌ها را با جاسازی کلمه در پردازش زبان طبیعی توضیح می‌دهد. در این بخش همچنین در مورد شبکه کلاسیک باشگاه کاراته Zachary و ساخت گره تعبیه شده برای این شبکه به صورت دو بعدی توضیح داده شده است.
· بخش 3 در مورد فرمول‌بندی کیفی تعبیه گره‌ها بدون جزئیات هیچ گونه ریاضی صحبت می‌کند.
· بخش 4 مختصری در مورد روش‌های مورد استفاده برای ایجاد تعبیه گره‌ها: پیاده روی تصادفی و Node2Vec - که بحث مفصل آنها بخشی از قسمت 6 این مجموعه خواهد بود.
2. درک مفهوم تعبیه گره
در یادگیری بازنمایی گراف - همانطور که در بالا بحث شد - بازنمایی ویژگی از طریق تعبیه گره اتفاق می‌افتد که در آن هر تعبیه ساختار شبکه زیربنایی را همانطور که در شکل 3 در زیر نشان داده شده است نشان می‌دهد. این بردار ابعاد-d "تعبیه گره" نامیده می‌شود که اطلاعات شبکه زیربنایی مورد علاقه ما را جمع‌آوری می‌کند. مفهومی که شامل تعبیه گره می‌شود بسیار شبیه مفهوم تعبیه کلمه در پردازش زبان طبیعی است که در آن تعبیه کلمات مشابه است. همانطور که در شکل 4 زیر نشان داده شده است، نزدیک به یکدیگر نگاشت می‌شوند:
شکل 3: بازنمایی ویژگی از طریق تعبیه هر گره که ساختار شبکه زیربنایی را به تصویر می‌کشد.
شکل 4: تعبیه کلمه در پردازش زبان طبیعی (NLP)
چرا تعبیه گره؟
در اینجا نیز در گراف‌ها، شباهت تعبیه‌ها بین گره‌ها نشان‌دهنده شباهت در شبکه است. یعنی: اگر گره‌ها به هم نزدیک باشند و توسط یک لبه به هم متصل شوند، در فضای تعبیه به هم نزدیک خواهند بود. این اجازه می‌دهد تا به طور خودکار اطلاعات ساختار شبکه را رمزگذاری کنیم و سپس می‌توانیم از این اطلاعات برای کارهای پیش‌بینی پایین دستی مانند:
· دسته‌بندی گره‌ها
· پیش‌بینی پیوند
· دسته‌بندی گراف
· تشخیص گره غیرعادی
· خوشه‌بندی
· و غیره
نمونه‌ای از تعبیه گره‌ها:
پیشینه شبکه باشگاه کاراته Zachary’s
[منبع: https://en.wikipedia.org/wiki/Zachary%27s_karate_club]:
باشگاه کاراته Zachary's یک شبکه اجتماعی از یک باشگاه کاراته دانشگاهی است که در مقاله توضیح داده شده است: "اطلاعاتی برای درگیری و شکاف در گروه‌های کوچک" توسط وین دبلیو زاخاری. شبکه Tne 34 عضو یک باشگاه کاراته را ضبط می‌کند و پیوندهای بین جفت اعضایی را که خارج از باشگاه با هم تعامل داشتند را مستند می‌کند. مجموعه داده به صورت عمومی در اینترنت در دسترس است و می‌تواند به عنوان لیستی از جفت‌های عدد صحیح خلاصه شود. هر عدد صحیح نشان دهنده یک شبکه باشگاه کاراته است و یک جفت نشان دهنده تعامل دو عضو است. مجموعه داده در شکل زیر خلاصه شده است:
شکل 5: بازنمایی شبکه‌ای از روابط اجتماعی در میان 34 نفر در باشگاه کاراته که توسط زاخاری مورد مطالعه قرار گرفته است.
شبکه کاراته Zachary به عنوان تعبیه گره – فرمول “Deep Walk” برای تعبیه گره‌ها
در ژوئن 2014 [https://arxiv.org/pdf/1403.6652.pdf]، پروزی و همکاران “Deep Walk” را ارائه کردند - یک رویکرد جدید برای یادگیری بازنمایی نهفته رئوس در یک شبکه. این بازنمایی‌های نهفته روابط اجتماعی را در یک فضای برداری پیوسته (که به عنوان "فضای تعبیه شده" نامیده می‌شود) رمزگذاری می‌کند و این اطلاعات تعبیه گره‌ها را می‌توان توسط مدل‌های یادگیری ماشین/یادگیری عمیق مورد استفاده قرار داد. تصویری از تعبیه‌های گره مربوط به شبکه باشگاه کاراته Zachary که از طریق رویکرد Deep Walk برای فرمول‌بندی تعبیه‌های گره فرمول‌بندی شده است در شکل زیر نشان داده شده است:
شکل 6: گراف ورودی شکل 5 برای شبکه باشگاه کاراته Zachary و تعبیه گره مربوطه.
گره‌های شکل بالا با رنگ‌های مختلف نشان داده شده‌اند. از شکل بالا می‌توان دید که چگونه گره‌های مختلف در فضای تعبیه نگاشت می‌شوند و گره‌های متصل از طریق لبه‌ها نزدیک به یکدیگر در فضای تعبیه قرار می‌گیرند.
برای تصویر بالا، یک شبکه بسیار ساده و یک فضای تعبیه دو بعدی در بالا نشان داده شده است – لازم به ذکر است که در واقعیت، فضای تعبیه ابعاد بسیار بزرگتری خواهد داشت. اجازه دهید اکنون بیشتر در مورد تعبیه گره بدانیم و بفهمیم (به طور اساسی) چگونه فرمول‌بندی تعبیه گره انجام می‌شود. من در مورد فرمول Deep Walk برای تعبیه گره از یک گراف ورودی در وبلاگ بعدی خود در این مجموعه بحث خواهم کرد.
3. فرمول‌بندی کیفی تعبیه گره
تعبیه گره: رمزگذار و رمزگشا
اکنون ببینیم که تعبیه‌های گره چگونه فرموله می‌شوند. ممکن است از اولین مقاله من در بخش 7 یاد شود، که یک گراف را می‌توان به صورت عددی به عنوان یک ماتریس مجاورت نشان داد. ماتریس مجاورت یک گراف چهار گره همانطور که در شکل زیر نشان داده شده است:
شکل 7: بازنمایی عددی یک گراف از طریق ماتریس مجاورت
برای سادگی، اجازه دهید فقط گراف‌های بدون جهت را در نظر بگیریم.
هدف از تعبیه گره‌ها رمزگذاری گره‌ها به گونه‌ای است که شباهت در فضای تعبیه (به عنوان مثال محصول نقطه‌ای) با شباهت در گراف مطابق شکل زیر و در معادله نشان داده شده است:
شکل 8: نگاشت تمام گره‌ها در یک گراف به یک فضای تعبیه شده بر اساس ساختار شبکه.
گره‌های u و v نشان‌دهنده در گراف بالا به عنوان مختصات zu و zv در فضای تعبیه نگاشت می‌شوند. تابع رمزگذاری ENC(u) یا ENC(v) باید به عنوان بخشی از فرمول تعریف شود:
شکل 9: نگاشت از گراف به فضای تعبیه از طریق تابع Encoding که باید تعریف شود، انجام می‌شود.
خلاصه فرآیند:
بنابراین، بر اساس بحث‌های بالا، فرمول‌بندی تعبیه گره‌ها را می‌توان به صورت زیر خلاصه کرد:
۱. رمزگذار را تعریف کنید، یعنی: نقشه برداری از گره‌ها به تعبیه. کد ENC (نشان داده شده در شکل‌های 8 و 9، u و v) را به بردارهایی که با مختصات zu و zv نشان داده شده اند، نگاشت می‌کند.
۲. یک تابع شباهت گره را تعریف کنید، یعنی معیاری از شباهت در شبکه اصلی که مشخص می‌کند چگونه رابطه در فضای برداری با رابطه در شبکه اصلی نگاشت می‌شود.
۳. پارامترهای انکودر را بهینه کنید تا شباهت u و v در شبکه حاصلضرب نقطه بین موجودیت‌های گره را تقریبی کند (معادله - شکل 8 و شکل 9)
تعبیه در فضای “d” بعدی از 64 تا 1000 (به طور معمول) خواهد بود. ابعاد نیز به اندازه شبکه و سایر پیچیدگی‌ها بستگی دارد.
لازم به ذکر است که رمزگذار به صورت ENC(v) نشان داده می‌شود: Z x v که در آن ماتریس Z دارای اندازه است: ابعاد تعبیه شده x تعداد گره‌ها.
v یک بردار نشانگر است که همه 0 ها را خواهد داشت به جز 1 در ستونی که گره v را نشان می‌دهد.
شکل 10: بازنمایی کیفی ماتریس تعبیه شده Z
چگونه مفهوم شباهت گره و تعبیه گره‌های آموزش را تعریف کنیم؟
ما در مورد شباهت گره صحبت کرده‌ایم - در بحثرهای بالا در مورد آن صحبت کردیم اما توضیح ندادیم. راه‌های مختلفی برای این کار وجود دارد. می‌توانستیم بگوییم:
۱. گره متصل شده توسط یک لبه باید دارای تعبیه‌های مشابه باشد
۲. گره‌هایی که همسایه‌های مشترک دارند
بخش‌های مشابهی از شبکه هستند.
شباهت گره‌ها را می‌توان بر اساس پیاده روی تصادفی تعریف کرد
مروری بر پیاده روی تصادفی:
· این روش بدون نظارت است، یعنی: وقتی در حال یادگیری تعبیه گره‌ها هستیم، از هیچ برچسب گره‌ای استفاده نمی‌کنیم. ما تعبیه‌ها را یاد می‌گیریم تا شباهت شبکه را بگیرند، اما برچسب‌های گره‌ها را نگیرند.
· ما همچنین از هیچ ویژگی گره استفاده نمی‌کنیم. هدف این است که مختصات تعبیه گره را تخمین بزنیم تا برخی از جنبه‌های ساختار شبکه حفظ شود. تعبیه‌ها مستقل از کار هستند که آموزش دیده‌اند و فقط برای یادگیری شبکه آموزش داده شده‌اند و در کار پیش‌بینی آموزش داده نمی‌شوند.
بحث مفصل در مورد استراتژی پیاده روی تصادفی بخشی از وبلاگ بعدی این مجموعه خواهد بود.
