VIETNAM NATIONAL UNIVERSITY - HO CHI MINH CITY HO CHI MINH CITY UNIVERSITY OF TECHNOLOGY FACULTY OF COMPUTER SCIENCE & TECHNOLOGY CAPSTONE PROJECT ACADEMIC AFFAIRS-SUPPORTED KNOWLEDGE GRAPH CONSTRUCTION FROM UNSTRUCTURED DATA Major: COMPUTER SCIENCE Thesis Committee: Computer Science 01 Quan Thanh Tho, PhD - Chairman Nguyen Quang Duc, MSc - Secretary Vu Van Tien, MSc - Commissioner Supervisors: Quan Thanh Tho, PhD - HCMUT, Vietnam Bui Cong Tuan, MSc - HCMUT, Vietnam Reviewer: Tran Tuan Anh, PhD - HCMUT, Vietnam Student: Tran Ngoc Oanh - 2053312 HO CHI MINH CITY - MAY 2024 VIETNAM NATIONAL UNIVERSITY - HO CHI MINH CITY HO CHI MINH CITY UNIVERSITY OF TECHNOLOGY FACULTY OF COMPUTER SCIENCE & TECHNOLOGY CAPSTONE PROJECT ACADEMIC AFFAIRS-SUPPORTED KNOWLEDGE GRAPH CONSTRUCTION FROM UNSTRUCTURED DATA Major: COMPUTER SCIENCE Thesis Committee: Computer Science 01 Quan Thanh Tho, PhD - Chairman Nguyen Quang Duc, MSc - Secretary Vu Van Tien, MSc - Commissioner Supervisors: Quan Thanh Tho, PhD - HCMUT, Vietnam Bui Cong Tuan, MSc - HCMUT, Vietnam Reviewer: Tran Tuan Anh, PhD - HCMUT, Vietnam Student: Tran Ngoc Oanh - 2053312 HO CHI MINH CITY - MAY 2024 Declaration of Authenticity The author, Trần Ngọc Oanh, declare that this Capstone Project was composed and implemented entirely by the author under the guidance and supervision of Assoc. Quản Thành Thơ and Mr. Bùi Công Tuấn at the Faculty of Computer Science and Engineering, Vietnam National University - Ho Chi Minh City University of Technology. In the process of researching and implementing this Capstone Project, the author has referenced multiple previous studies from other people and themselves.
All of the referenced work have been fully and clearly stated in the References part. This Capstone Project has not been published in any form under any circumstances. The author, Trần Ngọc Oanh i Acknowledgements First and foremost, the author would like to express their sincere thankfulness to Assoc. Quan Thanh Tho and Mr.
Bui Cong Tuan. Thank you for allocating your valuable time to guide, orientate and encourage the author throughout the outline and implementation phase of this Capstone Project. Next, the author are grateful that the lecturers at the Faculty of Computer Science and Engineer- ing, Vietnam National University - Ho Chi Minh City University of Technology have delivered the author sufficient fundamental knowledge, which serves as the springboard so that the author can compose this thesis and contribute to the Vietnamese Computer Science field. In addition, the author would like to cheer herself for their efforts when full-time internship and thesis composition happens simultaneously.
Although making the first step was not easy, she did not give up. By constructing a sensible plan and putting best efforts, the author is able to keep up with the track and finish the project just in time. Last but not least, the author would like to thank her family for always supporting them on their journey at university. Her parents’ diligence has become the largest source of motivation for the author to work hard.
Furthermore, seniors at her companies also conscientiously guide and train them in a professional working environment where the author takes part in practical application projects, which really shapes her individual thoughts and behaviors to be better. The author, Trần Ngọc Oanh ii Abstract Navigating academic affairs can be challenging due to dispersed and intricate regulations, poli- cies, and procedures. At Ho Chi Minh City University of Technology (HCMUT), the problem is exacerbated by the manual handling of student inquiries by academic staff, leading to inefficien- cies and inconsistencies. This thesis proposes constructing a comprehensive knowledge graph to consolidate and structure educational data, enabling efficient information retrieval and dis- semination.
The integration of a knowledge graph with advanced natural language processing techniques aims to provide students with accurate, timely responses while reducing the work- load on academic staff. The primary objective is to develop an unsupervised knowledge graph construction pipeline from multiple data sources. Notably, FAQ datasets reveal user intentions consistently, which can be leveraged as nodes in the knowledge graph. This approach eliminates the need for prede- fined labels and domains, making it universally applicable.
The project focuses on three key challenges: intentional entity discovery from unstructured text, relationship discovery using embedding-based methods, and multilingual applicability. By customizing intent detection for Vietnamese conversational datasets, we aim to enhance the information retrieval process at HC- MUT. Significant contributions include defining a graph structure with intents as entities, developing an unsupervised framework for entity discovery, employing an embedding-based approach for relation discovery, and implementing the proposed pipeline on HCMUT’s dataset. This project holds promise for improving the accessibility and efficiency of academic information dissemi- nation, ultimately benefiting both students and faculty.
iii Contents Declaration of Authenticity i Acknowledgements ii Abstract iii 1 Introduction 3 1.5 Capstone Project structure .6 Part-of-Speech Tagging. 32 iv 3 Related Works 34 3.1 Knowledge Graph Construction .1 Graph Ontologies and Case Study at HCMUT .2 Multi-source dataset from HCMUT .3 Case Study at HCMUT .2 Our proposed method: E-OED .4 Result and Analysis .4 HCMUT Case Study. 65 A LLMs choices’ Explanation 72 B Task assignment 74 C AIQAM’24: The First ACM Workshop on AI-Powered Q&A Systems for Multi- media Submission Paper 75 v List of Tables 2.1 With NSP and without NSP .1 From [56], Summary Details of the Selected Articles .2 Comparison of designs of classical and recent sentence-level RC models (ar- ranged in terms of publication year in each category) from [66] .2 Data censored tool .3 Multi-source dataset details .4 List of Experiments .5 Open intent discovery result .6 Design selection result .7 Relation discovery result .8 Relations discovery setting result .1 Commercial LLMs benchmark from their technical report. 72 1 List of Figures 2.1 BERT model architecture .2 Masked Language Modeling approach .3 Next Sentence Prediction approach .5 3-way softmax classifier architecture .6 Comparison of data augmentations on STS-B development set (Spearman’s cor- relation) (Paper source) .7 The architecture of BERTopic .8 Characters of M3-Embedding .9 This figure is a knowledge graph representation of a subset of Diffbot’s database [37] .10 A visualization on extracting entities and relationships from text to construct a knowledge graph[7] .1 The general process of constructing a knowledge graph .2 Taxonomy of works in knowledge graph construction .3 The general process of Entity discovery from paper [66] .1 Graph ontologies with main entities being intents discovered .2 Multi-source educational data at HCMUT .3 Graph representation developed from educational data at HCMUT .4 Workflow of our method .5 List of some discovered intents .6 Embedding-based Relation Discovery flow .7 Raw data without processing .9 BANKING77 dataset viewer .10 Example of majority voting .11 A sub graph extracted from HCMUT using proposed framework .1 Ranking of LLMs on Vellum.
73 2 1 Introduction In Chapter 1, the authors will present an overview of the urgency of the topic, objectives, and scope of the project’s research. The report outline will also be presented.1 Motivation Navigating the complex landscape of academic affairs can be a daunting task for students and faculty alike. Academic regulations, policies, and procedures are often scattered across various sources, making it difficult to find relevant information and understand the intricate details. This lack of accessibility and clarity can lead to confusion, frustration, and potential violations of university rules.
At Ho Chi Minh City University of Technology (HCMUT), the situation is no different. With a wealth of educational data originating from diverse sources such as legal documents, frequently asked questions (FAQs), news articles, databases, and API-enabled systems, the university faces a significant challenge in consolidating and disseminating this information effectively. Cur- rently, academic affairs staff at HCMUT are tasked with manually answering student inquiries, a process that is both resource-intensive and time-consuming. This approach not only places a heavy burden on the staff but also fails to provide students with timely and consistent responses.
The construction of a comprehensive knowledge graph for academic affairs at HCMUT presents a promising solution to these challenges. By consolidating and structuring the university’s edu- cational data into a unified knowledge base, a knowledge graph would enable efficient informa- tion retrieval and dissemination. Moreover, the integration of a knowledge graph with advanced language models and natural language processing techniques would allow students to ask ques- tions in natural language and receive accurate, relevant responses. This would not only enhance the student experience but also alleviate the workload on academic affairs staff, enabling them to focus on more critical tasks.
However, constructing knowledge graphs from raw text presents challenges, particularly in identifying entities and relationships. Previous approaches to entity discovery heavily relied on supervised methods, requiring sig- nificant human effort and time. This dependence on labeled data also restricts the approach to specific domains, necessitating separate models for each. To overcome these limitations, we pro- pose an unsupervised approach that involves clustering similar text snippets and automatically assigning labels to the clusters.
This leverages pre-trained models to generate text embeddings, allowing for efficient clustering algorithms. Our work builds upon the approach proposed by Grootendorst, BERTopic [21], which involves clustering text based on their intended meaning and automatically assigning labels using part-of-speech and dependency parsing methods. We will customize this approach for Vietnamese conversational datasets and subsequently develop the knowledge graph, aiming to unlock new possibilities for information retrieval and genera- tion. In summary, the motivation behind this capstone project is to address the pressing need for efficient and accessible information retrieval in the realm of academic affairs at HCMUT.
By 4 leveraging the power of knowledge graphs and language models, this project aims to streamline the dissemination of academic regulations, policies, and procedures, ultimately enhancing the overall experience for both students and faculty.2 Goals The main objective of this project is to develop an unsupervised knowledge graph construc- tion pipeline from multiple data sources. While analyzing HCMUT FAQ dataset, we observed a noteworthy pattern: in every FAQ dataset, users’ questions consistently convey their intentions. By employing a method to expose these intentions, we can effectively utilize them as nodes within our knowledge graph. This observation holds true across diverse domains, eliminating the need for pre-specifying de- tails such as the number or labels of intentions.
Consequently, this revelation introduces a novel approach for accomplishing our task—leveraging intention detection to unveil nodes within the knowledge graph. Ideally, users could input a conversational dataset and receive a list of inten- tional entities suitable for constructing a knowledge graph, regardless of the domain. From the entities, Knowledge graph can be constructed suing embedding-based cross-data for relation discovery. Achieving these goals necessitates a solid foundation in natural language processing (NLP) and clustering algorithms.
Moreover, we have to conduct a thorough literature review of some re- lated works on graph construction. Then, we can come up with a new pipeline which holds promising results. After all, we will summarize our work, give some future directions, and pre- pare for the next steps.3 Scope In this project, we aim to address three key challenges in constructing a knowledge graph:: • Intentional Entity Discovery: This vital component of our project focuses on identifying open intentional entities within unstructured text found in FAQ conversations. Given a conversational dataset, our pipeline will extract intents as entities.
• Relationship Discovery: Relationship is also a vital part of a knowledge graph. Our pipeline uses the intentional entities discovered in the previous step along with other entities from our multiple data sources to perform relationship discovery using an embedding-based method. • Multilingual: the proposed pipeline can work not only in one language but also in oth- ers. However, it requires a conversational dataset to perform intentional entity discovery, 5 which, in most real-life scenarios, is FAQ conversations.4 Contribution With the objectives and scope of this Capstone Project clearly defined, notable accomplishments have been achieved.
The contributions of this work can be summarized as follows: i. We define a graph structure that includes intents as entities and edges. Our automatic unsu- pervised framework E-OED is able to produce this structure for unstructured conversational datasets.
