فصل سیزدهم: گراف شبکه‌های عصبی

مقدمه

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

1. نمودار چیست؟

تعریف و انواع نمودارها

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

• انواع گراف:

  • گراف بدون جهت: یال‌ها بدون جهت هستند (مانند برخی روابط اجتماعی).

  • گراف جهت‌دار: یال‌ها دارای جهت هستند (مانند شبکه‌های استناد).

  • گراف ناهمگن: گره‌ها و یال‌ها می‌توانند از نوع‌های مختلف باشند (مثلاً گراف دانش).

  • گراف هندسی: گره‌ها مختصات فضایی دارند (مانند ابر نقاط سه‌بعدی).

مثال‌های دنیای واقعی

• شبکه‌های اجتماعی: افراد به‌عنوان گره و روابط اجتماعی به‌عنوان یال.

• مولکول‌ها: اتم‌ها گره و پیوندهای شیمیایی یال هستند.

• مدارهای الکتریکی: اجزای مدار به‌عنوان گره و اتصالات الکتریکی به‌عنوان یال.

2. نمایش نمودار

ماتریس‌های نمایش گراف

• ماتریس مجاورت:

  $$\mathbf{A} \in \{0,1\}^{N \times N}$$

  نشان‌دهنده وجود یا عدم وجود یال بین گره‌هاست.

• ماتریس ویژگی گره‌ها:

  $$\mathbf{X} \in \mathbb{R}^{N \times F}$$

  که در آن $F$ تعداد ویژگی‌های هر گره است.

• ماتریس ویژگی یال‌ها (در صورت وجود):

  $$\mathbf{E} \in \mathbb{R}^{M \times D}$$

  برای $M$ یال و $D$ ویژگی.

ویژگی‌های ماتریس مجاورت

• توان $L$ از ماتریس مجاورت:

  $$(\mathbf{A}^L)_{ij}$$

  تعداد مسیرهای طول $L$ بین گره $i$ و $j$ را نشان می‌دهد.

• جایگشت‌ناپذیری: نمایش باید نسبت به ترتیب گره‌ها ناوردا باشد، یعنی:

  $$\mathbf{A}’ = \mathbf{PAP}^{-1}, \quad \mathbf{X}’ = \mathbf{PX}$$

  که در آن $\mathbf{P}$ ماتریس جایگشت است.

3. شبکه‌های عصبی گراف (GNN)

معماری پایه

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

$$\mathbf{H}_{k+1} = \sigma\left( \beta_k \mathbf{1}^\top + \Omega_k \mathbf{H}_k (\mathbf{A} + \mathbf{I}) \right)$$

که در آن:

• $\mathbf{H}_k \in \mathbb{R}^{N \times d_k}$: ویژگی گره‌ها در لایه $k$

• $\Omega_k$: وزن‌های قابل یادگیری

• $\beta_k$: بایاس

• $\mathbf{A}$: ماتریس مجاورت

• $\mathbf{I}$: ماتریس همانی (برای افزودن گره به همسایگان خودش)

• $\sigma(\cdot)$: تابع فعال‌سازی

وظایف یادگیری

1. سطح گراف:

   $$\hat{y} = f(\mathcal{G})$$

   پیش‌بینی ویژگی کلی گراف (مثلاً سمّیت مولکول)

2. سطح گره:

   $$\hat{y}_i = f(\mathbf{h}_i)$$

   پیش‌بینی برچسب گره‌ها (مثلاً نوع نود)

3. پیش‌بینی یال:

   $$\hat{y}_{ij} = f(\mathbf{h}_i, \mathbf{h}_j)$$

   برای تخمین ارتباط دو گره

4. شبکه‌های کانولوشن گراف (GCN)

عملیات پایه GCN

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

• جمع ساده:

  $$\mathbf{h}_i^{(k+1)} = \sum_{j \in \mathcal{N}(i) \cup \{i\}} \mathbf{W} \mathbf{h}_j^{(k)}$$

• میانگین:

  $$\mathbf{h}_i^{(k+1)} = \frac{1}{|\mathcal{N}(i) \cup \{i\}|} \sum_{j \in \mathcal{N}(i) \cup \{i\}} \mathbf{W} \mathbf{h}_j^{(k)}$$

• حداکثر:

  $$\mathbf{h}_i^{(k+1)} = \max_{j \in \mathcal{N}(i) \cup \{i\}} \mathbf{W} \mathbf{h}_j^{(k)}$$

• توجه (Attention):

  $$\mathbf{h}_i^{(k+1)} = \sum_{j \in \mathcal{N}(i)} \alpha_{ij} \mathbf{W} \mathbf{h}_j^{(k)}, \quad \alpha_{ij} = \text{softmax}(e_{ij})$$

نرمال‌سازی GCN (Kipf & Welling)

فرمول نهایی برای یک لایه GCN:

$$\mathbf{H}^{(k+1)} = \sigma\left( \tilde{\mathbf{D}}^{-\frac{1}{2}} \tilde{\mathbf{A}} \tilde{\mathbf{D}}^{-\frac{1}{2}} \mathbf{H}^{(k)} \mathbf{W}^{(k)} \right)$$

که در آن:

• $\tilde{\mathbf{A}} = \mathbf{A} + \mathbf{I}$: اضافه کردن یال خودی

• $\tilde{\mathbf{D}}_{ii} = \sum_j \tilde{\mathbf{A}}_{ij}$: ماتریس درجه

5. مدل‌های القایی در برابر انتقالی

مدل القایی (Inductive)

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

$$f: \mathbf{X}, \mathbf{A} \longrightarrow \hat{Y}$$

مناسب برای گراف‌های دیده‌نشده (مثلاً مولکول‌های جدید).

مدل انتقالی (Transductive)

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

$$f: \mathcal{G}_{\text{train}} \longrightarrow \hat{Y}_{\text{test}}$$

مثال: شبکه استناد مقاله‌ها.

6. چالش‌های آموزش و بهینه‌سازی

نمونه‌گیری در گراف‌های بزرگ

• نمونه‌گیری همسایه‌ها:
  انتخاب تصادفی یا منظمی از همسایگان برای کاهش حافظه و زمان.

• پارتیشن‌بندی گراف:
  شکستن گراف به زیرگراف‌های کوچکتر برای پردازش دسته‌ای.

منظم‌سازی (Regularization)

• DropEdge:
  حذف تصادفی برخی یال‌ها در طول آموزش:

  $$\mathbf{A}_{\text{drop}} \sim \text{Bernoulli}(p)$$

• اتصالات باقیمانده (Residual Connections):
  کمک به یادگیری در شبکه‌های عمیق:

  $$\mathbf{H}^{(k+1)} = \text{GNN}(\mathbf{H}^{(k)}) + \mathbf{H}^{(k)}$$

7. گراف‌های یال (Edge Graphs)

تعریف

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

کاربرد

• پیش‌بینی ویژگی یا وجود یال‌های جدید

• افزایش بیان‌پذیری مدل در وظایف ارتباطی

8. جمع‌بندی

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

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