Graph representation learning

• Main Author: Zhang, Xinyi
• Other Authors: Lihui Chen
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2022
• Subjects: Engineering::Computer science and engineering; Engineering::Electrical and electronic engineering
• Online Access: https://hdl.handle.net/10356/155039
• Institution: Nanyang Technological University

Graph is a type of structured data which is attracting increasing attention in recent years due to its strong capability in describing multiple objects as well as their relationships. Common graphs include social networks, biological networks, and chemical structures, and so on. Therefore, graph analysis becomes an important research area, and exploring methods to effectively and efficiently process graphs is a valuable research topic. Graph representation learning has been shown to be promising in graph analysis where the graphs or part of the graphs will be converted into a lower-dimensional space while the important information (e.g., structure information and attribute information) of the graph is still well preserved. By feeding these new generated lower-dimensional graph representations to the off-the-shelf machine learning methods(including neural networks), this graph-type of data can be analyzed and then applied in various real-world applications such as link prediction, community detection, node classification as well as graph classification. Currently, there are two main categories of graph representation learning methods, graph embedding based methods and graph neural network (GNN) based methods, which have respectively applicable scenarios. Graph embedding based methods aims to embed graph data into lower dimensional space during which the graph representations are learned by preserving predefined proximity. Then, the learned graph representations can be feed to different downstream models for different applications. However, in GNN-based methods, different GNN structures will be separately designed and trained for different applications. Besides different techniques used in graph representation learning, according to the fineness of the objects for embedding, the graph representation learning methods can be mainly divided into node-level, edge-level, and graph-level representation learning methods. Here, node-level and graph-level representation learning methods have attracted more attention since edge representations can be generated through node representations. Due to the diversity of graph types, objects of representation learning as well as their corresponding real-world applications, graph representation learning still faces various challenges, so different techniques need to be explored in different specific situations. In graph-level representation learning, the main challenge is how to effectively pool multiple node representations to generate high-quality graph representations where rich information needs to be encoded. However, the low encoding efficiency of scalar-based representations is still a problem. As for the node-level graph representation learning, traditional node-level representation learning methods focus more on homogeneous information networks (homogeneous graphs) and have achieved remarkable performance. However, when it takes different aspects of a graph into consideration, especially in heterogeneous information networks (HINs) where multiple types of nodes and edges should be considered, node-level representation learning methods designed for homogeneous information networks are suboptimal and fail to handle the semantic incompatibility brought from HIN. To address the problems mentioned above, this thesis introduces three research works to improve the current graph representation learning methods: 1. We first focus on GNN-based methods and propose Capsule Graph Neural Network (CapsGNN), which is a novel message-passing-based architecture for graph-level representation learning. In this work, the scalar node representations are firstly generated through normal GNNs and then used to generate graph-level representations. Generating a high-quality graph representation should preserve much information such as node position, subgraph direction and node connection, however, encoding this information in the form of scalar means activating elements in a vector one-by-one which is exponentially less efficient than encoding them with distributed representations, so routing mechanism is applied to generate graph-level representations in the form of capsules which can encode graph information more efficiently. An attention module and a coordinate addition module are also introduced to improve the quality of the generated graph representations which is evaluated through the graph classification result. Experiments are also conducted to verify the efficiency of the use of capsules in graph representation learning. 2. Then we look into the graph embedding based methods and focus on node-level representation learning methods especially for the HIN. HIN is a special type of information network (graph) with a stronger description capability and it contains various types of nodes and edges. However, the heterogeneity of HINs also raises the problem of potential semantic incompatibility which might affect the performance of traditional node representation learning algorithms in downstream tasks. To address this issue, a novel graph embedding based HIN representation learning framework named mSHINE is designed to simultaneously learn multiple node representations for different meta-paths (aspects) of the HIN. At the same time, the proposed shared node representations in mSHINE allow compatible information to be shared across different meta-paths which improves the learning efficiency and the learned node representation quality. A set of criteria is also proposed for selecting initial meta-paths for mSHINE which is helpful to reduce the meta-path selection cost. This work is evaluated through node classification and link prediction tasks. 3. By analyzing the advantages and disadvantages of the previously proposed work which include both GNN-based and graph embedding based methods, a novel HIN embedding method named eHIN is proposed. eHIN is designed to address the existing problems in current node representation learning algorithms (including mSHINE) for HIN by combing the techniques from the GNN-based methods. Besides the shared node representations which is proposed from mSHINE, eHIN also applies the convolution-based module and the non-sampling optimization technique to improve the learning efficiency further. The convolution-based module is designed to capture the spatial information of nodes which is realized through the attention mechanism and the meta-path-based sequential information of nodes is preserved through a GRU unit. Node attributes and label information will be preserved in eHIN which shows an important role in some real-world applications. Systematically analyses are conducted to show the learning efficiency of eHIN and the properties of node representations learned from different meta-paths. In each work, we also discussed the performance of the learned graph representations in the corresponding applications such as graph classification, link prediction as well as the node classification, and the proposed methods show promising performance on almost all the tested applications and datasets.