Learning on Graphs

Abstract:

Learning on graphs (a.k.a., graph-based learning) mainly aims to analyze the property of entities (e.g., predict entity attributes) from graphs where entities and entity relations are represented as nodes and edges, respectively. Graph-based learning plays a crucial role in a variety of emerging applications in disciplines including physics, biology, chemistry, social and information science. For instance, in social science, graph-based learning is a typical solution for social network applications such as targeted advertising and recommendation.

Most of the existing graph-based learning methods mainly model graph structure based on a local smoothness assumption, that is closely connected nodes have similar predictions. Specifically, this assumption is typically implemented via either a graph Laplacian regularization or node embedding diffusion over the graph structure. However, in addition to the graph structure, these implementations of local smoothness largely ignore the rich information in graph applications such as various edge attributes, dynamic vertex features, and rich domain knowledge, which contain additional clues for local smoothness.

In this thesis, we investigate techniques to thoroughly mine the graph data to enhance the modeling of local smoothness. In particular, 1) we devise a multi-relation learning framework which improves the modeling of local smoothness by jointly considering multiple types of relations between vertices. 2) We design a new regularization term to encode domain knowledge which could guide the local smoothness modeling. 3) We propose a new neural network operator which adaptively adjusts the strength of smoothness between vertices in a time-aware manner according to the dynamic features of vertices. 4) We develop a new adversarial training approach which aims to enhance the robustness of local smoothness modeling by additionally performing adversarial perturbations on vertex features.

The proposed methods leverage different types of additional information to enhance local smoothness modeling suitable for different kinds of graph applications. Therefore, we apply the methods on different applications to conduct experiments, in particular, 1) university ranking (multiple relations), 2) popularity prediction (domain knowledge), 3) stock ranking (dynamic vertex features), and 4) conventional node classification applications (adversarial perturbations). Extensive experiments demonstrate the effectiveness of the proposed methods and validate the necessity of jointly encoding graph structure along with additional information for local smoothness modeling.