دیتا استراکچر های گراف در چند سال اخیر مورد توجه بسیاری از سازمان ها و صنایع مختلف شده اند .
برای مثال آزمایشگاه های ژنتیک گیاهی برای تشخیص تغییر کروموزوم ها بر روی درخت نسلی زیر هر گیاه از دیتا بیس های گراف استفاده میکنن ، فیسبوک برای پیشنهاد دوستان و مطالب از نزدیکی نقطه شما به گروه های نزدیک در گراف اطلاعاتی خود استفاده میکند ، یا تویتر به وسیله گروه های جمعیتی گراف ها و مطالب نشر شده توسط آنها تصمیم به برخورد با گروه های تندرو میکند .
اما مشکل بسیار بزرگ در گراف این است که گراف در فضا و ابعاد زندگی نمیکند به عبارت دیگر نمیتوان نود و ادج ( به فارسی راس و یال ) را با عدد معرفی کرد و آنها را از هم کم کرد یا اضافه کرد برای همین انجام بسیاری از محاسبات کلاسیک بر روی گراف غیر ممکن میشود و بسیاری از الگوریتم هایی که در دنیای هوش مصنوعی برای گراف ارائه میشوند روشی های هستند که بتوان هر نود یا ادج را بتوان به وسیله عدد معرفی بکنند که بتوان با آنها مانند دیتا استراکچر های عددی ( وکتور و ماتریکسی ) برخورد کرد .
در این نوشته من قصد دارم دو روش آموزش بدهم که هر نود را بتواند به عددی بر روی یک فضا تبدیل بکند که بتوان بر روی آن محاسبات انجام داد و بتوانیم از دانش نهفته در گراف هم استفاده بکنیم .
اول - DeepWalk
این روش که توسط دکتر steven skiena و تیمش ارائه شد روشی است که به گراف ها نگاهی همانند متن میشد . در این روش عملیات بسیار ساده است .
اول - چه تعداد پیاده روی از هر نود به عنوان مبدا انجام بشود .
دوم - تعداد قدم ها را مشخص میکنید ، به عبارتی هر پیاده روی چند قدم باشد و چند نود را طی بکند .
با همین روش ساده حجم زیادی از اطلاعات متوالی تولید میشود که میتوان بر روی آنها محاسبات انجام داد .
در این روش پیشنهاد میشود از روش skip gram استفاده بشود که بتوان برای هر نود مقادیر عددی تعریف کرد .
توجه داشته باشید که تمام ادج ها در این روش دارای مقادیری عددی نیستند و احتمال نسبت به تعداد نود های وصل شده به هر نود تغییر میکنند .
مثال :
در تصویر بالا پروسه رندوم واک دو بار انجام شده .
و اطلاعات به شکل زیر تبدیل میشوند :
0 -> 1 -> 2 -> 5 -> 6
0 -> 1 -> 2 -> 4 -> 8
این اطلاعات بعد از پروسس و ترین کردن نتیجه ای مثل تصویر بالا ایجاد میکنند اما توجه داشته باشید که تصویر بالا فقط جهت آموزش است بهتر است تعداد ابعاد انتخابی برای skip gram عدد بسیار بالاتری باشد مثل 300 و بعد از آن میتوانید با الگوریتم هایی مثل t-sne به دو بعد تبدیل کنید تا اطلاعات را تصویری ببینید.
دوم - node2vec
این روش که توسط Aditya Grover و Jure Leskovec ارائه شد بهبودی بر روش قبل بود سعی شد در این روش پروسه random walk کنترل بشود.
در این الگوریتم دو پارامتر به موضوع اضافه میشوند :
p , q
این دو پارامتر تعین کننده رفتار الگوریتم هستند که مسیر پیاده روی در محدوده نود اولیه باشد یا به سمت نود های بیرونی حرکت بکند و در هر قدم دورتر بشود .
در تصویر بالا پیاده روی از دایره قرمز شروع شده و به سمت نود سبز حرکت کرده ( توجه : حرکت اول به صورت رندوم هست و نظمی ندارد ) بعد از رسیدن به نود سبز حال میخواهیم به نود بعدی حرکت بکنیم و اینجاست که p,q خود را نشان میدهند .
اگر احتمال رفتن به هر نود 1 باشد :
متغیر p ) برای ادج هایی استفاده میشود که به نود قبلی برمیگردند
متغیر q ) برای ادج هایی استفاده میشود که به نود هایی جدید میرسند
بدون تغییر ) اگر نود مقصد همسایه نود قبلی باشد ( در تصویر دقت کنید که نود پایین سمت راست به دلیل همسایگی با نود قرمز بدون تغییر میماند و بر عددی تقسیم نمیشود )
بعد از به دست آوردن اعداد یعنی تقسیم عدد هر ادج ( در این مثال یک در نظر گرفته شده ) بر متغیر مورد نظر خود اعداد را به وسیله فانکشن softmax نرمال میکنیم و عدد رندوم را از distribution softmax انتخاب میکنیم.
و این پروسه را برای تمام نود ها و تعداد واک های مورد نظر انجام میدهیم و بعد از skip gram استفاده میکنیم .
نتیجه :
به وسیله این دو الگوریتم اکنون میتوانیم دیتاهای گراف را به وسیله vector نشان بدهیم و همان عملیاتی را انجام بدهیم که دوستان nlp در word embedding انجام میدهند . همان مثال معروف
king - man + woman = queen
و الان که هر نود دارای نشانی عددی هست میتوان عملیات های کلاسیک یادگیری ماشین را بسیار راحت تر انجام داد . مثلا میتوان از cosine similarity بین نقاط برای یک سیستم recommender استفاده کرد و ... .
اما این الگوریتم ها مشکلات خود را دارند که شاید در یادگیری های nlp مهم نباشند اما در اینجا خود را بسیار نشان میدهند .
مشکل اول اینکه بسیار از نظر محاسباتی این روش سنگین است و آماده کردن اطلاعات زمان زیادی میبرد به دست اوردن بعضی از اعداد در آماده سازی این اطلاعات هم خواهان الگوریتم های سنگین هست مثل الگوریتم average degree of separation برای تعیین کردن تعداد واک از هر نود که خود مطلب جدایی را به خود اختصاص میدهد .
مشکل دوم اضافه شدن هر نود به گراف خواهان تکرار بعضی از قسمت های الگوریتم است برای مثال اگر بخواهیم گراف کاربران فیسبوک را در نظر بگیریم با هربار اضافه شدن کاربر به گراف باید کلی محاسبات رو دوباره انجام بدهیم . یا اینکه اگر ذائقه کاربر عوض بشود در لحظه امکان محاسبه برای ما امکان ندارد .
پس استفاده از این روش خواهان دقت بسیار است که در چه مواردی باید استفاده بشود .
امیدوارم این آموزش مورد استفاده شما قرار بگیرد و اگر هر سوالی داشتید با کمال میل جواب میدهم ( بیشتر در تویتر فعال هستم ) .
پایان.
