مقدمه‌ای بر نظریۀ گراف (ریاضیات پیش‌نیاز GNN)

گراف‌ها مفاهیم پایه‌ای در مطالعهٔ شبکه‌های عصبی گرافی (GNNها) هستند. بنابراین، برای درک جامع از GNN، آشنایی با نظریهٔ پایهٔ گراف ضروری است.

مفاهیم پایه

گراف معمولاً با نماد \(G=(V,E)\) نمایش داده می‌شود که در آن \(V\) مجموعهٔ رئوس (vertices) و \(E\) مجموعهٔ یال‌ها (edges) است. هر یال \(e=(u,v)\) دارای دو نقطهٔ پایانی \(u\) و \(v\) است که گفته می‌شود توسط یال \(e\) به هم متصل شده‌اند. در این حالت، \(u\) را همسایه (neighbor) رأس \(v\) می‌نامند و این دو رأس را مجاور (adjacent) یکدیگر در نظر می‌گیرند. یال‌ها می‌توانند جهت‌دار (directed) یا بی‌جهت (undirected) باشند. اگر همهٔ یال‌ها جهت‌دار باشند، گراف را گراف جهت‌دار (directed graph) و اگر همهٔ یال‌ها بی‌جهت باشند، آن را گراف بی‌جهت (undirected graph) می‌نامند. درجهٔ یک رأس \(v\) که با \(d(v)\) نشان داده می‌شود، برابر است با تعداد یال‌هایی که به آن رأس متصل هستند.

نمایش جبری گراف‌ها

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

- ماتریس مجاورت (Adjacency matrix): برای یک گراف ساده \(G=(V,E)\) با \(n\) رأس، می‌توان آن را با یک ماتریس مجاورت \(A \in \mathbb{R}^{n \times n}\) توصیف کرد، که در آن:

\[ A_{ij} = \begin{cases} 1 & \text{if} \{v_i, v_j\} \in E \text{ و } i \ne j \\ 0 & \text{Otherwise} \end{cases} \]

بدیهی است که اگر \(G\) یک گراف بی‌جهت باشد، این ماتریس، یک ماتریس متقارن (symmetric) خواهد بود.

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

\[ A = \begin{bmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} \]- ماتریس درجه (Degree matrix): برای یک گراف \(G=(V,E)\) با \(n\) رأس، ماتریس درجهٔ آن \(D \in \mathbb{R}^{n \times n}\) یک ماتریس قطری است، که در آن:

\[ D_{ii} = d(v_i) \]

یعنی مقدار قطر اصلی در سطر و ستون \(i\) برابر است با درجهٔ رأس \(v_i\)​ (تعداد یال‌هایی که به آن متصل‌اند).

- ماتریس لاپلاس (Laplacian matrix): برای یک گراف ساده \(G=(V,E)\) با \(n\) رأس، اگر همهٔ یال‌ها را بی‌جهت در نظر بگیریم، آنگاه ماتریس لاپلاس \(L \in \mathbb{R}^{n \times n}\) به‌صورت زیر تعریف می‌شود:

\[ L = D - A \]

که در آن:

• \(D\) ماتریس درجه

• $\backslash (A\backslash )$ ماتریس مجاورت است.

در نتیجه، عناصر \(L\) به‌صورت زیر تعریف می‌شوند:

\[ L_{ij} = \begin{cases} d(v_i) & \text{if } i = j \\ -1 & \text{if } \{v_i, v_j\} \in E \text{ and } i \ne j \\ 0 & \text{otherwise} \end{cases} \]

*  توجه داشته باشید که این تعریف برای گراف بی‌جهت در نظر گرفته شده است.

- لاپلاس نرمال‌سازی‌شده متقارن (Symmetric Normalized Laplacian): ماتریس لاپلاس نرمال‌شده متقارن به صورت زیر تعریف می‌شود:

\[ L^{\text{sym}} = D^{-\frac{1}{2}} L D^{-\frac{1}{2}} = I - D^{-\frac{1}{2}} A D^{-\frac{1}{2}} \]

که در آن:

• $\backslash (D\backslash )$ ماتریس درجه

• \(A\) ماتریس مجاورت

• $\backslash (I\backslash )$ ماتریس همانی است.

عناصر ماتریس \(L^{sym}\) به صورت زیر تعریف می‌شوند:

\[ L^{\text{sym}}_{ij} = \begin{cases} 1 & \text{if } i = j \text{ and } d(v_i) \ne 0 \\ -\dfrac{1}{\sqrt{d(v_i) d(v_j)}} & \text{if } \{v_i, v_j\} \in E \text{ and } i \ne j \\ 0 & \text{otherwise} \end{cases} \]

لاپلاس نرمال‌سازی‌شده گام تصادفی (Random Walk Normalized Laplacian): این ماتریس به صورت زیر تعریف می‌شود:

\[ L^{\text{rw}} = D^{-1} L = I - D^{-1} A \]

که در آن:

• $\backslash (D\backslash )$ ماتریس درجه،

• $\backslash (A\backslash )$ ماتریس مجاورت،

• و \(I\) ماتریس همانی است.

عناصر ماتریس \(L^{rw}\) به صورت زیر هستند:

\[ L^{\text{rw}}_{ij} = \begin{cases} 1 & \text{if } i = j \text{ and } d(v_i) \ne 0 \\ -\dfrac{1}{d(v_i)} & \text{if } \{v_i, v_j\} \in E \text{ and } i \ne j \\ 0 & \text{otherwise} \end{cases} \]

- ماتریس رخداد (Incidence Matrix): یکی دیگر از ماتریس‌های رایج در نمایش گراف‌ها، ماتریس رخداد است. برای یک گراف جهت‌دار \(G=(V,E)\) با \(n\) رأس و \(m\) یال، ماتریس رخداد $\backslash (M\; \backslash in\; \backslash mathbb\{R\}^\{m\; \backslash times\; n\}\backslash )$ به صورت زیر تعریف می‌شود:

\[ M_{ij} = \begin{cases} 1 & \text{if } \exists k \text{ such that } e_j = \{v_i, v_k\} \\ -1 & \text{if } \exists k \text{ such that } e_j = \{v_k, v_i\} \\ 0 & \text{otherwise} \end{cases} \]

برای یک گراف بی‌جهت، ماتریس رخداد به صورت ساده‌تری تعریف می‌شود:

\[ \text{(Undirected case)} \quad M_{ij} = \begin{cases} 1 & \text{if } \exists k \text{ such that } e_j = \{v_i, v_k\} \\ 0 & \text{otherwise} \end{cases} \]