خب، بیا یه گپ دوستانه بزنیم درباره یه موضوع جذاب و جدید که توی دنیای داده و هوش مصنوعی خیلی ازش حرف می‌زنن: “خوشه‌بندی گراف‌ها”، خصوصا وقتی بعضی اطلاعات گرافت ناقص باشه. حالا اگه نمی‌دونی خوشه‌بندی گراف چیه، بزار خلاصه بگم: فرض کن یه شبکه اجتماعی مثل اینستاگرام یا لینکدین داری؛ هر نفر یه نقطه‌اس (که میگن “گره” یا “نود”) و رابطه‌هاشون میشه “یال”. حالا خوشه‌بندی یعنی بیا اونایی که شبیه هم هستن و ارتباطای بیشتری دارن رو کنار هم بذاریم، مثلا همه بچه‌مثبتا یا همه خل‌وچل‌هایی که بهم رفیقن، توی یه دسته بندازیم! این کار یه اصطلاح خفن داره: Deep Graph Clustering یا همون DGC. البته Deep یعنی با مدل‌های یادگیری عمیق (یه جور یادگیری ماشینی خفن که کلی لایه داره)، Graph یعنی گراف (یعنی شبکه‌ای از آدم‌ها یا چیزهای دیگه) و Clustering یعنی خوشه‌بندی یا دسته‌بندی بدون کمک از قبل (بدون مربی). مثلاً وقتی می‌خوای تو شبکه اجتماعی آدمایی که یه مدل خاص رفتار می‌کنن رو خود مدل بفهمه و گروه‌بندی کنه.
حالا مشکل چیه؟ تو دنیای واقعی گراف‌ها معمولاً خیلی بزرگ و دیتایِ بعضی از گره‌ها ناقصه. مثلاً تو تلگرام ممکنه شماره موبایل بعضیا نباشه، یا تو شبکه فیسبوک بعضیا عکس پروفایل نذاشته باشن؛ خلاصه اطلاعات خیلی وقتا کامل نیست (به این میگن “attribute-missing” یعنی وقتی ویژگی‌های گره‌ها ناقص هستن). این موضوع حسابی کار خوشه‌بندی رو سخت می‌کنه.
اینجا نویسنده‌های مقاله یه راهکار جدید و خیلی باحال پیشنهاد کردن به اسم: CMV-ND (که خودش مخفف Complementary Multi-View Neighborhood Differentiation هست!). حالا یعنی چی؟ بیا مرحله به مرحله توضیح بدم:
۱. اول ایده اصلی اینه: وقتی گراف بزرگ و اطلاعاتش ناقصه، بهتره اطلاعات ساختاری (یعنی چجوری گره‌ها به هم وصل شدن) رو بهتر استخراج کنیم و بینش دقیق‌تر داشته باشیم. برای این کار بریم سراغ همسایه‌های هر گره، اونم نه فقط همسایه‌های مستقیم، بلکه همسایه‌های دورتر، که بهش میگن “hop”؛ هر hop یعنی یه قدم دورتر توی شبکه بری. Recursive Neighborhood Search یعنی هی به صورت بازگشتی بری سراغ دوستای دوستا و حتی دورترهاشون، تا ساختار کامل گراف واسه هر گره رو بسازی.
۲. خب حالا که همسایه‌ها رو پیدا کردی، شاید اطلاعات تکراری بشه، چون ممکنه بعضیا با چند مسیر به یه گره برسن. اینجاست که نویسنده‌ها یه چیز باهوشانه پیشنهاد دادن به اسم Neighborhood Differential Strategy یعنی اطلاعات هر hop رو جوری سوا کن، که هیچ همپوشانی بین گره‌های هر مرحله نباشه. اینطوری حتی اگه اشتراک داشته باشن، اون بخش مشترکش رو حذف می‌کنی و هر بار فقط گره‌های جدید رو نگه می‌داری. نتیجه؟ همه اطلاعات ساختاری رو جمع می‌کنی بدون اینکه دیتای تکراری داشته باشی.
۳. بعد با همه این اطلاعاتِ تمیز شده، میان چند “نما” یا View درست می‌کنن. مثلاً اگه K تا hop داری، میشه K تا دید مختلف از اطراف اون گره (مثل اینکه از زاویه‌های مختلف به گراف نگاه کنی)، و علاوه بر اون Features خود گره هدف رو هم اضافه می‌کنن. به این‌ها میگن(K+1) complementary views یعنی چندتا نمای مکمل از گراف داری که هم تصویر بزرگ بهت میده هم جزئیات رو خوب نشون میده.
۴. آخرش این نماها رو به روش‌های خوشه‌بندی مولتی‌ویو میدن (Multi-view Clustering یعنی روشی که از چند نما یا View به طور همزمان برای دسته‌بندی استفاده می‌کنه)، یا هر مدل خوشه‌بندی گرافی که قبلاً ساختی، و نتیجه خارق‌العاده‌س! توی آزمایش‌ها شیش‌تا دیتاست معروفِ شبکه‌ای رو تست کردن، و روش CMV-ND تونسته حسابی عملکرد روش‌های قبلی رو بهتر کنه. یعنی هم دقت خوشه‌بندی بالاتر رفته، هم با مقیاس بزرگ و گراف ناقص خوب کنار اومده.
خلاصه اینکه، با این روش جدید میشه خوشه‌بندی گراف‌هایی که بعضی اطلاعاتشون ناقصه، یا خیلی بزر گراف دارن، رو خیلی بهتر و تمیزتر انجام داد و دیگه از ناقص بودن داده هم نمی‌ترسی! اگه تو حوزه هوش مصنوعی، داده‌کاوی، یا حتی شبکه‌های اجتماعی کار می‌کنی، این روش CMV-ND واقعاً می‌تونه یه تغییر خوب واست به وجود بیاره… خلاصه هر جا گراف بزرگ و پرت و پلایی داشتی، این تکنیک رو یاد داشته باش که کلی ب کارت میاد!
منبع: +
