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

