Khai Thác Đồ Thị Con Trên Đồ Thị Có Trọng Số - Luận Án Tiến Sĩ Khoa Học Máy Tính

Luận án tiến sĩ nghiên cứu khai thác đồ thị con trên đồ thị có trọng số, ứng dụng trong khoa học máy tính và tối ưu hóa thuật toán.

• Tác giả: Lê Thị Ngọc Thảo
• Người hướng dẫn: Lê Hoài Bắc
• Trường học: Đại học Quốc gia Thành phố Hồ Chí Minh
• Chuyên ngành: Khoa học máy tính
• Đề tài: Khai Thác Đồ Thị Con Trên Đồ Thị Có Trọng Số
• Loại tài liệu: Luận án tiến sĩ
• Năm xuất bản: 2023
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• 1. PHẦN MỞ ĐẦU
• 1.1. Giới thiệu chung về khai thác dữ liệu đồ thị
• 1.2. Bài toán khai thác đồ thị con phổ biến
• 1.3. Các hướng tiếp cận khai thác đồ thị con phổ biến
• 1.4. Bố cục của luận án
• 2. CƠ SỞ LÝ THUYẾT VỀ KHAI THÁC ĐỒ THỊ CON TRÊN ĐỒ THỊ CÓ TRỌNG SỐ
• 2.1. Các định nghĩa cơ bản về lý thuyết đồ thị
• 2.2. Thuật toán WeGraMi
• 2.3. Cơ sở lý thuyết về độ đo MaxMin
• 2.4. Độ phức tạp của thuật toán WeGraMi
• 2.5. Cơ sở dữ liệu và môi trường thực nghiệm
• 2.6. Thuật toán OWGraMi
• 2.7. Tia danh sách cạnh phổ biến
• 2.8. Xác định trọng số các đồ thị con dựa trên trọng số của đồ thị cha
• 2.9. Độ phức tạp của thuật toán OWGraMi
• 2.10. Kết chương
• 3. PHƯƠNG PHÁP MỞ RỘNG KHAI THÁC ĐỒ THỊ CON TRÊN ĐỒ THỊ CÓ TRỌNG SỐ
• 3.1. Giới thiệu hướng tiếp cận theo chiến lược áp dụng độ đo trung bình để tính trọng số
• 3.2. Cơ sở lý thuyết về chiến lược AveMin trong thuật toán AWeGraMi
• 3.3. Thuật toán AWeGraMi
• 3.4. Độ phức tạp của thuật toán AWeGraMi
• 3.5. Cơ sở dữ liệu và môi trường thực nghiệm
• 3.6. Kết chương
• DANH MỤC CÁC KÝ HIỆU, THUẬT NGỮ, CHỮ VIẾT TẮT
• DANH MỤC CÁC BẢNG BIỂU
• DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ

Tóm tắt

I. Tổng Quan Khai Thác Đồ Thị Con Trên Đồ Thị Có Trọng Số

Trong bối cảnh dữ liệu lớn (Big Data) ngày càng phát triển, việc khai thác hiệu quả dữ liệu đồ thị trở nên vô cùng quan trọng. Cơ sở dữ liệu đồ thị là lựa chọn tối ưu để tổ chức và lưu trữ các tập dữ liệu phức tạp, đặc biệt là các dữ liệu có kết nối. Mô hình đồ thị có trọng số được sử dụng rộng rãi để mô phỏng các mối quan hệ phức tạp giữa các đối tượng với mức độ quan trọng khác nhau. Bài toán khai thác các đồ thị con có trọng số từ một đồ thị lớn trở thành bài toán quan trọng trong nhiều lĩnh vực khoa học. Chủ đề này thu hút nhiều nghiên cứu, đặc biệt khi chỉ có thể sử dụng đồ thị lớn có trọng số để biểu diễn sự khác biệt giữa các đối tượng.

1.1. Giới thiệu về Khai Thác Dữ Liệu Đồ Thị

Khai thác dữ liệu đồ thị trở thành tâm điểm trong khai thác dữ liệu lớn. Thay vì tập trung vào giá trị dữ liệu, khai thác dữ liệu đồ thị tập trung vào mối liên hệ giữa các điểm dữ liệu. Điều này đặc biệt quan trọng với dữ liệu lớn, đa dạng và có kết nối. Mô hình đồ thị lớn có trọng số mô phỏng các mối quan hệ phức tạp có mức độ quan trọng khác nhau, ví dụ như tầm quan trọng của một cá nhân trong mạng xã hội hoặc mức độ lưu thông trên bản đồ. Khai phá tri thức từ đồ thị giúp truy vấn những câu hỏi phức tạp, vượt ra ngoài kết nối dữ liệu ban đầu.

1.2. Bài Toán Khai Thác Đồ Thị Con Phổ Biến FSM

Bài toán tìm kiếm đồ thị con trên đồ thị có trọng số được đề xuất lần đầu bởi Cook và Holder. Khai thác đồ thị con phổ biến (FSM) là một bài toán tâm điểm trong lĩnh vực khai thác dữ liệu đồ thị. Đồ thị con là một đồ thị thu được từ đồ thị ban đầu bằng cách loại bỏ một số đỉnh và cạnh. Đồ thị con phổ biến có số lần xuất hiện trong một cơ sở dữ liệu đồ thị hoặc đồ thị lớn vượt ngưỡng cho trước. Giá trị ngưỡng này gọi là độ hỗ trợ tối thiểu (min-sup). Mục đích của FSM là khám phá tập dữ liệu đồ thị con xuất hiện thường xuyên.

II. Thách Thức Trong Khai Thác Đồ Thị Con Có Trọng Số Lớn

Các thuật toán tìm đồ thị con đẳng cấu phổ biến đối mặt với hai thách thức: (1) xác định một đồ thị con của một đồ thị xuất hiện trong các đồ thị khác; (2) liệt kê hiệu quả tất cả các đồ thị con phổ biến. Số lượng các đồ thị con tăng theo kích thước của nó và đồ thị. Do đó, cần các thuật toán hiệu quả để xử lý cơ sở dữ liệu đồ thị lớn, cấu trúc phức tạp. Hai chiến lược chính: phát sinh ứng viên và tăng trưởng mẫu. Mỗi chiến lược có ưu và nhược điểm riêng, đòi hỏi sự cân nhắc kỹ lưỡng trong việc lựa chọn thuật toán.

2.1. Đồ Thị Con Đẳng Cấu và Liệt Kê Hiệu Quả

Một trong những thách thức lớn nhất của khai thác đồ thị con gần đúng là xử lý đồ thị con đẳng cấu. Cần một phương pháp hiệu quả để xác định liệu một đồ thị con có tồn tại trong một đồ thị lớn hơn. Việc liệt kê tất cả các đồ thị con phổ biến cũng rất tốn kém về mặt tính toán. Các thuật toán cần phải được thiết kế để tránh liệt kê các đồ thị con dư thừa và tối ưu hóa quá trình tìm kiếm.

2.2. Chiến Lược Phát Sinh Ứng Viên và Tăng Trưởng Mẫu

Chiến lược phát sinh ứng viên kết hợp các đồ thị con có cùng kích thước để tạo thành một đồ thị con ứng viên lớn hơn. Chiến lược tăng trưởng mẫu mở rộng một đồ thị con phổ biến bằng cách thêm một cạnh phụ. Cả hai chiến lược đều có ưu và nhược điểm riêng. Phát sinh ứng viên có thể tốn kém về mặt tính toán, trong khi tăng trưởng mẫu có thể dẫn đến sự trùng lặp trong quá trình tạo ứng viên. Cần sự kết hợp của cả hai chiến lược để đạt được hiệu quả cao nhất.

2.3. Tính Chất Bao Đóng Giảm DCP và Bài Toán Khai Thác

Tính chất bao đóng giảm (DCP) không còn thỏa mãn trong bài toán khai thác đồ thị con phổ biến trên đồ thị có trọng số. Điều này làm cho các thuật toán sử dụng trong WARM và WSM ít được sử dụng trong khai thác đồ thị con phổ biến vì không thể kiểm soát quá trình phát sinh tập ứng viên. Tuy nhiên, ý tưởng của WARM vẫn được vận dụng vào thuật toán khai thác đồ thị con có trọng số trên cạnh.

III. Thuật Toán WeGraMi Khai Thác Đồ Thị Con Trọng Số Hiệu Quả

Luận án đề xuất phương pháp tiếp cận mới để khai thác đồ thị con trên đồ thị có trọng số. Phương pháp này sử dụng độ đo MaxMin để tính trọng số cho đồ thị con. Thuật toán khai thác đồ thị con có trọng số WeGraMi được thiết kế để cắt tỉa không gian tìm kiếm dựa vào trọng số của đồ thị con, giúp giảm đáng kể chi phí tính toán. WeGraMi cung cấp giải pháp hiệu quả để khai thác đồ thị con phổ biến trong các đồ thị có trọng số lớn, phức tạp. Các bước triển khai thuật toán WeGraMi bao gồm tính độ hỗ trợ đầy đủ của một đồ thị con và sử dụng chiến lược MaxMin.

3.1. Cơ Sở Lý Thuyết Về Độ Đo MaxMin

Độ đo MaxMin được sử dụng để tính trọng số cho đồ thị con. Việc sử dụng MaxMin giúp đảm bảo rằng trọng số của đồ thị con phản ánh chính xác mức độ quan trọng của nó trong đồ thị lớn. MaxMin tập trung vào giá trị nhỏ nhất, giá trị lớn nhất và trung bình của các cạnh và đỉnh. Thuật toán tính độ đo trung tâm trong đồ thị đảm bảo trọng số của đồ thị con không bị ảnh hưởng bởi các đỉnh hoặc cạnh có trọng số thấp.

3.2. Cắt Tỉa Không Gian Tìm Kiếm Bằng Trọng Số

WeGraMi cắt tia không gian tìm kiếm dựa vào trọng số của đồ thị con. Điều này giúp giảm đáng kể số lượng các đồ thị con cần được xem xét, từ đó giảm chi phí tính toán. WeGraMi sử dụng ngưỡng trọng số để loại bỏ các đồ thị con không phổ biến, làm cho quá trình khai thác hiệu quả hơn. Độ phức tạp của khai thác đồ thị con trên đồ thị có trọng số cũng được giảm tải nhờ cơ chế này.

3.3. Mô Tả Chi Tiết Thuật Toán WeGraMi

Thuật toán WeGraMi bao gồm các bước sau: (1) Tính độ hỗ trợ đầy đủ của một đồ thị con. (2) Sử dụng chiến lược MaxMin để tính trọng số cho đồ thị con. (3) Cắt tia không gian tìm kiếm dựa vào trọng số của đồ thị con. (4) Lặp lại các bước trên cho đến khi tất cả các đồ thị con phổ biến được tìm thấy. Chi tiết về code cũng như các biến thể của thuật toán được mô tả trong luận án.

IV. Tối Ưu Hóa Thuật Toán WeGraMi OWGraMi AWeGraMi

Luận án giới thiệu các thuật toán tối ưu hóa WeGraMi, bao gồm OWGraMi và AWeGraMi, để cải thiện hiệu suất khai thác. OWGraMi sử dụng tia danh sách cạnh phổ biến và xác định trọng số dựa trên đồ thị cha. AWeGraMi áp dụng độ đo trung bình (AveMin) để tính trọng số, kết hợp giới hạn chặn trên dựa trên chiến lược MaxMin. Các cải tiến này giúp tăng tốc độ khai thác và giảm yêu cầu bộ nhớ. Mô hình đồ thị có trọng số trở nên linh hoạt hơn khi sử dụng các thuật toán này.

4.1. Thuật Toán OWGraMi Sử Dụng Danh Sách Cạnh Phổ Biến

OWGraMi (Optimized WeGraMi) sử dụng tia danh sách cạnh phổ biến để giảm số lượng các đồ thị con cần được xem xét. OWGraMi xác định trọng số của các đồ thị con dựa trên trọng số của đồ thị cha, giúp giảm chi phí tính toán. OWGraMi đặc biệt hiệu quả khi khai thác các đồ thị lớn có nhiều cạnh phổ biến. Phân tích mạng xã hội bằng đồ thị có thể tận dụng OWGraMi để nhanh chóng tìm ra các cộng đồng quan trọng.

4.2. Thuật Toán AWeGraMi Chiến Lược Độ Đo Trung Bình AveMin

AWeGraMi (Averaged WeGraMi) sử dụng chiến lược AveMin để tính trọng số cho các đồ thị con phổ biến. AveMin tính trung bình trọng số của các cạnh và đỉnh, cung cấp một ước tính chính xác hơn về mức độ quan trọng của đồ thị con. AWeGraMi kết hợp giới hạn chặn trên dựa trên chiến lược MaxMin, giúp giảm không gian tìm kiếm và tăng tốc độ khai thác. Bioinformatics đồ thị có thể áp dụng AWeGraMi để phân tích các mạng lưới tương tác protein.

4.3. So sánh OWGraMi AWeGraMi và WeGraMi

Mỗi thuật toán đều có ưu điểm riêng. WeGraMi là thuật toán cơ bản, OWGraMi tối ưu hóa bằng danh sách cạnh phổ biến và AWeGraMi tối ưu hóa bằng độ đo trung bình. Việc lựa chọn thuật toán phụ thuộc vào đặc điểm của đồ thị đầu vào. Ví dụ, OWGraMi hiệu quả với đồ thị có nhiều cạnh phổ biến, trong khi AWeGraMi hiệu quả hơn với đồ thị có trọng số phân bố không đều.

V. Ứng Dụng Kết Quả Nghiên Cứu Khai Thác Đồ Thị Con Trọng Số

Các thuật toán khai thác đồ thị con trọng số, đặc biệt là WeGraMi, OWGraMi và AWeGraMi, có ứng dụng rộng rãi trong nhiều lĩnh vực. Phân tích mạng xã hội, hệ hỗ trợ ra quyết định, phân tích dữ liệu và phát sinh luật kết hợp là những lĩnh vực hưởng lợi từ nghiên cứu này. Kết quả thực nghiệm cho thấy các thuật toán đề xuất có hiệu suất cao hơn so với các phương pháp hiện có, đặc biệt là trên các tập dữ liệu lớn và phức tạp. Machine learning đồ thị cũng tận dụng các kết quả nghiên cứu này.

5.1. Ứng Dụng Trong Phân Tích Mạng Xã Hội

Trong phân tích mạng xã hội, các thuật toán khai thác đồ thị con trọng số có thể được sử dụng để xác định các cộng đồng, tìm kiếm các cá nhân có ảnh hưởng và phát hiện các xu hướng. Trọng số cạnh có thể biểu diễn mức độ tương tác giữa các cá nhân, trong khi trọng số đỉnh có thể biểu diễn mức độ quan trọng của một cá nhân trong mạng. Các thuật toán này giúp hiểu rõ hơn về cấu trúc và động lực của mạng xã hội.

5.2. Ứng Dụng Trong Hệ Hỗ Trợ Ra Quyết Định

Trong hệ hỗ trợ ra quyết định, các thuật toán khai thác đồ thị con trọng số có thể được sử dụng để tìm kiếm các mẫu và mối quan hệ quan trọng trong dữ liệu. Các mẫu này có thể giúp người ra quyết định hiểu rõ hơn về tình hình và đưa ra các quyết định tốt hơn. Ví dụ, trong lĩnh vực tài chính, các thuật toán này có thể được sử dụng để phát hiện các gian lận và đánh giá rủi ro.

5.3. Kết Quả Thực Nghiệm và Đánh Giá Hiệu Năng

Kết quả thực nghiệm cho thấy các thuật toán WeGraMi, OWGraMi và AWeGraMi có hiệu suất cao hơn so với các phương pháp hiện có. Các thuật toán này có thể xử lý các tập dữ liệu lớn và phức tạp trong thời gian ngắn. OWGraMi và AWeGraMi đặc biệt hiệu quả khi khai thác các đồ thị có nhiều cạnh phổ biến hoặc trọng số phân bố không đều. Data Mining đồ thị ngày càng hiệu quả hơn nhờ những nghiên cứu này.

VI. Kết Luận Hướng Phát Triển Khai Thác Đồ Thị Con

Luận án đã trình bày một phương pháp hiệu quả để khai thác đồ thị con thuộc tính trên đồ thị có trọng số. Các thuật toán WeGraMi, OWGraMi và AWeGraMi cung cấp các giải pháp mạnh mẽ để giải quyết bài toán quan trọng này. Hướng phát triển trong tương lai bao gồm khai thác trên đồ thị động, đồ thị lớn, đồ thị thưa và đồ thị dày. Nghiên cứu này mở ra nhiều cơ hội cho các ứng dụng thực tế và đóng góp vào sự phát triển của lĩnh vực khai thác dữ liệu đồ thị.

6.1. Tóm Tắt Các Đóng Góp Chính Của Luận Án

Luận án đóng góp vào lĩnh vực khai thác dữ liệu đồ thị bằng cách đề xuất một phương pháp hiệu quả để khai thác đồ thị con trọng số. Các thuật toán WeGraMi, OWGraMi và AWeGraMi cung cấp các giải pháp mạnh mẽ để giải quyết bài toán quan trọng này. Nghiên cứu này cũng cung cấp các kết quả thực nghiệm chứng minh hiệu suất của các thuật toán đề xuất.

6.2. Hướng Nghiên Cứu Tương Lai Đồ Thị Động và Đồ Thị Lớn

Hướng nghiên cứu trong tương lai bao gồm khai thác trên đồ thị động, đồ thị lớn, đồ thị thưa và đồ thị dày. Khai thác trên đồ thị động đòi hỏi các thuật toán có thể xử lý sự thay đổi theo thời gian. Khai thác trên đồ thị lớn đòi hỏi các thuật toán có thể mở rộng quy mô và xử lý các tập dữ liệu lớn. Khai thác trên đồ thị thưa và đồ thị dày đòi hỏi các thuật toán có thể tận dụng cấu trúc của đồ thị để cải thiện hiệu suất. Tìm kiếm mẫu đồ thị sẽ trở nên quan trọng hơn khi kích thước đồ thị tăng lên.

6.3. Ứng Dụng Tiềm Năng và Kết Hợp Với Machine Learning

Nghiên cứu này mở ra nhiều cơ hội cho các ứng dụng thực tế trong nhiều lĩnh vực, bao gồm phân tích mạng xã hội, hệ hỗ trợ ra quyết định và phân tích dữ liệu. Ngoài ra, có thể kết hợp các thuật toán khai thác đồ thị con trọng số với các kỹ thuật machine learning để tạo ra các hệ thống thông minh hơn. Cắt đồ thị và các kỹ thuật độ đo gắn kết trong đồ thị sẽ giúp tạo ra những ứng dụng hiệu quả hơn.

Nội dung chính

Tổng quan luận án

Luận án tiến sĩ chuyên ngành Khoa học máy tính (mã số 62480101) của nghiên cứu sinh Lê Thị Ngọc Thảo, thực hiện tại Trường Đại học Khoa học Tự nhiên – Đại học Quốc gia Thành phố Hồ Chí Minh dưới sự hướng dẫn khoa học của PGS. Lê Hoài Bắc và TS. Võ Đình Bảy, bảo vệ năm 2023, tập trung vào đề tài "Khai thác đồ thị con trên đồ thị có trọng số".

Về tính cấp thiết và khoảng trống nghiên cứu, sự phát triển của dữ liệu lớn (Big Data) đòi hỏi các mô hình lưu trữ và xử lý phi truyền thống nhằm nắm bắt các mối liên kết phức tạp giữa các thực thể. Cơ sở dữ liệu đồ thị trở thành giải pháp tổ chức dữ liệu kết nối, trong đó mô hình đơn đồ thị lớn có gán trọng số được ứng dụng để mô phỏng tầm ảnh hưởng của tác nhân trong mạng xã hội, mật độ giao thông, mức độ ảnh hưởng của các nút mạng máy tính hay phân tích trích dẫn khoa học. Khai thác đồ thị con phổ biến (Frequent Subgraph Mining - FSM) là một nhánh trọng tâm trong khai thác dữ liệu đồ thị nhằm tìm kiếm các cấu trúc con lặp lại vượt ngưỡng hỗ trợ tối thiểu (min-sup).

Khoảng trống nghiên cứu được tác giả xác định từ thực tiễn: hầu hết các công trình nghiên cứu FSM có trọng số trước đây chủ yếu tập trung vào việc khai thác trên một tập hợp gồm nhiều đồ thị kích thước vừa và nhỏ (đa phần các bộ dữ liệu thực nghiệm có số đỉnh hoặc cạnh dưới 10.000), trong khi rất ít nghiên cứu giải quyết bài toán trên một đơn đồ thị kích thước lớn. Đồng thời, các nghiên cứu sẵn có chủ yếu khảo sát yếu tố trọng số trên cạnh, thiếu vắng các giải pháp xử lý trọng số đặt trên đỉnh đồ thị. Thêm vào đó, việc tích hợp yếu tố trọng số khiến tính chất bao đóng giảm (Downward Closure Property - DCP) không còn được thỏa mãn, làm cho không gian tìm kiếm bùng nổ theo cấp số nhân.

Để giải quyết khoảng trống này, luận án xác định mục tiêu nghiên cứu thông qua việc trả lời 3 câu hỏi nghiên cứu cụ thể:

• Câu hỏi 1: Có thể kế thừa từ thuật toán nào để xây dựng mô hình phù hợp với cơ sở dữ liệu đồ thị có trọng số?
• Câu hỏi 2: Nếu một đồ thị con phổ biến không thỏa ngưỡng trọng số thì tất cả các đồ thị con được phát sinh từ đồ thị con phổ biến này cũng không thỏa ngưỡng trọng số?
• Câu hỏi 3: Mỗi đỉnh trong đồ thị có trọng số. Vậy giá trị trọng số của một đồ thị sẽ được tính như thế nào?

Đối tượng nghiên cứu của luận án là đồ thị đơn vô hướng, có kích thước lớn, được gán nhãn đỉnh, nhãn cạnh và mang trọng số không âm trên các đỉnh ($W(u_i) \ge 0$). Phạm vi nghiên cứu giới hạn ở bài toán khai thác đồ thị con phổ biến có trọng số (ký hiệu là Bài toán - BT): cho trước một đồ thị $G = (V, E, L, W)$ và hai ngưỡng gồm ngưỡng phổ biến (min-sup, ký hiệu là $f$) và ngưỡng trọng số $w$, tìm tất cả các đồ thị con $S$ thuộc $G$ sao cho $S$ đồng thời thỏa mãn độ hỗ trợ tối thiểu và có trọng số $W(S) \ge w$. Các thuật nghiệm được đánh giá định lượng trên các tập dữ liệu mạng thực tế gồm MiCo, Facebook và CiteSeer.

Tổng quan tài liệu và vị trí của luận án

Luận án hệ thống hóa toàn diện các hướng nghiên cứu FSM từ khi bài toán được Cook và Holder khởi xướng vào các năm 1994 và 2000. Các thuật toán FSM truyền thống trên đồ thị không trọng số được phân loại thành hai nhóm chính:

• Nhóm thuật toán dựa trên tính chất Apriori: Tiêu biểu là AGM (Inokuchi, Washio, Motoda, 2000) tiếp cận dựa trên ma trận kề và tăng trưởng cấu trúc theo đỉnh; FSG (Kuramochi, Karypis, 2001) tiếp cận dựa trên danh sách kề và tăng trưởng cấu trúc theo cạnh. Nhóm này có hạn chế lớn là sinh và kiểm tra ứng viên dẫn đến số lượng ứng viên bùng nổ theo hàm mũ, đồng thời phải duyệt cơ sở dữ liệu nhiều lần để kiểm tra độ hỗ trợ.
• Nhóm thuật toán dựa trên chiến lược tăng trưởng mẫu (Pattern Growth): Nhằm khắc phục việc sinh dư thừa ứng viên, nhóm này mở rộng đồ thị con bằng cách thêm cạnh phụ. Các thuật toán tiêu biểu gồm MoFa (Borgelt, Berthold, 2002) dùng danh sách nhúng trên cấu trúc phân tử; gSpan (Yan và cộng sự, 2002) sử dụng mã DFS (DFS code) và thứ tự mã DFS nhỏ nhất (minimum DFS code) kết hợp tìm kiếm theo chiều sâu; FFSM (Huan, Wang, Prins, 2003) sử dụng ma trận kề và cây CAM tối ưu; Gaston (Nijssen, Kok, 2004) phân tách quá trình khai thác theo chuỗi đường dẫn, cây và đồ thị có chu trình.
• Nhóm thuật toán sử dụng chiến lược so sánh gần đúng: Nhằm giảm chi phí tính toán của phép kiểm tra đẳng cấu đồ thị (vốn là bài toán NP-khó), các công trình tiếp cận theo hướng xấp xỉ gồm SUBDUE (Ketkar, Holder, Cook, 2005) dùng độ dài mô tả tối thiểu (MDL); GREW (Kuramochi, Karypis, 2004) với hai biến thể GREW-SE và GREW-ME trên đồ thị thưa; gApprox (Chen và cộng sự, 2007); APGM (Jia và cộng sự, 2011) xử lý sai sót nhãn qua ma trận thay thế; VEAM (Acosta và cộng sự, 2012) mở rộng cho thay đổi cả nhãn đỉnh và cạnh; AgraP (Flores-Garrido, 2015) sử dụng hàm tương đồng $fsim$.

Đối với đồ thị lớn đơn nhất, thuật toán GraMi do Elseidy và các cộng sự đề xuất năm 2014 đánh dấu bước phát triển khi mô hình hóa bài toán kiểm tra độ phổ biến thành bài toán thỏa mãn ràng buộc (Constraint Satisfaction Problem - CSP) và sử dụng độ hỗ trợ tối thiểu dựa trên hình ảnh MNI (Minimum Image Based Support). Thuật toán GraphPi (Shi và cộng sự, 2020) tối ưu hóa việc đối sánh mẫu phân tán dựa trên lý thuyết nhóm.

Đối với khai thác mẫu có trọng số, khái niệm trọng số xuất hiện từ nghiên cứu của Cai và cộng sự (1998), sau đó phát triển trong khai thác luật kết hợp có trọng số (WARM) và khai thác chuỗi có trọng số (WSM). Yang và cộng sự (2012) áp dụng ý tưởng WARM để đề xuất thuật toán $t$-WIGM và $k$-WIGM trên đồ thị có trọng số cạnh. Jiang và cộng sự (2011) phát triển 3 biến thể của gSpan (ATW-gSpan, AW-gSpan, UBW-gSpan) trên tập các đồ thị có trọng số cạnh. Preti và cộng sự (2018) nghiên cứu đồ thị đa trọng số với giải pháp chính xác và gần đúng. Bài toán nhóm có trọng số cạnh tối đa (MEWCP) được giải quyết qua thuật toán LSMR (2018). Liu và cộng sự (2021) nghiên cứu tần suất và mật độ trên đồ thị lưỡng cực có trọng số. Raayatpanah và cộng sự (2022) dùng phân tích bao dữ liệu (DEA) và quy hoạch tuyến tính để tìm cung hiệu quả.

Vị trí của luận án được xác lập tại điểm giao thoa chưa được giải quyết: kế thừa mô hình CSP của GraMi để xử lý đơn đồ thị kích thước lớn, nhưng tập trung vào trọng số đỉnh thay vì trọng số cạnh, đồng thời thiết lập các nguyên lý toán học mới để duy trì khả năng cắt tỉa không gian tìm kiếm khi tính chất DCP nguyên bản bị phá vỡ.

Cơ sở lý thuyết và phương pháp nghiên cứu

Luận án thiết lập khung lý thuyết hình thức dựa trên lý thuyết đồ thị kinh điển và lý thuyết mô hình thỏa mãn ràng buộc (CSP). Đồ thị có trọng số được định nghĩa là bộ $G = (V, E, L, W)$, trong đó $V$ là tập đỉnh, $E \subseteq V \times V$ là tập cạnh, $L$ là hàm gán nhãn cho đỉnh và cạnh, $W: V \rightarrow \mathbb{R}^+$ là hàm gán trọng số không âm cho các đỉnh. Đồ thị con có trọng số $S = (V_S, E_S, L_S, W_S)$ của $G$ là đồ thị thỏa mãn tồn tại một phép đẳng cấu $f: V_S \rightarrow V$ bảo toàn cấu trúc cạnh, nhãn và trọng số.

Khung phân tích CSP biểu diễn việc tìm kiếm đồ thị con $S$ trong đồ thị lớn $G$ dưới dạng bộ ba $(X, D, C)$:

• $X$: tập hợp các biến đại diện cho các đỉnh của đồ thị con $S$ ($X = {x_v \mid v \in V_S}$).
• $D$: tập hợp các miền giá trị; mỗi biến $x_v$ có một miền $D(v)$ chứa tất cả các đỉnh $u \in V_G$ có cùng nhãn đỉnh với $v$ ($L_G(u) = L_S(v)$).
• $C$: tập hợp các ràng buộc, bao gồm ràng buộc phân biệt đỉnh ($x_u \neq x_{v'}$ khi $u \neq v'$) và ràng buộc bảo toàn liên kết nhãn cạnh ($L_G(x_u, x_{v'}) = L_S(u, v')$ với mọi $(u, v') \in E_S$).

Mỗi phép gán hợp lệ của các biến trong $X$ thỏa mãn tất cả các ràng buộc $C$ tương ứng với một phép đẳng cấu của $S$ trong $G$.

Về độ đo tần suất, thuật toán GraMi sử dụng độ đo MNI: $$s_G(S) = \min { |{f(v) \mid f \text{ là đẳng cấu của } S \text{ trong } G}|, \forall v \in V_S }$$ Tuy nhiên, tác giả chứng minh rằng độ đo MNI dừng ngay khi tìm đủ số lượng xuất hiện tối thiểu để kết luận tính phổ biến, do đó không phản ánh toàn bộ các phép gán hợp lệ cần thiết để tính toán chính xác trọng số của đồ thị con. Do đó, luận án đề xuất khái niệm "Độ hỗ trợ đầy đủ" (Full Support, ký hiệu $s_{fulG}(S)$): $$s_{fulG}(S) = \min { |D(v)|, \forall v \in V_S }$$ trong đó $D(v)$ là tập hợp đầy đủ tất cả các đỉnh $u \in V_G$ tham gia vào các phép gán hợp lệ tương ứng với các đẳng cấu của $S$ trong $G$.

Phương pháp nghiên cứu kết hợp giữa nghiên cứu lý thuyết hình thức (chứng minh toán học các định lý cắt tỉa không gian tìm kiếm) và nghiên cứu thực nghiệm định lượng trên máy tính. Dữ liệu thực nghiệm bao gồm ba cơ sở dữ liệu đồ thị mạng thực tế:

• MiCo: Mạng lưới hợp tác đồng tác giả trong khoa học máy tính.
• Facebook: Mạng lưới liên kết người dùng mạng xã hội.
• CiteSeer: Mạng lưới trích dẫn giữa các ấn phẩm khoa học.

Thuật toán	Loại đồ thị mục tiêu	Yếu tố trọng số	Độ đo độ phổ biến	Chiến lược tính trọng số	Kỹ thuật cắt tỉa không gian
GraMi (2014)	Đơn đồ thị lớn	Không có trọng số	MNI	Không áp dụng	Mô hình CSP, nhất quán cung đỉnh/cạnh
WeGraMi (Luận án)	Đơn đồ thị lớn	Trọng số đỉnh	Độ hỗ trợ đầy đủ ($s_{fulG}$)	Chiến lược MaxMin	Định lý 2.1 (cắt tỉa đồ thị con dựa trên MaxMin)
OWGraMi (Luận án)	Đơn đồ thị lớn	Trọng số đỉnh	Độ hỗ trợ đầy đủ ($s_{fulG}$)	Kế thừa trọng số cha	Tỉa danh sách cạnh phổ biến + kế thừa trọng số cha
AWeGraMi (Luận án)	Đơn đồ thị lớn	Trọng số đỉnh	Độ hỗ trợ đầy đủ ($s_{fulG}$)	Chiến lược AveMin	Sử dụng giới hạn chặn trên MaxMin

Nội dung chính theo từng chương

Chương 1: Cơ sở lý thuyết

Chương 1 tái hiện các định nghĩa cơ bản trong lý thuyết đồ thị vô hướng, đồ thị có hướng, bậc của đỉnh, đường đi, chu trình, dây chuyền, mạch và phép đẳng cấu đồ thị. Tiếp đó, chương phân tích phát biểu toán học của bài toán FSM trên tập dữ liệu đồ thị và trên đơn đồ thị lớn. Nội dung trọng tâm của chương là việc hình thức hóa cơ sở lý thuyết cho đồ thị có trọng số đỉnh:

• Định nghĩa trọng số đỉnh $W(u_i)$ là số thực không âm biểu diễn tầm quan trọng hoặc độ tin cậy.
• Định nghĩa đồ thị có trọng số $G = (V, E, L, W)$ và đồ thị con có trọng số $S$.
• Thiết lập mô hình CSP cho đồ thị có trọng số và chỉ ra hạn chế của độ đo MNI khi tính toán giá trị trọng số đại diện.
• Định nghĩa hình thức độ hỗ trợ đầy đủ $s_{fulG}(S)$ và phát biểu mô hình Bài toán - BT: tìm tất cả các đồ thị con $S$ trong $G$ thỏa mãn đồng thời hai điều kiện: $s_{fulG}(S) \ge f$ và $W(S) \ge w$.

Chương 2: Phương pháp khai thác đồ thị con trên đồ thị có trọng số

Chương 2 trình bày hai thuật toán cốt lõi do tác giả đề xuất để giải quyết Bài toán - BT là WeGraMi và OWGraMi.

Đối với thuật toán WeGraMi, trọng số của đồ thị con $S$ được tính toán qua chiến lược hai giai đoạn MaxMin:

• Giai đoạn 1 (Toán tử Max): Tính trọng số cho từng đỉnh $v \in V_S$ bằng giá trị lớn nhất trong số các đỉnh $u \in V_G$ thuộc miền giá trị hợp lệ $D(v)$ của mô hình CSP: $$W(v) = \max_{u \in D(v)} W(u)$$
• Giai đoạn 2 (Toán tử Min): Tính trọng số của đồ thị con $S$ bằng giá trị nhỏ nhất giữa các trọng số đỉnh của nó: $$W(S) = \min_{v \in V_S} W(v)$$

Cơ sở toán học then chốt để WeGraMi kiểm soát không gian tìm kiếm là Định lý 2.1: "Nếu một đồ thị con phổ biến $S$ không thỏa ngưỡng trọng số $w$ ($W(S) < w$), thì tất cả các đồ thị con được phát sinh từ đồ thị $S$ cũng không thỏa ngưỡng trọng số $w$". Định lý này cho phép thuật toán cắt tỉa sớm toàn bộ nhánh tìm kiếm phát sinh từ $S$. Hai thuật giải cụ thể được xây dựng gồm:

• ComputeFullSupport(S, G, f): Duyệt các biến trong miền CSP, tính kích thước miền hợp lệ và trả về giá trị độ hỗ trợ đầy đủ $s_{fulG}(S)$ nếu $s_{fulG}(S) \ge f$, ngược lại trả về 0.
• ComputeWeight(S, G, w): Xác định trọng số từng đỉnh $W(v)$ dựa trên giá trị cực đại của các phép gán hợp lệ, sau đó xác định $W(S)$ bằng toán tử cực tiểu; nếu phát hiện bất kỳ đỉnh nào có $W(v) < w$, giải thuật lập tức trả về 0 để cắt tỉa.

Đối với thuật toán OWGraMi (Optimized WeGraMi), tác giả bổ sung hai chiến lược tối ưu hóa:

1. Tỉa danh sách cạnh phổ biến: Loại bỏ các cạnh không thỏa mãn điều kiện phổ biến trước khi tiến hành bước mở rộng đồ thị con.
2. Xác định trọng số đồ thị con dựa trên đồ thị cha: Kế thừa trực tiếp giá trị trọng số của các đỉnh đã được tính toán ở đồ thị cha thay vì tính toán lại từ đầu trên mô hình CSP, giảm thiểu đáng kể chi phí duyệt lặp.

Thực nghiệm định lượng trong Chương 2 so sánh WeGraMi và OWGraMi trên ba bộ dữ liệu MiCo, Facebook và CiteSeer về số lượng đồ thị con ứng viên, số lượng mẫu thỏa ngưỡng, thời gian thực thi và dung lượng bộ nhớ tiêu thụ. Kết quả thực nghiệm cho thấy OWGraMi giảm đáng kể số lượng ứng viên phát sinh và rút ngắn thời gian xử lý so với WeGraMi khi thay đổi các ngưỡng $f$ và $w$.

Chương 3: Phương pháp mở rộng khai thác đồ thị con trên đồ thị có trọng số

Chương 3 mở rộng bài toán sang chiến lược áp dụng độ đo trung bình AveMin thông qua thuật toán AWeGraMi.

Chiến lược AveMin được đề xuất nhằm điều chỉnh độ nhạy của trọng số đồ thị con:

• Trọng số của từng đỉnh $v \in V_S$ được tính bằng giá trị trung bình cộng trọng số của các phép gán hợp lệ trong miền $D(v)$: $$W_{ave}(v) = \frac{1}{|D(v)|} \sum_{u \in D(v)} W(u)$$
• Trọng số của đồ thị con $S$ được lấy bằng giá trị nhỏ nhất của các trọng số đỉnh trung bình: $$W_{AveMin}(S) = \min_{v \in V_S} W_{ave}(v)$$

Do toán tử lấy giá trị trung bình không bảo toàn tính chất bao đóng giảm một cách tự nhiên, tác giả thiết lập kỹ thuật chặn trên (upper bound) dựa vào chiến lược MaxMin: vì giá trị trung bình luôn nhỏ hơn hoặc bằng giá trị cực đại ($W_{ave}(v) \le W_{max}(v)$), nên nếu trọng số theo MaxMin không vượt qua ngưỡng $w$ thì trọng số theo AveMin chắc chắn không thể vượt qua ngưỡng $w$. Nhờ đó, AWeGraMi sử dụng giá trị chặn trên của MaxMin làm điều kiện cắt tỉa sớm không gian tìm kiếm.

Nội dung chương phân tích độ phức tạp thuật toán và đánh giá thực nghiệm AWeGraMi trên hai bộ dữ liệu Facebook và CiteSeer, kiểm chứng hiệu quả về số lượng ứng viên, thời gian chạy và bộ nhớ khi ngưỡng hỗ trợ và ngưỡng trọng số biến thiên.

Chương 4: Kết luận

Chương 4 tổng hợp các kết quả nghiên cứu lý thuyết và thực nghiệm đã đạt được trong toàn bộ luận án, khẳng định việc hoàn thành các mục tiêu đặt ra ban đầu và đề xuất các hướng phát triển nghiên cứu tiếp theo.

Kết quả và những đóng góp mới

Luận án tự công bố các đóng góp mới về mặt lý thuyết và thực tiễn, gắn liền với 3 công trình khoa học đã được công bố của tác giả (ký hiệu [CT1], [CT2], [CT3]):

• Đóng góp 1 (Lý thuyết và mô hình hóa): Đề xuất hướng tiếp cận giải quyết Bài toán - BT dựa trên việc mở rộng mô hình CSP để biểu diễn đơn đồ thị lớn có trọng số đỉnh; định nghĩa và đưa vào sử dụng khái niệm Độ hỗ trợ đầy đủ ($s_{fulG}(S)$) thay thế cho độ đo MNI vốn không phản ánh trọn vẹn miền giá trị hợp lệ khi tích hợp trọng số.
• Đóng góp 2 (Thuật toán WeGraMi): Xây dựng thuật toán WeGraMi áp dụng chiến lược MaxMin để tính trọng số đồ thị con. Phát biểu và chứng minh Định lý 2.1, xác lập tính chất đơn điệu giảm của trọng số MaxMin, cho phép cắt tỉa không gian tìm kiếm ngay khi đồ thị con vi phạm ngưỡng trọng số.
• Đóng góp 3 (Thuật toán tối ưu OWGraMi): Phát triển thuật toán OWGraMi với hai kỹ thuật tối ưu: lọc danh sách cạnh phổ biến trước khi khai thác và cơ chế kế thừa trọng số từ đồ thị cha, giúp giảm khối lượng tính toán CSP lặp lại.
• Đóng góp 4 (Thuật toán mở rộng AWeGraMi): Mở rộng phương pháp tính trọng số qua chiến lược AveMin, đồng thời thiết lập giới hạn chặn trên dựa trên MaxMin để thực hiện cắt tỉa nhánh tìm kiếm khi tính chất bao đóng giảm không thỏa mãn trực tiếp.

Về mặt giải pháp, luận án đề xuất quy trình ba bước chuẩn hóa cho bài toán khai thác đồ thị con có trọng số trên đơn đồ thị lớn:

• Bước 1: Khai thác đồ thị con phổ biến trên đồ thị đơn kích thước lớn ứng với ngưỡng hỗ trợ $f$ dựa trên việc giải bài toán CSP.
• Bước 2: Tính trọng số đại diện cho đồ thị con phổ biến dựa vào tập các phép gán hợp lệ của các đỉnh theo độ đo lựa chọn (MaxMin hoặc AveMin).
• Bước 3: Cắt tỉa không gian tìm kiếm dựa vào ngưỡng trọng số $w$ (sử dụng trực tiếp Định lý 2.1 hoặc thông qua giới hạn chặn trên MaxMin).

Hạn chế và hướng nghiên cứu tiếp

Dựa trên nội dung và phạm vi nghiên cứu được tác giả trình bày trong văn bản:

• Hạn chế: Luận án chỉ tập trung vào đồ thị tĩnh, xét trọng số không âm trên các đỉnh của đồ thị mà chưa xem xét trường hợp đồ thị có đồng thời cả trọng số đỉnh và trọng số cạnh. Bản chất bài toán kiểm tra đẳng cấu đồ thị con và tìm kiếm phép gán CSP có độ phức tạp thuật toán NP-khó, do đó thời gian xử lý và tài nguyên bộ nhớ vẫn chịu áp lực lớn khi kích thước đồ thị tăng lên mức cực lớn hoặc khi đặt ngưỡng hỗ trợ tối thiểu ở mức rất thấp.
• Hướng nghiên cứu tiếp:
  • Mở rộng mô hình lý thuyết và thuật toán cho đồ thị có đồng thời trọng số trên cả đỉnh và cạnh.
  • Nghiên cứu bài toán khai thác trên đồ thị động (đồ thị có cấu trúc đỉnh, cạnh hoặc trọng số biến đổi theo thời gian).
  • Áp dụng các kỹ thuật tính toán phân tán và xử lý song song để nâng cao năng lực khai thác trên các cơ sở dữ liệu đồ thị có quy mô vượt trội.

Giá trị tham khảo

Luận án là tài liệu tham khảo chuyên sâu đối với:

• Nghiên cứu sinh, học viên cao học và giảng viên chuyên ngành Khoa học máy tính, Hệ thống thông tin và Khoa học dữ liệu: Cung cấp khung lý thuyết hình thức về mô hình hóa CSP trên đồ thị, kỹ thuật biến đổi độ đo hỗ trợ từ MNI sang Độ hỗ trợ đầy đủ, cùng các chứng minh toán học về tính chất bao đóng giảm đối với hàm trọng số.
• Kỹ sư phát triển phần mềm và chuyên gia phân tích dữ liệu: Các thuật giải chi tiết (ComputeFullSupport, ComputeWeight) và các chiến lược tối ưu trong OWGraMi và AWeGraMi có thể được ứng dụng trực tiếp trong xây dựng các công cụ phân tích mạng xã hội, phát hiện mẫu liên kết trong mạng trích dẫn khoa học hoặc phát sinh luật kết hợp trên đồ thị thực tế.
• Các phần đáng tham khảo nhất: Mục 1.3 và 1.4 (Chương 1) về mô hình CSP và bài toán đồ thị có trọng số; Mục 2.1 đến 2.3 (Chương 2) về thuật toán WeGraMi, chứng minh Định lý 2.1 và thuật toán OWGraMi; Mục 3.2 đến 3.4 (Chương 3) về kỹ thuật chặn trên MaxMin cho chiến lược AveMin.

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

1. Bài toán trọng tâm của luận án (Bài toán - BT) được phát biểu cụ thể như thế nào?

Bài toán - BT yêu cầu: Cho trước một đồ thị $G = (V, E, L, W)$ có gán nhãn đỉnh, nhãn cạnh và mang trọng số không âm trên các đỉnh. Với một ngưỡng hỗ trợ $f$ và một ngưỡng trọng số $w$ cho trước, tìm tất cả các đồ thị con $S$ thuộc $G$ sao cho $S$ là đồ thị con phổ biến có độ hỗ trợ đầy đủ $s_{fulG}(S) \ge f$ và có giá trị trọng số thỏa mãn $W(S) \ge w$.

2. Tại sao luận án không sử dụng độ đo MNI của GraMi mà phải đề xuất khái niệm "Độ hỗ trợ đầy đủ"?

Độ đo MNI trong GraMi chỉ giải bài toán CSP cho đến khi tìm thấy số lượng phép gán tối thiểu vừa đủ để khẳng định đồ thị con đạt ngưỡng phổ biến rồi dừng lại, bỏ qua các phép gán còn lại. Cách làm này không thu thập đủ toàn bộ các đỉnh tương ứng trong đồ thị lớn, khiến việc tính toán trọng số đại diện cho các đỉnh của đồ thị con bị sai lệch. Độ hỗ trợ đầy đủ ($s_{fulG}(S)$) tìm kiếm tất cả các phép gán hợp lệ của biến trên toàn bộ đồ thị, tạo ra tập miền giá trị đầy đủ để tính toán chính xác trọng số.

3. Chiến lược MaxMin tính trọng số của đồ thị con qua các bước nào và Định lý 2.1 có vai trò gì?

Chiến lược MaxMin gồm hai giai đoạn:

• Giai đoạn 1: Trọng số của mỗi đỉnh $v$ trong đồ thị con $S$ được tính bằng giá trị lớn nhất trong số các đỉnh $u$ thuộc miền giá trị hợp lệ $D(v)$ trên đồ thị lớn $G$ ($W(v) = \max {W(u) \mid u \in D(v)}$).
• Giai đoạn 2: Trọng số của đồ thị con $S$ được tính bằng giá trị nhỏ nhất giữa các trọng số đỉnh vừa tính ($W(S) = \min {W(v) \mid v \in V_S}$). Định lý 2.1 chứng minh rằng nếu $W(S) < w$ thì mọi đồ thị con phát sinh từ $S$ cũng đều có trọng số nhỏ hơn $w$, tạo ra điều kiện dừng để cắt tỉa sớm không gian tìm kiếm.

4. Thuật toán OWGraMi đã cải tiến những điểm gì so với WeGraMi để tăng tốc độ xử lý?

OWGraMi tối ưu hóa WeGraMi thông qua hai chiến lược: thứ nhất là tiến hành tỉa bỏ danh sách các cạnh không phổ biến trước khi áp dụng giải thuật mở rộng đồ thị con; thứ hai là kế thừa trực tiếp giá trị trọng số của các đỉnh từ đồ thị con cha đã tính toán trước đó, loại bỏ việc phải giải lại bài toán CSP từ đầu để xác định lại trọng số.

5. Trong thuật toán AWeGraMi, tại sao phải dùng giới hạn chặn trên MaxMin khi áp dụng chiến lược AveMin?

Chiến lược AveMin tính trọng số đỉnh bằng giá trị trung bình cộng các phép gán hợp lệ. Do phép tính trung bình không bảo toàn tính chất bao đóng giảm (một tập con mở rộng có thể có giá trị trung bình tăng lên), thuật toán không thể cắt tỉa trực tiếp bằng ngưỡng AveMin. Vì giá trị trung bình luôn nhỏ hơn hoặc bằng giá trị cực đại ($W_{ave}(v) \le W_{max}(v)$), thuật toán sử dụng giá trị MaxMin làm chặn trên: nếu chặn trên MaxMin nhỏ hơn ngưỡng $w$, giá trị AveMin chắc chắn nhỏ hơn $w$, cho phép cắt tỉa an toàn nhánh tìm kiếm.

Kết luận

Luận án tiến sĩ của Lê Thị Ngọc Thảo đã giải quyết bài toán khai thác đồ thị con phổ biến có trọng số trên đơn đồ thị kích thước lớn có trọng số đỉnh thông qua việc mở rộng mô hình CSP và kế thừa thuật toán GraMi. Tác giả đã đóng góp ba thuật toán liên hoàn gồm WeGraMi với chiến lược MaxMin và Định lý 2.1 cắt tỉa không gian tìm kiếm, OWGraMi với các kỹ thuật tối ưu hóa kế thừa trọng số và lọc cạnh, cùng AWeGraMi mở rộng cho độ đo trung bình AveMin với kỹ thuật chặn trên MaxMin. Các kết quả thực nghiệm trên các tập dữ liệu mạng thực tế MiCo, Facebook và CiteSeer đã chứng minh tính đúng đắn và hiệu quả tính toán của các phương pháp đề xuất.

Trích đoạn nội dung tài liệu

Phần mở đầu của luận án giới thiệu chung về lĩnh vực khai thác dé liệu đồ thị, trong đó dé cập đến bài toán khai thác đồ thị con phố biến và các phương pháp tiếp cận dé giải bài toán này. Tiếp theo đó, luận án tập trung vào giới thiệu bài toán của luận án: khai thác đồ thị con phô biến trên đồ thị có trọng số và đề xuất các hướng tiếp cận dé giải quyết bài toán này. Phần mở dau cũng giới thiệu bố cục và các đóng góp chính của luận án. Khai thác đồ thị con phé biến 1.

Giới thiệu chung về khai thác dữ liệu đồ thị Trong thời gian gan đây, thuật ngữ dir liệu lớn (Big Data) đã không còn là một khái niệm mới mẻ và ngày càng được nhắc đến thường xuyên trong các lĩnh vực công nghệ cũng như việc ứng dụng công nghệ vào trong cuộc sông. Khai thác hiệu quả dữ liệu lớn tạo ra lợi thế rất lớn cho các tổ chức trong môi trường hoạt động đầy cạnh tranh hiện nay. Dữ liệu lớn có thể được hiểu theo nghĩa rộng là một thuật ngữ nói về việc lưu trữ, quản lý và xử lý một tập hợp dữ liệu với kích thước cực kỳ lớn và phức tạp mà các kỹ thuật xử lý dữ liệu theo các phương thức truyền thống không đủ khả năng dé thực hiện. Việc cố gắng tô chức và lưu trữ các tập dữ liệu không 16 với các cau trúc phức tạp bằng mô hình cơ sở dữ liệu truyền thống là không khả thi.

Do đó, cơ sở dữ liệu đồ thị được lựa chọn đề tổ chức và lưu trữ dữ liệu lớn. Tập trung vào mối quan hệ giữa các điểm đữ liệu thay vì vào bản thân các giá trị, đồ thị là sự lựa chọn hoan hảo cho các tập dữ liệu lớn, da dạng nhưng có kết nối. Với đồ thị, chúng ta dé dang thé hiện mối liên hệ giữa các dữ liệu cũng như ý nghĩa của các liên kết này, trên cơ sở đó thực hiện truy vấn những câu hỏi phức tạp và trừu tượng vượt ra ngoài những kết nối dữ liệu ban đầu. Trong số đó, mô hình đồ thị lớn có trọng số thường được sử dụng dé mô phỏng các mối quan hệ phức tạp giữa các đối tượng có mức độ quan trọng khác nhau trong nhiều ứng dụng: tầm quan trọng của tác nhân trong mạng xã hội, mức độ lưu thông của các giao điểm trên bản đồ, mức độ ảnh hưởng của các nút mạng máy tính và phân tích trang web dựa vào chỉ số ranking,.

Bài toán khai thác các đồ thị con có trọng số từ một đồ thị lớn đã dần trở nên là bài toán quan trọng trong nhiều lĩnh vực khoa học như phân tích mạng xã hội, hệ hỗ trợ ra quyết định, phân tích dữ liệu [10], phát sinh luật kết hợp [11, 36]. Trong một số trường hợp, chỉ có thé sử dụng đồ thị lớn có trọng số dé minh họa hoặc biểu diễn sự khác biệt giữa các đối tượng [22]. Vì thế, chủ đề này đã thu hút nhiều nghiên cứu trong các năm gần đây. Với mô hình dit liệu đồ thị, bài toán khai thác dit liệu đồ thị trở thành tâm điểm trong khai thác đữ liệu lớn.

Khai thác đồ thị con phô biến là một trong những nhánh của các kỹ thuật khai thác đữ liệu đồ thị. Bài toán khai thác đồ thị con phố biến Được dé xuất đầu tiên bởi Cook va Holder năm 1994, 2000 [51, 52], khai thác đồ thị con phố biến (FSM - Frequent Subgraph Mining) là bài toán tâm điểm trong lĩnh vực khai thác đữ liệu đồ thị và nhận được sự quan tâm của nhiều nhà nghiên cứu vì có thể ứng dụng nhiều trong thực tế.