نظریه گراف برای یادگیری ماشین: از مبانی تا GNN

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

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

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

گراف‌ها ساختار داده‌ی روابط هستند. اگر داده‌های شما ارتباطاتی دارند، به نظریه‌ی گراف نیاز پیدا می‌کنید.

اهداف یادگیری

• ساخت یک کلاس گراف با نمایش‌های ماتریس و لیست مجاورت (adjacency list/matrix) و پیاده‌سازی پیمایش‌های BFS و DFS
• محاسبه‌ی لاپلاسین گراف و استفاده از مقادیر ویژه‌ی آن برای شناسایی مؤلفه‌های همبند و خوشه‌بندی گره‌ها
• پیاده‌سازی یک دور انتقال پیام (message passing) به سبک GNN در قالب ضرب ماتریس مجاورت نرمال‌شده
• استفاده از خوشه‌بندی طیفی (spectral clustering) برای افراز گراف با بردار فیدلر (Fiedler vector)

صورت مسئله

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

یک شبکه‌ی اجتماعی را در نظر بگیرید. می‌خواهید پیش‌بینی کنید کاربر چه محصولی را می‌خرد. تاریخچه‌ی خرید خود او مهم است، اما تاریخچه‌ی خرید دوستانش اهمیتی دوچندان دارد؛ پیوندها حامل سیگنال هستند.

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

شبکه‌های عصبی گراف (Graph Neural Networks یا GNNs) سریع‌ترین حوزه‌ی در حال رشد در یادگیری عمیق هستند. این شبکه‌ها پایه‌ی کشف دارو، سیستم‌های پیشنهاددهنده‌ی اجتماعی، تشخیص تقلب و استدلال روی گراف‌های دانش را تشکیل می‌دهند. هر GNN بر روی پایه‌ای یکسان بنا شده است: مبانی نظریه‌ی گراف.

به چهار چیز نیاز دارید:

1. روشی برای نمایش گراف‌ها به صورت ماتریس (تا بتوانید آن‌ها را ضرب کنید)
2. الگوریتم‌های پیمایش برای کاوش ساختار گراف
3. لاپلاسین؛ مهم‌ترین ماتریس در نظریه‌ی طیفی گراف
4. انتقال پیام؛ عملیاتی که موتور محرک GNNها است

مفاهیم پایه

گراف‌ها: گره‌ها و یال‌ها

یک گراف $G = (V, E)$ از رأس‌ها (گره‌ها) $V$ و یال‌ها $E$ تشکیل شده است. هر یال دو گره را به هم متصل می‌کند.

جهت‌دار در برابر بدون جهت. در یک گراف بدون جهت، یال $(u, v)$ یعنی $u$ به $v$ متصل است و $v$ هم به $u$ وصل می‌شود. در یک گراف جهت‌دار (digraph)، یال $(u, v)$ یعنی $u$ به $v$ اشاره می‌کند، اما لزوماً برعکس آن برقرار نیست.

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

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

ماتریس مجاورت (adjacency matrix) با نماد $A$، نمایش اصلی گراف است. برای گرافی با $n$ گره:

$$A[i][j] = \begin{cases} 1 & \text{if there is an edge from node } i \text{ to node } j \\ 0 & \text{otherwise} \end{cases}$$

برای گراف‌های بدون جهت، $A$ متقارن است: $A[i][j] = A[j][i]$. برای گراف‌های وزن‌دار، مقدار $A[i][j]$ برابر با وزن یال $(i, j)$ است.

مثال -- یک مثلث:

Nodes: 0, 1, 2
Edges: (0,1), (1,2), (0,2)

A = [[0, 1, 1],
     [1, 0, 1],
     [1, 1, 0]]

ماتریس مجاورت ورودی همه‌ی GNNها است. عملیات ماتریسی روی $A$ متناظر با عملیات روی گراف است.

درجه

درجه‌ی (degree) یک گره تعداد یال‌های متصل به آن است. برای گراف‌های جهت‌دار، درجه‌ی ورودی (یال‌های واردشونده) و درجه‌ی خروجی (یال‌های خارج‌شونده) داریم.

ماتریس درجه $D$ قطری است:

$$\begin{aligned} D[i][i] &= \text{degree of node } i \\ D[i][j] &= 0 \quad \text{for } i \ne j \end{aligned}$$

برای مثال مثلث: $D = \mathop{\mathrm{diag}}(2, 2, 2)$، زیرا هر گره به دو گره‌ی دیگر متصل است.

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

BFS و DFS

دو الگوریتم پایه‌ای پیمایش گراف؛ به هر دوی آن‌ها نیاز دارید.

جستجوی اول سطح (Breadth-First Search یا BFS): ابتدا همه‌ی همسایه‌ها را بررسی می‌کند، سپس همسایه‌های همسایه‌ها را. از ساختار داده‌ی صف (FIFO) استفاده می‌کند.

BFS from node 0:
  Visit 0
  Queue: [1, 2]        (neighbors of 0)
  Visit 1
  Queue: [2, 3]        (add neighbors of 1)
  Visit 2
  Queue: [3]           (neighbors of 2 already visited)
  Visit 3
  Queue: []            (done)

الگوریتم BFS کوتاه‌ترین مسیرها را در گراف‌های بدون وزن پیدا می‌کند. فاصله‌ی مبدأ تا هر گره برابر با سطحی از BFS است که آن گره برای اولین بار کشف می‌شود. به همین دلیل از BFS برای محاسبه‌ی فاصله‌ی گامی (hop-count) در شبکه‌های اجتماعی استفاده می‌شود.

جستجوی اول عمق (Depth-First Search یا DFS): تا جای ممکن در عمق پیش می‌رود و سپس عقب‌گرد (backtrack) می‌کند. از پشته (LIFO) یا بازگشت بهره می‌برد.

DFS from node 0:
  Visit 0
  Stack: [1, 2]        (neighbors of 0)
  Visit 2               (pop from stack)
  Stack: [1, 3]         (add neighbors of 2)
  Visit 3               (pop from stack)
  Stack: [1]
  Visit 1               (pop from stack)
  Stack: []             (done)

کاربردهای DFS:

• پیدا کردن مؤلفه‌های همبند (اجرای DFS از گره‌های بازدیدنشده)
• تشخیص دور (یال‌های بازگشتی در درخت DFS)
• مرتب‌سازی توپولوژیکی (معکوس ترتیب پایان DFS)

لاپلاسین گراف

$L = D - A$. مهم‌ترین ماتریس در نظریه‌ی طیفی گراف.

برای گراف مثلث:

$$D = \begin{bmatrix} 2 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 2 \end{bmatrix} \qquad A = \begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{bmatrix} \qquad L = \begin{bmatrix} 2 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 2 \end{bmatrix}$$

لاپلاسین ویژگی‌های فوق‌العاده‌ای دارد:

1. $L$ نیمه‌معین مثبت (positive semi-definite) است. همه‌ی مقادیر ویژه $\ge 0$ هستند.

2. تعداد مقادیر ویژه‌ی صفر برابر با تعداد مؤلفه‌های همبند است. یک گراف همبند دقیقاً یک مقدار ویژه‌ی صفر دارد. گرافی با 3 مؤلفه‌ی ناهمبند دارای سه مقدار ویژه‌ی صفر است.

3. کوچک‌ترین مقدار ویژه‌ی غیرصفر (مقدار فیدلر) میزان همبندی را می‌سنجد. مقدار فیدلر بزرگ یعنی گراف همبندی بالایی دارد. مقدار فیدلر کوچک نشان می‌دهد گراف یک نقطه‌ی ضعف یا گلوگاه (bottleneck) دارد.

4. بردار ویژه‌ی متناظر با مقدار فیدلر (بردار فیدلر) بهترین تفکیک را مشخص می‌کند. گره‌های با مقادیر مثبت در یک گروه و گره‌های با مقادیر منفی در گروه دیگر قرار می‌گیرند. این همان خوشه‌بندی طیفی است.

ویژگی‌های طیفی

مقادیر ویژه‌ی ماتریس مجاورت و لاپلاسین، ویژگی‌های ساختاری را بدون نیاز به هیچ پیمایشی آشکار می‌کنند.

خوشه‌بندی طیفی به این صورت عمل می‌کند:

1. محاسبه‌ی لاپلاسین $L$
2. پیدا کردن $k$ بردار ویژه‌ی کوچک‌تر $L$ (صرف‌نظر از بردار اول که در گراف‌های همبند همگی یک است)
3. استفاده از این بردارهای ویژه به عنوان مختصات جدید برای هر گره
4. اجرای الگوریتم $k$-means روی این مختصات

چرا این روش جواب می‌دهد؟ بردارهای ویژه‌ی $L$ «هموارترین» توابع را روی گراف کدگذاری می‌کنند. گره‌هایی که اتصال قوی دارند، مقادیر ویژه‌ی مشابهی دریافت می‌کنند. گره‌هایی که با یک گلوگاه جدا شده‌اند مقادیر متفاوتی می‌گیرند. در نتیجه بردارهای ویژه خوشه‌ها را به شکل طبیعی تفکیک می‌کنند.

ارتباط با گشت تصادفی. لاپلاسین نرمال‌شده با گشت‌های تصادفی (random walks) روی گراف مرتبط است. توزیع پایداری گشت تصادفی با درجه‌ی گره متناسب است. زمان آمیختگی (سرعت همگرایی گشت) به شکاف طیفی (spectral gap) بستگی دارد.

انتقال پیام

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

$$h_v^{(k+1)} = \text{UPDATE}\left(h_v^{(k)}, \text{AGGREGATE}\left(\{h_u^{(k)} : u \in \text{neighbors}(v)\}\right)\right)$$

در ساده‌ترین حالت، تابع تجمیع (AGGREGATE) میانگین و تابع به‌روزرسانی (UPDATE) یک تبدیل خطی به همراه تابع فعالیت است:

$$h_v^{(k+1)} = \sigma\left(W \cdot \text{mean}\left(\{h_u^{(k)} : u \in \text{neighbors}(v)\}\right)\right)$$

این در واقع همان ضرب ماتریسی در پوششی دیگر است. اگر $H$ ماتریس ویژگی‌های همه‌ی گره‌ها و $A$ ماتریس مجاورت باشد:

$$H^{(k+1)} = \sigma\left(A_{\text{norm}} H^{(k)} W\right)$$

که در آن $A_{\text{norm}}$ ماتریس مجاورت نرمال‌شده است (مجموع هر سطر برابر 1 است).

یک دور انتقال پیام به هر گره امکان می‌دهد همسایگان مستقیم خود را «ببیند». دو دور به آن امکان می‌دهد همسایگانِ همسایه‌ها را ببیند. با $K$ دور انتقال پیام، هر گره اطلاعات همسایگی در فاصله‌ی $K$ گام خود را به دست می‌آورد.

مفاهیم و کاربردهای یادگیری ماشین

پیاده‌سازی از صفر

مرحله‌ی 1: ساخت کلاس Graph از پایه

class Graph:
    def __init__(self, n_nodes, directed=False):
        self.n = n_nodes
        self.directed = directed
        self.adj = {i: {} for i in range(n_nodes)}

    def add_edge(self, u, v, weight=1.0):
        self.adj[u][v] = weight
        if not self.directed:
            self.adj[v][u] = weight

    def neighbors(self, node):
        return list(self.adj[node].keys())

    def degree(self, node):
        return len(self.adj[node])

    def weighted_degree(self, node):
        return sum(self.adj[node].values())

    def adjacency_matrix(self):
        import numpy as np
        A = np.zeros((self.n, self.n))
        for u in range(self.n):
            for v, w in self.adj[u].items():
                A[u][v] = w
        return A

    def degree_matrix(self):
        import numpy as np
        D = np.zeros((self.n, self.n))
        for i in range(self.n):
            D[i][i] = self.weighted_degree(i)
        return D

    def laplacian(self):
        return self.degree_matrix() - self.adjacency_matrix()

لیست مجاورت (self.adj) همسایه‌ها را با کارایی بالا ذخیره می‌کند. تبدیل به ماتریس مجاورت از numpy استفاده می‌کند چون همه‌ی عملیات طیفی به آن نیاز دارند.

مرحله‌ی 2: پیمایش‌های BFS و DFS

from collections import deque

def bfs(graph, start):
    visited = set()
    order = []
    distances = {}
    queue = deque([(start, 0)])
    visited.add(start)
    while queue:
        node, dist = queue.popleft()
        order.append(node)
        distances[node] = dist
        for neighbor in graph.neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    return order, distances


def dfs(graph, start):
    visited = set()
    order = []
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for neighbor in reversed(graph.neighbors(node)):
            if neighbor not in visited:
                stack.append(neighbor)
    return order

در BFS از deque (صف دوطرفه) برای اجرای سریع عملیات popleft با زمان $O(1)$ استفاده می‌شود. در DFS از یک لیست معمولی به عنوان پشته کمک می‌گیریم. هر دو روش دقیقاً یک بار هر گره را می‌بینند؛ یعنی زمان اجرای آن‌ها $O(V + E)$ است.

مرحله‌ی 3: مؤلفه‌های همبند و مقادیر ویژه‌ی لاپلاسین

def connected_components(graph):
    visited = set()
    components = []
    for node in range(graph.n):
        if node not in visited:
            order, _ = bfs(graph, node)
            visited.update(order)
            components.append(order)
    return components


def laplacian_eigenvalues(graph):
    import numpy as np
    L = graph.laplacian()
    eigenvalues = np.linalg.eigvalsh(L)
    return eigenvalues

تابع eigvalsh مخصوص ماتریس‌های متقارن است؛ لاپلاسین برای گراف‌های بدون جهت همیشه متقارن خواهد بود. این تابع مقادیر ویژه را به ترتیب صعودی برمی‌گرداند. با شمارش تعداد صفرها، تعداد مؤلفه‌های همبند مشخص می‌شود.

مرحله‌ی 4: خوشه‌بندی طیفی

def spectral_clustering(graph, k=2):
    import numpy as np
    L = graph.laplacian()
    eigenvalues, eigenvectors = np.linalg.eigh(L)
    features = eigenvectors[:, 1:k+1]

    labels = np.zeros(graph.n, dtype=int)
    for i in range(graph.n):
        if features[i, 0] >= 0:
            labels[i] = 0
        else:
            labels[i] = 1
    return labels

برای $k=2$، علامت مقادیر بردار فیدلر گراف را به دو خوشه تقسیم می‌کند. برای $k>2$، الگوریتم $k$-means را روی $k$ بردار ویژه‌ی اول (به جز بردار بدیهی همگی‌یک) اجرا می‌کنید.

مرحله‌ی 5: انتقال پیام

def message_passing(graph, features, weight_matrix):
    import numpy as np
    A = graph.adjacency_matrix()
    row_sums = A.sum(axis=1, keepdims=True)
    row_sums[row_sums == 0] = 1
    A_norm = A / row_sums
    aggregated = A_norm @ features
    output = aggregated @ weight_matrix
    return output

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

استفاده از ابزارهای واقعی

با استفاده از networkx و numpy، همین عملیات در یک خط کد خلاصه می‌شوند:

import networkx as nx
import numpy as np

G = nx.karate_club_graph()

A = nx.adjacency_matrix(G).toarray()
L = nx.laplacian_matrix(G).toarray()

eigenvalues = np.linalg.eigvalsh(L.astype(float))
print(f"Smallest eigenvalues: {eigenvalues[:5]}")
print(f"Connected components: {nx.number_connected_components(G)}")

communities = nx.community.greedy_modularity_communities(G)
print(f"Communities found: {len(communities)}")

pr = nx.pagerank(G)
top_nodes = sorted(pr.items(), key=lambda x: x[1], reverse=True)[:5]
print(f"Top 5 PageRank nodes: {top_nodes}")

کتابخانه‌ی networkx گراف‌هایی با هر اندازه‌ای را با بک‌اندهای بهینه‌شده‌ی C پردازش می‌کند. در محیط عملیاتی از آن استفاده کنید؛ از پیاده‌سازی دستی خودتان هم برای درک عمیق منطق پشت صحنه بهره ببرید.

تحلیل طیفی با numpy

import numpy as np

A = np.array([
    [0, 1, 1, 0, 0],
    [1, 0, 1, 0, 0],
    [1, 1, 0, 1, 0],
    [0, 0, 1, 0, 1],
    [0, 0, 0, 1, 0]
])

D = np.diag(A.sum(axis=1))
L = D - A

eigenvalues, eigenvectors = np.linalg.eigh(L)
print(f"Eigenvalues: {np.round(eigenvalues, 4)}")
print(f"Fiedler value: {eigenvalues[1]:.4f}")
print(f"Fiedler vector: {np.round(eigenvectors[:, 1], 4)}")

fiedler = eigenvectors[:, 1]
group_a = np.where(fiedler >= 0)[0]
group_b = np.where(fiedler < 0)[0]
print(f"Cluster A: {group_a}")
print(f"Cluster B: {group_b}")

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

خروجی این درس

این درس فایل زیر را می‌سازد:

• outputs/skill-graph-analysis.md -- یک مرجع مهارتی برای تحلیل داده‌های دارای ساختار گراف

ارتباط مفاهیم

شبکه‌های GNN شایسته‌ی توجه ویژه‌ای هستند. عملیات کانولوشن گراف در GCN (کیپف و ولینگ، 2017) از ماتریس مجاورت همراه با حلقه‌های خودارجاع اضافه (self-loops) با نماد $\hat{A} = A + I$ استفاده می‌کند:

$$H^{(l+1)} = \sigma\left(\hat{D}^{-1/2} \hat{A} \hat{D}^{-1/2} H^{(l)} W^{(l)}\right)$$

به طوری که $\hat{A} = A + I$ (ماتریس مجاورت به اضافه‌ی حلقه‌های خودارجاع) و $\hat{D}$ ماتریس درجه‌ی $\hat{A}$ است. حلقه‌های خودارجاع تضمین می‌کنند که هر گره در طول فرآیند تجمیع، ویژگی‌های خودش را نیز لحاظ کند. این دقیقاً همان انتقال پیام با نرمال‌سازی متقارن است. $\hat{D}^{-1/2} \hat{A} \hat{D}^{-1/2}$ همان ماتریس مجاورت نرمال‌شده است. لاپلاسین به این دلیل در اینجا ظاهر می‌شود که این نرمال‌سازی با $L_{\text{sym}} = I - D^{-1/2} A D^{-1/2}$ ارتباط نزدیکی دارد. درک لاپلاسین کلید فهم شیوه‌ی کار GCNها است.

تمرین‌ها

1. الگوریتم PageRank را از پایه پیاده‌سازی کنید. با امتیازهای یکنواخت شروع کنید. در هر مرحله: مقدار score(v) = (1-d)/n + d * sum(score(u)/out_degree(u)) را برای همه‌ی گره‌های u که به v اشاره دارند حساب کنید. پارامتر d=0.85 را در نظر بگیرید. فرایند را تا رسیدن به همگرایی (تغییرات کمتر از 1e-6) ادامه دهید. عملکرد آن را روی یک گراف کوچک وب آزمایش کنید.

2. شناسایی اجتماعات با خوشه‌بندی طیفی. گرافی با دو خوشه‌ی کاملاً مجزا بسازید (مثلاً دو دسته‌ی کامل clique که با یک یال به هم وصل شده‌اند). خوشه‌بندی طیفی را روی آن اجرا کنید و مطمئن شوید تفکیک درستی انجام می‌دهد. اگر یال‌های بین دو خوشه را افزایش دهید چه اتفاقی می‌افتد؟

3. پیاده‌سازی الگوریتم دایکسترا (Dijkstra) برای کوتاه‌ترین مسیر در گراف‌های وزن‌دار. نتایج را با اجرای BFS روی همان گراف با وزن‌های یکسان مقایسه کنید.

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

5. تحلیل یک گراف واقعی. از گراف باشگاه کاراته (34 گره، 78 یال) استفاده کنید. توزیع درجه، مقادیر ویژه‌ی لاپلاسین و خوشه‌بندی طیفی را به دست آورید. نتیجه‌ی خوشه‌بندی طیفی را با تفکیک واقعی و مبنا (ground truth) مقایسه کنید.

راهنمایی‌ها

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

تمرین 2. با متد add_edge دو دسته‌ی کامل بسازید، آن‌ها را با یک یال به هم متصل کنید و تابع spectral_clustering(graph, k=2) را فراخوانی کنید. بررسی کنید که به هر دسته یک برچسب مجزا اختصاص یابد. هم‌زمان با اضافه کردن یال‌های متقاطع، دومین مقدار ویژه‌ی کوچک‌تر تابع laplacian() را چاپ کنید؛ این مقدار با یکی شدن دو گروه افزایش می‌یابد.

تمرین 3. یک صف اولویت‌دار با کتابخانه‌ی heapq نگه دارید و همیشه گره‌ای را که کمترین مسافت شناخته‌شده را دارد بسط دهید. همه‌ی وزن‌ها را برابر با 1 قرار دهید و بررسی کنید که فاصله‌ی هر گره در دایکسترا با سطح BFS آن گره در خروجی bfs(graph, start) یکسان باشد.

تمرین 4. ماتریس همانی را به عنوان features ورودی در نظر بگیرید تا هر ستون نشان‌دهنده‌ی یک گره باشد؛ سپس تابع message_passing را دو بار اعمال کنید. در این حالت مقادیر غیرصفر در سطر مربوط به گره‌ی $v$ مشخص می‌کنند چه گره‌هایی به $v$ رسیده‌اند. این مجموعه را با گره‌هایی که فاصله‌شان در جستجوی اول سطح حداکثر 2 است مقایسه کنید.

تمرین 5. متد networkx.karate_club_graph() لیست یال‌ها و برچسب‌های مرجع را در ویژگی club گره‌ها در اختیارتان می‌گذارد. یال‌ها را درون شیء Graph کپی کنید و مطمئن شوید 34 گره و 78 یال دارد. برچسب‌های خروجی spectral_clustering را با مقادیر club مقایسه کنید؛ در نظر داشته باشید که نام دو برچسب ممکن است با یکدیگر جابه‌جا شده باشد.

اصطلاحات کلیدی

برای مطالعه‌ی بیشتر

• Kipf & Welling (2017) -- "Semi-Supervised Classification with Graph Convolutional Networks." مقاله‌ای که جرقه‌ی GNNهای مدرن را زد و نشان داد کانولوشن‌های طیفی گراف به انتقال پیام ساده می‌شوند.
• Spielman (2012) -- یادداشت‌های درس "Spectral Graph Theory". مرجع بی‌نظیر برای یادگیری لاپلاسین‌ها، شکاف‌های طیفی و افراز گراف.
• Hamilton (2020) -- کتاب "Graph Representation Learning". بررسی جامع GNNها از مفاهیم پایه‌ای تا کاربردهای عملی.
• Bronstein et al. (2021) -- "Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges." مقاله‌ی چارچوب یکپارچه‌ساز یادگیری هندسی.
• Veličković et al. (2018) -- "Graph Attention Networks." ارتقای انتقال پیام با استفاده از مکانیزم‌های اتنشن.