Learning on Graphs

Abstract:

Learning on graphs (a.k.a., graph-based learning) is mainly to analyze the property of entities (e.g., predict entity attributes and forecast potential links) from graphs where entities and entity relations are represented as nodes and edges. Learning on graph 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, learning on graphs is a typical solution for predicting the attributes (e.g., interest) of users and identifying the potential connection between users, which are useful for targeted advertising and recommendation.

Most of the existing methods for graph-based learning focus on the modeling of graph structure, mainly on the connectedness between node pairs. The existing methods are mainly based on local smoothness assumption which assumes that closely connected nodes have similar predictions in node classification. Traditionally, this assumption is implemented via a graph Laplacian regularization which incurs a large penalty when closely connected nodes are predicted with different labels. As the recent development of embedding techniques and deep neural networks, achieving the assumption via encouraging connected nodes to obtain similar embeddings has become the promising solution.

However, the core of learning on graphs is the jointly modeling of graph structure, vertex features, and side information. The existing methods only focus on graph structure and largely ignore other information, including various edge attributes, dynamic vertex features, and rich domain knowledge. Therefore, the existing methods would be suboptimal solutions for many graph applications. For instance, the existing methods that ignore edge attributes would be unsuitable for modeling user interests in a social network where users have multiple types of relations such as following, like, and comment.

In this thesis proposal, we investigate techniques to thoroughly model the graph data so as to learn comprehensive vertex representations and 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. 2) We design a new regularization term to encode domain knowledge and guide the local smoothness. 2) We propose a new neural network operator which adaptively adjusts the strength of smoothness between vertices according to the temporal features of vertices. 4) We develop a new training approach which can enhance the robustness of modeling local smoothness with deep neural networks by defending intentional perturbations on vertex features.

As the proposed methods focus on different types of information, we apply them on different applications to conduct experiments, including university ranking (multiple relations), stock ranking (dynamic vertex features), popularity prediction (partial-order rules) and conventional node classification applications. Experimental results demonstrate the effectiveness of the proposed methods and verify the necessity of jointly modeling graph structure, vertex features, and side information.