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

1. مقدمه

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

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

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

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

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

 

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

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

شکل 3: خلاصه مقاله 3 - ویژگی‌های مبتنی بر فاصله و ضریب جاکارد

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

این مقاله در مورد وظایف پیش‌بینی سطح گراف بحث می‌کند و به ویژگی‌های وظایف پیش‌بینی سطح گراف می‌پردازد که می‌توانند به یک مدل یادگیری ماشینی وارد شوند. این مقاله در مورد هسته‌های گراف صحبت می‌کند که به ما امکان می‌دهد شباهت بین گراف‌ها را اندازه‌گیری کنیم. در مورد هسته گرافلت و هسته Weisfeiler-Lehman به ترتیب در بخش‌های 5 و 6 بحث می‌کنیم. هسته Weisfeiler-Lehman که ممکن است به عنوان یک مورد خاص از شبکه‌های عصبی کانولوشن گراف همانطور که در بخش 8 توضیح داده شده است در نظر گرفته شود، از اهمیت ویژه‌ای برخوردار است. روابط در یک گراف از همسایه‌ها به همسایه‌ها و غیره شروع می‌شود. حاصل ضرب نقطه‌ای بردارهای مشخصه حاصل از دو گراف، میزان شباهت بین دو گراف را نشان می‌دهد.

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

2. ویژگی‌های سطح گراف:

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

به عنوان مثال، با توجه به شبکه نشان داده شده در زیر،

شکل 4: یک شبکه نمونه.

با نگاهی به گراف بالا، می‌توان ساختار گراف فوق را به صورت زیر در نظر گرفت:

·         دارای دو قسمت سست به هم متصل است.

·         لبه‌های کمی بین گره‌ها در هر قسمت وجود دارد.

·         تنها یک لبه وجود دارد که این دو قسمت را به هم متصل می‌کند.

در مرحله بعد، سوال این است که چگونه یک توصیف ویژگی ایجاد می‌کنیم که به ما امکان می‌دهد کل ساختار گراف را همانطور که در بالا توضیح داده شد مشخص کنیم؟

3. روش‌های هسته

این کار با استفاده از روش‌های هسته انجام می‌شود – روش‌های هسته به طور گسترده در یادگیری ماشین سنتی در پیش‌بینی سطح گراف استفاده می‌شوند. ایده طراحی کرنل به جای بردار ویژگی است. بیایید بفهمیم "هسته (کرنل)" چیست.

3.1 مقدمه‌ای بر هسته‌ها:

 هسته بین دو گراف G و G’ یک مقدار حقیقی را برمی‌گرداند: K(G, G') εR معیار شباهت بین دو گراف است - به عبارت دیگر معیار شباهت بین نقاط داده است.

ماتریس هسته:

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

تفسیر فیزیکی یک ماتریس نیمه قطعی مثبت

مرجع:

https://math.stackexchange.com/questions/9758/intuitive-explanation-of-a-positive-semidefinite-matrix

یک تعریف شهودی به شرح زیر است. هر بردار را با یک ماتریس نیمه معین مثبت ضرب کنید. زاویه بین بردار اصلی و بردار حاصل همیشه کمتر یا مساوی π /2 خواهد بود. این مشابه کاری است که یک عدد مثبت با یک متغیر واقعی انجام می‌دهد. آن را ضرب کنید و فقط عدد را افزایش یا منقبض می‌کند اما هرگز آن را در مورد مبدا منعکس نمی‌کند.

تفسیر مشابهی ممکن است با توجه به شباهت بین گراف‌ها ترسیم شود - ماتریس هسته همیشه یک شباهت بین 2 گراف را تا زمانی که شباهت وجود داشته باشد مرتبط می‌کند.

ویژگی مهم هسته:

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

یعنی یک هسته بین دو گراف:

معادله: هسته بین دو گراف به عنوان حاصل ضرب نقطه بازنمایی ویژگی مربوطه آنها

φ(G) و φ(G’) بردارهایی هستند که بردارهای مشخصه هستند و مقدار هسته حاصل ضرب نقطه‌ای بازنمایی دو بردار دو گراف است.

لازم به ذکر است که بازنمایی ویژگی φ لازم نیست به صراحت برای محاسبه مقدار هسته ایجاد شود. هنگامی که هسته تعریف شد، می‌توان از مدل‌های یادگیری ماشین مانند Kernel SVM برای پیش‌بینی استفاده کرد.

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

·         روش گرافلت

·         هسته ویسفایلر-لمان

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

·         هسته پیاده‌روی تصادفی

·         هسته گراف کوتاه‌ترین مسیر

4. ایده‌های کلیدی پشت هسته‌ها

4.1 کیسه بازنمایی گره‌ها از گراف‌ها

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

شکل 5: بازنمایی کیسه کلمات (BoW) از متن در یک سند

به همین ترتیب، یک بسط ساده برای ایده در یک گراف این است که گره‌ها را به عنوان کلمات در نظر بگیریم - یعنی همانطور که فراوانی کلمات را در اسناد ثبت می‌کنیم، می‌توانیم تعداد گره‌ها را نیز در گراف‌ها ثبت کنیم.

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

شکل 6: نمایش کیسه گره‌ها از گراف‌ها (این دقیق نیست زیرا اگرچه 2 گراف تعداد گره‌های یکسانی دارند، اما متفاوت هستند)

هسته 4.2 درجه - بر اساس درجه گره (کیف درجه گره)

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

شکل 7: گراف به صورت کیف گره نشان داده شده است

برای گراف بالا می‌توان گفت:

·         ما یک گره از درجه 1 داریم

·         ما 3 گره درجه 2 داریم

·         ما 0 گره درجه 3 داریم

و برای گراف در شکل زیر،

شکل ۸: گراف به عنوان درجه کیسه گره نشان داده شده است

می‌توانستیم بگوییم:

·         ما 0 گره درجه 1 داریم

·         2 گره از درجه 2

·         2 گره از درجه 3

بنابراین ما بازنمایی ویژگی‌های مختلف گراف‌های مختلف را به دست خواهیم آورد که به ما امکان می‌دهد بین گراف‌های مختلف تمایز قائل شویم که به واقعیت نزدیک‌تر از بازنمایی گراف‌ها به عنوان Bag of Nodes مانند شکل 6 است.

در این مرحله باید تاکید کرد که هم در هسته گرافلت و هم در هسته Weisfeiler-Lehman مفهوم Bag of (X) پیچیده‌تر از Node Degree است. اجازه دهید ابتدا در مورد هسته گرافلت در بخش بعدی بحث کنیم.

5. هسته گرافلت

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

·         گره‌ها در گرافلت‌ها نیازی به اتصال ندارند.

·         گرافلت‌ها روت نشده‌اند.

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

مثال:

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

سایز k

برای k = 3 (یعنی تعداد گره‌ها 3 باشد)، 4 گراف وجود دارد که در شکل زیر نشان داده شده است:

شکل 9: گرافلت برای k= 3

برای k= 4، 11 گرافل از یک گراف کاملاً متصل به یک گراف با 4 گره بدون اتصال وجود دارد که در شکل زیر نشان داده شده است:

شکل 10: گرافلت برای k=4

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

بنابراین، با توجه به 2 گراف G و G’، می‌توانیم هسته گرافلت را به صورت زیر تعریف کنیم:

این حاصل ضرب نقطه‌ای f_g و f_g’ است که بردار شمارش گرافیت G و G را نشان می‌دهد.

محدودیت هسته گرافلت

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

بنابراین، سؤال این است که چگونه یک هسته گرافلت کارآمدتر را تعریف کنیم - هسته Weisfeler Lehman به آن دست می‌یابد و این را در بخش بعدی انجام می‌دهد.

6. هسته گراف ویزفایلر-لمن:

آزمون ویزفایلر-لمن چیست؟

آزمون ویزفایلر لمن آزمونی برای هم ریختی گراف است. تصمیم‌گیری در مورد اینکه آیا 2 گراف از نظر ساختاری یکسان هستند یا هم شکل یک مسئله کلاسیک است. یکی ممکن است گراف‌های مولکولی داشته باشد که در شکل زیر نشان داده شده است و ممکن است بخواهید تعیین کنید که آیا گراف‌ها هم شکل هستند یا خیر.

شکل 11: گراف‌های مولکولی - آیا از نظر ساختاری مشابه/ایزومورف هستند؟

بنابراین، طبق تعریف: یک هم ریختی از یک گراف G به یک گراف H یک نگاشت یک به یک از رئوس گراف اول به رئوس گراف دوم است که مجاورت و عدم مجاورت را حفظ می‌کند. برای مثال، می‌توان از طریق الگوریتم/آزمون ویزفایلر لیمان (همانطور که در زیر بحث شد) ثابت کرد که گراف‌ها هم‌شکل هستند، اگرچه به دلیل جایگشت‌های متفاوت برچسب‌ها متفاوت به نظر می‌رسند.

شکل 12: ایزومورفیسم بین دو گراف

ایده هسته ویزفایلر لمن این است که یک توصیفگر ویژگی گراف کارآمد fi (G) طراحی کنیم که در آن هدف استفاده از ساختار همسایگی برای غنی‌سازی مکرر واژگان گره است.

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

الگوریتم ویزفایلر لمن الگوریتم پالایش رنگ:

۱. ایده این است که به ما یک گراف G با مجموعه‌ای از گره‌های “v” داده شده است - ما یک رنگ اولیه C0(v) را به هر گره v گراف اختصاص می‌دهیم.

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

این را می‌توان به صورت زیر فهمید:

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

معادله رنگ گره v در یک مرحله زمانی

پس از K مرحله اصلاح رنگ c^(k) v، ساختار گراف را در سطح اصلاح K-hop خلاصه می‌کند.

 اجازه دهید این را از طریق مثال زیر درک کنیم.

7. نمونه‌ای از الگوریتم ویزفایلر لمن اصلاح رنگ بین دو گراف

الف) 2 گراف را مطابق شکل زیر در نظر بگیرید که ساختار مشابهی دارند. همانطور که در شکل نشان داده شده است به همه گره‌های هر دو گراف یک رنگ اختصاص می‌دهیم - رنگ با 1 نشان داده شده است.

شکل 13: مرحله اول الگوریتم پالایش رنگ - به همه گره‌های گراف‌ها یک رنگ اختصاص دهید.

ب) در مرحله بعد رنگ‌های همسایه را بر اساس همسایه گره‌ها مطابق شکل زیر تجمیع می‌کنیم:

شکل 14: مرحله بعدی الگوریتم پالایش رنگ - تجمیع رنگ‌ها از گره‌های همسایه

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

شکل 15: مرحله 3 الگوریتم پالایش رنگ - رنگ‌های جدید پس از اعمال تابع هش

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

شکل 16: رنگ‌آمیزی هش گراف (گره‌ها)

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

شکل 17: تجمیع، درهم‌سازی و رنگ‌های جدید در مرحله بعدی الگوریتم پالایش رنگ

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

شکل 18: بردار ویژگی گراف‌ها پس از تکرارهای “k” ویزفایلر-لمن

حاصل ضرب نقطه‌ای بردارهای ویژگی، مقدار هسته ویزفایلر لمن را به دست می‌دهد و اگر بردار ویژگی را نرمال کنیم، حاصل ضرب نقطه‌ای باید مقدار 1 را به دست آورد که نشان می‌دهد گراف‌های G و G’ مشابه هستند.

شکل 19: حاصلضرب نقطه‌ای بردارهای ویژگی پس از تکرارهای ویزفایلر-لمن

تفسیر فیزیکی محصول نقطه‌ای

محصول نقطه می‌تواند بین -بی نهایت تا + بی نهایت باشد. مقادیر بزرگ‌تر نشان‌دهنده شباهت بیشتر است (بر خلاف فاصله اقلیدسی که مقادیر بزرگ‌تر نشان‌دهنده شباهت کمتر است). طول یک بردار در سه بعد: v = (a, b, c) sqrt (a^2 + b^2 + c^2) است. اگر دو بردار را با تقسیم بر طول آن نرمال کنید، تابع حاصلضرب نقطه‌ای از 1- تا 1+ خواهد بود. مقدار 1 در این مورد نشان دهنده شباهت کامل است/بردارها دقیقاً یکسان هستند. مقدار -1 دقیقاً مخالف است. در مقایسه با استفاده از فاصله اقلیدسی، حاصلضرب نقطه برای تشابه به ویژه برای بردارهایی با ابعاد بالا مفید است.

8. هسته ویزفایلر لمن و شبکه‌های کانولوشنال گراف

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

شکل 20: الگوریتم ویزفایلر لمن

همانطور که در بخش 7 در بالا توضیح داده شد،

·         تکرارها را در ویزفایلر لمن تکرار می‌کنیم تا زمانی که یک رنگ ثابت به دست آوریم. این مشابه با لایه‌های GCN است.

·         تجمیع رنگ‌آمیزی در ویزفایلر لمن مشابه تجمیع ویژگی‌ها در GCN است.

·         تابع هش ویزفایلر لمن مشابه تابع فعال‌سازی در GCN است.

این مشابه است / تقریباً شبیه مراحل GCN است که در زیر نشان داده شده است:

معادله کالک بازنمایی در شبکه‌های عصبی