Luận văn thạc sĩ: Nghiên cứu kỹ thuật học sâu để biểu diễn đô thị không đồng nhất

Luận văn thạc sĩ nghiên cứu máy tính nghiên cứu kỹ thuật học sâu để biểu diễn đô thị không đồng nhất, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện pháp hoàn thiện trong

• Tác giả: Nguyễn Thanh Toàn
• Người hướng dẫn: PGS. Quản Thành Thơ
• Trường học: Đại học Bách Khoa - ĐHQG-HCM
• Chuyên ngành: Khoa học máy tính
• Đề tài: Nghiên cứu kỹ thuật học sâu để biểu diễn đồ thị không đồng nhất
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2019
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• Acknowledgments
• Abstract (English)
• Abstract (Vietnamese)
• Declaration
• List of Figures
• List of Tables
• 1. CHƯƠNG 1: INTRODUCTION
• 1.1. Overview
• 1.2. What is Network Alignment?
• 1.3. Heterogeneous Network Representation by Network Alignment
• 1.4. Research Challenge
• 1.5. Applications
• 1.5.1. Social networks analysis
• 1.5.2. Bioinformatic networks analysis
• 1.5.3. Pattern recognition and image processing
• 1.6. Contributions of the Thesis
• 1.6.1. The pilot study I: Weakly-supervised network alignment
• 1.6.2. The pilot study II: Unsupervised network alignment
• 2. CHƯƠNG 2: RELATED WORK
• 2.1. Traditional alignment methods
• 2.2. Representation learning methods
• 3. CHƯƠNG 3: RESEARCH BACKGROUND AND PROBLEM STATEMENT
• 3.1. Problem Statement and Formulation
• 4. CHƯƠNG 4: WEAKLY-SUPERVISED NETWORK ALIGNMENT: A Pilot Study
• 4.1. Rough alignment under a GAN-based setting
• 4.2. Weakly-supervised Learning
• 4.3. Experimental Results and Analysis
• 4.3.1. Comparative performance to unsupervised methods
• 4.3.2. Comparative performance to supervised methods
• 5. CHƯƠNG 5: UNSUPERVISED NETWORK ALIGNMENT: A Pilot Study
• 5.1. Overview of NAWAL Framework
• 5.2. Reconciling embedding spaces
• 5.2.1. Rough alignment under a GAN-based setting
• 5.3. Retrieving alignment result
• 5.4. Alignment Performance Analysis
• 5.4.1. Robustness to structural noise
• 5.4.2. Robustness to graph size imbalance
• 6. CHƯƠNG 6: CONCLUSION AND FUTURE WORK
• 6.1. Summary of the work
• 6.2. Novelty of the thesis outcomes
• 6.3. Limitations and Future Directions
• Bibliography
• Appendix A: General Experimental Settings
• Curriculum Vitae

Tóm tắt

I. Giới thiệu

Nghiên cứu kỹ thuật học sâu trong biểu diễn đô thị không đồng nhất đã trở thành một lĩnh vực quan trọng trong khoa học máy tính, đặc biệt là trong việc phân tích mạng. Mạng là một ngôn ngữ phổ quát để mô tả dữ liệu phức tạp, cho phép người nghiên cứu nắm bắt mối quan hệ giữa các thực thể khác nhau. Việc phân tích hiệu quả các dữ liệu mạng không đồng nhất có thể hỗ trợ nhiều ứng dụng thực tiễn, bao gồm dự đoán liên kết, phân loại nút và phát hiện cộng đồng. Tuy nhiên, nhiều nghiên cứu hiện tại chỉ tập trung vào các mạng đồng nhất, trong khi thực tế thường yêu cầu phân tích nhiều mạng khác nhau. Do đó, việc phát triển các mô hình biểu diễn mạng không đồng nhất thông qua các kỹ thuật học sâu là cần thiết.

II. Kỹ thuật học sâu trong biểu diễn đô thị

Kỹ thuật học sâu đã được áp dụng để phát triển các mô hình biểu diễn đô thị không đồng nhất. Mô hình này cho phép hợp nhất thông tin từ các mạng đơn lẻ vào một không gian vector chung, giúp cải thiện khả năng suy diễn và phân tích mạng. Các phương pháp hiện tại bao gồm việc sử dụng mạng nơ-ron để học các biểu diễn từ các mạng khác nhau, từ đó tạo ra một mô hình mạnh mẽ cho việc căn chỉnh mạng. Điều này không chỉ giúp giải quyết bài toán căn chỉnh mạng mà còn cho phép khai thác thông tin từ nhiều nguồn khác nhau để cải thiện độ chính xác và độ tin cậy của các kết quả phân tích.

III. Phân tích dữ liệu không đồng nhất

Phân tích dữ liệu không đồng nhất là một thách thức lớn trong khoa học dữ liệu. Các nguồn dữ liệu khác nhau có thể có cấu trúc và định dạng khác nhau, dẫn đến khó khăn trong việc kết hợp và phân tích. Việc áp dụng các kỹ thuật học sâu có thể giúp tự động hóa quá trình này bằng cách học từ các mẫu dữ liệu và xác định các mối liên hệ giữa chúng. Các phương pháp như mô hình hóa và khai thác dữ liệu giúp phát hiện các mẫu và xu hướng trong dữ liệu không đồng nhất, từ đó cung cấp các thông tin quý giá cho các quyết định quản lý và phát triển đô thị.

IV. Ứng dụng của nghiên cứu

Nghiên cứu về kỹ thuật học sâu trong biểu diễn đô thị không đồng nhất có nhiều ứng dụng thực tiễn. Trong lĩnh vực phân tích mạng xã hội, việc căn chỉnh các tài khoản của người dùng trên nhiều nền tảng khác nhau có thể giúp cải thiện độ chính xác của các gợi ý và dự đoán. Trong lĩnh vực y sinh học, phân tích các mạng tương tác protein có thể cung cấp thông tin quý giá cho việc ưu tiên gen. Ngoài ra, nghiên cứu cũng có thể áp dụng trong nhận dạng mẫu và xử lý hình ảnh, giúp cải thiện hiệu suất của các thuật toán nhận dạng trong các tình huống phức tạp.

V. Kết luận

Tóm lại, nghiên cứu kỹ thuật học sâu trong biểu diễn đô thị không đồng nhất không chỉ đóng góp vào lý thuyết mà còn mang lại giá trị thực tiễn cao. Việc phát triển các mô hình mạnh mẽ và hiệu quả cho phép khai thác thông tin từ nhiều mạng khác nhau, từ đó cải thiện khả năng phân tích và ra quyết định trong nhiều lĩnh vực khác nhau. Những kết quả này mở ra hướng đi mới cho nghiên cứu và ứng dụng trong tương lai.

Nội dung chính

Tổng quan nghiên cứu

Trong kỷ nguyên dữ liệu lớn, các hệ thống mạng phức thức như mạng xã hội, mạng kinh tế và mạng tương tác sinh học đang bùng nổ với quy mô hàng tỷ nút và hàng chục tỷ cạnh liên kết. Tuy nhiên, phần lớn các phương pháp khai phá dữ liệu đồ thị hiện nay chỉ tập trung vào các mạng đơn lẻ và đồng nhất, trong khi các ứng dụng thực tế đòi hỏi khả năng tích hợp và biểu diễn đồ thị không đồng nhất (heterogeneous networks) từ nhiều miền dữ liệu khác nhau. Bài toán căn chỉnh mạng (network alignment) nhằm xác định sự tương ứng giữa các thực thể qua các mạng độc lập vốn là bài toán thuộc lớp NP-khó với chi phí tính toán tăng theo cấp số nhân. Đồng thời, việc thu thập dữ liệu liên kết neo (anchor links) có giám sát đòi hỏi chi phí nhân công rất lớn hoặc hoàn toàn bất khả thi do chính sách bảo mật thông tin người dùng.

Nghiên cứu của học viên Nguyễn Thanh Toàn, dưới sự hướng dẫn của Phó Giáo sư Quản Thành Thơ tại Trường Đại học Bách Khoa – Đại học Quốc gia Thành phố Hồ Chí Minh (bảo vệ tháng 07 năm 2019), đã giải quyết triệt để rào cản này. Luận văn tập trung đề xuất hai khung mô hình học sâu đột phá: WENA (Weakly-supervised Network Alignment) và NAWAL (Representation learning-based Network Alignment Without Anchor Links). Mục tiêu chính là chiếu không gian nhúng của các mạng đơn lẻ vào một không gian vector chung mà không phụ thuộc vào dữ liệu gán nhãn diện rộng. Kết quả thực nghiệm cho thấy mô hình đạt độ chính xác căn chỉnh vượt trên 90% ngay cả khi cấu trúc mạng xuất hiện 20% nhiễu, mở ra bước tiến quan trọng cho các bài toán phân loại nút, dự đoán liên kết và gợi ý đa nền tảng.

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

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng trên nền tảng ba trụ cột lý thuyết và mô hình tính toán hiện đại:

• Lý thuyết học biểu diễn đồ thị (Graph Representation Learning): Ánh xạ từng nút mạng $v \in V$ sang một vector liên tục $z_v \in \mathbb{R}^d$ trong không gian tiềm ẩn số chiều thấp ($d \ll |V|$), giúp bảo toàn cấu trúc topo và mối quan hệ lân cận bậc một giữa các thực thể.
• Khung mô hình mạng sinh đối kháng (Generative Adversarial Networks - GAN): Thiết lập trò chơi minimax giữa bộ tạo ánh xạ tuyến tính (Aligner) và bộ phân biệt (Discriminator) nhằm tối thiểu hóa phân kỳ Kullback-Leibler giữa phân phối biểu diễn của mạng nguồn và mạng đích mà không cần giám sát chéo.
• Bài toán căn chỉnh trực giao Procrustes (Orthogonal Procrustes Problem): Ứng dụng phép phân rã giá trị suy biến (Singular Value Decomposition - SVD) để tìm ma trận xoay tối ưu, bảo toàn tích vô hướng và khoảng cách hình học giữa các vector biểu diễn.

Các khái niệm then chốt xuyên suốt luận văn bao gồm: tính nhất quán cấu trúc (structural consistency), liên kết neo (anchor links), nhiễu cấu trúc mạng (structural noise) và độ tương đồng không gian tiềm ẩn (latent space similarity).

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

Nghiên cứu sử dụng nguồn dữ liệu thực nghiệm chuẩn quốc tế gồm: mạng tương tác protein PPI với hàng nghìn liên kết sinh học, mạng kinh tế ECON, mạng liên kết tế bào não BN, cùng ba bộ dữ liệu mạng xã hội quy mô lớn gồm Facebook, Twitter và Foursquare.

Phương pháp chọn mẫu áp dụng cơ chế lấy mẫu âm (Negative Sampling) với phân phối xác suất bậc nút $P(v) \sim d_v^{3/4}$ và số lượng mẫu âm $K = 5$, giúp tối ưu hóa hàm hợp lý logarit (log-likelihood) của các cặp nút kề nhau. Quá trình phân tích dữ liệu kết hợp giải thuật tối ưu hóa Stochastic Gradient Descent (SGD) theo từng mini-batch với giải thuật khớp tham lam (Greedy Matching) trên ma trận tương đồng $S = (W Z_s) Z_t^T$. Lý do lựa chọn phương pháp tiếp cận này là nhằm giảm thiểu chi phí tính toán từ cấp số nhân của các phương pháp ma trận truyền thống xuống mức tuyến tính, đồng thời loại bỏ định kiến do bước lấy mẫu ngẫu nhiên bậc cao gây ra. Toàn bộ timeline thực nghiệm và hoàn thiện thuật toán được tiến hành liên tục từ tháng 02 năm 2019 đến tháng 07 năm 2019.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình đánh giá thực nghiệm đã ghi nhận 4 phát hiện khoa học mang tính đột phá:

• Vượt trội vượt bậc so với các phương pháp phi giám sát: Trên ba tập dữ liệu PPI, BN và ECON ở mức nhiễu cấu trúc 20%, mô hình WENA đạt độ chính xác căn chỉnh trung bình 89.52%, trong khi phương pháp phi giám sát tốt nhất trước đó là REGAL chỉ đạt 32.28% (mức cải thiện đạt 57.24%), còn FINAL và BigAlign chỉ đạt lần lượt khoảng 35% và 27.1%.
• Hiệu năng tương đương hoặc vượt qua các mô hình có giám sát đầy đủ: Dù chỉ sử dụng đúng 2 liên kết neo định hướng, WENA đạt độ chính xác 90% đến 99%, vượt trội 28.8% so với mô hình giám sát DeepLink (chỉ đạt 54% đến 76% khi có 20% nhiễu) và tương đương với mô hình PALE vốn đòi hỏi tới 20% dữ liệu nhãn mẫu.
• Khả năng tự thích ứng hoàn toàn không cần nhãn của NAWAL: Mô hình NAWAL loại bỏ hoàn toàn nhu cầu về liên kết neo (0 anchor links) nhưng vẫn duy trì độ chính xác cao và khả năng chống chịu hiện tượng mất cân bằng kích thước đồ thị (graph size imbalance) trên mạng xã hội Facebook và Twitter.
• Độ bền vững vượt trội trước nhiễu cấu trúc: Khi tỷ lệ nhiễu tăng từ 0% lên 20%, độ chính xác của WENA trên tập dữ liệu ECON chỉ suy giảm nhẹ từ 99% xuống 92% (giảm 7%), trong khi mô hình DeepLink sụt giảm nghiêm trọng từ 81% xuống 55% (mất 26% độ chính xác).

Thảo luận kết quả

Sự vượt trội của mô hình xuất phát từ việc khắc phục nhược điểm cốt tử của các thuật toán phân rã ma trận cổ điển (như IsoRank, BigAlign hay FINAL). Các phương pháp cũ giả định cấu trúc mạng giữa hai miền phải hoàn toàn bảo toàn bậc lân cận, khiến giải thuật sụp đổ khi dữ liệu thực tế xuất hiện liên kết giả hoặc thiếu hụt cạnh. Trong khi đó, WENA và NAWAL tận dụng không gian nhúng liên tục kết hợp kỹ thuật học đối kháng để căn chỉnh phân phối tổng thể trước khi tinh chỉnh cục bộ.

Khi trình bày qua biểu đồ phân tán giảm chiều PCA (Principal Component Analysis), dữ liệu không gian nhúng của mạng nguồn và mạng đích trước khi huấn luyện nằm ở hai cụm phân tách hoàn toàn riêng biệt. Sau khi áp dụng cơ chế căn chỉnh đối kháng và ràng buộc trực giao với hệ số co giãn xấp xỉ 0.01, hai phân phối dữ liệu đã hòa nhập và khớp nối chính xác trên cùng một hệ tọa độ. So với các nghiên cứu cùng thời kỳ, việc áp dụng biến đổi Procrustes đóng kín giúp thuật toán duy trì tính ổn định toán học cao hơn hẳn việc chỉ dựa vào mạng nơ-ron truyền xuôi thông thường.

Đề xuất và khuyến nghị

Dựa trên kết quả nghiên cứu, 4 khuyến nghị ứng dụng thực tiễn và định hướng phát triển được đề xuất:

• Tích hợp thuật toán WENA vào hệ thống gợi ý xuyên nền tảng (Cross-network Recommendation): Đội ngũ kỹ sư dữ liệu tại các doanh nghiệp thương mại điện tử và mạng xã hội cần triển khai mô hình trong lộ trình 6 tháng, đặt mục tiêu nâng cao 25% độ chính xác trong gợi ý kết bạn và sản phẩm liên nền tảng, đồng thời cắt giảm 90% chi phí thu thập thông tin định danh người dùng.
• Ứng dụng khung NAWAL vào phân tích sinh tin học và dự đoán tương tác sinh học: Các viện nghiên cứu y sinh học nên áp dụng giải thuật căn chỉnh không giám sát trong giai đoạn 3 đến 6 tháng để đối sánh mạng protein-protein (PPI) liên loài, hướng tới mục tiêu nâng tỷ lệ phát hiện tương đồng chức năng gen và protein lên trên 85%.
• Tối ưu hóa ràng buộc trực giao xấp xỉ trong huấn luyện nhúng phân tán: Các nhóm phát triển thuật toán AI cần mở rộng phương thức cập nhật ma trận trực giao với tham số co giãn 0.01 lên các hệ thống tính toán phân tán trong vòng 12 tháng, nhằm giảm 35% thời gian huấn luyện trên các đồ thị có quy mô trên 10 triệu nút.
• Xây dựng giải pháp giám sát và truy vết luồng tin giả đa nền tảng: Cơ quan quản lý an toàn thông tin và truyền thông cần xây dựng công cụ phát hiện tài khoản ảo đồng nhất trên Facebook, Twitter và TikTok trong giai đoạn 2024-2025, hướng đến chỉ số nhận diện chính xác mạng lưới phát tán tin giả đạt trên 90%.

Đối tượng nên tham khảo luận văn

Luận văn là tài liệu tham khảo giá trị cho 4 nhóm đối tượng chuyên môn:

• Học viên cao học và nghiên cứu sinh chuyên ngành Khoa học Máy tính / Trí tuệ Nhân tạo: Nắm bắt phương pháp luận nghiên cứu chuyên sâu về học biểu diễn đồ thị không đồng nhất, kỹ thuật đối kháng GAN và cách tiếp cận bài toán tối ưu hóa NP-khó trong khoa học mạng.
• Kỹ sư Machine Learning và Data Scientist tại các tập đoàn công nghệ: Vận dụng trực tiếp mã nguồn và kiến trúc mô hình WENA/NAWAL để xây dựng các tính năng gợi ý kết nối, hợp nhất dữ liệu khách hàng (Customer Data Platform) từ nhiều nguồn dữ liệu rời rạc.
• Nhà nghiên cứu trong lĩnh vực Tin sinh học (Bioinformatics): Sử dụng khung căn chỉnh mạng để so sánh mạng lưới sinh học phân tử giữa các loài sinh vật, phục vụ công tác giải mã gen, phát hiện mục tiêu thuốc và nghiên cứu tiến hóa protein.
• Chuyên gia phân tích an ninh mạng và dữ liệu truyền thông: Khai thác giải thuật căn chỉnh thực thể để truy vết các chiến dịch truyền thông độc hại, phát hiện cấu trúc tài khoản ảo xuyên biên giới với độ chính xác và khả năng kháng nhiễu cao.

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

• Khái niệm căn chỉnh mạng (Network Alignment) có vai trò gì trong biểu diễn đồ thị không đồng nhất? Căn chỉnh mạng là bài toán xác định các nút tương ứng giữa hai hay nhiều mạng độc lập để hợp nhất thông tin vào một không gian vector chung. Điều này cho phép trích xuất tri thức từ các miền dữ liệu không đồng nhất, phục vụ phân tích dự đoán mà các mô hình đơn mạng không thể thực hiện.

• Tại sao mô hình WENA chỉ cần 2 liên kết neo mà vẫn đạt độ chính xác trên 90%? WENA sử dụng mạng GAN để căn chỉnh sơ bộ phân phối không gian nhúng của hai đồ thị về cùng một miền giá trị. Do đó, chỉ cần đúng 2 cặp điểm neo làm mốc định hướng, phép biến đổi trực giao Procrustes đã có thể xoay toàn bộ không gian vector về vị trí tối ưu với độ chính xác cao.

• Điểm khác biệt cốt lõi giữa NAWAL và các thuật toán truyền thống như IsoRank hay REGAL là gì? Các phương pháp truyền thống thao tác trực tiếp trên ma trận kề với độ phức tạp cấp số nhân và rất dễ gãy đổ khi có nhiễu cấu trúc. Ngược lại, NAWAL ánh xạ đồ thị sang không gian nhúng liên tục số chiều thấp và tự sinh liên kết neo nhân tạo, giúp mô hình hoạt động hoàn toàn phi giám sát và xử lý được mạng quy mô lớn.

• Cơ chế huấn luyện đối kháng GAN hoạt động như thế nào trong bài toán này? Bộ tạo đóng vai trò là hàm ánh xạ tuyến tính tìm cách biến đổi vector mạng nguồn sao cho giống mạng đích nhất. Bộ phân biệt đóng vai trò phân loại nhị phân để phân biệt vector thực và vector chuyển đổi. Quá trình huấn luyện minimax buộc không gian nhúng của hai mạng tiệm cận phân phối của nhau.

• Luận văn đã kiểm chứng độ bền vững trước nhiễu cấu trúc trên các bộ dữ liệu nào? Mô hình đã được thử nghiệm thực chứng trên ba mạng khoa học gồm mạng protein PPI, mạng não bộ BN, mạng kinh tế ECON và ba mạng xã hội thực tế Facebook, Twitter, Foursquare. Kết quả cho thấy độ chính xác luôn duy trì trên 90% ở mức nhiễu topo từ 10% đến 20%.

Kết luận

• Đóng góp học thuật cốt lõi: Luận văn đã giải quyết xuất sắc thách thức biểu diễn đồ thị không đồng nhất thông qua hai khung mô hình học sâu WENA và NAWAL, phá vỡ sự phụ thuộc vào dữ liệu gán nhãn lớn trong căn chỉnh mạng.
• Đột phá về mặt thuật toán: Kết hợp thành công kỹ thuật nhúng mạng bậc một, học đối kháng GAN, ràng buộc ma trận trực giao Procrustes và giải thuật khớp tham lam để tối ưu hóa thời gian tính toán.
• Hiệu năng thực nghiệm vượt trội: Đạt độ chính xác trên 89.52% ở mức nhiễu 20%, cải thiện 57.24% so với mô hình phi giám sát REGAL và vượt qua các mô hình có giám sát như DeepLink.
• Khả năng ứng dụng đa ngành: Mở rộng phạm vi triển khai từ hệ thống gợi ý thương mại điện tử, mạng xã hội đến các bài toán tin sinh học và an ninh mạng.
• Kế hoạch phát triển tiếp theo: Nghiên cứu mở rộng thuật toán căn chỉnh đồng thời đa mạng (trên 3 đồ thị) và tích hợp các đặc trưng thuộc tính nút phức tạp trong giai đoạn tới. Hãy áp dụng ngay giải pháp WENA/NAWAL để tối ưu hóa bài toán tích hợp dữ liệu đồ thị trong các dự án công nghệ của bạn.

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

ĐẠI HỌC QUỐC GIA TP. HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA -------------------- NGUYỄN THANH TOÀN NGHIÊN CỨU KỸ THUẬT HỌC SÂU ĐỂ BIỂU DIỄN ĐỒ THỊ KHÔNG ĐỒNG NHẤT Chuyên ngành : KHOA HỌC MÁY TÍNH Mã số: 60.01 LUẬN VĂN THẠC SĨ TP. HỒ CHÍ MINH, tháng 07 năm 2019 CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRƯỜNG ĐẠI HỌC BÁCH KHOA – ĐHQG-HCM Cán bộ hướng dẫn khoa học: PGS. QUẢN THÀNH THƠ Cán bộ chấm nhận xét 1: TS.

NGUYỄN THANH HIÊN Cán bộ chấm nhận xét 2: PGS. HUỲNH TRUNG HIẾU Luận văn thạc sỹ được bảo vệ tại Trường Đại học Bách Khoa, ĐHQG Tp.HCM ngày 03 tháng 07 năm 2019. Thành phần Hội đồng đánh giá luận văn thạc sỹ gồm: 1. Chủ tịch hội đồng: PGS.

DƯƠNG TUẤN ANH 2. Thư ký hội đồng: TS. NGUYỄN LÊ DUY LAI 3. Uỷ viên phản biện 1: TS.

NGUYỄN THANH HIÊN 4. Uỷ viên phản biện 2: PGS. HUỲNH TRUNG HIẾU 5. Uỷ viên hội đồng: TS.

NGUYỄN ĐỨC DŨNG Xác nhận của Chủ tịch Hội đồng đánh giá LV và Trưởng Khoa quản lý chuyên ngành sau khi luận văn đã được sửa chữa (nếu có). CHỦ TỊCH HỘI ĐỒNG TRƯỞNG KHOA KH&KTMT PGS. DƯƠNG TUẤN ANH ii ĐẠI HỌC QUỐC GIA TP.HCM CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM TRƯỜNG ĐẠI HỌC BÁCH KHOA Độc lập - Tự do - Hạnh phúc NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ tên học viên: Nguyễn Thanh Toàn MSHV: 1870428 Ngày, tháng, năm sinh: 16/10/1987 Nơi sinh: Tp.HCM Chuyên ngành: Khoa học máy tính Mã số : 64. TÊN ĐỀ TÀI: Nghiên cứu kỹ thuật học sâu để biểu diễn đồ thị không đồng nhất / On leveraging deep learning for heterogeneous network representation.

NHIỆM VỤ VÀ NỘI DUNG: Nghiên cứu kỹ thuật học sâu để đề xuất mô hình biểu diễn một cách hiệu quả các đồ thị không đồng nhất và có kích thước lớn. Tiến hành thực nghiệm và đánh giá hiệu quả của mô hình đề xuất so với các mô hình biểu diễn mới nhất trên thế giới. NGÀY GIAO NHIỆM VỤ: 11/02/2019 IV. NGÀY HOÀN THÀNH NHIỆM VỤ: 08/12/2019 V.

CÁN BỘ HƯỚNG DẪN: PGS. Quản Thành Thơ Tp. HCM, ngày 03 tháng 07 năm 2019 CÁN BỘ HƯỚNG DẪN TRƯỞNG KHOA KH&KTMT (Họ tên và chữ ký) (Họ tên và chữ ký) Ghi chú: Học viên phải đóng tờ nhiệm vụ này vào trang đầu tiên của tập thuyết minh LV iii Acknowledgments I would like to extend thanks to the many people, who so generously contributed to the work presented in this thesis report. Special mention goes to my supervisor, Prof.

Quan Thanh Tho. My master course is an amazing experience and I thank Professor Tho and other faculties wholeheartedly, not only for their tremendous academic support but also for giving me so many won- derful opportunities. Profound gratitude goes to all members in the group of Professor Tho for their whole- hearted support. Ho Chi Minh City, 03 Jul 2019 iv Abstract (English) Networks are universal languages for describing complex data.

The network data structure naturally captures relationships between entities from different fields, such as social networks, economics, and bioinformatics. Effective analyses on these data benefit a great range of subsequent research works and applications, including link prediction, node classification, and community detection. Many recent works only fo- cus on modeling single and homogeneous networks. However, real-world applications often require multiple network analyses, which leads to the need for a mechanism to effectively represent heterogeneous networks.

Sources of heterogeneity come from different domains. In this research, we leverage deep learning techniques for heteroge- neous network representation by merging information from different single networks into a common vectorial space in order to facilitate better inferences about networks. In particular, we find a mapping function that projects the source network embedding into the target network embedding to form the common vectorial representation of two domains. For simplicity, we focus on aligning two networks (e., social or protein networks), although our method can easily be extended to more networks.

The mapping function in this research is in line with the network alignment problem in computer science so that we use the metrics of network alignment to evaluate the efficiency of our representation learning algorithms. In the bulk of this thesis, we pro- pose two frameworks to tackle the network alignment: (1) Weakly-supervised network alignment with adversarial learning (WENA) and (2) Representation learning-based network alignment without anchor links (NAWAL). We conduct intensive experiments on many real-world datasets related to biological, economic, and social networks to demonstrate the potential impact of our frameworks. Empirical results show that with little to no ground truth is available, our frameworks significantly outperform existing unsupervised aligners and even outperform state-of-the-art supervised methods that use richer resources in terms of both noise robustness and accuracy.

Keywords: Heterogeneous network representation, network alignment, graph match- ing, node representation learning, network embedding, graph mining. v Abstract (Vietnamese) Mạng thông tin là một ngôn ngữ phổ quát dùng để biểu diễn nhiều loại dữ liệu phức tạp khác nhau. Cấu trúc dữ liệu dạng mạng giúp biểu diễn một cách tự nhiên mối quan hệ giữa các thực thể từ nhiều lĩnh vực khác nhau, chẳng hạn như mạng xã hội, mạng kinh tế, và mạng y sinh học. Việc phân tích hiệu quả các dữ liệu này có lợi cho một loạt các hoạt động nghiên cứu và các ứng dụng nối tiếp, bao gồm việc dự đoán liên kết mạng, phân loại nút trong mạng và phát hiện cộng đồng mạng.

Nhiều công trình gần đây chỉ tập trung vào việc biểu diễn các mạng đơn và đồng nhất. Tuy nhiên, các ứng dụng thực tiễn thường cần rút trích dữ liệu từ nhiều mạng khác nhau, điều đó dẫn đến sự cấp thiết phải có một cơ chế biểu diễn một cách hiệu quả dữ liệu mạng một cách không đồng nhất. Trong nghiên cứu này, chúng tôi sử dụng các kỹ thuật học sâu để biểu diễn đồ thị không đồng nhất bằng cách hợp nhất thông tin từ các mạng đơn lẻ riêng biệt vào một không gian biểu diễn chung, để làm cho các nhiệm vụ rút trích thông tin từ nhiều mạng trở nên dễ dàng hơn. Cụ thể là chúng ta tìm một hàm ánh xạ có thể chiếu không gian biểu diễn của mạng nguồn vào chung với không gian biểu diễn của mạng đích.

Để đơn giản, chúng tôi tập trung vào việc căn chỉnh hai mạng (ví dụ: mạng xã hội hoặc mạng protein), mặc dù phương pháp của chúng tôi có thể dễ dàng được mở rộng sang nhiều mạng hơn. Hàm ánh xạ trong nghiên cứu này tương ứng với bài toán căn chỉnh mạng (network alignment) trong khoa học máy tính, vì vậy chúng tôi sử dụng các độ đo của bài toán căn chỉnh mạng để đánh giá hiệu quả các phương pháp học biểu diễn đồ thị không đồng nhất được đề xuất. Trong phạm vi của luận án này, chúng tôi đề xuất hai mô hình để giải quyết bài toán căn chỉnh mạng: (1) Weakly-supervised network alignment with adversarial learning (WENA) and (2) Representation learning-based network alignment without anchor links (NAWAL). Chúng tôi thực hiện các thí nghiệm chuyên sâu trên nhiều bộ dữ liệu thực tế liên quan đến mạng y sinh học, mạng kinh tế và mạng xã hội để chứng minh hiệu quả của các phương pháp.

Kết quả thực nghiệm cho thấy rằng chỉ cần rất ít hoặc thậm chí không cần dữ liệu mẫu, các phương pháp của chúng tôi đề xuất cho kết quả vượt trội hơn đáng kể so với các phương pháp căn chỉnh mạng không giám sát hiện có, và thậm chí vượt trội so với các phương pháp được giám sát hiện đại sử dụng rất nhiều dữ liệu mẫu, về cả độ chính xác và độ chống chịu nhiễu về cấu trúc mạng. vi Declaration I, Nguyen Thanh Toan, declare that this thesis titled, "On leveraging deep learning for heterogeneous network representation" and the work presented in it are my own. I confirm that: • This work was done wholly or mainly while in candidature for a master by research degree at this University. • Where any part of this thesis has previously been submitted for a degree or any other qualification at this University or any other institution, this has been clearly stated.

• Where I have consulted the published work of others, this is always clearly attributed. • Where I have quoted from the work of others, the source is always given. With the exception of such quotations, this thesis is entirely my own work. • I have acknowledged all of the main sources of help.

Ho Chi Minh City, 03 Jul 2019 vii Contents Acknowledgments iv Abstract (English) v Abstract (Vietnamese) vi Declaration vii List of Figures xi List of Tables xiii 1 INTRODUCTION 1 1.2 What is Network Alignment? .3 Heterogeneous Network Representation by Network Alignment .1 Social networks analysis .2 Bioinformatic networks analysis .3 Pattern recognition and image processing .1 The pilot study I: Weakly-supervised network alignment .2 The pilot study II: Unsupervised network alignment .2 Representation learning methods. 13 3 RESEARCH BACKGROUND AND PROBLEM STATEMENT 15 3. 17 4 WEAKLY-SUPERVISED NETWORK ALIGNMENT: A Pilot Study 18 4.1 Rough alignment under a GAN-based setting .2 Weakly-supervised Learning .1 Comparative performance to unsupervised methods .2 Comparative performance to supervised methods. 28 5 UNSUPERVISED NETWORK ALIGNMENT: A Pilot Study 30 5.2 Reconciling embedding spaces .3 Retrieving alignment result .4 Reconciling embedding spaces .1 Rough alignment under a GAN-based setting .5 Alignment Result Retrieval .6 Alignment Performance Analysis .1 Robustness to structural noise .2 Robustness to graph size imbalance .1 Summary of the work .2 Novelty of the thesis outcomes .3 Limitations and Future Directions.

48 Bibliography 49 A Appendix A: General Experimental Settings 57 A. 59 Curriculum Vitae 60 x List of Figures 1.1 Gene Coexpression Network Alignment between maize and rice ([FF11]) 2 1.2 Heterogeneous network representation by merging networks from mul- tiple domains.3 Online Social Networks Alignment.4 Friend recommendation with network alignment .1 Overview of FINAL algorithm .2 Overview of REGAL algorithm .3 Overview of PALE algorithm .4 Overview of Deeplink algorithm .1 A motivating example of network alignment.1 Overview of the WENA Framework .3 Overview of the embedding approach .4 The neural network architecture for the embedding.5 Comparative performance to unsupervised methods (PPI).6 Comparative performance to unsupervised methods (BN).7 Comparative performance to unsupervised methods (ECON).8 Comparative performance to supervised methods (PPI).9 Comparative performance to supervised methods (BN).10 Comparative performance to supervised methods (ECON).11 The effect of alignment algorithm on the data distributions.1 Overview of NAWAL Framework.2 A GAN-based approach to learn the mapping.3 The neural network architecture for the discriminator training phase.4 The neural network architecture for the generator training phase.5 Robustness of algorithms to structural noise of Facebook dataset.6 Robustness of algorithms to structural noise of FourSquare dataset.7 Robustness of algorithms to structural noise of Twitter dataset. 42 xi List of Figures 5.8 Robustness of algorithms to graph size imbalance of Facebook dataset.9 Robustness of algorithms to graph size imbalance of FourSquare dataset.10 Robustness of algorithms to graph size imbalance of Twitter dataset.11 The effect of alignment algorithm on the data distributions. 46 xii List of Tables 4.1 Comparative performance to unsupervised methods (0.2 Comparative performance to supervised methods (0.1 Average performance of algorithms to structural noise.2 Average performance of algorithms to graph size imbalance.1 Overview Network, or graph, is a natural universal language for modeling complex systems appearing in every aspect of our daily life, ranging from Internet, ad-hoc wireless networks, social networks, road networks, trade networks to interacting genes and proteins networks.