Lý Thuyết Đồ Thị (Graph Theory)

Lý thuyết đồ thị cung cấp ngôn ngữ toán học để mô tả các mối quan hệ giữa các thực thể. File này bao gồm nút, cạnh, ma trận kề, các loại đồ thị, bậc và tính liên thông, Laplacian đồ thị, lý thuyết đồ thị phổ, và các ứng dụng đồ thị trong thế giới thực. Chúng ta sẽ đi sâu hơn về đồ thị trong các chương khoa học máy tính thuần túy sau này.

• Cho đến nay trong cuốn sách này, dữ liệu sống trên các cấu trúc đều đặn: vector trong \(\mathbb{R}^n\) (chương 1), ma trận dưới dạng lưới số (chương 2), ảnh dưới dạng lưới pixel (chương 8), chuỗi dưới dạng danh sách có thứ tự (chương 7). Nhưng nhiều hệ thống thế giới thực là không đều (irregular): một mạng xã hội không có cấu trúc lưới, một phân tử không có thứ tự trái-phải, và một mạng lưới đường bộ không xếp gọn gàng thành các hàng và cột.

• Đồ thị (Graphs) là công cụ toán học để biểu diễn các cấu trúc quan hệ không đều này. Một đồ thị nắm bắt các thực thể (nút) và các mối quan hệ (cạnh) giữa chúng. Khi dữ liệu được biểu diễn dưới dạng đồ thị, chúng ta có thể áp dụng các nguyên lý học sâu hình học từ file 1 để học từ nó.

Nút, Cạnh, và Ma Trận Kề (Nodes, Edges, and Adjacency)

• Một đồ thị \(G = (V, E)\) bao gồm một tập các nút (hoặc đỉnh) \(V = \{v_1, v_2, \ldots, v_n\}\) và một tập các cạnh \(E \subseteq V \times V\) nối các cặp nút.

• Các nút biểu diễn các thực thể: người, nguyên tử, thành phố, trang web, nơ-ron. Các cạnh biểu diễn các mối quan hệ: tình bạn, liên kết hóa học, đường xá, siêu liên kết, khớp thần kinh.

• Ma trận kề (adjacency matrix) \(A\) là biểu diễn ma trận của một đồ thị. Với một đồ thị có \(n\) nút, \(A\) là ma trận \(n \times n\) trong đó \(A_{ij} = 1\) nếu có một cạnh từ nút \(i\) đến nút \(j\), và \(A_{ij} = 0\) nếu không.

• Ví dụ, một đồ thị tam giác (3 nút, tất cả đều kết nối) có:

\[ A = \begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{bmatrix} \]

• Đường chéo bằng 0 vì các nút không kết nối với chính chúng (mặc định không có vòng tự thân). Ma trận kề là một ứng dụng trực tiếp của ma trận Boolean mà chúng ta đã học trong chương 2: mỗi mục là một quan hệ nhị phân.

• Ma trận kề mã hóa cấu trúc đồ thị một cách đầy đủ. Các phép toán ma trận trên \(A\) tiết lộ các tính chất của đồ thị: \(A^2_{ij}\) đếm số đường đi độ dài 2 giữa các nút \(i\) và \(j\) (nhắc lại phép nhân ma trận từ chương 2: mỗi mục là tổng các tích qua các nút trung gian). Tổng quát hơn, \(A^k_{ij}\) đếm các đường đi độ dài \(k\).

• Mỗi nút có thể mang một vector đặc trưng (feature vector) \(\mathbf{x}_i \in \mathbb{R}^d\). Với mạng xã hội, đây có thể là thông tin hồ sơ của người dùng. Với một phân tử, nó mã hóa loại nguyên tử, điện tích, và các tính chất khác. Tập đầy đủ các đặc trưng nút là một ma trận \(X \in \mathbb{R}^{n \times d}\), trong đó mỗi hàng là đặc trưng của một nút.

• Các cạnh cũng có thể mang đặc trưng: loại liên kết trong phân tử, khoảng cách trong đồ thị không gian, loại quan hệ trong đồ thị tri thức. Đặc trưng cạnh (edge feature) cho cạnh \((i, j)\) là một vector \(\mathbf{e}_{ij} \in \mathbb{R}^{d_e}\).

Các Loại Đồ Thị (Graph Types)

• Một đồ thị vô hướng (undirected graph) có các cạnh đối xứng: nếu \(i\) kết nối với \(j\), thì \(j\) cũng kết nối với \(i\). Ma trận kề là đối xứng: \(A = A^T\) (một ma trận đối xứng, chương 2). Tình bạn và liên kết hóa học là vô hướng.

• Một đồ thị có hướng (directed graph) (digraph) có các cạnh có hướng: một cạnh từ \(i\) đến \(j\) không suy ra một cạnh từ \(j\) đến \(i\). Ma trận kề là bất đối xứng. Theo dõi trên Twitter, siêu liên kết web, và mạng trích dẫn là có hướng.

• Một đồ thị có trọng số (weighted graph) gán một trọng số số cho mỗi cạnh. Ma trận kề có các mục giá trị thực thay vì nhị phân: \(A_{ij} = w_{ij}\). Khoảng cách trong mạng lưới đường bộ, độ mạnh tương quan trong kết nối não, và tần suất tương tác trong mạng xã hội là có trọng số.

• Một đồ thị hai phía (bipartite graph) có hai tập nút rời rạc, với các cạnh chỉ nối giữa các tập (không bao giờ trong cùng một tập). Người dùng và sản phẩm tạo thành một đồ thị hai phía: người dùng đánh giá sản phẩm, nhưng người dùng không đánh giá người dùng. Ma trận kề của đồ thị hai phía có cấu trúc khối:

\[ A = \begin{bmatrix} 0 & B \\ B^T & 0 \end{bmatrix} \]

• trong đó \(B\) là ma trận kề hai phía giữa hai tập nút.

• Một đa đồ thị (multigraph) cho phép nhiều cạnh giữa cùng một cặp nút và/hoặc vòng tự thân. Đồ thị tri thức thường là đa đồ thị: hai thực thể có thể có nhiều mối quan hệ (ví dụ: "sinh ra tại," "sống tại," "làm việc tại").

• Một siêu đồ thị (hypergraph) tổng quát hóa các cạnh để kết nối nhiều hơn hai nút cùng lúc. Một siêu cạnh (hyperedge) kết nối một tập các nút, biểu diễn các mối quan hệ bậc cao. Một bài báo nghiên cứu do năm người đồng tác giả là một siêu cạnh kết nối năm nút tác giả.

• Một đồ thị đầy đủ (complete graph) \(K_n\) có một cạnh giữa mọi cặp nút. Đây là tương tự đồ thị của một tầng kết nối đầy đủ, và nó là cấu trúc mà các transformer hoạt động trên đó (mọi token đều chú ý đến mọi token khác).

Bậc, Đường Đi, và Tính Liên Thông (Degree, Paths, and Connectivity)

• Bậc (degree) của một nút là số cạnh kết nối với nó. Trong đồ thị vô hướng, bậc của nút \(i\) là \(d_i = \sum_j A_{ij}\). Các nút bậc cao là "trung tâm (hubs)" với nhiều kết nối.

• Ma trận bậc (degree matrix) \(D\) là ma trận đường chéo với các bậc trên đường chéo: \(D_{ii} = d_i\). Ma trận này xuất hiện khắp nơi trong lý thuyết đồ thị và các công thức GNN.

• Một đường đi (path) giữa hai nút là một dãy các cạnh nối chúng. Đường đi ngắn nhất (shortest path) (hay geodesic) giữa \(i\) và \(j\) là đường đi với ít cạnh nhất (hoặc tổng trọng số thấp nhất trong đồ thị có trọng số). Thuật toán Dijkstra tìm đường đi ngắn nhất trong thời gian \(O((|V| + |E|) \log |V|)\).

• Một đồ thị là liên thông (connected) nếu có một đường đi giữa mọi cặp nút. Nếu không, nó có nhiều thành phần liên thông (connected components): các đồ thị con cô lập không có cạnh giữa chúng.

• Đường kính (diameter) của một đồ thị là đường đi ngắn nhất dài nhất giữa bất kỳ cặp nút nào. Nó đo lường đồ thị "trải rộng" như thế nào. Mạng xã hội nổi tiếng là có đường kính nhỏ ("sáu bậc tách biệt").

• Một chu trình (cycle) là một đường đi bắt đầu và kết thúc tại cùng một nút. Một đồ thị không có chu trình là một cây (tree). Cây là các đồ thị liên thông đơn giản nhất: \(n\) nút và chính xác \(n-1\) cạnh.

• Độ trung tâm (Centrality) đo lường tầm quan trọng của một nút. Độ trung tâm bậc (Degree centrality) đơn giản là bậc. Độ trung tâm trung gian (Betweenness centrality) đếm số đường đi ngắn nhất đi qua một nút. Độ trung tâm vector riêng (Eigenvector centrality) gán tầm quan trọng dựa trên tầm quan trọng của các nút lân cận, dẫn đến phương trình vector riêng \(A\mathbf{x} = \lambda \mathbf{x}\) (chương 2). PageRank của Google là một biến thể của độ trung tâm vector riêng cho đồ thị có hướng.

Laplacian Đồ Thị (The Graph Laplacian)

• Laplacian đồ thị (graph Laplacian) có lẽ là ma trận quan trọng nhất trong lý thuyết đồ thị. Nó được định nghĩa là:

\[L = D - A\]

• trong đó \(D\) là ma trận bậc và \(A\) là ma trận kề. Với ví dụ tam giác của chúng ta:

\[ L = \begin{bmatrix} 2 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 2 \end{bmatrix} - \begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{bmatrix} = \begin{bmatrix} 2 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 2 \end{bmatrix} \]

• Laplacian có các tính chất đáng chú ý:

  • Nó luôn đối xứng và bán xác định dương (positive semi-definite) (nhắc lại từ chương 2: tất cả các trị riêng đều \(\geq 0\)). Với bất kỳ vector \(\mathbf{x}\) nào:

\[\mathbf{x}^T L \mathbf{x} = \sum_{(i,j) \in E} (x_i - x_j)^2\]

- Dạng toàn phương này đo lường mức độ một tín hiệu $\mathbf{x}$ trên đồ thị biến thiên qua các cạnh. Nếu các nút lân cận có giá trị tương tự, $\mathbf{x}^T L \mathbf{x}$ là nhỏ. Nếu chúng khác biệt mạnh, nó là lớn. Laplacian đo lường **độ trơn tru (smoothness)** của các tín hiệu trên đồ thị.

- Trị riêng nhỏ nhất luôn là 0, với vector riêng $\mathbf{1} = [1, 1, \ldots, 1]^T$ (một tín hiệu hằng có độ biến thiên bằng không). Số trị riêng bằng 0 bằng số thành phần liên thông.

- Trị riêng nhỏ thứ hai $\lambda_2$ là **độ liên thông đại số (algebraic connectivity)** (giá trị Fiedler). Nó đo lường mức độ kết nối tốt của đồ thị: $\lambda_2 = 0$ nghĩa là đồ thị không liên thông, $\lambda_2$ lớn nghĩa là đồ thị kết nối chặt chẽ.

• Laplacian chuẩn hóa (normalised Laplacian) được chia tỷ lệ theo bậc:

\[\hat{L} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} A D^{-1/2}\]

• Việc chuẩn hóa này đảm bảo các tính chất của Laplacian không phụ thuộc vào tỷ lệ tuyệt đối của bậc các nút. Số hạng \(D^{-1/2} A D^{-1/2}\) là ma trận kề được chuẩn hóa đối xứng (symmetrically normalised adjacency), và nó xuất hiện trực tiếp trong công thức GCN (file 3).

Lý Thuyết Đồ Thị Phổ (Spectral Graph Theory)

• Các trị riêng và vector riêng của Laplacian đồ thị định nghĩa phổ (spectrum) của đồ thị, và chúng đóng vai trò như tương tự của biến đổi Fourier cho đồ thị.

• Trong xử lý tín hiệu cổ điển, biến đổi Fourier phân tích một tín hiệu thành các thành phần tần số (sine và cosine). Trên một đồ thị, các vector riêng của Laplacian đóng vai trò của các cơ sở tần số này. Các vector riêng với trị riêng thấp biến thiên chậm trên đồ thị (tần số thấp, trơn), trong khi các vector riêng với trị riêng cao biến thiên nhanh (tần số cao, dao động).

• Biến đổi Fourier Đồ thị (Graph Fourier Transform — GFT) của một tín hiệu \(\mathbf{x}\) trên đồ thị là:

\[\hat{\mathbf{x}} = U^T \mathbf{x}\]

• trong đó \(U\) là ma trận các vector riêng của Laplacian (nhắc lại phân rã trị riêng từ chương 2: \(L = U \Lambda U^T\)). Biến đổi ngược là \(\mathbf{x} = U \hat{\mathbf{x}}\).

• Tích chập đồ thị (graph convolution) trong miền phổ là phép nhân theo từng điểm trong miền tần số, giống như tích chập trong miền không gian tương ứng với phép nhân trong miền Fourier (định lý tích chập từ chương 8):

\[g_\theta \star \mathbf{x} = U \left( (U^T g_\theta) \odot (U^T \mathbf{x}) \right) = U \, \text{diag}(\hat{g}_\theta) \, U^T \mathbf{x}\]

• Bộ lọc \(\hat{g}_\theta\) là một hàm học được của các trị riêng. Đây là nền tảng của các GNN phổ (spectral GNNs), mà chúng ta sẽ đơn giản hóa thành GCN thực tế trong file 3.

• Nút thắt tính toán là phân rã trị riêng của \(L\), với chi phí \(O(n^3)\) cho một đồ thị với \(n\) nút. Điều này không thực tế cho các đồ thị lớn (hàng triệu nút). Các xấp xỉ đa thức (đa thức Chebyshev) tránh hoàn toàn phân rã trị riêng, và xấp xỉ này dẫn trực tiếp đến GCN.

Phát Hiện Cộng Đồng (Community Detection)

• Nhiều đồ thị thế giới thực có cấu trúc cộng đồng (community structure): các cụm nút kết nối dày đặc với các kết nối thưa thớt giữa các cụm. Mạng xã hội có các nhóm bạn bè, mạng sinh học có các mô-đun chức năng, mạng trích dẫn có các lĩnh vực nghiên cứu.

• Phân cụm phổ (Spectral clustering) sử dụng các vector riêng Laplacian để tìm các cộng đồng. Ý tưởng: nhúng mỗi nút sử dụng \(k\) vector riêng không tầm thường nhỏ nhất của \(L\), sau đó áp dụng k-means (chương 6) trong không gian nhúng này. Các nút trong cùng cộng đồng sẽ gần nhau trong không gian nhúng phổ.

• Điều này hoạt động vì vector Fiedler (vector riêng của \(\lambda_2\)) tự nhiên tách đồ thị thành hai nhóm: các nút có giá trị dương và các nút có giá trị âm, cắt qua các kết nối thưa thớt nhất. Các vector riêng bậc cao hơn tinh chỉnh điều này thành nhiều nhóm hơn.

• Modularity \(Q\) đo lường chất lượng của một phân hoạch cộng đồng. Nó so sánh số cạnh trong cùng cộng đồng với số kỳ vọng trong một đồ thị ngẫu nhiên:

\[Q = \frac{1}{2|E|} \sum_{ij} \left( A_{ij} - \frac{d_i d_j}{2|E|} \right) \delta(c_i, c_j)\]

• trong đó \(c_i\) là gán cộng đồng của nút \(i\) và \(\delta\) bằng 1 nếu các nút cùng cộng đồng. \(Q\) nằm trong khoảng từ \(-0.5\) đến \(1\), với giá trị cao hơn chỉ ra cấu trúc cộng đồng mạnh hơn.

Đồ Thị Thế Giới Thực (Real-World Graphs)

• Mạng xã hội: các nút là người, các cạnh là tình bạn hoặc tương tác. Facebook có hàng tỷ nút và hàng trăm tỷ cạnh. Các đồ thị này thường thưa (mỗi người có hàng trăm bạn, không phải hàng tỷ), thể hiện tính chất thế giới nhỏ (small-world) (độ dài đường đi trung bình ngắn), và có phân bố bậc đuôi nặng (heavy-tailed degree distributions) (một vài trung tâm với hàng triệu kết nối).

• Đồ thị phân tử: các nút là nguyên tử, các cạnh là liên kết hóa học. Mỗi nguyên tử có đặc trưng (loại nguyên tố, điện tích, lai hóa) và mỗi liên kết có đặc trưng (đơn, đôi, ba, thơm). Đồ thị phân tử nhỏ (hàng chục đến hàng trăm nút) nhưng có cấu trúc cao. Dự đoán tính chất phân tử từ cấu trúc đồ thị là một ứng dụng chính của GNN.

• Đồ thị tri thức: các nút là thực thể (người, địa điểm, khái niệm), các cạnh là quan hệ có kiểu ("sinh ra tại," "thủ đô của," "là trường hợp của"). Đồ thị tri thức cung cấp sức mạnh cho công cụ tìm kiếm, hệ thống gợi ý, và hỏi đáp. Chúng thường là đa đồ thị có hướng với hàng triệu thực thể và hàng tỷ quan hệ.

• Mạng trích dẫn: các nút là bài báo, các cạnh là trích dẫn (có hướng). Phân cụm tiết lộ các cộng đồng nghiên cứu. Đặc trưng nút bao gồm tiêu đề, tóm tắt, và năm xuất bản.

• Mạng tương tác protein: các nút là protein, các cạnh chỉ ra tương tác vật lý hoặc liên kết chức năng. Hiểu các đồ thị này giúp xác định mục tiêu thuốc và cơ chế bệnh.

• Mạng lưới đường bộ và giao thông: các nút là giao lộ, các cạnh là đoạn đường với trọng số khoảng cách/thời gian. Các thuật toán đường đi ngắn nhất trên các đồ thị này cung cấp sức mạnh cho hệ thống dẫn đường. Dự đoán chuyển động của xe tự lái (chương 11) biểu diễn tương tác giữa các tác tử dưới dạng đồ thị.

Bài tập lập trình (dùng CoLab hoặc notebook)

1. Xây dựng một đồ thị nhỏ dưới dạng ma trận kề và tính các tính chất cơ bản: bậc của mỗi nút, số đường đi độ dài 2, và đồ thị có liên thông hay không.

   import jax.numpy as jnp
   
   # A simple graph: 5 nodes
   # 0-1, 0-2, 1-2, 2-3, 3-4
   A = jnp.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]], dtype=float)
   
   # Degree
   degrees = A.sum(axis=1)
   print(f"Degrees: {degrees}")
   
   # Paths of length 2
   A2 = A @ A
   print(f"Paths of length 2 (node 0 to 3): {int(A2[0, 3])}")
   
   # Connected? Check if A^(n-1) has all nonzero entries
   An = jnp.linalg.matrix_power(A + jnp.eye(5), 4)  # (A+I)^4 for reachability
   connected = jnp.all(An > 0)
   print(f"Connected: {connected}")
   

2. Tính Laplacian đồ thị và các trị riêng của nó. Kiểm tra rằng trị riêng nhỏ nhất là 0 và vector riêng tương ứng là hằng.

   import jax.numpy as jnp
   
   A = jnp.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]], dtype=float)
   
   D = jnp.diag(A.sum(axis=1))
   L = D - A
   
   eigenvalues, eigenvectors = jnp.linalg.eigh(L)
   print(f"Eigenvalues: {eigenvalues}")
   print(f"Smallest eigenvector: {eigenvectors[:, 0]}")
   print(f"Fiedler value (algebraic connectivity): {eigenvalues[1]:.4f}")
   
   # Verify: x^T L x measures smoothness
   x = jnp.array([1.0, 1.0, 1.0, -1.0, -1.0])  # two groups
   smoothness = x @ L @ x
   print(f"Smoothness of two-group signal: {smoothness:.2f}")
   

3. Thực hiện phân cụm phổ trên một đồ thị với hai cộng đồng. Nhúng các nút sử dụng vector Fiedler và phân tách chúng theo dấu.

   import jax.numpy as jnp
   import matplotlib.pyplot as plt
   
   # Two communities of 5 nodes each, weakly connected
   A = jnp.zeros((10, 10))
   # Community 1: nodes 0-4 (dense)
   for i in range(5):
       for j in range(i+1, 5):
           A = A.at[i, j].set(1).at[j, i].set(1)
   # Community 2: nodes 5-9 (dense)
   for i in range(5, 10):
       for j in range(i+1, 10):
           A = A.at[i, j].set(1).at[j, i].set(1)
   # One bridge edge
   A = A.at[2, 7].set(1).at[7, 2].set(1)
   
   D = jnp.diag(A.sum(axis=1))
   L = D - A
   eigenvalues, eigenvectors = jnp.linalg.eigh(L)
   
   # Fiedler vector (2nd smallest eigenvalue)
   fiedler = eigenvectors[:, 1]
   communities = (fiedler > 0).astype(int)
   
   print(f"Fiedler vector: {fiedler}")
   print(f"Clusters: {communities}")
   
   plt.bar(range(10), fiedler, color=["#3498db" if c == 0 else "#e74c3c" for c in communities])
   plt.xlabel("Node"); plt.ylabel("Fiedler vector value")
   plt.title("Spectral Clustering via Fiedler Vector")
   plt.show()