مقدمه‌ای بر شبکه‌های عصبی گراف

1. مقدمه:

این ادامه سری وبلاگ‌های من در گراف‌ها است و هشتمین وبلاگ از این مجموعه است. در این مقاله، من قصد دارم در مورد یادگیری عمیق برای گراف‌ها و به ویژه تکنیک‌های مربوط به شبکه‌های عصبی گراف (GNN) صحبت کنم. GNNها یکی از محوری‌ترین موضوعات در گراف‌ها هستند و در واقع تمام مقالات قبلی من در این سری از وبلاگ‌های گراف به عنوان پایه‌ای محکم برای شبکه‌های عصبی گراف عمل می‌کند.

این مقاله به جزئیات دقیق شبکه‌های عصبی گراف نمی‌پردازد - جزئیات دقیق GNNها بخشی از وبلاگ‌های بعدی من خواهد بود. این مقاله سعی دارد ابتدا (در بخش 2) محدودیت‌های تعبیه گره به دست آمده با استفاده از شبکه‌های کم عمق مانند مدل skip-gram را همانطور که در قسمت 5، قسمت 6 و قسمت 7 این مجموعه مورد بحث قرار گرفت و سپس در بخش 3 و بخش 4 توضیح دهد. این مقاله نشان می‌دهد که چگونه شبکه‌های گراف عمیق بر این محدودیت‌ها غلبه می‌کنند و رویکردی برای حل مسئله که شامل پیش‌بینی است – مانند دسته‌بندی گره یا پیش‌بینی پیوند یا تشخیص ناهنجاری در گراف‌ها/زیرگراف‌ها، از انتها به انتها. بخش 4 همچنین نشان می‌دهد که چگونه پردازش یک گراف برای یادگیری عمیق با پردازش تصاویر یا متون متفاوت است.

بررسی مفهوم تعبیه گره:

در مقالات قسمت 5، قسمت 6 و قسمت 7 این مجموعه، در مورد "تعبیه گره‌ها" صحبت کردم که در آن قصد نگاشت گره‌ها از گراف به یک فضای تعبیه d بعدی بود تا گره‌های مشابه در شبکه باشند. همانطور که در شکل زیر نشان داده شده است، نزدیک به یکی و دیگری در فضای تعبیه شده نگاشت شده است.

شکل 1: تعبیه گره‌های 2 بعدی

به طور خلاصه، ما می‌خواستیم به این هدف برسیم که شباهت گره‌ها در شبکه معادل شباهت در فضای تعبیه‌شده است که از طریق معادله زیر نشان داده شده است.

معادله 1 - هدف از تعبیه گره‌ها - گره‌های مشابه در شبکه باید با شباهت در فضای تعبیه مطابقت داشته باشند.

شباهت گره‌ها در شبکه معمولاً از طریق شباهت جاکارد اندازه‌گیری می‌شود، همانطور که در بخش 3 از قسمت 6 سری وبلاگ‌های من با عنوان: «فرمول‌بندی تعبیه‌های گره در گراف‌ها: الگوریتم Node2Vec» مورد بررسی قرار می‌گیرد. و شباهت در فضای تعبیه با حاصلضرب نقطه بین دو بردار اندازه‌گیری می‌شود.

بنابراین، با توجه به یک گراف، نحوه ساخت یک ماتریس “Z” را همانطور که در شکل زیر نشان داده شده است، فهمیدیم که در آن هر ستون ماتریس با بردار تعبیه گره مربوطه در گراف مطابقت دارد:

شکل 2: تعبیه گره‌ها از طریق شبکه‌های کم عمق مانند مدل skip-gram آموخته شده است.

2. محدودیت‌های رویکردها برای نگاشت گره‌ها از گراف تا فضای تعبیه

با این حال، روش‌هایی مانند Node2Vec که در قسمت 6 سری وبلاگ‌های من مورد بحث قرار گرفت، محدودیت‌های خاصی داشت:

الف) تعداد پارامترهای مورد نیاز برای یادگیری:

ممکن است یادآوری شود که الگوریتم Node2Vec که در اینجا مورد بحث قرار گرفت، شامل مدل skip-gram برای یادگیری تعبیه‌های گره بود که از طریق وزن‌های لایه پنهان شبکه عصبی تک لایه نشان داده شد. برای هر گره، تعداد پارامترهایی که باید یاد بگیرند برابر با بعد “d” فضای تعبیه شده است.

بنابراین، برای کل گراف، تعداد کل پارامترهایی که باید یاد بگیرند برابر با تعداد گره‌ها x بعد تعبیه شده است که بسیار زیاد است. هیچ اشتراک پارامتری بین گره‌ها وجود نداشت.

ب) یادگیری انتقالی:

یادگیری با استفاده از مدل skip-gram، یادگیری انتقالی بود. این بدان معناست که یادگیری فقط شامل گره‌های «دیده شده» یا نمونه‌های «دیده شده» در فرآیند آموزش می‌شود. تعبیه گره‌های آموخته شده را نمی‌توان برای گره‌های دیده نشده از گراف‌های دیده نشده استفاده کرد. بنابراین، ما قادر به ایجاد تعبیه برای گره‌هایی که در طول آموزش دیده نمی‌شوند، نبودیم.

ج) ویژگی‌های گره که در تعبیه‌ها گنجانده نشده‌اند:

یادگیری با استفاده از Node2Vec که در قسمت 5 و قسمت 6 وبلاگ من مورد بحث قرار گرفت، شامل یادگیری ساختار شبکه زیرین گراف بود. یادگیری ویژگی‌های گره را در بر نمی‌گرفت. یک گره ممکن است دارای ویژگی‌هایی مانند سن، مکان، جنسیت و غیره بسته به مسئله موجود باشد. ویژگی‌های گره بخشی از بردار جاسازی نبودند. بنابراین، یادگیری نمی‌تواند پایان به انتها باشد.

اکنون می‌خواهیم در مورد رمزگذارهای گراف عمیق - شبکه‌های عصبی گراف صحبت کنیم که در آن ایده این است که رمزگذاری یک گره “v” در فضای تعبیه شامل تبدیل‌های غیرخطی چند لایه است. بنابراین، ما قصد داریم در مورد شبکه‌های عصبی عمیق و نحوه تبدیل اطلاعات از طریق لایه‌های متعدد شبکه عصبی و در نتیجه تعبیه نهایی صحبت کنیم.

بنابراین، آموزش مدل از طریق شبکه‌های عصبی گراف امکان‌پذیر خواهد بود: از انتها به انتها برای مسائل مربوط به دسته‌بندی گره یا پیش‌بینی پیوند یا هر نوع کار پیش‌بینی گراف.

3. شبکه‌های عصبی عمیق

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

شکل 3: فرآیند یادگیری در شبکه‌های عصبی گراف عمیق

خوبی در مورد Deep Encoders این است که ما می‌توانیم این رمزگذارها را به صورت سراسری آموزش دهیم - از دریافت ویژگی‌های گره تا پیش‌بینی.

راه‌حل‌ها از طریق شبکه‌های عصبی عمیق:

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

با شبکه‌های گراف عمیق، یادگیری می‌تواند سرتاسر باشد و قادر به حل مسائل مختلف مانند:

·         دسته‌بندی گره - برای پیش‌بینی نوع گره.

·         پیش‌بینی پیوند – برای پیش‌بینی اینکه آیا دو گره به هم مرتبط هستند یا خیر.

·         تشخیص انجمن - یعنی: خوشه‌بندی / نوع ارتباط وظایف برای شناسایی خوشه گره‌های بهم پیوسته.

·         یا وظایفی که شامل شباهت / سازگاری بین گراف‌ها یا زیرشبکه‌های مختلف است.

شکل 4: دسته‌بندی گره‌ها با استفاده از GNN.

شکل 5: پیش‌بینی پیوند با استفاده از GNN.

5. یادگیری عمیق کلاسیک در مقابل شبکه‌های عصبی گراف

یادگیری عمیق کلاسیک برای انواع داده‌های ساده طراحی شده است. به عنوان مثال، می‌توان تصاویر با اندازه ثابت w یا متن را پردازش کرد که یک گراف زنجیره / دنباله است همانطور که در شکل زیر نشان داده شده است.

شکل 6: یادگیری عمیق برای دسته‌بندی تصاویر

بنابراین، جعبه ابزار یادگیری عمیق کلاسیک برای انواع داده‌های ساده مانند توالی‌های خطی، شبکه‌های با اندازه ثابت مناسب‌تر است و نمی‌توان آن را برای انواع داده‌های پیچیده مانند گراف‌ها اعمال کرد.

شکل 7: یادگیری عمیق برای وظایف پردازش زبان طبیعی

اکنون سؤال این است که چگونه می‌توانیم یادگیری عمیق را برای انواع داده‌های پیچیده مانند گراف‌ها اعمال کنیم و اینجاست که شبکه‌های عصبی گراف وارد عمل می‌شوند زیرا به ما امکان می‌دهند یادگیری بازنمایی را برای انواع داده‌های بسیار پیچیده‌تر مانند شبکه‌ها یا تصاویر اعمال کنیم. موارد استفاده زیادی وجود دارد که در بخش 2 از بخش 1 سری وبلاگ های من مورد بحث قرار گرفت که در آنها نمایش گراف مناسب از اهمیت بالایی برخوردار است. بیایید ببینیم که چگونه شبکه‌های عصبی گراف می‌توانند توپولوژی پیچیده گراف‌ها را نشان دهند و چندین مسئله را که نیاز به بازنمایی گرافیکی دامنه زیربنایی دارند، حل کنند. جزئیات شبکه‌های گراف در وبلاگ‌های بعدی این مجموعه مورد بحث قرار خواهد گرفت!

تعبیه کل گراف‌ها یا زیر گراف‌ها

1. مقدمه:

این ادامه سری وبلاگ‌های من در Graphs است و هفتمین وبلاگ از این مجموعه است. در دو مقاله اخیرم، من درباره تعبیه گره صحبت کرده‌ام - مقاله ۵ بر مفهوم "یادگیری بازنمایی گراف" تاکید کرد که در آن به جای استخراج ویژگی‌های سطح گره، سطح پیوند، سطح گراف با استفاده از مهندسی ویژگی دستی، ایده این بود که با توجه به هر گره هر گره را در یک فضای تعبیه d بعدی نگاشت می‌کنیم. این تعبیه‌های گره در فضای تعبیه d بعدی شبکه گراف زیربنایی مورد علاقه ما را به تصویر می‌کشد. هدف از تعبیه‌های گره این است که گره‌ها را رمزگذاری کنند تا شباهت در فضای تعبیه با شباهت در گراف تقریبی شود - به طوری که گره‌های مشابه در فضای تعبیه نزدیک به یکدیگر قرار دارند.

مقاله 6، سپس به فرمول‌بندی تعبیه گره با استفاده از الگوریتم Node2Vec. مقاله برخی از مفاهیم بسیار مهم در گراف‌ها مانند "زمینه" گراف‌ها را برجسته می‌کند که تعبیه گره‌ها سعی می‌کنند از آن تقلید کنند همانطور که در بخش 3 مقاله ششم من بحث شد. این مقاله مجدداً از مدل skip-gram مورد استفاده برای تولید تعبیه‌های کلمه در پردازش زبان طبیعی بازدید کرد و سپس توضیح داد که چگونه می‌توان از همان مدل skip-gram برای تولید تعبیه‌های گره در یک گراف استفاده کرد و در نتیجه شباهت مفهومی بین واژه‌ها و تعبیه‌های گره را برجسته کرد. .

این مقاله در مورد تعبیه کل گراف‌ها صحبت خواهد کرد. یعنی: به جای تعبیه گره‌های مجزا، چگونه می‌توانیم کل گراف یا یک زیرگراف را در یک گراف تعبیه کنیم؟ ما در مورد 4 رویکردی که ممکن است برای تعبیه کل گراف‌ها استفاده شود، بحث خواهیم کرد:

·         گراف‌های تعبیه شده را به عنوان مجموع تعبیه گره‌ها،

·         تعبیه گراف‌ها/زیرگراف‌ها از طریق یک گره مجازی،

·         تعبیه گراف‌ها/زیرگراف‌ها از طریق پیاده‌روی تصادفی ناشناس و

·         تعبیه گراف‌ها را از طریق پیاده‌سازی‌ها نشان می‌دهند

موارد فوق از طریق بخش‌های زیر در این مقاله مورد بحث قرار می‌گیرد. به طور کلی، ممکن است کسی بخواهد کل گراف‌ها یا زیر گراف‌ها را در یک فضای تعبیه برای موارد استفاده مختلف تعبیه کند:

۱) به عنوان مثال، ممکن است کسی بخواهد گراف‌های غیرعادی را از مجموعه‌ای از گراف‌ها یا زیرگراف‌های غیرعادی را از یک گراف با اندازه بزرگ تشخیص دهد.

۲) یا برای دسته‌بندی مولکول‌ها، اگر بخواهیم پیش‌بینی کنیم که کدام مولکول سمی یا غیرسمی است. از آنجایی که یک مولکول از مجموعه‌ای از اتم‌ها یعنی گره‌ها در یک گراف تشکیل می‌شود، مسئله دسته‌بندی مولکول ممکن است شامل تعبیه مجموعه‌ای از گره‌ها یا کل گراف در فضای تعبیه باشد.

سپس هدف این است که کل گراف را در یک فضای تعبیه یا زیر مجموعه‌ای از گره‌ها در گراف در یک فضای گره قرار دهیم، همانطور که در شکل زیر نشان داده شده است:

شکل 1: تعبیه کل گراف (یا، یک زیرگراف) در فضای تعبیه.

می‌تواند رویکردهای متفاوتی برای انجام این کار وجود داشته باشد و اجازه دهید اکنون برخی از این رویکردهای مختلف را مورد بحث قرار دهیم که در بخش‌های زیر مورد بحث قرار گرفته‌اند.

2. تعبیه کل گراف‌ها به عنوان مجموع تعبیه گره‌ها:

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

معادله - تعبیه کل گراف به عنوان مجموع تعیبه گره‌های جداگانه

این روش در سال 2016 توسط دوونود و همه در مقاله 2016 خود با عنوان: "شبکه‌های کانولوشنال روی گراف‌ها برای یادگیری اثر انگشت مولکولی" برای دسته‌بندی مولکول‌ها بر اساس ساختار گراف استفاده شد و بسیار موفق بود. این یک رویکرد بسیار ساده بود و نویسندگان از آن نقل کردند که در عمل بسیار خوب عمل کرد.

3. تعبیه گراف‌ها از طریق یک گره مجازی:

یک پیشرفت نسبت به ایده اولیه میانگین‌گیری تعبیه‌های گره، معرفی یک گره مجازی برای نمایش کل گراف یا زیرگراف و سپس اجرای یک تکنیک استاندارد تعبیه گره مانند Node2Vec است. گره مجازی - همانطور که در شکل زیر نشان داده شده است - اساساً تعبیه کل گراف را نشان می‌دهد.

شکل 2: تعبیه زیر مجموعه‌ای از گره‌ها یا کل گراف با اتصال آن گره‌ها به یک گره مجازی.

مراحل کلی این رویکرد را می‌توان به صورت زیر توضیح داد:

·         گره مجازی را مطابق شکل زیر ایجاد کنید:

شکل 3: شبکه و گره مجازی

·         گره مجازی را به مجموعه‌ای از گره‌ها در کل گراف یا زیرگرافی که می‌خواهیم مطابق شکل زیر تعبیه کنیم وصل کنیم.

شکل 4: گره مجازی متصل به زیر مجموعه گره‌هایی که می‌خواهیم تعبیه کنیم

الگوریتم Node2Vec را اجرا کنید تا تعبیه گره مجازی همانطور که در شکل زیر نشان داده شده است را بدست آورید.

شکل 5: زیرمجموعه گره‌ها یا تمام گره‌های گراف که با استفاده از الگوریتم Node2Vec در فضای تعبیه شده‌اند.

اگر کسی بخواهد کل گراف را جاسازی کند، گره مجازی به تمام گره‌های شبکه متصل می‌شود. این رویکرد توسط لی و همه پیشنهاد شد و در مقاله‌ای با عنوان "شبکه‌های عصبی توالی گراف دروازه‌ای" که در https://arxiv.org/abs/1511.05493  موجود است توضیح داده شده است.

4. جاسازی گراف‌ها از طریق پیاده‌روی تصادفی ناشناس:

این رویکرد در مقاله “Anonymous Walk Embeddings” توسط Sergey Ivanoc و Ergeny Burnaer https://arxiv.org/abs/1805.11921  منتشر شد. این مقاله در سال 2018 منتشر شد و رویکرد دیگری برای تعبیه کل گراف‌ها بود.

من سعی کرده ام مفهوم دستیابی به تعبیه‌های گراف را از طریق پیاده‌روی‌های ناشناس از طریق بخش‌های فرعی زیر توضیح دهم:

·         ایده کلی تعبیه کل گراف‌ها یا زیرگراف‌ها با استفاده از پیاده‌روی ناشناس

·         پیاده‌روی‌های ناشناس چیست؟

·         چرا پیاده‌روی ناشناس؟

·         تعداد پیاده‌روی‌های تصادفی ناشناس ممکن در یک گراف

·         و سپس، در بخش 5، ما چگونه می‌توانیم گراف‌ها را از طریق پیاده‌روی تصادفی به طول l تعبیه کنیم.

ایده کلی تعبیه کل گراف‌ها با استفاده از تعبیه‌های پیاده‌روی ناشناس:

به طور اساسی، ما می‌خواهیم کل گراف را در فضای تعبیه جاسازی کنیم. برای اینکه بتوان گراف را با موفقیت تعبیه کرد، باید بتواند «زمینه» کل گراف را کپسوله کند. "زمینه" گراف از طریق:

۱) همسایگان مستقیم گراف.

۲) اتصالات یک گره از طریق عمق گراف.

من در مورد مفاهیم مربوط به جستجوی اول عرض (BFS) و جستجوی اول عمق (DFS) در قسمت 6 این سری از وبلاگ در بخش 3 اینجا صحبت کرده بودم. برای بدست آوردن همسایگان مستقیم یک گره و اتصالات آن در عمق یک گراف، باید پیاده‌روی‌های تصادفی را با هر گره انجام داد.

با جمع کردن احتمالات در تمام رئوس در یک گراف و نرمال کردن آنها بر اساس تعداد کل گره‌ها، احتمال انتخاب پیاده‌روی ناشناس در گراف G را به دست می‌آوریم. و این همان کاری است که "پیاده‌روی تصادفی ناشناس" همانطور که در پاراگراف های بعدی توضیح داده شد، انجام خواهد داد. .

پیاده‌روی‌های ناشناس چیست؟

اجازه دهید یک نمونه زیرگراف مورد علاقه را در نظر بگیریم - که ممکن است بخواهیم برای آن تعبیه ایجاد کنیم - نشان داده شده در شکل زیر:

شکل 6: گراف مورد علاقه

بیایید بگوییم که، ما یک پیاده روی تصادفی انجام می‌دهیم که از A شروع می شود و سپس به B و سپس به C پیمایش می کنیم و سپس به B برمی گردیم و سپس به سمت C حرکت می کنیم همانطور که در شکل زیر نشان داده شده است.

شکل 7- پیاده‌روی تصادفی 1 در گراف شکل 6

یک پیاده‌روی تصادفی دیگر که از C شروع می‌شود، به D و سپس به B به D و به B برمی‌گردد، همانطور که در زیر نشان داده شده است:

شکل 8- راه‌رفتن تصادفی 2 در گراف شکل 6

یا یک پیاده‌روی تصادفی دیگر مطابق شکل زیر:

شکل 9- پیاده‌روی تصادفی 3 در گراف شکل 6

در پیاده‌روی‌های تصادفی ناشناس، ما پیاده‌روی‌های تصادفی را با ترتیب برچسب‌های گره نشان نمی‌دهیم، بلکه با دنباله شاخص‌های گام زمانی که گره بازدید می‌شود، مطابق شکل زیر نمایش می‌دهیم. از این رو، آنها را "پیاده روی تصادفی ناشناس" می‌نامند.

شکل 10: پیاده‌روی‌های تصادفی ناشناس – جایگزینی برچسب‌های گره با شاخص‌های گام زمانی.

چرا پیاده‌روی تصادفی ناشناس؟

باید تاکید شود که اگر یک گره قبلاً در طول پیاده‌روی تصادفی بازدید شده باشد و دوباره بازدید شود، شاخص جدیدی دریافت نمی‌کند اما همان مقدار شاخصی را که در شکل 6/7/8/9 در بالا نشان داده شده است، به آن اختصاص می‌دهد.

همانطور که ممکن است متوجه شوید، با پیاده‌روی‌های ناشناس، پیاده‌روی‌های تصادفی در یک زیرگراف اساساً با در نظر گرفتن شاخص‌ها یکسان هستند تا برچسب‌های گره که به مراحل بعدی ایجاد تعبیه گره کمک می‌کند (Random Walk1 و Random Walk2 نشان داده شده در شکل 6 و شکل 7). بنابراین، با استفاده از مفهوم پیاده‌روی‌های تصادفی ناشناس، می‌توان تشخیص داد که آیا پیاده‌روی قبلاً بازدید شده است یا خیر.

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

تعداد پیاده‌روی‌های تصادفی ناشناس ممکن در یک گراف:

تعداد پیاده‌روی‌های تصادفی ناشناس ممکن در طول یک گراف یا یک زیرگراف به طور تصاعدی در طول گراف افزایش می‌یابد. به عنوان مثال، برای طول 3، 5 راه رفتن تصادفی ممکن وجود دارد - با توجه به اینکه هیچ محدودیتی مانند شکل زیر وجود ندارد.

5 پیاده‌روی تصادفی ممکن به طول 3 عبارتند از:

W1 = 111 - در اینجا شما 3 بار از همان گره شروع می‌کنید

W2 = 112 – در اینجا شما در مرحله اول و دوم در همان گره می‌مانید و سپس به گره دوم می‌روید.

W3 = 121 - در اینجا شما از اولین گره به گره دوم می‌روید و سپس به گره اول باز می‌گردید.

به طور مشابه، ما پیاده‌روی تصادفی را داریم:

W4 = 122

و

W5 = 123

تعداد پیاده‌روی‌های تصادفی ممکن به صورت تصاعدی با طول افزایش می‌یابد و این در شکل زیر مشخص شده است:

شکل 11: تعداد پیاده‌روی‌های تصادفی ممکن بسته به طول گراف.

5. چگونه گراف‌ها را از طریق پیاده‌روی تصادفی به طول l تعبیه کنیم؟

برای شبیه‌سازی پیاده‌روی‌های تصادفی به طول l، ایده این است که پیاده‌روی‌های تصادفی طول l را شبیه‌سازی کنیم و گراف را به‌عنوان توزیع احتمال روی این پیاده‌روی‌ها نشان دهیم.

از آنجایی که تعداد پیاده‌روی‌های تصادفی به‌طور تصاعدی با افزایش طول گراف افزایش می‌یابد، همانطور که در بخش قبل مورد بحث قرار گرفت و در شکل 10 نشان داده شد، لازم است در مورد تعداد پیاده‌روی‌های تصادفی که باید نمونه‌برداری شوند تا زمینه را به تصویر بکشیم، ایده‌ای داشته باشیم. گراف را طوری ترسیم کنید که خطا قابل چشم پوشی باشد.

این مقاله ایده‌ای از چند پیاده‌روی تصادفی “m” را ارائه می‌دهد، به طوری که تخمین و احتمال وقوع دقیق باشد. این مقاله بیان می‌کند که می‌توان دقت را با 2 پارامتر تعیین کرد: ε و δ، جایی که می‌گوییم می‌خواهیم توزیع احتمالات پیاده‌روی‌های تصادفی خطای بیش‌تر از ε با احتمال کمتر از δ نداشته باشد.

معادله حاصل برای تعداد کل پیاده‌روی‌های تصادفی به صورت زیر بدست می‌آید:

معادله تعداد کل پیاده‌روی‌های تصادفی “m” مورد نیاز برای نمونه‌برداری از بافت یک گراف با پیاده‌روی‌های تصادفی “η”.

که:

η = تعداد کل مسیرهای تصادفی ناشناس به طول l

به عنوان مثال،

η = 877 پیاده‌روی تصادفی ناشناس به طول l = 7 وجود دارد. اگر تنظیم کنیم، ε = 0.1 و δ = 0.01 است.

از موارد فوق، m = 122500 پیاده‌روی تصادفی ایجاد می‌کنیم تا به احتمال خطای کمتر از 0.01 برسیم.

همانطور که مشاهده می‌شود، هنگامی که یک پیاده‌روی تصادفی در قالب شاخص‌ها بیان می‌شود، می‌توان تشخیص داد که آیا زمینه آن زیرگراف قبلاً در نظر گرفته شده است یا خیر.

پیاده‌روی ناشناس بازنمایی در سطح بالا از همه احتمالات پیاده‌روی تصادفی است که از گره u شروع می‌شوند. با جمع کردن احتمالات در تمام رئوس در یک گراف و نرمال کردن آنها با تعداد کل گره‌ها، احتمال انتخاب پیاده‌روی ناشناس در گراف G را به دست می‌آوریم.

6. یادگیری تعبیه پیاده‌روی

ایده پشت پیاده‌روی‌های تصادفی را می‌توان با یادگیری تعبیه‌های پیاده‌روی بیشتر تقویت کرد. یعنی:

۱. تعبیه‌های کل پیاده‌روی را بیاموزید.

۲. به علاوه تعبیه‌های کل گراف را یاد بگیرید

تعبیه‌ها در کل گراف مطابق با تعبیه به‌دست‌آمده به عنوان الحاق همه پیاده‌روی‌های تصادفی از هر گره گراف است که زمینه کلی گراف را می‌سازد.

بنابراین، تعداد کل تعبیه‌های پیاده‌روی که باید آموخته شوند، تعداد کل پیاده‌روی‌های ناشناس به اضافه 1 خواهد بود - یکی اضافی برای تعبیه گراف.

چگونه پیاده‌روی‌ها را تعبیه کنیم؟

این کار به روشی بسیار شبیه به آنچه برای Node2Vec انجام شد انجام می‌شود – در اینجا ما می‌خواهیم راه‌ها را به جای گره‌ها تعبیه کنیم.

به عنوان مثال، با شروع از گره 1 در گراف، ما نمونه پیاده‌روی تصادفی را مطابق شکل زیر داریم:

شکل 12: به صورت تصادفی از یک گراف عبور می‌کند

ایده این است که یاد بگیریم پیاده‌روهایی را پیش‌بینی کنیم که همزمان در پنجره‌ای با اندازه Δ اتفاق می‌افتند که در آن از راه‌های تصادفی یک گره مشخص نمونه‌برداری می‌کنیم. این دوباره همان چیزی است که ما کلمات متنی را در یک جمله در word2vec پیش‌بینی می‌کنیم و تعبیهها را به عنوان وزن در لایه پنهان ایجاد می‌کنیم.

تابع هدف همان است که در مدل skip-gram در Word2Vec یا Node2Vec استفاده می‌شود همانطور که در اینجا بحث شد.

بدین ترتیب:

ما مسیرهای تصادفی مختلف “T” را از “u” هر کدام از طول “I” اجرا خواهیم کرد.

·         یادگیری که پیاده‌روی‌هایی را که همزمان در پنجره با اندازه Δ اتفاق می‌افتد، پیش‌بینی کنید، همانطور که در اینجا بحث شد، کلمات یا گره‌ها را در پنجره اندازه Δ در Word2Vec یا Node2Vex پیش‌بینی می‌کردیم.

·         ما باید z_i تعبیه شده یک پیادهروی ناشناس  w_i را تخمین بزنیم و احتمال وقوع آن را همانطور که در معادله زیر نشان داده شده است به حداکثر برسانیم:

·         ما باید تعبیه گراف را پس از بهینه‌سازی همانطور که در گراف کلی معماری زیر نشان داده شده است بدست آوریم:

شکل 13: معماری کلی برای یادگیری از طریق تعبیه پیاده‌روی

فرمولبندی تعبیه گره‌ها در گراف‌ها: الگوریتم Node2Vec

1-مقدمه:

این ادامه مجموعه مقالات من در زمینه گراف‌ها و ششمین مقاله از این مجموعه است. این مقاله در مورد فرمول‌بندی تعبیه گره‌ها در گراف‌ها صحبت می‌کند و به پنج بخش اصلی تقسیم می‌شود:

·         در ابتدا، ما در مورد انگیزه بحث می‌کنیم - چرا ما به ترسیم ساختارهای گراف در تعبیه‌ها اهمیت می‌دهیم. بخشی از این بخش ممکن است تکرار محتوای مقاله قبلی من در مورد درک تعبیه گره‌ها در گراف‌ها باشد، اما من احساس کردم که برای حفظ تداوم مجموعه و ایجاد زمینه کلی فرمول‌بندی تعبیه گره لازم است این کار را انجام دهم. این بخش 2 این مقاله را تشکیل می‌دهد.

·         در بخش دوم، ما در مورد مشکل صحبت می‌کنیم: چگونه مسئله را تعریف کنیم و "زمینه" یک گره و هدف کلی چیست. این بخش 3 را تشکیل می‌دهد.

·         در بخش سوم این مقاله، من در مورد رویکرد Word2vec برای تولید تعبیه کلمات صحبت کرده‌ام. من احساس می‌کنم که این بسیار مهم است زیرا الگوریتم Node2Vec برای فرمول‌بندی تعبیه‌های گره بر پایه موفقیت‌آمیز الگوریتم Word2Vec در پردازش زبان طبیعی (بخش 4) بنا شده است.

·         بخش چهارم در مورد الگوریتم Node2Vec و مهمتر از مفهوم پیاده‌روی تصادفی صحبت می‌کند که از زنجیره‌های مارکوف مرتبه دوم برای ایجاد زمینه هر گره استفاده می‌کند. شباهت Node2Vec با Word2Vec در این قسمت کاملا واضح است (بخش 5).

با خواندن و درک بخش 4 و بخش 5، مشخص خواهد شد که Word2Vec و Node2Vec در رویکرد خود کاملاً سازگار هستند.

·         و در آخر، ما (قسمت 5 - بخش 6) به ریاضیات می‌رسیم تا رویکرد الگوریتم Node2Vec در نگاشت گره‌ها به فضای تعبیه شده روشن شود.

تعبیه گره‌ها در گراف‌ها

. مقدمه

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

بنابراین، سناریویی که تاکنون وجود داشت این بود که با در نظر گرفتن یک گراف ورودی، مهندس یادگیری ماشین ویژگی‌های ساختاری این گراف را ایجاد کرد تا بتوان یک الگوریتم یادگیری را برای پیش‌بینی اعمال کرد. سناریو در شکل زیر نشان داده شده است.

شکل 1: یادگیری ماشین گراف با مهندسی ویژگی (سطح گره، سطح پیوند، ویژگی‌های سطح گراف)

استخراج ویژگی‌های سطح گراف از گراف‌ها برای مدل‌های یادگیری ماشین

1. مقدمه

 خلاصه‌ای از وبلاگ اول، دوم و سوم:

این ادامه مجموعه وبلاگ‌های من در شبکه‌های گراف و چهارمین مقاله از این مجموعه است. این مجموعه با یک مقاله مقدماتی آغاز شد که تعاریف اصلی گره‌ها، لبه‌ها، گراف‌های جهت‌دار و غیرجهت‌دار را برجسته می‌کرد و نمونه‌هایی از مدل‌سازی روابط گرافیکی را برای موارد استفاده مختلف ارائه می‌کرد. این مقاله بر چالش‌های مرتبط با پردازش شبکه‌های گراف در یادگیری ماشینی و یادگیری عمیق تأکید کرد که بر پیچیدگی در مقایسه با پردازش تصویر یا متن (نسبتاً ساده‌تر) تأکید کرد.

مقاله دوم به استخراج ویژگی‌های سطح گره از گراف‌ها پرداخت تا این ویژگی‌ها بتوانند به یک مدل یادگیری ماشینی مانند: ماشین بردار پشتیبانی یا جنگل‌های تصادفی یا رگرسیون لجستیک وارد شوند. با انجام این کار، مدل یادگیری ماشین با ویژگی‌هایی غنی می‌شود که توپولوژی گراف را در کنار ویژگی‌های سطح ویژگی توصیف می‌کند. این با بحث مفصلی در مورد مفاهیم شامل: گره، مرکزیت گره، ضریب خوشه‌بندی و گرافلت‌ها دنبال شد.

در حالی که درجه گره و مرکزیت گره‌های مختلف اندازه‌گیری می‌کند: مرکزیت ارزش ویژه، مرکزیت بین، مرکزیت نزدیکی ویژگی‌های مبتنی بر اهمیت هستند که می‌توانند در پیش‌بینی میزان اهمیت یا تأثیرگذاری گره‌ها در یک گراف استفاده شوند در حالی که ویژگی‌های مبتنی بر ساختار مانند ضریب خوشه‌بندی و بردار شمارش گرافلت توپولوژی گره و همسایگی آن را می‌گیرد.

شکل 1: خلاصه مقاله 2 - مفهوم درجه گره - نشان دهنده تعداد لبه‌هایی است که یک گره به آنها متصل است.