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

تعبیه شبکه — Node2Vec، DeepWalk، LINE

سال
2014 (DeepWalk); 2016 (Node2Vec)
نوع
Representation learning / unsupervised network method

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

اندازه قلم

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

تعبیه شبکه (Network embedding) خانواده‌ای از روش‌های یادگیری بازنمایی است که هر گره از یک گراف را به یک بردار فشرده و کم‌بُعد نگاشت می‌کند، در حالی که خواص ساختاری شبکه را حفظ می‌کند. این رویکرد توسط Perozzi، Al-Rfou و Skiena با DeepWalk (2014) برای داده‌های شبکه اجتماعی رسمی شد، که مدل skip-gram Word2Vec را به پیمایش‌های تصادفی روی گراف‌ها تطبیق داد، و توسط Grover و Leskovec با Node2Vec (2016) گسترش یافت، که پیمایش تصادفی بایاس‌شده‌ای را معرفی کرد که اکتشاف گستره-اول و عمق-اول را متعادل می‌سازد. این تعبیه‌ها داده‌های رابطه‌ای را به بردارهای ویژگی تبدیل می‌کنند که طبقه‌بندها و الگوریتم‌های خوشه‌بندی استاندارد یادگیری ماشین می‌توانند مستقیماً از آن‌ها استفاده کنند.

شهود پشت روش

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

تاریخ

ایده اعمال Word2Vec به داده‌های ساختاریافته گراف توسط Perozzi، Al-Rfou و Skiena در DeepWalk (KDD 2014) معرفی شد، که نشان داد پیمایش‌های تصادفی روی یک گراف اجتماعی می‌توانند جایگزین ویژگی‌های دست‌ساز برای طبقه‌بندی گره شوند. Grover و Leskovec این را در Node2Vec (KDD 2016) با معرفی یک پیمایش تصادفی بایاس‌شده مرتبه دوم که توسط p و q پارامترسازی شده است، گسترش دادند و کنترل صریحی بر مبادله بین اکتشاف همسایگی مبتنی بر هموفیلی و مبتنی بر هم‌ارزی ساختاری فراهم کردند. در حدود همان دوره، Tang و همکاران LINE (WWW 2015) را پیشنهاد کردند، که تعبیه‌ها را با بهینه‌سازی مستقیم اهداف مجاورت مرتبه اول و دوم به جای پیمایش‌های تصادفی یاد می‌گیرد، که آن را برای گراف‌های بسیار بزرگ مناسب می‌سازد. این سه روش با هم زمینه یادگیری بازنمایی شبکه را ایجاد کردند و معماری‌های شبکه عصبی گراف بعدی را الهام بخشیدند.

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

تعبیه شبکه زمانی مناسب است که شما گرافی با حداقل 50 گره داشته باشید و به ویژگی‌های برداری پیوسته برای وظایف پایین‌دستی مانند طبقه‌بندی گره، پیش‌بینی پیوند، یا خوشه‌بندی گره نیاز دارید. این روش هم برای گراف‌های وزن‌دار و هم بدون وزن مناسب است و ساختارهای جهت‌دار یا بدون جهت را مدیریت می‌کند. زمانی DeepWalk را انتخاب کنید که یک خط پایه پیمایش تصادفی ساده و یکنواخت کافی باشد. زمانی Node2Vec را انتخاب کنید که بخواهید تعادل بین هموفیلی و هم‌ارزی ساختاری را از طریق پارامترهای p و q تنظیم کنید. اگر نیاز دارید گره‌های جدید و قبلاً دیده‌نشده را در زمان استنتاج بدون بازآموزی تعبیه کنید، روش القایی مانند GraphSAGE را ترجیح دهید؛ تعبیه شبکه در شکل استاندارد خود تراکنشی است. این روش به ویژگی‌های گره با توزیع نرمال نیازی ندارد.

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

  • تراکنشی: مدل نمی‌تواند گره‌هایی را که در طول آموزش حضور نداشتند بدون بازآموزی کامل تعبیه کند.
  • حساسیت به ابرپارامترها: بُعد تعبیه، طول پیمایش، تعداد پیمایش‌ها، اندازه پنجره، p و q همگی بر کیفیت تعبیه تأثیر می‌گذارند و نیاز به تنظیم دارند.
  • پیمایش‌های تصادفی ساختار گراف مرتبه بالاتر (مانند ابر یال‌ها یا یال‌های چند رابطه‌ای) را بدون توسعه، ثبت نمی‌کنند.
  • عملکرد در گراف‌های بسیار کوچک (کمتر از 50 گره) که در آن مجموعه پیمایش برای یادگیری آمارهای قابل اعتماد بسیار پراکنده است، کاهش می‌یابد.

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

نقاط قوت

  • داده‌های گراف رابطه‌ای را به بردارهای با طول ثابت سازگار با هر خط لوله یادگیری ماشین استاندارد تبدیل می‌کند.
  • پارامترهای p و q در Node2Vec به تحلیلگر اجازه می‌دهند تا تعادل بین تعبیه‌های حساس به جامعه و حساس به نقش را تنظیم کند.
  • وزن‌های یال را می‌توان در احتمالات پیمایش گنجاند و قدرت رابطه را بدون مراحل مدل‌سازی اضافی ثبت کرد.
  • از طریق نمونه‌برداری کارآمد پیمایش تصادفی و رویه آموزش skip-gram به گراف‌های بزرگ مقیاس‌پذیر است.

کاربردها

  • طبقه‌بندی گره در شبکه‌های استنادی، پلتفرم‌های اجتماعی، یا گراف‌های تعامل بیولوژیکی.
  • پیش‌بینی پیوند — شناسایی یال‌های گمشده یا آینده با مقایسه شباهت تعبیه گره.
  • تشخیص جامعه با خوشه‌بندی بردارهای گره با روش‌های k-means یا سلسله‌مراتبی.
  • تشخیص ناهنجاری — گره‌هایی که تعبیه‌های آن‌ها در فضای برداری نقاط پرت هستند، ممکن است نقش‌های ساختاری غیرمعمولی را نشان دهند.
  • سیستم‌های توصیه‌گر که در آن‌ها کاربران و اقلام گره‌هایی در یک گراف تعامل دوجانبه یا چندلایه هستند.

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

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

1

فرآیند با یک گراف G آغاز می‌شود که در آن گره‌ها موجودیت‌ها و یال‌ها روابط را نشان می‌دهند. یال‌ها می‌توانند جهت‌دار یا بدون جهت باشند و ممکن است وزن‌هایی داشته باشند که بعداً بر احتمال پیمایش تأثیر می‌گذارند. اگر وزن‌های یال وجود داشته باشند، در احتمالات پیمایش گنجانده می‌شوند؛ اگر وجود نداشته باشند، همه یال‌ها وزن یکسانی دریافت می‌کنند. در این مرحله، تحلیلگر همچنین نوع الگوریتم را انتخاب می‌کند — DeepWalk برای پیمایش‌های تصادفی یکنواخت، Node2Vec برای پیمایش‌های بایاس‌شده که توسط پارامترهای p (بازگشت) و q (درون-بیرون) کنترل می‌شوند، یا LINE زمانی که مجاورت مرتبه اول و دوم باید به‌طور جداگانه یاد گرفته شود. انتخاب بین رژیم‌های پارامتری Node2Vec با ویژگی مورد انتظار شبکه هدایت می‌شود: هموفیلی (گره‌های مشابه به هم متصل می‌شوند، بنابراین اکتشاف گستره-اول ترجیح داده می‌شود، q < 1) یا هم‌ارزی ساختاری (گره‌هایی با نقش‌های مشابه ممکن است از هم دور باشند، بنابراین اکتشاف عمق-اول ترجیح داده می‌شود، p < 1).

2

با شروع از هر گره، الگوریتم مجموعه‌ای از پیمایش‌های تصادفی با طول ثابت (معمولاً 30 گام) را شبیه‌سازی می‌کند و آن‌ها را چندین بار تکرار می‌کند (معمولاً 200 پیمایش برای هر گره). هر پیمایش دنباله‌ای از شناسه‌های گره را تولید می‌کند که مشابه جمله‌ای از کلمات است. در DeepWalk، گره بعدی به‌طور یکنواخت از بین همسایگان انتخاب می‌شود. در Node2Vec، گره بعدی بر اساس احتمالات انتقال بایاس‌شده توسط p و q انتخاب می‌شود: بازگشت به گره قبلی با 1/p جریمه می‌شود، ماندن در همان فاصله با 1 حفظ می‌شود، و دورتر شدن با 1/q کنترل می‌شود. مجموعه تمام پیمایش‌ها، مجموعه‌ای از دنباله‌های گره را تشکیل می‌دهد که توپولوژی گراف را رمزگذاری می‌کند.

3

مجموعه دنباله‌های گره به یک مدل skip-gram (همان معماری Word2Vec) وارد می‌شود. برای هر گره در یک پیمایش، مدل گره‌های زمینه اطراف را در یک پنجره (معمولاً 10 گام) پیش‌بینی می‌کند. از طریق گرادیان کاهشی تصادفی، مدل یک نمایش برداری فشرده با بُعد ثابت — معمولاً 64 یا 128 — برای هر گره یاد می‌گیرد، به‌طوری‌که گره‌هایی که در پیمایش‌ها هم‌اتفاق می‌افتند، بردارهای مشابهی دارند. بُعد یک ابرپارامتر است: ابعاد بزرگ‌تر ساختار بیشتری را ثبت می‌کنند اما محاسبات را افزایش می‌دهند و خطر بیش‌برازش (overfitting) را در گراف‌های کوچک افزایش می‌دهند.

4

پس از آموزش، مدل یک بردار تعبیه شده برای هر گره ارائه می‌دهد. این بردارها به عنوان ویژگی برای طبقه‌بندی گره (وارد کردن آن‌ها به یک رگرسیون لجستیک یا طبقه‌بند عصبی)، پیش‌بینی پیوند (مقایسه شباهت بردارهای جفت گره‌های کاندید)، یا تشخیص جامعه (خوشه‌بندی بردارها) استفاده می‌شوند. این تعبیه‌ها تراکنشی (transductive) هستند: آن‌ها برای گره‌هایی که در طول آموزش دیده شده‌اند، ثابت هستند. اگر گره‌های جدید باید پس از آموزش تعبیه شوند، باید از یک روش القایی (inductive) مانند GraphSAGE استفاده شود، زیرا مدل استاندارد Node2Vec یا DeepWalk بدون بازآموزی نمی‌تواند به گره‌های دیده‌نشده تعمیم یابد.

دام‌های رایج

  • اعمال مدل Node2Vec به گره‌های جدیدی که در گراف آموزشی نبودند — مدل برداری برای آن‌ها نخواهد داشت؛ در صورت غیرقابل قبول بودن تعبیه تراکنشی، از روش القایی (مانند GraphSAGE) استفاده کنید.
  • استفاده از p=1، q=1 پیش‌فرض (معادل DeepWalk) بدون بررسی اینکه آیا شبکه از الگوی هموفیلی یا هم‌ارزی ساختاری پیروی می‌کند — تنظیم p و q برای الگوی مورد انتظار می‌تواند عملکرد وظیفه پایین‌دستی را به‌طور قابل توجهی بهبود بخشد.
  • در نظر گرفتن بُعد تعبیه به عنوان یک ثابت: در گراف‌های کوچک، بُعد 64 یا 128 ممکن است بیش‌برازش ایجاد کند؛ با بُعد کمتر شروع کنید و بر اساس وظیفه پایین‌دستی اعتبارسنجی کنید.
  • نادیده گرفتن حداقل نیاز نمونه: گراف‌های با کمتر از 50 گره، مجموعه پیمایش‌های بسیار نازکی تولید می‌کنند که برای آموزش تعبیه‌های قابل اعتماد کافی نیست.

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

تفاوت بین DeepWalk، Node2Vec و LINE چیست؟

DeepWalk از پیمایش‌های تصادفی یکنواخت و مدل skip-gram Word2Vec استفاده می‌کند — این ساده‌ترین خط پایه است. Node2Vec پیمایش‌های تصادفی بایاس‌شده کنترل‌شده توسط p و q را اضافه می‌کند، که به تحلیلگر اجازه می‌دهد تنظیم کند که آیا پیمایش مانند جستجوی گستره-اول (هموفیلی) یا جستجوی عمق-اول (هم‌ارزی ساختاری) کاوش می‌کند. LINE اصلاً از پیمایش‌های تصادفی استفاده نمی‌کند؛ این الگوریتم مستقیماً اهداف مجاورت مرتبه اول و دوم را روی لیست یال‌ها بهینه‌سازی می‌کند، که برای گراف‌های بسیار بزرگ مقیاس‌پذیرتر است اما سیگنال همسایگی مبتنی بر پیمایش را فدا می‌کند.

چگونه پارامترهای p و q را در Node2Vec انتخاب کنم؟

p احتمال بازگشت به گره قبلی را کنترل می‌کند (p کم = عقب‌گرد کمتر)، و q شعاع اکتشاف را کنترل می‌کند (q < 1 اکتشاف به سمت بیرون را ترجیح می‌دهد، q > 1 پیمایش را نزدیک منبع نگه می‌دارد). اگر انتظار دارید گره‌ها در یک جامعه مشابه باشند (هموفیلی)، q < 1 را تنظیم کنید تا پیمایش به سمت بیرون حرکت کند. اگر انتظار دارید گره‌هایی با نقش ساختاری مشابه، حتی اگر دور باشند، مشابه باشند، p < 1 را تنظیم کنید تا اکتشاف عمق-اول را تشویق کنید. هر دو رژیم را بر اساس وظیفه پایین‌دستی اعتبارسنجی کنید.

آیا می‌توانم گره‌های جدید را پس از آموزش بدون بازآموزی کل مدل تعبیه کنم؟

Node2Vec و DeepWalk استاندارد تراکنشی هستند: ماتریس تعبیه فقط گره‌های دیده‌شده در طول آموزش را پوشش می‌دهد. برای تعمیم القایی به گره‌های جدید و قبلاً دیده‌نشده، از روش شبکه عصبی گراف القایی مانند GraphSAGE استفاده کنید، که یک تابع تجمیع را بر روی همسایگی‌های گره یاد می‌گیرد که می‌تواند در زمان استنتاج به هر گرهی اعمال شود.

چند بُعد باید برای تعبیه استفاده کنم؟

رایج‌ترین انتخاب‌ها 64 و 128 هستند و این‌ها برای گراف‌های متوسط تا بزرگ به‌خوبی کار می‌کنند. برای گراف‌های کوچک (50-200 گره) با بُعد کمتر (16 یا 32) شروع کنید تا از بیش‌برازش جلوگیری شود و کیفیت تعبیه را با اندازه‌گیری عملکرد وظیفه پایین‌دستی (مانند دقت طبقه‌بندی گره) به جای خطای بازسازی به‌تنهایی ارزیابی کنید.

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

منابع

  1. Grover, A. & Leskovec, J. (2016). Node2Vec: Scalable Feature Learning for Networks. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 855-864.

    باز کردن مرجع DOI
    کپی شد.
  2. Perozzi, B., Al-Rfou, R., & Skiena, S. (2014). DeepWalk: Online Learning of Social Representations. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 701-710.

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