ỦY BAN NHÂN DÂN TỈNH BÌNH DƯƠNG
TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT

NGUYỄN XUÂN BÌNH

ỨNG DỤNG PHƯƠNG PHÁP NHÚNG ĐỈNH
VÀO ĐỒ THỊ HAI PHÍA ĐỂ XÂY DỰNG
HỆ THỐNG KHUYẾN NGHỊ

LUẬN VĂN THẠC SĨ
CHUYÊN NGÀNH: HỆ THỐNG THÔNG TIN
MÃ SỐ: 8 48 01 04

BÌNH DƯƠNG – 2021


ỦY BAN NHÂN DÂN TỈNH BÌNH DƯƠNG
TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT

NGUYỄN XUÂN BÌNH

ỨNG DỤNG PHƯƠNG PHÁP NHÚNG ĐỈNH
VÀO ĐỒ THỊ HAI PHÍA ĐỂ XÂY DỰNG
HỆ THỐNG KHUYẾN NGHỊ

LUẬN VĂN THẠC SĨ
CHUYÊN NGÀNH: HỆ THỐNG THÔNG TIN
MÃ SỐ: 8 48 01 04

NGƯỜI HƯỚNG DẪN KHOA HỌC
TS. TRẦN QUANG NGUYÊN

BÌNH DƯƠNG – 2021


LỜI CAM ĐOAN
Tơi xin cam đoan đây là cơng trình nghiên cứu của riêng tôi và được
sự hướng dẫn khoa học của TS. Trần Quang Nguyên. Các nội dung nghiên
cứu, kết quả trong đề tài này là trung thực và chưa cơng bố dưới bất kỳ hình
thức nào trước đây.
Những số liệu trong các bảng biểu phục vụ cho việc phân tích, nhận
xét, đánh giá được chính tác giả thu thập từ các nguồn khác nhau có ghi rõ
trong phần tài liệu tham khảo.
Ngồi ra, trong báo cáo cịn sử dụng một số nhận xét, đánh giá cũng
như số liệu của các tác giả khác, cơ quan tổ chức khác đều có trích dẫn và
chú thích nguồn gốc.
Nếu phát hiện có bất kỳ sự gian lận nào tơi xin hồn tồn chịu
trách nhiệm về nội dung báo cáo của mình. Trường Đại học Thủ Dầu Một
không liên quan đến những vi phạm tác quyền, bản quyền do tôi gây ra trong
q trình thực hiện (nếu có).
Bình Dương, ngày 27 tháng 9 năm 2021
Người thực hiện

i


LỜI CẢM ƠN
Lời đầu tiên, tôi xin gửi lời cảm ơn chân thành nhất đến thầy Trần
Quang Nguyên, thầy đã dành nhiều thời gian q báu hướng dẫn tơi một cách
tận tình và khoa học, tạo điều kiện tốt nhất để tơi hồn thành Luận văn này.
Tơi cũng xin trân trọng cảm ơn quý thầy cô Trường Đại học Thủ Dầu

Một, đặc biệt là các thầy cô chuyên ngành Hệ thống Thơng tin! Các thầy cơ
đã tận tình hướng dẫn và luôn tạo điều kiện thuận lợi giúp đỡ tôi trong suốt
khóa học tại trường. Tơi cũng rất cảm ơn sự giúp đỡ nhiệt tình của bạn bè
cùng khóa đã hỗ trợ tơi các kỹ năng thiết thực để hồn thiện Luận văn hơn.
Ngoài ra, với những tư liệu hữu ích để thực hiện luận văn, tôi xin cảm
ơn lãnh đạo và đồng nghiệp tại Công ty Truyền tải điện 4 đã ủng hộ và tạo
điều kiện giúp tôi thu thập cơ sở dữ liệu để hoàn thành mục tiêu của đề tài.
Cuối cùng, tơi muốn gửi lịng biết ơn vơ hạn đến gia đình tơi, tất cả
mọi người đã ln động viên, khuyến khích giúp tơi vượt qua những thời
điểm khó khăn để tơi có thể hồn thành tốt chương trình cao học tại trường
Đại học Thủ Dầu Một.
Tơi xin chúc q thầy cơ, gia đình và bạn bè luôn mạnh khỏe và đạt
được nhiều thành công trong cuộc sống!
Bình Dương, ngày 27 tháng 9 năm 2021
Người thực hiện

ii


MỤC LỤC
LỜI CAM ĐOAN ................................................................................................... i
LỜI CẢM ƠN ........................................................................................................ ii
MỤC LỤC ............................................................................................................. iii
DANH MỤC CÁC HÌNH ẢNH ........................................................................... vi
DANH MỤC CÁC BẢNG BIỂU ........................................................................ vii
MỞ ĐẦU ................................................................................................................ 1
1.

Lý do chọn đề tài ...................................................................................... 1


2.

Mục tiêu nghiên cứu ................................................................................. 2

3.

Đối tượng, phạm vi nghiên cứu ................................................................ 2

4.

Phương pháp nghiên cứu .......................................................................... 3

5.

Đóng góp của đề tài .................................................................................. 3

6.

Cấu trúc của đề tài .................................................................................... 4

CHƯƠNG 1.

TỔNG QUAN VỀ CÁC PHƯƠNG PHÁP BIỂU DIỄN ĐỒ THỊ

VÀ ỨNG DỤNG.................................................................................................... 6
1.1. Tổng quan về đồ thị .................................................................................. 6
1.1.1.

Các khái niệm về đồ thị .................................................................. 6


1.1.2.

Đồ thị đối với học máy ................................................................... 9

1.2. Biểu diễn đồ thị bằng phép nhúng đỉnh .................................................. 11
1.2.1.

Tổng quan về phép nhúng đỉnh đồ thị .......................................... 11

1.2.2.

Phương pháp phân tích nhân tử .................................................... 13

1.2.3.

Phương pháp bước đi ngẫu nhiên (Random walk) ....................... 15

1.2.4.

Các kiến trúc nhúng sâu tổng quát ............................................... 18

iii


1.3. Ứng dụng của việc biểu diễn đồ thị bằng phương pháp nhúng đỉnh ...... 20
1.4. Kết luận................................................................................................... 22
CHƯƠNG 2.

BIỂU DIỄN MẠNG ĐỒ THỊ HAI PHÍA BẰNG PHƯƠNG


PHÁP NHÚNG ĐỈNH ......................................................................................... 23
2.1. Bài toán biểu diễn mạng đồ thị hai phía ................................................. 23
2.2. Phương pháp nhúng đỉnh đồ thị hai phía đề xuất ................................... 26
2.2.1.

Mơ hình hóa các quan hệ trực tiếp ............................................... 26

2.2.2.

Mơ hình hóa các quan hệ gián tiếp bằng bước đi nhẫu nhiên ...... 27

2.2.3.

Tối ưu hóa mơ hình chung ........................................................... 31

2.3. Kết luận................................................................................................... 32
CHƯƠNG 3.

HỆ THỐNG KHUYẾN NGHỊ VÀ CÁC ĐỘ ĐO ĐÁNH GIÁ HỆ

THỐNG KHUYẾN NGHỊ ................................................................................... 33
3.1. Tổng quan về bài toán khuyến nghị ....................................................... 33
3.1.1.

Khái niệm hệ thống khuyến nghị ................................................. 33

3.1.2.

Phát biểu bài toán hệ thống khuyến nghị ..................................... 34


3.1.3.

Các hướng tiếp cận xây dựng hệ thống khuyến nghị ................... 36

3.2. Các phương pháp và độ đo đánh giá hệ thống khuyến nghị .................. 41
3.2.1.

Phương pháp đánh giá hệ thống khuyến nghị .............................. 41

3.2.2.

Đánh giá độ chính xác của dự đốn ............................................. 42

3.2.3.

Đánh giá danh sách đề xuất .......................................................... 43

3.3. Kết luận................................................................................................... 47
CHƯƠNG 4.

XÂY DỰNG HỆ THỐNG KHUYẾN NGHỊ BẰNG PHƯƠNG

PHÁP NHÚNG ĐỈNH MẠNG ĐỒ THỊ HAI PHÍA ÁP DỤNG VÀO THỰC TẾ
................................................................................................... 48

iv


4.1. Giới thiệu nguồn dữ liệu và sự cần thiết xây dựng hệ thống khuyến nghị
thực tế tại doanh nghiệp ................................................................................... 48

4.2. Thu thập và xây dựng cơ sở dữ liệu ....................................................... 50
4.3. Thực nghiệm và kết quả ......................................................................... 55
4.3.1.

Phương pháp thực nghiệm ............................................................ 55

4.3.2.

Kết quả và đánh giá ...................................................................... 56

4.4. Kết luận................................................................................................... 62
KẾT LUẬN .......................................................................................................... 64
1.

Kết quả đạt được của đề tài .................................................................... 64

2.

Các mặt hạn chế và hướng phát triển của đề tài ..................................... 64

DANH MỤC TÀI LIỆU THAM KHẢO ............................................................. 66
PHỤ LỤC ............................................................................................................. 70

v


DANH MỤC CÁC HÌNH ẢNH
Hình 1.1. Đơn đồ thị vơ hướng và đa đồ thị vơ hướng. ......................................... 7
Hình 1.2. Đơn đồ thị có hướng .............................................................................. 7
Hình 1.3. Đồ thị hai phía ........................................................................................ 8

Hình 1.4. Mạng cộng đồng với cấu trúc gồm ba nhóm riêng biệt. Các đỉnh lân cận
trong cùng 1 nhóm sẽ có xu hướng liên kết chặt với nhau hơn so với các đỉnh thuộc
nhóm khác. ............................................................................................................. 9
Hình 1.5. Cách thức mã hóa - giải mã của phép nhúng đỉnh ............................... 11
Hình 1.6. Thực hiện các bước đi ngẫu nhiên để thống kê việc đồng xuất hiện giữa
các cặp đỉnh .......................................................................................................... 15
Hình 1.7. Cách thức hoạt động của các tham số p và q trong bước đi ngẫu nhiên
của phương pháp node2vec .................................................................................. 17
Hình 1.8. Tổng quan về tự động mã hóa sâu ....................................................... 18
Hình 1.9. Tổng quan về mã hóa tổng hợp vùng lân cận ...................................... 19
Hình 3.1. Giao diện hệ khuyến nghị sản phẩm của Tiki.vn ................................. 34
Hình 3.2. Ví dụ một ma trận đánh giá tổng quát .................................................. 35
Hình 3.3. Các hướng tiếp cận hệ thống khuyến nghị ........................................... 36
Hình 3.4. Phương pháp dựa trên người dùng và dựa trên đối tượng ................... 38
Hình 4.1. Ví dụ bảng liệt kê phiếu xuất kho ........................................................ 51
Hình 4.2. Dữ liệu thu được sau khi trích xuất các thơng tin cần thiết ................. 52
Hình 4.3. Thống kê tần suất xuất hiện của đơn vị nhận ....................................... 54

vi


DANH MỤC CÁC BẢNG BIỂU
Bảng 4.1. Bảng dữ liệu sau khi xử lý thô ............................................................. 53
Bảng 4.2. Thống kê dữ liệu các đồ thị ................................................................. 57
Bảng 4.3. Kết quả thực nghiệm khi áp dụng nhúng đỉnh mạng đồ thị hai phía lên
hai bộ dữ liệu Kho_PTC4 và DBLP .................................................................... 57
Bảng 4.4. Kết quả thực nghiệm các phương án số lượng bộ ký tự ...................... 58
Bảng 4.5. Tần suất các giá trị trọng số user-item trong các bộ dữ liệu ................ 60
Bảng 4.6. Kết quả thực nghiệm khi áp dụng nhúng đỉnh mạng đồ thị hai phía và
khi áp dụng lọc cộng tác dựa trên người dùng và đối tượng................................ 60

Bảng 4.7. Kết quả thực nghiệm khi áp dụng nhúng đỉnh mạng đồ thị hai phía và
khi áp dụng lọc cộng tác dựa trên người dùng và đối tượng................................ 62

vii


MỞ ĐẦU
1. Lý do chọn đề tài
Mạng đồ thị là một trong những cấu trúc mạnh mẽ nhất để mô hình hóa các
vấn đề trong thế giới thực. Với sự gia tăng của các mạng xã hội quy mô lớn, biểu
diễn mạng để đưa vào các mơ hình học máy đã trở thành một lĩnh vực quan trọng
của khai phá dữ liệu. Xây dựng một biểu diễn mạng hiệu quả là một thách thức
quan trọng trong việc áp dụng học máy đối với dữ liệu mạng đồ thị. Các tác vụ học
máy dựa trên mạng đồ thị có khả năng giải quyết đa dạng nhiều vấn đề khác nhau.
Nhiều nghiên cứu đã được thực hiện trong các năm qua để tạo ra các biểu diễn
đỉnh từ dữ liệu có cấu trúc mạng đồ thị bằng cách sử dụng các phương pháp học
biểu diễn mạng.
Mạng đồ thị hai phía là mơ hình phù hợp nhất để biểu thị mối quan hệ giữa
người sử dụng và vật phẩm (bộ phim, quyển sách, mặt hàng v.v…) trong thực tế.
Nhiều phương pháp học biểu diễn mạng đã được phát triển, tuy nhiên số lượng
nghiên cứu đối với mạng đồ thị hai phía là khơng nhiều, đặc biệt là việc biểu diễn
các mối quan hệ khơng trực tiếp mà có tính chất bắc cầu là một trong những đặc
trưng quan trọng của mạng đồ thị hai phía. Việc biểu diễn mạng đồ thị hai phía tốt
sẽ là cơ sở để xây dựng một hệ thống khuyến nghị đáp ứng được các yêu cầu đặt
ra như tốc độ đáp ứng, độ chính xác của kết quả khuyến nghị.
Các hệ thống khuyến nghị đã được quan tâm nghiên cứu và phát triển nhanh
chóng trong thời gian gần đây, đặc biệt các hệ khuyến nghị trong thương mại điện
tử đem lại nhiều lợi nhuận cho các nhà bán sản phẩm. Từ thực tế đó có thể thấy
nếu như các lĩnh vực quản trị nội bộ, hoạt động sản xuất kinh doanh của các doanh
nghiệp được cũng được xây dựng một hệ thống khuyến nghị thì sẽ góp phần nâng

cao hiệu quả, năng suất lao động của đơn vị.
Do đó, đề tài lựa chọn việc nghiên cứu phương pháp nhúng đỉnh vào mạng
đồ thị hai phía để xây dựng một hệ thống khuyến nghị, ứng dụng vào công tác quản
lý kho và cấp phát vật tư thiết bị tại Công ty Truyền tải điện 4.
1


2. Mục tiêu nghiên cứu
Mục tiêu của đề tài là nghiên cứu một phương pháp nhúng đỉnh mạng đồ
thị hai phía, sau đó áp dụng các phương pháp học máy để xây dựng hệ thống
khuyến nghị đối với mạng đồ thị hai phía, cuối cùng là áp dụng vào thực tế vào
hoạt động sản xuất kinh doanh của một doanh nghiệp.
Mục tiêu cụ thể gồm:
-

Tìm hiểu tổng quan các phương pháp biểu diễn mạng đồ thị.

-

Nghiên cứu phương pháp nhúng đỉnh mạng đồ thị hai phía.
o Tìm hiểu và thiết lập một bộ bước đi ngẫu nhiên trên hai tập đỉnh
khác loại của mạng đồ thị hai phía để tìm kiếm và bảo toàn các
mối quan hệ gián tiếp giữa các đỉnh cùng phía.
o Tìm hiểu và thiết lập một bộ tối ưu hóa chung đồng thời cho cả
các quan hệ trực tiếp và quan hệ gián tiếp của các đỉnh của mạng
đồ thị hai phía.

-

Tìm hiểu tổng quan về bài toán khuyến nghị, các hướng tiếp cận cũng

như các phương pháp đánh giá hiệu quả của một hệ thống khuyến nghị.

-

Xây dựng hệ thống khuyến nghị với đầu vào là các vector nhúng đỉnh
đã được học của mạng đồ thị hai phía. Áp dụng hệ thống khuyến nghị
lên hoạt động thực tế là công tác quản lý kho và cấp phát vật tư thiết bị
tại Công ty Truyền tải điện 4.

3. Đối tượng, phạm vi nghiên cứu
Trọng tâm nghiên cứu của đề tài là xây dựng một hệ thống khuyến nghị ứng
dụng trên thực tế sản xuất kinh doanh tại một doanh nghiệp, với nguồn dữ liệu của
đơn vị để thiết lập nên một mạng đồ thị hai phía và áp dụng các phương pháp
nhúng đỉnh để biểu diễn mạng đồ thị hai phía thực tế. Cơ sở dữ liệu được thu thập
là hoạt động quản lý và cấp phát vật tư thiết bị cho các đơn vị trực thuộc của Công
ty Truyền tải điện 4.
Phạm vi nghiên cứu của đề tài là tìm hiểu một phương pháp cụ thể thực hiện
nhúng đỉnh mạng đồ thị hai phía để đưa vào tác vụ học máy xây dựng hệ thống

2


khuyến nghị và ứng dụng thực tế. Kết quả của phương pháp được đánh giá và so
sánh với hệ thống khuyến nghị cơ bản không áp dụng nhúng đỉnh đồ thị.

4. Phương pháp nghiên cứu
Phương pháp nghiên cứu của luận văn là kết hợp nghiên cứu lý thuyết và
áp dụng thực nghiệm
Về lý thuyết, trước tiên đề tài nghiên cứu tổng quan về đồ thị, các phương
pháp nhúng đỉnh đồ thị cũng như ứng dụng của nó. Đề tài tìm hiểu chi tiết về

phương pháp nhúng đỉnh mạng đồ thị hai phía với các đặc điểm là sử dụng phương
pháp bước đi ngẫu nhiên đề tìm kiếm và phát hiện các mối quan hệ bậc cao giữa
các đỉnh cùng loại, và tối ưu hóa đồng thời các thành phần quan hệ trực tiếp và
gián tiếp giữa các đỉnh, giúp bảo toàn tốt nhất đặc trưng của các quan hệ trong
mạng đồ thi hai phía sau khi nhúng đỉnh. Kết quả nhúng đỉnh đồ thị hai phía này
được sử dụng là đầu vào xây dựng hệ thống khuyến nghị.
Về thực nghiệm, đề tài thu thập cơ sở dữ liệu thực tế là công tác quản lý và
cấp phát vật tư thiết bị tại kho vật tư Công ty Truyền tải điện 4 trong khoảng thời
gian từ năm 2017 đến tháng 6 năm 2021. Các dữ liệu này được thu thập và xây
dựng thành một mạng đồ thị hai phía với hai loại đỉnh là user: các đơn vị sử dụng
và item: các vật tư thiết bị. Dữ liệu được gán mã, xử lý thô và tinh chỉnh, lọc các
nội dung thừa, các yếu tố gây nhiễu, các yếu tố không phải là trọng tâm công tác
của yêu cầu công việc trong thực tế. Sau đó ứng dụng nhúng đỉnh vào mạng đồ thị
hai phía này để xây dựng được hệ thống khuyến nghị trong hoạt động sản xuất
kinh doanh thực tiễn của doanh nghiệp.

5. Đóng góp của đề tài
Đề tài đã nghiên cứu tổng quan về các phương pháp nhúng đỉnh đồ thị, đặc
biệt là đồ thị hai phía, tìm hiểu các mơ hình hệ thống khuyến nghị, từ đó xây dựng
có hiệu quả một hệ thống khuyến nghị trên cơ sở nhúng đỉnh mạng đồ thị hai phía
áp dụng vào dữ liệu thực tế trong hoạt động của một doanh nghiệp. Đây sẽ là tiền
đề để có thể tiếp tục phát triển hệ thống khuyến nghị này triển khai trên các cơ sở
sản xuất kinh doanh khác hoặc các lĩnh vực khác của cuộc sống.

3


Ngoài ra, bộ cơ sở dữ liệu thực tế thu thập được cũng như cách thức xử lý
dữ liệu và xây dựng thành mạng đồ thị hai phía sẽ giúp cho doanh nghiệp tiếp tục
cập nhật, bổ sung cho cơ sở dữ liệu hiện có và cải thiện độ chính xác của hệ thống

khuyến nghị, góp phần câng cao hiệu quả hoạt động của doanh nghiệp.

6. Cấu trúc của đề tài
Cấu trúc của đề tài được trình bày trong 4 chương như sau:
Chương 1. Tổng quan về các phương pháp biểu diễn đồ thị và ứng dụng
Chương này trình bày sơ lược về khái niệm đồ thị và tập trung tìm hiểu tổng
quan về một số phương pháp biểu diễn đồ thị phổ biến, đồng thời nêu lên một số
ứng dụng của việc biểu diễn đồ thị trong thực tế.
Chương 2. Biểu diễn mạng đồ thị hai phía bằng phương pháp nhúng
đỉnh.
Trong chương này, đề tài khái quát bài toán biểu diễn mạng đồ thị hai phía
và trọng tâm tìm hiểu cụ thể một phương pháp nhúng đỉnh mạng đồ thị hai phía
với kỹ thuật bước đi ngẫu nhiên và tối ưu hóa đồng thời các thành phần nhằm bảo
tồn được đặc trưng các quan hệ trực tiếp và quan hệ gián tiếp thông qua bắc cầu
các đỉnh của mạng đồ thị hai phía.
Chương 3. Hệ thống khuyến nghị và các độ đo đánh giá hệ thống
khuyến nghị.
Chương này đề tài sẽ trình bày những vấn đề tổng quan về hệ thống khuyến
nghị, phân tích các hướng tiếp cận phổ biến trong xây dựng hệ thống khuyến nghị
cũng như tìm hiểu các phương pháp đánh giá hiệu quả của một hệ thống khuyến
nghị. Từ đó lựa chọn mơ hình và độ đo cho hệ thống khuyến nghị dự kiến xây
dựng thực tế.
Chương 4. Xây dựng hệ thống khuyến nghị bằng phương pháp nhúng
đỉnh mạng đồ thị hai phía áp dụng vào thực tế.

4


Nội dung chương này là đóng góp chính của đề tài, trong đó tập trung trình
bày về cách thức thu thập và xử lý dữ liệu thực tế để thiết lập một mạng đồ thị hai

phía, từ đó ứng dụng phương pháp nhúng đỉnh mạng đồ thị hai phía từ thực tế để
xây dựng một hệ thống khuyến nghị, áp dụng cho hoạt động sản xuất của một
doanh nghiệp. Chương này cũng đánh giá hiệu quả của hệ thống khuyến nghị được
xây dựng qua các độ đo và so sánh với các hệ thống khuyến nghị thông thường
khác.
Cuối cùng là phần kết luận tổng hợp các kết quả nghiên cứu đã đạt được,
các đóng góp của đề tài, hướng mở rộng nghiên cứu và phát triển đề tài.

5


CHƯƠNG 1. TỔNG QUAN VỀ CÁC PHƯƠNG PHÁP
BIỂU DIỄN ĐỒ THỊ VÀ ỨNG DỤNG
Học máy trong lĩnh vực đồ thị là một trong những công việc quan trọng
nhưng phổ biến, với các ứng dụng trải rộng từ nghiên cứu phân tử, điều chế thuốc
cho đến giới thiệu bạn bè trong mạng xã hội. Thách thức chính đối với học máy về
đồ thị là tìm một phương pháp để biểu diễn, hoặc mã hóa, cấu trúc đồ thị sao cho
có thể dễ dàng được khai phá bởi các mơ hình học máy. Phần này giới thiệu tổng
quan về các phương pháp biểu diễn đồ thị và các ứng dụng của đồ thị đối với học
máy.

1.1.

Tổng quan về đồ thị

1.1.1. Các khái niệm về đồ thị
Đồ thị là một cấu trúc dữ liệu phổ biến, được sử dụng rất nhiều trong khoa
học máy tính và các lĩnh vực liên quan. Hệ thống giao thông, quy hoạch đô thị, cấu
trúc phân tử, vật lý y sinh, mạng xã hội hay hệ thống khuyến nghị thương mại điện
tử v.v… tất cả đều có thể sẵn sàng được mơ hình hóa thành đồ thị và giữ nguyên

các đặc tính tương tác giữa các phần tử độc lập trong hệ thống. Do tính phổ biến
của mình, đồ thị là xương sống của vô số hệ thống trong thực tế, cho phép các
thông tin về sự tương tác, quan hệ giữa các thực thế được lưu trữ và truy xuất một
cách hiệu quả.
Một đồ thị 𝒢 được đặc trưng bởi một tập hợp 𝑉 với N đỉnh và một tập hợp
𝐸 gồm các cạnh nối giữa các cặp đỉnh. Phân biệt các loại đồ thị khác nhau bởi kiểu
và số lượng cạnh nối hai đỉnh nào đó của đồ thị.
Một số định nghĩa và ký hiệu về đồ thị như sau:
-

Đơn đồ thị vô hướng 𝒢 = (𝑉, 𝐸) bao gồm 𝑉 là tập các đỉnh khác rỗng,
và 𝐸 là tập các cặp khơng có thứ tự gồm hai phần tử khác nhau của 𝑉
gọi là các cạnh.

6


-

Đa đồ thị vô hướng 𝒢 = (𝑉, 𝐸) bao gồm 𝑉 là tập các đỉnh khác rỗng, và
𝐸 là tập các cặp khơng có thứ tự gồm hai phần tử khác nhau của 𝑉 gọi
là các cạnh. Hai cạnh e1 và e2 được gọi là cạnh lặp (bội hay song song)
nếu chúng cùng tương ứng với một cặp đỉnh.
Mỗi đơn đồ thị là đa đồ thị, nhưng không phải đa đồ thị nào cũng là đơn
đồ thị, vì trong đa đồ thị có thể có hai (hoặc nhiều hơn) cạnh nối một
cặp đỉnh nào đó.

Hình 1.1. Đơn đồ thị vơ hướng và đa đồ thị vơ hướng.

-


Đồ thị có hướng 𝒢 = (𝑉, 𝐸) bao gồm 𝑉 là tập các đỉnh khác rỗng và 𝐸
là tập các cặp có thứ tự gồm hai phần tử khác nhau của 𝑉 gọi là các cung.
Tương tự có đơn đồ thị có hướng và đa đồ thị có hướng.

Hình 1.2. Đơn đồ thị có hướng

-

Hai đỉnh 𝑢 và 𝑣 trong đồ thị vô hướng 𝒢 = (𝑉, 𝐸) được gọi là liền kề
nếu (𝑢, 𝑣) ∈ 𝐸. Nếu 𝑒 = (𝑢, 𝑣) thì 𝑒 gọi là cạnh liên thuộc với các đỉnh

7


𝑢 và 𝑣. Cạnh 𝑒 cũng được gọi là cạnh nối các đỉnh 𝑢 và 𝑣. Các đỉnh 𝑢
và 𝑣 gọi là các điểm đầu mút của cạnh 𝑒.
-

Bậc của đỉnh 𝑣 trong đồ thị 𝒢 = (𝑉, 𝐸), ký hiệu deg(𝑣), là tổng số các
cạnh liên thuộc với nó.

-

Đường đi P độ dài n từ đỉnh 𝑢 đến đỉnh 𝑣, với n là số nguyên dương,
trên đồ thị 𝒢 = (𝑉, 𝐸) là dãy P: 𝑥0 , 𝑥1 , … , 𝑥𝑛−1 , 𝑥𝑛 , trong đó 𝑢 =
𝑥0 , 𝑣 = 𝑥𝑛 , 𝑥𝑖 ∈ 𝑉, 𝑖 = 0, 1, 2, … , 𝑛 − 1, 𝑛. Đỉnh 𝑢 gọi là đỉnh đầu, đỉnh
𝑣 gọi là đỉnh cuối của đường đi.

-


Đường đi có đỉnh đầu trùng với đỉnh cuối được gọi là 1 chu trình.

Một đồ thị thường được mô tả bởi một ma trận kề 𝐗 bậc N x N, với 𝐗 𝑖𝑗 là
giá trị gắn liền với cạnh giữa cặp đỉnh (i, j). Giá trị này bằng 0 nếu khơng có mối
liên kết giữa các đỉnh. Với đồ thị của cây nhị phân, ma trận X là ma trận nhị phân
và 𝐗 𝑖𝑗 = 1 thể hiện là hai đỉnh được liên kết với nhau.
Đồ thị hai phía
Đồ thị hai phía (bipartite graph) là một đồ thị có các đỉnh gồm hai tập độc
lập 𝑈 và 𝑉 không giao nhau, sao cho mỗi cạnh liên kết một đỉnh thuộc 𝑈 với một
đỉnh thuộc 𝑉. Đồ thị hai phía là một đồ thị khơng chứa chu trình có độ dài lẻ.
Đồ thị hai phía thường được viết dưới dạng 𝒢 = (𝑈, 𝑉, 𝐸) với với hai tập
đỉnh 𝑈 và 𝑉, và 𝐸 là tập các cạnh của đồ thị.

Hình 1.3. Đồ thị hai phía

8


1.1.2. Đồ thị đối với học máy
Đồ thị không chỉ hữu dụng như là một kho chứa thơng tin có cấu trúc, chúng
cịn đóng một vai trị quan trọng trong học máy hiện đại. Nhiều ứng dụng học máy
tìm kiếm các phương pháp để có thể đưa ra dự đốn hoặc khám phá ra các hình
mẫu mới bằng cách sử dụng dữ liệu cấu trúc đồ thị để trích xuất thơng tin đặc trưng.
Ví dụ như để xác định vai trò của một protein trong đồ thị tương tác sinh học, tìm
ra một hiệu quả trị liệu mới với các loại thuốc hiện hữu, đốn vai trị của một cá
nhân trong một mạng cộng tác, giới thiệu những người bạn mới cho một người
dùng trong một mạng xã hội, đây là các mạng lưới, hệ thống mà cấu trúc của nó
có thể được biểu diễn dưới dạng đồ thị.


Hình 1.4. Mạng cộng đồng với cấu trúc gồm ba nhóm riêng biệt. Các
đỉnh lân cận trong cùng 1 nhóm sẽ có xu hướng liên kết chặt với nhau
hơn so với các đỉnh thuộc nhóm khác.
Vấn đề trọng tâm của học máy về đồ thị là tìm ra một cách thức để kết hợp
thông tin về cấu trúc đồ thị vào trong một mơ hình học máy. Ví dụ trường hợp dự
đốn liên kết trong một mạng xã hội, ta có thể muốn mã hóa các thuộc tính theo
cặp giữa các nút đồ thị, như là độ bền chặt của mối quan hệ hoặc số lượng bạn
chung giữa những người dùng. Hoặc đối với trường hợp phân loại nút, ta có thể

9


muốn tích hợp thơng tin về vị trí tồn cục của nút hoặc cấu trúc của vùng lân cận
của nút trong đồ thị (Hình 1.4). Xét từ khía cạnh học máy, thách thức ở đây chính
là khơng có một cách đơn giản nào để mã hóa thơng tin có số chiều lớn của cấu
trúc đồ thị vào thành một vector đặc trưng.
Để trích xuất thơng tin cấu trúc từ các đồ thị, các hướng tiếp cận học máy
truyền thống thường dựa trên thống kê tóm tắt (ví dụ bậc đồ thị hoặc hệ số phân
cụm), các hàm lõi, hoặc các đặc trưng được tính tốn cẩn thận để đo các cấu trúc
lân cận cục bộ [1]. Tuy nhiên các phương pháp này bị giới hạn do các đặc trưng
được tính tốn thủ cơng này khơng linh hoạt, chúng khơng thích nghi trong quá
trình học, và việc thiết kế các đặc trưng này là một quá trình rất mất thời gian và
tốn kém.
Gần đây đã có rất nhiều hướng tiếp cận để tìm ra cách biểu diễn học máy
để mã hóa thông tin cấu trúc của đồ thị. Ý tưởng của hướng tiếp cận này là học
một phép ánh xạ để nhúng các đỉnh, hoặc toàn bộ đồ thị, vào một khơng gian vector
ℝ𝑑 có số chiều thấp. Mục tiêu là tối ưu hóa ánh xạ này để các quan hệ hình học
trong khơng gian nhúng phản ánh được cấu trúc của đồ thị gốc. Sau khi tối ưu hóa
khơng gian nhúng, các dữ liệu nhúng đã được học có thể được sử dụng như là các
đặc trưng đầu vào cho các tác vụ học máy sau đó. Sự khác biệt chính giữa hướng

tiếp cận học biểu diễn với các phương pháp trước đó là ở cách xử lý vấn đề biểu
diễn cấu trúc đồ thị. Các phương pháp truyền thống thực hiện các bước tiền xử lý,
dùng các thống kê được tính tốn thủ cơng để trích xuất thơng tin cấu trúc. Ngược
lại, hướng tiếp cận học biểu diễn xem vấn đề như là một tác vụ học máy, sử dụng
cách tiếp cận theo hướng thiên về dữ liệu để học các phép nhúng có thể mã hóa
cấu trúc đồ thị.
Các phần sau sẽ tìm hiểu các phương pháp biểu diễn đồ thị bằng nhúng đỉnh
trong lĩnh vực học máy và khai phá dữ liệu, đặc biệt là các phương pháp có thể mở
rộng cho các đồ thị rất lớn cỡ hàng triệu đỉnh và được thúc đẩy mạnh bởi các tiến
bộ về học sâu.

10


1.2.

Biểu diễn đồ thị bằng phép nhúng đỉnh

1.2.1. Tổng quan về phép nhúng đỉnh đồ thị
Mục tiêu của nhúng đỉnh đồ thị là là mã hóa các đỉnh thành các vector có
số chiều thấp nhưng có thể tóm tắt được vị trí của các đỉnh trong đồ thị và cấu trúc
của phần đồ thị lân cận. Các phép nhúng số chiều thấp này có thể được quan sát
bằng cách mã hóa hoặc chiếu các đỉnh lên một khơng gian đặc trưng với các quan
hệ hình học trong khơng gian này tương ứng với sự tương tác giữa các đỉnh trong
đồ thị ban đầu.

Hình 1.5. Cách thức mã hóa - giải mã của phép nhúng đỉnh
Các phép nhúng đỉnh đồ thị bao gồm phần chính là bộ mã hóa (encoder) và
bộ giải mã (decoder). Bộ mã hóa là một hàm ánh xạ mỗi đỉnh thành một vector có
số chiều thấp, gọi là vector nhúng, và bộ giải mã sẽ trả về thông tin cấu trúc của

đồ thị từ các vector nhúng đã học (Hình 1.5). Ý tưởng của hướng tiếp cận mã hóa
– giải mã này là: nếu ta có thể học cách giải mã thơng tin đồ thị có số chiều lớn, ví
dụ như các vị trí tồn cục của các đỉnh trong đồ thị hoặc cấu trúc của vùng đồ thị
lân cận, từ các phép nhúng số chiều thấp đã được mã hóa trước đó, thì về tổng thể,
các phép nhúng này cần phải chứa tồn bộ các thơng tin cần thiết cho các tác vụ
học máy phía sau.
Bộ mã hóa là một hàm có dạng:
ENC ∶ 𝒱 → ℝ𝑑 ,

11

(1.1)


Bộ mã hóa thực hiện ánh xạ các đỉnh của đồ thị thành các phép nhúng vector
𝐳𝑖 ∈ ℝ𝑑 với 𝐳𝑖 tương ứng với phép nhúng của đỉnh 𝑣𝑖 ∈ 𝒱. Bộ giải mã là một hàm
nhận một tập các phép nhúng đỉnh và giải mã các thông số cần thiết từ đồ thị theo
yêu cầu cụ thể từ các phép nhúng. Ví dụ, bộ giải mã có thể dự đoán sự tồn tại của
các cạnh nối giữa các đỉnh (ví dụ mối liên hệ giữa các người dùng trong mạng xã
hội), hoặc dự đốn đỉnh thuộc nhóm nào trong đồ thị (ví dụ phân loại khách hàng).
Về tổng thể có thể có nhiều bộ giải mã, tuy nhiên đều dựa trên nguyên tắc giải mã
cặp đôi cơ bản sau:
DEC ∶ ℝ𝑑 × ℝ𝑑 → ℝ+ ,

(1.2)

Bộ giải mã sẽ ánh xạ các cặp vector nhúng thành một phép đo độ tương tự
các đỉnh giá trị thực. Phép đo này xác định mức độ tương tự giữa hai đỉnh trong
đồ thị ban đầu.
Khi áp dụng bộ giải mã cặp đôi với một cặp vector nhúng đỉnh (𝐳𝑖 , 𝐳𝑗 ), ta

nhận được một sự phục dựng lại độ tương tự giữa các đỉnh 𝑣𝑖 và 𝑣𝑗 trong đồ thị
ban đầu, và mục tiêu là tối ưu hóa bộ mã hóa và giải mã sao cho sai số, hay mất
mát (loss), trong sự phục dựng này là nhỏ nhất.
DEC (ENC(𝑣𝑖 ), ENC(𝑣𝑗 )) = DEC(𝐳𝑖 , 𝐳𝑗 ) ≈ 𝑠𝒢 (𝑣𝑖 , 𝑣𝑗 ),

(1.3)

với 𝑠𝒢 là phép đo tương tự giữa các đỉnh trong đồ thị. Nói cách khác, mơ
hình mã hóa – giải mã cần được tối ưu sao cho có thể giải mã cặp đơi các độ tương
tự của đỉnh 𝑠𝒢 (𝑣𝑖 , 𝑣𝑗 ) trong đồ thị ban đầu từ các phép nhúng đỉnh số chiều thấp
𝐳𝒊 và 𝐳𝑗 . Trong thực tế, mục tiêu cần đạt được của phương trình (3) chính là tối
thiểu hóa mất mát thực tế ℒ trên một tập cặp đỉnh 𝒟:
ℒ = ∑(𝑣𝑖 ,𝑣𝑗)∈𝒟 ℓ (DEC(𝐳𝑖 , 𝐳𝑗 ), 𝑠𝒢 (𝑣𝑖 , 𝑣𝑗 )) ,

(1.4)

với ℓ ∶ ℝ × ℝ → ℝ là một hàm mất mát do người dùng xác định, dùng để
đo lường sự khác biệt giữa độ tương tự giải mã được (hay ước lượng được)
𝐷𝐸𝐶(𝐳𝑖 , 𝐳𝑗 ) và giá trị thực 𝑠𝒢 (𝑣𝑖 , 𝑣𝑗 ).

12


Khi đã tối ưu mơ hình mã hóa – giải mã, ta có thể sử dụng bộ mã hóa đã
được huấn luyện để tạo ra các phép nhúng cho các đỉnh, và sử dụng kết quả nhúng
đó như là các đầu vào đặc trưng cho các tác vụ học máy về sau. Ví dụ ta có thể đưa
các phép nhúng đã học vào một bộ phân loại hồi quy để dự đốn đỉnh thuộc nhóm
nào [2], hoặc có thể tính khoảng cách các đỉnh nhúng để đưa ra khuyến nghị kết
bạn trong mạng xã hội [3].
Thông qua hướng tiếp cận mã hóa – giải mã, có thể tổng quát lại các phương

pháp nhúng đỉnh khác nhau đều gồm bốn thành phần chính sau:
1. Một hàm tương tự cặp đơi 𝑠𝒢 ∶ 𝒱 × 𝒱 → ℝ+ , được xác định trên đồ thị
𝒢. Hàm này đo độ tương tự giữa các cặp đỉnh trong 𝒢.
2. Một bộ mã hóa ENC, để tạo ra các phép nhúng đỉnh. Hàm này chứa một
số tham số huấn luyện được tối ưu hóa trong giai đoạn huấn luyện.
3. Một bộ giải mã DEC, để phục dựng lại giá trị các độ tương tự theo cặp
đôi từ các phép nhúng được sinh ra. Hàm này không chứa các tham số
huấn luyện.
4. Một hàm mất mát ℓ, đánh giá chất lượng của việc phục dựng cặp đơi để
huấn luyện mơ hình, so sánh kết quả giải mã DEC(𝒛𝒊 , 𝒛𝑗 ) với giá trị thực
𝑠𝒢 (𝑣𝑖 , 𝑣𝑗 ).
Các phần sau sẽ tìm hiểu tổng quan về một số phương pháp nhúng đỉnh đồ
thị cụ thể thường được sử dụng.
1.2.2. Phương pháp phân tích nhân tử
Trong phương pháp phân tích nhân tử (Factorization-based), xét bộ mã hóa
là hàm ánh xạ các đỉnh thành các vector nhúng sau:
ENC(𝑣𝑖 ) = 𝐙𝐯𝑖 ,

(1.5)

với 𝐙 ∈ ℝ𝑑×𝒱 là một ma trận chứa các vector nhúng của tất cả các đỉnh và
𝐯𝑖 ∈ 𝕀𝒱 là một vector chỉ thị để biểu thị cột của 𝐙 tương ứng với đỉnh 𝑣𝑖 . Tập các
tham số huấn luyện là Θ𝐸𝑁𝐶 = {𝐙}. Những hướng tiếp cận học biểu diễn đỉnh này

13


phần lớn được bắt nguồn từ các kỹ thuật phân tích ma trận thành nhân tử cổ điển
để giảm số chiều dữ liệu.
Laplacian eigenmaps: Một trong những phương pháp sớm và phổ biến là

kỹ thuật Laplacian eigenmaps với bộ giải mã được xác định như sau:
DEC(𝐳𝑖 , 𝐳𝑗 ) = ‖𝐳𝑖 − 𝐳𝑗 ‖

2

(1.6)

2

và hàm mất mát của các cặp đỉnh tương ứng với độ tương tự giữa chúng
trong đồ thị:
ℒ = ∑(𝑣𝑖 ,𝑣𝑗)∈𝒟 DEC(𝐳𝑖 , 𝐳𝑗 ). 𝑠𝒢 (𝑣𝑖 , 𝑣𝑗 ).

(1.7)

Tích vơ hướng (inner product): Nhiều phương pháp nhúng dựa trên bộ giải
mã sử dụng tích vơ hướng cặp đôi như sau:
DEC(𝐳𝑖 , 𝐳𝑗 ) = 𝐳𝑖 𝑻 𝐳𝑗

(1.8)

với độ bền chặt quan hệ giữa hai đỉnh tỷ lệ với tích vơ hướng giữa các phép
nhúng của chúng. Các giải thuật Graph Factorization (GF), GraRep và HOPE đều
dựa trên nguyên lý này [1], sử dụng một bộ giải mã tích vơ hướng và hàm mất mát
sai số bình phương trung bình MSE:
2

ℒ = ∑(𝑣𝑖 ,𝑣𝑗)∈𝒟‖DEC(𝐳𝑖 , 𝐳𝑗 ) − 𝑠𝒢 (𝑣𝑖 , 𝑣𝑗 )‖2

(1.9)


Các phương pháp khác nhau chủ yếu ở cách sử dụng phép đo độ tương tự
giữa các đỉnh, cách xác định 𝑠𝒢 (𝑣𝑖 , 𝑣𝑗 ). Các phương pháp trên được đề cập trong
phần kỹ thuật phân tích ma trận thành nhân tử vì xét trung bình trên tất cả các đỉnh,
hàm mất mát được tối ưu đều có dạng:
ℒ ≈ ‖𝐙 𝑇 𝐙 − 𝐒‖22

(1.10)

với 𝐒 là ma trận chứa các độ đo tương tự theo cặp đơi đỉnh (hay nói cách
khác 𝐒𝑖,𝑗 ≜ 𝑠𝒢 (𝑣𝑖 , 𝑣𝑗 )) và 𝐙 là ma trận các phép nhúng đỉnh. Tóm lại, mục tiêu của
các phương pháp này là học phép nhúng cho mỗi đỉnh sao cho tích vơ hướng của

14


các vector nhúng được học xấp xỉ với các phép đo độ tương tự đã xác định của các
đỉnh.
1.2.3. Phương pháp bước đi ngẫu nhiên (Random walk)
Nhiều phương pháp nhúng đỉnh hiệu quả gần đây dựa trên thống kê bước
đi ngẫu nhiên trong đồ thị. Cải tiến quan trọng trong hướng tiếp cận này là tối ưu
hóa các phép nhúng đỉnh sao cho các đỉnh sẽ có phép nhúng tương tự nhau nếu các
đỉnh có xu hướng cùng xuất hiện trong các bước đi ngẫu nhiên ngắn trên đồ thị
(Hình 1.6) [1].
Các phương pháp dựa trên bước đi ngẫu nhiên lấy mẫu một số lượng lớn
bước đi ngẫu nhiên bắt đầu từ mỗi đỉnh, 𝑣𝑖 . Các vector nhúng sau đó được tối ưu
hóa sao cho tích vơ hướng giữa hai phép nhúng, 𝐳𝑖 và 𝐳𝑗 , tỷ lệ với xác suất đi đến
đỉnh 𝑣𝑗 trong các bước đi ngẫu nhiên xuất phát từ 𝑣𝑖 .

Hình 1.6. Thực hiện các bước đi ngẫu nhiên để thống kê việc đồng

xuất hiện giữa các cặp đỉnh
Theo đó, thay vì sử dụng các phép đo cụ thể về độ tương tự của các đỉnh,
các phương pháp dựa trên bước đi ngẫu nhiên sử dụng một thước đo linh hoạt,
ngẫu nhiên để xác định độ tương tự của đỉnh, đưa đến hiệu quả vượt trội khi được
cài đặt một số tham số nhất định [4].

15


1.2.3.1. Phương pháp DeepWalk và node2vec:
Giống như hướng tiếp cận phân rã ma trận ở phần trên, DeepWalk và
node2vec cũng sử dụng bộ giải mã dựa trên tích vơ hướng. Tuy nhiên, thay vì giải
mã một phép đo độ tương tự các đỉnh xác định trước, các phương pháp này tối ưu
hóa các phép nhúng để mã hóa kết quả thống kê các bước đi ngẫu nhiên của các
đỉnh trong đồ thị. Ý tưởng của các hướng tiếp cận này là học các phép nhúng với
bộ giải mã sau [1]:

DEC(𝐳𝑖 , 𝐳𝑗 ) ≜

𝐳 T𝐳
𝑒 𝑖 𝑗
T
∑𝑣 ∈𝒱 𝑒 𝐳𝒊 𝐳𝑘
𝑘

≈ 𝑝𝒢,𝑇 (𝑣𝑗 |𝑣𝑖 )

(1.11)

với 𝑝𝒢,𝑇 (𝑣𝑗 |𝑣𝑖 ) là xác suất của việc ghé thăm đỉnh 𝑣𝑗 của bước đi ngẫu nhiên

chiều dài 𝑇 xuất phát từ đỉnh 𝑣𝑖 . Khác với các phép đo độ tương tự trong các
phương pháp phân rã ma trận, 𝑝𝒢,𝑇 (𝑣𝑗 |𝑣𝑖 ) là ngẫu nhiên và bất đối xứng.
Mục tiêu của các hướng tiếp cận này là tối thiểu hóa mất mát entropy sau:
ℒ = ∑(𝑣𝑖 ,𝑣𝑗)∈𝒟 −log (DEC(𝐳i , 𝐳j ))

(1.12)

với tập huấn luyện 𝒟 được tạo ra bởi các bước đi ngẫu nhiên bắt đầu từ từng
đỉnh, hay nói cách khác là N cặp cho mỗi đỉnh 𝑣𝑖 được lấy từ phân phối (𝑣𝑖 , 𝑣𝑗 ) ∼
𝑝𝒢,𝑇 (𝑣𝑗 |𝑣𝑖 ). Tuy nhiên, việc đánh giá hàm mất mát một cách đơn giản trong
phương trình trên là cực kỳ tốn kém, bởi vì tính tốn mẫu số của phương trình
(1.11) rất mất thời gian vì độ phức tạp cao. Do đó, DeepWalk và node2vec sử dụng
các tối ưu hóa và xấp xỉ khác nhau để tính tốn hàm mất mát mục tiêu. DeepWalk
sử dụng kỹ thuật "softmax phân cấp" để tính tốn hệ số chuẩn hóa, sử dụng cấu
trúc cây nhị phân để tăng tốc độ tính tốn [2]. Ngược lại, node2vec xấp xỉ Phương
trình (1.12) bằng cách sử dụng “lấy mẫu âm”: thay vì chuẩn hóa trên tập đỉnh đầy
đủ, node2vec ước lượng hệ số chuẩn hóa bằng cách sử dụng một tập hợp các “mẫu
âm” ngẫu nhiên [5].
Ngoài những khác biệt về thuật toán này, sự khác biệt chính giữa node2vec
và DeepWalk là node2vec cho phép định nghĩa linh hoạt về các bước đi ngẫu nhiên,

16