ĐẠ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.
