Thuật toán Leiden: Phát hiện cộng đồng trong GraphRAG Global Search

Mở đầu

Nếu bạn từng đọc paper GraphRAG của Microsoft, hoặc tò mò tại sao Global Search trả lời được các câu hỏi tổng quát ("chủ đề chính của tài liệu là gì?") thay vì chỉ tìm đoạn văn bản gần giống nhất, câu trả lời nằm ở một bước ít được nhắc tới: community detection trên đồ thị tri thức. Và thuật toán đứng sau bước đó chính là Leiden.

Bài viết dựa trên paper gốc: "From Louvain to Leiden: guaranteeing well-connected communities" (Traag, Waltman, van Eck, 2019) — arXiv:1810.08473.

1. Bài toán: chia đồ thị thành các community

Trong một mạng lưới (đồ thị), các node thường không phân bố đều mà có xu hướng tụ lại thành từng cụm dày đặc — gọi là community. Bài toán community detection là tìm ra các cụm này mà không biết trước cấu trúc.

Cách phổ biến nhất để đánh giá "một cách chia có tốt không" là dùng một hàm chất lượng (quality function). Hai hàm phổ biến:

Modularity:

H = (1/2m) · Σ_c [ e_c − γ·K_c²/(2m) ]

CPM (Constant Potts Model) — công thức đơn giản và trực quan hơn, được paper này dùng làm nền tảng chứng minh:

H = Σ_c [ e_c − γ·C(n_c, 2) ]

Trong đó e_c là số cạnh thực tế trong community c, n_c là số node, và γ (resolution parameter) đóng vai trò như một ngưỡng mật độ: community nên có mật độ cạnh nội bộ ít nhất bằng γ, còn mật độ giữa 2 community khác nhau phải thấp hơn γ. γ càng cao, thuật toán tìm ra càng nhiều community nhỏ.

Tối ưu hàm này là bài toán NP-hard, nên trong thực tế người ta dùng các thuật toán tham lam (heuristic) — nổi tiếng nhất là Louvain.

2. Louvain hoạt động thế nào, và vấn đề của nó

Louvain lặp qua 2 bước đơn giản:

1. Di chuyển node: xét từng node, chuyển nó sang community lân cận nào giúp tăng H nhiều nhất.
2. Gộp mạng: biến mỗi community vừa tìm được thành một "siêu node" duy nhất, tạo ra đồ thị thu gọn (aggregate graph), rồi lặp lại bước 1 trên đồ thị mới này.

Quá trình lặp lại cho tới khi không còn cách di chuyển nào giúp tăng H nữa. Louvain nổi tiếng vì đơn giản, nhanh, và cho kết quả tốt — nó là một trong những thuật toán được trích dẫn nhiều nhất trong lĩnh vực này.

Lỗ hổng nghiêm trọng: disconnected community

Đây là phát hiện chính của paper. Louvain có một điểm yếu: vì nó chỉ xét việc di chuyển từng node một cách độc lập, nó có thể vô tình tạo ra community không còn liên thông (disconnected) — tức là 2 phần trong cùng một community chỉ có thể "đi tới nhau" bằng cách đi vòng ra ngoài community.

Cơ chế gây lỗi: giả sử node 0 đóng vai trò "cầu nối" giữa 2 cụm nhỏ trong cùng community đỏ. Ở một bước nào đó, Louvain phát hiện node 0 hợp với một community khác hơn (vì nó có nhiều liên kết ngoài), nên di chuyển nó đi. Vấn đề: các node còn lại (1-6) không được xét lại — chúng vẫn "đủ tốt" ở vị trí hiện tại xét theo từng node riêng lẻ, dù toàn bộ community giờ đã đứt làm đôi.

Thực nghiệm trên các mạng thực tế cho thấy con số đáng báo động:

• Tới 25% community bị kết nối kém (badly connected)
• Tới 16% community bị đứt hẳn (disconnected), đặc biệt tệ hơn khi lặp thuật toán nhiều vòng

Nghịch lý: lặp Louvain nhiều lần được kỳ vọng sẽ cải thiện kết quả, nhưng thực tế lại làm trầm trọng thêm vấn đề disconnected community, dù hàm chất lượng H vẫn tăng đều — vì Louvain hoàn toàn không có cơ chế "sửa sai" cho những community đã bị đứt sau khi gộp mạng.

Về mặt lý thuyết, Louvain chỉ đảm bảo được một điều: không còn 2 community nào gộp lại mà có lợi (gọi là γ-separation). Nó không đảm bảo tính liên thông.

3. Leiden: thêm một bước "kiểm tra lại"

Leiden giữ nguyên tinh thần của Louvain nhưng chèn thêm giai đoạn thứ ba vào giữa: sau khi di chuyển node xong, đừng vội tin — hãy vào từng community, thử tách lại từ đầu, và chỉ cho gộp nếu liên kết đủ chặt.

Giai đoạn 1 — Di chuyển node nhanh (MoveNodesFast)

Về bản chất giống Louvain, nhưng hiệu quả hơn nhờ dùng hàng đợi (queue): thay vì quét lại toàn bộ node mỗi vòng như Louvain, Leiden khởi tạo hàng đợi chứa tất cả node theo thứ tự ngẫu nhiên. Mỗi lần một node được di chuyển, chỉ những hàng xóm của nó chưa cùng community mới mới được đẩy vào hàng đợi để xét lại. Nhờ vậy sau lần quét đầu tiên, các vòng sau chỉ cần xét những node thực sự "bị ảnh hưởng" — đây là lý do chính khiến Leiden nhanh hơn Louvain đáng kể, đặc biệt trên mạng lớn.

Giai đoạn 2 — Tinh chỉnh phân vùng (RefinePartition)

Đây là phần cốt lõi giải quyết vấn đề của Louvain. Với mỗi community C tìm được ở giai đoạn 1:

1. Bắt đầu lại từ phân vùng "mỗi node một community riêng", chỉ trong phạm vi C.
2. Chỉ xét các node đủ "liên kết tốt" với phần còn lại của C (thoả điều kiện mật độ tối thiểu γ).
3. Với mỗi node đủ điều kiện, không chọn tham lam community tốt nhất — mà chọn ngẫu nhiên có trọng số trong số các lựa chọn làm tăng H, xác suất tỉ lệ thuận với exp(ΔH/θ). Tham số θ (paper dùng θ=0.01) kiểm soát mức độ ngẫu nhiên: θ nhỏ gần giống tham lam, θ lớn ngẫu nhiên hơn.

Kết quả: một community "tưởng là 1 khối" ở bước 1 có thể bị phát hiện và tách thành nhiều community con ở bước này — chính là cách Leiden phát hiện và sửa các trường hợp như node 0 ở ví dụ trên.

Vì sao phải ngẫu nhiên? Đây là chi tiết hay bị bỏ qua. Paper chứng minh bằng phản ví dụ cụ thể (Appendix C.2): nếu luôn chọn tham lam, có những phân vùng tối ưu không bao giờ đạt tới được — vì 2 node có liên kết rất mạnh sẽ luôn bị dính chung dù phân vùng tối ưu yêu cầu tách chúng ra các community khác nhau. Thêm chút ngẫu nhiên mở ra khả năng "thử" các lựa chọn tốt (không nhất thiết tốt nhất), giúp thuật toán không bị kẹt ở cực trị địa phương.

Giai đoạn 3 — Gộp mạng (AggregateGraph)

Giống Louvain về hình thức, nhưng khác biệt quan trọng: đồ thị gộp được xây dựa trên phân vùng đã tinh chỉnh (P_refined) từ giai đoạn 2, chứ không phải phân vùng gốc từ giai đoạn 1. Điều này cho thuật toán "nhiều chỗ trống" hơn để tìm ra phân vùng tốt ở các vòng lặp tiếp theo — vì partition khởi tạo cho vòng sau vẫn dựa trên P (không phải P_refined), giữ được thông tin từ cả 2 mức độ chi tiết.

4. Các đảm bảo toán học — điều làm nên tên tuổi Leiden

Đây là phần khiến Leiden khác một "thủ thuật kỹ thuật" thông thường — mọi tính chất đều có chứng minh đi kèm.

Thời điểm	Đảm bảo	Ý nghĩa thực tế
Sau mỗi vòng lặp	γ-separation	Không còn 2 community nào có lợi khi gộp (Louvain cũng có)
Sau mỗi vòng lặp	γ-connectivity	Community chắc chắn liên thông — Louvain không có
Vòng lặp ổn định	Node optimality	Không node đơn lẻ nào có lợi khi đổi community
Vòng lặp ổn định	Subpartition γ-density	Không tập con lớn nào muốn tách hẳn ra
Hội tụ tiệm cận	Uniform γ-density	Chia kiểu gì thì 2 phần vẫn liên kết đủ chặt
Hội tụ tiệm cận	Subset optimality	Mọi tập con bất kỳ đều được gán tối ưu — đảm bảo mạnh nhất

Chứng minh γ-connectivity dùng kỹ thuật quy nạp theo tầng gộp: mỗi lần một node được thêm vào tập đang gộp trong giai đoạn tinh chỉnh, điều kiện bắt buộc là nó phải liên kết đủ chặt với toàn bộ phần đã gộp trước đó (không chỉ với 1 node lẻ) — nên tại mọi thời điểm xây dựng, tập đang có luôn liên thông đủ mạnh. Quy nạp qua các tầng cho ra kết quả đúng ở tầng cao nhất.

Đảm bảo mạnh nhất — subset optimality — chỉ đạt được khi lặp thuật toán đủ nhiều lần (không phải chỉ 1 lần chạy). Khác với Louvain (khi đạt trạng thái ổn định thì mọi vòng lặp sau đều ổn định), Leiden có thể tiếp tục cải thiện phân vùng sau một vòng lặp ổn định, nhờ tính ngẫu nhiên ở giai đoạn tinh chỉnh mở ra khả năng khám phá thêm.

5. Kết quả thực nghiệm

Trên 6 mạng dữ liệu thực tế (DBLP, Amazon, IMDB, Live Journal, Web of Science, Web UK), so với Louvain:

• Nhanh hơn: tới 20 lần trên mạng lớn (Web UK, ~39 triệu node)
• Chất lượng cao hơn: modularity tối đa cao hơn ở tất cả 6 mạng
• Tỷ lệ disconnected community = 0% (đảm bảo toán học, không phải quan sát thực nghiệm)

Điều thú vị: với các mạng phức tạp như Web of Science, Leiden cần trung bình hơn 750 vòng lặp mới đạt trạng thái ổn định hoàn toàn — nhưng vòng lặp đầu tiên (tốn kém nhất) mất khoảng 110-120 giây, còn các vòng sau chỉ khoảng 40 giây nhờ cơ chế fast local move.

6. Liên hệ thực tế: vì sao GraphRAG cần đúng Leiden

Nếu bạn triển khai hệ thống dạng GraphRAG (đồ thị tri thức trích xuất từ văn bản bằng LLM, rồi phân cụm để tóm tắt), đây là lý do Leiden — không phải một thuật toán clustering bất kỳ — được chọn:

• Global Search không tìm theo similarity như RAG thông thường. Nó lấy "community report" (bản tóm tắt do LLM sinh ra cho từng cụm entity), chia batch, cho LLM trả lời từng batch (map), rồi tổng hợp (reduce). Nếu community bị disconnected, report sẽ tóm tắt những entity chẳng liên quan gì vào chung một báo cáo — làm câu trả lời tổng hợp bị loãng hoặc sai lệch.
• Cấu trúc phân tầng (hierarchy) trong GraphRAG chính là các tầng gộp (aggregate graph) của Leiden — tầng dưới chi tiết, tầng trên khái quát. Câu hỏi tổng quát dùng report ở tầng cao; câu hỏi cụ thể lùi xuống tầng thấp.
• Tham số γ (resolution) ánh xạ trực tiếp tới độ "thô/mịn" của các tầng report: γ cao → nhiều cụm nhỏ, report chi tiết nhưng tốn nhiều lượt gọi LLM để tóm tắt hơn.

Nếu report của bạn từng "gộp nhầm" các entity chẳng liên quan, nhiều khả năng là do resolution parameter chưa phù hợp — không phải do bản thân thuật toán, vì tính liên thông đã được đảm bảo bằng toán học.

7. Dùng thử bằng Python

Thư viện leidenalg (do chính tác giả paper phát triển) hoặc graspologic (Microsoft dùng trong GraphRAG) đều triển khai thuật toán này:

import leidenalg as la
import igraph as ig

# Xây đồ thị từ danh sách cạnh
g = ig.Graph.TupleList(edges, weights=True)

# Chạy Leiden với CPM, resolution càng cao càng nhiều cụm nhỏ
partition = la.find_partition(
    g,
    la.CPMVertexPartition,
    resolution_parameter=0.05,
    n_iterations=-1,  # -1 nghĩa là lặp tới khi hội tụ (asymptotically stable)
)

print(f"Số community: {len(partition)}")

Lưu ý: n_iterations=-1 chính là cách để đạt đảm bảo mạnh nhất (subset optimality) mà bài báo chứng minh — nếu chỉ chạy 1 vòng, bạn chỉ có γ-connectivity, chưa chắc đã tối ưu ở mức tập con.

Kết luận

Leiden không phải một cải tiến nhỏ về tốc độ — nó sửa một lỗ hổng cấu trúc thực sự của Louvain (disconnected community) bằng cách thêm một bước tinh chỉnh có kiểm soát ngẫu nhiên, đồng thời đi kèm bộ chứng minh toán học đầy đủ cho từng mức đảm bảo. Đây là lý do nó trở thành lựa chọn mặc định trong các pipeline hiện đại như GraphRAG — không chỉ vì nhanh hơn, mà vì kết quả đáng tin cậy hơn để xây dựng các bước tiếp theo (như tóm tắt bằng LLM) lên trên.

---

Tài liệu tham khảo: Traag, V.A., Waltman, L., van Eck, N.J. (2019). "From Louvain to Leiden: guaranteeing well-connected communities". arXiv:1810.08473