Giới thiệu dự án

Sự bùng nổ của kỷ nguyên số và không gian mạng đã tạo ra khối lượng dữ liệu khổng lồ về hành vi người dùng trên các nền tảng trực tuyến như Spotify, Netflix, YouTube và Yelp. Theo thống kê từ ngành công nghiệp giải trí trực tuyến, hơn 80% thời lượng xem trên Netflix và 35% doanh thu của Amazon được thúc đẩy trực tiếp từ các hệ thống gợi ý (Recommender Systems). Tuy nhiên, các hệ thống này đang đối mặt với bài toán dữ liệu thưa thớt (data sparsity) và vấn đề khởi đầu lạnh (cold-start), khi số lượng tương tác đã quan sát chỉ chiếm dưới 1% tổng số không gian liên kết tiềm năng.

Đồ án khóa luận tốt nghiệp "Nghiên cứu phương pháp dự đoán liên kết trong mạng xã hội dựa trên mạng neuron đồ thị" (thực hiện bởi Chu Xuân Sơn, Nguyễn Hoàng Long; GVHD: TS. Cao Thị Nhạn tại Trường Đại học Công nghệ Thông tin - ĐHQG-HCM) tập trung giải quyết bài toán dự đoán liên kết (Link Prediction) trên mạng thông tin không đồng nhất (Heterogeneous Information Networks - HIN).

  (watched)                          (watched)
      (Dự đoán liên kết mới / Đề xuất item)

Mục tiêu nghiên cứu cụ thể

  1. Khảo sát và hệ thống hóa lý thuyết: Phân loại toàn diện các phương pháp dự đoán liên kết truyền thống (Heuristic/Topology-based), phân rã ma trận (Matrix Factorization), học sâu kết hợp đặc trưng (Neural Factorization Machines - NFM) và mạng nơ-ron đồ thị (Graph Neural Networks - GNN).
  2. Xây dựng kiến trúc mô hình học sâu đồ thị nâng cao: Nghiên cứu và áp dụng mô hình PEAGNN (Metapath and Entity-Aware Graph Neural Network / PEAGAT) khai thác ngữ nghĩa siêu đường dẫn (Metapath) và cấu trúc đồ thị con cục bộ (Local Subgraphs).
  3. Thực nghiệm và tối ưu hóa đa mô hình: Triển khai thử nghiệm so chuẩn (benchmarking) trên hai tập dữ liệu thực tế: MovieLens Latest-small (100.836 đánh giá, 610 người dùng, 9.724 bộ phim) và Yelp2018 (6.280 đánh giá, 1.897 người dùng, thông tin kinh doanh đa thực thể).
  4. Đánh giá định lượng chuẩn xác: So sánh hiệu năng xếp hạng top-$K$ dựa trên hai độ đo chính: Hit Ratio ($HR@10$) và Normalized Discounted Cumulative Gain ($NDCG@10$).

Phạm vi và giới hạn

  • Phạm vi: Tập trung vào bài toán dự đoán liên kết tĩnh (Static Link Prediction) trên mạng đồ thị hai phía người dùng - thực thể (Bipartite User-Item Graphs) kết hợp với các thuộc tính định danh (Genres, Tags, Occupations, Cities).
  • Giới hạn: Chưa xử lý đồ thị động theo thời gian thực (Dynamic/Temporal Graphs) và giới hạn quy mô huấn luyện trên tập dữ liệu mức độ nhỏ/vừa (Small-scale benchmark).

Phân tích và thiết kế giải pháp

Phân tích hiện trạng

Các kỹ thuật dự đoán liên kết trải qua 4 thế hệ tiếp cận chính:

Phương pháp Đại diện tiêu biểu Ưu điểm Nhược điểm cốt lõi
Topology-based Heuristics Common Neighbors (CN), Jaccard (JC), Adamic-Adar (AA), Resource Allocation (RA) Tính toán nhanh, không cần tham số học, trực quan. Bỏ qua ngữ nghĩa nút, phụ thuộc hoàn toàn vào cấu trúc lân cận bậc 1-2, độ chính xác thấp khi đồ thị thưa.
Matrix Factorization SVD, SVD++, PMF Nắm bắt được biểu diễn ẩn (latent factors) của user và item, khử nhiễu tốt. Mô hình hóa tuyến tính thuần túy, không tích hợp được thuộc tính phi tuyến phức tạp và cấu trúc HIN.
Feature-based Deep Learning Factorization Machines (FM), NFM, DeepFM Tận dụng Bi-Interaction Layer và MLP để học tương tác bậc cao giữa các đặc trưng. Không bảo toàn cấu trúc không gian Topo đồ thị, dễ mất mát quan hệ ngữ nghĩa phân cấp.
Graph Neural Networks GAE, VGAE, SEAL, PEAGNN Tự động tổng hợp thông tin cấu trúc Topo cục bộ và toàn cục, nhúng thông tin Metapath đa hop. Chi phí tính toán lan truyền thông điệp (message passing) cao, đòi hỏi kỹ thuật lấy mẫu (sampling).

Phân tích yêu cầu hệ thống (MoSCoW)

  • Must have: Pipeline tiền xử lý HIN graph, bộ sinh đồ thị con cục bộ (Metapath-aware subgraph generator), mô hình PEAGNN với cơ chế Attention Fusion, module Negative Sampling tỷ lệ 1:4, hệ thống đánh giá $HR@10$ và $NDCG@10$.
  • Should have: Bộ so chuẩn baseline tích hợp SVD, SVD++, NFM; visualization biểu diễn vector embedding trước và sau dự đoán bằng t-SNE/PCA.
  • Could have: Đánh giá độ nhạy siêu tham số (Hyperparameter sensitivity analysis) cho độ dài metapath và số chiều latent dimensions ($d \in {32, 64, 128}$).
  • Won't have: Giao diện Web serving thời gian thực, module phân tán đồ thị quy mô terabyte (Distributed Graph Partitioning).

Thiết kế hệ thống

Kiến trúc hệ thống tiếp cận theo mô hình hướng module khép kín từ dữ liệu thô đến xếp hạng liên kết:

[Raw CSVs: MovieLens / Yelp] 
[Heterogeneous Information Network (HIN)]
[Metapath Subgraphs]   [Negative Sampler (1:4)]
(User-Movie-Genre-...)   (Unseen edges)
 [PEAGNN Deep Framework]
   [Top-10 Ranking Evaluation (HR@10, NDCG@10)]

Technology Stack và phiên bản cụ thể

  • Ngôn ngữ thực thi: Python 3.8.10
  • Deep Learning Framework: PyTorch 1.12.0 (hỗ trợ CUDA 11.6)
  • Graph Machine Learning: PyTorch Geometric (PyG) 2.1.0 / DGL 0.9.1
  • Phân tích và Xử lý dữ liệu: NumPy 1.23.1, Pandas 1.4.3, Scikit-learn 1.1.2
  • Xử lý đồ thị học thuật: NetworkX 2.8.4
  • Trực quan hóa: Matplotlib 3.5.2, Seaborn 0.11.2

Methodology & Project Timeline

Quy trình phát triển tuân theo mô hình CRISP-DM (Cross-Industry Standard Process for Data Mining) chia thành 5 giai đoạn:

Tuần 1-3   : Nghiên cứu lý thuyết Link Prediction, GNN, SEAL, NFM, PEAGNN.
Tuần 4-6   : Thu thập, khám phá dữ liệu (EDA), xây dựng Heterogeneous Graph.
Tuần 7-10  : Hiện thực thuật toán PEAGNN, tối ưu hàm mất mát và cơ chế Attention.
Tuần 11-13 : Huấn luyện, Tuning Hyperparameters, thực hiện Negative Sampling.
Tuần 14-16 : Đánh giá thực nghiệm HR@10, NDCG@10, viết báo cáo luận văn.

Implementation và kết quả

Development Process & Key Algorithms

Hệ thống triển khai 4 thành phần giải thuật nền tảng:

1. Metapath Aggregation Layer

Tổng hợp thông tin cấu trúc cục bộ dọc theo từng siêu đường dẫn $mp \in \mathcal{MP}$:

$$X_{mp}^{(l+1)} = \sigma \left( \tilde{D}{mp}^{-\frac{1}{2}} \tilde{A}{mp} \tilde{D}{mp}^{-\frac{1}{2}} X{mp}^{(l)} W_{mp}^{(l)} \right)$$

Trong đó $\tilde{A}{mp} = A{mp} + I_N$ là ma trận kề bổ sung self-loop của đồ thị con sinh bởi metapath $mp$, và $\tilde{D}_{mp}$ là ma trận bậc đường chéo tương ứng.

2. Metapath Fusion Layer với Semantic-level Attention

Hợp nhất biểu diễn từ nhiều metapath thông qua cơ chế Attention tự thích ứng:

$$c_v = \text{trace}(W^T H_v), \quad \text{với } H_v = [X_{mp_1}(v) ,|, X_{mp_2}(v) ,|, \dots ,|, X_{mp_P}(v)]$$

$$\alpha_{mp_i} = \frac{\exp(c_v^i)}{\sum_{j=1}^P \exp(c_v^j)}, \quad e_v = \sum_{i=1}^P \alpha_{mp_i} X_{mp_i}^{(L)}(v)$$

3. Prediction Layer & Optimization

Biểu diễn cặp $(u, i)$ được ghép nối $e_g = [e_u ,|, e_i]$ và đưa qua mạng MLP 2 tầng với hàm kích hoạt phi tuyến:

$$\hat{y}_{ui} = \sigma \left( w_2^T \cdot \text{ReLU}(w_1^T e_g + b_1) + b_2 \right)$$

Hàm mất mát Binary Cross-Entropy kết hợp lấy mẫu tiêu cực (Negative Sampling):

$$\mathcal{L} = -\sum_{(u, i) \in \mathcal{E}^+} \log(\hat{y}{ui}) - \sum{(u, j) \in \mathcal{E}^-} \log(1 - \hat{y}_{uj}) + \lambda |\Theta|_2^2$$

Trích dẫn cấu trúc mã nguồn cốt lõi (PEAGNN Implementation)

import torch
import torch.nn as nn
import torch.nn.functional as F
from torch_geometric.nn import GCNConv

class MetapathFusionLayer(nn.Module):
    """
    Module Semantic-level Attention hợp nhất đa siêu đường dẫn (Metapaths)
    """
    def __init__(self, in_channels: int, num_metapaths: int):
        super(MetapathFusionLayer, self).__init__()
        self.proj_weight = nn.Parameter(torch.Tensor(in_channels, num_metapaths))
        nn.init.xavier_uniform_(self.proj_weight)

    def forward(self, metapath_embeddings: list) -> torch.Tensor:
        # metapath_embeddings: Danh sách P tensors kích thước [N, in_channels]
        stacked = torch.stack(metapath_embeddings, dim=1) # [N, P, in_channels]
        
        # Tính toán attention score cho từng metapath
        weights = torch.matmul(stacked, self.proj_weight.mean(dim=1)) # [N, P]
        alpha = F.softmax(weights, dim=-1).unsqueeze(-1) # [N, P, 1]
        
        # Tổng hợp biểu diễn có trọng số
        fused_embedding = torch.sum(alpha * stacked, dim=1) # [N, in_channels]
        return fused_embedding

class PEAGNNPredictor(nn.Module):
    """
    Mô hình PEAGNN hoàn chỉnh cho bài toán Link Prediction
    """
    def __init__(self, in_features: int, hidden_dim: int, num_metapaths: int):
        super(PEAGNNPredictor, self).__init__()
        self.conv1 = GCNConv(in_features, hidden_dim)
        self.fusion = MetapathFusionLayer(hidden_dim, num_metapaths)
        
        # 2-layer MLP Classifier
        self.classifier = nn.Sequential(
            nn.Linear(hidden_dim * 2, hidden_dim),
            nn.ReLU(),
            nn.Dropout(p=0.2),
            nn.Linear(hidden_dim, 1),
            nn.Sigmoid()
        )

    def forward(self, x_list, edge_index_list, user_idx, item_idx):
        # 1. Lan truyền thông tin trên từng đồ thị con metapath
        mp_outs = []
        for x, edge_index in zip(x_list, edge_index_list):
            h = F.relu(self.conv1(x, edge_index))
            mp_outs.append(h)
            
        # 2. Hợp nhất qua cơ chế Attention
        fused_nodes = self.fusion(mp_outs)
        
        # 3. Lấy embedding của cặp User-Item mục tiêu
        u_emb = fused_nodes[user_idx]
        i_emb = fused_nodes[item_idx]
        pair_representation = torch.cat([u_emb, i_emb], dim=-1)
        
        # 4. Dự đoán xác suất liên kết
        return self.classifier(pair_representation).squeeze(-1)

Testing và Validation

Quá trình kiểm thử áp dụng chiến lược Leave-One-Out Cross Validation kết hợp Negative Sampling tỷ lệ $1:4$ (với mỗi liên kết dương thực tế, ghép kèm 4 liên kết âm chưa từng xuất hiện để tạo thành tập xếp hạng candidate pool).

   (Negative Sampling 1:4 Unseen Items)
 Candidate List = [Movie_109 (Pos), Movie_3 (Neg), Movie_55 (Neg), Movie_890 (Neg), Movie_12 (Neg)]
            (PEAGNN Scoring)
 Sorted Rank List: [1. Movie_109, 2. Movie_12, 3. Movie_55, 4. Movie_890, 5. Movie_3]
         (Evaluate Hit@10 & NDCG@10)

Kết quả đạt được

Bảng so sánh hiệu năng thực nghiệm giữa các kiến trúc trên hai bộ dữ liệu thực tế:

Mô hình Cơ chế đặc trưng MovieLens ($HR@10$) MovieLens ($NDCG@10$) Yelp2018 ($HR@10$) Yelp2018 ($NDCG@10$)
SVD Matrix Factorization 0.6241 0.3812 0.5120 0.3015
SVD++ MF + Implicit Feedback 0.6580 0.4105 0.5342 0.3228
NFM Non-linear Feature Interaction 0.7015 0.4628 0.5890 0.3710
PEAGNN (Đề xuất) Metapath-Aware GNN + Attention 0.7854 0.5476 0.6735 0.4482

Đánh giá định lượng:

  • Trên tập MovieLens Latest-small, PEAGNN vượt trội hơn mô hình SVD cổ điển +25.8% về HR@10 và +43.6% về NDCG@10; vượt qua mô hình học sâu NFM +11.9% về HR@10 và +18.3% về NDCG@10.
  • Trên tập Yelp2018, PEAGNN duy trì mức cải thiện +14.3% HR@10 so với NFM, khẳng định khả năng trích xuất thông tin ngữ nghĩa mạnh mẽ trên các đồ thị thưa và nhiều thuộc tính định danh.

Đổi mới và đóng góp

  1. Khai thác toàn diện ngữ nghĩa siêu đường dẫn (Metapath-Aware Semantic): Khác với các phương pháp GCN/GAT truyền thống chỉ coi mọi liên kết là đồng nhất, giải pháp xây dựng các metapath chuyên biệt:
    • Trên MovieLens: $\text{User} \xrightarrow{\text{rates}} \text{Movie} \xrightarrow{\text{has}} \text{Genre} \xrightarrow{\text{in}} \text{Movie} \xrightarrow{\text{rated_by}} \text{User}$
    • Trên Yelp: $\text{User} \xrightarrow{\text{reviews}} \text{Business} \xrightarrow{\text{located_in}} \text{City} \xrightarrow{\text{has}} \text{Business}$
  2. Cơ chế Softmax Semantic-level Attention tự thích ứng: Tự động gán trọng số tối ưu cho từng metapath dựa trên ngữ cảnh thực tế của từng cặp nút thay vì cố định trọng số thủ công.
  3. Giải quyết triệt để vấn đề Over-smoothing và Sparsity: Bằng việc trích xuất đồ thị con cục bộ và áp dụng Negative Sampling cân bằng ($1:4$), mô hình duy trì tính phân biệt (distinctiveness) của vector nhúng ngay cả ở các bậc lan truyền sâu.

Ứng dụng thực tế và triển khai

Kịch bản ứng dụng trong doanh nghiệp

  • Nền tảng Streaming/VOD (Video on Demand): Gợi ý cá nhân hóa danh sách phim cho người dùng mới dựa trên thông tin thể loại và đạo diễn (giảm thiểu bài toán Cold-start).
  • Mạng xã hội và Đánh giá địa điểm (Location-based Social Networks): Dự đoán địa điểm ăn uống, dịch vụ mà người dùng có xu hướng ghé thăm tiếp theo dựa trên liên kết địa lý và cộng đồng lân cận.
  • Thương mại điện tử (E-Commerce): Tối ưu hóa tỷ lệ chuyển đổi Click-Through-Rate (CTR) bằng cách dự đoán các liên kết mua sắm chéo (Cross-selling).
[JSON Payload Response: List[Item_ID, Confidence_Score]]

Chiến lược triển khai và độ phức tạp

  • Độ phức tạp tính toán: Quá trình huấn luyện đạt $\mathcal{O}(|\mathcal{MP}| \cdot |\mathcal{E}| \cdot d + |\mathcal{V}| \cdot d^2)$, trong đó $|\mathcal{MP}|$ là số lượng metapaths ($P \le 5$), $d$ là số chiều vector embedding ($d=64$). Thời gian suy luận (Inference latency) đạt dưới 15ms/request trên môi trường GPU đơn lẻ.
  • Yêu cầu phần cứng tối thiểu:
    • Huấn luyện (Training): CPU 8 Cores, RAM 16GB, GPU NVIDIA RTX 2060 6GB VRAM trở lên.
    • Triển khai (Serving): CPU 4 Cores, RAM 8GB (hoặc AWS EC2 g4dn.xlarge).

Hạn chế và hướng phát triển

Hạn chế kỹ thuật

  1. Thiết kế Metapath thủ công (Manual Metapath Selection): Hiệu năng mô hình phụ thuộc vào việc lựa chọn các lược đồ đường dẫn tiên nghiệm từ chuyên gia miền nghiệp vụ.
  2. Quy mô đồ thị tĩnh (Static Graph Constraint): Chưa tính toán trọng số suy giảm theo thời gian (temporal decay) khi hành vi và sở thích của người dùng biến đổi liên tục.

Hướng phát triển mở rộng

  • Tích hợp Tự động hóa Metapath: Sử dụng Reinforcement Learning hoặc Neural Architecture Search (NAS) để tự động sinh và lựa chọn các chuỗi quan hệ tối ưu trên đồ thị cực lớn.
  • Phát triển Dynamic/Temporal GNNs: Nâng cấp sang kiến trúc Continuous-Time Dynamic Graph (như TGN, TGAT) để nắm bắt biến động tương tác theo chuỗi thời gian thực.

Đối tượng hưởng lợi

  • Sinh viên & Học viên cao học: Cung cấp tài liệu tham khảo chi tiết, có cấu trúc chuẩn mực về việc ứng dụng Graph Deep Learning vào bài toán RecSys và Link Prediction.
  • Kỹ sư AI / Machine Learning Engineers: Bản thiết kế kiến trúc chuẩn, mã nguồn mô-đun hóa với PyTorch Geometric, dễ dàng đóng gói và tích hợp vào các pipeline gợi ý thực tế.
  • Doanh nghiệp vừa và nhỏ (SMEs): Giải pháp hệ thống gợi ý mã nguồn mở hiệu năng cao, chi phí bản quyền 0 đồng, cải thiện tỷ lệ giữ chân người dùng (Retention Rate) và doanh thu bán hàng.

Câu hỏi thường gặp (FAQ)

1. Yêu cầu kỹ thuật cốt lõi để triển khai mã nguồn này là gì?

Hệ thống yêu cầu môi trường Python $\ge 3.8$, cài đặt PyTorch $1.12.0$ đi kèm các thư viện đồ thị chuyên dụng tương thích phiên bản CUDA: torch-geometric, torch-scatter, torch-sparse, và networkx.

2. Mô hình xử lý bài toán dữ liệu thưa (Data Sparsity) như thế nào?

PEAGNN giải quyết dữ liệu thưa bằng cách liên kết các nút thông qua mạng thông tin không đồng nhất (HIN). Khi hai nút không có tương tác trực tiếp, mô hình vẫn trích xuất được độ tương đồng ngữ nghĩa gián tiếp thông qua các thực thể trung gian như thể loại, nhãn (tags), hoặc cộng đồng chung.

3. Tại sao tỷ lệ Negative Sampling 1:4 được lựa chọn?

Tỷ lệ $1:4$ là điểm cân bằng thực nghiệm tối ưu giữa việc tránh quá khớp (over-fitting) và duy trì thời gian hội tụ của hàm mất mát. Tỷ lệ lấy mẫu âm quá thấp gây thiên vị lớp dương, trong khi tỷ lệ quá cao làm chậm quá trình huấn luyện và gây nhiễu gradient.

4. Chi phí tính toán khi mở rộng sang đồ thị hàng triệu nút?

Khi mở rộng sang đồ thị lớn (Large-scale graphs), cần kết hợp thuật toán lấy mẫu đồ thị con theo đợt như NeighborSampler hoặc Cluster-GCN để giới hạn số lượng láng giềng lan truyền, giúp mức sử dụng bộ nhớ VRAM duy trì ở mức $\mathcal{O}(B \cdot d)$ cố định cho mỗi batch.

5. Điểm khác biệt mấu chốt giữa NFM và PEAGNN là gì?

NFM chỉ mô hình hóa tương tác phi tuyến tính giữa các vector đặc trưng phẳng (flat features) qua Bi-Interaction Pooling. Ngược lại, PEAGNN bảo toàn cấu trúc liên kết Topo không gian đa bậc và nắm bắt ngữ nghĩa quan hệ phân cấp sâu thông qua cơ chế Attention trên đồ thị con Metapath.

Kết luận

Khóa luận tốt nghiệp "Nghiên cứu phương pháp dự đoán liên kết trong mạng xã hội dựa trên mạng neuron đồ thị" của nhóm tác giả Chu Xuân Sơn và Nguyễn Hoàng Long (dưới sự hướng dẫn của TS. Cao Thị Nhạn - UIT) đã hệ thống hóa và chứng minh tính ưu việt vượt trội của Graph Neural Networks trong bài toán Link Prediction. Thông qua mô hình PEAGNN, nghiên cứu đã kết hợp thành công ngữ nghĩa đa tầng của siêu đường dẫn (Metapath) với cơ chế tập trung (Attention Fusion), mang lại bước nhảy vọt về độ chính xác xếp hạng ($HR@10$ đạt $0.7854$ trên MovieLens và $0.6735$ trên Yelp2018). Đây là nền tảng kỹ thuật vững chắc cho việc triển khai các hệ thống gợi ý cá nhân hóa thế hệ mới trong thực tế.