MACHINE LEARNING WITH GRAPHS

Abstract

In recent years, graph-based machine learning methods have attracted great attention because of their effectiveness and efficiency. Inspired by this trend, this thesis summarizes my research topics on machine learning techniques for the purpose of handling various kinds of problems on large graph data. Generally, this thesis contains two parts. The first part is devoted to graph embedding, which aims to encode graph structure into dense vectors (or embeddings). In particular, we will consider a low rank-matrix factorization based approach to learn embeddings of attributed graphs. By jointly preserving graph structure and attribute-level similarity, our approach can generate embeddings, whose quality is higher than that of embeddings generated by state-of-the-art methods. The second part of the thesis is devoted to graph-based semi-supervised learning, which attempts to predict labels for unlabeled nodes given a small set of labeled nodes and a large set of unlabeled nodes. In this part, we consider two different approaches: graph-regularization based semi-supervised learning and graph convolutional network, which deal with non-attributed and attributed graphs respectively. For graph-regularization based semi-supervised learning, we develop a simple approach for imbalanced classification, which can not only learn a smooth label function on the graph but also take into account the class imbalance of datasets. For graph convolutional network, we first introduce an attention mechanism induced by sub-maximal entropy random walks. Given this, we propose an attention-based graph convolutional network, which can jointly learn node attributes and graph structures at multiply scales. Both approaches can achieve promising performance on several benchmark datasets.