شبکه‌های کانولوشنی گراف (Graph Convolutional Networks)

در این مطلب، دربارهٔ شبکه‌های کانولوشنی گراف (GCNs) صحبت خواهیم کرد که هدفشان تعمیم عملیات کانولوشن به دامنهٔ گراف است. از آن‌جایی که شبکه‌های عصبی کانولوشنی (CNNs) در حوزهٔ یادگیری عمیق موفقیت چشمگیری داشته‌اند، تعریف عملیات کانولوشن برای گراف‌ها نیز کاملاً طبیعی و منطقی به‌نظر می‌رسد. پیشرفت‌ها در این زمینه معمولاً به دو دستهٔ کلی تقسیم می‌شوند: رویکردهای طیفی (spectral) و رویکردهای مکانی (spatial). از آن‌جایی که در هر کدام از این دو دسته مدل‌های متنوع زیادی وجود دارد، در این مطلب فقط به معرفی چند مدل کلاسیک و مهم بسنده می‌کنیم.

قضیه نقطه ثابت باناخ

قضیه (باناخ، ۱۹۲۲):
فرض کنید \(X,d\) یک فضای متری کامل باشد، و $\backslash (T:X\; \backslash rightarrow\; X\backslash )$ یک نگاشت انقباضی باشد، یعنی: \[ \exists\, c \in (0, 1) \quad \text{such that for all } x, y \in X:\quad d(T(x), T(y)) \leq c \cdot d(x, y) \]

شبکه‌های عصبی گراف پایه (Vanilla GNNs)

در این مطلب، با مدل پایه‌ای شبکه‌های عصبی گراف یا Vanilla GNN آشنا می‌شویم. این مدل که نخستین‌بار در سال 2009 توسط Scarselli و همکارانش معرفی شد، یکی از اولین تلاش‌ها برای تعمیم شبکه‌های عصبی به داده‌هایی با ساختار گرافی است. در ادامه، علاوه بر معرفی این مدل، به محدودیت‌های آن نیز از نظر «توانایی نمایش» و «کارایی آموزشی» خواهیم پرداخت.

مقدمه‌ای بر احتمالات (ریاضیات پیش‌نیاز GNN)

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

مقدمه‌ای بر جبر خطی (ریاضیات پیش‌نیاز GNN)

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

شبکه‌های عصبی گراف (مقدمه‌ای بر روابط)

شبکه‌های عصبی گرافی (GNN) از جمله مدل‌های قدرتمند یادگیری عمیق هستند که برای تحلیل داده‌هایی با ساختار گراف استفاده می‌شوند. در این ساختار، داده‌ها به صورت یک گراف \(G=(V,E)\) تعریف می‌شوند که در آن \(V\) مجموعه‌ای از گره‌ها و \(E\) مجموعه‌ای از یال‌ها یا ارتباطات میان گره‌هاست. هر گره \(v \in V\) با یک بردار ویژگی \(x_v \in \mathbb{R}^d\) مشخص می‌شود.

شبکه‌های عصبی گرافی عموماً از طریق یک مکانیزم انتشار پیام (Message Passing) کار می‌کنند که می‌توان آن را به صورت ریاضی به این شکل بیان کرد:

\[\mathbf{h}_v^{(k)} = \sigma\left(\mathbf{W}^{(k)} \sum_{u \in \mathcal{N}(v)} \frac{1}{\sqrt{|\mathcal{N}(v)||\mathcal{N}(u)|}} \mathbf{h}_u^{(k-1)} + \mathbf{b}^{(k)}\right)\]

که در آن، \(h_v^{(k)}\) نمایش برداری گره \(v\) در لایه \(k\)، \(W^{(k)}\) ماتریس وزن و \(b^{(k)}\) بردار بایاس در لایه \(k\) هستند. همچنین، \(\mathcal{N}(v)\) مجموعه همسایگان گره \(v\) را نشان می‌دهد و \(\sigma(\cdot)\) تابع فعال‌سازی (مانند ReLU یا tanh) است. بردار نمایش اولیه هر گره نیز عموماً ویژگی‌های اولیه گره است، یعنی:

\[\mathbf{h}_v^{(0)} = \mathbf{x}_v \]

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

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

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

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