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

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

مقدمه

مفهوم GNN (شبکه‌های عصبی گراف) نخستین‌بار توسط Gori و همکاران (2005) و سپس توسط Scarselli و همکاران (2004، 2009) پیشنهاد شد. برای ساده‌سازی، در اینجا به مدل معرفی‌شده در Scarselli et al. (2009) می‌پردازیم که هدف آن، گسترش شبکه‌های عصبی موجود برای پردازش داده‌هایی با ساختار گرافی است.در یک گراف، رأس (node) به‌صورت طبیعی توسط ویژگی‌های خودش و همچنین گره‌های مرتبط با آن تعریف می‌شود. هدف GNN، یادگیری بردار نهفته‌ی حالت (state embedding) برای هر گره است که با \(h_v \in \mathbb{R}^s\) نشان داده می‌شود. این بردار، اطلاعات مربوط به همسایگی گره را رمزگذاری (کدگذاری) کرده و برای تولید خروجی \(o_v\)​ (مانند توزیع برچسب پیش‌بینی‌شده برای گره) استفاده می‌شود. در مقالهٔ Scarselli et al. (2009)، یک گراف نمونه در شکل بالا نشان داده شده است. مدل پایهٔ GNN یا Vanilla GNN با گراف‌های همگن و بی‌جهت کار می‌کند؛ به‌طوری‌که هر گره \(v\) دارای بردار ویژگی \(x_v\)​ است، و هر یال نیز ممکن است دارای ویژگی‌هایی باشد. در این مقاله، از نمادهای \(co[v]\) و \(ne[v]\) برای نمایش مجموعهٔ یال‌ها و همسایگان گره \(v\) استفاده شده است. برای گراف‌های پیچیده‌تری مانند گراف‌های ناهمگن (heterogeneous)، نسخه‌های پیشرفته‌تری از GNN بعدا بررسی خواهند شد.

مدل

با در اختیار داشتن ویژگی‌های ورودی گره‌ها و یال‌ها، در ادامه توضیح خواهیم داد که مدل چگونه بردار نهفتهٔ گره \(h_v\)​ و بردار خروجی \(o_v\)​ را به‌دست می‌آورد. برای به‌روزرسانی وضعیت (state) گره بر اساس همسایگی ورودی، تابع پارامتری \(f\) به نام تابع انتقال محلی (local transition function) تعریف شده است که میان تمام گره‌ها مشترک می‌باشد. برای تولید خروجی گره نیز، از یک تابع پارامتری دیگر به نام \(g\) استفاده می‌شود که به آن تابع خروجی محلی (local output function) گفته می‌شود.

بنابراین، بردار وضعیت نهفتهٔ گره \(h_v\)​ و خروجی \(o_v\)​ به صورت زیر تعریف می‌شوند:

\begin{equation}
\mathbf{h}_v = f(\mathbf{x}_v, \mathbf{x}_{co[v]}, \mathbf{h}_{ne[v]}, \mathbf{x}_{ne[v]})
\end{equation}

\begin{equation}
\mathbf{o}_v = g(\mathbf{h}_v, \mathbf{x}_v)
\end{equation}

که در این معادلات:

\( \mathbf{x}_v \): ویژگی ورودی گره \( v \)

\( \mathbf{x}_{co[v]} \): ویژگی‌های یال‌های متصل به گره \( v \)

\( \mathbf{h}_{ne[v]} \): وضعیت نهفتهٔ گره‌های همسایه

\( \mathbf{x}_{ne[v]} \): ویژگی‌های گره‌های همسایه

 

در مثال مربوط به گره \( l_1 \) (در شکل بالایی):

\( \mathbf{x}_1 \): ویژگی گره \( l_1 \)

\( co[l_1] \): شامل یال‌های \((l_1, l_4), (l_1, l_6), (l_1, l_2), (l_3, l_1)\)

\( ne[l_1] \): شامل گره‌های \( l_2, l_3, l_4, l_6 \)

 

فرض کنید ماتریس‌های \(H\)، \(O\)، \(X\) و \(X_N\) به‌ترتیب با کنار هم قرار دادن تمام وضعیت‌ها (states)، خروجی‌ها (outputs)، ویژگی‌ها (features) و ویژگی‌های گره‌ها ساخته شده‌اند.

در این صورت، فرم فشرده‌ی مدل به صورت زیر خواهد بود:

\begin{equation}
\mathbf{H} = F(\mathbf{H}, \mathbf{X})
\end{equation}

\begin{equation}
\mathbf{O} = G(\mathbf{H}, \mathbf{X}_N)
\end{equation}

که در آن:

• $\backslash (F\backslash )$تابع انتقال سراسری (global transition function) است

• و \(G\) تابع خروجی سراسری (global output function) می‌باشد.

این توابع، نسخه‌های پشته‌شده‌ی توابع محلی \(f\) و $\backslash (g\backslash )$ هستند که برای تمام گره‌های گراف اعمال می‌شوند.

مقدار \(H\) نقطه‌ی ثابت معادلهٔ اول است و در صورتی که \(F\) یک نگاشت انقباضی (contraction map) باشد، به‌صورت یکتا تعریف می‌شود.

با توجه به قضیه نقطه ثابت باناخ (Banach's fixed point theorem) [Khamsi and Kirk, 2011]، GNN از یک طرح تکراری کلاسیک برای محاسبه‌ی وضعیت گره‌ها استفاده می‌کند:
\begin{equation}
\mathbf{H}^{t+1} = F(\mathbf{H}^t, \mathbf{X})
\end{equation}

که در آن \(H^t\) بیانگر مقدار ماتریس وضعیت در تکرار \(t\)-ام است.

---

📘 تعریف ریاضی نقطهٔ ثابت:

اگر \(H^*\) طوری باشد که:\[H^*=F(H^*,X)\]آن‌وقت می‌گوییم \(H^*\) یک نقطهٔ ثابت برای \(F\) است.

🧩 چرا نقطهٔ ثابت مهم است؟

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

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

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

---

همچنین توجه شود که محاسبات تعریف‌شده در توابع $\backslash (f\backslash )$ و $\backslash (g\backslash )$ را می‌توان به‌صورت شبکه‌های عصبی پیش‌خور (FNNs) تعبیر کرد.

پس از معرفی چارچوب GNN، سوال بعدی این است که چگونه می‌توان پارامترهای تابع انتقال محلی \(f\) و تابع خروجی محلی $\backslash (g\backslash )$ را آموخت.
با در اختیار داشتن اطلاعات هدف ($\backslash (t\_v\backslash )$ برای هر گره خاص) به‌منظور یادگیری نظارت‌شده، تابع خطا (Loss) به صورت زیر تعریف می‌شود:

\begin{equation}
\text{loss} = \sum_{i=1}^{p} (t_i - o_i)
\end{equation}

که در آن $\backslash (p\backslash )$ تعداد گره‌هایی است که برچسب نظارتی دارند.
الگوریتم یادگیری بر پایهٔ استراتژی گرادیان نزولی (gradient descent) بنا شده و شامل مراحل زیر است:

• وضعیت‌های گره \(h_v^t\)​ به‌صورت تکراری تا زمان \(T\) به‌روزرسانی می‌شوند.
  سپس یک تقریب از نقطهٔ ثابت به دست می‌آید: \(H(T) \approx H\)

• گرادیان وزن‌ها $\backslash (W\backslash )$ از روی مقدار loss محاسبه می‌شود.

• وزن‌ها $\backslash (W\backslash )$ طبق گرادیان به‌دست‌آمده در مرحله قبل، به‌روزرسانی می‌شوند.

پس از اجرای الگوریتم، مدلی خواهیم داشت که برای یک وظیفهٔ خاص (نظارت‌شده یا نیمه‌نظارتی) آموزش دیده است.
همچنین وضعیت‌های پنهان گره‌ها نیز به دست آمده‌اند.
مدل پایهٔ GNN (Vanilla GNN) راهکار مؤثری برای مدل‌سازی داده‌های گرافی ارائه می‌دهد و نخستین گام در جهت ادغام شبکه‌های عصبی در حوزهٔ گراف به شمار می‌رود.

محدودیت‌ها

  اگرچه نتایج تجربی نشان داده‌اند که GNN معماری قدرتمندی برای مدل‌سازی داده‌های ساختاریافته است، اما همچنان محدودیت‌هایی برای نسخهٔ پایهٔ GNN (Vanilla GNN) وجود دارد: 🔹 اول، به‌روزرسانی وضعیت‌های پنهان گره‌ها به‌صورت تکراری تا رسیدن به نقطهٔ ثابت (Fixed Point) از نظر محاسباتی پُرهزینه است.

مدل نیاز دارد که تا زمان $TT$ گام محاسباتی انجام دهد تا به نقطهٔ ثابت نزدیک شود.
اگر از فرض رسیدن به نقطهٔ ثابت صرف‌نظر کنیم، می‌توانیم یک GNN چندلایه طراحی کنیم که نمایشی پایدار از گره و همسایگی‌اش ارائه دهد.

🔹 دوم، مدل پایهٔ GNN در تمام تکرارها از پارامترهای ثابتی استفاده می‌کند؛ درحالی‌که اغلب شبکه‌های عصبی مدرن در هر لایه، پارامترهای متفاوتی به کار می‌برند و این امر نوعی استخراج ویژگی سلسله‌مراتبی محسوب می‌شود.
علاوه بر آن، به‌روزرسانی وضعیت پنهان گره‌ها، فرایندی ترتیبی است که می‌تواند از هسته‌های RNN مانند GRU و LSTM بهره‌مند شود.

🔹 سوم، در برخی کاربردها، یال‌ها (edges) نیز دارای ویژگی‌های غنی و اطلاعاتی هستند که در مدل پایهٔ GNN نمی‌توان به‌خوبی آن‌ها را مدل کرد.
برای مثال، در گراف‌های دانش (Knowledge Graph)، یال‌ها بیانگر نوع رابطه‌اند و پیام‌رسانی در یال‌های مختلف باید متفاوت انجام شود.
همچنین یادگیری وضعیت پنهان یال‌ها خود یک چالش مهم به‌شمار می‌رود.

🔹 نهایتاً، اگر مقدار \(T\) بزرگ باشد، استفاده از نقطهٔ ثابت برای نمایش گره‌ها (به‌جای گراف‌ها) مناسب نخواهد بود.
چرا که در این حالت، نمایش گره‌ها در نقطهٔ ثابت بیش از حد یکنواخت شده و دیگر اطلاعات کافی برای تمایز میان گره‌ها فراهم نمی‌کند.

---

پیوست

در ریاضیات، به تابعی که خروجی‌های آن دو نقطه را به هم نزدیک‌تر از ورودی‌هایشان کند، نگاشت انقباضی (Contraction Mapping) گفته می‌شود. به‌عبارت‌دیگر، این تابع باعث "انقباض" فاصله میان نقاط می‌شود. تعریف ریاضی این مفهوم به صورت زیر است:

یک تابع \(\mathbb{F}: \mathbb{R}^n \rightarrow \mathbb{R}^n\) یک نگاشت انقباضی است، اگر برای هر دو نقطهٔ دلخواه $\backslash (x\backslash )$ و $\backslash (y\backslash )$ در فضای ورودی، داشته باشیم:\[ \| F(x) - F(y) \| \leq c \cdot \| x - y \| \quad \text{where } 0 < c < 1 \]این رابطه نشان می‌دهد که فاصلهٔ بین خروجی‌های تابع کمتر از فاصلهٔ ورودی‌هاست. به بیان شهودی، اگر دو نقطه را وارد تابع کنیم و ببینیم که تصاویر آن‌ها به هم نزدیک‌تر شده‌اند، آنگاه این تابع دارای خاصیت انقباضی است.

چرا این خاصیت مهم است؟ به‌دلیل قضیه نقطهٔ ثابت باناخ (Banach Fixed Point Theorem). این قضیه می‌گوید اگر تابعی یک نگاشت انقباضی باشد و فضای تعریف آن کامل باشد (مثل \(\mathbb{R}^n\))، آنگاه دو ویژگی مهم تضمین می‌شود:

1. این تابع دقیقاً یک نقطهٔ ثابت یکتا دارد؛ یعنی نقطه‌ای مانند \(x^*\) که در آن \(x^*=F(x^*\).

2. اگر از هر نقطهٔ دلخواه شروع کنیم و تابع را به‌صورت تکراری اعمال کنیم، این توالی به نقطهٔ ثابت همگرا می‌شود.

برای مثال، فرض کنید تابع \(F(x)=0.5x\) باشد. اگر از مقدار اولیه \(x=10\) شروع کنیم و تابع را تکرار کنیم:

• $\backslash (F(10)=5\backslash )$

• $\backslash (F(5)=2.5\backslash )$

• $\backslash (F(2.5)=1.25\backslash )$

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

در Vanilla GNN نیز از همین ایده استفاده شده است. مدل در هر مرحله وضعیت گره‌ها را به‌روزرسانی می‌کند:\[H^{t+1}=F(H^t,x)\]

اگر \(F\) یک نگاشت انقباضی باشد، این روند تکراری تضمین می‌کند که وضعیت گره‌ها به یک نمایش پایدار (نقطهٔ ثابت) همگرا می‌شوند. یعنی بعد از چند مرحله، دیگر تغییر محسوسی در وضعیت گره‌ها ایجاد نمی‌شود و سیستم به نوعی «تعادل» می‌رسد. این ویژگی پایه‌ی تئوری Vanilla GNN است و نقش مهمی در همگرایی و پایداری آن دارد.