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

1. مقدمه

خلاصه ای از اولین و دومین وبلاگ من از این مجموعه:

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

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

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

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

شکل 2: خلاصه مقاله 2 - ضریب خوشه‌بندی

بررسی اجمالی این مقاله:

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

بخش 4 این مقاله در مورد ویژگی‌های مبتنی بر فاصله، ضرایب جاکارد و شاخص Adamic-Adar صحبت می‌کند که معیارهای همسایگی محلی بین یک جفت گره را تشکیل می‌دهند.

بخش‌های 2 و 3 بینشی از پیش‌بینی‌های سطح پیوند و فرمول‌بندی پیش‌بینی سطح پیوند در یک مدل یادگیری ماشین ارائه می‌کنند.

2. وظایف پیش‌بینی سطح پیوند: وظایف پیش‌بینی سطح پیوند چیست؟

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

شکل 3: وظایف پیش‌بینی سطح پیوند

اکنون کلید - برای برآورده کردن نیاز فوق - طراحی ویژگی‌های یک جفت گره است. در این مرحله، می‌توان فکر کرد که چرا به وظایف سطح گره (که در مقاله قسمت 2 این سری بحث شد) برگردیم و ویژگی‌های جفت گره‌ها را بر اساس ویژگی‌های گره‌های مجزا به هم پیوند ندهیم و یک مدل یادگیری ماشینی را که بازنمایی ویژگی آموزش دهیم. با این حال، این خیلی سودمند نخواهد بود زیرا رابطه بین گره‌ها به این صورت شکل گرفته نمی‌شود.

شکل 4: چگونه ویژگی‌ها را بین یک جفت گره طراحی کنیم؟

3. تدوین وظایف پیش‌بینی لینک برای آموزش

2 راه وجود دارد که می‌توان وظایف پیش‌بینی پیوند را فرموله کرد:

۱) پیوندهای تصادفی از دست رفته در شبکه: یکی از راه‌ها حذف مجموعه‌ای تصادفی از پیوندها و سپس پیش‌بینی مجدد آنها با استفاده از الگوریتم یادگیری ماشین است. شکل 3 را در زیر ببینید.

۲) پیوندها در طول زمان: نوع دیگر فرمولاسیون جایی است که شما پیوندها را در طول زمان پیش‌بینی می‌کنید. که، اگر یک شبکه گراف مانند یک شبکه استنادی، شبکه اجتماعی یا یک شبکه همکاری داشته باشیم، می‌توانیم به گراف بین t0 و t0’ نگاه کنیم و سپس بر اساس یال‌ها و ساختار گراف تا t0 می‌توانیم خروجی داشته باشیم. یک لیست رتبه‌بندی شده “L”از پیوندهایی که در آینده بین زمان t1 و t1 رخ می‌دهد.

شکل 5: حذف تصادفی پیوندها از شبکه برای آموزش ML

این نوع فرمول برای شبکه‌هایی که در طول زمان تکامل می‌یابند خوب است، در حالی که فرمول‌بندی لینک‌هایی که به‌طور تصادفی از دست می‌روند (همانطور که در بالا توضیح داده شد) برای شبکه‌های استاتیک مانند شبکه پروتئین-پروتئین مفیدتر است.

بنابراین، اکنون با در نظر گرفتن دو فرمول بالا، اجازه دهید اکنون بر روی ارائه توضیحات ویژگی بین جفت گره‌های داده شده تمرکز کنیم.

روش پیش‌بینی لینک:

بنابراین، با توجه به روش، برای هر جفت گره (مثلا x و y)، ما یک امتیاز را محاسبه می‌کنیم - امتیاز با c_bar (x,y) نشان داده می‌شود. به عنوان مثال، همسایه‌های مشترک x و y چه چیزی می‌تواند باشد.

و سپس همه جفت‌ها (x, y) را بر اساس امتیازهای کاهشی c_bar(x,y) مرتب می‌کنیم و سپس جفت‌های “m” را به‌عنوان پیوندهای جدیدی که قرار است در ظاهر شوند پیش‌بینی کنیم. شبکه سپس می‌توانیم ضرر را بر اساس پیوندهایی که واقعاً ظاهر شده‌اند یا نه، محاسبه کنیم.

4. چگونه ویژگی‌هایی را برای پیش‌بینی لینک طراحی کنیم؟

ویژگی‌های سطح پیوند

اکنون می‌خواهیم 3 روش مختلف را در مورد چگونگی ویژگی یا نحوه ایجاد توصیفی از رابطه بین دو گره در یک شبکه مرور کنیم. قصد داریم در مورد:

·         ویژگی‌های مبتنی بر فاصله

·         ویژگی‌های همپوشانی محله‌های محلی

·         ویژگی‌های همپوشانی همسایگی سراسری

شکل 6: طراحی ویژگی‌ها برای پیش‌بینی لینک.

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

4.1 ویژگی‌های مبتنی بر فاصله:

این ویژگی بسیار رایج و بسیار شهودی است. ما می‌توانیم در مورد کوتاه‌ترین فاصله مسیر بین دو گره فکر کنیم و آن را در مد مشخص کنیم. بنابراین، اگر گره‌های B و H را داشته باشیم و کوتاه‌ترین فاصله مسیر بین این دو گره 2 باشد یعنی SBH = 2 (Edge BD و Edge DH) همانطور که در شکل 7 زیر نشان داده شده است.

شکل 7: ویژگی مبتنی بر فاصله - کوتاه‌ترین طول مسیر بین گره‌های B و H = 2

به طور مشابه، فاصله بین B و E، A و B، B و G، B و F نیز برابر 2 است که در شکل 7 زیر نشان داده شده است.

شکل 8: ویژگی‌های مبتنی بر فاصله بین برخی از جفت گره‌های دیگر.

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

به عنوان مثال، SBH = 2 و گره‌های B و H دارای دو گره مشترک D و C هستند در حالی که B و E و A و B دارای یک چنین گره هستند - همانطور که در شکل 7/شکل 8 در بالا مشاهده شده است.

بنابراین ارتباط بین B و H قویتر از ارتباط بین (B و E) و (A و B) است زیرا بین B و E و A و B فقط یک مسیر و بین B و H دو مسیر وجود دارد.

4.2 همپوشانی محله محلی: ضریب جاکارد

این ما را به مبحث بعدی هدایت می‌کند که «همپوشانی همسایگی محلی» است - که قدرت اتصال را نشان می‌دهد که تعداد همسایگان مشترک بین یک جفت گره را می‌شمارد، یعنی همپوشانی همسایگی محلی تعداد گره‌های مشترک بین دو گره v1 و v2 را نشان می‌دهد.

از نظر ریاضی، برای شمارش همسایگان مشترک بین دو گره v1 و v2، تقاطع گره‌های v1 و v2 را می‌گیریم، یعنی تقاطع دو مجموعه.

همسایه‌های مشترک: بنابراین، همسایه‌های مشترک بین یک جفت گره، گره‌های مشترک بین دو گره را می‌گیرد.

شبکه زیر را در نظر بگیرید:

شکل 9: شبکه مثالی برای محاسبه همسایگان مشترک بین گره A و گره B

همسایگان مشترک:

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

ضریب جاکارد:

معادله: بیان ضریب جاکارد

Union = Neighbors of A + Neighbors of B

بنابراین،

ضریب جاکارد برای جفت گره A و B:

معادله: محاسبه ضریب جاکارد برای جفت گره (A,B)

4.3 همپوشانی محله‌های محلی: شاخص Adamic Adar:

 نوع دیگر معیار محله محلی «شاخص آدامیک آدار» است. این در عمل بسیار خوب عمل می‌کند و با نشان داده می‌شود:

معادله شاخص آدامیک آدار

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

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

مثال - برای همان شبکه شکل 9:

4.4 محدودیت همپوشانی همسایگان محلی:

مشکل همپوشانی همسایگان محلی eh این است که اگر دو گره یک گره مشترک نداشته باشند، متریک همیشه 0 برمی‌گرداند.

به عنوان مثال، اگر باید همپوشانی همسایگان محلی بین گره‌های A و E را همانطور که در شبکه زیر نشان داده شده است محاسبه کنیم:

شکل 10: همپوشانی همسایگی محلی جفت گره A و E = 0

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

4.5 محاسبه همپوشانی همسایگی سراسری: ضریب کاتز

در مرحله بعد، سوال این است که چگونه تعداد مسیرهای یک طول معین را بین 2 گره مختلف محاسبه کنیم - این می‌تواند به زیبایی با استفاده از توان‌های ماتریس مجاورت گراف محاسبه شود. یعنی: محاسبه تعداد مسیرهای بین دو گره به قدرت‌های محاسباتی ماتریس Graph Adjacency کاهش می‌یابد - یعنی ماتریس Graph Adjacency را گرفته و در خود ضرب می‌شود.

اثبات این موضوع در اینجا بحث نشده است.

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

·         Auv تعداد مسیرهای به طول 1 (همسایگی مستقیم) بین u و v را مشخص می‌کند.

·         Auv^2 تعداد مسیرهای به طول 2 (همسایه همسایه) بین u و v را مشخص می‌کند.

·         Auv^ l تعداد مسیرهای با طول l را مشخص می‌کند.

5. خلاصه - ویژگی‌های سطح لبه

بنابراین، برای ویژگی‌های مبتنی بر لبه 2 گره، موارد زیر را مورد بحث قرار داده‌ایم:

۱) ویژگی‌های مبتنی بر فاصله: این از کوتاه‌ترین مسیر بین گره‌ها استفاده می‌کند اما همپوشانی همسایگی را نشان نمی‌دهد.

۲) همپوشانی محله محلی: این از معیارهایی مانند ضریب جاکارد استفاده می‌کند که محاسبه می‌کند گره چند همسایه مشترک دارد.

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